探秘 Lithp：John McCarthy 原始 Lisp 语言解释器代码与运行机制全解析

Lithp：John McCarthy 原始 Lisp 语言解释器

Lithp 是 John McCarthy 原始 Lisp 语言的解释器。Lithp 的详细注释代码可在 Github 上找到。

仅仅编写 Lisp 解释器还不够，开发者还想和大家分享所学。阅读这段源代码，能让我们一窥 John McCarthy、Steve Russell、Timothy P. Hart、Mike Levin 以及开发者自己的思路。以下是可供阅读的源文件：

  • atom.py
  • env.py
  • error.py
  • fun.py
  • interface.py
  • lisp.py
  • lithp.py（即本文档）
  • number.py
  • reader.py
  • seq.py
  • core.lisp

Lithp 解释器需要 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):
  1. 初始化全局环境
  2. 解析命令行参数并做出相应处理
  3. 初始化基础 Lisp 函数
  4. 读取输入
  5. 进行求值
  6. 输出结果
  7. 回到步骤 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)

只有一个空列表，名为 `nil`

self.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]\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 的 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="", 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 也可以使用读取器机制处理文件

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 Programmer's Manual
  • (IBM 1955) IBM 704 操作手册
  • (Hart 1963) Timothy P. Hart 所著的AIM-57: MACRO Definitions for LISP