Comment by nils-m-holm

5 years ago

Here is a minimal LISP compiler in 400 lines of LISP that does not gloss over anything:

http://t3x.org/lfn/liscmp.lisp.html

It only depends on about 350 lines of LISP code for standard functions like CADR, APPEND, READ, etc, plus avout 400 lines of C for low-level stuff (variable binding and garbage collection).

The 350 lines of LISP standard function even contain low-level things like interning of symbols:

http://t3x.org/lfn/lisp.lisp.html

Even the garbage collector could be written in LISP

http://t3x.org/lfn/gc.lisp.html

but there are a few issues that are not addressed in the code. For a full explanation of the compiler and some bits of historical trivia, see

http://t3x.org/lfn/index.html

8 comments

nils-m-holm

Reply
kragen  5 years ago

This is very interesting, thank you! At first glance, it does perhaps gloss over a few things still: instruction encoding, jump-target backpatching (or its moral equivalent), the system call interface, the fetch-execute cycle, and a debugger; but not, for example, function entry and exit, or, as you point out, garbage collection or the reader. Also, on p. 16, there's an error seemingly due to the author not knowing about the Y-combinator:

    The LABEL special form,
    as implemented by EVAL,
    was a clever construct
    for defining anonymous recursive functions.
    Anonymous functions
    ("lambda functions")
    cannot usually recurse
    (apply themselves),
    just because they are anonymous,
    so there is no name that can be used
    to invoke them.