SICP 5 Computing with Register Machines - プログラミング再入門

ノート

プログラムの実行環境についてsubstitution model、environment model、metacircular evaluatorと見て来たが、一番核心の部分はベースのLispシステムに委ねて解説されていない。

この章ではプロセッサとそのマシン語に相当するレジスタ・システムをLisp上に実装してプログラムを実行する。

5.1 Designing Register Machines

データフローダイヤグラムの様なデータパスダイヤグラム。

レジスタは四角
データの代入は矢印に⊗マーク（このマークには名前が付いていて、ボタンとして働く）
定数は三角
演算は台形
テスト（即ち述語演算？）は丸

述語演算の結果についてはこの図では表現されない。またボタンは正しい順序で押される必要がある。これを別のコントローラーダイヤグラム（どう見てもフローチャート）で記述する。四角のアクションの所にはボタンの名前が書いてある。

Exercise 5.1

や*の演算の入力に対して出力をそのまま代入しても良いものなのか良く分からないので、取り敢えず中間の変数を置く事にする。

5.1.1 A Language for Describing Register Machines

データパスダイヤグラムとコントローラーダイヤグラムをS式で表現する。
また、ボタンは名前だけでは内容が分からないので、そのアクションが分かる様な式にする。

Exercise 5.2

動かしてみないと正しいのか検証出来ないけど。

'(data-paths
  (registers
   ((name n))
   ((name counter)
    (buttons ((name counter<-1) (source constant 1))
             ((name counter<-t1) (source register t1))))
   ((name product)
    (buttons ((name product<-1) (source constant 1))
             ((name product<-t2) (source register t2))))
   ((name t1)
    (buttons ((name t1<-+) (source operation +))))
   ((name t2)
    (buttons ((name t2<-*) (source operation *)))))
  
  (operations
   ((name +)
    (inputs (constant 1) (register counter)))
   ((name *)
    (inputs (register conter) (register product)))))
  
'(controller
   (assign counter (const 1))
   (assign product (const 1))
   test-counter
   (test (op <) (reg counter) (reg n))
   (branch (label factorial-done))
   (assign t1 (op +) (const 1) (reg counter))
   (assign t2 (op *) (reg counter) (reg product))
   (assign (reg counter) (reg t1))
   (assign (reg product) (reg t2))
   (goto (label test-counter))
   factorial-done)

Actions

readとprintと言うアクション（演算）を導入。
>
But read does not take inputs from any registers; its value depends on something that happens outside the parts of the machine we are designing.

Though it has an effect, this effect is not on a part of the machine we are designing.<
『IOはプログラム（マシン）とは別の世界で起きる』と言う言い回しが関数型言語（と言うかHaskell）的。

assign, test, branch, gotoに加えてperformを導入。

5.1.2 Abstraction in Machine Design

マシンのデザインには常に詳細が隠されたプリミティブが存在する。が、基本的にはこれらは展開可能である。

Exercise 5.3

まずgood-enough?とimproveをプリミティブとした単純な実装。引数には現れないがどちらもxを入力としている。

good-enough?を-（引き算）、abs、squareを比較演算<をプリミティブとして実装する。

述語を実装する時の最後の部分をどう表現するのが良いのか良く分からない。

improveをaverageと/をプリミティブとして実装する。

全体をあわせると。

コードにすると

#lang racket
'(data-paths
  (registers
   ((name x))
   ((name guess)
    (buttons ((name guess<-1.0) (source constant 1.0))
             ((name guess<-average) (source operation average))))
   ((name d)
    (buttons ((name d<-div) (source operation /))))
   ((name s)
    (buttons ((name s<-square) (source operation square))))
   ((name diff)
    (buttons ((name diff<-sub) (source operation -))))
   ((name ad)
    (buttons ((name ad<-abs) (source operation abs))))
  
  (operations
   ((name /)
    (inputs (register x) (register guess)))
   ((name average)
    (inputs (register guess) (register d)))
   ((name square)
    (inputs (register guess)))
   ((name -)
    (inputs (register x) (register s)))
   ((name abs)
    (inputs (register diff)))
   ((name >)
    (inputs (register ad) (constant 0.001))))))
  
'(controller
    (assign guess (const 1.0))
  good-enough?
    (assign s (op square) (register guess))
    (assign diff (op -) (register x) (register s))
    (assign ad (op abs) (register diff))
    (test (op >) (const 0.001) (register ad))
    (branch (label sqrt-done))
    (assign d (op /) (register x) (register guess))
    (assign guess (op average) (register d) (register guess))
    (goto (label good-enough?))
  sqrt-done)

ここまでの所、何も動作させていないので合ってるのかどうなのかサッパリ分からない。