Learn to Code via Tutorials on Repl.it

← Back to all posts
PyLisp: LISP in Just Over 100 Lines of Python
ericqweinstein (195)

Hi everyone,

I recently posted a little LISP in JavaScript (with an accompanying tutorial). People seemed to like it, so here's another, slightly improved version: this time in Python!

This tutorial is very similar to the JavaScript one, so I recommend you read that one first (at least to get a sense of how our program turns text into tokens, then parses the resulting structure to figure out what to do). I figured I'd do a repl talk post to highlight the differences between the Python version and the JS one.

First, our Python version includes three LISPy functions: car (which gets the head, or first element, of a list), cdr (which gets the tail of the list: everything except the first element), and cons (which prepends an element to a list):

def __init__(self):
    self.env = {
        '==': lambda args: args[0] == args[1],
        '!=': lambda args: args[0] != args[1],
        '<': lambda args: args[0] < args[1],
        '<=': lambda args: args[0] <= args[1],
        '>': lambda args: args[0] > args[1],
        '>=': lambda args: args[0] >= args[1],
        '+': lambda args: reduce((lambda x, y: x + y), args),
        '-': lambda args: reduce((lambda x, y: x - y), args),
        '*': lambda args: reduce((lambda x, y: x * y), args),
        '/': lambda args: reduce((lambda x, y: x / y), args),
        'car': lambda args: args[0][0],
        'cdr': lambda args: args[0][1:],
        'cons': lambda args: [args[0]] + args[1]
    }

Try them out in the REPL to see how they work! What do you think (car (quote (1 2 3))) will evaluate to?

The rest of the functions (run(), parse(), tokenize(), read(), and atom()) are almost identical to their JavaScript versions, so let's skip ahead to the differences in our eval() function.

As before, we return if we don't have an expression to evaluate, and we return number and string literals when we see them. The major difference is that this eval() takes a second parameter, an optional environment hash, and uses that to look up terms that have been defined (including literals, as in (define pi 3.14159), and function names, as in (define square (lambda (x) (* x x)))).

Skipping over our 'quote' branch for a moment, we see that the rest of our functions use this env to figure out what to do. Our 'if' branch (which handles conditionals, such as (if (< 2 3) 'yup' 'nope') pulls out the test expression (in this example, (< 2 3)) and evaluates it, returning the first option ('yup') if the expression evaluates to True and the second option ('nope') if it's False. We use the 'define' branch to add new identifiers to our environment (for naming variables and functions).

The next two branches, which handle lambdas and function calls, respectively, are a little tricky, so we'll go through them in slightly more detail. In the 'lambda' branch, we first separate the expression into the lambda keyword (which we assign to _, meaning we're not going to use it in our evaluation), the parameters to the function (var), and function body (e). We then return a Python lambda, recursively calling self.eval() on the function body, passing the bound arguments and parameters as the second argument. dict(zip(params, args)) turns two lists (such as ['x', 'y'] and [1, 2]) into a dictionary, like {'x': 1, 'y': 2}, which represents the parameters our function accepts bound to the arguments the user passes in.

The final else branch handles function calls: the function name (or operator, for arithmetic) is the first argument, and the arguments to the function are the rest of the expression. We go ahead and evaluate each argument to get its value before calling the function name with these values, ultimately turning something like (square 10) into (* 10 10), which is 100.

Last but not least, the aforementioned 'quote' branch handles list quoting: since function invocations are lists in LISP, we define list literals using quote. (quote (1 2 3)) should return the Python list [1, 2, 3], which means we can use list functions like car, cdr, and cons.

What do you get if you type the following?

(define pi 3.14159)
(define square (lambda (x) (* x x)))
(define circle-area (lambda (r) (* pi (square r))))
(circle-area 100)

So there we have it: a little LISP in just over 100 lines of Python. Feel free to fork this REPL and add your own improvements!