How to Write a Lisp Interpreter in Python (2010)
norvig.com
norvig.com
There's also the follow-up[1]:
(How to Write a ((Better) Lisp) Interpreter (in Python))
(norvig.com)
--------
[0] https://hn.algolia.com/?q=lisp+python#!/story/sort_by_date/p...
[1] http://norvig.com/lispy2.html
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.
--------
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-languag...
[0]: https://github.com/daGrevis/diy-lisp/blob/master/stdlib.diy
http://docs.hylang.org/en/latest/ a sexpr representation of Python
https://github.com/halgari/clojure-py a clojure implementation in pure Python
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
That's not fundamendal at all. If anything, either seldom used or frowned upon.
And, please, don't tell me about the Lisp 1.5 - it was "fundamental" but has been evolved since then.
btw, if you really do look inside arc.arc you will see "a bunch of nested macros".) This approach, championed by pg (or rather rtm) and described in the classic On Lisp book is, in some sense, the culmination of the few selected ideas behind a Lisp - you evolve the language as your understanding of the project deepens (evolves) by hacking appropriate DSL as you go. It is not just a "book stuff" - Arc is very real thing and this very site has been built very quickly (and cheap) using this very approach with very few lines of clean, readable code.
Ironically, we are using these pages to discuss "religious nonsense" such OO-is-the-only-way, Java-is-the-proper-everything, Scrum-is-the-way-to-manage-big-projects, or "sectarian stuff" like Javascript.)
SICP for example writes (almost) no macros. Norvig himself has written only a few macros for his book PAIP.
The limitation is that all the arguments to your high-order function will be evaluated before its application, so if you need a special form (with its own evaluation rule) you have to write a "short-circuiting" macro transformation. This is how to write "advanced" DSLs.
Almost a 2/3 of Arc are macros, but, yes, there are very few "special forms" among them.
As for PAIP, he loves structs and looping DSLs, while, at least for me, the beauty is hidden in explicit recursive calls for traversing a recursive data-structures (lists, trees, graphs) made out of conses. I'm Brian Harvey's man.)
Who said anything about CL in specific? The article is about "how to write a Lisp in Python".
Second, no "reader macros" are not "fundamental", even for CL. Well, except if you mean the built-in ones, like #. But surely, adding custom reader macros is neither necessary nor fundamental for CL (nor are non-lispy DSLs). And they sure aren't for a simple Lisp (as in TFA).
From TFA:
"the beauty of the language is that we only need six special forms"
P.S Anybody who downvotes = disagress, does he also have any counter-argument?
There are not mere "only six special forms" involved in what makes a Lisp "a miracle". There is, in my opinion, a small, well-balanced set of ideas/principles which are complementing each other. Notably "everything is a symbol (pointer)" semantics, common for code and data cons-based underlying representation, so "the code is data" maxim makes sense, the uniform general evaluation rule for prefix-notation expressions, the "list-aware" reader function, to name the few.
All these ideas or principles aren't CL specific, on the contrary, these are common for all Lisps. CL is just a good example of incorporating mini/specialized DSLs (loops, format, etc).
I have tried to describe "how the miracle works" but failed miserably.) These are my counter-arguments.
http://karma-engineering.com/lab/blog/Good-ideas
http://karma-engineering.com/lab/wiki/ProperUnderstanding
In nearly every submission I read the comments of these days, I see numerous perfectly fine and valuable comments in gray text.
Since so much good content ends up in that state, it renders such styling pointless. Gray text no longer means that the content is very likely commercial spam or otherwise without much value.
I even go out of my way to read all of those comments. With so much good content being downvoted these days, they often have some of the more insightful remarks.
It's even gotten past that to the "flag if you disagree" point. I call that the "douchebag census data." Those users should be shunted to another "tier" of the site that's even subtler than hellbanning.
My point wasn't about mr.Norvig's essays - they are extraordinary and elegant, my point was about what is a toy [Lisp] and what isn't.)
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.
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).
caveat I'm a core Hy developer. ;)
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.
It was a really rewarding experience; definitely recommended!