The Tiniest Lisp (in Python)
I was inspired by a link I had found on LtU: the Lisp 1.5 reference manual. If you look at page 13 you will see a simple definition of the core of Lisp. Really, it’s beautiful.
Accordingly, I spent a bit of time implementing the simplest possible Lisp in Python — it’s very tiny, only about 50 lines. This is maybe a rough equivalent of “stupid human tricks” for computers, but these little puzzles for some reason are fun once in a while, and you never know if what you learn might come in handy later.
As always with these kinds of things, I made it easier by cheaping it out. Basically, I’m using everything I can from Python: the datatypes, the stack, and the garbage collection.
import inspect globs = {} def isprim(name): return inspect.isfunction(globs.get(name, None)) def islazy(name): if isprim(name): return name in ['cond', 'quote', 'setq' ] return globs.get(name, [None])[0] == 'macro' def isatom(name): return not (type(name) == list or type(name) == dict) def setq(sexpr, context): globs[sexpr[0]] = sexpr[1] return sexpr[1] def _apply(fn, args, context): if isprim(fn): return globs[fn](args, context) context = dict(zip(globs[fn][1], args)) return _eval(globs[fn][2], context) def _eval(sexpr, context): if isatom(sexpr): if sexpr in context: return context[sexpr] return sexpr fn = sexpr[0] args = sexpr[1:] if not islazy(fn): args = map(lambda n: _eval(n, context), args) return _apply(fn, args, context) def _cond(sexpr, context): for elem in sexpr[0]: if _eval(elem[0], context): return _eval(elem[1], context) return False globs['setq'] = setq globs['cond'] = _cond globs['car'] = lambda sexpr, context: sexpr[0][0] globs['cdr'] = lambda sexpr, context: sexpr[0][1:] globs['quote'] = lambda sexpr, context: sexpr[0] globs['+'] = lambda sexpr, context: sexpr[0] + sexpr[1] globs['-'] = lambda sexpr, context: sexpr[0] - sexpr[1] globs['*'] = lambda sexpr, context: sexpr[0] * sexpr[1] globs['/'] = lambda sexpr, context: sexpr[0] / sexpr[1] globs['equal?'] = lambda sexpr, context: sexpr[0] == sexpr[1]
print _eval(['setq', 'factorial', ['lambda', ['x'], ['cond', [ [ ['equal?', 'x', 0], 1 ], [ True, [ '*', 'x', ['factorial', ['-', 'x', 1]]]]]]]], globs) print _eval(['factorial', 10], globs) ['lambda', ['x'], ['cond', [[['equal?', 'x', 0], 1], [True, ['*', 'x', ['factorial', ['-', 'x', 1]]]]]]] 3628800
Python native: 0.000137090682983 Python/Lisp: 0.0119869709015
Nice idea. One suggestion would be to avoid shadowing the “globals” built-in function.
Doh! Thanks.
Did that speed it up?
Very cool. Have you seen yvfc.py?
Also, can I suggest you getting rid of WordPress’s silly ‘texturize’ feature? The fancy quotes it inserts into the page makes the code unusable. See here.
Would be interesting to try this with boost::lambda and the STL and see how it compares.
Impressive.
Wow, Lisp is slow! ;)
(Actually, probably the ease of doing exactly what you’ve done contributes quite a bit to this myth. :)
There are a bunch of “smart” (non-ASCII) quotes in there.
What’s the purpose and usage of ‘macro’? What’s the purpose of type(name)==dict ?
“macro” indicates a function that lazy-evaluates the arguments — that is, they are inherently quoted. The type(name) == dict is so that I could use native Python types, although, admittedly, I probably won’t take it that far.
Dude. I once wrote a (not terribly good) 150-line Lisp interpreter in Perl, which was until now the shortest Lisp interpreter of which I was aware.
I take my hat off to you.
[Though mine had an actual parsing stage :-) ]
As someone who bounces between Python and Scheme a lot, I can only say Schweeeeeet!
You’re missing a few things, notably a _read function that accepts s-expressions and turns them into list structure. With that, you can do this for a main loop:
while 1:
print _eval(_read())
Note, you’re confusingly using the variable name “sexpr” to refer to lists. An s-expression is a string; it’s comparable to repr() of a list in Python. The s-expression “(1 2)” is equivalent to the Python repr output “[1, 2]“.
Working a lot on this code! But what’s wrong with this?:
globs["apply"] = lambda sexpr, context: Apply(sexpr[0], sexpr[1], context)
print Eval(["apply", ["quote", ["lambda", [], 1]], ["quote", [10]]], globs)
@Stefano: You want something like (apply (lambda (x) 10) ’20), right? There’s a small bug in apply — it should eval the first arg — and you’ll also need to define lambda as a function. I’m posting a follow up to this article that goes into more detail and also links to other Python/Lisp implementations, as it turns out this is territory that is well trodden.
It’s working now, I can show you some interesting code, how can I send you an email?
@Stefano: sent you mail, but it bounced — my e-mail is in the sidebar.
Nice exercise :) you didn’t have to do much work because Python is so close to Lisp. Still, writing Lisp in Lisp beats Python any day for clarity and purity.
It would be cool to get Lisp running on Google Appengine (which only supports python and java is in beta).
@Justin: Have you considered Clojure? http://elhumidor.blogspot.com/2009/04/clojure-on-google-appengine.html
[...] by Bernhard Tim Lopez published an elegant and tiny LISP interpreter for Python on his blog. Inspired by Norvig’s Paradigms [...]