在 Python 中实现 Lisp

Question

首先：是的，我对 Norvig 的 lispy 进行了非常长时间的研究。第二：我复用了他的部分代码。

关于我的代码和我的问题。我正在用 Python 编写一个非常不惯用的 lisp 解释器，我很好奇如何编写嵌套函数定义（例如 (define square (lambda (x) (* xx)))然后 (define SoS (lambda (xy) (+ (square x) (square y))))) 目前不起作用。我有点卡住了。我能做些什么？

编辑：任何有关我的编码风格或我可以做出的改进的建议将不胜感激。谢谢你！

"""

FIX NESTED DEFINITIONS!

(def square (lambda (x) (* x x)))
(def SoS (lambda x y) (+ (square x) (square y)))

DOES NOT WORK!

"""


#!/usr/bin/python
import readline, sys, shlex
userFuncs   = {}
userVars    = {}
stdOps      = "% * / - + set!".split()


def lispify(nested_lists):
    return str(nested_lists).replace('[','(').replace(']',')').replace(', ',' ').replace("'",'')

def mul_arr(array):
    tot = 1
    for i in array: tot *= i
    return tot

def div_arr(array):
    tot = array[0]
    for i in array[1:]: tot /= i
    return tot

def sub_arr(array):
    print array
    if len(array) > 1: tot = array[0]
    else: tot = 0-array[0]
    for i in array[1:]: tot -= i
    return tot

def atom(tok):
    try: return int(tok)
    except:
        try: return float(tok)
        except: return str(tok)

def pre_in(read):
    tempOp = read[0]
    body = read[1:]
    expr = []
    for i in range(len(body)-1):
        if not isinstance(body[i], list) and body[i] != " ":
            expr.append(str(body[i]))
            expr.append(tempOp)
        else:
            expr.append(str(pre_in(body[i])))
            expr.append(tempOp)
    try:
        if not isinstance(body[-1], list): expr.append(str(body[-1]))
        else: expr.append(str(pre_in(body[-1])))
    except: pass
    if expr != None: return "("+' '.join(expr)+")"

def tok(s):
    try: return shlex.split(s.replace('(',' ( ').replace(')',' ) '))
    except: return s.replace('(',' ( ').replace(')',' ) ').split()

def read_from(toks):
    if len(toks) == 0: raise SyntaxError('unexpected EOF')
    tok = toks.pop(0)
    if tok == "'":
        l = []
        toks.pop(0)
        while toks[0] != ")": l.append(read_from(toks))
        toks.pop(0)
        return lispify(l)
    if tok == '(':
        l = []
        while toks[0] != ')': l.append(read_from(toks))
        toks.pop(0)
        return l
    elif tok == ')': raise SyntaxError('unexpected \')\'')
    else: return atom(tok)

def total_eval(read):
    if isinstance(read, int):
        return read
    elif isinstance(read, str):
        if read not in stdOps:
            if read in userVars:
                return atom(userVars[read])
            else:
                return str(atom(read))
    elif isinstance(read, list):
        if read[0] in userFuncs:
            print read[0]+" = "+userFuncs[read[0]]
            exec(read[0]+" = "+userFuncs[read[0]])
            return eval(read[0]+str(tuple(read[1:])))
        elif read[0] == "+":
            return sum([float(total_eval(i)) for i in read[1:]])
        elif read[0] == "*":
            return mul_arr([float(total_eval(i)) for i in read[1:]])
        elif read[0] == "/":
            return div_arr([float(total_eval(i)) for i in read[1:]])
        elif read[0] == "-":
            return sub_arr([float(total_eval(i)) for i in read[1:]])
        elif read[0] == "set!" or read[0] == "setf":
            userVars[read[1]] = total_eval(read[2])
            return "ok"
        elif read[0] == "lambda":
            tempvars    = ','.join(i.replace(',','') for i in read[1])
            expr        = read[2]
            return "lambda "+str(tempvars)+": "+pre_in(expr)
        elif read[0] == "def" or read[0] == "define" or read[0] == "defun":
            funcName = read[1]
            funcBody = read[2]
            userFuncs[funcName] = total_eval(funcBody)
            return "ok"
        elif read[0] == "cons":
            body = read[1:]
            arr = body[0]
            to_push = body[1]
            if not isinstance(arr, list):
                arr = [arr]
            for i in to_push:
                arr.append(i)
            return lispify(arr)
        elif read[0] == "append":
            body = read[1:]
            main = body[0]
            tail = body[1:]
            for i in tail:
                if i != []:
                    main.append(i)
            #print main
            return lispify(main)
        elif read[0] == "list":
            return lispify(str([total_eval(read[1:][i]) for i in range(len(read[1:]))]))
        elif read[0] == "\'" or read[0] == "quote":
            return lispify(read[1:][0])
        elif read[0] == "print":
            return total_eval(read[1:][0])
        elif not isinstance(read[0], list):
            if read[0] in userFuncs:
                args = read[1:]
                exec(read[0]+" = "+userFuncs[read[0]])
                return eval(read[0]+str(tuple([float(i) for i in args])))
        else:
            if read[0][0] == "lambda":
                tempvars    = ','.join(i.replace(',','') for i in read[0][1])
                expr        = read[0][2]
                exec("temp = lambda "+str(tempvars)+": "+str(pre_in(expr)))
                args = read[1:] if len(read[1:]) > 1 else read[1]
                if isinstance(args, list): return eval("temp"+str(tuple([total_eval(i) for i in args])))
                else: return eval("temp("+str(float(args))+")")
"""
while 1:
    try:
        a = raw_input("lisp>   ")
        try:
            print tok(a)
            print read_from(tok(a))
            print total_eval(read_from(tok(a))),"\n"
        except:
            errorMsg = str(sys.exc_info()[1]).split()
            if errorMsg[0] == "list":
                print "ParseError: mismatched parentheses\n"
            else:
                print ' '.join(errorMsg)
                print
    except (EOFError, KeyboardInterrupt):
        print "\nbye!"
        break
"""
while 1:
    a = raw_input("lisp>   ")
    #print tok(a)
    #print read_from(tok(a))
    print total_eval(read_from(tok(a)))
    print
#"""

Answer 1

看一下 pre_in 的输出：

>>> pre_in(read_from(tok("(+ (square x) (square y))")))
'((x) + (y))'

应该是 '(square(x) + square(y))'。

（顺便说一句，您的示例代码包含语法错误。SoS 应定义为 (lambda (xy) (+ (square x) (square y)))。 ）

Answer 2

在 read_from 中，您有以下行两次：

while toks[0] != ")": l.append(read_from(toks))

其中之一可能应该是：

while toks[0] != "'": l.append(read_from(toks))

很少的建议/提示：

• 阅读并遵循 “PEP 8——Python 代码风格指南”。例如：上面的行应该被分成两行。
• 如果您尝试编写自己的解析器，请不要尝试使用 shlex 来创建快捷方式，因为 shlex 是为不同的问题而设计的。
• 编写更短的方法（分解total_eval）
• 请参阅python的reduce函数http ://docs.python.org/library/functions.html#reduce 和 operator 包 http://docs.python.org/library/operator.html
• 最重要的提示 - 成为专业人士的捷径：使用 编写代码时进行单元测试。另请参阅：针对 Python Web 开发的 TDD 资源