3 ms·

Here is a minimal LISP compiler in 400 lines of LISP that does not gloss over anything: http://t3x.org/lfn/liscmp.lisp.html http://t3x.org/lfn/liscmp.lisp.html

Here is a minimal LISP compiler in 400 lines of LISP that does not gloss over anything: http://t3x.org/lfn/liscmp.lisp.html 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 http://t3x.org/lfn/lisp.lisp.html Even the garbage collector could be written in LISP http://t3x.org/lfn/gc.lisp.html 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 http://t3x.org/lfn/index.html

kragen 6y 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.
- tekknolagi 6y ago
  The author is the commenter :)
  - kragen 6y ago
    Oh, so he is. I wonder if he'll explain I misunderstood him or correct the error.
    - nils-m-holm 6y ago
      In case you are still reading this: the book is about ancient LISP (LISP 1.0, 1.5, PDP-6 LISP), which was dynamically scoped. The Y combinator requires lexical scoping, though.
      - kragen 6y ago
        Hmm, that's a good point. The general-case solution they adopted for not having lexical scoping at the time was FUNARG, but of course that's just as much of a kludge as LABEL (which was, yes, in 1959 Lisp, before FUNARG). There are cheats like this, of course: (defun quasiquote-y (f) `(lambda (n) (funcall (function ,f) (function ,f) n))) Perhaps surprisingly, this does work in dynamically-scoped Lisp-2s like Elisp (which, unlike Lisp 1.5, doesn't have FUNARG), even for λ-expressions: (funcall (quasiquote-y '(lambda (f n) (if (< n 2) 1 (* n (funcall f f (- n 1)))))) 4) Defining a version of QUASIQUOTE-Y that works for the following subtly different LAMBDA form has so far escaped me but seems like it ought to be feasible: (lambda (f n) (if (< n 2) 1 (* n (funcall f (- n 1))))) Now, of course, in modern Lisps, we consider it a barbaric practice to treat a list beginning with the symbol LAMBDA as a function as such, as opposed to a piece of code which could be EVALed to produce a function. But this ancient abomination remains honored in the dark precincts of Elisp, and of course was entirely supported in Lisp 1.5 (though doing the equivalent of QUASIQUOTE would have been considerably more awkward; FUNARG was the favored design error of the day) and McCarthy 1959. ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-199.pdf ("The function of FUNCTION") relates the 1970 perspective on this problem.
        nils-m-holm 6y ago
        The FUNARG device was defined in the LISP 1.5 manual, but never implemented. Later versions of MACLISP did a limited version of FUNARG (called FUNCTION*) that solved the downward, but not the upward FUNARG problem. Then dynamic scoping interferes badly with tail call elimination (TCE), because bindings do not have indefinite extent and need to be removed at some point. The exact point of removal leads to all kinds of interesting problems. The short version is, you can have TCE or correct bindings, but not both. So a dynamically scoped Y will kind of "work", but eventually either cause a FUNARG problem or overflow the stack.

kragen 6y 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.

tekknolagi 6y ago
The author is the commenter :)
- kragen 6y ago
  Oh, so he is. I wonder if he'll explain I misunderstood him or correct the error.
  - nils-m-holm 6y ago
    In case you are still reading this: the book is about ancient LISP (LISP 1.0, 1.5, PDP-6 LISP), which was dynamically scoped. The Y combinator requires lexical scoping, though.
    - kragen 6y ago
      Hmm, that's a good point. The general-case solution they adopted for not having lexical scoping at the time was FUNARG, but of course that's just as much of a kludge as LABEL (which was, yes, in 1959 Lisp, before FUNARG). There are cheats like this, of course: (defun quasiquote-y (f) `(lambda (n) (funcall (function ,f) (function ,f) n))) Perhaps surprisingly, this does work in dynamically-scoped Lisp-2s like Elisp (which, unlike Lisp 1.5, doesn't have FUNARG), even for λ-expressions: (funcall (quasiquote-y '(lambda (f n) (if (< n 2) 1 (* n (funcall f f (- n 1)))))) 4) Defining a version of QUASIQUOTE-Y that works for the following subtly different LAMBDA form has so far escaped me but seems like it ought to be feasible: (lambda (f n) (if (< n 2) 1 (* n (funcall f (- n 1))))) Now, of course, in modern Lisps, we consider it a barbaric practice to treat a list beginning with the symbol LAMBDA as a function as such, as opposed to a piece of code which could be EVALed to produce a function. But this ancient abomination remains honored in the dark precincts of Elisp, and of course was entirely supported in Lisp 1.5 (though doing the equivalent of QUASIQUOTE would have been considerably more awkward; FUNARG was the favored design error of the day) and McCarthy 1959. ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-199.pdf ("The function of FUNCTION") relates the 1970 perspective on this problem.
      - nils-m-holm 6y ago
        The FUNARG device was defined in the LISP 1.5 manual, but never implemented. Later versions of MACLISP did a limited version of FUNARG (called FUNCTION*) that solved the downward, but not the upward FUNARG problem. Then dynamic scoping interferes badly with tail call elimination (TCE), because bindings do not have indefinite extent and need to be removed at some point. The exact point of removal leads to all kinds of interesting problems. The short version is, you can have TCE or correct bindings, but not both. So a dynamically scoped Y will kind of "work", but eventually either cause a FUNARG problem or overflow the stack.