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 Go 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 Go 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:

// Builtin is a helper for calling a native Go function.
// We define a struct around it so that we can do
// pointer comparisons for equality in other parts of this package.
type Builtin struct {
    fn Native
}

// Native is a function in Go that can evaluate expressions.
type Native func(args Atom) (Atom, error)

In order to appear in expressions, we need a new kind of atom to represent them. We'll add a new enum to our AtomType:

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

const (
    // Nil represents the empty list.
    AtomType_Nil AtomType = iota
    // Builtin is a native function.
    AtomType_Builtin
    .
    .
    .

Sections of code which we wrote previously are abbreviated as vertical ellipsis (". . .").

And then add it to our Atom struct:

// AtomValue is the value of an Atom.
// It can be a simple type, like an integer or symbol, or a pointer to a Pair.
type AtomValue struct {
    builtin *Builtin
    integer int
    pair    *Pair
    symbol  *Symbol
}

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

// Write writes the value of an Atom to the writer.
// If the atom is a pair, Write is called recursively
// to write out the entire list.
func (a Atom) Write(w io.Writer) (int, error) {
    switch a._type {
    case AtomType_Nil:
        // atom is nil, so write "NIL"
        return w.Write([]byte{'N', 'I', 'L'})
    case AtomType_Builtin:
        // atom is a native function
        return w.Write([]byte(fmt.Sprintf("#<BUILTIN:%p>", a.value.builtin)))
    .
    .
    .

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

// make_builtin returns an Atom on the stack.
func make_builtin(fn Native) Atom {
    return Atom{
        _type: AtomType_Builtin,
        value: AtomValue{
            builtin: &Builtin{
                fn: fn,
            },
        },
    }
}

Extending the evaluator

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

// copy_list returns a shallow copy of a list.
// todo: define "shallow copy" and why we would create one.
func copy_list(list Atom) Atom {
    if nilp(list) {
        return _nil
    }
    a := cons(car(list), _nil)
    p := a
    for list = cdr(list); !nilp(list); list = cdr(list) {
        setcdr(p, cons(car(list), _nil))
        p = cdr(p)
    }
    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.

// 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 {
    if fn._type != AtomType_Builtin {
        // it is an error to call this with anything other than a builtin
        return Error_Type
    }
    return fn.value.builtin.fn(args, result)
}

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.

// eval_expr evaluates an expression with a given environment.
// it returns the result and any errors.
func eval_expr(expr, env Atom) (Atom, error) {
    .
    .
    .

    op, args := car(expr), cdr(expr)
    if op._type == AtomType_Symbol {
        .
        .
        .
    }

    // evaluate and update the operator
    if err := eval_expr(op, env, &op); err != nil {
        return err
    }

    // evaluate arguments by calling eval on a copy of each.
    // we have to make the copy, so we don't destroy the input.
    args = copy_list(args)
    for arg := args; !nilp(arg); arg = cdr(arg) {
        // evaluate the arg and update its value
        if err := eval_expr(car(arg), env, &arg.value.pair.car); err != nil {
            return err
        }
    }

    // return the result of applying eval on our operator and arguments
    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:

// builtin_car makes our native car function available to the interpreter.
// note that the result may not be updated if we find errors.
func builtin_car(args Atom, result *Atom) error {
    // verify number and type of arguments
    if nilp(args) || !nilp(cdr(args)) {
        return Error_Args
    } else if car(args)._type != AtomType_Pair {
        return Error_Type
    }

    if nilp(car(args)) {
        *result = _nil
    } else {
        *result = car(car(args))
    }
    return nil
}

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

// builtin_cdr makes our native cdr function available to the interpreter.
// note that the result may not be updated if we find errors.
func builtin_cdr(args Atom, result *Atom) error {
    // verify number and type of arguments
    if nilp(args) || !nilp(cdr(args)) {
        return Error_Args
    } else if car(args)._type != AtomType_Pair {
        return Error_Type
    }

    if nilp(car(args)) {
        *result = _nil
    } else {
        *result = cdr(car(args))
    }
    return nil
}

builtin_cdr is almost identical to builtin_car.

// builtin_cons makes our native cons function available to the interpreter.
// note that the result may not be updated if we find errors.
func builtin_cons(args Atom, result *Atom) error {
    // verify number and type of arguments
    if nilp(args) || nilp(cdr(args)) || !nilp(cdr(cdr(args))) {
        return Error_Args
    }

    *result = cons(car(args), car(cdr(args)))
    return nil
}

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

// env_create_default creates a new environment with some native
// functions added to the symbol table.
func env_create_default() Atom {
    // create a new environment
    env := env_create(_nil)
    // add the default list of native functions to the environment
    env_set(env, make_sym([]byte("CAR")), make_builtin(builtin_car))
    env_set(env, make_sym([]byte("CDR")), make_builtin(builtin_cdr))
    env_set(env, make_sym([]byte("CONS")), make_builtin(builtin_cons))
    // return the new environment
    return env
}

Testing

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.

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

    for _, tc := range []struct {
        id     int
        input  string
        expect string
        err    error
    }{
        {id: 1, input: "(define foo 1)", expect: "FOO"},
        {id: 2, input: "(define bar 2)", expect: "BAR"},
        {id: 3, input: "(cons foo bar)", expect: "(1 . 2)"},
        {id: 4, input: "(define baz (quote (a b c)))", expect: "BAZ"},
        {id: 5, input: "(car baz)", expect: "A"},
        {id: 6, input: "(cdr baz)", expect: "(B C)"},
    } {
        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)
        }
    }
}