Lisp's mini-interpreter in Python

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

What will be the minimal Lisp interpreter written in Python? To my surprise, the decision went in seven lines! Both the expressiveness of Python and the beauty and uncomplicated nature of Lisp played a role in this.

First, you need to decide on the grammar and the 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 the function, the rest are the function arguments:
')

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

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

Let's give a few examples before moving on to the interpreter code and its expanding functions:

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

All right, enough of the 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 data: is it an atom, or a list (in our case, a tuple)? If it is an atom, 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 function arguments. In this case, each argument is computed in place using the recursive call to eval() .

With a naked interpreter you will not go far. Let's expand it a little bit.

plus

Let's start with a simple mathematical addition function. In various Lisp dialects, addition is denoted by the + sign (and what did you think?) However, due to the limitations of the Python syntax, we cannot write (+, 2, 3) . 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 data “citing” is used - quote . For example, in Emacs-Lisp: (quote 1 2 3) . This record can be abbreviated by writing quote with a single quote before the data: '(1 2 3) . Without "quoting", Lisp will regard this expression as: 1 is the name of the function, 2 3 are the arguments of the function, which will certainly cause an execution error. Since Python syntax will not allow writing data with a single quote, you 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)) 

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

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

The comments on the article discuss various options for correcting this flaw.

apply

Suppose that the input of a function is supplied data in the form of a list, for example (plus, (quote, 1, 2, 3)) . Our interpreter will not survive this, because inside it all ends with a call to 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 map function! Map applies this function to each of the elements of this list and returns the result as a new list. For example: (map, inc, (quote, 1, 2, 3)) returns (2, 3, 4) . Here, inc is an increment function, for example (inc 10) returns 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) 

Lambda

The tale ends in lambda expressions. Using Python syntax, you cannot automatically call eval() inside the body of a lambda function:

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

does not work, because expression (plus, x, 1) not calculated. 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 a dozen or so other useful functions. But whatever one may say, it is limited to the syntax of Python and full-fledged Lips with this approach not to squeeze out.

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