Concurrent Clean : カリー化と遅延評価と効率

[id:lethevert:20060911:p2]の続き。

add :: Int -> Int -> Int

という関数があって、

add 1 2

という関数適用があった場合、低レベルではどういう形で実行されるのかを考えてみます。
ここで低レベルの命令として、２種類の命令を定義します。

apply: 関数に引数を適用して、未評価のthunkを生成します。thunkを生成するには、関数と引数を組にしたデータをヒープに割り当てます。
eval: thunkを評価して、評価済みのthunkに変換します。変換は、ヒープ上に割り当てられたthunkのデータを直接書き換えることで行います。既にthunkが評価済みの場合は何も行いません。

この命令を使って上の関数適用を変換すると、

t0 <- apply add 1
t1 <- apply t0 2

と２回のapplyを使うことになります。これは、自動カリー化の機能があるため、addの定義が、

add x y = x + y
add x = \y = x + y

のいずれであるかが、型から知ることができないからです。
これに対し、型に表現されていない低レベルのアリティを知ることができれば、

t0 <- apply add 1 2

のようにapplyの回数を１回減らすことができます。applyの操作にはコストがかかるので、低レベルのアリティを知ることで、効率性を向上させることができます。
なお、遅延評価であるため、この関数適用に対しては、thunkを生成するところまでしか行われず、評価は値が必要となるまで遅延されています。

さらに、

add 1 (add 2 (add 3 4))

という式がすぐに値が必要となる文脈に置かれていたとして、アリティが２であることが分かっていたとすれば、

t0 <- apply add 3 4
t1 <- apply add 2 t0
t2 <- apply add 1 t1
eval t2

のように変換されるのですが、add関数の中でその引数は必ず利用されることが定義上決まっているので、引数の計算を遅延せずに関数適用の前に計算を済ませてしまうことができます。
次の命令を導入します。

t0 <- apply_eval add 3 4
t1 <- apply_eval add 2 t0
t2 <- apply_eval add 1 t1

このように、関数適用の前に引数を計算することで、applyの回数を減らすことができ、効率を上げることができます。