読者です 読者をやめる 読者になる 読者になる

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という名前は適当なでっちあげ