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).
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.
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.
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].
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/
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.
>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.
Sorry? The ability to add looping constructs and other control structures, like with* or defstruct/defmethod etc. to CL isn't fundamental for CL as a language? What is fundamental, then?
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.)
Yeah, having high-order functions gives you the ability to write "a primitive" DSL, which is the one of the big ideas from SICP.
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.)
>Sorry? The ability to add looping constructs and other control structures, like with or defstruct/defmethod etc. to CL isn't fundamental for CL as a language? What is fundamental, then?*
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?
"the beauty of the language is that we only need six special forms" - this is an oversimplification.)
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.
The "downvote if you disagree" has gotten to a rather stupid point here lately.
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.
The "downvote if you disagree" has gotten to a rather stupid point here lately.
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.
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.
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.
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).
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.
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.
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]:
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/p...
[1] http://norvig.com/lispy2.html
[2] https://news.ycombinator.com/item?id=1746916
[3] https://news.ycombinator.com/item?id=7825526
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.
Is your lisp interpreter's C source code available anywhere? I'd love to dig through it.
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
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-equat... 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)
For those who like the idea: http://www.amazon.co.uk/gp/aw/d/193435645X?pc_redir=14008622...
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
[1] http://norvig.com/21-days.html
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-languag...
[1]: https://github.com/daGrevis/diy-lisp
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
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/
Other projects worth looking at are:
http://docs.hylang.org/en/latest/ a sexpr representation of Python
https://github.com/halgari/clojure-py a clojure implementation in pure Python
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
>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.
Sorry? The ability to add looping constructs and other control structures, like with* or defstruct/defmethod etc. to CL isn't fundamental for CL as a language? What is fundamental, then?
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.)
Well, one can get quite far without writing macros.
SICP for example writes (almost) no macros. Norvig himself has written only a few macros for his book PAIP.
Yeah, having high-order functions gives you the ability to write "a primitive" DSL, which is the one of the big ideas from SICP.
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.)
>Sorry? The ability to add looping constructs and other control structures, like with or defstruct/defmethod etc. to CL isn't fundamental for CL as a language? What is fundamental, then?*
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?
"the beauty of the language is that we only need six special forms" - this is an oversimplification.)
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
http://karma-engineering.com/lab/wiki/Bootstrapping1
http://karma-engineering.com/lab/wiki/Bootstrapping2
The "downvote if you disagree" has gotten to a rather stupid point here lately.
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.
The "downvote if you disagree" has gotten to a rather stupid point here lately.
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.
http://norvig.com/lispy2.html does support macros.
This one is better, indeed.)
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.)
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.
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.
Well, looping constructs are not related to a particular domain (e.g. electronic circuit design), but are general purpose construct.
Another recommended reading is the book "Understanding Computation" that has a section dedicated to Lambda Calculus: http://computationbook.com/
Anyone who likes this idea but wants to do it in C might enjoy this http://www.buildyourownlisp.com/
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).
Exercise for the reader: how might the representation Norvig uses for environments be changed if we assume all data is immutable? :)
Nobody's heard of Hy then?
https://github.com/hylang/tryhy
What would lead you to believe that nobody's heard of Hy?
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. ;)
I don't understand how that wouldn't qualify as a Lisp? Does it matter what the level below is implemented out of?
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.
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 :)
It was a really rewarding experience; definitely recommended!
I love Norvig's writing. He has a way of writing in concisely and make code appear effortless.
And you get to the end and think "hey, I could have done that." One of the signs of a great teacher.
http://www-inst.eecs.berkeley.edu/~cs61a/sp14/proj/scheme/sc...
Just finished this project a month ago! It was surprisingly difficult, learned a heck of a lot. Go bears!
Yeah, I too instantly thought of the 61a project.