柯里化的前生今世(五):动态作用域

  1. 云栖社区>
  2. 博客>
  3. 正文

柯里化的前生今世(五):动态作用域

何幻 2016-10-28 11:55:51 浏览1171
展开阅读全文

关于

在上一篇中,我们介绍了编译器和解释器,抽象语法树与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)我们先把parambody字段提取出来
(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

网友评论

登录后评论
0/500
评论
何幻
+ 关注