魔盒挑战 2022.5 简单LISP解释器

一份简易的LISP（Scheme）教程

相信不少人对LISP这门编程语言有所耳闻，又常常听说这门语言“抽象难学”。但实际上LISP的语法规则相当简单，甚至只有几个最基本的规则。下面就拿LISP的一种经典方言Scheme举例：

(+ 1 2)

上面的代码很好理解。(+ a b)在这里是一个表达式，可以理解为一个函数，接受两个参数，并且返回它们之和，(+ 1 2)的结果就是3，同理(* 2 3)的结果是6，(- 1 2)的结果是-1……

这些表达式也可以组合起来：

(+ (* 3 5) (- 10 6))

上面这个表达式的值就是19，这相当于(3 * 5) + (10 - 6)。

我们常常将LISP表达式通过缩进更清晰地表示：

(+ (* 3
      (+ (* 2 4)
         (+ 3 5)))
   (+ (- 10 7)
      6))

上面这段代码相当于(3 * ((2 * 4) + (3 + 5))) + ((10 - 7) + 6)，值是57.

除了基本的加减乘除外，LISP还有一些特殊的关键字，例如define可以用来定义变量：

(define size 2)
(* 5 size)

这里先定义了一个值为2的变量size，然后将它乘以5，最终结果是10.

更有意思的是，define还可以用来定义自己的函数：

(define (square x) (* x x))

这里定义了一个名为square的函数，它接收一个参数x，并返回它的平方。

我们刚才定义的square函数可以这样调用：

(define size 3)
(square size)

这段代码的返回值是9.

下面是define函数定义的一般形式：

(define (<函数名> <参数1> <参数2> <参数3> ...) <具体实现...>)

下面定义一个稍微复杂的函数sum-of-squares，接收两个参数，返回它们的平方和：

(define (sum-of-squares x y)
  (+ (square x) (square y))

注意到，这里使用了刚才定义的square函数。上面这段代码应该很容易理解。下面我们使用该函数：

(sum-of-squares 3 4)

这段代码的返回值是25，即(3 * 3) + (4 * 4)的值.

除了define之外，LISP也有类似if ... else ...的条件表达式，在Scheme中它被这样实现：

(define (abs x)
  (cond ((> x 0) x)
        ((= x 0) 0)
        ((< x 0) (- x))))

上面的代码定义了一个abs函数，用来返回某个数的绝对值。这里使用了cond做条件判断。上面的代码应该也不难理解。cond条件表达式的一般形式如下：

(cond (<条件1> <返回值1>)
      (<条件2> <返回值2>)
      (<条件3> <返回值3>)
      ...)

同时cond表达式也提供了一个可选的else，用来在所有条件都不成立时返回值：

(define (abs x)
  (cond ((< x 0) (- x))
        (else x)))

此外，Scheme也提供了简化的cond，即if：

(define (abs x)
  (if (< x 0)
      (- x)
      x))

上面的代码也很好理解。if后面跟的第一个参数是条件，条件应该是一个返回布尔值的函数，这里的(< x 0)表示条件"若x小于0"；第二个参数是当条件成立时的返回值，也就是x小于0时返回-x；第三个参数是当条件不成立时的返回值，也就是当x大于等于0时返回x。

下面是if条件表达式的一般形式：

(if <条件> <条件成立时的返回值> <条件不成立时的返回值>)

同时，Scheme也包含Python中的and、or、not，而且它们也是惰性求值的：

(and <e1> <e2> <e3> ...)
(or <e1> <e2> <e3> ...)
(not <e>)

对于and，Scheme解释器从左到右一个个地求值<e>，如果某个<e>求值得到假，这一and表达式的值就是假，后面那些<e>自然也不用再求值了。如果所有的<e>都求出真值，这一and表达式的值就是最后那个<e>的值。

同理，对于or，Scheme解释器从左到右一个个地求值<e>，如果某个<e>求值得到真，这一or表达式的值就是真，后面那些<e>自然也不用再求值了。如果所有的<e>都求出假值，这一or表达式的值就是最后那个<e>的值。

对于not，如果<e>求出的值是假，not表达式的值就是真，否则其值为假。

作为示例，下面定义大于等于函数>=：

(define (>= x y)
  (or (> x y) (= x y)))

或者可以这么定义：

(define (>= x y)
  (not (< x y))

实际上，到此为止，所有基本的Scheme语法就解释完毕了，已经可以开始编写图灵完备的程序了。仅仅掌握这些知识就能写代码了，简直简单到不可思议……但是等一下，循环呢？

在LISP中，循环的实现方式是递归。Lisp没有常规的for/while循环，一切类似的操作都可以使用递归实现。下面通过已经介绍的这些语法，实现一个计算阶乘的函数factorial：

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

可以看到，这里使用了递归的思想：若n是1，则直接返回1，否则返回n乘以factorial(n-1)。计算阶乘就是这么简单。

下面我们尝试着综合运用学到的知识，实现一个求幂的函数。相比于上面实现阶乘的函数，这里的求幂函数使用了迭代的思想，所以会稍微复杂一些，可能需要花一点时间去理解，你也许需要在草稿纸上动手画一画示意图，但这里用到的知识完全没有超出上面介绍的范围：

(define (expt b n)
  (expt-iter b n 1))
(define (expt-iter b counter product)
  (if (= counter 0)
      product
      (expt-iter b
                 (- counter 1)
                 (* b product))))

不过，这种求幂的方法未免有些低效。我们知道$b^8$可以拆分成$b^4*b^4$，而$b^4$又可以继续拆分成$b^2*b^2$，而$b^2$就是$b*b$，只需通过这么三步就可以计算得到结果。而上面的代码如果要计算$b^8$，则只是一步步将结果乘以$b$，计算了$8$次。于是我们可以这样实现一个快速求幂函数：

(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))
(define (even? n)
  (= (remainder n 2) 0))

上面代码里的remainder表示求余，相当于Python中的%符号。

题目

好了，通过上面的教程，你应当已经基本理解Scheme的语法了。这些语法本质上非常简单，而且LISP独特的语法使得这些语法解析起来非常简单。你可能会认为实现一个Scheme解释器非常复杂，但实际上如果只需要实现上面这些简单的功能，几十行Python代码就可以做到，你可以试试看。事实上，目前速度最快并且进行高度优化的一个完整Scheme解释器"Chez Scheme"也只用了不到一千行C语言代码，由此可见Lisp的实现是多么简单。

你只需要编写一个Python版本的Scheme解释器（当然，如果你乐意，也可以使用其它语言），这个解释器只需要实现上面提到的最基本的语法。它接受一个字符串，也就是Scheme代码，返回这段代码的执行结果。你的脚本应当可以通过命令行进行交互，例如：

> python test.py "(define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1))))) (factorial 5)"
120

或者，这个Scheme解释器可以读取一个文本文件，执行其中的Scheme代码。例如：

> python test.py expt.txt
256

下面是上面示例中expt.txt的内容：

(define (expt b n)
  (expt-iter b n 1))
(define (expt-iter b counter product)
  (if (= counter 0)
      product
      (expt-iter b
                 (- counter 1)
                 (* b product))))
(expt 2 8)

在这里给出一个基本的Python代码框架，它接收一个文件名，读取并解析该文件中的Scheme代码，并打印结果到终端（不过如果你喜欢，自然也可以不按这个框架来写）：

#!/usr/bin/python3
# -*-coding:utf-8-*-
import re
import sys


def process_code_string(s: str) -> str:
    ...


if __name__ == '__main__':
    args = sys.argv
    if len(args) <= 1:
        raise TypeError('interpreter takes exactly one argument (0 given)')
    elif len(args) > 2:
        raise TypeError(f'interpreter takes exactly one argument ({len(args) - 1} given)')
    
    filepath = args[1]
    with open(filepath, 'r', encoding='utf-8') as f:
        s = f.read()
    
    print(process_code_string(s))

解释器的核心代码应该都包括在process_code_string这一函数中。这里省略了该函数的实现，因为这显然是需要你自己去完成的。

具体来说，你需要实现以下Scheme语法：

• 实现基本的数据类型（数字及布尔值）
• 基本组合式，例如加减乘除运算、取负数、取余（remainder）、求商（quotient）、开方（sqrt）、判断相等/大于/小于等。如果你愿意实现一个更完善的解释器，可以考虑加入sin、cos、tan、asin、acos、atan、min、max、abs、square、exp、expt、log等内置函数
• 变量及函数定义（通过define）。或者你也可以通过lambda块的方式实现函数定义（你可以自行了解相关资料）
• cond条件表达式，需要包含else的实现，并且需要包含and/or/not。你实现的cond表达式应当是惰性求值的
• （可选）实现if表达式。由于if表达式实质上是对cond的简化，因此这并不是必须实现的
• 递归调用函数

下面是详细的评分标准（满分100分）：

• 实现基本组合式求值与数字类型（例如(+ 1 2)）—— 15分
• 实现布尔类型（#f和#t） —— 5分
• 实现常见运算（加减乘除、取余、开方、相等/大于/小于判断等）—— 10分
• 实现变量定义 —— 15分
• 实现cond条件表达式（if表达式可不实现）—— 10分
• 实现函数定义（define或lambda块，可挑选任意一种实现方式） —— 20分
• 实现函数的递归调用 —— 15分
• 其他分数（根据实现方式、逻辑结构、代码规范等给出的主观综合评分）—— 10分

你需要在附带的文档中给出你实现Scheme解释器的过程，使用了什么样的思路，并给出示例代码和运行结果。此外，你还需要给出附有适当注释的解释器源代码。

在完成这一题目后（即使你仅仅完成了一小部分也没有关系），请将代码及文档发送到邮箱gaoge011022@163.com，我们会尽快为题目打分，给出结果。当然了，如果你不仅仅满足于此，你也可以考虑继续实现下面的”进阶“甚至“挑战”任务，会有加分。

提示：如果你希望高效地实现这个解释器，可能会需要用到关于抽象语法树(Abstract Syntax Tree)的知识，这是一种简单的树状数据结构，并且与Lisp语法的相性非常好。不过，如果你不愿那么深入，直接用正则表达式甚至通过.replace()和.split()分割字符串也能实现一个不错的Scheme解释器。

提示2：如果你希望能够实际体验一下编写Scheme代码，你可以在Chez Scheme的官方网站上下载安装一个现成的Scheme解释器用来体验一下。在安装完成后，你的电脑上将会出现Chez Scheme的程序，运行之后会弹出一个交互式的命令行窗口，你可以在这里运行你的Scheme代码。

提示3：如果你对如何实现这个解释器毫无头绪，可以通过搜索“Python实现LISP解释器”获得一些信息。不过建议你尽量不要这么做。

注意事项：在Scheme中，布尔值被表示为#f或#t，对应着Python中的False与True，例如(> 1 2)对应的返回值就应该是#f。

注意事项2：在Scheme中，可以使用;表示注释的开头，以换行作为结尾。例如(expt 2 8) ; 256，这后面的; 256会被自动忽略。你可以考虑实现这一特性，也可以选择不实现。

注意事项3：如果你仍感觉实现这些功能比较困难，可以考虑只实现上面提到的一部分功能，例如只实现最简单的(+ 1 2)，变量定义(define x 1)等。

进阶

如果你在实现完这个简单的Scheme解释器后仍有余力，可以考虑实现一些更高级的语法，例如添加对字符串和浮点数的支持、lambda语句块、列表(list)、局部变量(let)甚至闭包。你可以在w3cschool上找到一个完整的Scheme教程(Yet Another Scheme)，并考虑实现这里提到的部分特性。当然，你也可以自己查找其他资料学习Scheme。

这里并不给出一个具体需要实现哪些语法的列表，你可以自由发挥。推荐你先尝试实现列表（cons及list），以及在列表上使用的一些常用函数（car/cdr/filter/map/reduce/for-each等），由于Python本身对这些函数有支持，并且Python的list与Scheme中的list很相似，因此你只需要在之前的代码基础上做一些小小的改进就可以实现。或者你也可以先实现lambda语句块，它本质上不过是另一种更通用的变量定义方式，应当也是很容易实现的。你也可以优先考虑实现let/throw/quote这些简单的语法，这应当也比较轻松。至于实现字符串可能稍微有些困难，这需要运用一些数据结构的思想，例如栈和树，不过你也可以通过简单的循环判断实现。

另外，非常推荐你首先选择实现Scheme内置的(display x)函数，它负责在命令行（终端）中直接打印x的值，很类似于Python中的print函数。这样就可以非常方便地调试Scheme代码了。

你甚至可以考虑实现一些自己的独特想法，甚至是不包含在Scheme语法规范里的语法。例如，你可以实现一个(print-to-file <string> <filepath>)函数，将字符串<string>的值输出到文件。你也可以将一些函数内置，例如上面提到的(square x)函数，使其不需定义就可以直接使用。你可以充分发挥创造力，打造属于自己的LISP方言。

例如，在LISP的另一门方言Clojure中，实现了宏定义(->> ...)，它可以像下面这样使用：

(->> 1
     (+ 1)
     (* 2)
     (- 10))

上面这段代码的值是-6，正好就是((1 + 1) * 2) - 10的结果。在Clojure中，这被称为thread-last宏，它将典型的LISP书写顺序颠倒了过来，重整为更自然的从左到右的阅读顺序，很符合人类的习惯，也更加清晰。

假设你已经实现了list、字符串、lambda块等高级特性，利用上面提到的"->>"，就可以编写更有意思的代码：

(define (process-string Alist)
  (->> Alist
       (filter (lambda (x) (> (string-length x) 1)))
       (map capitalize)
       (interpose ",")
       (reduce str)))
(define list-of-employees (list "neal" "s" "stu" "j" "rich" "bob" "aiden"))
(process-string list-of-employees)
; 下面一步一步地演示了list-of-employees的转换过程
; ("neal" "s" "stu" "j" "rich" "bob" "aiden")
; ("neal" "stu" "rich" "bob" "aiden")
; ("Neal" "Stu" "Rich" "Bob" "Aiden")
; ("Neal" "," "Stu" "," "Rich" "," "Bob" "," "Aiden")
; "Neal, Stu, Rich, Bob, Aiden"

上面先不讨论filter、map、capitalize、interpose、reduce、str这几个内置函数是怎么实现的，只着眼于代码本身。上面这段代码演示了处理如何处理一个包含公司雇员姓名的列表：先去除所有只有一个字母的错误数据，再对每个雇员的姓名应用capitalize，即将其首字母大写，然后用interpose在两两单词之间插入,作为分隔符，然后通过reduce累加地调用str函数将这些单词组合起来。

上面代码中演示的解决问题的方式被称为函数式编程思想，而LISP就是一种典型的函数式编程语言。函数式编程不关心复杂的数据结构与类继承关系，而是创造一系列通用的函数，将复杂的问题转换为最基本的几个数据结构，然后利用这些通用的函数求解问题，而不是制造更多的数据结构。函数式编程将函数当作”一等公民“，函数也可以被当作变量，可以直接作为参数传入，这被称为高阶函数，例如上面代码中的"filter"就接收了一个lambda函数作为参数。在函数式编程中，很常用的三个操作列表的函数是filter(筛选)、map(映射)、reduce(折叠/化约)，Python中也有这三个函数，你可以了解一下，并考虑在你的Scheme解释器上实现它们（不过你显然需要先实现list）。此外，函数式编程还有不变性、减少副作用等概念，你若感兴趣可以自行了解。

不过，要让你的Scheme解释器支持运行上面提到的代码可能并不容易。这个例子仅仅是展示了LISP的无限可能：即使->>并不是Scheme的标准语法，你仍可以轻松地实现这个功能（相较于其他语言来说），这意味着你可以充分发挥你的想象力，创造属于自己的LISP方言。

当然了，这一部分不作强制要求，仅仅作为加分项（满分40分，作为附加分）。如果你实现了基本功能之外的功能，需要在附带的文档中指出你实现了哪些Scheme高阶特性，又有哪些是你独创的语法，并给出示例代码和运行结果。此外，你还需要给出附有适当注释的解释器源代码。

为了不束缚想象力，这一部分较为开放，并不包括详细的评分标准。但你可以在下面的推荐里挑选几个实现。当然，你可以实现的功能远不仅限于这个范围。我们会根据你具体的实现情况以及创新点决定你的40分附加分：

• 实现字符串以及浮点数
• 实现局部变量（let）
• 实现高阶函数
• 实现列表（list和cons）及相关函数（filter/map/reduce/for-each等）
• 实现内置的哈希表
• 实现文件输入/输出API
• 实现引用语法（'）
• 实现向量（vector）
• 实现一些独特的内置宏定义（例如上面演示的thread-last宏）
• 实现一些有趣的独创语法
• 其他创新点

再次强调，相比于100%还原Scheme语法，我们更希望能够看到一些闪光的创新点。我们的目的并不是复刻一门语言，而是实现一个有趣的解释器。因此，我们会考虑对创新特性进行更多加分，即使是实现起来非常容易的创新点。

注：如果你对此很感兴趣，希望深入学习Scheme，可以在这次活动结束后阅读《计算机程序的构造与解释（SICP）》，这本书从原理入手，通过Scheme解释了编程语言的原理，很有趣但也很需要一定的思维量。不过在这次活动中就不推荐你阅读了，这本书需要很长的时间才能搞明白，而且应当对你在本次活动中的解题过程没什么帮助。

挑战

注意：这一部分仅仅作为“挑战”，即使你完成了这些挑战，给出了很完善的实现，也只能获得很少的加分（满分10分）。建议优先考虑完善上面的基本题目与“进阶”部分。

如果你在完成进阶任务后仍有余力，可以考虑完成这里的一部分“挑战”。完成这些挑战有助于将你的Scheme解释器变成一个真正具有实用价值的解释器，可以真正方便地运行各种代码，并且具有简单的调试功能。

以下是挑战列表。当然，如果你不满足于这些挑战，也可以自己完成想做的挑战：

• 实现一个简单的REPL（交互式运行环境），就像Python自带的IDLE一样。实现这一功能可能远比你想象的简单许多，甚至只需要十数行代码
• 输出更好的报错信息，当代码出现语法错误时猜测可能是哪里出了问题
• 实现尾递归优化
• 实现垃圾回收（你可以考虑最简单的引用计数法，当然也可以挑战自己选择使用更复杂的算法实现）
• 考虑完全不使用eval实现解释器。注意：较难
• 为LISP添加面向对象支持，例如加入class关键字。如果你对如何添加类似Java/Python中传统的面向对象支持没有头绪，可以考虑实现JavaScript中的原型链继承。一个更简单的主意是先考虑实现C语言中的结构体（struct）。注意：这可能非常困难！尝试完成这一挑战时请务必谨慎

值得注意的是，“挑战”与“进阶”的区别在于“进阶”仅限于语法层面，而“挑战”部分的内容范围更广，并且不集中于语法层面，且难度大得多。例如你在语法之外实现了解释器速度上的优化，那么这些工作就算在“挑战”中。“挑战”的加分很少（仅10分），因此推荐你不优先考虑解释器的效率问题。

如果你尝试着完成了这些挑战的一部分，可以将你通过Scheme实现解释器的心路历程、实现了哪些语法、又实现了哪些自创语法、示例代码和运行结果写在文档里，并给出解释器的源代码。再次强调，这一部分仅仅是一个“挑战”，即使你给出了很完善的实现，也只会有很少的加分，仅建议你在有余力的情况下考虑挑战这个任务。