The Tiniest Lisp (in Python)

February 19, 2008 | coding

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]

Now test it out:

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

The interpreted version is “only” about 100x slower on factorial 100.

Python native: 0.000137090682983
Python/Lisp:   0.0119869709015

Discussion

Comments are moderated whenever I remember that I have a blog.

Ryan Ginstrom | 2008-02-20 08:42:46

Nice idea. One suggestion would be to avoid shadowing the "globals" built-in function.

tim | 2008-02-20 08:57:39

Doh! Thanks.

Clint | 2008-02-20 14:30:38

Did that speed it up?

Steve | 2008-02-20 14:35:53

Very cool. Have you seen <a href="http://www.pick.ucam.org/~ptc24/yvfc.html" rel="nofollow">yvfc.py</a>? 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 <a href="http://wordpress.org/support/topic/117862#post-559262" rel="nofollow">here</a>.

John Connors | 2008-02-20 15:33:43

Would be interesting to try this with boost::lambda and the STL and see how it compares.

buccia | 2008-02-20 15:43:58

Impressive.

Larry Clapp | 2008-02-20 17:09:40

Wow, Lisp is slow! ;) (Actually, probably the ease of doing exactly what you've done contributes quite a bit to this myth. :)

Aaron Brown | 2008-02-20 18:18:09

There are a bunch of "smart" (non-ASCII) quotes in there.

stefano rossi | 2008-02-20 21:19:33

What's the purpose and usage of 'macro'? What's the purpose of type(name)==dict ?

tim | 2008-02-20 22:42:55

"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.

pozorvlak | 2008-02-21 00:01:22

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 :-) ]

Eduardo | 2008-02-21 00:52:02

As someone who bounces between Python and Scheme a lot, I can only say <b><i>Schweeeeeet!</i></b>

Freudness | 2008-02-21 05:02:55

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]".

stefano rossi | 2008-02-21 17:36:23

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)

tim | 2008-02-21 20:23:42

@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.

stefano rossi | 2008-02-22 00:33:20

It's working now, I can show you some interesting code, how can I send you an email?

tim | 2008-02-22 06:46:49

@Stefano: sent you mail, but it bounced -- my e-mail is in the sidebar.

sys | 2008-07-30 22:55:08

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.