グラフ簡約の謎 (「ふつける」勉強会 より)
今日は趣向を変えてオフラインで「遅延評価」の章。
一番の収穫は、機動戦士ガンダム0079カードビルダー(http://gundam-cardbuilder.com/index_c.html)情報だったりする気もしないでもないが、「グラフ簡約」のもう少し詳細な仕組みは気になるところ。
グラフ簡約の疑問点は、「同じ計算式だがソース上は独立している」式はグラフ上の同じノードとして解釈するのか否か？というもの*1。
例えば、
let a = 1 + 3 in let b = 1 + 3 in a + b
という式があった時に、最後の行でのaとbの値は別々に評価する、つまりグラフ上では違うノードとして解釈するのか、あるいは1+3という「同じ」式だから同じタイミングで評価する、つまりグラフ上では同じノードとして解釈するのか？
あの場では「ソースコード上で、"同じ"部分しか同じグラフのノードとして解釈されないので、別々に評価される」という旨のことを主張した(つもりだ)が、同じ関数に同じ引数を与えて呼びだしたときは、同じ値返すのが決まってるんだから、値を覚えといてくれないと嬉しくない*2気はしてきた。別々に評価されるとすると、その場合では関数が個別に評価されることになる(よね？)。でも、後者の仕組みを実現するには、遅延評価のせいで関数呼びだし時には引数の値が同じかどうか判断できないのがネックになるよなあ。
あるテストコードを処理系に実行させることで、処理系内でどちらの方法をとっているのか判定できるだろうか？この違いで計算量が大幅に代わってくるコードは書ける気はするが。
