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...)

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

struct Atom {
	enum {
		.
		.
		.
		AtomType_Closure
	} type;

	union {
		.
		.
		.
	} 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.

int make_closure(Atom env, Atom args, Atom body, Atom *result)
{
	Atom p;

	if (!listp(args) || !listp(body))
		return Error_Syntax;

	/* Check argument names are all symbols */
	p = args;
	while (!nilp(p)) {
		if (car(p).type != AtomType_Symbol)
			return Error_Type;
		p = cdr(p);
	}

	*result = cons(env, cons(args, body));
	result->type = AtomType_Closure;

	return Error_OK;
}

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

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, "LAMBDA") == 0) {
			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))

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

int apply(Atom fn, Atom args, Atom *result)
{
	Atom env, arg_names, body;

	if (fn.type == AtomType_Builtin)
		return (*fn.value.builtin)(args, result);
	else if (fn.type != AtomType_Closure)
		return Error_Type;

	env = env_create(car(fn));
	arg_names = car(cdr(fn));
	body = cdr(cdr(fn));

	/* Bind the arguments */
	while (!nilp(arg_names)) {
		if (nilp(args))
			return Error_Args;
		env_set(env, car(arg_names), car(args));
		arg_names = cdr(arg_names);
		args = cdr(args);
	}
	if (!nilp(args))
		return Error_Args;

	/* Evaluate the body */
	while (!nilp(body)) {
		Error err = eval_expr(car(body), env, result);
		if (err)
			return err;
		body = cdr(body);
	}

	return Error_OK;
}

Testing

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

> (define square (lambda (x) (* x x)))
SQUARE
> (square 3)
9
> (square 4)
16

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

> ((lambda (x) (- x 2)) 7)
5

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

> (define make-adder (lambda (x) (lambda (y) (+ x y))))
MAKE-ADDER
> (define add-two (make-adder 2))
ADD-TWO
> (add-two 5)
7

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