【翻訳属性】另一个Scheme入门_01_安装解释器【commonlisp吧】_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：280贴子：
【翻訳属性】另一个Scheme入门_01_安装解释器收藏
1. 也荐Scheme使用Scheme可以做到以下两点：(1)写出美观的代码(2)享受编程的乐趣以上便是仅有的学习Scheme的理由。若试图使用Scheme来制作实用软件，则可能招致失望。尽管如此，优秀的Hacker中爱好Scheme的人颇多，学习Scheme我想并没有坏处。事实上，最优秀的计算机科学教科书之一《Structure and Interpretation of Computer Programs (SICP)》的示例程序也是使用Scheme编写的。此外，GNU采用了名为guile的Scheme作为扩展语言。guile与MS-Word和Excel中的宏是类似的，使用简单的脚本程序，即可对应用程序进行控制。虽然笔者对Common Lisp更为熟悉，但对即将开始学习Lisp的人，笔者更加推荐Scheme。理由有两点：（1）标准精简（2）语法完整常有这样的说法，学习Scheme能使思维的条理性更强。即使在工作上与Scheme无缘，Scheme所带来的良好条理性，对于使用其他语言想必也会有帮助。Scheme是一门受欢迎的语言，因此提供入门讲解的网站也很多，只可惜这些网站的内容对纯初学者来说稍显困难。笔者从现在开始要写的一系列文章，将会注重解说的浅显和细致。尽量避免以阅读过某些资料为前提的状况发生。
江苏盘锦天燃气模温机，一台省得让你怀疑人生的燃气锅炉
2. 面向读者本文主要面向使用过计算机，但没有编程经验的人。具备打开和保存文本文档程度的知识即可。具体来说：（1）大学选择了信息类学科，突然接触Scheme课程感觉难以应付的学生。（2）玩Basic感觉不过瘾的人。（不过，在学习Scheme的过程中Basic的知识反而会成为障碍。）（3）平常使用C系语言（C/C++、Java），并希望广泛了解其他语言的人。（4）由于兴趣开始学习编程，决定首先精通Scheme的人。（偶尔也会有这种人。）面向以上人群。由于Scheme语法简单，可以将说明简洁化。但这样会使难易跨度增大，因此本文将以循序渐进为目标。当然，一开始可能会对这种满是括弧的代码产生眩晕感。不过，通过选择适当的代码编辑器，实现括弧配对、缩进的自动化，可以减轻括弧对读写代码所带来的负担。人借助缩进阅读代码，缩进不正常是由括弧不配对所造成的，因此可以通过代码编辑器的括弧配对功能找出问题根源。
3. Scheme的标准与实现关于安装，这里以Windows系为平台。由于笔者没有Mac，关于Mac下的情况无从得知。还有，使用Unix系的人，要么自己对流程已经相当熟悉，或者有熟悉的朋友（系统管理员）可以向其请教（或者请其帮忙完成）。安装方法可能每个平台各不相同，但Scheme本身的使用方法是一样的。Scheme也有不少版本的标准，最近常用的有R5RS和R6RS。以学习为目的的话R5RS就足够了，不过若要编写实用程序R6RS更为方便吧。此外，在R6RS中，R5RS下不够明确的规定也得到了明确。笔者认为今后R6RS将逐渐普及开来，因此本文将遵循R6RS。RnRS是Revised n Report on the Algorithmic Language Scheme的缩写，可参考以下网址。R5RS http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs.htmlR6RS http://www.r6rs.org/另外，存在一个名为Scheme Requests For Implementation (SRFI) 的标准库。由于R5RS只规定了语言的核心部分，各种实现都有着不同的扩展功能，实现之间的兼容性底下。为解决这种情况，以扩展功能标准化为目的的SRFI被制定了出来。能在Windows下运行的Scheme解释器有ChezScheme、MzScheme、SCM等众多版本，本文将使用安装简单、运行轻快的MzScheme。MzScheme是近来被广泛应用的Scheme解释器，它遵循最新标准R6RS，同时也支持SRFI。
4. 安装MzScheme4.1 安装MzScheme本体（※译者插播：若选择使用DrScheme的话本部分的安装可以跳过，直接进行4.2.1。）MzScheme可以从以下网址下载。执行下载后的文件即可安装。http://download.plt-scheme.org/mzscheme/此外，若使用下述的DrScheme的话MzScheme将会被一同安装，因此没有必要单独安装MzScheme。事实上，MzScheme是PLT-Scheme环境的后台引擎，而DrScheme是PTL-Scheme的前端界面。如果安装PLT-Scheme的话两者都会被安装。（※译者插播：PTL-Scheme目前已更名为Racket，进入上述链接时会弹出提示。值得注意的是，“Racket is a programming language.”。）4.2 安装前端界面MzScheme通过命令行也可以使用，当然由于有DrScheme和Emacs等方便的前端，使用它们能够提高工作效率。4.2.1 DrScheme（PLT-Scheme）DrScheme可以从以下网址下载。执行下载后的文件即可将DrScheme和MzScheme一同安装。http://download.plt-scheme.org/drscheme/安装工作到此结束。通过“开始 → 所有程序 → PLT Scheme → DrScheme”启动。启动可能会略耗时间，稍作等待就会显示出一个易用的前端界面（如图1）。图1： DrScheme截图DrScheme的用法可以参照一下网址：DrScheme: PLT Programming Environment - http://download.plt-scheme.org/doc/html/drscheme/DrScheme安装简单，无需额外设置即可开始使用，值得推荐。
4.2.2 Emacs另一个值得推荐的前端就是Emacs。Emacs是功能强大的编辑器，在程序开发上被广泛使用。如果使用Emacs进行Scheme程序开发，将来即使更换Scheme解释器，同样的Emacs及设定依然能够使用。对于希望尝试其他解释器的人来说Emacs更加方便。（顺带一提，笔者即使用Emacs编写Scheme程序。）Windows版的Emacs可以从以下网址下载：http://ftp.gnu.org/gnu/emacs/windows/下&#3/9/17 时的最新版 emacs-22.3-bin-i386.zip ，解压到任意地方安装即告完成。对解压之后生成的 bin/runemacs.exe 制作快捷方式会比较便利。最后只要对emacs和MzScheme的初始化设定进行编辑，安装就全部结束了。【编辑.emacs】C:\Documents and Settings\{USER}\Application Data\.emacs(Vista 的话在 C:\Users\{USER}\Application Data\.emacs) [向.emacs追加以下设定]
-----------------------------------------(show-paren-mode t) 显示配对括弧(setq scheme-program-name "C:\Program Files\PLT\MzScheme.exe") ; run-scheme 时使用的解释器; 如果以上设定不起效果的话，尝试将 C:\Program Files\PLT\ 追加到PATH里，; 并尝试以下设定↓ （※译者即使用这个设定方才成功）; (setq scheme-program-name "MzScheme.exe")(autoload 'run-scheme "cmuscheme" "Run an inferior Scheme process." t)(define-key global-map "\C-cs" 'run-scheme) ; 使用 C-c s 在 emacs 上执行 MzScheme; 若将 Emacs 作为 scheme 专用的话，以下设定会带来方便(setq inhibit-startup-message t) 不显示启动画面(run-scheme scheme-program-name) 启动时直接执行 scheme 解释器-----------------------------------------【编辑mzschemerc.ss】编辑或者新建C:\Documents and Settings\{USER}\mzschemerc.ss，向其内追加设定。如果不进行此步骤，出错时错误信息就不会被显示到Emacs上。可以通过运行MzScheme并执行以下操作，确认MzScheme的初始化设定的文件路径。&
(find-system-path 'init-file
) 这样就能知道初始化设定的文件路径#&path:C:\Documents and Settings\{USER}\mzschemerc.ss&[向mzschemerc.ss追加以下设定]-----------------------------------------(current-error-port
(current-output-port))-----------------------------------------这样准备工作就全部结束了。Scheme的代码编写及运行都能够在Emacs内完成，非常方便。如˜示，上窗口为代码编辑区域，下窗口为代码执行区域。使用这个环境可以对单个函数进行测试，编写程序十分轻松。IJ Emacs截图
精华帖顶起
思美人同名游戏,画质精良,招式华丽,场面恢宏首服刚开,福利多,元宝好拿!
PTL PLT ...
登录百度帐号推荐应用有人建议我写一个小型语言解释器，如果是 LISP 那就更完美了。作为一名程序员，这是你职业生涯必须经历的事情之一，也是一次让你大开眼界的经历：你会对日常工作中的工具产生新的见解，那些令人望而生畏的概念也会被慢慢掀开神秘的面纱。
本文中，我们基于 1978 年 John McCarthy 发表的
文章，实现一个小型 LISP 解释器，麻雀虽小但五脏俱全，这里主要利用 Swift 框架来对一些包含 LISP 符号表达式的字符串解释。
我们最终会使用解释器来构建一个简单的 REPL (Read-Eval-Print-Loop) 程序，它将交互地执行语句并打印出求值结果。我们还实现了探究解释器的一个 Playground 。
本文将手把手教你直至完成属于你的 LISP 解释器，这将是一次难忘的周末计划。选择跟着一起实现或只是阅读介绍取决于你的心情，当然你也可以参考本文的实现，构建你独有的解释器。
下图显示了我们将要建造的总体设计：
第一个功能块( 读取阶段 Read Phase)的作用是读取一些包含代码的文本，并在后续两个阶段过程中通过输入程序的内部表示将文本生成一个语法树。
第一阶段，词法分析程序（Lexer）将输入文本分离成词法单元 Token（从文本的角度来说，就是程序的构建块），接着语法剖析程式（Parser）接受这些词法单元生成一个，也就是源代码的分层表示。
一旦有了抽象语法树，我们就能够对表达式求值，然后打印输出到用户的屏幕上。
文本介绍的解释器封装库和 playground 测试代码已经上传到 。
LISP 基础知识让我们简要回顾下将要实现的 LISP 解释器基础知识，McCarthy 的基本涵盖了该语言所有的定义。
首先，如果你不熟悉 LISP，首字母缩略词源自 LISt 处理程序，这是描述 LISP 家族语言一个很好的方式。它们的基本数据结构是列表，之后你的程序也将基于列表执行操作。
你应该已经猜到我为何使用”家族”这一术语，McCarthy 定义的 LISP 当前存在很多变种或方言，从传统语言如 Racket 到 Clojure 之类的语言，它们建立在不同技术之上（Java虚拟机以及 Java 的 runtime)，并且能够通过其不同的范例使用 LISP 提供的功能来扩展底层平台。
这里我们要实现的是一个最小的 LISP 解释器，它包含了一些有用的基本元素。
LISP 解释器其实就是对那些以递归数据结构的一个评估程序，呈现形式有原子和列表(Atom & List)。原子是一些简单的字母数字字符，具有不同的含义，而列表（也称为复合形式）是其他符号表达式的序列，以括号形式表示一个值序列。
LISP 中还有另外一种形式存在，这种特殊的形式有别于其他的符号表达式，区别在于对子表达式的求值规则不同。
为了表示程序将要处理的数据，我们将再次使用相同的符号表达式数据类型，最后使用相同的数据结构来表示源代码和所使用的数据。
但是什么是抽象语法树呢？语法上有效的程序包括一系列的符号表达式，即一系列嵌套列表，所以当源代码转换为抽象语法树，我们将再次使用一个能够存储列表的数据结构来建模我们的程序。
像 LISP 这样的语言，文本表示（通常指源代码）与其抽象语法树具有相同的结构，称之为(homoiconic)，它是元编程的基本特性之一，程序具有以相同语言修改本身或其他程序的能力，较之非同像性语言(大多数你知道，包括 Swift )要简单的多。你可以在运行时将代码当作数据来修改或者变换，而不使用复杂的机制。
如果你整篇阅读了 McCarthy 的文章，会发现可以让 LISP 自解释构建一个 LISP 解释器，称之为“Meta Circular Evaluator”，就只是几行代码而已。我们即将建立的 Swift 解释器将完成同样的事情，递归地评估这些符号表达式，并产生另一个符号表达式作为结果。
让我们看一个使用符号表达式表达的 LISP 例程：
(COUNT (QUOTE (A B C) ) 42)
上述例程中，COUNT，QUOTE，A，B，C，42 都是原子（暂时忽略它们的意义），每个括号中的序列是一个列表。注意列表如何包含任何类型的符号表达式，甚至包括子列表。
我们的解释器如何对这些表达式求值呢？
评估这个表达式将使用称之为
的表达式，其中每个列表将被视为一个操作，随后是其需要应用的操作数，例如对两个数求和可以用 (+ 1 2) 表示。
上面例程中，操作者/函数 COUNT 将被应用到操作数/参数 (QUOTE (A B C)) 和 42。
你一定注意到在我们的语言定义中，原子是没有类型的，我们只有单一类型的原子，而常见类型如整数、布尔值和字符串是不可用的。LISP 没有 Swift 语言中复杂的类型系统。
手册定义了一系列执行基本操作的原子，并描述了一旦包含它们的列表所产生的值。在下表中，e 将表示通用的符号表达式，而 L 表示列表。
(quote e1)
返回子表达式，例如(quote A) = A
返回第一个非空自列表，例如 (car (quote (A B C))) = A
返回除去第一个元素后，所有剩余元素构成的子列表，例如(cdr (quote (A B C))) = (B C)
(cons e l)
组合第一个元素和子列表中的元素成一个新列表，例如 (cons (quote A) (quote (B C))) = (A B C)
(equal e1 e2)
如果两个符号表达式递归相等，则返回一个名为 true 的原子，如果它们不为空，则返回空的 list()（同时用作 nil 和 false 值）。例如： (equal (car (quote (A B))) = (quote A))
如果符号表达式是原子或空列表（如果它是一个列表），则返回 true。(atom A)= true
(cond (p1 e1) (p2 e2) … (pn en))
p 条件表达式不等于空列表则返回其第一个 e 表达式。 cond 可以构造一些语法稍微复杂的条件表达式。 例如
(cond ((atom (quote A)) (quote B)) ((quote true) (quote C) = B
(list e1 e2 … en)
返回所有给定表达式的列表，与将递归应用于表达式序列相同。
上述包含了评估这些表达式的规则集。
如果仔细观察，你会注意到 cond与其他的有些不同，因为它根据它包含的子列表有条件地评估它的主体。 这是我们第一个特殊形式的例子，我们将在实现评估器时特别注意这个细节。
现在让我们看看这些操作符的另一类，即能够定义函数的操作符:
( (lambda (v1 … vn) e) p1 … pn)
定义具有主体e的lambda表达式，描述使用一系列环境变量的匿名函数v。将使用提供的参数作为变量的值来评估此函数。 例如
(cond ((atom (quote A)) (quote B)) ((quote true) (quote C) = B
(defun (v1 … vn) e)
定义 lambda 表达式并将其注册在当前上下文中，以便在需要时使用。 我们可以像这样 (defun cadr (X) (car (cdr x)))定义一个函数，然后在另一个表达式中调用它：(cadr (quote (A B C D))).
McCarthy 的论文描述了一个额外的操作，可以用来定义局部标记 lambda 表达式，但我们不会实现它，当我们需要类似的东西，会使用 defun 替代。
构建解释器现在我们简单过完一遍论文的内容了，是时候开始讨论解释器的实现了。
在本节中，我们会对组成解释器的每个功能模块进行详细的分析，完整代码请前往
仓库地址下载。
第一个需要思考的问题是：符号表达式是如何在内部解释中呈现的，又是如何定义结构化的抽象语法树。这是一个重要的方面，因为良好的结构简化了计算过程。
为符号表达式创建模型最显而易见的方式是使用递归枚举为符号表达式创建模型：
public enum SExpr{
case Atom(String)
case List([SExpr])}
一般情况下声明递归的枚举需要加上 indirect 关键字，但是在本例中， List 的关联值(数组类型)扮演着一个容器角色，因此无须添加该关键字。这个枚举定义已经能满足我们对符号表达式定义的要求。
现在让我们为这个枚举添加一些其他的东西，我们需要理解两个表达式怎么算相等，以及一个打印方法。为了达到这两个目的，我们需要实现 Equatable 和 CustomStringConvertible两个协议。
extension SExpr : Equatable {
public static func ==(lhs: SExpr, rhs: SExpr) -& Bool{
switch(lhs,rhs){
case let (.Atom(l),.Atom(r)):
return l==r
case let (.List(l),.List(r)):
guard l.count == r.count else {return false}
for (idx,el) in l.enumerated() {
if el != r[idx] {
return false
return true
return false
}}extension SExpr : CustomStringConvertible{
public var description: String {
switch self{
case let .Atom(value):
return "\(value) "
case let .List(subxexprs):
var res = "("
for expr in subxexprs{
res += "\(expr) "
res += ")"
return res
}}
这两个函数递归遍历符号表达式结构，触发对自己的调用（使用等式运算符或将 SExpr 转换为字符串）来发挥他们的作用。
现在请回忆下之前定义的数据结构，然后思考 RERL 图中的每个组件应该如何实现。
词法分析器和语法分析器在 Read 阶段，将源代码翻译为抽象语法树过程可分为两个阶段，每个过程由专门的组件负责：词法分析器 Lexer 和语法分析器 Parser。
词法分析器或分词器的主要职责是对包含源代码的文本输入块进行。
词法分析器能够考虑上下文，将一系列字符分解成具有意义的 lexeme 或 token 。Token 可以是语言关键字，如if，运算符 = 或各种标识符（例如变量名）和字面量。
由于我们的语言的，有效标记的定义是非常简单的，词法分析器/分词器也是如此。 Lexer 将只识别由空格或括号分隔的字符串标记。
让我们向 SExpr 添加一个 read() 方法来将字符串转换为我们的枚举表达式，并开始讨论分词阶段的处理方式。
extension SExpr {
读取 LISP 字符串表达式并将其转换为具有层级结构的 S-Expression
public static func read(_ sexpr:String) -& SExpr{
enum Token{
case pOpen,pClose,textBlock(String)
将字符串分解为一系列词法单元
- Parameter sexpr: 字符串类型的表达式
- Returns: 词法单元数组
func tokenize(_ sexpr:String) -& [Token] {
var res = [Token]()
var tmpText = ""
for c in sexpr.characters {
switch c {
if tmpText != "" {
res.append(.textBlock(tmpText))
tmpText = ""
res.append(.pOpen)
if tmpText != "" {
res.append(.textBlock(tmpText))
tmpText = ""
res.append(.pClose)
if tmpText != "" {
res.append(.textBlock(tmpText))
tmpText = ""
tmpText.append(c)
return res
let tokens = tokenize(sexpr)
let res = parse(tokens)
return res.subexpr ?? .List([])
}}
tokenize 方法将遍历输入字符串的所有字符，将不透明（从语法的角度）字符串转换为 Token 枚举中定义的一系列值。 可能的值是：pOpen（用于开括号），pClose（用于右括号）和 textBlock（用于每个其他字符串，表示一个原子）。 一切都很直接，因为没有特殊的规则能够造成内容读取无效。
下一阶段依靠执行。
语法分析器的目的是将一系列 token 转换为抽象语法树形式表示我们的源代码，有利于检查语法错误，并且易于评估（如果我们正在构建一个编译器而不是解释器，则可以加入优化和编译模块）。
我们将实现一个非常简单的，它将提取 token 数组按照自然语序构建抽象语法树。如果你计划构建一个语法更复杂的分析器，可能需要参考一些更复杂的，如 或 。
但是对于具有复杂语法的语言，语法分析器通常使用解析器生成器（例如 ANTLR，最近引入了对 Swift 的支持）生成，因此你必须在 DSL 中描述语法，而不是手动编写解析器。
语法分析器肯定会比词法分析器更复杂，但是，由于这种语言很简单，它将是一个非常小而简单的分析器。
extension SExpr {
Read a LISP string and convert it to a hierarchical S-Expression
public static func read(_ sexpr:String) -& SExpr{
func appendTo(list: SExpr?, node:SExpr) -& SExpr {
var list = list
if list != nil, case var .List(elements) = list! {
elements.append(node)
list = .List(elements)
}else{
list = node
return list!
Parses a series of tokens to obtain a hierachical S-Expression
- Parameter tokens: Tokens to parse
- Parameter node: Parent S-Expression if available
- Returns: Tuple with remaning tokens and resulting S-Expression
func parse(_ tokens: [Token], node: SExpr? = nil) -& (remaining:[Token], subexpr:SExpr?) {
var tokens = tokens
var node = node
repeat {
let t = tokens[i]
switch t {
case .pOpen:
let (tr,n) = parse( Array(tokens[(i+1)..&tokens.count]), node: .List([]))
assert(n != nil)
(tokens, i) = (tr, 0)
node = appendTo(list: node, node: n!)
if tokens.count != 0 {
}else{
case .pClose:
return (Array(tokens[(i+1)..&tokens.count]), node)
case let .textBlock(value):
node = appendTo(list: node, node: .Atom(value))
}while(tokens.count & 0)
return ([],node)
let tokens = tokenize(sexpr)
let res = parse(tokens)
return res.subexpr ?? .List([])
}}
词法分析器使用 .pOpen 和 .pClose 将列表分割成 token 元素,parse(tokens：node :) 方法进行遍历并将每个其他 token 转换为原子。
注意，递归地执行解析，每个嵌套调用接收 token 数组等待解析，并且父列表将包含在下一递归步骤期间解析的值（从根表达式的 nil 开始）。 当执行到右括号时，列表被认为是完整的，并且将解析的剩余 token 一起返回给调用者。
在这些函数之后，你可以看到 read() 方法的实际主体，它执行这一系列中的每个步骤并返回顶层形式或在错误情况下返回一个空列表（我们在上一节中看到的两者都返回 false）。
let tokens = tokenize(sexpr)
let res = parse(tokens)
return res.subexpr ?? .List([])
}}
现在我们有一个可用的 Read 模块，让我们添加一些东西到 SExpr 枚举中，这将允许我们直接从字符串字面量获得一个表达式，而不通过实现 ExpressibleByStringLiteral 协议手动调用 read（）方法：
extension SExpr : ExpressibleByStringLiteral,
ExpressibleByUnicodeScalarLiteral,
ExpressibleByExtendedGraphemeClusterLiteral {
public init(stringLiteral value: String){
self = SExpr.read(value)
public init(extendedGraphemeClusterLiteral value: String){
self.init(stringLiteral: value)
public init(unicodeScalarLiteral value: String){
self.init(stringLiteral: value)
这样我们就可以直接从字符串中读取程序：
let expr: SExpr = "(cond ((atom (quote A)) (quote B)) ((quote true) (quote C)))"print(expr)print(expr.eval()!)
评估和默认全局环境评估阶段将比我们目前所看到的更复杂，eval() 函数将递归地评估抽象语法树，并返回符号表达式求值结果。
首先，让我们总结下所有这门语言所定义的基本操作符，它们被定义在一个名为 defaultEnvironment 的私有字典中，它将关联到每个操作符原子，由 (SExpr, [SExpr]?, [SExpr]?)-&SExpr 类型的函数来实现它。
这些函数将使用包含原始列表（函数名和参数）的 SExpr 参数，计算并返回一个 SExpr 作为结果。 这两个可选数组作为第二和第三个参数将包含一个变量列表及其值，并将用于通过 defun 和 lamdba 定义用户定义的函数，在所有其他情况下，它们将只是 nil。 当我们看到这些操作符时我们再回头看。
为了跟踪基本内置操作符，Builtin 枚举已经用一个函数声明，该函数标识哪些操作符不需要子表达式求值。像 quote（存在唯一的目的是禁用子表达式求值）这种操作符属于特殊形式，其他还有 cond 或 lambda 定义运算符，将在内部处理子表达式的求值。
fileprivate enum Builtins:String{
case quote,car,cdr,cons,equal,atom,cond,lambda,defun,list,
println,eval
True if the given parameter stop evaluation of sub-expressions.
Sub expressions will be evaluated lazily by the operator.
- Parameter atom: Stringified atom
- Returns: True if the atom is the quote operator
public static func mustSkip(_ atom: String) -& Bool {
(atom == Builtins.quote.rawValue) ||
(atom == Builtins.cond.rawValue) ||
(atom == Builtins.defun.rawValue) ||
(atom == Builtins.lambda.rawValue)
}}
所有 defaultEnvironment 函数都以简单的检查开始，以验证是否已提供最小数量的参数，然后继续构建返回结果。
让我们来看看其中的一些，完整项目的工程你可以看。
private var defaultEnvironment: [String: (SExpr, [SExpr]?, [SExpr]?)-&SExpr] = {
var env = [String: (SExpr, [SExpr]?, [SExpr]?)-&SExpr]()
env[Builtins.quote.rawValue] = { params,locals,values in
guard case let .List(parameters) = params, parameters.count == 2 else {return .List([])}
return parameters[1]
env[Builtins.cdr.rawValue] = { params,locals,values in
guard case let .List(parameters) = params, parameters.count == 2 else {return .List([])}
guard case let .List(elements) = parameters[1], elements.count & 1 else {return .List([])}
return .List(Array(elements.dropFirst(1)))
env[Builtins.equal.rawValue] = {params,locals,values in
guard case let .List(elements) = params, elements.count == 3 else {return .List([])}
var me = env[Builtins.equal.rawValue]!
switch (elements[1].eval(with: locals,for: values)!,elements[2].eval(with: locals,for: values)!) {
case (.Atom(let elLeft),.Atom(let elRight)):
return elLeft == elRight ? .Atom("true") : .List([])
case (.List(let elLeft),.List(let elRight)):
guard elLeft.count == elRight.count else {return .List([])}
for (idx,el) in elLeft.enumerated() {
let testeq:[SExpr] = [.Atom("Equal"),el,elRight[idx]]
if me(.List(testeq),locals,values) != SExpr.Atom("true") {
return .List([])
return .Atom("true")
return .List([])
env[Builtins.atom.rawValue] = { params,locals,values in
guard case let .List(parameters) = params, parameters.count == 2 else {return .List([])}
switch parameters[1].eval(with: locals,for: values)! {
case .Atom:
return .Atom("true")
return .List([])
return env}()
虽然像 quote 或 cdr 这样的函数只是操作参数列表来构建输出列表，但是其他的函数像 equals 实现了一个更复杂的逻辑（在这种情况下，它执行递归等式检查）。 为了保持源代码可读的教学目的，错误检查被保持到最小，额外的参数被忽略，当出现错误时，返回空列表。
对于像条件 cond 这样的特殊形式，需要对评估进行不同的处理。
条件运算符对于实现递归是至关重要的，因为只有这种语句，我们才能决定是否停止递归或继续进行另一次迭代。
env[Builtins.cond.rawValue] = { params,locals,values in
guard case let .List(parameters) = params, parameters.count & 1 else {return .List([])}
for el in parameters.dropFirst(1) {
guard case let .List(c) = el, c.count == 2 else {return .List([])}
if c[0].eval(with: locals,for: values) != .List([]) {
let res = c[1].eval(with: locals,for: values)
return res!
return .List([])}
cond 的实现方式：一旦列表第一个包含 cond 原子的元素被删除了，遍历列表直至找到一个子列表，其中第一个成员是一个值不同于空列表的表单（这意味着 false，前面我们已经看到了），一旦找到它，评估子列表的第二个成员并返回它。 使用这种评估，我们只评估我们实际需要什么，当评估递归函数时，我们不遵循这些函数的主体包含的无限序列的嵌套递归调用。
在这些默认函数中，defun 和 lambda 操作符允许创建用户定义的函数，然后在一个名为 localContext 的全局访问字典中注册：
public var localContext = [String: (SExpr, [SExpr]?, [SExpr]?)-&SExpr]()
让我们看看 defun（ lambda 的实现基本和它一致）是如何实现的。
env[Builtins.defun.rawValue] =
{ params,locals,values in
guard case let .List(parameters) = params, parameters.count == 4 else {return .List([])}
guard case let .Atom(lname) = parameters[1] else {return .List([])}
guard case let .List(vars) = parameters[2] else {return .List([])}
let lambda = parameters[3]
let f: (SExpr, [SExpr]?, [SExpr]?)-&SExpr = { params,locals,values in
guard case var .List(p) = params else {return .List([])}
p = Array(p.dropFirst(1))
if let result = lambda.eval(with:vars, for:p){
return result
}else{
return .List([])
localContext[lname] = f
return .List([])}
此函数需要一个包含四个符号表达式的列表，一个用于操作符名称，一个用于名称（这将是一个简单的原子），最后两个用于变量列表和 lambda 主体。 因此，一旦我们将每个组件存储在一个常量中（注意，空列表再次用作错误值），我们在 localContext 中定义和注册一个类型为 (SExpr，[SExpr]?，[SExpr]?)-& SExpr 的函数，将会看到，当评估器在表达式中找到它时，会被 eval() 调用。
在调用期间，这个匿名函数将使用当前参数来评估 lambda 的主体，替换原始变量列表中包含的变量，并返回结果。
为了更好地理解这里发生了什么，让我们来看看 eval()函数：
public enum SExpr{
case Atom(String)
case List([SExpr])
Evaluates this SExpression with the given functions environment
- Parameter environment: A set of named functions or the default environment
- Returns: the resulting SExpression after evaluation
public func eval(with locals: [SExpr]? = nil, for values: [SExpr]? = nil) -& SExpr?{
var node = self
switch node {
case .Atom:
return evaluateVariable(node, with:locals, for:values)
case var .List(elements):
var skip = false
if elements.count & 1, case let .Atom(value) = elements[0] {
skip = Builtins.mustSkip(value)
if !skip {
elements = elements.map{
return $0.eval(with:locals, for:values)!
node = .List(elements)
if elements.count & 0, case let .Atom(value) = elements[0], let f = localContext[value] ?? defaultEnvironment[value] {
let r = f(node,locals,values)
return node
private func evaluateVariable(_ v: SExpr, with locals: [SExpr]?, for values: [SExpr]?) -& SExpr {
guard let locals = locals, let values = values else {return v}
if locals.contains(v) {
return values[locals.index(of: v)!]
}else{
评估期遍历抽象语法树，根据可评估的类型形式执行不同的操作
当遇到一个原子时，可以试着把它当做具有局部变量的当前上下文的变量（最初由 defun 或 lambda 设置，并在调用之间传播）进行解析，但大多数时候它只是返回原子。
这是在执行用户定义lambda的变量替换的地方，我们简单地使用 evaluateVariable 验证每个原子的名称是否存在于变量的数组中，如果是，我们用具有相同索引的原子替换值数组中的原子。
在评估列表或复合形式时，我们需要更多的考虑。
我们将首先尝试递归地评估当前列表中的所有子表达式，但前提是当前运算符不需要处理此评估本身。如上所述，在这个简单的 LISP 解释器中只有 quote，特殊形式和 lambda 定义运算符这三类。
一旦子表达式求值完毕，就应该将运算符应用于其操作数，该操作符在 localContext 中执行查找于运算符原子具有相同名称的lambda，然后在 defaultEnvironment 中找。顺序很重要，因为我们希望能够使用那些手动定义的新函数来隐藏默认定义。
如果存在具有该名称的lambda，则调用该函数，并将结果返回到递归计算的上一步。
这就结束了对基本解释器的描述，整件事情需要大概400行代码。
SwiftyLisp REPL现在是时候实现 REPL 了，但是它花费不了太长时间，解释器具有我们需要的所有基本功能。
我们将从终端读取一行，将其转换为 SExpr，对其进行评估并打印结果，这要归功于 CustomStringConvertible 协议。
import SwiftyLispvar exit = falsewhile(!exit){
print("&&&", terminator:" ")
let input = readLine(strippingNewline: true)
exit = (input=="exit") ? true : false
if !exit {
let e = SExpr.read(input!)
print(e.eval()!)
}}
REPL 已经上传到 GitHub 另外一个。
总结本文介绍了一个最小 LISP 解释器，介绍普通解释器的基本构建块，而不考虑语言。
如果你以前从来没有这样做过，第一眼可能看起来令人畏惧，但我想要传达的意思是：这只不过是一个具有一定工作量的项目，但是每个人都能够完成。
查看 Github 上的，并在评论中告诉我，如果你想阅读更多关于解释器和编译器的话！
本文由 SwiftGG 翻译组翻译，已经获得作者翻译授权，最新文章请访问 。