sicp04-1

程序设计技术和方法 裘宗燕，2008-2009 /1 4. 元语言抽象(1) 本节讨论 „ 基本求值过程 „ 求值器的核心操作 eval 和 apply „ 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 达式数据抽象和接口操作 „ 求值器数据结构 „ 求值器的改进 „ 惰性求值的 Scheme 求值器 „ 流作为惰性表 程序设计技术和方法 裘宗燕，2008-2009 /2 程序设计和语言 „ 前面讨论各种程序设计技术，主要研究： ‰ 如何组合基本程序设计元素，构成具有更复杂功能的结构 ‰ 如何将复杂结构抽象为高层构件，以方便地用于进一步组合 ‰ 如何采用一些更高层次的观点和组织方式，提高系统的模块性 这些都是编程，这里一直用 Lisp (方言 Scheme) 作为编程语言 „ 问题变得更复杂，或需要解决某领域的大量问题，都可能发现所用语言 （Lisp 或其他语言）都不够令人满意，不够方便，希望有一种能更有 效地表述想法的新语言。没有现成的语言时，就需要自己创造 „ 建立新语言是重大工程决策，不应轻易去做。但另一方面，建立新语言 也是控制复杂性的最有力的工作策略 „ 本章研究建立新语言的技术，“元语言抽象”。人们常为特定领域的需要 创造新语言。针对问题 (领域) 专门设计的语言能大大提高在一定范围内 处理复杂情况的能力，提供最合用的原语、组合方式和抽象方式，以最 有效的方式去描述问题。程序员有时也应该去做语言设计师 程序设计技术和方法 裘宗燕，2008-2009 /3 程序设计和语言 „ 程序设计使用语言，工作中可能涉及多层次的多种语言。有的很简单， 如 C 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 库 printf 的排版语言；最复杂的是高级编程语言 „ 在编程领域，不仅可以根据需要设计语言，还能通过构造解释器的方式 实现新语言。一个语言的解释器就是一个过程，将其应用于该语言的一 个表达式，它会按该表达式的要求执行相应动作 „ 实现语言应是程序设计最本质的思想：求值器定义了语言里各种表达式 的意义，而它本身也就是一个程序 „ 任何比较复杂的程序都可能看作某语言的求值器（解释器）。如前面构 造的算术系统。前面的数字逻辑电路模拟器和约束传播系统是羽翼丰满 的语言，有其基本原语、组合手段和抽象手段 „ 本章研究如何在一个语言的基础上构造新语言。这里以 Lisp 为基础， 把各种求值器实现为 Lisp（Scheme）过程。Lisp 有强大的符号处理 能力，特别适合做这种工作 程序设计技术和方法 裘宗燕，2008-2009 /4 程序设计和语言 下面做的事情包括： „ 实现一个 Lisp 求值器。它包含 Lisp 的主要功能，足以求值本书的大部 分程序。该求值器有普遍意义，从某种意义看，各种编程语言处理器的 内部都包含一个类似的求值器 „ 实现一个正则序求值的 Lisp 求值器。由于求值器是个过程，改变求值 方式的工作量不大。采用正则序，用表就可以实现流的功能 „ 设计和实现一个非确定性计算语言，其中表达式可以有多个值，通过某 种搜索求出它们的值。这种语言里的计算进程就像能分叉，维护多重轨 迹的工作由求值器完成 „ 实现一个逻辑程序设计语言，使人可以用关系的形式表达与与计算相关 知识，而不是按函数观点写出计算过程。这个语言与 Lisp 大相径庭， 但其求值器仍然能享用 Lisp 求值器的结构 程序设计技术和方法 裘宗燕，2008-2009 /5 元循环求值器 „ 用 Lisp 做 Lisp 求值器，让它在 Lisp 里运行，像是循环定义。可行， 求值就是一种计算过程，可用任何足够强的语言实现，包括用 Lisp „ 用一种语言实现其自身求值器，称为元循环。这个元循环求值器本质上 就是前面 Scheme 求值模型的一个实现，该模型： ‰ 求值组合式（非特殊形式）时，先求值其子表达式，而后把运算符 子表达式的值作用于运算对象子表达式的值 ‰ 复合过程应用于一集实参就是在一个新环境里求值过程体。新环境 是过程的环境加一个新框架，其中是所有形参与对应实参值的约束 „ 两步都可能递归应用。直到遇到 ‰ 符号(直接到环境里取值) ‰ 基本过程 (直接调用代码) ‰ 本身就是值的表达式（如数） „ 求值由求值器里的两个关键过程 eval 和 apply 实现，相互关系见图 程序设计技术和方法 裘宗燕，2008-2009 /6 元循环求值器 „ 求值器实现依赖于一些处理被求值表达式的语法过程。下面采用数据抽 象技术，使求值器独立于语言的具体表示。如 ‰ assignment? 检查是否赋值表达式，而不直接判断是否 set! ‰ assignment-variable 和 assignment-value 取其中部分 „ 还有一些与过程和环境有关的抽象接口过程，如 ‰ make-procedure 构造复合过程 ‰ lookup-variable-value 取变量的值 ‰ apply-primitive-procedure 应用基本过程 „ 元循环求值器的核心是过程 eval 和 apply „ 这两个基本过程都需要处理多种情况，这里将始终采用数据抽象技术， 通过抽象谓词判断表达式等的类型，使两个核心过程的实现独立于表达 式的具体语法形式 程序设计技术和方法 裘宗燕，2008-2009 /7 核心过程 eval eval 以一个表达式和一个环境为参数，分情况求值各种表达式 „ 基本表达式： ‰ 各种自求值表达式（如数）：直接将其返回 ‰ 变量：从环境中找出当前值 „ 特殊形式： ‰ 引号表达式：返回被引表达式 ‰ 变量赋值或定义：修改环境，建立或修改相应约束 ‰ if 表达式：求值条件部分，而后根据情况求值相应子表达式 ‰ lambda 表达式：建立过程对象，包装过程的参数表、体、和环境 ‰ begin 表达式：按顺序求值其中的各个表达式 ‰ cond 表达式：将其变换为一系列 if 而后求值 „ 组合式（过程应用）：递归求值各个子表达式，而后将得到的过程和实 际参数值送给 apply，要求执行过程的应用 程序设计技术和方法 裘宗燕，2008-2009 /8 核心过程 eval (define (eval exp env) (cond ((self-evaluating? exp) exp) ((variable? exp) (lookup-variable-value exp env)) ((quoted? exp) (text-of-quotation exp)) ((assignment? exp) (eval-assignment exp env)) ((definition? exp) (eval-definition exp env)) ((if? exp) (eval-if exp env)) ((lambda? exp) (make-procedure (lambda-parameters exp) (lambda-body exp) env)) ((begin? exp) (eval-sequence (begin-actions exp) env)) ((cond? exp) (eval (cond->if exp) env)) ((application? exp) (apply (eval (operator exp) env) (list-of-values (operands exp) env))) (else (error "Unknown expression type -- EVAL" exp)))) 这里采用分情况 处理的实现方式 完全可用数据导 向的编程方式， 使增加表达式类 型更为方便 许多实际系统采 用后一实现方式 程序设计技术和方法 裘宗燕，2008-2009 /9 核心过程 apply „ apply 以一个过程和一个实参表为参数，实现过程的应用。两种情况： ‰ 基本过程：用 apply-primitive-procedure 直接处理 ‰ 复合过程：建立新求值环境（用形参和实参表建立一个框架），而 后在新环境里顺序求值过程体里的表达式（允许多个表达式） (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)))) 程序设计技术和方法 裘宗燕，2008-2009 /10 过程参数，if 表达式 „ 对过程调用，eval需要求值各实际参数表达式，得到实参表： (define (list-of-values exps env) (if (no-operands? exps) '() (cons (eval (first-operand exps) env) (list-of-values (rest-operands exps) env)))) 也可用 map。这里想说明求值器可以用没有高阶过程的语言里实现 „ eval-if 求值条件表达式： (define (eval-if exp env) (if (true? (eval (if-predicate exp) env)) (eval (if-consequent exp) env) (eval (if-alternative exp) env))) 用 true? 把 eval 条件表达式的结果翻译到实现语言 (Scheme) 的逻 辑值。这样，元循环求值器里的逻辑值可以用任何表示形式，可以不 同于 Scheme 的逻辑值表示 程序设计技术和方法 裘宗燕，2008-2009 /11 赋值和定义，序列 „ 赋值和定义的实现方法类似，修改环境的工作留给下层过程： (define (eval-assignment exp env) (set-variable-value! (assignment-variable exp) (eval (assignment-value exp) env) env) 'ok) (define (eval-definition exp env) (define-variable! (definition-variable exp) (eval (definition-value exp) env) env) 'ok) „ apply 求值过程体的表达式序列，就是在同一环境里逐个求值它们： (define (eval-sequence exps env) (cond ((last-exp? exps) (eval (first-exp exps) env)) (else (eval (first-exp exps) env) (eval-sequence (rest-exps exps) env)))) 程序设计技术和方法 裘宗燕，2008-2009 /12 表达式表示 „ 符号表达式（Lisp 程序）具有递归结构，求值器根据表达式的类型确 定操作。把表达式看作数据抽象（类似求微分程序），可松弛操作规则 和表达式具体形式之间的联系。下面实现各种表达式的语法过程 „ 自求值表达式。只需要一个谓词，数和字符串属于此类： (define (self-evaluating? exp) (cond ((number? exp) true) ((string? exp) true) (else false))) „ 变量。直接用符号表示，只需要一个谓词 (define (variable? exp) (symbol? exp)) „ 区分各种表达式需要判断类型标志，需要下面过程 (define (tagged-list? exp tag) (if (pair? exp) (eq? (car exp) tag) false)) 程序设计技术和方法 裘宗燕，2008-2009 /13 表达式表示： quote，赋值 „ 表达式形式 (quote )，相应语法过程和谓词: (define (quoted? exp) (tagged-list? exp 'quote)) (define (text-of-quotation exp) (cadr exp)) „ 表达式形式 (set! )，语法过程: (define (assignment? exp) (tagged-list? exp 'set!)) (define (assignment-variable exp) (cadr exp)) (define (assignment-value exp) (caddr exp)) 程序设计技术和方法 裘宗燕，2008-2009 /14 表达式表示：定义 „ 定义有两种形式：(define ) 和 (define ( ... ) ) 后一形式是下面形式的语法包装： (define (lambda ( ... ) )) 语法过程： (define (definition? exp) (tagged-list? exp 'define)) (define (definition-variable exp) (if (symbol? (cadr exp)) (cadr exp) (caadr exp))) (define (definition-value exp) (if (symbol? (cadr exp)) (caddr exp) (make-lambda (cdadr exp) ; formal parameters (cddr exp)))) ; body 程序设计技术和方法 裘宗燕，2008-2009 /15 表达式表示：lambda，if „ lambda 表达式是表，以 lambda 为第一个元素： (define (lambda? exp) (tagged-list? exp 'lambda)) (define (lambda-parameters exp) (cadr exp)) (define (lambda-body exp) (cddr exp)) 构造函数（实现 define 需要）： (define (make-lambda parameters body) (cons 'lambda (cons parameters body))) „ if 表达式的语法过程： (define (if? exp) (tagged-list? exp 'if)) (define (if-predicate exp) (cadr exp)) (define (if-consequent exp) (caddr exp)) (define (if-alternative exp) (if (not (null? (cdddr exp))) (cadddr exp) 'false)) if 表达式的构造函数（实现 cond时要用） (define (make-if predicate consequent alternative) (list 'if predicate consequent alternative)) 程序设计技术和方法 裘宗燕，2008-2009 /16 表达式表示：begin „ begin 包装一系列表达式，要求对它们顺序求值： (define (begin? exp) (tagged-list? exp 'begin)) (define (begin-actions exp) (cdr exp)) (define (last-exp? seq) (null? (cdr seq))) (define (first-exp seq) (car seq)) (define (rest-exps seq) (cdr seq)) 需要构造函数 sequence->exp (用于 cond->if)，它把多个表达式的 序列包装为一个 begin 表达式： (define (sequence->exp seq) (cond ((null? seq) seq) ((last-exp? seq) (first-exp seq)) (else (make-begin seq)))) (define (make-begin seq) (cons 'begin seq)) 程序设计技术和方法 裘宗燕，2008-2009 /17 表达式表示：过程应用 „ 另一些语法过程： (define (application? exp) (pair? exp)) (define (operator exp) (car exp)) (define (operands exp) (cdr exp)) (define (no-operands? ops) (null? ops)) (define (first-operand ops) (car ops)) (define (rest-operands ops) (cdr ops)) „ 至此基本表达式的语法过程定义完了 „ 语言里还定义了一些派生表达式类型，包括 cond 等。下面考虑它们， 实际上是把它们翻译为基本表达式 程序设计技术和方法 裘宗燕，2008-2009 /18 派生表达式：cond „ cond 总可以用嵌套的 if 表达式实现。对 cond 的求值变换为 if (define (cond? exp) (tagged-list? exp 'cond)) (define (cond-clauses exp) (cdr exp)) (define (cond-else-clause? clause) (eq? (cond-predicate clause) 'else)) (define (cond-predicate clause) (car clause)) (define (cond-actions clause) (cdr clause)) (define (cond->if exp) (expand-clauses (cond-clauses exp))) (define (expand-clauses clauses) (if (null? clauses) 'false ; no else clause (let ((first (car clauses)) (rest (cdr clauses))) (if (cond-else-clause? first) (if (null? rest) (sequence->exp (cond-actions first)) (error "ELSE clause isn't last -- COND->IF" clauses)) (make-if (cond-predicate first) (sequence->exp (cond-actions first)) (expand-clauses rest)))))) 还可以定义其他的 派生表达式 本小节的练习中提 出了许多问题 程序设计技术和方法 裘宗燕，2008-2009 /19 求值器数据结构：谓词和过程 „ 为完成表达式处理，求值器还需定义好过程和环境的表示形式，逻辑值 等的表示方式，这些属于求值器的内部数据结构 „ 谓词检测。把所有非 false 对象作为逻辑真 (define (true? x) (not (eq? x false))) (define (false? x) (eq? x false)) „ 设 (apply-primitive-procedure ) 处理基本过程应用， (primitive-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)) 程序设计技术和方法 裘宗燕，2008-2009 /20 求值器数据结构：环境操作 „ 求值需要环境，环境需要实现 „ 环境是框架的序列，每个框架是一个表格，其中的项就是变量与值的约 束。将环境看着数据抽象，提供下面操作： ‰ (lookup-variable-value ) 取得符号 在环境 里的约束值，没有约束时报错 ‰ (extend-environment ) 返回 所构造的新环境，其第一个框架里包含 与 的关联，外围环境是 ‰ (define-variable! ) 在环境 的第一个 框架里加入 与 的关联 ‰ (set-variable-value! ) 修改环境 里变 量 的约束，使其关联值变成 。找不到 的约 束时报错 „ 在此基础上，考虑实现环境的数据结构 程序设计技术和方法 裘宗燕，2008-2009 /21 求值器数据结构：框架 „ 环境用框架的表表示，其 cdr 是外围环境 (define (enclosing-environment env) (cdr env)) (define (first-frame env) (car env)) (define the-empty-environment '()) „ 框架是表的序对，其 car 是变量表，cdr 是关联值表 (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)))) 程序设计技术和方法 裘宗燕，2008-2009 /22 求值器数据结构：变量检索 „ 变量取值：顺序检查环境中的框架，找到第一个出现时返回值表中与变 量对应的元素。遇到空环境时报错 (define (lookup-variable-value var env0) (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 env0)) 程序设计技术和方法 裘宗燕，2008-2009 /23 求值器数据结构：变量赋值 „ 变量赋值。修改环境中变量第一个出现的关联值。找不到变量时报错： (define (set-variable-value! var val env0) (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 env0)) 程序设计技术和方法 裘宗燕，2008-2009 /24 求值器数据结构：变量定义 „ 定义变量。在第一个框架里加入该变量与值的关联。如果存在该变量的 约束时修改与之关联的值 (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)))) „ 同样功能可用不同方法实现，采用不同数据结构和算法。上面是一种朴 素的简单实现，许多问题没有慎重考虑，特别是效率 ‰ 程序执行中频繁检索变量（求值/赋值/定义等），检索效率很关键 ‰ 在框架里顺序比较，在框架序列中顺序检索的效率太低。实际求值 器在这方面需要采用精心设计的结构和技术 程序设计技术和方法 裘宗燕，2008-2009 /25 求值器的运行 „ 这个求值器给出了一个严格描述的 Lisp 求值模型（本身用 Lisp ）。用 程序描述的求值器可运行，可以借助它去理解语言；还可以改造它去试 验不同求值规则。下面考虑这些方面的问题 „ 表达式求值最终归结到基本过程调用。运行求值器前要解决调用基本 Lisp 功能的问题。每个基本过程要有一个约束，使 eval 求值中能找到 相应对象并把它传给 apply。为此需要创建一个初始环境，其中为每个 基本过程名建立对象关联，还需包含 true 和 false 等的约束 „ 创建初始环境： (define (setup-environment) (let ((initial-env (extend-environment (primitive-procedure-names) (primitive-procedure-objects) the-empty-environment))) (define-variable! 'true true initial-env) (define-variable! 'false false initial-env) initial-env)) (define the-global-environment (setup-environment)) 程序设计技术和方法 裘宗燕，2008-2009 /26 求值器的运行 „ 基本过程的表示形式不重要，但 apply 必须能识别它们，并能借助相应 过程去应用它们。这里的设计是让它们都以符号 primitive 开头 (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)) 程序设计技术和方法 裘宗燕，2008-2009 /27 求值器的运行 „ 应用基本过程时可以直接用基础 Lisp 系统将这种过程应用于参数 (define (apply-primitive-procedure proc args) (apply-in-underlying-scheme (primitive-implementation proc) args)) „ 注意：这里的 apply-in-underlying-scheme 也就是 Scheme 系统的 apply。由于上面定义的元循环求值器重新定义了 apply，从而掩盖了 系统原来的定义，应该在定义之前为原来的 apply 定义另一个引用 (define apply-in-underlying-scheme apply) 这样，上面过程 apply-primitive-procedure 就可以调用基础系统里 的 apply 基本过程了 程序设计技术和方法 裘宗燕，2008-2009 /28 求值器的运行 „ 为方便元循环求值器的使用，可仿照 Scheme 系统，定义一个基本循 环，输出提示符后读入-求值-打印。输出前加一个特殊标志： (define input-prompt ";;; M-Eval input:") (define output-prompt ";;; M-Eval value:") (define (driver-loop) (prompt-for-input input-prompt) (let ((input (read))) (let ((output (eval input the-global-environment))) (announce-output output-prompt) (user-print output))) (driver-loop)) (define (prompt-for-input string) (newline) (newline) (display string) (newline)) (define (announce-output string) (newline) (display string) (newline)) 程序设计技术和方法 裘宗燕，2008-2009 /29 求值器的运行 „ 定义 user-print 过程是为了避免打印复合过程的环境，因为这种环境可 能有复杂的结构，而且可能包含循环结构 (define (user-print object) (if (compound-procedure? object) (display (list 'compound-procedure (procedure-parameters object) (procedure-body object) ')) (display object))) 程序设计技术和方法 裘宗燕，2008-2009 /30 运行实例 „ 一段运行实例： (define the-global-environment (setup-environment)) (driver-loop) ;;; M-Eval input: (define (append x y) (if (null? x) y (cons (car x) (append (cdr x) y)))) ;;; M-Eval value: ok ;;; M-Eval input: (append '(a b c) '(d e f)) ;;; M-Eval value: (a b c d e f) 程序设计技术和方法 裘宗燕，2008-2009 /31 以数据作为程序 „ 考虑用 Lisp 程序求值 Lisp 表 达式的问题 „ 按操作的观点，一个程序可看作 是一部（可能为无穷大的）抽象 机器的一个描述。例如： (define (factorial n) (if (= n 1) 1 (* (factorial (- n 1)) n))) 阶乘机器是一部递归机器，由一些基本部 件和开关等构成 按同样看法，求值器是一部特殊机器。对 于给定输入（一部机器的描述），它能模 拟该输入所描述的那部机器的行为 求值器的功能是“表演”任意机器的行为方 式，它是“万能表演机器” 程序设计技术和方法 裘宗燕，2008-2009 /32 以数据作为程序 „ 按这个观点，求值器就是一部通用机器，它能模拟任何用 Lisp 程序描 述的机器的行为。第一个清晰地提出这一思想的人是图灵 „ 想想：有没有可能在其他领域中实现这种具有通用功能的事物？例如： 电子线路？汽车？机床？催化剂？书？药？有可能吗？ „ 最惊人的事实：求值器完全可以模拟它自身！(当然要付出效率的代价) ■ 求值器是联系数据对象和编程语言的桥梁。求值器运行中，人输入的 表达式是被求值的程序，求值器将它当作数据（一个表），按特定规则 去操作这个表 ■ 以用户程序作为求值器处理的数据，不仅未必带来混乱，还可能带来一 些方便。Lisp 系统通常都提供基本函数 eval，允许直接调用其求值器 (eval '(* 5 5) user-initial-environment) (eval (cons '* (list 5 5)) user-initial-environment) 都会返回 25。eval 使人可以在运行中构造程序然后去求值它们 程序设计技术和方法 裘宗燕，2008-2009 /33 内部定义 „ 元循环求值器顺序执行送来的定义，把定义加入环境框架。这符合交互 式开发的需要，因为程序员的定义和使用工作常常交替进行 „ 但这种方式可能不是处理块结构的内部定义的最好方式。例如 (define (f x) (define (even? n) (if (= n 0) true (odd? (- n 1)))) (define (odd? n) (if (= n 0) false (even? (- n 1)))) ) even? 体里的 odd? 要用随后定义的过程，而此时它未定义。可见 odd? 的作用域应该是整个 f 的体，而不是定义之后的那部分。块结 构里的所有定义应同时加入环境，应有相同作用域 程序设计技术和方法 裘宗燕，2008-2009 /34 内部定义 „ 前面求值器“恰好”能正确处理，是因为它处理了所有定义后才真使用它 们。只要所有内部定义都出现在体和使用所定义变量的任何表达式的求 值之前，顺序定义和同时定义总产生同样效果（练习4.19） „ 可以修改定义使所有内部定义具有同样作用域。为此可以用 lambda 表 达式变换，把内部定义都取出来放入一个 let 表达式。例如： (lambda (define u ) (define v ) ) (lambda (let ((u '*unassigned*) (v '*unassigned*)) (set! u ) (set! v ) )) 变换为： ■ 存在具有同样效果的其他变换。参看练习4.18 ■ 本小节的练习讨论了许多与定义有关的语义问题，以及一些其他问题。 请大家自己看一看 程序设计技术和方法 裘宗燕，2008-2009 /35 分离语法分析和执行 „ 前面求值器很简单，但效率很低。特别是表达式的语法分析和执行交织 在一起，如果一个表达式执行多次，就会对它做多次语法分析。例： (define (factorial n) (if (= n 1) 1 (* (factorial (- n 1)) n))) 求 (factorial 4) 时，每次调用都要确定过程体是否为 if，而后提取谓 词部分并基于其值继续求值，等等。求值子表达式时 eval又要做分情 况处理。这种分析的代价很高，重复做完全是浪费 „ 修改求值器提高效率的一种方式：重新安排处理过程，使表达式分析的 工作只做一次。具体做法是把 eval 的工作分为两部分： ‰ 过程 analyze 对被求值表达式进行语法分析，返回一个执行过程， 将分析结果封装在其中 ‰ 执行过程以环境为参数完成实际执行，产生表达式求值的效果。这 样就可以只做一次分析，而后可以多次执行 程序设计技术和方法 裘宗燕，2008-2009 /36 分离语法分析和执行 „ 分析和执行分离后，eval 变成了： (define (eval exp env) ((analyze exp) env)) „ 过程 analyze 像 eval 一样做分情况分析，但不进行完全的求值，而是 构造出一个可直接执行的程序（具体构造通过调用子程序完成）： (define (analyze exp) (cond ((self-evaluating? exp) (analyze-self-evaluating exp)) ((quoted? exp) (analyze-quoted exp)) ((variable? exp) (analyze-variable exp)) ((assignment? exp) (analyze-assignment exp)) ((definition? exp) (analyze-definition exp)) ((if? exp) (analyze-if exp)) ((lambda? exp) (analyze-lambda exp)) ((begin? exp) (analyze-sequence (begin-actions exp))) ((cond? exp) (analyze (cond->if exp))) ((application? exp) (analyze-application exp)) (else (error "Unknown expression type -- ANALYZE" exp)))) 程序设计技术和方法 裘宗燕，2008-2009 /37 分离语法分析和执行 „ 生成自求值表达式对应的过程 (define (analyze-self-evaluating exp) (lambda (env) exp)) „ 对引号表达式，可在分析时直接求出被引表达式，不必每次求值时做： (define (analyze-quoted exp) (let ((qval (text-of-quotation exp))) (lambda (env) qval))) „ 取变量值，还是要在执行时到环境里查找： (define (analyze-variable exp) (lambda (env) (lookup-variable-value exp env))) 程序设计技术和方法 裘宗燕，2008-2009 /38 分离语法分析和执行 „ 赋值和定义都需要到求值时做，去设置变量（需要环境）。但先完成了 被赋值表达式的分析，可以大大提高执行时的效率： (define (analyze-assignment exp) (let ((var (assignment-variable exp)) (vproc (analyze (assignment-value exp)))) (lambda (env) (set-variable-value! var (vproc env) env) 'ok))) (define (analyze-definition exp) (let ((var (definition-variable exp)) (vproc (analyze (definition-value exp)))) (lambda (env) (define-variable! var (vproc env) env) 'ok))) 程序设计技术和方法 裘宗燕，2008-2009 /39 分离语法分析和执行 „ if 表达式，分析中提取谓词和两个分支表达式 (define (analyze-if exp) (let ((pproc (analyze (if-predicate exp))) (cproc (analyze (if-consequent exp))) (aproc (analyze (if-alternative exp)))) (lambda (env) (if (true? (pproc env)) (cproc env) (aproc env))))) „ lambda 表达式，体的分析只做一次，多次执行可能大大提高效率 (define (analyze-lambda exp) (let ((vars (lambda-parameters exp)) (bproc (analyze-sequence (lambda-body exp)))) (lambda (env) (make-procedure vars bproc env)))) make-procedure 继续使用前面的定义 程序设计技术和方法 裘宗燕，2008-2009 /40 分离语法分析和执行 „ 对表达式序列（begin 表达式或 lambda 体）需要深入分析。其中每个 表达式产生一个执行过程，把它们组合起来做成一个执行过程 (define (analyze-sequence exps) (define (sequentially proc1 proc2) (lambda (env) (proc1 env) (proc2 env))) (define (loop first-proc rest-procs) (if (null? rest-procs) first-proc (loop (sequentially first-proc (car rest-procs)) (cdr rest-procs)))) (let ((procs (map analyze exps))) (if (null? procs) (error "Empty sequence -- ANALYZE")) (loop (car procs) (cdr procs)))) 分析各子表达式 把前两个子表达式的 执行过程组合起来 „ 过程应用的分析最复杂，需要分析其中的运算符和运算对象，每个生成 一个执行过程，而后把它们送给 execute-application 过程（与 apply 对应），要求它去执行 程序设计技术和方法 裘宗燕，2008-2009 /41 分离语法分析和执行 „ 过程应用的分析 (define (analyze-application exp) (let ((fproc (analyze (operator exp))) (aprocs (map analyze (operands exp)))) (lambda (env) (execute-application (fproc env) (map (lambda (aproc) (aproc env)) aprocs))))) (define (execute-application proc args) (cond ((primitive-procedure? proc) (apply-primitive-procedure proc args)) ((compound-procedure? proc) ((procedure-body proc) (extend-environment (procedure-parameters proc) args (procedure-environment proc)))) (else (error "Unknown proc type -- EXEC-APPLICATION" proc)))) 分析各运算对象 执行各运算对象的执行 过程，得到实参值表 完成过程应用 程序设计技术和方法 裘宗燕，2008-2009 /42 Scheme 的变形：惰性求值 „ 有了求值器之后，可以修改它，试验一些语言设计的选择和变化 „ 要开发一个新语言，通常 ‰ 用现有语言实现新语言的求值器，而后研究各种设计想法的价值， 研究各种可能的语言设计选择 ‰ 将设计选择实现在求值器里，提供给相关人员使用和 评价 LEC评价法下载LEC评价法下载评价量规免费下载学院评价表文档下载学院评价表文档下载 ，而后再 根据评价结果修改求值器，并进一步送出评价 ‰ 在高的层次上实现求值器，更容易实现、测试和修改。因为可以从 基础语言借用大量功能 ‰ 到新语言已经比较成