关于
本文是系列文章中的第五篇，
在上一篇中，我们介绍了编译器和解释器，抽象语法树与S表达式的关系，并且我们还打算写一个极简的元循环解释器。通过写这个解释器，一方面我们可以熟悉Racket语言，另一方面，可以帮助我们从实现角度来理解某些高级概念。
概览
（废话少说言归正传，一言不合就贴代码。。
这段代码我们用Racket实现了一个具有动态作用域Lisp方言的解释器。
我们没有使用Racket的模式匹配match，而是遵循一般教学用的常规写法，
把S表达式分为3种：符号，自求值表达式，列表（函数定义，函数调用）。
如果是符号，我们就得去“环境”中查找符号的值。
如果是自求值表达式，我们就直接返回它。（我们这里的自求值表达式只有数字
如果是函数定义，我们就用一个数据结构把参数和函数体存起来。
如果是函数调用，我们就先用实参“扩展”调用时的“环境”，然后让函数体在这个环境中求值。
#lang racket
; tool
(struct function
(param body))
(define (create-frame)
(make-hash))
(define (extend-frame frame key value)
(hash-set! frame key value))
(define (extend-env env frame)
(cons frame env))
(define (get-symbol-value env key)
(let lookup-env
((env env))
(if (null? env)
(error 'get-symbol-value "failed to find symbol")
(let ((head-frame (car env)))
(if (hash-has-key? head-frame key)
(hash-ref head-frame key '())
(lookup-env (cdr env)))))))
(define (handle-decision-tree tree exp)
(if (null? tree)
(error 'handle-decision-tree "failed to make decision")
(let* ((head (car tree))
(predicator (car head))
(decision (cadr head)))
(if (predicator exp)
(if (not (list? decision))
(decision exp)
(handle-decision-tree decision exp))
(handle-decision-tree (cdr tree) exp)))))
; env
(define *env* `(,(create-frame)))
; main
(define (eval-exp exp)
(handle-decision-tree
`((,is-symbol? ,eval-symbol)
(,is-self-eval-exp? ,eval-self-eval-exp)
(,is-list?
((,is-lambda? ,eval-lambda)
(,is-function-call-list? ,eval-function-call-list))))
exp))
(define (is-symbol? exp)
(display "is-symbol?\n")
(symbol? exp))
(define (eval-symbol exp)
(display "eval-symbol\n")
(get-symbol-value *env* exp))
(define (is-self-eval-exp? exp)
(display "is-self-eval-exp?\n")
(number? exp))
(define (eval-self-eval-exp exp)
(display "eval-self-eval-exp\n")
exp)
(define (is-list? exp)
(display "is-list?\n")
(list? exp))
(define (is-lambda? exp)
(display "is-lambda?\n")
(eq? (car exp) 'lambda))
(define (eval-lambda exp)
(display "eval-lambda\n")
(let ((param (caadr exp))
(body (caddr exp)))
(function param body)))
(define (is-function-call-list? exp)
(display "is-function-call-list?\n")
#t)
(define (eval-function-call-list exp)
(display "eval-function-call-list\n")
(let* ((fn (eval-exp (car exp)))
(arg (eval-exp (cadr exp)))
(body (function-body fn))
(param (function-param fn))
(frame (create-frame)))
(extend-frame frame param arg)
(let* ((env *env*)
(value '()))
(set! *env* (extend-env *env* frame))
(set! value (eval-exp body))
(set! *env* env)
value)))
测试
(display (eval-exp '1))
(display "\n\n")
(display (eval-exp '(lambda (x) x)))
(display "\n\n")
(display (eval-exp '((lambda (x) x)
1)))
(display "\n\n")
(display (eval-exp '((lambda (x)
((lambda (y) x)
2))
1)))
(display "\n\n")
(display (eval-exp '((lambda (x)
((lambda (f)
((lambda (x)
(f 3))
2))
(lambda (z) x)))
1)))
名词解释
今天这篇文章中提到了很多“耳熟能详”的概念名词，下面通过代码来解释它们。
环境
(define *env* `(,(create-frame)))
环境是帧（frame）的列表，其中“ ` ”是反引用（quasi-quotation），
反引用是一种模板，便于构建列表。
`(,(create-frame))
<=> (list (create-frame))
(create-frame)创建了一个帧，然后把它放到列表中，该列表目前只有一个元素。
这个帧的列表就是环境。
我们这里定义了一个全局变量*env*，
任何一个函数调用和返回，都会影响*env*。
帧（frame）
帧是键值对的集合，表示了符号与值的映射关系，我们称之为绑定（binding）。
(define (create-frame)
(make-hash))
(define (extend-frame frame key value)
(hash-set! frame key value))
具体实现中，我们使用了哈希表来存储键值对。
帧是可以被扩展的，extend-frame函数用新的键值对扩展了已有的帧。
环境的扩展
(define (extend-env env frame)
(cons frame env))
我们知道了，环境是帧的列表，环境还可以用新的帧来进行扩展。
这样环境中就可以包含很多个帧了，新的帧会放在列表头部。
求值
对一个符号进行求值，就是去环境中查找该符号所对应的值。
该符号与值的映射关系，可能体现在环境中的不同帧中，
我们取列表头部开始第一个映射关系。
即，我们认为后加入的帧，覆盖（shadow）了以前的绑定（binding）关系。
具体实现如下，我们递归的使用lookup-env进行查找。
(define (get-symbol-value env key)
(let lookup-env
((env env))
(if (null? env)
(error 'get-symbol-value "failed to find symbol")
(let ((head-frame (car env)))
(if (hash-has-key? head-frame key)
(hash-ref head-frame key '())
(lookup-env (cdr env)))))))
函数
函数是一个数据结构，
(struct function
(param body))
该结构的每个实例都表示一个具体的函数，
其中包含两个字段，param表示参数列表，body表示函数体。
当我们遇到函数定义表达式时，我们这样定义了一个函数（数据结构）。
(define (eval-lambda exp)
(display "eval-lambda\n")
(let ((param (caadr exp))
(body (caddr exp)))
(function param body)))
当我们求值一个函数调用表达式时，
（1）我们先把param和body字段提取出来
（2）创建一个新的帧，其中保存了形参到值的映射关系
（3）用新的帧扩展全局环境
（4）在全局环境中求值函数体
（5）函数返回后，恢复原来的环境
我们看到，这里有一个帧的添加和删除操作，
如果函数调用中还有另一个函数调用，就会在帧删除之前又添加一个帧。
实际上，这是一个入栈弹栈操作。
因此，我们说环境的具体实现形式是列表，但在数据结构上，它构成了一个栈。
帧在这种情况下，也成为栈帧（stack frame）。
(define (eval-function-call-list exp)
(display "eval-function-call-list\n")
(let* ((fn (eval-exp (car exp)))
(arg (eval-exp (cadr exp)))
(body (function-body fn))
(param (function-param fn))
(frame (create-frame)))
(extend-frame frame param arg)
(let* ((env *env*)
(value '()))
(set! *env* (extend-env *env* frame))
(set! value (eval-exp body))
(set! *env* env)
value)))
求值过程
现在我们对相关概念都进行了解释，我们来看看整个求值过程吧。
当我们遇到(eval-exp '1)时，会发现1是一个数字，我们断定为它是一个自求值表达式，直接返回它，因此(eval-exp '1)的值就是1了。
当我们遇到(eval-exp '(lambda (x) x))时，会发现这是一个函数定义表达式，我们拿到它所定义函数的参数列表param => (x)和函数体body => x，创建了一个结构——function，来存储它们。
当我们遇到(display (eval-exp '((lambda (x) x) 1)))，我们发现这是一个函数调用表达式（实际上，如果不是其他类型的表达式，我们都认为是函数调用），首先得到函数对象，然后再得到函数对象中保存的参数列表和函数体，在扩展中环境中求值函数体，因为这时环境中x => 1，所以body => x => 1，结果为1。
同理，我们可以分析其他的测试用例。
动态作用域
我们来看最后一个测试用例，
(eval-exp '((lambda (x)
((lambda (f)
((lambda (x)
(f 3))
2))
(lambda (z) x)))
1))
首先x => 1，然后f => (lambda (z) x)，
在f被调用(f 3)之前，我们覆盖了x的值，x => 2，
这时候，求值f的函数体，得到了(f 3) => 2。
我们看到f => (lambda (z) x)函数体中的x，
是在f被调用的环境中求值的，f在不同的位置被调用，x可能不同。
((lambda (x)
(f 3))
?)
我们可以给x任意的值。
这样有利有弊，
因为实现起来简单，很多古老的语言都是动态作用域的，
可是会带来上面所说的不确定性，类库的设计者无法预测所有被调用的场景，
很容易出现问题。
后来从Scheme开始，人们提出了词法作用域（静态作用域）的概念，
让f => (lambda (z) x)中的x始终等于f被定义处的x => 1，
这就避免了上述问题，当我们想确定x的值时，
只需要去f被定义的地方找一下，看看代码就行了。
（通过看看代码，分析文本，因此称为“词法的”。。
下文
本文我们实现了一个简单的具有动态作用域的Lisp方言，
下文，我们将在它的基础上进行修改，让它支持词法作用域，
我们会引入词法环境和闭包的概念，请拭目以待吧。。
参考
The Racket Reference
SICP : 4.1元循环求值器
An Introduction to Scheme and its Implementation
