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]

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.