6 ms·

How to Write a Lisp Interpreter in Python (2010)

144 points by yankoff 12y ago

leephillips 12y ago
Very interesting, as you might imagine. Actually, LaTeX was introduced in 1984, when the author began his thesis, and TeX had been out for years. But they did not yet seem to be widely known. I began my thesis a few years after Norvig, and I started with troff, which was still the standard, but had terrible output. Then someone told me about TeX, and I wrote my whole thesis in plain TeX, using a Mac Plus (that I still have and that still works).
anaphor 12y ago
Exercise for the reader: how might the representation Norvig uses for environments be changed if we assume all data is immutable? :)
Monkeyget 12y ago
I love Norvig's writing. He has a way of writing in concisely and make code appear effortless.
- camperman 12y ago
  And you get to the end and think "hey, I could have done that." One of the signs of a great teacher.
alixander 12y ago
http://www-inst.eecs.berkeley.edu/~cs61a/sp14/proj/scheme/scheme.html http://www-inst.eecs.berkeley.edu/~cs61a/sp14/proj/scheme/sc...
- DanFeldman 12y ago
  Just finished this project a month ago! It was surprisingly difficult, learned a heck of a lot. Go bears!
- rel 12y ago
  Yeah, I too instantly thought of the 61a project.
dschiptsov 12y ago
mr. Norvig is a great man, no doubts. Have you read AIMA, by the way? I did.) This, of course, is not a "complete" Lisp. Let's say that [one of] the most fundamental feature of a Lisp is ability to define a new "special form" (without modifying the code of the interpreter) as a [reader] macro. This is the way of defining a DSL. the loop constructs, structures, even whole CLOS is nothing but a DSL. All we need is quote, quasi-quote, unquote, unquote-splicing, the "conses-aware" read function which "expands" these and the if special form that "short-circuits". This (everything is made out of conses + general evaluation rule + reader macros) could be called a Lisp. Want to see a Lisp? Look at arc.arc
- gkya 12y ago
  This “DSL” acronym is used everywhere nowadays; mistakenly so I think. A DSL (domain specific language) is like cold-fusion, R or VHDL; it is a complete language designed with the target domain in mind.
  - dschiptsov 12y ago
    Now tell us, please, how looping constructs in CL aren't DSLs and how it how it contradicts your definitions. hint: the term DSL was popularized by SICP. One needs high-order procedures to implement a simple DSL, the feature which wasn't available in most language but Lisps.
    - gkya 12y ago
      Well, looping constructs are not related to a particular domain (e.g. electronic circuit design), but are general purpose construct.
- coldtea 12y ago
  >Let's say that [one of] the most fundamental feature of a Lisp is ability to define a new "special form" (without modifying the code of the interpreter) as a [reader] macro That's not fundamendal at all. If anything, either seldom used or frowned upon.
ColinWright 12y ago
There are lengthy discussions every time this is submitted[0] to HN - it's one of the items that makes me think we need some sort of "Hall of Fame" or similar. There's also the follow-up[1]: (How to Write a ((Better) Lisp) Interpreter (in Python)) (norvig.com) Unsurprisingly, that also gets a good discussion when submitted[2], but since that discussion is closed, and this discussion has started again, I thought I'd re-submit that one[3] (partly as an experiment). -------- [0] https://hn.algolia.com/?q=lisp+python#!/story/sort_by_date/prefix/0/write%20lisp%20interpreter%20python https://hn.algolia.com/?q=lisp+python#!/story/sort_by_date/p... [1] http://norvig.com/lispy2.html http://norvig.com/lispy2.html [2] https://news.ycombinator.com/item?id=1746916 https://news.ycombinator.com/item?id=1746916 [3] https://news.ycombinator.com/item?id=7825526 https://news.ycombinator.com/item?id=7825526
scribu 12y ago
And here I was thinking that I'd been the first to have the kooky idea of implementing Scheme in Python: https://github.com/scribu/scheme.py https://github.com/scribu/scheme.py :) It was a really rewarding experience; definitely recommended!
jgrodziski 12y ago
A good complement to Norvig's writings (actually inspired by it) is "Lisp as the Maxwell's equations of software" by Michael Nielsen: http://www.michaelnielsen.org/ddi/lisp-as-the-maxwells-equations-of-software/ http://www.michaelnielsen.org/ddi/lisp-as-the-maxwells-equat... Worth reading!
jgrodziski 12y ago
Another recommended reading is the book "Understanding Computation" that has a section dedicated to Lambda Calculus: http://computationbook.com/ http://computationbook.com/
wfn 12y ago
I had once started writing a Lisp interpreter in Python, only to realize that I was leveraging a lot of pythonic power (most notably at least for me at the time - garbage collection) - i.e. more than I had planned to use. So then I switched to writing the same interpreter in C, and building my own memory manager. (As is usually the case --) turns out it's more complicated (for someone with little experience in writing these sorts of things) than one might expect. :) But it's very rewarding indeed. Of course I still think that there's much value in writing such an interpreter in Python. I would simply recommend for someone doing that to later on re-write it in some lower level language! Re: this, Norvig commented/said, > [...] we are relying on many features of Python: call stack, data types, garbage collection, etc. The next step would be to show a compiler to some sort of assembly language. I think either the Java JVM or the Python byte code would be good targets. We'd also need a runtime system with GC. I show the compiler in my PAIP book.
- sillysaurus3 12y ago
  Is your lisp interpreter's C source code available anywhere? I'd love to dig through it.
  - wfn 12y ago
    Honestly, the code is a mess. (Really.) I'm trying to determine/recall how far I was able to get by looking at it (at least the initial goal was to have functionality akin to jmc's original paper, with syntax from pg's reinterpretation of it[1].) I'm putting "clean up [, possibly finish] and push to a repo" on my "generic todo list." :) will try to remember to ping you if/when that happens. Until then, honestly not much use of it. [1]: http://lib.store.yahoo.net/lib/paulgraham/jmc.ps http://lib.store.yahoo.net/lib/paulgraham/jmc.ps
daGrevis 12y ago
I will try this out! Also there is diy-lisp[0]. I myself did it and it was very rewarding and fun![1] [0]: http://kjetilvalle.com/posts/implement-a-programming-language.html http://kjetilvalle.com/posts/implement-a-programming-languag... [1]: https://github.com/daGrevis/diy-lisp https://github.com/daGrevis/diy-lisp
- daGrevis 12y ago
  The cool thing about diy-lisp is that at the end you implement standard library of your language in, well, your language![0] [0]: https://github.com/daGrevis/diy-lisp/blob/master/stdlib.diy https://github.com/daGrevis/diy-lisp/blob/master/stdlib.diy
chrisloy 12y ago
Read this before, but always good to be reminded of a classic. I'd consider most of the essays on his front page essential reading, but I particularly enjoy the wit in his essay on writing a spelling corrector in Python [0], and the flattery of our collective egos in 'Teach Yourself Programming in Ten Years' [1]. -------- [0] http://norvig.com/spell-correct.html http://norvig.com/spell-correct.html [1] http://norvig.com/21-days.html http://norvig.com/21-days.html
basyt 12y ago
Nobody's heard of Hy then? https://github.com/hylang/tryhy https://github.com/hylang/tryhy
- chc 12y ago
  What would lead you to believe that nobody's heard of Hy?
- agentultra 12y ago
  The only problem with Hy is that it's not, technically, a Lisp: it's Python with a Lisp syntax so that you can programmatically manipulate Python AST trees with a simple interface: plain-old-data-structures, iterators, and functions. caveat I'm a core Hy developer. ;)
  - sitkack 12y ago
    I don't understand how that wouldn't qualify as a Lisp? Does it matter what the level below is implemented out of?
    - agentultra 12y ago
      Lisp is more than just parenthesis, just as Python is more than just whitespace-delimited blocks of text. We can do some neat tricks by transforming a parenthetical syntax to Python AST that may even seem like Lisp some of the time... but the semantics are and will always be Python without stretching truth and logic a little.
cessor 12y ago
There is a nice book by Terence Parr on "The Pragmatic Bookshelf" called "Language Implementation Patterns". I found this to be a perfect introduction to compilers with a very practical point of view. Rather than talking about grammars for ages he dives right into some (java) code and shows you what problems come up when parsing code and how compilers solve them in different cases. I followed along in python and managed to write my own c-like compiler with it. I believe it is a perfect introduction for students that shows them that writing compilers is not dry, theoretical and boring, but interesting and fundamentally effectful. Terrence is by the way the author of Antlr (reference just for his street cred)
- lifeisstillgood 12y ago
  For those who like the idea: http://www.amazon.co.uk/gp/aw/d/193435645X?pc_redir=1400862274 http://www.amazon.co.uk/gp/aw/d/193435645X?pc_redir=14008622...
userbinator 12y ago
If you want to go the other way, there's also a Python implementation in Lisp; unfortunately, without a nice article on how it was written: http://common-lisp.net/project/clpython/ http://common-lisp.net/project/clpython/
- sitkack 12y ago
  Other projects worth looking at are: http://docs.hylang.org/en/latest/ http://docs.hylang.org/en/latest/ a sexpr representation of Python https://github.com/halgari/clojure-py https://github.com/halgari/clojure-py a clojure implementation in pure Python
orangeduck 12y ago
Anyone who likes this idea but wants to do it in C might enjoy this http://www.buildyourownlisp.com/ http://www.buildyourownlisp.com/

144 points by yankoff 12y ago

Very interesting, as you might imagine. Actually, LaTeX was introduced in 1984, when the author began his thesis, and TeX had been out for years. But they did not yet seem to be widely known. I began my thesis a few years after Norvig, and I started with troff, which was still the standard, but had terrible output. Then someone told me about TeX, and I wrote my whole thesis in plain TeX, using a Mac Plus (that I still have and that still works).

anaphor 12y ago

Exercise for the reader: how might the representation Norvig uses for environments be changed if we assume all data is immutable? :)

Monkeyget 12y ago

I love Norvig's writing. He has a way of writing in concisely and make code appear effortless.

camperman 12y ago
And you get to the end and think "hey, I could have done that." One of the signs of a great teacher.

alixander 12y ago

http://www-inst.eecs.berkeley.edu/~cs61a/sp14/proj/scheme/scheme.html http://www-inst.eecs.berkeley.edu/~cs61a/sp14/proj/scheme/sc...

DanFeldman 12y ago
Just finished this project a month ago! It was surprisingly difficult, learned a heck of a lot. Go bears!
rel 12y ago
Yeah, I too instantly thought of the 61a project.

dschiptsov 12y ago

mr. Norvig is a great man, no doubts. Have you read AIMA, by the way? I did.) This, of course, is not a "complete" Lisp. Let's say that [one of] the most fundamental feature of a Lisp is ability to define a new "special form" (without modifying the code of the interpreter) as a [reader] macro. This is the way of defining a DSL. the loop constructs, structures, even whole CLOS is nothing but a DSL. All we need is quote, quasi-quote, unquote, unquote-splicing, the "conses-aware" read function which "expands" these and the if special form that "short-circuits". This (everything is made out of conses + general evaluation rule + reader macros) could be called a Lisp. Want to see a Lisp? Look at arc.arc

gkya 12y ago
This “DSL” acronym is used everywhere nowadays; mistakenly so I think. A DSL (domain specific language) is like cold-fusion, R or VHDL; it is a complete language designed with the target domain in mind.
- dschiptsov 12y ago
  Now tell us, please, how looping constructs in CL aren't DSLs and how it how it contradicts your definitions. hint: the term DSL was popularized by SICP. One needs high-order procedures to implement a simple DSL, the feature which wasn't available in most language but Lisps.
  - gkya 12y ago
    Well, looping constructs are not related to a particular domain (e.g. electronic circuit design), but are general purpose construct.
coldtea 12y ago
>Let's say that [one of] the most fundamental feature of a Lisp is ability to define a new "special form" (without modifying the code of the interpreter) as a [reader] macro That's not fundamendal at all. If anything, either seldom used or frowned upon.

ColinWright 12y ago

There are lengthy discussions every time this is submitted[0] to HN - it's one of the items that makes me think we need some sort of "Hall of Fame" or similar. There's also the follow-up[1]: (How to Write a ((Better) Lisp) Interpreter (in Python)) (norvig.com) Unsurprisingly, that also gets a good discussion when submitted[2], but since that discussion is closed, and this discussion has started again, I thought I'd re-submit that one[3] (partly as an experiment). -------- [0] https://hn.algolia.com/?q=lisp+python#!/story/sort_by_date/prefix/0/write%20lisp%20interpreter%20python https://hn.algolia.com/?q=lisp+python#!/story/sort_by_date/p... [1] http://norvig.com/lispy2.html http://norvig.com/lispy2.html [2] https://news.ycombinator.com/item?id=1746916 https://news.ycombinator.com/item?id=1746916 [3] https://news.ycombinator.com/item?id=7825526 https://news.ycombinator.com/item?id=7825526

scribu 12y ago

And here I was thinking that I'd been the first to have the kooky idea of implementing Scheme in Python: https://github.com/scribu/scheme.py https://github.com/scribu/scheme.py :) It was a really rewarding experience; definitely recommended!

jgrodziski 12y ago

A good complement to Norvig's writings (actually inspired by it) is "Lisp as the Maxwell's equations of software" by Michael Nielsen: http://www.michaelnielsen.org/ddi/lisp-as-the-maxwells-equations-of-software/ http://www.michaelnielsen.org/ddi/lisp-as-the-maxwells-equat... Worth reading!

jgrodziski 12y ago

Another recommended reading is the book "Understanding Computation" that has a section dedicated to Lambda Calculus: http://computationbook.com/ http://computationbook.com/

wfn 12y ago

I had once started writing a Lisp interpreter in Python, only to realize that I was leveraging a lot of pythonic power (most notably at least for me at the time - garbage collection) - i.e. more than I had planned to use. So then I switched to writing the same interpreter in C, and building my own memory manager. (As is usually the case --) turns out it's more complicated (for someone with little experience in writing these sorts of things) than one might expect. :) But it's very rewarding indeed. Of course I still think that there's much value in writing such an interpreter in Python. I would simply recommend for someone doing that to later on re-write it in some lower level language! Re: this, Norvig commented/said, > [...] we are relying on many features of Python: call stack, data types, garbage collection, etc. The next step would be to show a compiler to some sort of assembly language. I think either the Java JVM or the Python byte code would be good targets. We'd also need a runtime system with GC. I show the compiler in my PAIP book.

sillysaurus3 12y ago
Is your lisp interpreter's C source code available anywhere? I'd love to dig through it.
- wfn 12y ago
  Honestly, the code is a mess. (Really.) I'm trying to determine/recall how far I was able to get by looking at it (at least the initial goal was to have functionality akin to jmc's original paper, with syntax from pg's reinterpretation of it[1].) I'm putting "clean up [, possibly finish] and push to a repo" on my "generic todo list." :) will try to remember to ping you if/when that happens. Until then, honestly not much use of it. [1]: http://lib.store.yahoo.net/lib/paulgraham/jmc.ps http://lib.store.yahoo.net/lib/paulgraham/jmc.ps

daGrevis 12y ago

I will try this out! Also there is diy-lisp[0]. I myself did it and it was very rewarding and fun![1] [0]: http://kjetilvalle.com/posts/implement-a-programming-language.html http://kjetilvalle.com/posts/implement-a-programming-languag... [1]: https://github.com/daGrevis/diy-lisp https://github.com/daGrevis/diy-lisp

daGrevis 12y ago
The cool thing about diy-lisp is that at the end you implement standard library of your language in, well, your language![0] [0]: https://github.com/daGrevis/diy-lisp/blob/master/stdlib.diy https://github.com/daGrevis/diy-lisp/blob/master/stdlib.diy

chrisloy 12y ago

Read this before, but always good to be reminded of a classic. I'd consider most of the essays on his front page essential reading, but I particularly enjoy the wit in his essay on writing a spelling corrector in Python [0], and the flattery of our collective egos in 'Teach Yourself Programming in Ten Years' [1]. -------- [0] http://norvig.com/spell-correct.html http://norvig.com/spell-correct.html [1] http://norvig.com/21-days.html http://norvig.com/21-days.html

basyt 12y ago

Nobody's heard of Hy then? https://github.com/hylang/tryhy https://github.com/hylang/tryhy

chc 12y ago
What would lead you to believe that nobody's heard of Hy?
agentultra 12y ago
The only problem with Hy is that it's not, technically, a Lisp: it's Python with a Lisp syntax so that you can programmatically manipulate Python AST trees with a simple interface: plain-old-data-structures, iterators, and functions. caveat I'm a core Hy developer. ;)
- sitkack 12y ago
  I don't understand how that wouldn't qualify as a Lisp? Does it matter what the level below is implemented out of?
  - agentultra 12y ago
    Lisp is more than just parenthesis, just as Python is more than just whitespace-delimited blocks of text. We can do some neat tricks by transforming a parenthetical syntax to Python AST that may even seem like Lisp some of the time... but the semantics are and will always be Python without stretching truth and logic a little.

cessor 12y ago

There is a nice book by Terence Parr on "The Pragmatic Bookshelf" called "Language Implementation Patterns". I found this to be a perfect introduction to compilers with a very practical point of view. Rather than talking about grammars for ages he dives right into some (java) code and shows you what problems come up when parsing code and how compilers solve them in different cases. I followed along in python and managed to write my own c-like compiler with it. I believe it is a perfect introduction for students that shows them that writing compilers is not dry, theoretical and boring, but interesting and fundamentally effectful. Terrence is by the way the author of Antlr (reference just for his street cred)

lifeisstillgood 12y ago
For those who like the idea: http://www.amazon.co.uk/gp/aw/d/193435645X?pc_redir=1400862274 http://www.amazon.co.uk/gp/aw/d/193435645X?pc_redir=14008622...

userbinator 12y ago

If you want to go the other way, there's also a Python implementation in Lisp; unfortunately, without a nice article on how it was written: http://common-lisp.net/project/clpython/ http://common-lisp.net/project/clpython/

sitkack 12y ago
Other projects worth looking at are: http://docs.hylang.org/en/latest/ http://docs.hylang.org/en/latest/ a sexpr representation of Python https://github.com/halgari/clojure-py https://github.com/halgari/clojure-py a clojure implementation in pure Python

orangeduck 12y ago

Anyone who likes this idea but wants to do it in C might enjoy this http://www.buildyourownlisp.com/ http://www.buildyourownlisp.com/