我的静态类型脚本语言Umka的开发已经进入阶段,需要用比几十行中的脚本更复杂的示例来测试语言功能。为此,我决定用我的语言实现Lisp解释器。我受到Go语言的创建者之一Rob Pike进行的教学实验的启发。 Pike最近在Go中发布了一个小型的Lisp解释器。派克(Pike)的话给我留下了深刻的印象,即口译员的描述在古老的Lisp 1.5手册的第13页上。...鉴于Umka和Go在语法上的亲和力,很难抵制在Umka中构建这样的解释器的诱惑,而不是通过字面上的转移派克的代码,而是完全从头开始。我希望Lisp和功能语言的鉴赏家能原谅我与美接触的天真惊奇。
对于初学者来说,Lisp可能会遇到几乎震惊的情况。代码和数据之间的界线在哪里?循环在哪里?堆栈在哪里?唯一的数据结构是一棵树。它也可以代表一个列表。解析程序时,它也成为抽象语法树。在评估表达式时,它也会替换堆栈。任何树都可以尝试作为代码执行或用作数据。代替循环-递归。语言的核心甚至没有算术。然而,这是一种图灵完整的语言,可以无限扩展和撒满语法糖。
定义一个最小的Lisp解释器实际上只需不到一页。当然,它只是使用了前面几页中定义的功能。Lisp的创建者John McCarthy似乎已经超越自己的传统,最终出版了一份Lisp微型手册,其中包含语言定义以及解释器的来源-共两页。是的,他在标题上加上了“不是全部事实”。
语言的核心(这里我们谈论的是最古老和最简单的方言)需要五个基本功能,四个关键字和两个无法通过语言本身表达的常量。
不熟悉这些语言的人的基本语言结构
(car x)
-突出显示列表的开头x
(cdr x)
-突出显示列表的末尾x
(cons x y)
-加入名单x
和y
(atom x)
-检查x
原子性(eq x y)
-检查原子元素x
和y
相等性(cond (a x) (b y))
-一个值的选择x
或者y
由条件a
或b
(quote x)
-使用说明x
,无需计算((lambda (x) a) y)
-使用bodya
,形式参数x
和实际参数调用未命名的函数y
((label ff (lambda (x) a)) y)
-为未命名的函数分配名称ff
t
-真相nil
-错误或空表达式
使用这些构造,可以定义和调用递归函数,以便单个语句将整个程序封闭起来。如果我们向其中添加算术函数,则可以例如计算阶乘6:
((label fac (lambda (n) (cond ((eq n 0) 1) ((quote t) (mul n (fac (sub n 1))))))) 6)
Lisp, . Lisp 1.5 13 , . . , REPL . , , , label
defn
, , . Lisp .
由于整个解释器都充满了递归和树处理功能,因此它是对Umka语言许多功能(从堆栈到垃圾收集)的出色测试。我认为Umka在测试中表现出色。我们只需要修复与名称和高级类型声明的导出有关的两个或三个小错误。整个解释器代码的长度不足400行。
对于那些想要与我的口译员一起玩并通过接力赛传授Rob Pike灵感的人,我建议从master分支而不是最新版本的文件夹中获取示例。