SICP

Exercise 5.13. Modify the simulator so that it uses the controller sequence to determine what registers the machine has rather than requiring a list of registers as an argument to make-machine. Instead of pre-allocating the registers in make-machine, you can allocate them one at a time when they are first seen during assembly of the instructions.

这个题很有意思！看上去我们需要修改很多东西，但仔细想想，我们只有在找 register 时才会碰到 register 的分配问题。所以只需要修改一点点代码就可以。

首先，我们去掉 make-machine 中 regs 参数，

(define (make-machine ops controller-text)
  (let ((machine (make-new-machine)))
    ((machine 'install-operations) ops)
    ((machine 'install-instruction-sequence)
     (assemble controller-text machine))
    machine))

然后在 make-new-machine 中 lookup-register 被调用时要么返回已有的寄存器，要么分配新的寄存器。

      (define (lookup-register name)
        (let ((r (assoc name regs)))
          (if r
              (cdr r)
              (begin
                (allocate-register name)
                (cdr (assoc name regs))))))

Done! 下面进行测试。

(load "../testframe.scm")

(define test-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)
   (restore n)
   (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))

(define test-machine
  (make-machine
   (list (list '< <)
         (list '- -)
         (list '+ +))
   test-controller))

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

(set-register-contents! test-machine 'n 10)
(start test-machine)
(assert= (get-register-contents test-machine 'val)
         (fib 10))

SICP 全笔记