Concurrent Clean: 評価戦略によるコンパイル結果の違い

eagerとlazyの２種類の評価戦略によってコンパイル結果がどのように変わるかを考えてみる。サンプルは次のCleanプログラムで、コンパイル結果はシンプルなスタックマシンを想定した疑似アセンブリで記述する。

test = add (add 1 2) 3
add x y = x + y

eagerの場合は、addの呼び出しの前に引数をすべて評価してしまうので、次のような結果になる。

test:
    pushInt 3 // スタックに3を積む
    pushInt 2
    pushInt 1
    call add 2 // 2つの引数を使ってaddを呼び出す
    call add 2
add:
    addInt // 2つの整数を足し算する

lazyの場合は、addの呼び出しの引数はすべてThunkにするので、buildというThunkを生成する命令を用いて次のようにコンパイルされる。testの最後にevalが入っているのは、testの最終的な評価結果が評価後の値になるようにするためだ。

test:
    buildInt 3 // 評価すると3になるThunkを作って、スタックに積む
    buildInt 2
    buildInt 1
    build add 2 // 2つの引数を使ってaddを呼び出すThunkを生成し、スタックに積む
    build add 2
    eval 0 // スタックの0番目のThunkを評価する
add:
    eval 1
    eval 0
    addInt

eagerとlazyが混ざる場合は、ちょっとややこしくなる。例えば、addの１つ目の引数 x がlazyで、２つ目の引数 y がeagerの場合は、次のようになる。Thunkに含める場合は、eagerな引数もThunkにしておかないと正しい順序で評価されない。そのため、Thunkの評価時には、Thunkにしたeagerな引数を評価するための追加の命令が必要になる。

test:
    pushInt 3
    buildInt 2
    buildInt 1
    build add 2
    call add 2
add_eval: // Thunkの評価用のエントリー
    eval 1
add: // 直接callしたときのエントリー
    eval 0
    addInt