Expressions, Environment and Evaluation

Expressions

LISP is all about expressions. An expression can be a literal, an identifier, or a list consisting of an operator and one or more arguments.

A literal is an object with an intrinsic value. In our system, that's either an integer or NIL (if you consider "nothing" to be a value).

An identifier is a name for an object. Symbols can be identifiers.

Everything else is a list of the form (operator argument...) where argument... means zero or more arguments.

Environment

To associate identifiers with objects we need an environment. This is a collection of bindings, each of which consists of an identifier and its corresponding value. For example:

Bindings
Identifier	Value
`FOO`	`42`
`BAR`	`NIL`
`BAZ`	`(X Y Z)`

Note that the identifiers are all symbols, but the values can be any object within our system of data — the value for BAZ is a list containing three symbols.

An environment can also have a parent environment. If there is no binding for a particular identifier in the environment, we can check the parent, the parent's parent and so on. In this way we can create a tree of environments which share bindings with their ancestors unless explicit replacements exist.

Implementation

There is a convenient way of representing environments using our LISP data types:

(parent (identifier . value)...)

So the environment above (assuming it has no parent) is:

(NIL (FOO . 42) (BAR . NIL) (BAZ . (X Y Z)))

Here is a function to create an empty environment with a specified parent (which could be NIL):

// env_create creates a new environment.
// if parent is not NIL, then parent is added to the environment.
func env_create(parent Atom) Atom {
    return cons(parent, _nil)
}

Next we have two functions to retrieve and create bindings in an environment.

// env_get retrieves the binding for a symbol from the environment.
// does not update result unless it finds a symbol in the environment.
func env_get(env, symbol Atom, result *Atom) error {
    for bs := cdr(env); !nilp(bs); bs = cdr(bs) {
        if b := car(bs); car(b).value.symbol == symbol.value.symbol {
            *result = cdr(b)
            return nil
        }
    }
    // search the parent environment (if we have one).
    if parent := car(env); !nilp(parent) {
        return env_get(parent, symbol, result)
    }
    // not found, so return an unbound error
    return Error_Unbound
}

Disallowing duplicate symbols means that we don't have to call strcmp here, which should mean that this lookup function is not too slow.

// env_set creates a binding for a symbol in the environment.
func env_set(env, symbol, value Atom) {
    for bs := cdr(env); !nilp(bs); bs = cdr(bs) {
        if b := car(bs); car(b).value.symbol == symbol.value.symbol {
            b.value.pair.cdr = value
            return
        }
    }
    setcdr(env, cons(cons(symbol, value), cdr(env)))
}

Only env_get recursively checks the parent environments. We don't want to modify the bindings of parents.

Evaluation

Now that we have expressions, we can start to evaluate them. Evalution is a process which takes an expression and an environment, and produces a value (the result). Let's specify the rules.

A literal will evaluate to itself.
The environment allows us to determine a value for an identifier. Attempting to evaluate an identifier for which no binding exists is an error.
A list expression with one of the following operators is called a special form:

QUOTE

The result of evaluating (QUOTE EXPR) is EXPR, which is returned without evaluating.

DEFINE

Evaluating (DEFINE SYMBOL EXPR) creates a binding for SYMBOL (or modifies an existing binding) in the evaluation environment. SYMBOL is bound to the value obtained by evaluating EXPR. The final result is SYMBOL.
Anything else, including list expressions with any other operator, is invalid.

Implementation

We will need to check whether an expression is a proper list.

// listp returns true if the expression is a proper list or is NIL.
func listp(expr Atom) bool {
    for ; !nilp(expr); expr = cdr(expr) {
        if expr._type != AtomType_Pair {
            return false
        }
    }
    return true
}

We need to add a few more entries to our list of errors:

// Error_Args is returned when a list expression was shorter or longer than anticipated.
Error_Args = fmt.Errorf("args")

// Error_Type is returned when an object in an expression isn't the expected type.
Error_Type = fmt.Errorf("type")

// Error_Unbound is returned when we attempt to evaluate an unbound symbol.
Error_Unbound = fmt.Errorf("unbound")

The function to perform evaluation is now a straightforward translation of the rules into Go.

// 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 {
    if expr._type == AtomType_Symbol {
        return env_get(env, expr, result)
    } else if expr._type != AtomType_Pair {
        *result = expr
        return nil
    } else if !listp(expr) {
        return Error_Syntax
    }

    op, args := car(expr), cdr(expr)
    if op._type == AtomType_Symbol {
        // evaluate special forms
        if op.value.symbol.EqualString("QUOTE") {
            if nilp(args) || !nilp(cdr(args)) {
                return Error_Args
            }
            *result = car(args)
            return nil
        } else if op.value.symbol.EqualString("DEFINE") {
            if nilp(args) || nilp(cdr(args)) || !nilp(cdr(cdr(args))) {
                return Error_Args
            }
            sym := car(args)
            if sym._type != AtomType_Symbol {
                return Error_Type
            }
            var val Atom
            if err := eval_expr(car(cdr(args)), env, &val); err != nil {
                return err
            }
            env_set(env, sym, val)
            *result = sym
            return nil
        }
    }

    return Error_Syntax
}

Testing

Let's create some test cases and verify that it works.

ID	Input	Output
1	foo	error: unbound
2	(quote foo)	FOO
3	(define foo 42)	FOO
4	foo	42
5	(define foo (quote bar))	FOO
6	foo	BAR

func TestChapter04(t *testing.T) {
    env := env_create(_nil)

    for _, tc := range []struct {
        id     int
        input  string
        expect string
        err    error
    }{
        {id: 1, input: "foo", expect: "NIL", err: Error_Unbound},
        {id: 2, input: "(quote foo)", expect: "FOO"},
        {id: 3, input: "(define foo 42)", expect: "FOO"},
        {id: 4, input: "foo", expect: "42"},
        {id: 5, input: "(define foo (quote bar))", expect: "FOO"},
        {id: 6, input: "foo", expect: "BAR"},
    } {
        expr, _, err := read_expr([]byte(tc.input))
        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)
        }
    }
}

We can now assign names to objects.