The Roots of Lisp (2002) [pdf]

I've on more than one occasion used Lisp's "everything is data" idea to build little domain-specific languages in JSON. One of the easiest places to start is with representing HTML this way; you can e.g. start to write the Python or JS code:

    ["table", ["tbody", ["tr", ["td class=first", 1], ["td", 2]]]]

instead of:

    <table><tbody><tr><td class="first">1</td><td>2</td></tr></tbody></table>

A really early attempt at this is: https://github.com/drostie/d.o/blob/master/build.js but I haven't maintained it in a while.

If you're interested in language design, there appears to be a "little gap" which means a lot between a Lisp data structure and an XML data structure: In XML's view, every list's first element is a string; in Lisp's, it can be anything. This little gap actually corresponds to one of the interesting habits which has disappeared since compilers took over our assembly-writing: it used to be the case that programmers would sometimes compute an instruction code for the next instruction; similarly in Lisps you sometimes (but not too often; it's confusing!) compute a function for your next operation.

If that confuses you because you're not good with Lisp, it's equivalent in Python or JS is:

     (f(x, y, z))(a, b, c)

so that you figure out which function to call and then immediately call it on some parameters. It's not necessarily a difference in expressiveness, as the XML-style just can add an atom 'call' which expresses the above as:

    call(f(x y z) a b c)

but it does seem to correspond to some deeply different philosophy for the system.

Not to sound smart ass but I got that in 1996 when I was fortunate enough to have a course on Scheme by D. Ribbens here at Liege University in Belgium. He showed us how to build that very interpreter and how powerful it was (he used to say : forget about algorithms or OOP, here's the truly powerful stuff :-) ). Since then I contemplate the slow evolution of languages, leaning to functional programming (although Scheme is not FP, that's for sure).

That said, what could be taught to a young student today that would provide the same kind of enlightenment I had with those few pages of list(p) ?

The paper concludes that a "remarkably elegant model of computation" can be made using just 7 primitive operators, which allows for defining a self-interpreter.

In fact, 0 primitive operators suffice, as the ability to denote functions (Section 2) gives us the Turing complete lambda calculus.

A self-interpreter for a version of lambda calculus denoted in binary fits in under 26 bytes, as shown on http://www.cwi.nl/~tromp/cl/cl.html

I used ps2pdf[1] to make a cleaner/better version from the original PostScript[2] file from Paul Graham's site[3]:

http://slackwise.net/files/docs/The%20Roots%20of%20Lisp.pdf

The tracking/kerning is still off, but not as much. It's definitely easier to read than the one linked in this post. Anyone know a better utility, or is the source PostScript just poorly typeset?

Edit: I've just applied pkfix[4] to the file as mainland recommended[5], and it looks wonderful! I've replaced the file on my server, so you can Ctrl-F5 it to see the wonderful crisp text.

[1]: http://ghostscript.com/doc/current/Ps2pdf.htm [2]: http://lib.store.yahoo.net/lib/paulgraham/jmc.ps [3]: http://www.paulgraham.com/rootsoflisp.html [4]: http://ctan.mackichan.com/support/pkfix/pkfix.pl [5]: https://news.ycombinator.com/item?id=8350995

Why are the letters like that? I feel like I'm reading a ransom letter.