Subject: Re: The secret of hand compiling LISP/Scheme
From: (Rob Warnock)
Date: Mon, 08 Oct 2007 19:42:00 -0500
Newsgroups: comp.lang.lisp,comp.lang.scheme
Message-ID: <>
Tim Bradshaw  <> wrote:
| On Oct 8, 7:35 am, wrote:
| > I have googled a lot and not found any clear information on how to
| > "hand compile" a rudimentary LISP interpreter.
| You have a language L which you want to implement on a machine M...
| Write (on paper) a compiler for L which targets M.  You can write it
| in any language, but for simplicity we'll say you are writing it in
| L.  Call this compiler C.
| Now: you know the syntax and semantics of L, and you have the source
| of C, written in L.  So you can now, manually, run through what C
| would do to its own source, and write down the output it would produce
| from it.  Call this CM1: it is a bunch of machine code for M.
| In particular CM1 is a program which, when run on M, is a compiler for
| L (it's the binary for C in fact).
| So, run CM1 on M, giving it as input the source of C.  This will
| produce more output, CM2.  CM2 should be the same as CM1: if it's not
| you've made a mistake.

A longer description of the general methodology Tim is describing --
along with an elegant series of "T diagrams" showing most clearly what
is input, what is output, what is the translator from input to output,
and what the translator is running on -- can be found in this classic
    "The XPL Programming Language"
    William M. McKeeman, James J. Horning, and David B. Wortman
    ISBN 13-155077-2 (Prentice Hall, March 1971)

Amazon has used copies for from $4-$40, a steal for a 527 page
hardcover. [Note that the front & back endpapers of the original
hardback are covered with the above-mentioned "T diagrams".]

Yes, it's an obsolete language[1], but the principles still hold.

The following lovely standalone tutorial on T diagrams may help one
follow Tim's textual explication above:

Another tutorial, using ASCII art [also see Figure 2.12 near the
bottom of that page]:
    2.1 T-diagrams


[1] Perhaps with the exception of it (still?) being used to
    compile NASA's "Hal/S" language for the Space Shuttle,
    see <>.

Rob Warnock			<>
627 26th Avenue			<URL:>
San Mateo, CA 94403		(650)572-2607