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

遅延評価をもうちょっと考える

HaskellHackathon

いつ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

で表現できる.0Zeroで,3Succ (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というデータコンストラクタ1xsを与えるという式なんだけど,HaskellだとConsという関数1xsを適用するという式なんだった.つまり,データコンストラクタは関数適用で表現されているということ.これさえわかってしまえば,つまり右辺に出てくるxsの評価は,関数適用の引数であるということになって,ちゃんとfreezeされる.めでたし.

あと,本当はletで束縛する値の右辺の評価もfreezeしないといけない.これは,型を考えなれば,letは関数抽象+関数適用になることを考えれば自明だと思う.

let x = x in 100

let x = x in x

の動作を考えれば良い.

*1:当然だけど,こんなアホな実装をしている処理系は無いと思う