在上一篇中，我们介绍了编译器和解释器，抽象语法树与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)))今天这篇文章中提到了很多“耳熟能详”的概念名词，下面通过代码来解释它们。
环境是帧（frame）的列表，其中“ ` ”是反引用（quasi-quotation），反引用是一种模板，便于构建列表。
`(,(create-frame)) <=> (list (create-frame))(create-frame)创建了一个帧，然后把它放到列表中，该列表目前只有一个元素。这个帧的列表就是环境。
我们这里定义了一个全局变量*env*，任何一个函数调用和返回，都会影响*env*。
帧是键值对的集合，表示了符号与值的映射关系，我们称之为绑定（binding）。
(define (create-frame) (make-hash)) (define (extend-frame frame key value) (hash-set! frame key value))具体实现中，我们使用了哈希表来存储键值对。帧是可以被扩展的，extend-frame函数用新的键值对扩展了已有的帧。
我们知道了，环境是帧的列表，环境还可以用新的帧来进行扩展。这样环境中就可以包含很多个帧了，新的帧会放在列表头部。
对一个符号进行求值，就是去环境中查找该符号所对应的值。该符号与值的映射关系，可能体现在环境中的不同帧中，我们取列表头部开始第一个映射关系。即，我们认为后加入的帧，覆盖（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 ReferenceSICP : 4.1元循环求值器An Introduction to Scheme and its Implementation
相关资源：js函数柯里化的方法和作用实例分析