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.<p>There's also the follow-up[1]:<p><pre><code> (How to Write a ((Better) Lisp) Interpreter (in Python))
(norvig.com)
</code></pre>
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).<p>--------<p>[0] <a href="https://hn.algolia.com/?q=lisp+python#!/story/sort_by_date/prefix/0/write%20lisp%20interpreter%20python" rel="nofollow">https://hn.algolia.com/?q=lisp+python#!/story/sort_by_date/p...</a><p>[1] <a href="http://norvig.com/lispy2.html" rel="nofollow">http://norvig.com/lispy2.html</a><p>[2] <a href="https://news.ycombinator.com/item?id=1746916" rel="nofollow">https://news.ycombinator.com/item?id=1746916</a><p>[3] <a href="https://news.ycombinator.com/item?id=7825526" rel="nofollow">https://news.ycombinator.com/item?id=7825526</a>
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.<p>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.<p>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!<p>Re: this, Norvig commented/said,<p>> <i>[...] 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.</i>
A good complement to Norvig's writings (actually inspired by it) is "Lisp as the Maxwell's equations of software" by Michael Nielsen:
<a href="http://www.michaelnielsen.org/ddi/lisp-as-the-maxwells-equations-of-software/" rel="nofollow">http://www.michaelnielsen.org/ddi/lisp-as-the-maxwells-equat...</a>
Worth reading!
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)
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].<p>--------<p>[0] <a href="http://norvig.com/spell-correct.html" rel="nofollow">http://norvig.com/spell-correct.html</a><p>[1] <a href="http://norvig.com/21-days.html" rel="nofollow">http://norvig.com/21-days.html</a>
I will try this out!<p>Also there is diy-lisp[0]. I myself did it and it was very rewarding and fun![1]<p>[0]: <a href="http://kjetilvalle.com/posts/implement-a-programming-language.html" rel="nofollow">http://kjetilvalle.com/posts/implement-a-programming-languag...</a><p>[1]: <a href="https://github.com/daGrevis/diy-lisp" rel="nofollow">https://github.com/daGrevis/diy-lisp</a>
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: <a href="http://common-lisp.net/project/clpython/" rel="nofollow">http://common-lisp.net/project/clpython/</a>
mr. Norvig is a great man, no doubts. Have you read AIMA, by the way? I did.)<p>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 <i>the</i> way of defining a DSL. the loop constructs, structures, even whole CLOS is nothing but a DSL.<p>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".<p><i>This</i> (everything is made out of conses + general evaluation rule + reader macros) could be called a Lisp.<p>Want to see a Lisp? Look at arc.arc
Another recommended reading is the book "Understanding Computation" that has a section dedicated to Lambda Calculus: <a href="http://computationbook.com/" rel="nofollow">http://computationbook.com/</a>
Anyone who likes this idea but wants to do it in C might enjoy this <a href="http://www.buildyourownlisp.com/" rel="nofollow">http://www.buildyourownlisp.com/</a>
Very interesting, as you might imagine.<p>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).
And here I was thinking that I'd been the first to have the kooky idea of implementing Scheme in Python: <a href="https://github.com/scribu/scheme.py" rel="nofollow">https://github.com/scribu/scheme.py</a> :)<p>It was a really rewarding experience; definitely recommended!