A Little Lisp Interpreter in Python

When reading the “Binary trees” chapter in Programming Interviews Exposed by John Mongan, I thought about the ways recursion is explained to beginners. For example, via sorts, traversing binary trees, building Fibonacci sequence and so on and so forth. But is it really that difficult to find a more interesting example? That’s when Lisp came to my mind, as it is inseparable from the notion of recursion. Moreover, a little Lisp interpreter is a great example to study recursion.

What would be a minimal Lisp interpreter written in Python? To my surprise, the solution was seven lines long! Python expressiveness and Lisp beauty and simplicity served their purpose.

To start with, let’s define the grammar and the way to evaluate expressions:

list := (item0, item1, ...)
item := list | atom
atom := stringliteral | numliteral

Evaluation rules are just like in any other Lisp dialect. The first element of a list is a function; the other ones are function arguments:

fn = list[0]
args = list[1:]

You should note that the list is written in the form of a Python tuple. This cheat allows to shift the tasks of lexical and syntactical analysis to Python’s shoulders. Besides, the interpreter itself does not have embedded operators and special forms. We can add all of that as enhancements.

Before moving to the interpreter code and expansive functions, let’s take a look at some examples:

(quote, 1, 2, 3) # >>> (1, 2, 3)
  (plus, 1, 2, 3)  # >>> 6
  (inc, 10)        # >>> 11

Anyway, it’s high time to get down to programming!

A Tiny Lisp Interpreter

def eval(list_or_atom):
    if isinstance(list_or_atom, tuple):
        # the code is sent, according to  StreetStrider and Amper comments 
        fn, *fn_args = [eval(item) for item in list_or_atom]
        return fn(*fn_args)
    else:
        return list_or_atom

That’s it! And that’s how it works:

1. At first we check the type of the input data. Is it an atom or a list (in our case it’s a tuple)? If it is an atom, return its unmodified value. For instance, eval(1) will return 1.
   
2. If an argument is a tuple, we define the first element of the list as a function and all other list elements as function arguments. At that, we calculate each argument with the help of recursive call of eval().
   

But bare interpreter will get you only so for. Let’s extend it a bit.

plus

Let’s start with a simple mathematic addition function. In different Lisp dialects addition is marked with + sign (what did you think?). But due to Python syntax limits, you will not be able to write (+, 2, 3). Therefore, we should name the addition operation as plus:

def plus(*args):
    """Sums up the input arguments."""
    return sum(args)
eval((plus, 3, 4, 5))
>>> 12
# with recursion
eval((plus, 3, (plus, 2, 10), 5))
>> 20

quote

Lisp has a special form of data «quoting» – quote. It's intended to separate the code from the data. For instance, in Emacs-Lisp: (quote 1 2 3). We can shorten this line by writing quote with the help of a single quote before the data: '(1 2 3). Without “quoting”, Lisp will think that: 1 is the function name, while 2 3 are function arguments, which will definitely lead to an execution error. Since Python syntax will not allow to write new data using a single quote, we will have to use quote as a function:

def quote(*args):
    """Returns a list without evaluating it."""
    return tuple(args)
eval((quote, 'x', 3, 0.7))
>>> ('x', 3, 0.7)
eval((quote, 1, 2, (quote, 3, 4)))
>>> (1, 2, (3, 4))

apply

Suppose, the data is supplied to the function input in the form of a list, for example: plus, (quote, 1, 2, 3)). Our interpreter will not survive it as all of that will lead to the call of sum([(1,2,3), ]). To solve this problem, there’s apply function in Lisp:

def apply(fn, args):
    """Applies a function to a list of arguments."""
    return fn(*args)
eval((apply, plus, (quote, 1, 2, 3)))
>>> 6
map and inc

Of course, there’s map function as well. Map applies the given function to each of the list elements and returns a result as a new list. As in example: (map, inc, (quote, 1, 2, 3)) returns (2, 3, 4). inc here is the increment function, for example, (inc 10) will return 11.

def map(fn, lst):
    """Applies the function to each element of the list and returns
       the results in a new list."""
    return tuple(fn(item) for item in lst)
def inc(arg):
    """Increases the argument by 1."""
    return arg + 1
eval((map, inc, (quote, 1, 2, 3)))
>> (2, 3, 4)

Lambdas

Now let’s take a look at lambda expressions. Using Python syntax, it is impossible to automatically call eval() inside the body of a lambda function.

eval((map, lambda x: (plus, x, 1), (quote, 1, 2, 3)))

This does not work, as (plus, x, 1) expression is not calculated. To get the required result, we can rewrite the lambda function body the following way:

eval((map, lambda x: eval(plus, x, 1), (quote, 1, 2, 3)))

which, of course, violates the order of syntax.

Hope you’ve found something interesting in this article and those users thinking that Lisp is a complex set of brackets, have changed their mind :)

We can extend this interpreter with a dozen of useful functions. But after all, it is limited by Python syntax and we won’t be able to make a real Lisp from it.