python - Lisp 解释器引用，在 python 中

Question

我想用 python 编写一个 lisp 解释器。它适用于非递归表达式。但是，我发现在递归中引用很困惑。

以下程序的描述:

1. 以字符串形式编写的lisp代码在parse()函数中解析，将空格和圆括号替换为逗号和方括号，传递给python的eval() 函数。

2. 符号和句法词典包含原始程序。

3. 评估以递归方式进行，其中语法模式能够更改环境字典。 (label => 扩展当前字典，lambda => 创建一个新字典)。 quote 直接返回它后面的内容。至于过程，它通过在评估所有语句后调用它们来工作。

就是这样。

# -*- coding:utf-8 -*-
import re

def parse(s):
    l = re.sub(r'\s+', ', ', (' '+s.lower()+' ').replace('(', '[').replace(')', ']'))[2:-2]
    return eval(re.sub(r'(?P<symbol>[\w#%\\/^*+_\|~<>?!:-]+)', lambda m : '"%s"' % m.group('symbol'), l))

def cons(a, d):
    if atom(d):
        return (a, d)
    return (lambda *args : list(args))(a, *d)

def car(s):
    return s[0]

def cdr(s):
    if len(s) == 1:
        return []
    return s[1:]

def atom(s):
    return not isinstance(s, list)

def eq(s, t):
    return s == t

def cond(l, d):
    for [p, e] in cdr(l):
        if eval_(p, d):
            return eval_(e, d)

class lambda_object:
    count = 0
    def __init__(self, l, d):
        self.dic = d
        self.li = l[1]
        self.ex = l[2]
        lambda_object.count += 1
        self.serial = lambda_object.count

    def __call__(self, *args):
        for i in range(len(self.li)):
            self.dic[self.li[i]] = args[i]
        return eval_(self.ex, self.dic)

    def __str__(self):
        return 'COMPOND-PROCEDURE-#%d' % self.serial

    __repr__ = __str__

def label(l, d):
    d[l[1]] = eval_(l[2])

def quote(l, d):
    return l[1]

symbol_s = {'cons':cons, 'car':car, 'cdr':cdr, 'atom?':atom, 'eq?':eq, '#t':True, '#f':False}
syntax_s = {'cond':cond, 'lambda':lambda_object, 'quote':quote, 'label':label}


def eval_(l, s=symbol_s):
    print 'code =>', l
    if atom(l):
        return symbol_s[l]
    #if not atom(l[0]):
    #    l[0] = eval_(l[0])
    if l[0] in syntax_s:
        return syntax_s[l[0]](l, s)
    else:

---

编辑:

根据答案，以下几行是不正确的:

        for i in range(len(l))[1:]:
            l[i] = eval_(l[i])
        print 'sval =>', l
        if isinstance(l[0], str):
            l[0] = s[l[0]]
        return l[0](*l[1:])

它们应该是:

        operator = eval_(l[0], s)
        operands = map(lambda e: eval_(e,s), l[1:])
        print 'sval =>', operator, '<<', operands
        return operator(*operands)

---

这就是程序。

运行时:

code = '''
(label ff
  (lambda (s)
    (cond
      ((atom? s) s)
      (#t (ff (car s))))))
'''
print eval_(parse(code))
print symbol_s

print eval_(parse("(ff (quote (((a b) c))))"))

它产生了一些东西:

code => ['label', 'ff', ['lambda', ['s'], ['cond', [['atom?', 's'], 's'], ['#t', ['ff', ['car', 's']]]]]]
code => ['lambda', ['s'], ['cond', [['atom?', 's'], 's'], ['#t', ['ff', ['car', 's']]]]]
None
{'cons': <function cons at 0x10efcaf98>, 'ff': COMPOND-PROCEDURE-#1, 'eq?': <function eq at 0x10efcaf28>, 'car': <function car at 0x10efca978>, '#f': False, 'atom?': <function atom at 0x10efcad68>, 'cdr': <function cdr at 0x10efcab38>, '#t': True}
code => ['ff', ['quote', [[['a', 'b'], 'c']]]]
code => ['quote', [[['a', 'b'], 'c']]]
sval => ['ff', [[['a', 'b'], 'c']]]
code => ['cond', [['atom?', 's'], 's'], ['#t', ['ff', ['car', 's']]]]
code => ['atom?', 's']
code => s
sval => ['atom?', [[['a', 'b'], 'c']]]
code => #t
code => ['ff', ['car', 's']]
code => ['car', 's']
code => s
sval => ['car', [[['a', 'b'], 'c']]] 

;; from this line, the quotation disappeared

sval => ['ff', [['a', 'b'], 'c']]
code => ['cond', [[<function atom at 0x10efcad68>, [[['a', 'b'], 'c']]], 's'], ['#t', [COMPOND-PROCEDURE-#1, [['a', 'b'], 'c']]]]
code => [<function atom at 0x10efcad68>, [[['a', 'b'], 'c']]]
code => [[['a', 'b'], 'c']]
code => [['a', 'b'], 'c']
code => ['a', 'b']
code => b
Traceback (most recent call last):
  File "slisp.py", line 113, in <module>
    print eval_(parse("(ff (quote (((a b) c))))"))
...
  File "slisp.py", line 66, in eval_
    return symbol_s[l]
KeyError: 'b'

我知道有问题，但我不知道如何解决。在评估 (ff (quote (((a b) c)))) 时，它在下一个递归中更改为 (ff ((a b) c)) 没有引号。

这是怎么回事？

Answer 1

因为 ff 是一个程序，它计算它的参数。在第一种情况下，它有参数 (quote (((a b) c))) 在它适用它:

code => ['ff', ['quote', [[['a', 'b'], 'c']]]]
code => ['quote', [[['a', 'b'], 'c']]]
sval => ['ff', [[['a', 'b'], 'c']]]

第二次它有参数 (car s) 其中 s 是一个绑定(bind)变量。

code => ['ff', ['car', 's']] ;; unevaluated expression
code => ['car', 's']
code => s
sval => ['car', [[['a', 'b'], 'c']]] ;; what apply gets for car

;; from this line, the quotation disappeared
sval => ['ff', [['a', 'b'], 'c']] ;; what apply gets for ff

据我所知，我在这里看不到任何错误。它完全按照它应该做的去做。

可能其他地方有错误。当您查看从一个递归到另一个递归的 cond 输出时:

code => ['cond', [['atom?', 's'], 's'], ['#t', ['ff', ['car', 's']]]]
code => ['cond', [[<function atom at 0x10efcad68>, [[['a', 'b'], 'c']]], 's'], ['#t', [COMPOND-PROCEDURE-#1, [['a', 'b'], 'c']]]]

除了环境之外，这些应该是相同的，因为它的代码相同。如果你看看你在 eval_ 中做了什么，我看到你做了:

`l[i] = eval_(l[i])`

这很糟糕，因为 l 包含你的 AST。第二次您重新访问它时，评估将不再是代码的符号，而是您上次获得的值。您需要将运算符和操作数评估为其他内容，然后应用它们。

我不是 python 程序员，但我猜你正在寻找这样的东西:

operator = eval_(l[0], s)
operands = map(lambda e: eval_(e,s), l[1:])
return operator(*operands);

虽然你在几个地方都这样做了，但是你在任何地方使用代码 = 都可能会发生变化。