笔记仓库

正常人的正常笔记集

寄存机器的构造与解释

传统计算机可以被抽象为一种寄存机器模型(register machine model),在这个模型里,执行程序的过程即按顺序依次执行一系列指令来操纵某些固定存储元素(寄存器)的内容,典型的寄存机器指令的内容为对一些寄存器内容进行操作并把结果赋给另一个寄存器。

Chapter 5: Computing with Register Machines整章内容都在介绍这个寄存机器模型,讨论怎样寄存机器怎样实现计算机程序的种种细节。目前我只详细看完了前两小节,5.1 Designing Register Machines讨论怎样设计这样的寄存机器模型并用相应的符号和语言来表示程序,5.2 A Register-Machine Simulator探讨了怎样用Scheme去模拟实现前面设计的寄存机器语言。相对而言,5.1的内容比较浅显且互联网上更容易找到相应的资料,我在本文就只粗略地介绍一下这种语言的用法,把全文的内容重点放到5.2对应的如何用高级语言去实现这种语言上,通过亲自设计实现模拟并利用它来观测寄存器和栈的使用情况以及指令执行的效率,可以从更接近底层和硬件的视角来审视高级程序设计的问题。

总之我还是很鼓励各位读者亲自去看一下原书动手实现和思考,毫无疑问本文确实是标题党,真正精彩的内容还在后面的章节我也没有细看,只是把我认为非常基础的两个小节内容做了解析和整理。如果实在觉得啃原著吃力我也希望我的笔记和解读能给困惑中的初学者带来帮助。5.2原文的编排顺序总体很不错,但如assembler部分有点混乱,再加上有点卖弄trick之嫌,会自学者造成很大的阅读压力。没有关系,我们之后会一步步解析这些内容。

基本模型

一个典型的计算过程:用辗转相除法(Euclid算法)求ab的最大公约数

1
2
3
4
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))

在寄存机器上运行该过程的过程,可以从数据流的角度建立数据通路(data path)模型来描述数据的产生,流向和存储,也可以根据基本操作的顺序建立控制器(controller)模型来演示指令的推进过程。

数据通路

(gcd a b)的数据通路可以简单的表示为

图例

  • 矩形:寄存器,如a,b,t
  • 指向矩形箭头:表示对寄存器的赋值操作,上面标记的$\otimes$可以看成一个决定操作是否进行的按钮,标记如$a \leftarrow b$按钮表示把b寄存器的值赋给a
  • 三角形:表示常量
  • 梯形:计算操作,一般为原语(primitive)操作。用常数或寄存器内容产生计算结果。
  • 圆形:测试,与计算操作类似,但测试的输出结果为是或否,这个结果也由控制器来使用,在数据通路图中不直接体现。

因为发生递归时寄存器ab都会重新被赋一个关于另一个寄存器的值,所以引入临时寄存器t来完成这样的交换赋值。

数据通路也可以用这样的语言描述为

1
2
3
4
5
6
7
8
(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))))))

这样的描述虽然很好的反映了数据流的变化,但想要数据正确地在这些元件之间流动并最终从寄存器a中取出最终结果,需要谨慎的按照一定顺序去按下这些按钮,这件不那么容易表述清楚的事在此完全没有体现,还需要从控制器模型获得相关的信息。

这个表示法和用于描述这种表示法的DSL相对来说并不怎么重要,之后我也不会再在关于数据路径的问题上展开讨论太多,只是辅助理解。

控制器

控制器负责安排这些指令操作发生的顺序,(gcd a b)的控制器为

图示为我们所熟悉的流程图表示法。

在这个模型的基础上,可以表达一个程序究竟按照什么顺序去执行了哪些指令。为了直观表达,gcd寄存机器的控制器模型也可以用这样类似于Lisp的自定义语言(你可以把它看作一种粗糙的伪代码)去描述

1
2
3
4
5
6
7
8
9
(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

这也是接下来通篇重点探究的寄存机器语言的雏形。


寄存机器语言

上述基于控制器的语言描述仍然有很多模糊的地方,为了更精准的描述,可以调整为这样的形式

1
2
3
4
5
6
7
8
9
(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)

如果你曾经写过汇编语言,对此应该是有些亲切感的。接下来直接规定这些指令的用法和意义,并讨论如何把高级程序转换成可以直接执行的寄存机器语言指令

基本用法

常见操作对应的指令

  • (const <constant-value>):表示常量
  • (reg <register-name>):寄存器的内容

以及以下稍微复杂的指令,其中<input>为上述常量或寄存器内容

  • (assign <register-name> (reg <register-name>)): 将一个寄存器的内容放入另一个寄存器
  • (assign <register-name> (const <constant-value>)): 将常量值放入寄存器
  • (assign <register-name> (op <operation-name>) <input1> ... <inputn>):将这些<input>作为输入的<operation-name>操作的结果放入寄存器
  • (perform (op <operation-name>) <input1> ... <inputn>):用这些<input>进行<operation-name>操作
  • (test (op <operation-name>) <input1> ... <inputn>): 测试这些<input>进行<operation-name>操作是否为真,如果是则进入执行接下来的branch语句,否则跳过这个branch指令
  • (branch (label <label-name>)):如果上一步测试结果为真,跳转到<label-name>对应的label
  • (goto (label <label-name>)): 跳转到<label-name>对应的label

寄存器不仅可以用来存放数值,也可以用来存放需要被跳转的目标label

  • (assign <register-name> (label <label-name>)):把<label-name>对应label值放入寄存器<register-name>
  • (goto (reg <register-name>)): 跳转到寄存器存放的label位置

后面会看到,处理递归时会用到一个栈(stack)来管理后续指令(像gcd那样的尾递归不需要),因此有相应的栈操作:

  • (save <register-name>): 把寄存器内容压入栈内
  • (restore <register-name>):弹出栈顶元素并放入寄存器内

接下来我们将以一些例子演示用这些指令描述高级程序在寄存机器上是如何运行的。

I/O GCD machine

增加一些读写操作,调用gcd过程使之循环接收输入值ab并输出计算结果,类似于以前写evaluator程序的driver-loop主循环。数据通路可以表示为

用寄存机器语言表示为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(controller
gcd-loop
(assign a (op read))
(assign b (op read))
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
(perform (op print) (reg a))
(goto (label gcd-loop)))

这里出现了只需要副作用的print操作所以用前面提到的perform来表示执行这个指令。另外,rem操作并不是像其他运算那样的primitives,需要被转换成更底层的操作,如:

1
2
3
4
5
6
rem-loop
(test (op <) (reg t) (reg b))
(branch (label rem-done))
(assign t (op -) (reg t) (reg b))
(goto (label rem-loop))
rem-done

不过这也并不那么重要,所以为了理解gcd先把它当作primitives看待也无妨。

阶乘

一个一拍大腿写成的计算$n!$的过程大概是这样的:

1
2
3
4
(define (factorial n)
(if (= n 1)
1
(* (factorial (- n 1)) n)))

对比gcd在发生递归时,新gcd过程的结果就是原来的gcd的结果,这类递归被称为尾递归(tail recursion),可以转换成迭代形式。在寄存器中不需要再原来的gcd中保留任何内容,直接进入新的gcd执行新的指令,不需要再执行任何上一层gcd遗留下来的任何指令。而(factorial n)则需要在计算完(factorial (- n 1))后把它的结果再返回到被调用的地方再乘n,因此需要维护在计算完成前需要维护原factorial的环境。那么在n减至1之前,所有factorial的环境都必须保留着,等着下一级调用传回的操作数与当前的n相乘。举个例子,简单的看一下计算$6!$需要的展开

除了需要显性的保存n的值,调用函数计算完成(factorial n)后的接下来的操作(有点类似我们上一篇提到的continuation)也是由上一级factorial决定的,最外层可以直接跳出回到其他程序,而第一次递归调用则需要返回最外层factorial发生乘法操作的位置……依次类推,存储计算完成后应该跳转的位置的寄存器continue也需要像n那样被保留。为了实现这一切,在控制器中需要再引入一个先进先出的栈,每当递归发生时,把ncontinue寄存器的内容用save压入栈中,子函数计算完成后再从栈中用restore指令弹出恢复到相应的寄存器中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(controller
(assign continue (label fact-done)) ; set up final return address
fact-loop
(test (op =) (reg n) (const 1))
(branch (label base-case))
;; Set up for the recursive call by saving n and continue.
;; Set up continue so that the computation will continue
;; at after-fact when the subroutine returns.
(save continue)
(save n)
(assign n (op -) (reg n) (const 1))
(assign continue (label after-fact))
(goto (label fact-loop))
after-fact
(restore n)
(restore continue)
(assign val (op *) (reg n) (reg val)) ; val now contains n(n - 1)!
(goto (reg continue)) ; return to caller
base-case
(assign val (const 1)) ; base case: 1! = 1
(goto (reg continue)) ; return to caller
fact-done)

对应的数据通路图如下,不需要完全看懂数据通路,只是用于理解上述控制器发生了哪些操作的参考:

注意到ncontinue都是与同一个栈发生的数据交流,所以对这两个寄存器压栈和弹栈操作时需要注意两个寄存器之间的顺序,否则弹出的值会被放入错误的寄存器。这个问题在一些寄存机器的实现中是通过对每个变量都指定一个栈来解决的,但这里为了经济和效率考虑,只给整个机器分配了一个栈。

另外,我们其实都很清楚(factorial n)完全可以改写成尾递归形式:

1
2
3
4
5
6
7
(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product)
(+ counter 1))))
(iter 1 1))

这个版本的factorial转换成的寄存机器指令就不会需要额外的栈操作开销,这也是尾递归相比普通的树形递归(tree recursion)运行效率上的优越的根源。

Fibonacci序列

一个典型的求Fibonacci数的递归过程:

1
2
3
4
(define (fib n)
(if (< n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))

相比前面写的那些递归过程,(fib n)在过程内还显式调用了两次fib,并把两次的返回结果进行了加法运算,但把它改写为寄存机器语言时,有了前面factorial使用栈的经验,fib也没有非常特殊的地方,无非是在(fib n)的两个关键节点:计算(fib (- n 1))前后和计算(fib (- n 2)前后分别需要压栈和弹栈的操作而已,而两次操作也是互相独立各不干扰的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
(controller
(assign continue (label fib-done))
fib-loop
(test (op <) (reg n) (const 2))
(branch (label immediate-answer))
;; set up to compute Fib(n-1)
(save continue)
(assign continue (label afterfib-n-1))
(save n) ; save old value of n
(assign n (op -) (reg n) (const 1)); clobber n to n-1
(goto (label fib-loop)) ; perform recursive call
afterfib-n-1 ; upon return, val contains Fib(n-1)
(restore n)
(restore continue)
;; set up to compute Fib(n-2)
(assign n (op -) (reg n) (const 2))
(save continue)
(assign continue (label afterfib-n-2))
(save val) ; save Fib(n-1)
(goto (label fib-loop))
afterfib-n-2 ; upon return, val contains Fib(n-2)
(assign n (reg val)) ; n now contains Fib(n-2)
(restore val) ; val now contains Fib(n-1)
(restore continue)
(assign val ; Fib(n-1)+Fib(n-2)
(op +) (reg val) (reg n))
(goto (reg continue)) ; return to caller, answer is in val
immediate-answer
(assign val (reg n)) ; base case: Fib(n)=n
(goto (reg continue))
fib-done)

在每一个(goto (label fib-loop))即递归发生前,都会先把ncontinue的内容压入栈内,并重新赋为接下来的递归调用需要用的ncontinue值,n-1(label afterfib-n-1),或者n-2(label afterfib-n-2),当到达afterfib-n-1afterfib-n-2时表示上一次调用已经完成了,计算结果被放在了val寄存器中,此时只要恢复ncontinue的值就可以继续计算了。当然,(fib (- n 1))的值即当时的val需要被压入栈内,当(fib (- n 2))计算完成后val会被覆盖为(fib (- n 2)),此时需要从栈中取出当时存放的val放入n寄存器(在完成(fib (- n 2))的计算后n值已经没有保留的必要了,所以拿来当(fib (-n 1))的临时容器了),相加得到最终的val后返回到当前fib被调用的地方。

观察力敏锐的人可能已经注意到了,第14行的(restore continue)和第17行的(save continue)之间并没有任何关于continue的读写操作,只是单纯的把一个元素从栈中弹出来又压回去,虽然遵循了谨慎保存及时恢复上下文的原则,但仍然是冗余的操作,一般在编译时会利用窥孔优化(peephole optimization)技术移除。

小结

到此为止,我们通过一些例子熟悉了机器寄存语言的语法规则,也对程序的底层实现稍有了解。关于这部分内容的材料很多,原书5.1对此的阐述十分详尽,对于这些做法的必要性论述也很清晰,有兴趣的可以去认真阅读以下,因为内容太多但并不复杂也不难以理解所以我就不展开详细讲述了,只挑了一些对于寄存机器模型重要的例子和通用规则来演示,以方便下文侧重详谈如何用高级语言去模拟实现它。

另外,这部分资料和工具也很充足,比如公开课MIT 6.0011Lec9b 寄存机器部分lecture就细谈了这种语言的设计和使用。虽然这种语言这是被构造出来的DSL,但与汇编语言有很大的相似之处,如果没接触过汇编也在闲暇无聊想解压时试试小游戏human resource machine2,以简单的基于汇编风格的语言为基础的编程入门教学游戏,不涉及递归,但也大量涉及寄存器和分支跳转操作。

总之,了解它的必要性和基本语法后,好戏刚刚开始,让我们开始用Scheme来模拟实现它吧!


解释器设计细节

为了体验和模拟寄存机器语言的使用,我们用Scheme来实现对它的解释。用高级语言去实现,模拟和解释这些指令固然是损耗效率的做法,但通过这种尝试不但可以理解这些指令本身的作用,也会对如何用Scheme来构造一种新的语言有更深的见解。

为了顺应思维习惯,我会调整一些原文给出的顺序。

模拟机的目标

对于外部用户,使用这个封装好的模拟寄存机器相关操作只需要通过以下命令:

  • (make-machine <register-names> <operations> <controller>)<register-names>为所用的寄存器列表,<operations>为操作列表,<controller>为需要模拟的指令控制器,构造一个新的寄存机器模型并返回。
  • (set-register-contents! <machine-model> <register-name> <value>) 把寄存机器模型<machine-model>的寄存器<register-name>内容设置为<value>,通常用于模拟输入
  • (get-register-contents <machine-model> <register-name>) 取出机器模型<machine-model>中的寄存器<register-name>的内容并返回,通常用于得到模拟结果
  • (start <machine-model>) 开始机器模型<machine-model>的模拟,即开始执行指令

以前面的gcd过程为例的gcd-machine构造如下:

1
2
3
4
5
6
7
8
9
10
11
12
(define gcd-machine
(make-machine
'(a b t) ;registers list
(list (list 'rem remainder) (list '= =)) ;operations list
'(test-b ;controller
(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)gcd用到的所有寄存器,rem运算符等对应Scheme原语remainder过程,=也对应操作符=,Controller部分即前面所使用的寄存语言描述的指令操作。用gcd-machine计算gcd需要先把输入ab初始化,用start开始模拟过程后,从a寄存器得到最终结果。

1
2
3
4
5
6
7
8
(set-register-contents! gcd-machine 'a 206)
;done
(set-register-contents! gcd-machine 'b 40)
;done
(start gcd-machine)
;done
(get-register-contents gcd-machine 'a)
;2

接下来演示如何一步步实现机器模型的构造和使用。

寄存器

寄存器包含一个局部状态变量作为它的存放内容,可以通过get/set进行读写内容。

1
2
3
4
5
6
7
8
9
(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))

典型的message passing风格的过程,返回一个dispatch函数,依照惯例用语法糖来包装这两种方法,使其更符合我们的编程习惯:

1
2
3
4
5
(define (get-contents register)
(register 'get))

(define (set-contents! register value)
((register 'set) value))

仔细观察可以发现make-register的参数name在过程中没有被用到,可以不传入。寄存器的名字本来也是人为规定在,后面可以看到机器中的处理是把每个名字都都与make-register构造的新的寄存器绑定来实现对应寄存器的取用。

栈是我们在其他语言里面经常实现的数据结构了,在Scheme中也是用(make-stack)构造返回一个新的栈对象。这里是用一个局部状态变量list来表示栈所使用的空间,它的第一个元素car就是栈顶,初始化为空列表。在用pop弹出元素时需要注意检查是否为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(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))

封装为

1
2
3
4
5
(define (pop stack)
(stack 'pop))

(define (push stack value)
((stack 'push) value))

机器框架

一个新的寄存机器除了需要前面提到的寄存器列表,操作列表,控制器文本以外,内部还会需要一些数据结构来推进指令操作的进行。

首先需要两个辅助寄存器:

  • flag:保存测试操作的结果(truefalse),用以决定跳转到接下来遇到的分支语句branch是否跳转
  • pc: 即program counter指针,用于保存下一步需要进行的指令操作

以及前面提到需要管理递归使用的栈stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
(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)))

加载寄存器列表时会调用allocate-register给每个寄存器名字构造一个新的寄存器,被把这对绑定放进register-table,用户可以在外部通过调用'get-register获取相应的寄存器。

机器运行开始的则调用(execute)过程,首先取出pc指向的内容即下一步需要执行的,完成汇编的 指令,它由原始的指令文本和经过汇编分析得到的该指令实际需要调用的操作过程组成,这个过程函数被称为指令执行过程(instruction execution procedure),即instruction-execution-proc部分,它们内部会包含对pc内容的改变(指令的继续或跳转),所以(execute)的递归调用对于正确的寄存机器语言保证能使得pc指向空内容从而终止。而怎样完成汇编会在之后的内容中看到。

对机器提供的方法的封装:

1
2
3
4
5
6
7
(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)

另外为了更方便的得到机器中的寄存器,可以定义

1
2
(define (get-register machine reg-name)
((machine 'get-register) reg-name))

利用(make-new-machine)得到的未初始化的新的寄存机器,通过编写特定的寄存机器语言程序得到特定的寄存机器,即最终目标所提及的make-machine


1
2
3
4
5
6
7
8
9
(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))

实例化机器模型时,先构造一个新的机器模型,再初始化这个机器中的寄存器列表和操作符列表,当然最关键的是需要对这些控制器指令文本进行汇编,转换为带有可执行的过程的列表,载入机器的指令序列列表,最后返回机器模型。

生成指令执行过程

关于assemble具体做了什么先暂时放着,先来理解汇编过程中最基础的操作,如何把原始的指令转文本转换成可以直接执行的过程。

与在Separating Syntactic Analysis from Execution实现的分析器相似,make-execution-procedure承担的也是把某个原始指令文本inst预先“翻译”成目标语言可执行的过程并返回,需要执行这个指令时,直接调用对应零参过程即可。当然,这些inst会涉及一系列对于寄存器,栈,操作符的读写,以及它们所在的机器模型本身,所以都要作为参数传入。另外,labels是一个存放label与其对应位置开始的指令序列的表,用于快速找到需要跳转的位置,获得labels表是在汇编期间完成的,这里先假设已经得到了这个表可以直接使用,后面再详谈获得的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(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))))

类似于以前写过的eval,按照指令的类型进行不同的解释,这里没有把predicate封装成过程而是直接检查列表第一个元素,得到对应的分类。指令操作涉及的内存操作也是不同的,所以并必要把所有make-execution-procedure的参数全数传入,按照需求取用就已经足够了。那么开始看cond语句中每一个类型对应的做法吧。

assign

赋值操作会先找到需要被赋值的寄存器target,再计算被赋的值是一个操作结果还是原语表达式(如reg表达式或常数或label等),最后返回一个把target赋值为该结果并把令pc指向下一个指令的零参过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
(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)))))

注意这里在lambda表达式内用的是(value-proc),因为value-proc无论是make-operation-exp还是make-primitive-exp的返回结果也都和make-assign一样是一个零参的过程。

分割assign指令文本需要的选择器(selector)为:

1
2
3
4
(define (assign-reg-name assign-instruction)
(cadr assign-instruction))
(define (assign-value-exp assign-instruction)
(cddr assign-instruction))

pc指向下一个指令的过程advance-pc定义为

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

除了branchgoto指令外,advance-pc是所有操作的一般结尾。

test

处理test指令的make-test过程与上面的make-assign过程相似,计算其条件部分操作的结果并存放到flag寄存器,然后让pc指向下一个指令

1
2
3
4
5
6
7
8
9
10
11
12
13
(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))

branch

跟随着test指令而来的branch指令表示测试成功应该跳到哪个位置。make-branch先获得branch的跳转目标dest,并从labels表中获取这个标签对应的指令序列insts,当flag寄存器的内容为真时,跳转到dest即把 pc置为insts,否则推进到当前指令的下一个指令。

1
2
3
4
5
6
7
8
9
10
11
12
13
(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))

注意到对dest会先检查是否为label,所以我们的解释程序只能对在branch指令直接给出的label值做出正确的处理,如果用寄存器内容表达它就可能出问题,而这个局限在goto指令上就不存在。

goto

goto是无条件跳转指令,不需要检查flag的内容。对于其跳转目标dest可以是寄存器内容也可以是label表达式,从寄存器内容中可以直接读出label表达式,再找到labels表中对应的指令序列insts,把pc内容设置为insts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(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))

栈操作

saverestore分别执行压栈和弹栈操作,获取指令中的寄存器后,用前文封装的pushpop过程即可。最后不要忘记把pc指向下一个指令。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(define (make-save inst machine stack pc)
(let ((reg (get-register machine
(stack-inst-reg-name inst))))
(lambda ()
(push stack (get-contents reg))
(advance-pc pc))))

(define (make-restore inst machine stack pc)
(let ((reg (get-register machine
(stack-inst-reg-name inst))))
(lambda ()
(set-contents! reg (pop stack))
(advance-pc pc))))

(define (stack-inst-reg-name stack-instruction)
(cadr stack-instruction))

perform

perform指令要求执行某个操作但不需要把结果返回给任何寄存器,一般只是想要这个操作的副作用(side effect)。make-perform只需要把指令的操作表达式部分对应的过程调用一次,然后推进pc即可。

1
2
3
4
5
6
7
8
9
10
11
12
(define (make-perform inst machine labels operations pc)
(let ((action (perform-action inst)))
(if (operation-exp? action)
(let ((action-proc
(make-operation-exp
action machine labels operations)))
(lambda ()
(action-proc)
(advance-pc pc)))
(error "Bad PERFORM instruction -- ASSEMBLE" inst))))

(define (perform-action inst) (cdr inst))

子表达式

指令内含有一些需要计算的子表达式,通过相应的过程也可以生成这些子表达式对应的执行过程,也是形容上面几个过程返回的零参过程。你可能会疑惑为什么不直接返回这些自表达式的计算结果而要返回一个延迟对象呢?比如label表达式,在指令序列没有被汇编完成时,labels表是不完整的,而提取生成labels表的过程又是和生成指令执行过程的过程是同时交替进行的;另外,寄存器的内容会在执行指令时实时更新,无法一劳永逸的固定它的读取结果。所以需要把这些子表达式的求值相应的作出延迟,让它们在真正开始执行指令模拟时才被计算,这样才能保证得到准确的结果。

reg,label,const表达式会被用于赋值给寄存器或作为操作的输入,但不涉及运算操作,用来生成执行过程的make-primitive-exp如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(define (make-primitive-exp exp machine labels)
(cond ((constant-exp? exp)
(let ((c (constant-exp-value exp)))
(lambda () c)))
((label-exp? exp)
(let ((insts
(lookup-label labels
(label-exp-label exp))))
(lambda () insts)))
((register-exp? exp)
(let ((r (get-register machine
(register-exp-reg exp))))
(lambda () (get-contents r))))
(else
(error "Unknown expression type -- ASSEMBLE" exp))))

选择器语法:

1
2
3
4
5
6
(define (register-exp? exp) (tagged-list? exp 'reg))
(define (register-exp-reg exp) (cadr exp))
(define (constant-exp? exp) (tagged-list? exp 'const))
(define (constant-exp-value exp) (cadr exp))
(define (label-exp? exp) (tagged-list? exp 'label))
(define (label-exp-label exp) (cadr exp))

assigntestperform会包含一些operations表规定的机器操作,用make-operation-exp生成可执行过程为:

1
2
3
4
5
6
7
8
(define (make-operation-exp exp machine labels operations)
(let ((op (lookup-prim (operation-exp-op exp) operations))
(aprocs
(map (lambda (e)
(make-primitive-exp e machine labels))
(operation-exp-operands exp))))
(lambda ()
(apply op (map (lambda (p) (p)) aprocs)))))

可以看到这里默认了操作数的输入必须是可以用make-primitive-exp生成执行过程的简单子表达式,即reg,label,const表达式。最终需要返回的执行过程中,得到这些输入值后用对应的操作符调用它们,返回操作结果。

op指令相关的操作语法对照:

1
2
3
4
5
6
7
8
(define (operation-exp? exp)
(and (pair? exp) (tagged-list? (car exp) 'op)))

(define (operation-exp-op operation-exp)
(cadr (car operation-exp)))

(define (operation-exp-operands operation-exp)
(cdr operation-exp))

operations表中查找操作符对应的函数过程用到的lookup-prim函数定义:

1
2
3
4
5
(define (lookup-prim symbol operations)
(let ((val (assoc symbol operations)))
(if val
(cadr val)
(error "Unknown operation -- ASSEMBLE" symbol))))

注意以上所有子表达式生成的执行过程都不包含对pc的操作,计算子表达式只需要返回结果给它被调用的指令执行过程,而重置pc应该是由这些完整的指令执行过程来完成的。

汇编器

汇编器(assembler)真正的把机器的控制器表达式转换为指令执行过程列表,也是由它来调用make-execution-procedure进行所谓的对指令的解释。

每一条控制器文本指令text都会被转换成一个序对(pair),这个序对结构为instruction,第一部分是原始文本text,第二部分是真正会被执行的对应过程。


1
2
3
4
5
6
7
8
(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))

假设我们已经分离得到了控制器文本中的所有指令instruction结构(但instruction-execution-proc部分为空,还未被初始化)的insts和标签列表labels,那么初始化insts获取每个指令对应的指令执行过程并放到它的instruction-execution-proc中需要用到的update-insts!可以写为:

1
2
3
4
5
6
7
8
9
10
11
12
13
(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)))

而分离文本中的指令和标签则需要扫描一遍整个文本列表,如果被扫描到的是标签(通过symbol?检查)则用make-label-entry把这个标签的名字和接下来所有指令列表组成一条记录添加到labels表并保持指令列表不变

1
2
(define (make-label-entry label-name insts)
(cons label-name insts))

如果被扫描到的是操作指令,则保持labels表不变,用make-instruction新建一个instruction记录并添加到指令列表。

整个过程extract-labels定义如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(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)))))))

receive函数的作用有些类似于在前篇用continuation实现非确定计算使用的continuation函数相似,每处理一条控制器文本(next-inst)就重新构造一个receive,把next-inst的处理结果累积到新的receive,当扫描到最后即text为空时,传递到这里的receive已经包含了前面所有文本的处理结果,调用这个被层层构造累加的receive '() '()相当于直接用原始的receive来调用处理构造完成的instslabels列表。那么完整的汇编过程assemble

1
2
3
4
5
(define (assemble controller-text machine)
(extract-labels controller-text
(lambda (insts labels)
(update-insts! insts labels machine)
insts)))

调用assemble结束后,返回经过ipdate-insts!给每个指令分配好相应的指令执行过程的指令列表insts,在实例化机器时,把整个insts放入机器的指令序列the-instruction-sequence,在开始运行机器时,pc的内容为the-instruction-sequence

注意!

如果觉得用receive函数来接受累计的处理结果这种编程技巧并不优雅,或者不够直观难以理解,也可以用更直接的方式改写:

1
2
3
4
5
6
7
8
9
10
11
(define (extract-labels text)
(if (null? text)
(cons '() '())
(let ((result (extract-labels (cdr text))))
(let ((insts (car result)) (labels (cdr result)))
(let ((next-inst (car text)))
(if (symbol? next-inst)
(cons insts
(cons (make-label-entry next-inst insts) labels))
(cons (cons (make-instruction next-inst) insts)
labels)))))))

相应的

1
2
3
4
5
(define (assemble controller-text machine)
(let ((result (extract-labels controller-text)))
(let ((insts (car result)) (labels (cdr result)))
(update-insts! insts labels machine)
insts)))

总结

至此,用Scheme模拟解释寄存机器语言已经完成了。通过这样编写程序来模拟更简单的寄存机器模型,可以观察我们的平时所写的程序在更底层的视角上是如何被机器理解的。除此之外,可以在此基础上修改我们模拟实现的细节,比如安置探针监测栈、寄存器的使用情况,增加指令的执行计数,可以更方便的监测寄存机器程序运行的性能,相关内容也可以见5.2.4 Monitoring Machine Performance的示例和讨论,我就不展开详细解读了。本文的重点还是放在怎样来实现寄存机器语言的模拟解释实现,希望大家能理解寄存机器模型并对怎样由一种语言构造另一种有新的感悟。谢谢阅读!


  1. 1.原课程材料可以在mit ocw找到,这里为了方便读者观看,直接链接到B站汉化版,真诚感谢Learning-SICP 项目团队为此做出的贡献。
  2. 2.在Steam, Google Pay, App Store等平台上均有正版发售,定价大约$5,鼓励有消费余力者支持一下开发团队。这类游戏的定位似乎是针对儿童的亲子娱乐/益智教学/编程启蒙,我个人阴差阳错在朋友推荐下接触了它,感觉确实是很不错的幼儿编程启蒙游戏,考虑到我本人在以后的人生中几乎必然找不到对象,也没有孩子,就没去细究应该怎么用于幼儿编程教学,恬不知耻的自己玩上了。