Lambda expressions and closures

This is where things start to get interesting. We will now implement support for lambda expressions, a way to build functions dynamically out of the LISP expressions we can already deal with.

A lambda expression is a list expression with a particular syntax:

(LAMBDA (arg...) expr...)

The result of evaluating a LAMBDA expression is a new kind of object which we will call a closure. A closure can be used in list expressions in the same way as a built-in function. In this case the arguments will be bound to the symbols listed as arg... in the lambda expression. The body of the function consists of the expressions expr..., which will be evaluated in turn. The result of evaluating the final expression is the result of applying the arguments to the closure.

That's a pretty dense definition, so here is an example of how we would like to use lambda expressions:

(DEFINE SQUARE (LAMBDA (X) (* X X)))

SQUARE should now be a function of one argument X, which returns the result of evaluating (* X X). Thus evaluating (SQUARE 3) should return 9.

Implementation

We will represent the closure using a list:

(env (arg...) expr...)

env is the environment in which the closure was defined. This is needed to allow the lambda function to use bindings without having to pass them as arguments. For example, recall that CAR is bound in the initial environment to our primitive builtin_car function.

The first task is to add a new constant for the type field of our Atom structure:

// AtomType is the enum for the type of value in a cell.
type AtomType int

const (
    .
    .
    .
    AtomType_Closure
    .
    .
    .
)

Since the closure is just a regular list, there is no need to add anything to value.

Like our other atom types, we will create a utility function to initialize them. make_closure, unlike the others, performs some validation of the arguments and so needs to return an error code.

// make_closure returns an Atom on the stack.
// a closure is a list that binds the environment and arguments.
// note that result may not be updated if there are errors.
func make_closure(env, args, body Atom, result *Atom) error {
    // verify number and type of arguments
    if !listp(args) || !listp(body) {
        return Error_Syntax
    }
    // verify that all arguments are all symbols.
    // if not, return an error.
    for p := args; !nilp(p); p = cdr(p) {
        if car(p)._type != AtomType_Symbol {
            return Error_Type
        }
    }

    // bind the environment and arguments to the closure
    *result = Atom{
        _type: AtomType_Closure,
        value: AtomValue{
            pair: &Pair{
                car: env,
                cdr: cons(args, body),
            },
        },
    }
    return nil
}

Next up is another special case in eval to create a closure whenever a lambda expression is encountered.

// 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("DEFINE") {
            .
            .
            .
        } else if op.value.symbol.EqualString("LAMBDA") {
            // verify number and type of arguments
            if nilp(args) || nilp(cdr(args)) {
                return Error_Args
            }
            return make_closure(env, car(args), cdr(args), result)
        }
    }
    .
    .
    .
}

The body of our SQUARE example above is expressed in terms of X. In order to evaluate the body, we need to create a new environment with X bound to the value of the argument:

(closure-env (X . 3))

where the parent environment closure-env is the environment that was stored in the closure.

Finally we extend apply to create the new environment and call eval for each expression in the body.

// apply calls a native function with a list of arguments and updates the result.
// note that the result may not be updated if we find errors.
func apply(fn, args Atom, result *Atom) error {
    // handle builtins
    if fn._type == AtomType_Builtin {
        return fn.value.builtin.fn(args, result)
    }

    // handle closure
    if fn._type == AtomType_Closure {
        // create a new environment for the closure
        env := env_create(car(fn))

        // bind the arguments
        for arg_names := car(cdr(fn)); !nilp(arg_names); arg_names = cdr(arg_names) {
            if nilp(args) {
                // not enough arguments passed in to bind against
                return Error_Args
            }
            // put the name and value into the environment
            env_set(env, car(arg_names), car(args))
            // move on to the next argument
            args = cdr(args)
        }
        if !nilp(args) {
            // too many arguments to bind against
            return Error_Args
        }

        // evaluate every expression in the body
        for body := cdr(cdr(fn)); !nilp(body); body = cdr(body) {
            if err := eval_expr(car(body), env, result); err != nil {
                return err
            }
        }

        return nil
    }

    // any other type is an error
    return Error_Type
}

Testing

Let's check that our SQUARE function works as intended.

Of course, lambda expressions do not have to be bound to a symbol — we can create anonymous functions.

Fans of functional programming will be pleased to see that we can now do this kind of thing:

Do you know where the value "2" is stored?

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

	for _, tc := range []struct {
		id     int
		input  string
		expect string
		err    error
	}{
		{id: 1, input: "(define square (lambda (x) (* x x)))", expect: "SQUARE"},
		{id: 2, input: "(square 3)", expect: "9"},
		{id: 3, input: "(square 4)", expect: "16"},
		{id: 4, input: "((lambda (x) (- x 2)) 7)", expect: "5"},
		{id: 5, input: "(define make-adder (lambda (x) (lambda (y) (+ x y))))", expect: "MAKE-ADDER"},
		{id: 6, input: "(define add-two (make-adder 2))", expect: "ADD-TWO"},
		{id: 7, input: "(add-two 5)", expect: "7"},
	} {
		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)
		}
	}
}