Читая главу «Двоичные деревья» из книги Джона Монгана Programming Interviews Exposed я задумался о том, как чаще всего рекурсию объясняют начинающим программистам: через сортировку, обход двоичного дерева, построение последовательности Фибоначчи и т.д. Неужели нельзя найти пример поинтереснее? Из закоулков сознания вырвался Лисп, который по своей природе неотделим от понятия рекурсии. Более того, небольшой интерпретатор Лиспа — отличный пример для исследования рекурсии.
Каким же будет минимальный интерпретатор Лиспа, написанный на Питоне? К моему удивлению, решение уложилось в семь строк! Свою роль в этом сыграла как выразительность Питона, так и красота и незамысловатость Лиспа.
Сначала, надо определиться с грамматикой и способом вычисления выражений:
Правила вычисления такие же, как и в любом другом диалекте Лиспа: первый элемент списка — это функция, остальные — аргументы функции:
Обратите внимание на то, что список записывается в форме кортежа (tuple) Питона. Этот чит позволяет перенести задачи лексического и ситактического анализа на плечи самого Питона. Кроме того, сам по себе интерпретатор не содержит встроенных операторов и специальных форм. Всё это может быть добавлено в качестве расширений.
Давайте приведём несколько примеров, перед тем как переходить к коду интерпретатора и расширающих его функций:
Ну всё, довольно лирики, перейдём к программированию!
Вот и всё! А работает это так:
С голым интерпретатором далеко не пойдёшь. Давайте немного его расширим.
Начнём с простой математической функции сложения. В различных диалектах Лиспа сложение обозначается знаком
Для отделения кода от данных в Лиспе используется специальная форма «цитирования» данных —
UPD: kmeaw совершенно правильно заметил, что в полноценном Лиспе quote должен работать по-другому: ни один элемент списка не вычисляется. Например в Elisp:
В комментариях к статье обсуждаются различные варианты исправления этого недостатка.
Допустим, что на вход функции подаются данные в виде списка, например
Куда же без классической функции
Сказка заканчивается на лямбда-выражениях. Используя синтаксис Питона, невозможно автоматически вызывать
не работает, т.к. выражение
что конечно же нарушает последовательность синтаксиса.
Этот интерпретатор можно расширить ещё десятком-другим полезных функций. Но как ни крути, он ограничен синтаксисом Питона и полноценного Липса при таком подходе из него не выжать.
Я надеюсь, что вы узнали для себя что-то новое и полезное, и что хабравчане считавшие Лисп сложным набором скобок, пересмотрят своё мнение :)
Каким же будет минимальный интерпретатор Лиспа, написанный на Питоне? К моему удивлению, решение уложилось в семь строк! Свою роль в этом сыграла как выразительность Питона, так и красота и незамысловатость Лиспа.
Сначала, надо определиться с грамматикой и способом вычисления выражений:
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 и Amper
fn, *fn_args = [eval(item) for item in list_or_atom]
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))
UPD: kmeaw совершенно правильно заметил, что в полноценном Лиспе quote должен работать по-другому: ни один элемент списка не вычисляется. Например в Elisp:
'(1 2 '(3 4))
>>> (1 2 (quote 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)))
что конечно же нарушает последовательность синтаксиса.
Этот интерпретатор можно расширить ещё десятком-другим полезных функций. Но как ни крути, он ограничен синтаксисом Питона и полноценного Липса при таком подходе из него не выжать.
Я надеюсь, что вы узнали для себя что-то новое и полезное, и что хабравчане считавшие Лисп сложным набором скобок, пересмотрят своё мнение :)