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.

// eval_expr evaluates an expression with a given environment and updates the result.
// note that the result may not be updated if we find errors.
func eval_expr(expr, env Atom, result *Atom) error {
    .
    .
    .
    op, args := car(expr), cdr(expr)
    if op._type == AtomType_Symbol {
        // evaluate special forms
        if op.value.symbol.EqualString("QUOTE") {
            .
            .
            .
        } else if op.value.symbol.EqualString("IF") {
            // verify number and type of arguments
            if nilp(args) || nilp(cdr(args)) || nilp(cdr(cdr(args))) || !nilp(cdr(cdr(cdr(args)))) {
                return Error_Args
            }
            var cond Atom
            if err := eval_expr(car(args), env, &cond); err != nil {
                return err
            }
            var val Atom
            if nilp(cond) {
                val = car(cdr(cdr(args)))
            } else {
                val = 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_create_default creates a new environment with some native
// functions added to the symbol table.
func env_create_default() Atom {
    .
    .
    .
    env_set(env, make_sym([]byte{'T'}), make_sym([]byte{'T'}))

    // return the new environment
    return env
}

Remember that make_sym will return the same symbol object if it is called multiple times with identical strings.

Testing

Unlike Go, zero in a boolean test is true, not a compiler error.

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.

// builtin_numeq implements a comparison operator for numbers,
// returning T if they are equal.
// note that the result may not be updated if we find errors.
func builtin_numeq(args Atom, result *Atom) error {
    // verify number and type of arguments
    if nilp(args) || nilp(cdr(args)) || !nilp(cdr(cdr(args))) {
        return Error_Args
    }
    a, b := car(args), car(cdr(args))
    if a._type != AtomType_Integer || b._type != AtomType_Integer {
        return Error_Type
    }

    if a.value.integer == b.value.integer {
        // todo: should be able to assume that T is in the environment
        *result = make_sym([]byte{'T'})
    } else {
        *result = _nil
    }
    return nil
}

builtin_less follows the same pattern and is not shown here.

Finally we must add them to the initial environment.

// env_create_default creates a new environment with some native
// functions added to the symbol table.
func env_create_default() Atom {
    .
    .
    .
    env_set(env, make_sym([]byte{'='}), make_builtin(builtin_numeq))
    env_set(env, make_sym([]byte{'<'}), make_builtin(builtin_less))

    // return the new environment
    return env
}

Testing

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:

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.

func TestChapter08(t *testing.T) {
    env := env_create_default()

    for _, tc := range []struct {
        id     int
        input  string
        expect string
        err    error
    }{
        {id: 1, input: "(if t 3 4)", expect: "3"},
        {id: 2, input: "(if nil 3 4)", expect: "4"},
        {id: 3, input: "(if 0 t nil)", expect: "T"},
        {id: 4, input: "(= 3 3)", expect: "T"},
        {id: 5, input: "(< 11 4)", expect: "NIL"},
        {id: 6, input: "(define fact (lambda (x) (if (= x 0) 1 (* x (fact (- x 1))))))", expect: "FACT"},
        {id: 7, input: "(fact 10)", expect: "3628800"},
        {id: 8, input: "(if (= (fact 10) 3628800) (quote passed) (quote failed))", expect: "PASSED"},
    } {
        var expr Atom
        _, err := read_expr([]byte(tc.input), &expr)
        if err != nil {
            t.Errorf("%d: read error: want nil: got %v\n", tc.id, err)
            continue
        }

        var result Atom
        err = eval_expr(expr, env, &result)

        if tc.err == nil && err == nil {
            // yay
        } else if tc.err == nil && err != nil {
            t.Errorf("%d: error: want nil: got %v\n", tc.id, err)
        } else if !errors.Is(err, tc.err) {
            t.Errorf("%d: error: want %v: got %v\n", tc.id, tc.err, err)
        }
        if got := result.String(); tc.expect != got {
            t.Errorf("%d: eval: want %q: got %q\n", tc.id, tc.expect, got)
        }
    }
}