Lisp Interpreters

In terms of learning about interpreters lisp is a good starting point. It requires simple lexing requirements for the minimal set of types, the parsing is near trivial, and there is plenty of information on metacircular evaluation schemes for lisp ( http://www.paulgraham.com/rootsoflisp.html ). This is not to say that it is trivial to create an interpreter from scratch. One of the reasons that metacircular evaluation is so simple is that it takes advantage of the environment it is within. If this is done within another lisp, usually parsing the input is taken care of by a (read), garbage collection is taken care of, system functions are already accessible, types are defined, and other parts of the lisp system are done. To some this strips the problem of its nuisances and allows the programmer to get at the interesting parts.

I agree that this can hold true, but I think it leaves the possibility of some hidden magic. So in the chase of this magic I designed and coded a lisp interpreter. After begin influenced by common lisp for a while I tried to emulate most of what it offered. The result is a C program that behaves like scheme, but reads like common lisp. This is mostly due to the fact that coding out multiple namespaces is a pain.

Features

  • simple type system for symbols, strings, numbers, cons, functions, and composite types

  • Callable Mark-Sweep garbage collector

  • Lisp defined macro system via pre-evaluation hook

  • Simple error handling via throw/catch

  • Very Rudimentary continuations

  • Hand built read function

  • Standard REPL(read-eval-print-loop)

  • Scoped variables

A Brief Tour

After building it and starting the interpreter the REPL appears. (../lisp fn.lisp bq.lisp macroexpand.lisp base.lisp) For self evaluating expressions it functions as you would expect:

[LISP]> 1234
1234
[LISP]> "apple-pie"
"apple-pie"
[LISP]> :im-a-symbol
:im-a-symbol
[LISP]> 'another-symbol
another-symbol
[LISP]> '(1 2 a (list (of)) some :symbols "here")
(1 2 a (list (of)) some :symbols "here")

Functions are taken care of by fn and macros around it. If desired, lambda can be defined in terms of fn.

[LISP]> (defun foo (a) (print a) (print 'defun))
#<Function>
[LISP]> (foo 'argument)
argument
defun
defun
[LISP]> ((fn (a) (print a) (print 'fn)) 'argument)
argument
fn
fn
[LISP]> (defmacro lambda (&rest rest) (cons 'fn rest))
(nil)
[LISP]> ((lambda (a) (print a) (print 'lambda)) 'argument)
argument
lambda
lambda

A better test of the macro system is the use of backquote, which is one of my favorite features in common lisp. An incomplete system was built to recognize backquotes and unquote. This allows for many macros to have fairly simple declarations:

(defmacro if (test yes no)
  `(cond (,test ,yes)
         ('t ,no))

Basic errors are tossed up to the REPL if not caught. They are then displayed:

[LISP]> (+ 1 2 3 4 "hat")
error"can only add numbers"

The environment can be accessed with (get_env) and at the moment it is still done with nested linked lists of bindings. And using the rough continuations they can be looped over non-recursively:

(mapcar (fn (binding) (car binding))
        (get_env))

This yields the list of bindings for the system with all defined lisp and C functions, as well as some constants, like nil or t: (get_env global assoc pair append not null + setq if backquote bq qlist list defun defmacro macro setf setdef macroexpand :func mapcar funcall macro-callp macrop :mac consp symbolp set-slot get-slot symbol-value specialp set_slot get_slot make-type deftype throw type-of read apply boundp princ print def set plus eq unbound car cdr cons symbol_value eval retry atom exit get_syms get_env eval-hook nil t)

Lastly there is the fragile continue system. This is a basic loop from 1 to 10. It is ugly and not tested too well, but it works.

(def 'foobar 0)
(continue loop
  (cond ((eq foobar 10) ((fn () (print 'done) foobar)))
        (t ((fn () (print (set 'foobar (plus 1 foobar))) (retry 'loop))))))

Further Reading

One of the very useful sources when I was working on this interpreter was: http://home.pipeline.com/~hbaker1/MetaCircular.html

In many ways it reduced the mystery of some of the special forms (aka hardcoded chunks of the language) and how to code them. There are also a number of interesting articles from that same author up one directory, I recommend reading a few.

See It For Yourself

To see this in action just grab the code with:

git clone git://fundamental-code.com/com-lisp.git