Library

We will now create a small library of useful functions for our LISP system. Rather than creating new builtins for each one, let's take advantage of the fact that much of the LISP standard library can be implemented in LISP itself in terms of lower-level functions.

First we need a function to read the library definitions from disk. And a routine, similar to our REPL in main, to process the definitions. Because we read the whole file in one go, there is no problem with splitting definitions over several lines.

func load_file(env Atom, path string) error {
    fmt.Printf("Reading %s...\n", path)
    input, err := os.ReadFile(path)
    if err != nil {
        return err
    }

    var expr Atom
    rest, err := read_expr(input, &expr)
    for ; err == nil; rest, err = read_expr(rest, &expr) {
        var result Atom
        if err := eval_expr(expr, env, &result); err != nil {
            fmt.Printf("error: %s in expression:\n\t%s\n", err, expr.String())
        } else {
            fmt.Printf("%s\n", result.String())
        }
    }
    if err != nil && err != Error_EndOfInput {
        fmt.Printf("error: %s in expression:\n\t%s\n", err, expr.String())
    }

    return nil
}

Finally read in the library after setting up the builtins.

func TestChapter12(t *testing.T) {
    env := env_create_default()
    if err := load_file(env, "library.lisp"); err != nil {
        t.Errorf("error: want nil: got %v\n", err)
    }
    .
     .
    .
}

Testing

Create library.lisp with the following definition:

(define (abs x) (if (< x 0) (- x) x))

And run the interpreter:

Reading library.lisp...
ABS
> (abs -2)
2

The ABS function will now be available in every session without having to define it each time.

fold

foldl and foldr allow us to easily construct functions which combine elements of a list.

(define (foldl proc init list)
  (if list
      (foldl proc
             (proc init (car list))
             (cdr list))
      init))

(define (foldr proc init list)
  (if list
      (proc (car list)
            (foldr proc init (cdr list)))
      init))

See the internet for more details.

(define (list . items)
  (foldr cons nil items))

(define (reverse list)
  (foldl (lambda (a x) (cons x a)) nil list))

list constructs a new list containing its arguments. reverse creates a copy of a list with the items in reverse order.

The recursive definition of LIST requires O(n) stack space - a serious implementation would most likely use a more efficient version.

Testing

> (list (+ 3 5) 'foo)
(8 FOO)
> (reverse '(1 2 3))
(3 2 1)

See how much easier this was than implementing the functions as builtins.

More builtins

Some primitive functions require access to the internals of the system.

apply

The apply function:

(APPLY fn arg-list)

calls fn with the arguments bound to the values in the list arg-list.

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

eq?

eq? tests whether two atoms refer to the same object.

// builtin_eq tests whether two atoms refer to the same object.
// note that the result may not be updated if we find errors.
func builtin_eq(args Atom, result *Atom) error {
    // verify number and type of arguments
    if nilp(args) || nilp(cdr(args)) || !nilp(cdr(cdr(args))) {
        return Error_Args
    }

    // todo: should be able to assume that T is in the environment
    a, b, t := car(args), car(cdr(args)), make_sym([]byte{'T'})
    if a._type != b._type {
        *result = _nil
        return nil
    }
    switch a._type {
    case AtomType_Nil:
        *result = t
    case AtomType_Builtin:
        if a.value.builtin != b.value.builtin {
            *result = _nil
        } else {
            *result = t
        }
    case AtomType_Closure:
        if a.value.pair != b.value.pair {
            *result = _nil
        } else {
            *result = t
        }
    case AtomType_Integer:
        if a.value.integer != b.value.integer {
            *result = _nil
        } else {
            *result = t
        }
    case AtomType_Macro:
        if a.value.pair != b.value.pair {
            *result = _nil
        } else {
            *result = t
        }
    case AtomType_Pair:
        if a.value.pair != b.value.pair {
            *result = _nil
        } else {
            *result = t
        }
    case AtomType_Symbol:
        if a.value.symbol != b.value.symbol {
            *result = _nil
        } else {
            *result = t
        }
    default:
        panic(fmt.Sprintf("assert(_type != %d)", a._type))
    }
    return nil
}

pair?

Tests whether an atom is a pair.

// builtin_pairp tests whether an atom is a pair.
// note that the result may not be updated if we find errors.
func builtin_pairp(args Atom, result *Atom) error {
    // verify number and type of arguments
    if nilp(args) || !nilp(cdr(args)) {
        return Error_Args
    }

    if car(args)._type != AtomType_Pair {
        *result = _nil
    } else {
        *result = make_sym([]byte{'T'})
    }
    return nil
}

Don't forget to add bindings for these to the initial environment.

// env_create_default creates a new environment with some native
// functions added to the symbol table.
func env_create_default() Atom {
    .
    .
    .
    _ = env_set(env, make_sym([]byte("APPLY")), make_builtin(builtin_apply))
    _ = env_set(env, make_sym([]byte("EQ?")), make_builtin(builtin_eq))
    _ = env_set(env, make_sym([]byte("PAIR?")), make_builtin(builtin_pairp))

    // return the new environment
    return env
}

map

We can use foldr and apply to implement another important function map, which constructs a list containing the results of calling an n-ary function with the values contained in n lists in turn.

(define (unary-map proc list)
  (foldr (lambda (x rest) (cons (proc x) rest))
         nil
         list))

(define (map proc . arg-lists)
  (if (car arg-lists)
      (cons (apply proc (unary-map car arg-lists))
            (apply map (cons proc
                             (unary-map cdr arg-lists))))
      nil))

Once again please note that there are alternative implementations.

It works like this:

> (map + '(1 2 3) '(4 5 6))
(5 7 9)

The result is a list containing the results of evaluating (+ 1 4), (+ 2 5), and (+ 3 6).

func TestChapter12(t *testing.T) {
    env := env_create_default()
    if err := load_file(env, "library.lisp"); err != nil {
        t.Errorf("error: want nil: got %v\n", err)
    }

    for _, tc := range []struct {
        id     int
        input  string
        expect string
        err    error
    }{
        {id: 1, input: "(abs -2)", expect: "2"},
        {id: 2, input: "(list (+ 3 5) 'foo)", expect: "(8 FOO)"},
        {id: 3, input: "(reverse '(1 2 3))", expect: "(3 2 1)"},
        {id: 4, input: "(map + '(1 2 3) '(4 5 6))", expect: "(5 7 9)"},
    } {
        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)
        }
    }
}