Comments 28
считавшие Лисп сложным набором скобокПо-моему лисп это как раз самое простое что можно только вообще интерпретировать. Интерпретатор лиспа на Си с реализацией основных функций укладывается в несколько сот строк кода, что идеально подходит для изучения языков программирования. Вот кстати один такой: piumarta.com/software/lysp/
+2
Ну, интерпретатор Malbolge на Си занимает ~100 строк, однако… ;)
-1
Несколько сот строк кода на лисп? Зачем так много кода?
(Инструкция.)
#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");}}
(Инструкция.)
-5
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
Здесь я в качестве головной формы передал сконструированную лямбду.
+2
>>>К моему удивлению, решение уложилось в семь строк!
Можно сделать однострочник!
Более того, получившийся однострочник умещается в 79 байт, что соответствует PEP-8.
Можно сделать однострочник!
eval = lambda x: x[0]([eval(i) for i in x[1:]]) if isinstance(x, tuple) else x
Более того, получившийся однострочник умещается в 79 байт, что соответствует PEP-8.
+8
Прошу прощения, потерял один символ.
eval = lambda x: x[0](*[eval(i) for i in x[1:]]) if isinstance(x,tuple) else x
+4
Сократил до 72 байт, используя map():
eval = lambda x: x[0](*map(eval, x[1:])) if isinstance(x, tuple) else x
+5
ИМХО, звездочка совершенно не нужна.
-2
Если цель интерпретации лиспа — получить много круглых скобочек, то звёздочка даже вредна!
Судите сами (python 2.7):
Судите сами (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))
+2
Красота! Только такое человеку, который знакомится с Python лучше не показывать (не о себе, вообще о начинающих в Python :)
0
Но у quote звездочку вы не убрали (правильно: «quote = lambda args: args») — отсюда лишнее скобки. Логично, что лисп-функция берет на вход список параметров, а не переменное число параметров.
+1
del
0
Power of python)
-1
Ваш интерпретатор неправильно реализует quote.
Предлагаю переписать eval:
Предлагаю переписать 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.
'(1 2 (quote 3 4))
quote потому и quote, что останавливает eval.
0
Точно, спасибо большое! Если вы не против, использую Ваш код в UPD статьи.
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
0
Зачем у вас операция eval применяется к аргументам по два раза: в виде
Если уж делать декоратор для всех «библиотечных» функций — то можно вообще избавиться от прямого рекурсивного вызова внутри eval:
С учетом же замечания StreetStrider код получается вот таким:
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)
+2
Peter Norvig однажды написал аналогичный интерпретатор, lis.py:
Статья с описанием здесь: norvig.com/lispy.html
Скрытый текст
################ 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
+1
… и перевод статьи на хабре: (Как написать (Lisp) интерпретатор (на Python))
+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]
+4
Sign up to leave a comment.
Мини-интерпретатор Lisp'a на Python