Мини-интерпретатор Lisp'a на Python
Читая главу «Двоичные деревья» из книги Джона Монгана 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): fn = list_or_atom[0] fn_args = [eval (item) for item in list_or_atom[1:]] return fn (*fn_args) else: return list_or_atom Вот и всё! А работает это так: Сначала мы проверяем тип входных данных: атом ли это, или список (в нашем случае — tuple)? Если это атом, то его значение возвращается неизменным. Т.е. например eval (1) вернёт 1. Если же аргумент — это кортеж, то мы обозначем первый элемент списка как функцию, а все остальные элементы списка — как аргументы функции. При этом, каждый аргумент вычисляется на месте используя рекурсивный вызов 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))) что конечно же нарушает последовательность синтаксиса.Этот интерпретатор можно расширить ещё десятком-другим полезных функций. Но как ни крути, он ограничен синтаксисом Питона и полноценного Липса при таком подходе из него не выжать.
Я надеюсь, что вы узнали для себя что-то новое и полезное, и что хабравчане считавшие Лисп сложным набором скобок, пересмотрят своё мнение:)
