How to Write a Lisp Interpreter In Python (2010) | Hacker News Reader

How to Write a Lisp Interpreter In Python (2010)

norvig.com

132 pointsKibbutzDalia29 comments

The article uses a simplified version of Scheme as a toy Lisp, for an exercise, which is an excellent choice, but a downside is that it could be misinterpreted as characterizing Scheme well.

First, there's what I think is an important distinction of idiomatic programming in Scheme, for which the first example in the article gives the wrong idea, with a noble lie: that Java code implies an immediate return, but the Scheme code does not.

Were that Scheme expression not in a tail position of a procedure (which it probably wouldn't be), it wouldn't have effect analogous to that of the Java code. And a one-armed `if` makes little sense in a tail position in modern Scheme, and looks erroneous.

Scheme is a full imperative algorithmic language, and doesn't have to be used in a pure-functional way, but idiomatic programming in Scheme tends to lean towards functional when practical. You almost never do premature returns quite like that in Scheme, for example. (One can do most any memory-safe thing one wants, including the less-idiomatic and even the outrageously insane, but hopefully over time one learns the idiomatic ways, rather than overuses/misuses less-idiomatic features, like leaning on a crutch they don't need and that's actually harmful to them.)

Separate from that, another thing possibly misleading about this article is that their Scheme implementation doesn't do what's sometimes called "proper implementation of tail calls" (which would be required to be a real Scheme). Idiomatic Scheme will tend to use tail calls heavily, with impunity, which would not be the case if a Scheme implementation let such calls exhaust resources.

You realize the person whose code you are criticizing wrote one of the classic books on Lisp right?

You realize that the OP's concerns actually intesify if the author in question is perceived as an authority on the topic, right?

You realise it's problematic to emphasise typos, right?

You realize it's problematic to emphasize typos, right?

(Thanks, would edit if I could.)

I suspect he'd agree that this piece can be misinterpreted to give people the wrong idea about Scheme, despite the kind words he has for Scheme.

Scheme already has undeserved image problems, from various CS101 drive-by exposures that students get to it, never properly learning it.

https://en.wikipedia.org/wiki/Argument_from_authority

The other things that "beginner" tutorials such as this do is they say "lisp" when they really mean "something resembling Scheme".

I started a project some time ago to write an elisp interpreter, mostly for fun. But since elisp is much more like Common Lisp than Scheme, it has a surprising amount more syntax than a Scheme does. The parser was much more complex than I initially thought it would be.

(An ((Even Better) Lisp) Interpreter (in Python)) http://norvig.com/lispy2.html

And an even better:

https://github.com/hylang/hy

This is not better at least in the traditional ways Lisp is evaluated by. The scoping rules inherit Python’s confusing and conflated notions of binding vs mutation.

Not to take away from the side splitting hilariousness of this novel meme, but I just noticed Lisp is actually one of the few languages where you can't add spurious parentheses. If you find that a, (a), ((a)), etc are equivalent, it's probably not Lisp you're looking at.

Unless a is a function that returns itself

In Scheme or Clojure, but not in Common Lisp. Now, should we adopt this parentheses-exacticity as part of the definition what is a real Lisp?

P.S. Of course, a Lisp-2 saves us only from an unlimited proliferation of parentheses, but a simple (defmacro foo () 'foo) will allow you to get a couple whenever really needed.

Thread from 2016: https://news.ycombinator.com/item?id=12777852

2014: https://news.ycombinator.com/item?id=7825054

Two in 2010: https://news.ycombinator.com/item?id=1746916

and https://news.ycombinator.com/item?id=1745322

I've noticed you do these quite often, and I thoroughly approve. I just wonder, do you do all of them by hand, or have you automated the process by now?

We do have the "past" link at the top of the page.

I too was wondering this. Is this your full time job? Are you a bot? :-) Just kidding. I too find this useful - found some interesting discussions on the Constructing a Compiler thread from yesterday. Keep up the good work!

Not automated. I look at the threads first, to make sure there's something relevant to bother clicking on.

And of course, evolution of the code with great explanations - http://www.michaelnielsen.org/ddi/lisp-as-the-maxwells-equat... .

Particularly good is (canonical?) lisp-in-lisp code at the end.

This is the final project of Berkeley's intro to cs class, cs61a.org.

It used to be writing a Lisp interpreter in Lisp.

This is such a great post, and if you are new to Lisp or Compilers or PLT I would recommend investing time in it.

> I think it meets Alan Kay's 1972 claim that you could define the "most powerful language in the world" in "a page of code." (However, I think Alan would disagree, because he would count the Python compiler as part of the code, putting me well over a page.)

If anyone is curious, I have some ideas on how you could more precisely define this problem and an objective mathematical way of evaluating it. Shoot me an email if curious.

I wrote my own lisp interpreter in python and it was a very instructive experience, especially since you can get a simple working prototype in one day of hacking around.

Then I got stuck at recursively evaluating macros.

I wrote a Golang version when I was trying to learn Go: https://github.com/bediger4000/lisp-in-python-in-go

This is a great article.

There is btw a bug in the read_from_tokens

  >>> parse("(")
  ...
  IndexError: list index out of range

Is there a rustlang version of this?

It's not a nice blog post and it's horribly incomplete, but I did write this JIT-compiled programming environment for a Scheme-like language in Rust.

https://github.com/michaelmelanson/risp

this has been on before https://news.ycombinator.com/item?id=1745322

I used the same article to write lisp in C#.... worked out really nice

Discussed other times too:

https://news.ycombinator.com/item?id=7825054 (2014)

https://news.ycombinator.com/item?id=12777852 (2016)

Reply on news.ycombinator.com