Міні-інтерпретатор 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

Ось і все! А працює це так:
 
     
  1. Спочатку ми перевіряємо тип вхідних даних: атом це, чи список (у нашому випадку — tuple)? Якщо це атом, то його значення повертається незмінним. Тобто наприклад
    eval(1)
    поверне
    1
    .
  2.  
  3. Якщо ж аргумент — це кортеж, то ми позначили перший елемент списку як функцію, а всі інші елементи списку — як аргументи функції. При цьому, кожен аргумент обчислюється на місці використовуючи рекурсивний виклик
    eval()
    .
  4.  
З голим інтерпретатором далеко не підеш. Давайте трохи його розширимо.
 
 
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)))

що звичайно ж порушує послідовність синтаксису.
 
Цей інтерпретатор можна розширити ще десятком-другим корисних функцій. Але як не крути, він обмежений синтаксисом Пітона та повноцінного Ліпса при такому підході з нього не вичавити.
 
Я сподіваюся, що ви дізналися для себе щось нове і корисне, і що хабравчане вважали Лисп складним набором дужок, переглянуть свою думку :)
    
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.