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:


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.


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:

struct Atom {
	enum {
	} type;

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

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

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;


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

> (define square (lambda (x) (* x x)))
> (square 3)
> (square 4)

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

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

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))))
> (define add-two (make-adder 2))
> (add-two 5)

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