Booleans and short-circuit evaluation

Booleans

(Apologies if you are a logician and I've got this all wrong...)

A boolean value is one of two classes of values which are called true and false. If we wish to interpret a value as a boolean, we consider it to be true if it is in the class of true values, and false otherwise.

Short-circuit evalutaion

So far every expression we pass to eval is evaluated. With the exception of special forms such as DEFINE and LAMBDA, which store away expressions to be evaluated later, eval must walk the whole tree before returning a result.

In this chapter we will define yet another special form IF, which will cause eval to choose which of two possible expressions to evaluate, and discard the other.

The syntax is as follows:

(IF test true-expr false-expr)

But what kind of value is true? In our environment we will define NIL to be false. Any other value is true.

Here is the code to handle IF-expressions.

int eval_expr(Atom expr, Atom env, Atom *result)
{
	.
	.
	.
	if (op.type == AtomType_Symbol) {
		if (strcmp(op.value.symbol, "QUOTE") == 0) {
		.
		.
		.
		} else if (strcmp(op.value.symbol, "IF") == 0) {
			Atom cond, val;

			if (nilp(args) || nilp(cdr(args)) || nilp(cdr(cdr(args)))
					|| !nilp(cdr(cdr(cdr(args)))))
				return Error_Args;

			err = eval_expr(car(args), env, &cond);
			if (err)
				return err;

			val = nilp(cond) ? car(cdr(cdr(args))) : car(cdr(args));
			return eval_expr(val, env, result);
		}
	}
	.
	.
	.
}

The argument check is getting a little unwieldy. A couple of alternatives are to modify car and cdr to return NIL if the argument is not a pair and forego the syntax check, or to create a helper function to count the list length. It won't get any worse than this, though — so let's not waste time on it.

Traditionally LISP functions return the symbol T if they need to return a boolean value and there is no obvious object available. T is bound to itself, so evaluating it returns the symbol T again. A symbol is not NIL, and so is true.

Add a binding for T to the initial environment:

env_set(env, make_sym("T"), make_sym("T"));

Testing

> (if t 3 4)
3
> (if nil 3 4)
4
> (if 0 t nil)
T

Unlike C, zero is true, not false.

Predicates

While we could stop here, it would be useful to make some tests other than "is it NIL". This is where predicates come in. A predicate is a function which returns a true/false value according to some condition.

We will define two built-in predicates, "=" which tests for numerical equality, and "<" which tests if one number is less than another.

The functions are similar to our other numerical built-ins.

int builtin_numeq(Atom args, Atom *result)
{
	Atom a, b;

	if (nilp(args) || nilp(cdr(args)) || !nilp(cdr(cdr(args))))
		return Error_Args;

	a = car(args);
	b = car(cdr(args));

	if (a.type != AtomType_Integer || b.type != AtomType_Integer)
		return Error_Type;

	*result = (a.value.integer == b.value.integer) ? make_sym("T") : nil;

	return Error_OK;
}

builtin_less follows the same pattern and is not shown here.

Finally we must add them to the initial environment.

env_set(env, make_sym("="), make_builtin(builtin_numeq));
env_set(env, make_sym("<"), make_builtin(builtin_less));

Testing

> (= 3 3)
T
> (< 11 4)
NIL

Barring memory and stack limitations, our LISP environment is now Turing-complete! If you have been entering the code as we go along, you can confirm that we have implemented the core of a usable programming language in well under 1,000 lines of C code.

A classic demonstration:

> (define fact
    (lambda (x)
      (if (= x 0)
        1
        (* x (fact (- x 1))))))
FACT
> (fact 10)
3628800

There is more to do yet, though. LISP has other features which make it possible to express some really interesting stuff, and there are a few loose ends to tidy up as well.