Пользователь
0,0
рейтинг
24 июня 2014 в 18:20

Разработка → Мини-интерпретатор 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)))

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

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

Я надеюсь, что вы узнали для себя что-то новое и полезное, и что хабравчане считавшие Лисп сложным набором скобок, пересмотрят своё мнение :)
Zaur Nasibov @BasicWolf
карма
46,2
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (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.

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