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