4 ms·

The Roots of Lisp (2002) [pdf]

57 points by malisper 12y ago

frownie 12y ago
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) ?
- pjmlp 12y ago
  Funny I also got some enlightenment in the same year but with Caml Light and Prolog with a little Smaltalk on the side (VisualWorks). At Nova University in Lisbon. And that was just the beginning as my university had a few lectures that made use of them, since a few of the major teachers were quite into FP and LP communities. Then I had to traverse the desert of mainstream languages, until being finally allowed to use such concepts on the programming languages I work with.
Slackwise 12y ago
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 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 http://ghostscript.com/doc/current/Ps2pdf.htm [2]: http://lib.store.yahoo.net/lib/paulgraham/jmc.ps http://lib.store.yahoo.net/lib/paulgraham/jmc.ps [3]: http://www.paulgraham.com/rootsoflisp.html http://www.paulgraham.com/rootsoflisp.html [4]: http://ctan.mackichan.com/support/pkfix/pkfix.pl http://ctan.mackichan.com/support/pkfix/pkfix.pl [5]: https://news.ycombinator.com/item?id=8350995 https://news.ycombinator.com/item?id=8350995
- mainland 12y ago
  Using pkfix before ps2pdf will improve the final output---it replaces bitmap fonts with Type 1 fonts.
  - Slackwise 12y ago
    That is amazing. I've gone and used pkfix and updated the file. It looks perfect now. Thanks!
- dang 12y ago
  Since that's more readable, and since the original url (http://www.cs.uml.edu/ecg/pub/uploads/OPLspr09/genesis-of-lisp-jmc.pdf http://www.cs.uml.edu/ecg/pub/uploads/OPLspr09/genesis-of-li...) wasn't canonical, we updated it to yours. Thanks!
drostie 12y ago
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 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.
- davexunit 12y ago
  Your JSON snippet is reminiscent of SXML, a format for describing XML/HTML as s-expressions. The difference being that, using quasiquote and unquote, Lisps are full-fledged templating languages. Here's a simple template written in Scheme: (define stuff '("foo" "bar" "baz")) `(ul (@ (class "foo")) ,@(map (lambda (thing) `(li ,thing)) stuff)) Output: (ul (@ (class "foo")) (li "foo") (li "bar") (li "baz")) Fun stuff!
- zwp 12y ago
  > representing HTML You may like Clojure's Hiccup: https://github.com/weavejester/hiccup https://github.com/weavejester/hiccup http://www.rkn.io/2014/03/13/clojure-cookbook-hiccup/ http://www.rkn.io/2014/03/13/clojure-cookbook-hiccup/ These representations underline how anomalous <IMG...>, <BR>, etc are in "standard" HTML.
guiomie 12y ago
Why are the letters like that? I feel like I'm reading a ransom letter.
tromp 12y ago
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 http://www.cwi.nl/~tromp/cl/cl.html

57 points by malisper 12y ago

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

pjmlp 12y ago
Funny I also got some enlightenment in the same year but with Caml Light and Prolog with a little Smaltalk on the side (VisualWorks). At Nova University in Lisbon. And that was just the beginning as my university had a few lectures that made use of them, since a few of the major teachers were quite into FP and LP communities. Then I had to traverse the desert of mainstream languages, until being finally allowed to use such concepts on the programming languages I work with.

Slackwise 12y ago

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

mainland 12y ago
Using pkfix before ps2pdf will improve the final output---it replaces bitmap fonts with Type 1 fonts.
- Slackwise 12y ago
  That is amazing. I've gone and used pkfix and updated the file. It looks perfect now. Thanks!
dang 12y ago
Since that's more readable, and since the original url (http://www.cs.uml.edu/ecg/pub/uploads/OPLspr09/genesis-of-lisp-jmc.pdf http://www.cs.uml.edu/ecg/pub/uploads/OPLspr09/genesis-of-li...) wasn't canonical, we updated it to yours. Thanks!

drostie 12y ago

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

davexunit 12y ago
Your JSON snippet is reminiscent of SXML, a format for describing XML/HTML as s-expressions. The difference being that, using quasiquote and unquote, Lisps are full-fledged templating languages. Here's a simple template written in Scheme: (define stuff '("foo" "bar" "baz")) `(ul (@ (class "foo")) ,@(map (lambda (thing) `(li ,thing)) stuff)) Output: (ul (@ (class "foo")) (li "foo") (li "bar") (li "baz")) Fun stuff!
zwp 12y ago
> representing HTML You may like Clojure's Hiccup: https://github.com/weavejester/hiccup https://github.com/weavejester/hiccup http://www.rkn.io/2014/03/13/clojure-cookbook-hiccup/ http://www.rkn.io/2014/03/13/clojure-cookbook-hiccup/ These representations underline how anomalous <IMG...>, <BR>, etc are in "standard" HTML.

guiomie 12y ago

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

tromp 12y ago

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 http://www.cwi.nl/~tromp/cl/cl.html