遅延評価をもうちょっと考える
いつthawしなくてはいけないのか，いつfreezeしなければいけないのか，ちょっと考えてしまったので書いておく．
セッティング
そもそもHaskellでは，値は2種類しかない．
ここではそう考える*1．
Haskellでの表現を書くと，
data Value = FunValue Id Expr | ConstrValue Id (List Value)
みたいな感じになる．
関数とデータコンストラクタが値であるのは理解してもらえると思う．リストとか整数とかはというと，これはデータコンストラクタで表現する．例えば，リストは
data List = Cons Int | Nil
というヴァリアントが定義されていると思えば，[1,2,3]はCons(1, Cons(2, Cons(3, Nil)))で表現できる．整数は，とりあえず自然数だけ考えると，
data Nat = Succ Nat | Zero
で表現できる．0はZeroで，3はSucc (Succ (Succ Zero))になる．
で舌の根も乾かぬうちに前言を撤回するんだけど，これにサンクを入れて，3種類，ということにする．
data Value = FunValue Id Expr | ConstrValue Id (List Value) | ThunkValue Env Expr
Thunkのthawはこんな感じ．
thaw :: Value -> Value thaw (ThunkValue env expr) = thaw (eval_expr env expr) thaw v = v
freezeっていうのは，つまり評価を遅延したい式exprと現在の環境envについて，
Thunkvalue env expr
とかいう値にすること．(ちなみに，これだけではcall-by-needにはなりません．毎回サンクがthawされてしまいます)
あと，サンクを作る処理の事をfreeze，サンクを具体的な値に評価することをthawと言う．lazy/forceと一緒．(どう違うんだろ)
いつthawするか
thawしなくてはいけない場面というのは，2種類ある．
- データコンストラクタとのパターンマッチング
- その他，処理系の都合
データコンストラクタとのパターンマッチングというのは，caseのときのこと．
case a of A -> y B x C -> x
とか書いてあったら，まずaの値がAであるかを確認しなくてはいけないし，AじゃなかったとしたらBであるかどうか確認しなくてはいけない．一つ注意しなくてはいけないのは，不可反駁なパターンの場合．つまりパターンが変数だった場合．
case 1/0 of n -> 100
とか書いてあった場合は，パターンは変数なので，即座に1/0のサンクをthawせずにnを束縛しなくてはいけない．この場合は，結局1/0は計算されないので，式全体の値は100になる．
処理系の都合，というのは「式が入力されたら値を表示する」とか，そういう話．これは各処理系で勝手にやれば良い．
あと本当はもう一つある．f xみたいな関数適用があったら，fの値が関数かどうか調べないといけない．このときもthawしないといけない．もっとも，フツーこれは型検査でチェックされるので，ちょっと感じは違うけど．
いつfreezeすれば良いか
逆にいつfreezeすれば良いかも考えてみる．実はさっきまで，よくわかってなくて，昨日の時点ではいらんところでfreezeしまくりのコードになってた．ちゃんと考えれば，自明だった．
そもそも，遅延評価というのは関数適用の引数をいつ評価するのか，という話である．
つまり，関数適用の時点で，引数の式の評価をfreezeしてやれば良い．
以上．簡単♪
データコンストラクタをどのように扱うか，というのは，ちょっと問題になるんじゃないかと思った．例えば，無限リスト
xs = 1:xs
の右辺．これ，MLの感覚だと，Consというデータコンストラクタに1とxsを与えるという式なんだけど，HaskellだとConsという関数に1とxsを適用するという式なんだった．つまり，データコンストラクタは関数適用で表現されているということ．これさえわかってしまえば，つまり右辺に出てくるxsの評価は，関数適用の引数であるということになって，ちゃんとfreezeされる．めでたし．
あと，本当はletで束縛する値の右辺の評価もfreezeしないといけない．これは，型を考えなれば，letは関数抽象+関数適用になることを考えれば自明だと思う．
let x = x in 100
と
let x = x in x
の動作を考えれば良い．
*1:当然だけど，こんなアホな実装をしている処理系は無いと思う
