http://habrahabr.ru/post/227119/

Читая главу «Двоичные деревья» из книги Джона Монгана Programming Interviews Exposed я задумался о том, как чаще всего рекурсию объясняют начинающим программистам: через сортировку, обход двоичного дерева, построение последовательности Фибоначчи и т.д. Неужели нельзя найти пример поинтереснее? Из закоулков сознания вырвался Лисп, который по своей природе неотделим от понятия рекурсии. Более того, небольшой интерпретатор Лиспа — отличный пример для исследования рекурсии.

Каким же будет минимальный интерпретатор Лиспа, написанный на Питоне? К моему удивлению, решение уложилось в семь строк! Свою роль в этом сыграла как выразительность Питона, так и красота и незамысловатость Лиспа.

Сначала, надо определиться с грамматикой и способом вычисления выражений:

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

Правила вычисления такие же, как и в любом другом диалекте Лиспа: первый элемент
списка — это функция, остальные — аргументы функции:

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

Обратите внимание на то, что список записывается в форме кортежа (tuple) Питона. Этот чит позволяет перенести задачи лексического и ситактического анализа на плечи самого Питона. Кроме того, сам по себе интерпретатор не содержит встроенных операторов и специальных форм. Всё это может быть добавлено в качестве расширений.

Давайте приведём несколько примеров, перед тем как переходить к коду интерпретатора и расширающих его функций:

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

Ну всё, довольно лирики, перейдём к программированию!

Крошечный интерпретатор Лиспа

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

Вот и всё! А работает это так:

1. Сначала мы проверяем тип входных данных: атом ли это, или список (в нашем случае — tuple)? Если это атом, то его значение возвращается неизменным. Т.е. например eval(1) вернёт 1.
2. Если же аргумент — это кортеж, то мы обозначем первый элемент списка как функцию, а все остальные элементы списка — как аргументы функции. При этом, каждый аргумент вычисляется на месте используя рекурсивный вызов eval().

С голым интерпретатором далеко не пойдёшь. Давайте немного его расширим.

plus

Начнём с простой математической функции сложения. В различных диалектах Лиспа сложение обозначается знаком + (а вы как думали?) Однако из-за ограничений синтаксиса Питона, написать (+, 2, 3) у нас не получится. Поэтому назовём операцию сложения словом 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

Для отделения кода от данных в Лиспе используется специальная форма «цитирования» данных — quote. Например в Emacs-Lisp: (quote 1 2 3). Эту запись можно сократить записав quote с помощью одинарной кавычки перед данными: '(1 2 3). Без «цитирования», Лисп будет расценивать подобное выражение как: 1 — это название функции, 2 3 — это аргументы функции, что безусловно вызовет ошибку исполнения. Т.к. синтаксис Питона не даст записать данные с одинарной кавычкой, придётся использовать quote как функцию:

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

Допустим, что на вход функции подаются данные в виде списка, например (plus, (quote, 1, 2, 3)). Наш интерпретатор этого не переживёт, ведь внутри всё это закончится вызовом sum([(1,2,3), ]). Для разрешения этой ситуации в Лиспе существует функция 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 и inc

Куда же без классической функции map! Map применяет данную функцию к каждому из элементов данного списка и возвращает результат в виде нового списка. Например: (map, inc, (quote, 1, 2, 3)) возвращает (2, 3, 4). Здесь, inc — это функция инкремента, например (inc 10) вернёт 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)

Лямбды

Сказка заканчивается на лямбда-выражениях. Используя синтаксис Питона, невозможно автоматически вызывать eval() внутри тела лямбда-функции:

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

не работает, т.к. выражение (plus, x, 1) не вычисляется. Чтобы получился требуемый результат, тело лямбда-функции можно переписать следующим образом:

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

что конечно же нарушает последовательность синтаксиса.

Этот интерпретатор можно расширить ещё десятком-другим полезных функций. Но как ни крути, он ограничен синтаксисом Питона и полноценного Липса при таком подходе из него не выжать.

Я надеюсь, что вы узнали для себя что-то новое и полезное, и что хабравчане считавшие Лисп сложным набором скобок, пересмотрят своё мнение :)