Positioning SICP 5: Computing with Register Machines
Positioning SICP 5: Computing with Register Machines #
作者：何岩，recreating.org出品，谢绝转载。
阅读SICP，站在Lisp发明者的上帝视角来思考：“我为什么要这么设计Lisp？”
0.前言 #
1）本章开始，进入硬件层面，如何用硬件来模拟Lisp解释器，本质上等价于，如何用硬件来模拟Lambda演算。只有连接到物理世界，计算才可能真正发生。
2）首先用寄存器系统来模拟简单计算过程
3）发明一种寄存器语言来描述寄存器系统的物理现实。
3）再用lisp语言来模拟寄存器语言，就等于是用lisp来模拟寄存器系统的运行，这样的目的是可以用文字来表达寄存器系统，否则用图像来表达真实的寄存器系统的设计成本太高。
4）再用寄存器语言构建出lisp解释器。就等于有一个硬件可以解释器lisp语言。就等于计算可以自动的发生在物理世界。
5）当然，本书缺少的一部分是，更底层的寄存器是如何用继电器来实现的。这部分可以看这本书《编码的奥秘》，探索到最底层，可以知道，所有的一切都由电磁效应这个物理规律所承载，但是电磁感应如何成立呢？
6）电磁感应就是光的解释器。
Chapter 5.1 Designing Register machines #
1.目的：用机器来模拟计算 #
例如：模拟gcd
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
用画图来表示寄存器机器，分为两个部分
1.Data path
(img)
2.Controller
(img)
这两个部分都是硬件，尤其是控制部分，也是由硬件的组合来表达。
2.用一种机器语言来描述寄存器机器 #
(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)
Chapter 5.2 A Register-Machine Simulator #
1.目的：用lisp来模拟寄存器机器语言 #
启发：如果可以用机器语言来描述一个机器，再用lisp编程语言来描述机器语言，就等于用计算机实现了对现实的模拟。
Why？为什么不直接用Lisp描述机器呢？为什么中间多了一个计算机语言？
因为计算机语言更接近机器的运行逻辑。
这就是分层思维，当然，lisp语言可以之间描述机器行为，但是会比较复杂。
这也是DLS的意义，领域语言。一个业务领域，对应一个领域语言。Lisp是实现领域语言的最佳选择。
2.效果演示如下： #
(define gcd-machine
(make-machine
‘(a b t)
(list (list 'rem remainder) (list ’= =))
‘(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)))
(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
3.如何实现Machine Language #
(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))
registers
(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))
The stack
(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 'puch) value))
The basic machine
(define (make-new-machine)
(let ((pc (make-register 'pc))
(flag (make-register 'flag))
(stack (make-stack))
(the-instruction-sequence ’()))
…
Chapter 5.4 The Explicit-Control Evaluator #
用硬件来实现Lisp的解释器
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 (op lambda?) (reg exp))
(test (op begin?) (reg exp))
(branch (label ev-begin))
(test (op application?) (reg exp))
(branch (label ev-application))
(goto (label unknown-expression-type))