Мини-интерпретатор Lisp'a на Python

[RPG]

считавшие Лисп сложным набором скобок

По-моему лисп это как раз самое простое что можно только вообще интерпретировать. Интерпретатор лиспа на Си с реализацией основных функций укладывается в несколько сот строк кода, что идеально подходит для изучения языков программирования. Вот кстати один такой: piumarta.com/software/lysp/

[mktums]

Ну, интерпретатор Malbolge на Си занимает ~100 строк, однако… ;)

[RPG]

Ну давайте ещё машину Тьюринга вспомним:)

[ruikarikun]

Интерпретатор Brainfuck тоже небольшой, да.

[Athari]

Несколько сот строк кода на лисп? Зачем так много кода?

#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");}} 

(Инструкция.)

[StreetStrider]

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

Здесь я в качестве головной формы передал сконструированную лямбду.

[BasicWolf]

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

[ruikarikun]

>>>К моему удивлению, решение уложилось в семь строк!

Можно сделать однострочник!

eval = lambda x: x[0]([eval(i) for i in x[1:]]) if isinstance(x, tuple) else x

Более того, получившийся однострочник умещается в 79 байт, что соответствует PEP-8.

[ruikarikun]

Прошу прощения, потерял один символ.

eval = lambda x: x[0](*[eval(i) for i in x[1:]]) if isinstance(x,tuple) else x

[ruikarikun]

Сократил до 72 байт, используя map():

eval = lambda x: x[0](*map(eval, x[1:])) if isinstance(x, tuple) else x

[valplo]

ИМХО, звездочка совершенно не нужна.

[ruikarikun]

Если цель интерпретации лиспа — получить много круглых скобочек, то звёздочка даже вредна!

Судите сами (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))

[BasicWolf]

Красота! Только такое человеку, который знакомится с Python лучше не показывать (не о себе, вообще о начинающих в Python :)

[valplo]

Но у quote звездочку вы не убрали (правильно: «quote = lambda args: args») — отсюда лишнее скобки. Логично, что лисп-функция берет на вход список параметров, а не переменное число параметров.

[ruikarikun]

del

[SteveNers]

Power of python)

[kmeaw]

Ваш интерпретатор неправильно реализует 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)

[BasicWolf]

Подскажите пожалуйста, а что собственно не так с quote?

[kmeaw]

> (quote (1 2 (quote 3 4)))
'(1 2 (quote 3 4))

quote потому и quote, что останавливает eval.

[BasicWolf]

Точно, спасибо большое! Если вы не против, использую Ваш код в UPD статьи.

[kmeaw]

Я не против, но лучше взять вариант mayorovp.

[BasicWolf]

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

[mayorovp]

Зачем у вас операция 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)

[JIghtuse]

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

[xkrt]

… и перевод статьи на хабре: (Как написать (Lisp) интерпретатор (на Python))

[Amper]

        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]

[BasicWolf]

Полностью согласен, сейчас подправлю.

[ruikarikun]

До чего же всё-таки красивый код можно писать на Python.