Lithp.py (~2008)

# lithp.py 源码：https://fogus.me/fun/lithp/ Lithp——John McCarthy 原始 Lisp 语言的解释器。Lithp 的详细注释代码可以在 Github（http://github.com/fogus/lithp）上找到。仅仅编写一个 Lisp 解释器还不够——我还想与你*分享*我的所学。阅读这份源码能让你一窥 John McCarthy、Steve Russell、Timothy P. Hart 和 Mike Levin 的思想，额外附赠我本人的思考。以下源文件可供阅读： - atom.py（https://fogus.me/fun/lithp/atom.html） - env.py（https://fogus.me/fun/lithp/env.html） - error.py（https://fogus.me/fun/lithp/error.html） - fun.py（https://fogus.me/fun/lithp/fun.html） - interface.py（https://fogus.me/fun/lithp/interface.html） - lisp.py（https://fogus.me/fun/lithp/lisp.html） - lithp.py（https://fogus.me/fun/lithp/index.html）*（本文件）* - number.py（https://fogus.me/fun/lithp/number.html） - reader.py（https://fogus.me/fun/lithp/reader.html） - seq.py（https://fogus.me/fun/lithp/seq.html） - core.lisp（https://fogus.me/fun/lithp/core.html） Lithp 解释器需要 Python 2.6.1+ 才能运行。请将评论、错误报告、趣闻轶事等添加到 Lithp 的 Github 项目页面（http://github.com/fogus/lithp）。 ```python import pdb import getopt, sys, io from env import Environment from fun import Function from atom import TRUE from atom import FALSE from lisp import Lisp from reader import Reader from error import Error from fun import Lambda from fun import Closure NAME = "Lithp" VERSION = "v1.1" WWW = "http://fogus.me/fun/lithp/" PROMPT = "lithp" DEPTH_MARK = "." ``` Lithper 类是解释器的驱动程序。它执行以下操作： 1. 初始化全局环境 2. 解析命令行参数并相应处理 3. 初始化基础 Lisp 函数 4. 读取输入 5. 求值 6. 打印 7. 返回步骤 4 进行循环 ```python def __init__(self): iostreams=(sys.stdin, sys.stdout, sys.stderr) (self.stdin, self.stdout, self.stderr) = iostreams self.debug = False self.verbose = True self.core = True self.closures = True self.rdr = Reader() self.environment = Environment() self.init() ``` ## 定义核心函数 ```python self.environment.set("eq", Function(self.eq)) self.environment.set("quote", Function(self.quote)) self.environment.set("car", Function(self.car)) self.environment.set("cdr", Function(self.cdr)) self.environment.set("cons", Function(self.cons)) self.environment.set("atom", Function(self.atom)) self.environment.set("cond", Function(self.cond)) ``` ## 定义工具函数 ```python self.environment.set("print", Function(self.println)) ``` ## 特殊形式 ```python self.environment.set("lambda", Function(self.lambda_)) self.environment.set("label", Function(self.label)) ``` ## 定义核心符号 ```python self.environment.set("t", TRUE) ``` 这里只有一个空列表，它被命名为`nil`。 ```python self.environment.set("nil", FALSE) ``` ## 定义元元素 ```python self.environment.set("__lithp__", self) self.environment.set("__global__", self.environment) ``` ```python def usage(self): self.print_banner() print print NAME.lower(), " [lithp files]\n" def print_banner(self): print "The", NAME, "programming shell", VERSION print " by Fogus,", WWW print " Type :help for more information" print def print_help(self): print "Help for Lithp v", VERSION print " Type :help for more information" print " Type :env to see the bindings in the current environment" print " Type :load followed by one or more filenames to load source files" print " Type :quit to exit the interpreter" def push(self, env=None): if env: self.environment = self.environment.push(env) else: self.environment = self.environment.push() def pop(self): self.environment = self.environment.pop() def repl(self): while True: # 借鉴自CLIPS（http://clipsrules.sourceforge.net/）的S-表达式解析方法 source = self.get_complete_command() # 检查任何REPL指令 if source in [":quit"]: break elif source in [":help"]: self.print_help() elif source.startswith(":load"): files = source.split(" ")[1:] self.process_files(files) elif source in [":env"]: print(self.environment) else: self.process(source) ``` 源码一次处理一个 S-表达式。 ```python def process(self, source): sexpr = self.rdr.get_sexpr(source) while sexpr: result = None try: result = self.eval(sexpr) except Error as err: print(err) if self.verbose: self.stdout.write(" %s\n" % result) sexpr = self.rdr.get_sexpr() ``` 在我的人生经历中，我一直听说闭包和动态作用域不能共存。作为一个思想实验，我能想象出为什么会出现这种情况。也就是说，虽然闭包捕获了变量的上下文绑定，但在动态作用域中，变量查找发生在动态栈上。这意味着你可以闭包一个变量，只要它是唯一的，但一旦其他人定义了同名的变量并尝试查找，那么闭包变量将解析为动态栈顶的绑定。这假设查找发生在同名变量被弹出之前。虽然这在概念上容易理解，但我还是想看看实践中会发生什么——结果并不美观。 ```python def lambda_(self, env, args): if self.environment != env.get("__global__") and self.closures: return Closure(env, args[0], args[1:]) else: return Lambda(args[0], args[1:]) ``` 将求值委托给具体形式。 ```python def eval(self, sexpr): try: return sexpr.eval(self.environment) except ValueError as err: print(err) return FALSE ``` 一个完整的命令定义为一个完整的 S-表达式。简单来说，就是任意原子或任何括号平衡的列表。 ```python def get_complete_command(self, line="", depth=0): if line != "": line = line + " " if self.environment.level != 0: prompt = PROMPT + " %i%s " % (self.environment.level, DEPTH_MARK * (depth+1)) else: if depth == 0: prompt = PROMPT + "> " else: prompt = PROMPT + "%s " % (DEPTH_MARK * (depth+1)) line = line + self.read_line(prompt) # 用于平衡括号 balance = 0 for ch in line: if ch == "(": # 目前不完美，但暂时够用 balance = balance + 1 elif ch == ")": # 右括号过多是个问题 balance = balance - 1 if balance > 0: # 平衡括号时返回零 return self.get_complete_command(line, depth+1) elif balance < 0: raise ValueError("Invalid paren pattern") else: return line def read_line(self, prompt): if prompt and self.verbose: self.stdout.write("%s" % prompt) self.stdout.flush() line = self.stdin.readline() if(len(line) == 0): return "EOF" if line[-1] == "\n": line = line[:-1] return line ``` Lithp 也使用读取器管道来处理文件。 ```python def process_files(self, files): self.verbose = False for filename in files: infile = open(filename, 'r') self.stdin = infile source = self.get_complete_command() while(source not in ["EOF"]): self.process(source) source = self.get_complete_command() infile.close() self.stdin = sys.stdin self.verbose = True if __name__ == '__main__': lithp = Lithp() try: opts, files = getopt.getopt(sys.argv[1:], "hd", ["help", "debug", "no-core", "no-closures"]) except getopt.GetoptError as err: # 打印帮助信息并退出： print(str(err)) # 会打印类似“option -a not recognized”的内容 lithp.usage() sys.exit(1) for opt,arg in opts: if opt in ("--help", "-h"): lithp.usage() sys.exit(0) elif opt in ("--debug", "-d"): lithp.verbose = True elif opt in ("--no-core"): lithp.core = False elif opt in ("--no-closures"): lithp.closures = False else: print("unknown option " + opt) # 如果适用，处理核心lisp函数 if lithp.core: lithp.process_files(["../core.lisp"]) if len(files) > 0: lithp.process_files(files) lithp.print_banner() lithp.repl() ``` ### 参考文献 - (McCarthy 1979) *History of Lisp* by John McCarthy - (McCarthy 1960) *Recursive functions of symbolic expressions and their computation by machine, part I* by John McCarthy - (Church 1941) *The Calculi of Lambda-Conversion* by Alonzo Church - (Baker 1993) *Equal Rights for Functional Objects or, The More Things Change, The More They Are the Same* by Henry Baker - (Kleene 1952) *Introduction of Meta-Mathematics* by Stephen Kleene - (McCarthy 1962) *LISP 1.5 Programmer's Manual* by John McCarthy, Daniel Edwards, Timothy Hart, and Michael Levin - (IBM 1955) *IBM 704 Manual of Operation* here (http://www.cs.virginia.edu/brochure/images/manuals/IBM_704/IBM_704.html) - (Hart 1963) *AIM-57: MACRO Definitions for LISP* by Timothy P. Hart