Мини-интерпретатор 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):
            # код подправлен, согласно комменатариям StreetStrider и Amper
            fn, *fn_args = [eval(item) for item in list_or_atom]
            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))
    


    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)))
    

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

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

    Я надеюсь, что вы узнали для себя что-то новое и полезное, и что хабравчане считавшие Лисп сложным набором скобок, пересмотрят своё мнение :)
    Метки:
    Поделиться публикацией
    Комментарии 28
    • +2
      считавшие Лисп сложным набором скобок
      По-моему лисп это как раз самое простое что можно только вообще интерпретировать. Интерпретатор лиспа на Си с реализацией основных функций укладывается в несколько сот строк кода, что идеально подходит для изучения языков программирования. Вот кстати один такой: piumarta.com/software/lysp/
      • –1
        Ну, интерпретатор Malbolge на Си занимает ~100 строк, однако… ;)
        • –1
          Ну давайте ещё машину Тьюринга вспомним:)
          • –1
            Интерпретатор Brainfuck тоже небольшой, да.
        • –5
          Несколько сот строк кода на лисп? Зачем так много кода?

          #define d define
          #d a include
          #a <stdio.h>
          #a <string.h>
          #a <ctype.h>
          #d p char*
          #d P ,(p)
          #d T(E) !strcmp(E,"()")
          #d U return
          #d W while
          #d X sbrk(199)
          #d z atof
          #d e isspace
          #d D A(_)
          #d E S(C(_))
          #d B(y) p y(_)p _;{
          #d G(y,V) B(y)p i;U sprintf(i=X,"%lf",z(E)V z(S(C(D)))),i;}
          
          	    p sbrk(),*S(),*j(),*O,*H;K,Y,M=14;double
          	  z();Q(_)p _;{int V=0;W(e(*_))_++;H=_;W(V|!(e
          	(*H)|*H==')'||(*H=='('&&H-_)))V+=(*H=='(')-(*H==
                ')'),H++;U H-_;}B(C)U _++,Y=Q(_),_=strncpy(X,_,Y),_[
              Y]=0,_;}B(A)_++,_+=Q(_);W(e(*_))_++;U O=X,*O='(',strcpy(
            O+1,_),O;}B(Z)U _;}B(c)U C(E);}B(q)U A(E);}B(t)p i=E;U H=S(C
          (D)),sprintf(O=X,T(H		         )?"(%s)":"(%s %s",i,H+1)
          
          	     ,O;}B(F)U S(C(A(T(E)?D:_)));}L(i,s)p
          
          i,*s;{U isdigit(*i)		?         z(i)!=z(s):strcmp(i,s);}
            B(b)U L(E,S(C(D)))?"()":"t";}B(R)U E;}B(o)U z(E)<z(S(C(D)))?
              "t":"()";}G(f,+)G(g,-)G(h,*)p r[4][2]={"function"   P R,
                "quote"P C,"lambda"P Z,"defun"P j};B(j)U r[M][1]=D,*
          	r[M++]=C(_);}p not[99][2]={"if"P F,"equal"P b,"<"
          	  P o,"+"P f,"-"P g,"*"P h,"car"P c,"cdr"P q,
          	    "cons"P t,"t","t"};B(S)int Li,s;p u;if(
          	      isdigit(*_)|T(_))U _;for(Y=M;Y--;)
          		if(!strcmp(_,*r[Y]))U r[Y][1]
          	      ;u=E,_=D;if(*u-'(')U(*((p(*)())u)
          	    )(_);s=Li=M;W(!T(_))r[M][1]=E,*r[M++]
          	="",_=D;O=C(u);W(!T(O))*r[Li++]=C(O),O=A(O);U O=S
              (C(A(u))),M=s,O;}main(){H=O=X,Y=0;W(Y|!e(K=getchar()))K==
              EOF?exit(0):0,Y+=(K=='(')-(K==')'),*H++=K;*H=0,puts(S(O))
          				,
           		main();{printf("XLISP 4.0\n");}} 

          (Инструкция.)
        • +2
          fn_args = [eval(item) for item in list_or_atom[1:]]
          

          Вы зря здесь сделали срез, нулевой элемент S-выражения также вычисляемый.
          Вот пример на языке Racket (который является диалектом Scheme, который является диалектом (не Commmon)Lisp):

          > (lambda (x) x)
          #<procedure>
          > ((lambda (x) x) 1)
          1
          

          Здесь я в качестве головной формы передал сконструированную лямбду.
          • 0
            Да, Вы абсолютно правы. Как я понял, функцию нужно извлекать после вычисления каждого элемента списка. Спасибо!
          • +8
            >>>К моему удивлению, решение уложилось в семь строк!

            Можно сделать однострочник!
            eval = lambda x: x[0]([eval(i) for i in x[1:]]) if isinstance(x, tuple) else x
            

            Более того, получившийся однострочник умещается в 79 байт, что соответствует PEP-8.
            • +4
              Прошу прощения, потерял один символ.
              eval = lambda x: x[0](*[eval(i) for i in x[1:]]) if isinstance(x,tuple) else x
              

              • +5
                Сократил до 72 байт, используя map():
                eval = lambda x: x[0](*map(eval, x[1:])) if isinstance(x, tuple) else x
                
                • –2
                  ИМХО, звездочка совершенно не нужна.
                  • +2
                    Если цель интерпретации лиспа — получить много круглых скобочек, то звёздочка даже вредна!

                    Судите сами (python 2.7):
                    >>> quote = lambda *args: tuple(args)
                    >>> eval = lambda x: x[0](map(eval, x[1:])) if isinstance(x, tuple) else x
                    >>> eval((quote, 1, 2, (quote, 3, 4)))
                    ((1, 2, ((3, 4),)),)
                    >>> eval = lambda x: x[0](*map(eval, x[1:])) if isinstance(x, tuple) else x
                    >>> eval((quote, 1, 2, (quote, 3, 4)))
                    (1, 2, (3, 4))
                    
                    • 0
                      Красота! Только такое человеку, который знакомится с Python лучше не показывать (не о себе, вообще о начинающих в Python :)
                      • +1
                        Но у quote звездочку вы не убрали (правильно: «quote = lambda args: args») — отсюда лишнее скобки. Логично, что лисп-функция берет на вход список параметров, а не переменное число параметров.
                • 0
                  del
                  • –1
                    Power of python)
                    • 0
                      Ваш интерпретатор неправильно реализует quote.
                      Предлагаю переписать eval:
                      def eval(list_or_atom, f=lambda x,y:x):
                          if isinstance(list_or_atom, tuple) and callable(list_or_atom[0]):
                              fn = list_or_atom[0]
                              fn_args = [f(item,f) for item in list_or_atom[1:]]
                              return fn(*fn_args)
                          else:
                              return list_or_atom
                      
                      def prim(f): return lambda *args: f(*map(lambda x:eval(x,eval), args))
                      
                      @prim
                      def plus(*args): return sum(args)
                      
                      • 0
                        Подскажите пожалуйста, а что собственно не так с quote?
                        • 0
                          > (quote (1 2 (quote 3 4)))
                          '(1 2 (quote 3 4))

                          quote потому и quote, что останавливает eval.
                          • 0
                            Точно, спасибо большое! Если вы не против, использую Ваш код в UPD статьи.
                            • 0
                              Я не против, но лучше взять вариант mayorovp.
                            • 0
                              kmeaw, как вариант — оставить всё как есть, в статье, в разделе о quote, написать о недостаточно правильной реализации. А вот по-поводу, как реализовать quote правильно, я бы немного поспорил: можно например внести в интерпретатор следующие изменения:

                              # ...
                              fn = eval(list_or_atom[0])
                              if fn == quote
                                  # no need to eval the rest of the list
                              else
                                 # eval the rest of the list
                              
                          • +2
                            Зачем у вас операция eval применяется к аргументам по два раза: в виде fn_args = [f(item,f) и в виде map(lambda x:eval(x,eval), args)?

                            Если уж делать декоратор для всех «библиотечных» функций — то можно вообще избавиться от прямого рекурсивного вызова внутри eval:
                            def eval(list_or_atom):
                                if isinstance(list_or_atom, tuple) and callable(list_or_atom[0]):
                                    return list_or_atom[0](*list_or_atom[1:])
                                else:
                                    return list_or_atom
                            
                            def prim(f): return lambda *args: f(*map(eval, args))
                            
                            @prim
                            def plus(*args): return sum(args)
                            


                            С учетом же замечания StreetStrider код получается вот таким:
                            def eval(list_or_atom):
                                if not isinstance(list_or_atom, tuple):
                                    return list_or_atom
                                fn = eval(list_or_atom[0])
                                if not callable(fn):
                                    return (fn,) + list_or_atom[1:]
                                return fn(*list_or_atom[1:])
                            
                            def prim(f): return lambda *args: f(*map(eval, args))
                            
                            @prim
                            def plus(*args): return sum(args)
                            
                          • +1
                            Peter Norvig однажды написал аналогичный интерпретатор, lis.py:
                            Скрытый текст
                            ################ Lispy: Scheme Interpreter in Python
                            
                            ## (c) Peter Norvig, 2010; See http://norvig.com/lispy.html
                            
                            ################ Symbol, Env classes
                            
                            from __future__ import division
                            
                            Symbol = str
                            
                            class Env(dict):
                                "An environment: a dict of {'var':val} pairs, with an outer Env."
                                def __init__(self, parms=(), args=(), outer=None):
                                    self.update(zip(parms,args))
                                    self.outer = outer
                                def find(self, var):
                                    "Find the innermost Env where var appears."
                                    return self if var in self else self.outer.find(var)
                            
                            def add_globals(env):
                                "Add some Scheme standard procedures to an environment."
                                import math, operator as op
                                env.update(vars(math)) # sin, sqrt, ...
                                env.update(
                                 {'+':op.add, '-':op.sub, '*':op.mul, '/':op.div, 'not':op.not_,
                                  '>':op.gt, '<':op.lt, '>=':op.ge, '<=':op.le, '=':op.eq, 
                                  'equal?':op.eq, 'eq?':op.is_, 'length':len, 'cons':lambda x,y:[x]+y,
                                  'car':lambda x:x[0],'cdr':lambda x:x[1:], 'append':op.add,  
                                  'list':lambda *x:list(x), 'list?': lambda x:isa(x,list), 
                                  'null?':lambda x:x==[], 'symbol?':lambda x: isa(x, Symbol)})
                                return env
                            
                            global_env = add_globals(Env())
                            
                            isa = isinstance
                            
                            ################ eval
                            
                            def eval(x, env=global_env):
                                "Evaluate an expression in an environment."
                                if isa(x, Symbol):             # variable reference
                                    return env.find(x)[x]
                                elif not isa(x, list):         # constant literal
                                    return x                
                                elif x[0] == 'quote':          # (quote exp)
                                    (_, exp) = x
                                    return exp
                                elif x[0] == 'if':             # (if test conseq alt)
                                    (_, test, conseq, alt) = x
                                    return eval((conseq if eval(test, env) else alt), env)
                                elif x[0] == 'set!':           # (set! var exp)
                                    (_, var, exp) = x
                                    env.find(var)[var] = eval(exp, env)
                                elif x[0] == 'define':         # (define var exp)
                                    (_, var, exp) = x
                                    env[var] = eval(exp, env)
                                elif x[0] == 'lambda':         # (lambda (var*) exp)
                                    (_, vars, exp) = x
                                    return lambda *args: eval(exp, Env(vars, args, env))
                                elif x[0] == 'begin':          # (begin exp*)
                                    for exp in x[1:]:
                                        val = eval(exp, env)
                                    return val
                                else:                          # (proc exp*)
                                    exps = [eval(exp, env) for exp in x]
                                    proc = exps.pop(0)
                                    return proc(*exps)
                            
                            ################ parse, read, and user interaction
                            
                            def read(s):
                                "Read a Scheme expression from a string."
                                return read_from(tokenize(s))
                            
                            parse = read
                            
                            def tokenize(s):
                                "Convert a string into a list of tokens."
                                return s.replace('(',' ( ').replace(')',' ) ').split()
                            
                            def read_from(tokens):
                                "Read an expression from a sequence of tokens."
                                if len(tokens) == 0:
                                    raise SyntaxError('unexpected EOF while reading')
                                token = tokens.pop(0)
                                if '(' == token:
                                    L = []
                                    while tokens[0] != ')':
                                        L.append(read_from(tokens))
                                    tokens.pop(0) # pop off ')'
                                    return L
                                elif ')' == token:
                                    raise SyntaxError('unexpected )')
                                else:
                                    return atom(token)
                            
                            def atom(token):
                                "Numbers become numbers; every other token is a symbol."
                                try: return int(token)
                                except ValueError:
                                    try: return float(token)
                                    except ValueError:
                                        return Symbol(token)
                            
                            def to_string(exp):
                                "Convert a Python object back into a Lisp-readable string."
                                return '('+' '.join(map(to_string, exp))+')' if isa(exp, list) else str(exp)
                            
                            def repl(prompt='lis.py> '):
                                "A prompt-read-eval-print loop."
                                while True:
                                    val = eval(parse(raw_input(prompt)))
                                    if val is not None: print to_string(val)
                            


                            Статья с описанием здесь: norvig.com/lispy.html
                          • +4
                                    eval_list = [eval(item) for item in list_or_atom]
                                    fn = eval_list[0]
                                    fn_args = eval_list[1:]

                            Думаю, что так будет красивей:

                                    fn, *fn_args = [eval(item) for item in list_or_atom]
                            • +1
                              Полностью согласен, сейчас подправлю.
                              • +1
                                До чего же всё-таки красивый код можно писать на Python.

                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.