# 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)
```
where `test`, `true-expr` and `false-expr` are arbitrary expressions. If the result of evaluating `test` is considered to be true, then the result of the `IF`-expression is the result of evaluating `true-expr`, otherwise it is the result of evaluating `false-expr`. Only one of `true-expr` and `false-expr` is evaluated; the other expression is ignored.

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"));
```
Remember that `make_sym` will return the same symbol object if it is called multiple times with identical strings.

#### 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
```
I have cheated a little here: the REPL does not allow the user to enter multi-line expressions, so you must enter the definition for `fact` all on one line.

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.