2011年5月19日木曜日

個人用電卓のプログラミング

またThe Art of Happy Hacking Calculator Programmingの話だ. 2年ほど前のこのブログに, 私のデザインしたHappy Hacking Calculatorのプログラミングの話を何回か書いた. 例えば1から10までの和のプログラムは,

(0Ua"N+U1-"_aG^N)X=

factorialは

("_6_G1+5_"G"1-!*)!=

という具合いである. Gの命令について復習すると, スタックの上から2段目の内容が負なら, プログラム制御をスタック最上段の数だけバックする(左へ進む), 非負ならそのまま進むというのであった. そこで, プログラムを書くのに面倒なのは, 飛び先までの長さの計測である. factorialのプログラムの左から5文字目のGはスタックの最上段に-6があるので, その下が負なら, 右へ(1+5_"G)の6文字を飛び越えることを示す. つまり右のGの次の"のところだ. 当時のプログラムでは, 長さのところを空けておき, 他が出来てから手作業で長さを数えていた.



またこの図の左のようだと, G命令から10文字左へ飛び, 右のようだと9文字左へ行く. それが同じ場所である. 従って, 工夫によってはプログラムが短く出来る.

これをなんとか自動化したい, つまりコンパイラを書きたいとかねがね考えていた.

飛び先までの間に条件付きのbranch命令や無条件のjump命令があると, そのパラメータの文字数が未定であったりするので, 自縄自縛(という表現が適切かな)になり, コンパイラの書き方が決らなかった.

最近, 思いついた方法があり, それでプログラムを生成してみたが, なんとかなりそうである. そのことを書きたい.

コンパイルされるプログラムはこんな形をしている.

(define sum '(0 up 10 'foo dup down + up 1 - dup neg
(branch foo) pop down 'exit))

(define factorial
'(dup neg (branch bar) 1 ent (branch exit) 'bar
dup 1 sub ! * 'exit))

(define ackermann '(
dup 1 - (branch a) exch dup 1 - (branch b)
exch dup 2 - (branch c)
up dup 1 - exch down 1 - A A (jump exit)
'c pop pop 2 ent (jump exit)
'b pop 2 * (jump exit)
'a pop pop 0
'exit
))

sumが10までの和のプログラムで, クォートされているリスト内がプログラム本体である. 0とか10は定数で, そのまま文字に置き換わる. 今の版ではコンパイラの関数によって十進だったり十六進数だったりする. up, dup, down, +, -, negなどが, プログラムの命令だ. (このAckermann関数は, SICPのex1.10にあるものだ.)

(branch foo)はfooへのbranch命令を挿入することを示す. その飛び先は'fooのところである. jump命令では, スタックの判定用に無理に負の数をおいて常に飛ぶのである.



それぞれの図の箱は, 長さ固定のプログラム. その間のbmやその間jmはbranchやjump命令. 矢印はそこから飛ぶ飛び先で, lnは飛ぶ長さである.
bmやjmは, 対応する飛ぶ距離lnの文字に変換した長さlに,

a. 左へのbranchはlの次にGの1文字,
b. 右へのbranchはlの次に_とGの2文字,
c. 左へのjumpは1_の2文字とlの次にGの1文字,
d. 右へのjumpはlの次に_"Gの3文字
をつける. つまり追加文字数は, a, b, c, dのそれぞれで, 1, 2, 3, 3である.

ackermannのプログラムは, 二進十進(あるいは十六進)変換を

(define (f n)
(if (< n 10) 1 (if (< n 100) 2 3)))

と定義し,

(define b0 0)
(define b1 0)
(define b2 0)
(define j0 0)
(define j1 0)
(define j2 0)

(define (iter)
(let* ((l0 (+ 4 b1 4 b2 10 j0 4 j1 3 j2))
(l1 (+ 4 b2 10 j0 4 j1))
(l2 (+ 10 j0))
(l3 (+ 4 j1 3 j2 3))
(l4 (+ 3 j2 3))
(l5 3)
(c0 (+ (f l0) 2))
(c1 (+ (f l1) 2))
(c2 (+ (f l2) 2))
(k0 (+ (f l3) 3))
(k1 (+ (f l4) 3))
(k2 (+ (f l5) 3)))
(if (equal? (list c0 c1 c2 k0 k1 k2) (list b0 b1 b2 j0 j1 j2))
(list b0 b1 b2 j0 j1 j2 l0 l1 l2 l3 l4 l5)
(begin (set! b0 c0) (set! b1 c1) (set! b2 c2)
(set! j0 k0) (set! j1 k1) (set! j2 k2) (iter)))))

のプログラムで(iter)とすると,
 (4 4 4 5 5 4 47 32 15 19 10 3)

が得られる. したがってb047_G, b132_G, b215_G, j019_"G, j110_"G, j23_"G となる.

facotorialは

(define (iter)
(let* ((l0 (+ 2 b1))
(l1 5)
(c0 (+ (f l0) 2))
(c1 (+ (f l1) 2)))
(if (equal? (list c0 c1) (list b0 b1))
(list b0 b1 l0 l1)
(begin (set! b0 c0) (set! b1 c1) (iter)))))

で,
(3 3 5 5)

が得られるから, b05_G, b15_G でよい.

10までの和は,

(2 9)

が得られ, b0はすなわち9Gとなる.

以上は, それぞれの関数用のプログラムを実行した例だが, プログラムの半ばコンパイルした中間出力のリストを使うことも出来るようになった.

ackermann関数の例では, bmやjmをリストにし, プログラムのブロックをその長さlnで置き換えた中間出力

((3 "\"1-") (b a 0 0) (4 ":\"1-") (b b 0 0) (4 ":\"2-") (b c 0 0)
(10 "U\"1-:N1-AA") (j exit 0 0) c (4 "^^2E") (j exit 0 0)
b (3 "^2*") (j exit 0 0) a (3 "^^0") exit))
から

"1-47_G:"1-32_G:"2-15_GU"1-:N1-AA19_"G^^2E10_"G^2*3_"G^^0

を得るプログラムは走るようになっているが, まだ改善の余地だらけで, 公開ははばかられる.

0 件のコメント: