A mini-Lisp interpreter on a Python

as "Binary trees" from the book of John Mongan Programming Interviews Exposed I got to thinking about how often I explain recursion to novice programmers: through sorting, bypass a binary tree, build the Fibonacci sequence, etc. can't they find a more interesting example? From the dark corners of consciousness escaped the Lisp, which by its nature is inseparable from the concept of recursion. Furthermore, a small Lisp interpreter is a great example to study recursion.

What will be the minimum Lisp interpreter written in Python? To my surprise, the solution was placed in seven rows! My role in this was played as the expressiveness of Python and the beauty and plainness of Lisp.

First, we need to define a grammar and way of expression evaluation:

the

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

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

the

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

Please note that the list is written in the form of a tuple (tuple) Python. This cheat allows you to move tasks lexical analysis and staticheskogo on the shoulders of the Python. In addition, the interpreter provides no built-in operators and special forms. All this can be added as extensions.

Let's give some examples, before moving on to the code of the interpreter and russiausa of its functions:

the

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

Okay, enough lyrics, move on to programming!

Tiny Lisp interpreter

the

def eval(list_or_atom):
if isinstance(list_or_atom, tuple):
# code is corrected according to kommentariem StreetStrider and 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:

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

With a bare interpreter won't get very far. Let's expand it a bit.

plus

Let's start with simple math functions of addition. In various dialects of Lisp, the addition is indicated by + (and you as thought?) However, due to limitations of the syntax of Python to write (+, 2, 3) we did not succeed. Therefore, we call the operation of adding the word plus:

the

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

To separate code from data in Lisp is a special form of "citation" data — quote. For example, in Emacs Lisp: (quote 1 2 3). This entry can be shortened by writing a quote with a single quote before the data: '(1 2 3). No "citation", Lisp will interpret such an expression as 1 is the name of the function, 2 3 is the function's arguments, which certainly will cause a run-time error. Because the syntax of Python will not allow you to write data with a single quote, you will have to use the quote as a function:

the

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 rightly pointed out that in the full quote Lisp should work differently: there is no element in the list is not evaluated. For example in Elisp:

the

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

In the comments to the article are discussed various options for remedying this deficiency.

apply

Suppose that the function serves the data in a list e.g. (plus (quote, 1, 2, 3)). Our interpreter did not survive, because everything inside it will end with a call to sum([(1,2,3), ]). To resolve this situation, in Lisp there is a function apply:

the

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 do without the classic functionality of the map! Map applies the given function to each element of the given list and returns the result as a new list. For example: (map, inc, (quote, 1, 2, 3)) returns (2, 3, 4). Here, inc is a function of the increment, such as (inc 10) returns 11.

the

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 story ends on lambda expressions. Using the syntax of Python does not call eval() inside the body of the lambda function:

the

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

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

the

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

that certainly breaks the sequence of syntax.

This interpreter can be extended for another a dozen of other useful features. But anyway, it is limited by the syntax of Python and a full lips with this approach, he did not squeeze.

I hope you learned something new and useful, and what habracha considered Lisp a complex set of parentheses will reconsider :)

Article based on information from habrahabr.ru