Scheme - レジスタ計算機での計算(階乗とFibonacci計算機のシミュレーションとスタックの内容)

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• MIT/GNU Scheme (処理系)

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の5(レジスタ計算機での計算)、5.1(レジスタ計算機の設計)、5.1.4(再帰を実装するためのスタックの使用)、二重再帰、問題 5.5を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 5.5

階乗計算機のシミュレーション。(nの値が4の場合)

(assign continue (label fact-done))
(assign n (const 5))
;; n 4
(test (op =) (reg n) (const 1))
(save continue)
(save n)
;; stack continue: fact-done
;; stack n: 4
(assign n (op -) (reg n) (const 1))
;; n 3
(assign continue (label after-fact))
(goto (label fact-loop))
(test (op =) (reg n) (const 1))
(save continue)
(save n)
;; stack continue: fact-done after-fact
;; stack n: 4 3
(assign n (op -) (reg n) (const 1))
;; n 2
(assign continue (label after-fact))
(goto (label fact-loop))
(test (op =) (reg n) (const 1))
(save continue)
(save n)
;; stack continue: fact-done after-fact after-fact
;; stack n: 4 3 2
(assign n (op -) (reg n) (const 1))
;; n 1
(assign continue (label after-fact))
(goto (label fact-loop)
(test (op =) (reg n) (const 1))
;; base-case
(assign val (const 1))
(goto (reg continue))
;; (goto (label-after-fact))
(restore n)
(restore continue)
;; n 2
;; continue after-fact
;; stack n: 4 3
;; stack continue: fact-done after-fact
(assign val (op *) (reg n) (reg val))
;; val 2
(goto (reg continue))
;; (goto (label after-fact))
(restore n)
(restore continue)
;; n 3
;; continue after-fact
;; stack n: 4
;; stack continue: fact-done
(assign val (op *) 3 2)
;; val 6
(goto (label after-fact))
(restore n)
(restore continue)
;; n 4
;; continue fact-done
;; stack n:
;; stack continue:
(assign val (op *) 4 6)
;; val 24
(goto (label fact-done))

ということで、4の階乗は24。

Fibonacci計算機のシュミレーション。(nの値が4の場合。)

(assign n (const 4))
(assign continue (label fib-done))

(test (op <) (reg n) (const 2))
(save continue)
;; stack continue: fib-done
(assign continue (label afterfib-n-1))
(save n)
;; stack n: 4
(assign n (op -) (reg n) (const 1))
;; n 3
(goto (label fib-loop))
(test (op <) (reg n) (const 2))
(save continue)
;; stack continue: fib-done afterfib-n-1
(assign continue (label afterfib-n-1))
(save n)
;; stack n: 4 3
(assign n (op -) (reg n) (const 1))
;; n 2
(goto (label fib-loop))
(test (op <) (reg n) (const 2))
(save continue)
;; stack continue: fib-done afterfib-n-1 afterfib-n-1
(assign continue (label afterfib-n-1))
(save n)
;; stack n: 4 3 2
(assign n (op -) (reg n) (const 1))
;; n 1
(goto (label fib-loop))
(test (op <) (reg n) (const 2))
;; (label immediate-answer)
(assign val (reg n))
;; val 1
(goto (reg continue))
;; continue after-fib-n-1
(restore n)
(restore continue)
;; n 2
;; continue afterfib-n-1
;; stack n: 4 3
;; stack continue: fib-done afterfib-n-1
(assign n (op -) (reg n) (const 2))
;; n 0
(save continue)
;; stack continue: fib-done afterfib-n-1 afterfib-n-1
(assign continue (label afterfib-n-2))
(save val)
;; stack val: 1
(goto (label fib-loop))
(test (op <) (reg n) (const 2))
;; immediate-answer
(assign val (reg n))
;; val 0
(goto (reg continue))
;; continue afterfib-n-2
(assign n (reg val))
;; n 0
(restore val)
;; val 1
;; stack val:
(restore continue)
;; continue afterfib-n-1
;; stack continue: fib-done afterfib-n-1
(assign val (op +) (reg val) (reg n))
;; val 1
(goto (reg continue))
;; continue after-fib-n-1
(restore n)
;; n 3
;; stack n: 4
(restore continue)
;; continue: afterfib-n-1
;; stack continue: fib-done
(assign n (op -) (reg n) (const 2))
;; n 1
(save continue)
;; stack continue: fib-done afterfib-n-1
(assign continue (label after-fib-n-2))
(save val)
;; stack val: 1
(goto (label fib-loop))
(tst (op <) (reg n) (const 2))
;; immediate-answer
(assign val (reg n))
;; val 1
(goto (reg continue))
;; continue after-fib-n-2
(assign n (reg val))
;; n 1
(restore val)
;; val 1
;; stack val:
(restore continue)
;; continue afterfib-n-1
;; stack continue: fib-done
(assign val (op +) (reg val) (reg n))
;; val 2
(goto (reg continue))
;; continue afterfib-n-1
(restore n)
;; n 4
;; stack n:
(restore continue)
;; continue fib-done
;; stack continue:
(assign n (op -) (reg n) (const 2))
;; n 2
(save continue)
;; stack continue: fib-done
(assign continue (label afterfib-n-2))
(save val)
;; stack val: 2
(goto (label fib-loop))
(test (op <) (reg n) (const 2))
(save continue)
;; stack continue: fib-done afterfib-n-2
(assign continue (label afterfib-n-1))
(save n)
;; stack n: 2
(assign n (op -) (reg n) (const 1))
;; n 1
(goto (label fib-loop)
(test (op <) (reg n) (const 2))
;; immediate-answer
(assign val (reg n))
;; val 1
(goto (reg continue))
;; continue afterfib-n-1
(restore n)
;; n 2
;; stack n:
(restore continue)
;; continue afterfib-n-2
;; stack continue: fib-done
(assign n (op -) (reg n) (const 2))
;; n 0
(save continue)
;; stack continue: fib-done afterfib-n-2
(assign continue (label afterfib-n-2))
(save val)
;; stack val: 2 1
(goto (label fib-loop))
(test (op <) (reg n) (const 2))
;; immediate-answer
(assign val (reg n))
;; val 0
(goto (reg continue))
;; continue afterfib-n-2
(assign n (reg val))
;; n 0
(restore val)
;; val 1
;; stack val: 2
(restore continue)
;; continue afterfib-n-2
;; stack continue: fib-done
(assign val (op +) (reg val) (reg n))
;; val 1
(goto (reg continue))
;; continue afterfib-n-2
(assign n (reg val))
;; n 1
(restore val)
;; val 2
;; stack val:
(restore continue)
;; continue fib-done
;; stack continue:
(assign val (op +) (reg val) (reg n))
;; val 3
(goto (reg continue))
;; continue fib-done

ということで、4番目のフィボナッチ数は3。

Schemeで、それぞれの結果が正しいか確認。

コード(BBEdit)

sample.scm

(define (factorial n)
  (if (= n 1)
      1
      (* (factorial (- n 1)) n)))

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

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

$ scheme
MIT/GNU Scheme running under MacOSX
Type `^C' (control-C) followed by `H' to obtain information about interrupts.

Copyright (C) 2011 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Image saved on Saturday October 26, 2013 at 11:02:50 PM
  Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118
  Edwin 3.116

1 ]=> (load "./tmp.scm")

;Loading "./sample.scm"... done
;Value: fib

1 ]=> (factorial 4)

;Value: 24

1 ]=> (fib 4)

;Value: 3

1 ]=> ^D
End of input stream reached.
Moriturus te saluto.
$