Racket-1

认识 Racket-1：一个用 Racket 编写的简单解释器，展示解释器的基本组成部分。

开始上手

在终端输入下面的命令，把 Racket-1 解释器的源代码复制到当前目录：

cp ~cs61as/lib/racket1.rkt .

你也可以在这里下载代码。

要在 Racket 中启动 Racket-1，请输入：

;; 加载 Racket-1 文件
(require "racket1.rkt")

;; 启动解释器
(racket-1)

通过求值一些表达式来熟悉 Racket-1。试着输入常规的 Racket 表达式，看看会发生什么！

你可能注意到，在 Racket-1 里你不能做正常 Racket 里的所有事情：

你有全部用于算术和列表操作的 Racket 原语。
你有 lambda，但没有高阶函数。
你没有 define。

要停止 Racket-1 解释器并返回 Racket，只需求值一个非法表达式，比如 ()。

什么是解释器？

要在计算机上运行一个程序，计算机里必须有某个东西理解代码的意图，执行必要的计算，然后返回结果。这个东西充当程序员的创意与执行计算的硬件之间的中介。这样的中介之一，就是解释器（interpreter）。

racket 就是 Racket 的解释器。它把 Racket 源代码翻译成指令，然后告诉计算机执行这些指令。它有能力读取输入并显示输出。

Racket-1 也是一个解释器，它适用于 Racket 的一个纯函数式子集。Racket-1 是用 Racket 写的，这个事实很有趣，但并不重要。我们也可以用别的语言（比如 Python）来写 Racket-1；而作为用户，真正重要的是解释器做什么，而不是它的源代码长什么样。

再过几课，我们会更深入地讨论解释器。现在，先来看看 Racket-1 是怎么工作的。

Racket-1 如何工作？

racket-1

racket-1 遵循以下规则：

要求值一个组合式：

求值该组合式的各个子表达式；
把是最左子表达式（运算符）之值的过程，应用于是其他子表达式（运算数）之值的那些实参。要把复合过程应用于实参，就用相应的实参替换每个形式参数，然后求值过程体。

（SICP：1.1.3、1.1.5）

示例：

Racket> ((lambda (x) (* x x)) (- 2 (* 4 3)))
100

这里发生了什么？根据上面的规则，请手工走一遍这个求值过程。

读取-求值-打印循环

解释器需要一个循环，才能做它做的所有事情。你每输入一条命令，racket-1 就解析并执行你的输入，返回输出，然后等待下一条命令。这叫做读取-求值-打印循环（Read-Eval-Print Loop，REPL）。

下面是 racket-1 的全部代码：

(define (racket-1)
    (newline)
    (display "Racket-1: ")
    (flush-output)
    (print (eval-1 (read)))
    (newline)
    (racket-1)
)

前三行只是打印提示符 “Racket-1: “。第四行才是关键：输入在这里被读取、解析，并送给 eval-1 去求值。等 eval-1 执行完代码，结果就被打印出来。最后，racket-1 调用自身来重启整个过程——再显示一个 “Racket-1: “，接收下一条命令。

eval-1

eval-1 负责返回作为 exp 传给它的任何计算结果。它由一个 cond 组成，对它能解释和计算的每一样东西都有一个子句。注意，特殊形式正是在 eval-1 中被捕获和处理的。

(define (eval-1 exp)
  (cond ((constant? exp) exp)
        ((symbol? exp) (eval exp))      ; 使用底层 Racket 的 EVAL
        ((quote-exp? exp) (cadr exp))
        ((if-exp? exp)
         (if (eval-1 (cadr exp))
             (eval-1 (caddr exp))
             (eval-1 (cadddr exp))))
        ((lambda-exp? exp) exp)
        ((pair? exp) (apply-1 (eval-1 (car exp))      ; 求值运算符
                              (map eval-1 (cdr exp))))
        (else (error "bad expr: " exp))))

apply-1

当要把过程应用于其实参时，eval-1 会调用 apply-1。apply-1 负责处理两种情况：

racket-1 原语。在这个语境中，原语就是非用户定义的过程。所有 Racket 过程都是 Racket-1 原语。
lambda 函数，即用户定义的过程。

(define (apply-1 proc args)
  (cond [(procedure? proc)      ; 使用底层 Racket 的 APPLY
          (apply proc args)]
        [(lambda-exp? proc)
         (eval-1 (substitute (caddr proc)   ; 过程体
                             (cadr proc)    ; 形式参数
                             args           ; 实参
                             '()))]         ; 已绑定的变量
        [else (error "bad proc: " proc)]))

racket-1 中的相互递归

Racket-1 练手

好吧，虽然你刚刚盯着代码看完了，但大概还没有完全理解它。我们来做几道练习，更好地熟悉这个程序。

手工详细追踪 racket-1 如何处理下面的过程调用：
```
((lambda (x) (+ x 3)) 5)
```
特别地，请走一遍 racket-1 为求值这个表达式必须调用的所有函数。

试着发明高阶过程；由于你没有 define，只能用 Y 组合子技巧，像这样：

Racket-1:
((lambda (f n)  ; 这个 lambda 在定义 MAP
    ((lambda (map) (map map f n))
    (lambda (map f n)
        (if (null? n)
            '()
            (cons (f (car n)) (map map f (cdr n))) )) )) ; 定义 MAP 的 lambda 到此结束
first              ; MAP 的实参 f
'(the rain in spain)) ; MAP 的实参 n

(t r i s)

由于所有 Racket 原语在 racket-1 中自动可用，你可能以为可以用 Racket 的原生 map 函数。试试这两个例子：
```
Racket-1:
(map first '(the rain in spain))
Racket-1:
(map (lambda (x) (first x)) '(the rain in spain))
```
解释结果。
修改解释器，添加 and 特殊形式。测试你的成果。确保一旦计算出假值，你的 and 就返回 #f，不再求值任何后续实参。