SICP Chapter5 读书笔记

Chapter 5: Computing with Register Machines 寄存器里的计算

5.1 Designing Register Machines 寄存器的设计

以 gcd 算法为例

(define (gcd a b)
  (if (= b 0)
    a
    (gcd b (remainder a b))))

每个向寄存器赋值的方式都由一个带有X的箭头指示,指向数据源的寄存器。
我们可以将X视为一个按钮,当按下时,它允许源处的值“流入”指定的寄存器。

为了正确计算GCD,必须按正确的顺序“按下按钮”,确保数据流路径正确。

例子:堆栈实现递归

5.1.1 A Language for Describing Register Machines 描述寄存器的语言

数据通路图和控制器图很适合描述像GCD这样的简单机器。但要描述像寄存器这样的复杂机器,就难受了。

所以我们要创造一种语言,它能以正文的形式表现出由数据通路图和控制器图给出的所有信息。

一部GCD机器的规范描述如下:

(data-paths
 (registers
  ((name a)
   (buttons ((name a<-b) 
             (source (register b)))))
  ((name b)
   (buttons ((name b<-t)
             (source (register t)))))
  ((name t)
   (buttons ((name t<-r)
             (source (operation rem))))))
 (operations
  ((name rem)
   (inputs (register a) (register b)))
  ((name =)
   (inputs (register b) (constant 0)))))
 
(controller
 test-b                ; label
   (test =)            ; test
   (branch 
    (label gcd-done))  ; conditional branch
   (t<-r)              ; button push
   (a<-b)              ; button push
   (b<-t)              ; button push
   (goto 
    (label test-b))    ; unconditional branch
 gcd-done)             ; label

我们可以忽略掉数据通路描述,只留下控制器序列,可以把描述改写为下列形式:

(controller
 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)

相比于上面的规范描述,这种描述更便于阅读,但也有缺点:

  1. 对于大型机器而言,这样的语法描述太啰嗦,因为只要控制器指令序列中多次重复出现某个元素,我们就要反复去看这个元素的完整描述(GCD的例子没有这个问题因为没个操作和按钮都只出现了一次) 总的来说,重复出现的数据通路描述将使得机器中实际的数据通路结构变得模糊不清,令人难以理解。
  2. 机器定义中的控制器指令看起来像Lisp的表达式,因此就使人很容易忘记它们并不是任意的Lisp表达式,只能表示合法的机器指令。(如上面这里的操作只能对常量和寄存器的内容去做)

我们更关注对于控制器的理解,(数据通路设计相对就不重要了)所以还是选用这种语言。(但实际机器设计时,数据通路设计很重要)

5.1.2 Abstraction in Machine Design 机器设计的抽象

我们通常会定义一台机器包含(实际上非常复杂的)“基本操作”。例如我们要把Scheme的环境操作当作“基本操作”,这很有用,它能使我们暂时忽略机器的这部分细节,将注意力放在有关设计的其他方面。

5.1.3 Subroutines 子程序

5.2 A Register-Machine Simulator 一个寄存器机器的模拟器

用前一节寄存器机器语言描述的机器构造一个模拟器。这个模拟器本质上是一个Scheme程序,其中包含四个界面过程:

第一个过程根据寄存器机器的描述,为这部机器构造一个模型(一个数据结构,其中的各个部分对应于被模拟的各个组成部分)

另外三个过程我们可以通过操作这个模型去模拟相应的机器:

1.构造并返回机器的模型,其中包含了给定的寄存器、操作和控制器:

(make-machine <register-names> <operations> <controller>)

2.将一个值存入给定机器的一个被模拟的寄存器里:

(set-register-contents! <machine-model> <register-name> <value>)

3.返回给定机器里一个被模拟的寄存器的内容:

(get-register-contents <machine-model> <register-name>)

4.模拟给定机器的执行,从相应控制器序列的开始处启动,直到达到序列尾部时停止。

5.2.1 The Machine Model 机器模型
  • 为了实现机器模型,make-machine在开始时调用过程make-new-machine,构造出所有寄存器机器的机器模型里都需要的一些公共部分,由make-new-machine构造出的基本机器模型,从本质上看是一个容器,其中包含了若干个寄存器和一个堆栈,还有一个执行机制,它一条一条地处理控制器指令。
  • 然后,make-machine将给它传递消息来扩充这一基本模型,把机器的寄存器、操作和控制器加进去。
  • 它首先为新机器里需要提供的每个寄存器名字分配一个寄存器,并安装好这一机器指定的各种操作。
  • 最后它用一个汇编程序把控制器列表变换为新机器所用的指令,并将他们安装为这一机器的指令序列。
  • make-machine返回修改后的机器模型作为值。
(define (make-machine register-names 
                      ops 
                      controller-text)
  (let ((machine (make-new-machine)))
    (for-each (lambda (register-name)
                ((machine 'allocate-register) 
                 register-name))
              register-names)
    ((machine 'install-operations) ops)
    ((machine 'install-instruction-sequence)
     (assemble controller-text machine))
    machine))

寄存器

把寄存器表示为带有一个局部状态的过程:

(define (make-register name)
  (let ((contents '*unassigned*))
    (define (dispatch message)
      (cond ((eq? message 'get) contents)
            ((eq? message 'set)
             (lambda (value) 
               (set! contents value)))
            (else
             (error "Unknown request: 
                     REGISTER"
                    message))))
    dispatch))
 
(define (get-contents register)
  (register 'get))
(define (set-contents! register value)
  ((register 'set) value))

make-register过程创建这种寄存器,里面保存着一个值,可以访问或修改。

堆栈

把堆栈也表示为一个带有局部状态的过程:

(define (make-stack)
  (let ((s '()))
    (define (push x)
      (set! s (cons x s)))
    (define (pop)
      (if (null? s)
          (error "Empty stack: POP")
          (let ((top (car s)))
            (set! s (cdr s))
            top)))
    (define (initialize)
      (set! s '())
      'done)
    (define (dispatch message)
      (cond ((eq? message 'push) push)
            ((eq? message 'pop) (pop))
            ((eq? message 'initialize) 
             (initialize))
            (else 
             (error "Unknown request: STACK"
                    message))))
    dispatch))
 //访问函数(过程):
(define (pop stack) (stack 'pop))
(define (push stack value)
  ((stack 'push) value))

make-stack过程建立堆栈,它的局部状态就是一个包含着这个堆栈的数据项的表。堆栈接收的请求有push、pop、initialize(初始化为空)。

基本机器

过程make-new-machine构造起一个对象,内部状态包括了一个堆栈,另外还有一个初始为空的指令序列和一个操作的表,开始时这个表里只包含一个初始化堆栈的操作;还有一个寄存器的列表,初始时包含两个分别称为flag和pc(program counter)的寄存器。内部过程allocate-register用于向寄存器列表中加入新项,内部过程lookup-register在这个列表里查找寄存器。

(define (make-new-machine)
  (let ((pc (make-register 'pc))
        (flag (make-register 'flag))
        (stack (make-stack))
        (the-instruction-sequence '()))
    (let ((the-ops
           (list 
            (list 'initialize-stack
                  (lambda () 
                    (stack 'initialize)))))
          (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-instruction-sequence)
               (execute))
              ((eq? 
                message 
                'install-instruction-sequence)
               (lambda (seq) 
                 (set! 
                  the-instruction-sequence 
                  seq)))
              ((eq? message 
                    'allocate-register) 
               allocate-register)
              ((eq? message 'get-register) 
               lookup-register)
              ((eq? message 
                    'install-operations)
               (lambda (ops) 
                 (set! the-ops 
                       (append the-ops ops))))
              ((eq? message 'stack) stack)
              ((eq? message 'operations) 
               the-ops)
              (else (error "Unknown request: 
                            MACHINE"
                           message))))
      dispatch)))
(define (start machine)
  (machine 'start))
(define (get-register-contents 
         machine register-name)
  (get-contents 
   (get-register machine register-name)))
(define (set-register-contents! 
         machine register-name value)
  (set-contents! 
   (get-register machine register-name) 
   value)
  'done)
(define (get-register machine reg-name)
  ((machine 'get-register) reg-name))
5.2.2 The Assembler 汇编程序

汇编程序包含一个输入语言(寄存器机器语言),以及对于这个语言里的每个类型必须执行的操作。

为每条指令生成一个执行过程的技术(也就是4.1.7节里面,为了加快求值器的速度,把分析工作和运行时执行动作分离的技术。)

要生成指令执行过程,汇编程序还必须知道所有标号的引用位置。为此首先扫描控制器的正文,从指令序列中分辨出各个标号,构建起指令表和标号列表,每个标号对应指令表的指针。

(define (assemble controller-text machine)
  (extract-labels controller-text
    (lambda (insts labels)
      (update-insts! insts labels machine)
      insts)))
 
(define (extract-labels text receive)
  (if (null? text)
      (receive '() '())
      (extract-labels 
       (cdr text)
       (lambda (insts labels)
         (let ((next-inst (car text)))
           (if (symbol? next-inst)
               (receive 
                   insts
                   (cons 
                    (make-label-entry 
                     next-inst
                     insts)
                    labels))
               (receive 
                   (cons (make-instruction 
                          next-inst)
                         insts)
                   labels)))))))

extra-labels的参数是一个表text(控制器指令表达式的序列)和一个过程recieve。

(define (update-insts! insts labels machine)
  (let ((pc (get-register machine 'pc))
        (flag (get-register machine 'flag))
        (stack (machine 'stack))
        (ops (machine 'operations)))
    (for-each
     (lambda (inst)
       (set-instruction-execution-proc!
        inst
        (make-execution-procedure
         (instruction-text inst) 
         labels
         machine
         pc
         flag
         stack
         ops)))
     insts)))
 
(define (make-instruction text)
  (cons text '()))
(define (instruction-text inst) (car inst))
(define (instruction-execution-proc inst)
  (cdr inst))
(define (set-instruction-execution-proc!
         inst
         proc)
  (set-cdr! inst proc))

update-insts!修改指令表,这里只包含指令的正文,所以要考虑如何加入执行过程:

(define (make-label-entry label-name insts)
  (cons label-name insts))
 
(define (lookup-label labels label-name)
  (let ((val (assoc label-name labels)))
    (if val
        (cdr val)
        (error "Undefined label: ASSEMBLE" 
               label-name))))

机器指令的数据结构也就是指令正文对应的执行过程的pairs。

5.2.3 Generating Execution Procedures for Instructions 为指令生成执行过程

汇编程序调用make-execution-procedure,为一条指令生成一个执行过程(像4.1.7求值器的analyze过程)。这个过程也是基于指令的类型,把生成执行过程的工作分派出去:

(define (make-execution-procedure 
         inst labels machine pc flag stack ops)
  (cond ((eq? (car inst) 'assign)
         (make-assign 
          inst machine labels ops pc))
        ((eq? (car inst) 'test)
         (make-test 
          inst machine labels ops flag pc))
        ((eq? (car inst) 'branch)
         (make-branch 
          inst machine labels flag pc))
        ((eq? (car inst) 'goto)
         (make-goto inst machine labels pc))
        ((eq? (car inst) 'save)
         (make-save inst machine stack pc))
        ((eq? (car inst) 'restore)
         (make-restore inst machine stack pc))
        ((eq? (car inst) 'perform)
         (make-perform
          inst machine labels ops pc))
        (else (error "Unknown instruction 
                      type: ASSEMBLE"
                     inst))))

assign指令(由过程make-assign处理):

(define (make-assign 
         inst machine labels operations pc)
  (let ((target 
         (get-register 
          machine 
          (assign-reg-name inst)))
        (value-exp (assign-value-exp inst)))
    (let ((value-proc
           (if (operation-exp? value-exp)
               (make-operation-exp
                value-exp 
                machine
                labels
                operations)
               (make-primitive-exp
                (car value-exp)
                machine
                labels))))
      (lambda ()   ; execution procedure
                   ; for assign
        (set-contents! target (value-proc))
        (advance-pc pc)))))

查找寄存器名字和分析值表达式的工作,都只需在汇编时做一次,不需要在指令模拟时每次都做(采用执行过程的原因)

advance-pc是每条指令的正常结束操作(除了branch和goto)指向下一个指令

(define (advance-pc pc)
  (set-contents! pc (cdr (get-contents pc))))

test、branch和goto指令

(define 
  (make-test 
   inst machine labels operations flag pc)
  (let ((condition (test-condition inst)))
    (if (operation-exp? condition)
        (let ((condition-proc
               (make-operation-exp
                condition 
                machine
                labels
                operations)))
          (lambda () 
            (set-contents! 
             flag (condition-proc))
            (advance-pc pc)))
        (error "Bad TEST instruction: 
                ASSEMBLE" inst))))
 
(define (test-condition test-instruction)
  (cdr test-instruction))
(define 
  (make-branch 
   inst machine labels flag pc)
  (let ((dest (branch-dest inst)))
    (if (label-exp? dest)
        (let ((insts
               (lookup-label 
                labels 
                (label-exp-label dest))))
          (lambda ()
            (if (get-contents flag)
                (set-contents! pc insts)
                (advance-pc pc))))
        (error "Bad BRANCH instruction: 
                ASSEMBLE"
               inst))))
 
(define (branch-dest branch-instruction)
  (cadr branch-instruction))
(define (make-goto inst machine labels pc)
  (let ((dest (goto-dest inst)))
    (cond ((label-exp? dest)
           (let ((insts
                  (lookup-label 
                   labels
                   (label-exp-label dest))))
             (lambda () 
               (set-contents! pc insts))))
          ((register-exp? dest)
           (let ((reg
                  (get-register 
                   machine
                   (register-exp-reg dest))))
             (lambda ()
               (set-contents! 
                pc
                (get-contents reg)))))
          (else (error "Bad GOTO instruction: 
                        ASSEMBLE"
                       inst)))))
 
(define (goto-dest goto-instruction)
  (cadr goto-instruction))

其他指令如save、restore等具体自行看书~

5.3 Storage Allocation and Garbage Collection 储存分配和废料回收

为了实现 Scheme 解释器,还需要考虑表结构的表示和处理

介绍具体的存储操作(基本的表操作、巧妙的存储管理机制)

5.4 The Explicit-Control Evaluator 显式控制的求值器

有了5.1-5.3的实现的条件,实现第四章介绍的元循环解释器(注意实现细节)

Scheme求值器寄存器机器里包含了一个堆栈和七个寄存器:exp、env、val、continue、proc、argl和unev。

两种执行程序的方式(优劣):

解释型:

专门的解释器对源程序每一行解释成特定平台的机器码并立即执行的语言;

解释型语言不会对整体性的编译和链接处理,解释型语言相当于把编译语言中编译和解释过程混合到了一起同时完成。

优点:跨平台较容易,是以牺牲程序执行效率为代价。

缺点:效率较低,不能脱离解释器独立运行

代表语言:ruby  python

编译型:

专门的编译器, 针对特定的平台(操作系统)“翻译”成机器码(包括机器指令和操作数),并包装成该平台可执行程序的格式;如需要其他的代码,要进行链接。

优点: 可脱离开发环境,特定的平台上独立运行,运行效率较高。

缺点:无法移植;需要移植,要源代码重新编译。

代表语言:C    C++

5.5 Compilation 编译

把 Scheme 语言程序翻译成寄存器机器语言

如何支持解释代码和编译代码之间的连接、支持动态编译

发表评论

电子邮件地址不会被公开。 必填项已用*标注