LithpJohn McCarthy 原始 Lisp 语言解释器Lithp 是 John McCarthy 原始 Lisp 语言的解释器。Lithp 的详细注释代码可在 Github 上找到。仅仅编写 Lisp 解释器还不够开发者还想和大家分享所学。阅读这段源代码能让我们一窥 John McCarthy、Steve Russell、Timothy P. Hart、Mike Levin 以及开发者自己的思路。以下是可供阅读的源文件atom.pyenv.pyerror.pyfun.pyinterface.pylisp.pylithp.py即本文档number.pyreader.pyseq.pycore.lispLithp 解释器需要 Python 2.6.1 及以上版本才能运行。请在 Lithp 的 Github 项目页面 添加注释、报告错误或分享相关轶事等。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 类的工作内容Lithper 类是解释器的驱动程序它主要完成以下工作class Lithp(Lisp):初始化全局环境解析命令行参数并做出相应处理初始化基础 Lisp 函数读取输入进行求值输出结果回到步骤 4 继续循环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()def init(self):定义核心函数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))定义实用函数self.environment.set(print, Function(self.println))特殊形式self.environment.set(lambda, Function(self.lambda_)) self.environment.set(label, Function(self.label))定义核心符号self.environment.set(t, TRUE)只有一个空列表名为 nilself.environment.set(nil, FALSE)定义元元素self.environment.set(__lithp__, self) self.environment.set(__global__, self.environment)def usage(self): self.print_banner() print print NAME.lower(), options [lithp files]\ndef print_banner(self): print The, NAME, programming shell, VERSION print by Fogus,, WWW print Type :help for more information printdef 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 interpreterdef push(self, envNone): 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 的 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 表达式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()闭包与动态作用域问题在开发者的学习过程中常听说闭包和动态作用域不能共存。通过思考能理解其中的原因。也就是说闭包会捕获变量的上下文绑定而动态作用域的查找是在动态栈上进行的。这意味着只要变量是唯一的就可以对其进行闭包操作但一旦有人定义了同名变量在该变量被弹出之前尝试查找闭包变量时就会解析为动态栈上最顶层的绑定。虽然从概念上很容易理解但开发者还是想看看实际情况会怎样结果并不理想。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:])将求值操作委托给表达式def eval(self, sexpr): try: return sexpr.eval(self.environment) except ValueError as err: print(err) return FALSE完整的命令定义为一个完整的 s 表达式。简单来说它可以是任何原子或括号平衡的列表。def get_complete_command(self, line, depth0): 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 linedef 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 lineLithp 也可以使用读取器机制处理文件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) John MaCarthy 所著的History of Lisp(McCarthy 1960) John McCarthy 所著的Recursive functions of symbolic expressions and their computation by machine, part I(Church 1941) Alonzo Church 所著的The Calculi of Lambda-Conversion(Baker 1993) Henry Baker 所著的Equal Rights for Functional Objects or, The More Things Change, The More They Are the Same(Kleene 1952) Stephen Kleene 所著的Introduction of Meta-Mathematics(McCarthy 1962) John McCarthy、Daniel Edwards、Timothy Hart 和 Michael Levin 所著的LISP 1.5 Programmers Manual(IBM 1955) IBM 704 操作手册(Hart 1963) Timothy P. Hart 所著的AIM-57: MACRO Definitions for LISP