澳门百家乐娱乐场
官网
Portraits
Journal
Contact
这里我们用一种最简单的数据结构,Scheme 的 association list,来表示环境。Association list 看起来像这个样子:((x . 1) (y . 2) (z . 5))。它是一个两元组(pair)的链表,左边的元素是 key,右边的元素是 value。写得直观一点就是:
((x . 1) (y . 2) (z . 5)) 查表操作就是从头到尾搜索,如果左边的 key 是要找的变量,就返回整个 pair。简单吧?效率很低,但是足够完成我们现在的任务。
ext-env 函数扩展一个环境。比如,如果原来的环境 env1 是 ((y . 2) (x . 1)) 那么 (ext-env x 3 env1),就会返回 ((x . 3) (y . 2) (x . 1))。也就是把 (x . 3) 加到 env1 的最前面去。
那我们什么时候需要扩展环境呢?当我们进行绑定的时候。绑定可能出现在函数调用时,也可能出现在 let 绑定时。我们选择的数据结构,使得环境自然而然的具有了作用域(scope)的特性。
环境其实是一个堆栈(stack)。内层的绑定,会出现在环境的最上面,这就是在“压栈”。这样我们查找变量的时候,会优先找到最内层定义的变量。
举个例子:
(let ([x 1]) ; env='()。绑定x到1。 (let ([y 2]) ; env='((x . 1))。绑定y到2。 (let ([x 3]) ; env='((y . 2) (x . 1))。绑定x到3。 (+ x y)))) ; env='((x . 3) (y . 2) (x . 1))。查找x,得到3;查找y,得到2。 ;; => 5 这段代码会返回5。这是因为最内层的绑定,把 (x . 3) 放到了环境的最前面,这样查找 x 的时候,我们首先看到 (x . 3),然后就返回值3。之前放进去的 (x . 1) 仍然存在,但是我们先看到了最上面的那个(x . 3),所以它被忽略了。
这并不等于说 (x . 1) 就可以被改写或者丢弃,因为它仍然是有用的。你只需要看一个稍微不同的例子,就知道这是怎么回事:
(let ([x 1]) ; env='()。绑定x到1。 (+ (let ([x 2]) ; env='((x . 1))。绑定x到2。 x) ; env='((x . 2) (x . 1))。查找x,得到2。 x)) ; env='((x . 1))。查找x,得到1。 ;; => 3 ; 两个不同的x的和,1+2等于3。 这个例子会返回3。它是第3行和第4行里面两个 x 的和。由于第3行的 x 处于内层 let 里面,那里的环境是 ((x . 2) (x . 1)),所以查找 x 的值得到2。第4行的 x 在内层 let 外面,但是在外层 let 里面,那里的环境是 ((x . 1)),所以查找 x 的值得到1。这很符合直觉,因为 x 总是找到最内层的定义。
值得注意的是,环境被扩展以后,形成了一个新的环境,而原来的环境并没有被改变。比如,上面的 ((y . 2) (x . 1)) 并没有删除或者修改,只不过是被“引用”到一个更大的列表里去了。
这样不对已有数据进行修改(mutation)的数据结构,叫做“函数式数据结构”。函数式数据结构只生成新的数据,而不改变或者删除老的。它可能引用老的结构,然而却不改变老的结构。这种“不修改”(immutable)的性质,在我们的解释器里是很重要的,因为当我们扩展一个环境,进入递归,返回之后,外层的代码必须仍然可以访问原来外层的环境。
当然,我们也可以用另外的,更高效的数据结构(比如平衡树,串接起来的哈希表)来表示环境。如果你学究一点,甚至可以用函数来表示环境。这里为了代码简单,我们选择了最笨,然而正确,容易理解的数据结构。
对变量的解释了解了变量,函数和环境,我们来看看解释器对变量的“取值”操作,也就是 match 的第一种情况。
[(? symbol? x) (lookup x env)]
这就是在环境中,沿着从内向外的“作用域顺序”,查找变量的值。
这里的 (? symbol? x) 是一种特殊的模式,它使用 Scheme 函数 symbol? 来判断输入是否是一个符号,如果是,就把它绑定到 x,然后你就可以在右边用 x 来指称这个输入。
对绑定的解释
官网
Portraits
Journal
Contact