(An ((Even Better) Lisp) Interpreter (in Python)) | Hacker News Reader

(An ((Even Better) Lisp) Interpreter (in Python))

norvig.com

140 pointscgopalan17 comments

If you like this sort of thing and want to learn Haskell, consider looking at "Write Yourself a Scheme in 48 Hours"[1]. Of course, writing a Scheme interpreter in Scheme is also classic; SICP[2] is also worth perusing.

[1]: http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_H...

[2]: http://mitpress.mit.edu/sicp/

I have been having a lot of fun hacking together a simple Scheme interpreter in C. This is my guide: http://michaux.ca/articles/scheme-from-scratch-bootstrap-v0_...

The implementation of an interpreter has always interested me, but I never thought it was within my reach as a weekend project. Norvig's original lis.py post made me look around for other implementations. This follow-up is a real treat.

My favorite HN posting of the year so far.

There's no good reason for the label "lambda"!

The footnote was interesting. Instead of (lambda (x) (* x x)), Smalltalk writes [:x | x*x]. Apparently Church's original lambda notation was very close to that.

This helps more than you'd think. For example, (if condition (lambda () foo) (lambda () bar)) is too verbose, but (if condition [foo] [bar]) is fine. Simplifying lambda gives you lazy evaluation, and then you don't need syntax for conditionals.

An alternative solution: if you're willing to allow non-ASCII characters into your source code, then DrRacket provides a keyboard shortcut to insert a λ character. I'll illustrate with anonymous recursion.

  > (define sum
      (λ (n)
        ((λ (f) (f f n 0))
         (λ (f n total)
           (if (zero? n)
               total
               (f f (- n 1) (+ n total)))))))
  > (sum 10)
  55

You can go one step further and start giving things like color meaning. (example: http://www.colorforth.com/ide.html written with colorForth http://www.colorforth.com/cf.htm ) Of course, alternatives should exist for someone to write on a US-keyboard in any editor. Clojure supports two ways to do anonymous closures, though neither of them use a lambda symbol.

> if you're willing to allow non-ASCII characters into your source code

Blasphemy.

You could use any letter, really. Perhaps l or f.

Poked me in the eye as well! It's easy to find a lot of interesting and illuminating writing about the importance and influence of notation and symbols, especially in famous cases (say, Leibniz's vs Newton's) but why a specific foo is named foo can be an oddly tricky and inconclusive nerd googlegame (nerd googlegame may be highly redundant).

Gamma function, gamma constant, gamma correction, gamma radiation, gamma distribution, and there went an hour I could have been wasting on today's best catpictures.

A sequel to this article, where Norvig explains how to make a really minimal (but ridiculously clear and elegant) Lisp interpreter in 90 lines of Python:

http://norvig.com/lispy.html

From the URLs, it looks like a prequel.

just looks like "this" needs to be properly disambiguated :)

Wow, that's kind of embarrassing. To eliminate ambiguity, here they are in order:

http://norvig.com/lispy.html

http://norvig.com/lispy2.html

2 comes after? I don't know...

It doesn't implement real call/cc and continuations, which is what I want to learn. Still great stuff.

Lisp in Small Pieces covers call/cc and much more, and I highly recommend it. It's deep and rich, so be warned that it may completely devour your time.

Another look at call/cc is in Marc Feeley's 90 Minute Scheme to C Compiler:

http://news.ycombinator.com/item?id=2633841 (submission that incudes a link to slides and video)

I feel like:

Interpreter in C: an implementation. Interpreter in Python: an exercise.

Reply on news.ycombinator.com