第五章计算模型

导读

在前四章中，我们使用 Scheme 语言编写程序，并通过构建解释器来理解编程语言的本质。然而，这些程序最终需要在物理机器上执行。物理机器是如何执行程序的？程序的高级抽象如何映射到机器的低级操作？计算的物理极限是什么？

第五章"计算模型"将回答这些问题。在这一章中，我们将构建寄存器机器（register machine）模型，这是一种抽象的计算设备，由寄存器、操作器和控制器组成。我们将学习如何用寄存器机器来模拟 Scheme 解释器，理解计算过程的物理实现。我们还将构建编译器，将高级语言程序翻译为机器指令，提高执行效率。

本章的学习目标包括：

理解寄存器机器的结构和操作
学会用寄存器机器描述计算过程
掌握机器模型的求值过程
理解编译器的基本结构和优化技术
掌握垃圾回收的原理和实现
了解计算的物理极限和复杂性

核心概念详解

5.1 寄存器机器的基本结构

寄存器机器（register machine）是一种抽象计算设备，由以下部分组成：

寄存器（registers）：存储数据的容器，每个寄存器有一个名称

操作器（operations）：对数据执行操作的装置

控制器（controller）：按顺序执行指令的装置

栈（stack）：用于保存和恢复寄存器值的临时存储

寄存器机器的状态由寄存器的值和控制器的位置决定。每一步执行，控制器读取一条指令，执行相应的操作，然后移动到下一条指令。

scheme

; 一个简单的寄存器机器，计算两个数的最大公约数
(define gcd-machine
  (make-machine
   '(a b t)  ; 寄存器
   (list (list 'rem remainder) (list '< <))  ; 操作
   '(test-b
     (test (op <) (reg b) (const 0))
     (branch (label gcd-done))
     (assign t (op rem) (reg a) (reg b))
     (assign a (reg b))
     (assign b (reg t))
     (goto (label test-b))
     gcd-done)))

这个机器有三个寄存器 a、b、t，两个操作 rem（求余）和 <（小于比较），控制器是一系列指令。

5.2 寄存器机器语言

寄存器机器语言是一组低级指令，包括：

assign：将值赋给寄存器

(assign <reg> (op <operation>) <operand1> <operand2> ...)
(assign <reg> (reg <reg2>))
(assign <reg> (const <value>))
(assign <reg> (label <label>))

test：测试条件

(test (op <operation>) <operand1> <operand2> ...)

branch：条件分支

(branch (label <label>))

goto：无条件跳转

(goto (label <label>))
(goto (reg <reg>))

save/restore：栈操作

(save <reg>)
(restore <reg>)

perform：执行操作（不保存结果）

(perform (op <operation>) <operand1> <operand2> ...)

这些指令构成了寄存器机器的指令集。通过组合这些指令，可以描述任何计算过程。

5.3 寄存器机器模拟器

为了执行寄存器机器程序，我们需要一个模拟器。模拟器是一个 Scheme 程序，它解释执行寄存器机器指令。

scheme

(define (make-machine register-names ops controller-text)
  (let ((machine (make-new-machine)))
    (for-each (lambda (register-name)
                ((machine 'install-register) register-name))
              register-names)
    ((machine 'install-operations) ops)
    ((machine 'install-instruction-sequence)
     (assemble controller-text machine))
    machine))

(define (make-new-machine)
  (let ((pc (make-register 'pc))
        (flag (make-register 'flag))
        (stack (make-stack))
        (the-instructions '()))
    (let ((register-table
           (list (list 'pc pc) (list 'flag flag))))
      (define (allocate-register name)
        (if (assoc name register-table)
            (error "Multiply defined register: " name)
            (set! register-table
                  (cons (list name (make-register name))
                        register-table)))
        'register-allocated)
      (define (lookup-register name)
        (let ((val (assoc name register-table)))
          (if val
              (cadr val)
              (error "Unknown register:" name))))
      (define (execute)
        (let ((insts (get-contents pc)))
          (if (null? insts)
              'done
              (begin
                ((instruction-execution-proc (car insts)))
                (execute)))))
      (define (dispatch message)
        (cond ((eq? message 'start)
               (set-contents pc the-instructions)
               (execute))
              ((eq? message 'install-instruction-sequence)
               (lambda (seq) (set! the-instructions seq)))
              ...))
      dispatch)))

模拟器包含一个执行循环，不断从程序计数器（pc）读取指令并执行。每条指令的执行可能修改寄存器的值、栈的内容或程序计数器的值。

5.4 从高级语言到寄存器机器

将 Scheme 程序转换为寄存器机器程序需要两个步骤：

语法分析：将 Scheme 表达式解析为抽象语法树

代码生成：将抽象语法树转换为寄存器机器指令

例如，Scheme 表达式 (+ 1 2) 可以转换为：

; 语法分析
(application
  (operator +)
  (operands (1 2)))

; 代码生成
(assign proc (op lookup-variable-value) (const +) (reg env))
(assign argl (op list) (const 2))
(assign argl (op cons) (const 1) (reg argl))
(assign val (op apply) (reg proc) (reg argl))

这个过程与编译器的前端类似。实际上，我们可以构建一个编译器，直接将 Scheme 程序编译为寄存器机器指令。

5.5 显式控制求值器

显式控制求值器（explicit-control evaluator）是一个用寄存器机器语言编写的 Scheme 解释器。它是第四章元循环求值器的机器级实现。

scheme

; 求值循环
eval-dispatch
  (test (op self-evaluating?) (reg exp))
  (branch (label ev-self-eval))
  (test (op variable?) (reg exp))
  (branch (label ev-variable))
  (test (op quoted?) (reg exp))
  (branch (label ev-quoted))
  (test (op assignment?) (reg exp))
  (branch (label ev-assignment))
  (test (op definition?) (reg exp))
  (branch (label ev-definition))
  (test (op if?) (reg exp))
  (branch (label ev-if))
  (test (op lambda?) (reg exp))
  (branch (label ev-lambda))
  (test (op begin?) (reg exp))
  (branch (label ev-begin))
  (test (op application?) (reg exp))
  (branch (label ev-application))
  (goto (label unknown-expression-type))

显式控制求值器使用寄存器存储表达式、环境、过程和参数列表。它通过跳转和分支实现控制流，通过栈保存和恢复寄存器值。

5.6 编译器的基本结构

编译器将高级语言程序翻译为低级机器指令。一个基本的编译器包含以下组件：

词法分析器（lexer）：将源代码分解为词法单元（token）

语法分析器（parser）：将词法单元组织为抽象语法树

语义分析器（semantic analyzer）：检查语义正确性

代码生成器（code generator）：将抽象语法树转换为目标代码

优化器（optimizer）：优化目标代码

scheme

; 简单的编译器框架
(define (compile exp target linkage)
  (cond ((self-evaluating? exp)
         (compile-self-evaluating exp target linkage))
        ((quoted? exp)
         (compile-quoted exp target linkage))
        ((variable? exp)
         (compile-variable exp target linkage))
        ((assignment? exp)
         (compile-assignment exp target linkage))
        ((definition? exp)
         (compile-definition exp target linkage))
        ((if? exp)
         (compile-if exp target linkage))
        ((lambda? exp)
         (compile-lambda exp target linkage))
        ((begin? exp)
         (compile-begin (begin-actions exp) target linkage))
        ((cond? exp)
         (compile (cond->if exp) target linkage))
        ((application? exp)
         (compile-application exp target linkage))
        (else (error "Unknown expression type -- COMPILE" exp))))

compile 过程根据表达式类型分派到相应的编译过程。每个编译过程生成目标代码指令序列。

5.7 链接约定

编译过程需要处理链接（linkage）问题：编译后的代码如何跳转到下一条指令？

有三种链接方式：

return：返回到调用者（用于过程体）

next：继续执行下一条指令（用于序列）

标签：跳转到指定标签（用于分支）

scheme

(define (compile-linkage linkage)
  (if (eq? linkage 'return)
      (make-instruction-sequence '(continue) '()
       '((goto (reg continue))))
      (make-instruction-sequence '() '()
       `((goto (label ,linkage))))))

(define (end-with-linkage linkage instruction-sequence)
  (preserving '(continue)
   instruction-sequence
   (compile-linkage linkage)))

5.8 寄存器保存与恢复

在编译过程调用时，需要保存和恢复寄存器的值，避免被覆盖：

scheme

(define (preserving regs seq1 seq2)
  (if (null? regs)
      (append-instruction-sequences seq1 seq2)
      (let ((first-reg (car regs)))
        (if (and (needs-reg? seq2 first-reg)
                 (modifies-reg? seq1 first-reg))
            (preserving (cdr regs)
             (make-instruction-sequence
              (list-union (list first-reg)
                          (registers-needed seq1))
              (list-difference (registers-modified seq1)
                               (list first-reg))
              (append `((save ,first-reg))
                      (statements seq1)
                      `((restore ,first-reg))))
             seq2)
            (preserving (cdr regs) seq1 seq2)))))

preserving 检查第二个序列是否需要某个寄存器，而第一个序列是否修改了该寄存器。如果是，则在第一个序列前后添加 save/restore 指令。

5.9 垃圾回收

在寄存器机器中，内存管理是一个重要问题。当对象不再被引用时，应该回收其占用的内存。垃圾回收（garbage collection）是自动内存管理的机制。

标记-清除算法（mark-and-sweep）：

标记阶段：从根对象（寄存器和栈中的对象）开始，递归标记所有可达对象

清除阶段：扫描内存，回收未标记的对象

scheme

(define (gc)
  ; 标记阶段
  (for-each mark-reachable
            (list (get-register 'val)
                  (get-register 'argl)
                  ...))
  ; 清除阶段
  (for-each (lambda (block)
              (if (not (marked? block))
                  (free-block block)))
            all-blocks))

(define (mark-reachable obj)
  (if (and (pointer? obj) (not (marked? obj)))
      (begin (mark obj)
             (for-each mark-reachable (children obj)))))

复制算法（copying collection）：

将内存分为两个区域：from-space 和 to-space。在 from-space 中分配对象，垃圾回收时将存活对象复制到 to-space，然后交换两个区域。

scheme

(define (gc-copy)
  (let ((scan-pointer to-space-start))
    (for-each (lambda (root)
                (copy root))
              roots)
    (while (< scan-pointer free-pointer)
      (for-each (lambda (field)
                  (copy field))
                (fields scan-pointer))
      (set! scan-pointer (+ scan-pointer object-size)))
    (swap from-space to-space)))

5.10 编译器的优化

编译器可以进行多种优化，提高生成代码的效率：

常量折叠（constant folding）：在编译时计算常量表达式

scheme

; 优化前
(assign val (op +) (const 1) (const 2))
; 优化后
(assign val (const 3))

死代码消除（dead code elimination）：删除不会执行的代码

scheme

; 优化前
(test (op <) (reg x) (const 0))
(branch (label L1))
(assign y (const 1))
(goto (label L2))
L1:
(assign y (const 2))
L2:
; 如果 x 总是 >= 0，可以优化为
(assign y (const 1))

内联展开（inline expansion）：将过程调用替换为过程体

scheme

; 优化前
(assign val (op square) (reg x))
; 优化后（假设 square 定义为 (* x x)）
(assign val (op *) (reg x) (reg x))

寄存器分配（register allocation）：优化寄存器的使用，减少 save/restore 操作

scheme

; 优化前
(save argl)
(assign argl (op cons) (reg x) (reg argl))
(restore argl)
; 优化后（如果不需要保存）
(assign argl (op cons) (reg x) (reg argl))

重要知识点

1. 计算的物理模型

寄存器机器提供了计算的物理模型。它展示了高级抽象如何映射到物理操作：

变量映射到寄存器
过程调用映射到跳转和链接
环境映射到内存中的数据结构
控制流映射到分支和跳转指令

这种映射揭示了计算的本质：计算是对物理状态的变换。

2. 解释与编译的权衡

解释器和编译器是执行程序的两种基本方式：

解释器：灵活，易于调试，但执行速度慢
编译器：执行速度快，但灵活性差，调试困难

现代语言通常结合两者：先编译为字节码，再用虚拟机解释执行。这种方式兼顾了灵活性和性能。

3. 指令集设计

寄存器机器的指令集设计影响程序的效率和复杂性。设计指令集需要考虑：

正交性：指令之间独立，可以自由组合
完备性：指令集能表达任何计算
效率：常用操作有对应的指令
简洁性：指令数量少，易于实现

RISC（精简指令集）和 CISC（复杂指令集）是两种不同的设计哲学。

4. 内存管理策略

内存管理是系统编程的重要问题。不同的策略适用于不同的场景：

手动管理：程序员负责分配和释放，效率高但容易出错
引用计数：跟踪每个对象的引用数，引用数为零时回收
标记-清除：标记可达对象，清除不可达对象
复制算法：复制存活对象，回收整个区域
分代回收：根据对象生命周期分代，提高回收效率

5. 编译优化技术

编译优化是提高程序性能的关键技术。常见的优化包括：

局部优化：在基本块内优化
全局优化：跨基本块优化
循环优化：针对循环的优化
过程间优化：跨过程边界的优化
运行时优化：基于运行时信息的优化（JIT 编译）

常见误区

1. 混淆抽象层次

寄存器机器是低级抽象，Scheme 是高级抽象。在两个层次之间转换时，容易混淆概念。例如，Scheme 的过程调用是高级抽象，映射到寄存器机器是跳转和链接指令。理解这种映射关系对于正确设计编译器非常重要。

2. 忽略栈的重要性

栈在寄存器机器中起着关键作用，用于保存和恢复寄存器值。忽略栈的使用可能导致寄存器值被覆盖，产生错误的结果。在编译过程调用时，必须仔细分析哪些寄存器需要保存。

3. 对垃圾回收的误解

垃圾回收不是"免费"的。它需要消耗 CPU 时间和内存。不同的垃圾回收算法有不同的性能特征，需要根据应用场景选择合适的算法。此外，垃圾回收不能解决所有内存问题，如内存泄漏（对象仍然被引用但不再需要）。

4. 过度优化

编译优化可以提高性能，但也可能增加编译时间、降低代码可读性、引入错误。应该根据实际需要选择合适的优化级别，而不是盲目追求最高优化。

5. 对计算模型的局限性认识不足

寄存器机器是图灵完备的，可以模拟任何计算过程。但这不意味着所有计算都是可行的。计算的物理极限（如时间复杂度、空间复杂度）限制了实际可解问题的范围。理解这些限制对于设计高效的算法非常重要。

实践应用

1. 虚拟机设计

寄存器机器模型是现代虚拟机设计的基础。Java 虚拟机（JVM）、.NET 公共语言运行时（CLR）等都是基于寄存器或栈的虚拟机。

scheme

; 简单的栈式虚拟机
(define (execute-instruction inst)
  (cond ((eq? (car inst) 'push)
         (stack-push! stack (cadr inst)))
        ((eq? (car inst) 'pop)
         (stack-pop! stack))
        ((eq? (car inst) 'add)
         (let ((a (stack-pop! stack))
               (b (stack-pop! stack)))
           (stack-push! stack (+ a b))))
        ...))

2. 字节码编译器

将高级语言编译为字节码，然后在虚拟机上执行。这种方式兼顾了跨平台性和执行效率。

scheme

; 将 Scheme 编译为字节码
(define (compile-to-bytecode exp)
  (cond ((number? exp) `((push-const ,exp)))
        ((variable? exp) `((load-var ,exp)))
        ((assignment? exp)
         (append (compile-to-bytecode (assignment-value exp))
                 `((store-var ,(assignment-variable exp)))))
        ((application? exp)
         (append (map compile-to-bytecode (operands exp))
                 `((call ,(operator exp) ,(length (operands exp))))))
        ...))

3. 硬件设计

寄存器机器模型也用于硬件设计。CPU 的设计就是实现一个寄存器机器，执行指令集架构（ISA）定义的指令。

scheme

; 简单的 CPU 模型
(define (cpu-cycle)
  ; 取指
  (let ((inst (memory-read pc)))
    ; 译码
    (let ((opcode (decode-opcode inst))
          (operands (decode-operands inst)))
      ; 执行
      (execute opcode operands)
      ; 更新 PC
      (set! pc (+ pc 1)))))

4. 性能分析工具

基于寄存器机器模型，可以构建性能分析工具，测量程序的执行时间、内存使用等。

scheme

; 简单的性能分析器
(define (profile machine program)
  (let ((start-time (current-time))
        (start-memory (memory-usage machine)))
    (run-machine machine program)
    (let ((end-time (current-time))
          (end-memory (memory-usage machine)))
      (list (cons 'time (- end-time start-time))
            (cons 'memory (- end-memory start-memory))))))

5. 形式化验证

寄存器机器模型可以用于形式化验证，证明程序的正确性。通过定义机器的状态转换规则，可以使用模型检查工具验证程序是否满足特定性质。

scheme

; 状态转换规则
(define (transition state instruction)
  (cond ((eq? (car instruction) 'assign)
         (update-register state
                          (cadr instruction)
                          (eval-operand (caddr instruction) state)))
        ((eq? (car instruction) 'goto)
         (update-pc state (cadr instruction)))
        ...))

; 验证性质
(define (verify machine property)
  (let ((states (generate-all-states machine)))
    (for-all states (lambda (s) (holds? property s)))))

本章小结

本章深入探讨了计算模型的概念和技术。我们学习了：

寄存器机器：由寄存器、操作器、控制器和栈组成的抽象计算设备。寄存器机器语言是一组低级指令，可以描述任何计算过程。

寄存器机器模拟器：用 Scheme 编写的程序，解释执行寄存器机器指令。模拟器包含执行循环、寄存器管理、栈操作等组件。

从高级语言到机器：将 Scheme 程序转换为寄存器机器程序需要语法分析和代码生成。这个过程与编译器的前端类似。

显式控制求值器：用寄存器机器语言编写的 Scheme 解释器，是元循环求值器的机器级实现。

编译器：将高级语言程序翻译为机器指令。编译器包含词法分析、语法分析、语义分析、代码生成和优化等组件。

链接约定：处理编译后代码的跳转问题，包括 return、next 和标签三种方式。

寄存器保存与恢复：在过程调用时保存和恢复寄存器值，避免被覆盖。

垃圾回收：自动内存管理机制，包括标记-清除算法和复制算法。

编译优化：提高生成代码效率的技术，包括常量折叠、死代码消除、内联展开和寄存器分配。

寄存器机器模型揭示了计算的物理本质。通过理解高级抽象如何映射到物理操作，我们可以更好地设计高效的程序和系统。编译器技术是现代软件基础设施的核心，理解编译器的原理对于开发高效的编程语言和工具非常重要。

本章也展示了计算的极限。虽然寄存器机器是图灵完备的，但计算的物理限制（时间、空间）决定了实际可解问题的范围。理解这些限制，有助于我们设计更高效的算法和系统。

至此，我们完成了《计算机程序的构造和解释》五章内容的学习。从基本的过程抽象，到数据抽象，再到状态和对象，然后到元语言抽象，最后到计算模型，我们逐步深入理解了程序设计的本质。这些概念和技术构成了现代计算机科学的基础，对于任何从事软件开发的人来说都是必不可少的知识。

第五章 计算模型

导读

核心概念详解

5.1 寄存器机器的基本结构

5.2 寄存器机器语言

5.3 寄存器机器模拟器

5.4 从高级语言到寄存器机器

5.5 显式控制求值器

5.6 编译器的基本结构

5.7 链接约定

5.8 寄存器保存与恢复

5.9 垃圾回收

5.10 编译器的优化

重要知识点

1. 计算的物理模型

2. 解释与编译的权衡

3. 指令集设计

4. 内存管理策略

5. 编译优化技术

常见误区

1. 混淆抽象层次

2. 忽略栈的重要性

3. 对垃圾回收的误解

4. 过度优化

5. 对计算模型的局限性认识不足

实践应用

1. 虚拟机设计

2. 字节码编译器

3. 硬件设计

4. 性能分析工具

5. 形式化验证

本章小结

第五章计算模型