hs2bf - SAM
G-machine->Brainfuckの中間言語を考えてみます。
G-machine?
Forthのような言語です。詳しくは初回に示した資料:
Implementing Functional Languages: a tutorial(pdf)
を読んでもらうことにして、とりあえず動作中のメモリはこんな風になっています。
SAM(Sequential Access Machine) *1
さてこのG-machine用のコードをBFに変換するわけですが、
直接は無理そうです。そこで中間言語を考える必要があるわけですが、欲しい機能としては
- そろそろ完全にimperativeに
- 複数のメモリ領域
- garbage collectionを実装できるくらいの低レベル
- 動的メモリ確保
3と4は矛盾するような気もしますが、それは後で説明します。
メモリ配置
このようにすることにします。前回と同様の考えかたです。
GCはheapを2つにしてコピー型にしようかと考えています。
stack(0)とstack(1)ですが、これはIdが2バイトの場合です。まともな速さで動くのは多分3バイトくらいまでなので決め打ちでもよいのですが、一応可変できるように考えておきます。
処理
今のところのイメージでは(あくまでもイメージです)
S0 S1 H0
pr ^@S0
alloc 1 flag
pushSC1
clr 1 flag
val 1 flag 2
while flag
inline eval flag
inline exec flag
delete flag
pr eval@S0/flag:1
while flag
alloc 2 addr
inline StackTop
move 2 $ addr
bank S0 H0
inline heapRef addr
alloc 1 temp
move 1 $ temp
move 1 temp $ flag
delete temp
delete addr
dispatch flag
0
...
...
3
move 1 $ flag
dispatch flag
2
halt
clr 1 $
4
move 1 $ flag
pr exec@S0
...
pr heapNew@H0/addr:2
alloc 2 temp
alloc 2 next
move 2 $ temp
move 2 temp $ next
while $
val 2 next -1
ptr 1
ptr 1
move 2 temp $ next
ptr -1
move 2 next temp
...
見ての通りほとんど生のBFと変わりませんが、メモリの扱いが大幅に強化されています(ちなみに$が現在位置です)。
一見関数呼び出しに対応しているようですが、inlineと書いてあるように再帰に対応していないので、単純な置換でflatなコード片に変換できます。
allocとdeleteはCでいうallocaのようなものですが、スタックに確保するのではなく必要な最大レジスタ数を調べて適当に割り当てるだけです。whileの内外を跨げないようになっています。
複数のメモリ領域(heapとstackなど)はbankコマンドで切り替えますが、実際には全ての命令について対応するバンクがコンパイル時に決定しているような制限を課すことにします。
あとはdispatchですが、これはいわゆるswitch文で、temporaryひとつを使って
dispatch f
0
X
1
Y
2
Z
は
clr 1 t while f val 1 f -1 dispatch f 0 Y 1 Z clr 1 t val 1 t +1 while t X clr 1 t
そして
clr 1 t while f val 1 f -1 clr 1 t while f val 1 f -1 Z clr 1 t val 1 t +1 while t Y clr 1 t clr 1 t val 1 t +1 while t X clr 1 t
のように再帰的に展開できます(多分)。
準備おk
このくらい強力であればGMの各コマンドとevalを実装可能な雰囲気なので、あとはコード生成を自動化するだけです。
またSAMからBFへの変換も(きっと)問題ないでしょう。
最初にHaskell->BF変換されるプログラムはどんな感じになるのか、楽しみです。
# 追記(2010/2/6): dispatchの展開を修正
*1:SAMという名前は適当なでっちあげ
