Python Lisp mini interpreter

Reading the chapter “Binary Trees” from John Mongan’s book Programming Interviews Exposed, I thought about how recursion is most often explained to novice programmers: through sorting, traversing a binary tree, building a Fibonacci sequence, etc. Is it really impossible to find an example more interesting? Lisp escaped from the back streets of consciousness, which by its nature is inseparable from the concept of recursion. Moreover, the small Lisp interpreter is a great example for exploring recursion.

What will be the minimal Lisp interpreter written in Python? To my surprise, the solution fit in seven lines! Both the expression of Python and the beauty and uncomplicatedness of Lisp played a role in this.

First, you need to determine the grammar and method of calculating expressions:

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

The calculation rules are the same as in any other Lisp dialect: the first element of the list is a function, the rest are function arguments:

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

Note that the list is written in the form of a Python tuple. This cheat allows you to transfer the tasks of lexical and sitactic analysis to the shoulders of Python himself. In addition, the interpreter itself does not contain built-in operators and special forms. All of this can be added as extensions.

Let's give some examples before moving on to the code of the interpreter and the functions expanding it:

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

That’s it, pretty lyrics, let's move on to programming!

Tiny Lisp interpreter

def eval(list_or_atom):
    if isinstance(list_or_atom, tuple):
        # код подправлен, согласно комменатариям StreetStrider и Amper
        fn, *fn_args = [eval(item) for item in list_or_atom]
        return fn(*fn_args)
    else:
        return list_or_atom

That's all! And it works like this:

1. First, we check the type of input: is it an atom, or a list (in our case, tuple)? If it is an atom, then its value is returned unchanged. Those. for example eval(1)returns 1.
2. If the argument is a tuple, then we denote the first element of the list as a function, and all other elements of the list as arguments of the function. In this case, each argument is calculated in place using a recursive call eval().

You will not go far with a naked interpreter. Let's expand it a bit.

plus

Let's start with a simple mathematical addition function. In various Lisp dialects, addition is indicated by a sign +(what do you think?) However, due to limitations of the Python syntax, (+, 2, 3)we will not be able to write . Therefore, we call the addition operation the word plus:

def plus(*args):
    """Sums up the input arguments."""
    return sum(args)
eval((plus, 3, 4, 5))
>>> 12
# с рекурсией
eval((plus, 3, (plus, 2, 10), 5))
>> 20

quote

To separate the code from the data in Lisp, a special form of "citation" of data is used - quote. For example, in Lisp-the Emacs: (quote 1 2 3). This entry can be reduced by writing quote by a single quotation mark before the data: '(1 2 3). Without "quoting", Lisp will regard this expression as: 1- this is the name of the function, 2 3- these are the arguments of the function, which will certainly cause an execution error. Because Python's syntax will not allow writing data with a single quote, you have to use it quoteas 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))

UPD: kmeaw quite correctly noted that in a full-fledged Lisp quote should work differently: not a single element of the list is evaluated. For example in Elisp:

'(1 2 '(3 4))
>>> (1 2 (quote 3 4))

In the comments to the article, various options for correcting this shortcoming are discussed.

apply

Suppose that the input of the function is data in the form of a list, for example (plus, (quote, 1, 2, 3)). Our interpreter will not survive this, because inside it will all end in a challenge sum([(1,2,3), ]). To resolve this situation in Lisp there is a function apply:

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

Where without the classic function map! Map applies this function to each of the elements in this list and returns the result as a new list. For example: (map, inc, (quote, 1, 2, 3))returns (2, 3, 4). Here, incis an increment function, for example it (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

The tale ends with lambda expressions. Using Python syntax, it is impossible to automatically call eval()lambda functions inside the body:

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

does not work, because expression is (plus, x, 1)not evaluated. To get the desired result, the body of the lambda function can be rewritten as follows:

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

which of course violates the syntax sequence.

This interpreter can be expanded with dozens of other useful functions. But whatever one may say, it is limited by the syntax of Python and full-fledged Lips with such an approach not to squeeze out of it.

I hope that you have learned something new and useful for yourself, and that the Habravites who considered Lisp as a complex set of brackets will reconsider their opinion :)