Apply：过程应用

apply

apply 接受两个实参：一个过程，以及该过程所要应用的实参表。它把过程分为两类：对原语过程，调用 apply-primitive-procedure 应用；对复合过程，则按顺序求值构成过程体的各个表达式。复合过程体的求值环境是这样构造的：把过程所携带的基础环境扩展，纳入一个新框架，其中把过程的形参与该过程被应用时的实参绑定。下面是 apply 的定义：

(define (apply procedure arguments)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure procedure arguments))
        ((compound-procedure? procedure)
         (eval-sequence
           (procedure-body procedure)
           (extend-environment
             (procedure-parameters procedure)
             arguments
             (procedure-environment procedure))))
        (else
         (error
          "Unknown procedure type -- APPLY" procedure))))

下面逐个讲解这个定义中用到的过程。

过程的表示

为了处理原语，我们假定已有以下过程可用：

• (apply-primitive-procedure proc args) 把给定的原语过程应用于表 args 中的各个实参值，返回应用的结果。

• (primitive-procedure? proc) 检验 proc 是否为原语过程。

复合过程用构造函数 make-procedure 从形参、过程体和环境构造：

(define (make-procedure parameters body env)
  (list 'procedure parameters body env))
(define (compound-procedure? p)
  (tagged-list? p 'procedure))
(define (procedure-parameters p) (cadr p))
(define (procedure-body p) (caddr p))
(define (procedure-environment p) (cadddr p))

原语过程

此刻，也许很长一段时间内，你可能会好奇原语过程在 Scheme 里是怎么表示的。其实原语过程的表示没有唯一正确的方式，只要 apply 能用 primitive-procedure? 和 apply-primitive-procedure 识别并应用它们即可。

Scheme 的创造者们决定把原语过程表示为一个表：以符号 primitive 开头，其中包含底层 Lisp 中实现该原语的过程。

(define (primitive-procedure? proc)
  (tagged-list? proc 'primitive))

(define (primitive-implementation proc) (cadr proc))

(define primitive-procedures
  (list (list 'car car)
        (list 'cdr cdr)
        (list 'cons cons)
        (list 'null? null?)
        <更多原语>
        ))

(define (primitive-procedure-names)
  (map car
       primitive-procedures))

(define (primitive-procedure-objects)
  (map (lambda (proc) (list 'primitive (cadr proc)))
       primitive-procedures))

应用原语过程时，我们只需用底层 Lisp 系统把实现过程应用于各个实参：

(define (apply-primitive-procedure proc args)
  (apply-in-underlying-scheme
   (primitive-implementation proc) args))

环境上的操作

当然，求值器需要操作环境的功能。再说一遍，什么是环境？它是框架的序列，每个框架是一张绑定表，把变量和对应的值关联起来。我们用以下操作来操作环境：

• (lookup-variable-value <var> <env>) 返回环境中与该符号绑定的值，如果变量未绑定则报错。

• (extend-environment <variables> <values> <base-env>) 返回一个新环境，它包含一个新框架，其中符号表中的各符号与值表中相应元素绑定，其外围环境为 <base-env>。

• (define-variable! <var> <value> <env>) 在环境的第一个框架中新增一个绑定，把该变量与该值关联。

• (set-variable-value! <var> <value> <env>) 改变环境中该变量的绑定，使该变量现在绑定到这个值；如果变量未绑定则报错。

为了实现这些操作，我们用框架的表来表示环境。某个环境的外围环境就是这个表的 cdr。空环境就是空表。

(define (enclosing-environment env) (cdr env))
(define (first-frame env) (car env))
(define the-empty-environment '())

环境的每个框架表示为一对表：一个表列出该框架中绑定的变量，另一个表列出相关联的值。

(define (make-frame variables values)
  (cons variables values))
(define (frame-variables frame) (car frame))
(define (frame-values frame) (cdr frame))
(define (add-binding-to-frame! var val frame)
  (set-car! frame (cons var (car frame)))
  (set-cdr! frame (cons val (cdr frame))))

要用一个新框架扩展环境，把变量与值关联起来：我们先构造一个由变量表和值表组成的框架，再把它拼接到环境前面。如果变量个数与值个数不匹配，我们报错。

(define (extend-environment vars vals base-env)
  (if (= (length vars) (length vals))
      (cons (make-frame vars vals) base-env)
      (if (< (length vars) (length vals))
          (error "Too many arguments supplied" vars vals)
          (error "Too few arguments supplied" vars vals))))

在环境中查找变量时，我们扫描第一个框架中的变量表。如果找到目标变量，就返回值表中相应的元素。如果在当前框架中没找到，就接着搜索外围环境，依此类推。如果搜到空环境仍未找到，就报「未绑定变量」错误。

(define (lookup-variable-value var env)
  (define (env-loop env)
    (define (scan vars vals)
      (cond ((null? vars)
             (env-loop (enclosing-environment env)))
            ((eq? var (car vars))
             (car vals))
            (else (scan (cdr vars) (cdr vals)))))
    (if (eq? env the-empty-environment)
        (error "Unbound variable" var)
        (let ((frame (first-frame env)))
          (scan (frame-variables frame)
                (frame-values frame)))))
  (env-loop env))

要在指定环境中把变量改为新值，我们像 lookup-variable-value 一样扫描查找该变量，找到后修改相应的值。

(define (set-variable-value! var val env)
  (define (env-loop env)
    (define (scan vars vals)
      (cond ((null? vars)
             (env-loop (enclosing-environment env)))
            ((eq? var (car vars))
             (set-car! vals val))
            (else (scan (cdr vars) (cdr vals)))))
    (if (eq? env the-empty-environment)
        (error "Unbound variable -- SET!" var)
        (let ((frame (first-frame env)))
          (scan (frame-variables frame)
                (frame-values frame)))))
  (env-loop env))

要定义变量，我们先在第一个框架中查找该变量的绑定，如果存在就修改这个绑定（和 set-variable-value! 一样）。如果不存在这样的绑定，就在第一个框架中新增一个。

(define (define-variable! var val env)
  (let ((frame (first-frame env)))
    (define (scan vars vals)
      (cond ((null? vars)
             (add-binding-to-frame! var val frame))
            ((eq? var (car vars))
             (set-car! vals val))
            (else (scan (cdr vars) (cdr vals)))))
    (scan (frame-variables frame)
          (frame-values frame))))

再访 apply

我们再看一遍 apply 的定义。这次明白了吗？

(define (apply procedure arguments)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure procedure arguments))
        ((compound-procedure? procedure)
         (eval-sequence
           (procedure-body procedure)
           (extend-environment
             (procedure-parameters procedure)
             arguments
             (procedure-environment procedure))))
        (else
         (error
          "Unknown procedure type -- APPLY" procedure))))

要点

在本小节中，你学到了：

1. apply 是如何定义的
2. 原语过程是如何定义和应用的
3. 环境操作是如何定义的

接下来？

我们将了解求值器是如何作为一个程序运行起来的。