第二十三课 - Eval in register machine
在上一节课中，我们的 register machine 增加了对 subroutine 和 stack 的支持，可以顺利执行一些过程 (procedure)，如 gcd、factorial 等。既然如此，我们是否可以用它来构建通用机 (universal machine)，即之前的 evaluator？构建完 evaluator 后，我们的 简易 CPU 也就完成了。
Tail-recursive Evaluator
例子：sfact
(define sfact (lambda (n prod)
(display prod)
(if (= n 1) prod
(sfact (- n 1) (* n prod)))))
sfact 是 iterative process 还是 recursive process？
sfact 虽然调用了自己，但由于它在调用 subroutine 前把 prod 当作参数传递，因此它的状态无需保存在栈中，这时候栈深是常数级别，因此整个过程是 iterative process。
输入一个 iterative procedure，如果一个 Evaluator 的栈深没有随着程序的自调用而增大，那么这个 Evaluator 被称为 Tail-recursive Evaluator
Tail-call Optimization
Tail-recursive Evaluator 的核心技术就是 Tail-call Optimization (尾递归优化)。
Machine for EC-EVAL
组件：
- 7 registers
- exp 保存表达式 (expression to be evaluated)
- env 保存当前环境 (current environment)
- continue 保存返回地址 (return point)
- val 保存输出结果 (resulting value)
- unev 还未执行的表达式列表 (list of unevaluated expressions)、临时寄存器 (temporary register)
- proc 过程 (operator value)
- argl 参数 (arguments values)
- Many abstract operations
- 假设一些与 syntax、environment model 有关的操作都以 primitive procedures 的形式存在，它们可以由更基本的操作构成，但这里为了描述方便，假设它们已经存在
Main entry point
EC-EVAL 的 entry point 是 eval-dispatch，如下所示：
; inputs: exp expression to evaluate
; env environment
; continue return point
; output: val value of expression
; writes: all (except continue)
; stack: unchanged
eval-dispatch
(test (op self-evaluating?) (reg exp))
(branch (label ev-self-eval))
(test (op variable?) (reg exp))
(branch (label ev-variable))
...
(goto (label unkown-expression-type))
eval-dispatch 与调用者之间的契约在注释中注明。eval-dispatch 的形式也与十七课中的 eval 一致，按顺序判断表达式类型，然后把表达式传递给相应的 eval-helpers，这些过程与调用者之间的契约与 eval-dispatch 一致，以下是几个例子：
ev-self-eval
(assign val (reg exp))
(goto (reg continue)
ev-variable
(assign val (op lookup-variable-value)
(reg exp) (reg env))
(goto (reg continue))
ev-lambda
(assign unev (op lambda-parameters)
(reg exp))
(assign exp (op lambda-body) (reg exp))
(assign val (op make-procedure)
(reg unev) (reg exp) (reg env))
(goto (reg continue))
- ev-self-eval 负责处理 self-evaluating 表达式，因为 self-evaluating 表达式的值就是表达式本身，因此 ev-self-eval 直接将 exp 寄存器中的信息直接放入 val 寄存器中，然后返回到 continue 指向的返回地址
- ev-variable 负责在环境中查询变量的 binding，因此 ev-variable 取出 exp 中的变量表达式以及 env 中的环境，利用 lookup-variable-value 过程从环境中取出对应的变量值，放入 val 寄存器中，然后返回 continue 指向的返回地址
- ev-lambda 负责处理 lambda 表达式，lambda 表达式需要存储参数、过程体以及当时的环境，因此 ev-lambda 依次从 exp 中取出参数和过程体，然后从 exp 中取出环境，用 make-procedure 将三者打包，放入 val 寄存器中，最后返回 continue 指向的返回地址。
ev-definition: 递归调用 eval-dispatch
与上文中 eval-helpers 的例子 ev-self-eval、ev-variable 和 ev-lambda 不同，ev-definition 需要递归调用 eval-dispatch：
ev-definition
(assign unev (op definition-variable) (reg exp))
(save unev)
(save env)
(save continue)
(assign exp (op definition-value) (reg exp))
(assign continue (label ev-definition-1))
(goto (label eval-dispatch))
ev-definition-1
(restore continue)
(restore env)
(restore unev)
(perform (op define-variable!)
(req unev) (reg val) (reg env))
(assign val (const ok))
(goto (reg continue))
由于 eval-dispatch 可能会修改 uenv、env、continue 寄存器，同时在递归调用结束后 ev-definition 还需要原先这些寄存器里的数据，因此在递归调用之前，需要把它们压入栈中，调用完成中再从栈中弹出。
ev-if: 递归调用 eval-dispatch 与尾递归优化
ev-if
(save exp)
(save env)
(save continue)
(assign continue (label ev-if-decide))
(assign exp (op if-predicate) (reg exp))
(goto (label eval-dispatch))
ev-if-decide
(restore continue)
(restore env)
(restore exp)
(test (op true?) (reg val))
(branch (label ev-if-consequent))
ev-if-alternative
(assign exp (op if-alternative) (reg exp))
(goto (label eval-dispatch))
ev-if-consequent
(assign exp (op if-consequent) (reg exp))
(goto (label eval-dispatch))
- 递归调用 eval-dispatch 获取 predicate 的结果，同样在递归调用之前将 uenv、env、continue 压入栈中，递归调用之后再将它们从栈中弹出
- 在调用 alternative 和 consequent 时，由于 ev-if 无需对 alternative 和 consequent 的返回值做后处理，因此 ev-if 使用尾递归优化 (Tail-call optimization)。如果没有尾递归优化，它们的写法如下所示：
ev-if-alternative
(save continue)
(assign continue (label alternative1))
(assign exp (op if-alternative) (reg exp))
(goto (label eval-dispatch))
alternative1
(restore continue)
(goto (label continue))
ev-if-consequent
(save continue)
(assign continue (label consequent1))
(assign exp (op if-consequent) (reg exp))
(goto (label eval-dispatch))
consequent1
(restore continue)
(goto (label continue))
Sequences: 递归调用 eval-dispatch 与尾递归优化
ev-begin
(save continue)
(assign unev (op begin-actions) (reg exp))
(goto (label ev-sequence))
; ev-sequence: used by begin and apply (lambda bodies)
;
; inputs: unev list of expressions
; env environment in which to evaluate
; stack top value is return point
; writes: all (calls eval without saving)
; output: val
; stack: top value removed
ev-sequence
(assign exp (op first-exp) (reg unev))
(test (op last-exp?) (reg unev))
(branch (label ev-sequence-last-exp))
(save unev)
(save env)
(assign continue (label ev-sequence-continue))
(goto (label eval-dispatch))
ev-sequence-continue
(restore env)
(restore unev)
(assign unev (op rest-exps) (reg unev))
(goto (label ev-sequence))
ev-sequence-last-exp
(restore continue)
(goto (label eval-dispatch))
- ev-sequence-last-exp 没有再进行额外的入栈出栈开销，做了尾递归优化，使得 sfact 这样尾递归表达式能够按照迭代过程的方式来执行。但尾递归优化无法对 env 和 unev 使用，原因在于二者在递归调用的过程中可能被修改，如果不压入栈中就会丢失对应的信息。
- ev-sequence-continue 没有使用 val 寄存器，原因在于 sequence 语句，只以最后一条语句的返回值作为最终返回结果，中间表达式的返回结果都忽略不计。
Applications
apply-dispatch
; inputs: proc procedure to be applied
; argl list of arguments
; stack top value is return point
; writes: all (calls ev-sequence)
; output: val
; stack: top value removed
apply-dispatch
(test (op primitive-procedure?) (reg proc))
(branch (label primitive-apply))
(test (op compound-procedure?) (reg proc))
(branch (label compound-apply))
(goto (label unknown-procedure-type))
primitive-apply
primitive-apply
(assign val (op apply-primitive-procedure) (reg proc) (reg argl))
(restore continue)
(goto (reg continue))
compound-apply
compound-apply
(assign unev (op procedure-parameters) (reg proc))
(assign env (op procedure-environment) (reg proc))
(assign env (op extend-environment)
(reg unev) (reg argl) (reg env))
(assign unev (op procedure-body) (reg proc))
(goto (label ev-sequence))
ev-application
ev-application
(save continue)
ev-appl-operator
(assign unev (op operands) (reg exp))
(save env)
(save unev)
(assign exp (op operator) (reg exp))
(assign continue (label ev-appl-did-operator))
(goto (label eval-dispatch))
ev-appl-did-operator
(restore unev)
(restore env)
(assign proc (reg val))
; eval argl
(assign argl (op empty-arglist))
(test (op no-operands?) (reg unev))
(branch (label apply-dispatch))
(save proc)
ev-appl-operand-loop
(save argl)
(assign exp (op first-operand) (reg unev))
(test (op last-operand?) (reg unev))
(branch (label ev-appl-last-arg))
;; eval one operand
(save env)
(save unev)
(assign continue (label ev-appl-accumulate-arg))
(goto (label eval-dispatch))
ev-appl-accumulate-arg
(restore unev)
(restore env)
(restore argl)
(assign argl (op adjoin-arg) (reg val) (reg argl))
(assign unev (op rest-operands) (reg unev))
(goto (label ev-appl-operand-loop))
ev-appl-last-arg
(assign continue (label ev-appl-accum-last-arg))
(goto (label eval-dispatch))
ev-appl-accum-last-arg
(restore argl)
(assign argl (op adjoin-arg) (reg val) (reg argl))
(restore proc)
(goto (label apply-dispatch))
由于 operator 自身可能包含 application，它们可能会 extend-environment，也会使用到 unev 寄存器，因此在 eval operator 的时候，需要把当前的 env、uenv 寄存器压入栈中保存起来。eval operator 结束时，结果会被存在 val 寄存器中，ev-appl-did-operator 把它放入 proc 寄存器中，等待下一步被调用。
接下来 ev-appl-operand-loop、ev-appl-last-arg 和 ev-appl-accum-last-arg 一同 eval application 的参数，最后执行 application。
现在我们完成了 EC-EVAL 的主要组件，也能体验到用 register machine 构建 universal machine，也即 evaluator 的过程。
小结
本节通过大量代码讲解了如何用 register machine 构建 universal machine 的过程，让我们对 scheme evaluator 的底层拥有最基本的了解。非研究目的代码不必细扣。