Built-in functions

So far in our implementation, we have made use of the functions car, cdr and cons to construct and access LISP data. Now, we will make the same functionality available within the interpreted environment.

We shall extend the list expression syntax to add some new operators:

(CAR EXPR)

Evaluates EXPR and returns the car of the result. It is an error if EXPR does not evaluate to a pair or NIL.

(CDR EXPR)

Evaluates EXPR and returns the cdr of the result. It is an error if EXPR does not evaluate to a pair or NIL.

(CONS A B)

Evaluates both arguments A and B, and returns a newly constructed pair containing the results.

In the definitions above we allow taking the car and cdr of NIL, unlike our C versions. Some algorithms are simpler to express if the car and cdr of NIL are defined to be NIL.

We could choose to implement these by adding more special cases to eval_expr, just like we did with QUOTE and DEFINE. However, we will want to add more operators in the future — and adding each one to eval_expr would cause the function to get very long. The alternative is to introduce the concept of functions.

Functions

A function is a recipe for converting arguments into a value. If eval_expr encounters a list expression with a function as the operator, all it has to do is follow the recipe to come up with a value to use as the result of the expression.

One way to implement these recipes is to create C functions which can be called from eval_expr. We will call these built-in or primitive functions. Let's see how to extend our LISP interpreter to accommodate these.

A new type of atom

eval_expr will call built-in functions through a C function pointer, so they must all have the same prototype:

typedef int (*Builtin)(struct Atom args, struct Atom *result);

In order to appear in expressions, we need a new kind of atom to represent them.

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

	union {
		.
		.
		.
		Builtin builtin;
	} value;
};

For completeness, print_expr needs to know how to display the new atom:

void print_expr(Atom atom)
{
	switch (atom.type) {
	.
	.
	.
	case AtomType_Builtin:
		printf("#<BUILTIN:%p>", atom.value.builtin);
		break;
	}
}

And finally a helper function to create atoms of the new type:

Atom make_builtin(Builtin fn)
{
	Atom a;
	a.type = AtomType_Builtin;
	a.value.builtin = fn;
	return a;
}

Extending the evaluator

We will need to create a shallow copy of the argument list.

Atom copy_list(Atom list)
{
	Atom a, p;

	if (nilp(list))
		return nil;

	a = cons(car(list), nil);
	p = a;
	list = cdr(list);

	while (!nilp(list)) {
		cdr(p) = cons(car(list), nil);
		p = cdr(p);
		list = cdr(list);
	}

	return a;
}

apply simply calls the builtin function with a supplied list of arguments. We will extend this function later when we want to deal with other kinds of evaluation recipe.

int apply(Atom fn, Atom args, Atom *result)
{
	if (fn.type == AtomType_Builtin)
		return (*fn.value.builtin)(args, result);

	return Error_Type;
}

If a list expression is not one of the special forms we defined previously, then we will assume that the operator is something which evaluates to a function. We will also evaluate each of the arguments, and use apply to call that function with the list of results.

int eval_expr(Atom expr, Atom env, Atom *result)
{
	Atom op, args, p;
	Error err;

	.
	.
	.

	if (op.type == AtomType_Symbol) {
		.
		.
		.
	}

	/* Evaluate operator */
	err = eval_expr(op, env, &op);
	if (err)
		return err;

	/* Evaulate arguments */
	args = copy_list(args);
	p = args;
	while (!nilp(p)) {
		err = eval_expr(car(p), env, &car(p));
		if (err)
			return err;

		p = cdr(p);
	}

	return apply(op, args, result);
}

The argument list is copied before being overwritten with the results of evaluating the arguments. We don't want to overwrite the original argument list in case we need to use the form again in the future.

Initial environment

Previously we created an empty environment for the read-eval-print loop. The user has no way of creating atoms which represent builtin functions, so we populate the initial environment with bindings for our builtins.

The functions themselves:

int builtin_car(Atom args, Atom *result)
{
	if (nilp(args) || !nilp(cdr(args)))
		return Error_Args;

	if (nilp(car(args)))
		*result = nil;
	else if (car(args).type != AtomType_Pair)
		return Error_Type;
	else
		*result = car(car(args));

	return Error_OK;
}

Almost all of the function is code to deal with errors and type checking! Creating functions in this way is pretty tedious.

int builtin_cdr(Atom args, Atom *result)
{
	if (nilp(args) || !nilp(cdr(args)))
		return Error_Args;

	if (nilp(car(args)))
		*result = nil;
	else if (car(args).type != AtomType_Pair)
		return Error_Type;
	else
		*result = cdr(car(args));

	return Error_OK;
}

builtin_cdr is almost identical to builtin_car.

int builtin_cons(Atom args, Atom *result)
{
	if (nilp(args) || nilp(cdr(args)) || !nilp(cdr(cdr(args))))
		return Error_Args;

	*result = cons(car(args), car(cdr(args)));

	return Error_OK;
}

With these defined, we can at last use env_set to create the bindings.

int main(int argc, char **argv)
{
	Atom env;
	char *input;

	env = env_create(nil);

	/* Set up the initial environment */
	env_set(env, make_sym("CAR"), make_builtin(builtin_car));
	env_set(env, make_sym("CDR"), make_builtin(builtin_cdr));
	env_set(env, make_sym("CONS"), make_builtin(builtin_cons));

	while ((input = readline("> ")) != NULL) {
		.
		.
		.
	}

	return 0;
}

Testing

> (define foo 1)
FOO
> (define bar 2)
BAR
> (cons foo bar)
(1 . 2)
> (define baz (quote (a b c)))
BAZ
> (car baz)
A
> (cdr baz)
(B C)

Notice that (CONS FOO BAR) is not the same as (QUOTE (FOO . BAR)). In the former expression, the arguments are evaluated and a new pair is created.