Каким же будет минимальный интерпретатор Лиспа, написанный на Питоне? К моему удивлению, решение уложилось в семь строк! Свою роль в этом сыграла как выразительность Питона, так и красота и незамысловатость Лиспа.
Сначала, надо определиться с грамматикой и способом вычисления выражений:
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): """Apply the function to each element of the list and return 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))) что конечно же нарушает последовательность синтаксиса.
Этот интерпретатор можно расширить ещё десятком-другим полезных функций. Но как ни крути, он ограничен синтаксисом Питона и полноценного Липса при таком подходе из него не выжать.
Я надеюсь, что вы узнали для себя что-то новое и полезное, и что хабравчане считавшие Лисп сложным набором скобок, пересмотрят своё мнение 🙂
ссылка на оригинал статьи http://habrahabr.ru/post/227119/
Добавить комментарий