日々の流転

λ. Cleanの定関数と定グラフ

<URL:http://d.hatena.ne.jp/lethevert/20060601/p1> より。

Haskellはグラフ書き換えによる意味論を言語仕様に採用していないので、言語仕様上はCleanの定関数や定グラフのような概念は存在しない。というか、そもそもHaskellの言語仕様は実行メカニズムをほとんど規定していない。では実際の処理系ではどうかというと、例えばGHCでは(ある種の最適化後に)ラムダ抽象以外の形をしている定義は、すべてCleanでいうところの定グラフとしてコンパイルされる。

full laziness transformation

また、full laziness transformation (full laziness optimisation, let-floating) によって、局所的な定義が大域的な定義に引き上げられることがあるので、大域的か局所的かの区別も存在しない。 この full laziness transformation は大概は有用なのだが、時々困ったことをしてくれることもある。たとえば、以下のプログラムをコンパイルして実行するとメモリを食いつぶす。

f :: Int -> Int
f n = xs !! n
    where xs = [0..]

main :: IO ()
main =
    do print (f maxBound)
       print (f 0)

何故なら、full laziness transformation によって xs がトップレベルに引き上げられ、以下のようなプログラムと等しくなるため。結果、fが生きている限りxsも生きていることになり、メモリを食いつぶしてしまう。なお、「print (f 0)」を削除するとfがGCされxsもGCされるので、メモリを食いつぶすことはない(GHCではCleanと異なりCAFもGC対象になる)。

f :: Int -> Int
f n = xs !! n

xs :: [Int]  
xs = [0..]

main :: IO ()
main =
    do print (f maxBound)
       print (f 0)

では、こういうときにはどうするかというと、「-fno-full-laziness」というオプションを使って full laziness transformation を抑制してやる。全くしょーもないバッドノウハウである。

……とはいえ、Haskellはグラフ書き換え系を意味論として採用しておらず、おそらく今後とも採用しないことを考えると、言語自体による対応ではなくオプションやプラグマによって対応するというのは妥当なところだろう。個人的にはグローバルなオプションではなく、個々の定義に対して full laziness transformation を抑制するためのプラグマを付けられると良いと思うのだが……。

Cleanの定関数を模倣する

そして、Cleanの定関数のように「計算結果を共有せず毎回計算を行いたい」ときには、

• ダミーの引数(通常はユニット型)を加えた上で
• -fno-full-laziness で full laziness transformation を抑制すればよい

(FIXME: 具体例を追記)

これも面倒なので、プラグマがあると良いのではないかと思う。

λ. Turnabout

メモ。<URL:http://d.hatena.ne.jp/tapot/20050629> より。

これまでIEでGreasemonkeyのスクリプトを使うにはTrixieを使っていたが、これはTrixieよりも良さそうだ。