ブログに書いてみるとよく分からなくなってきました 🙃
Haskell-jp で回答をもらいました。
@lotz84_ さんの記事や GHC のプロファイルに出てくる CAF がよく分かってなかったのをまとめる。
fact のメモ化
lotz さんの記事の階乗 fact 関数を題材にする。
fact :: Int -> Integer fact 0 = 1 fact n = fromIntegral n * fact (n-1)
lotz さんの記事よれば、次の実装だとメモ化されるとのこと。
-- | 関数をメモ化する関数 memoize :: (Int -> a) -> Int -> a memoize f = (map f [0..] !!) fact :: Int -> Integer fact = memoize fact' where fact' 0 = 1 fact' n = fromIntegral n * fact' (n-1)
な、なんで……
1つめを fact1、2つめを fact2 として GHCi で確かめてみる。
> :set +s > fact1 50000 `seq` pure () (2.44 secs, 2,605,979,968 bytes) > fact1 50000 `seq` pure () (2.41 secs, 2,605,979,968 bytes) > fact2 50000 `seq` pure () (2.50 secs, 2,613,580,040 bytes) > fact2 50000 `seq` pure () (0.00 secs, 88,432 bytes)
確かに fact2 の2回めの評価はすぐに終わっている。
簡単のために fact2 を次のように書き換える。
fact3 :: Int -> Integer fact3 = (map fact' [0..] !!) where fact' 0 = 1 fact' n = fromIntegral n * fact' (n-1)
> fact3 50000 `seq` pure () (2.47 secs, 2,611,180,024 bytes) > fact3 50000 `seq` pure () (0.00 secs, 88,432 bytes)
同じようにメモ化されている。
では次のように書き換えると？ポイントフリー化されていたのを引数を明示するようにした。
fact4 :: Int -> Integer fact4 x = map fact' [0..] !! x where fact' 0 = 1 fact' n = fromIntegral n * fact' (n-1)
> fact4 50000 `seq` pure () (2.58 secs, 2,619,180,432 bytes) > fact4 50000 `seq` pure () (2.59 secs, 2,619,180,432 bytes)
メモ化されない。
もう1つ、ラムダ式で定義すると？
fact5 :: Int -> Integer fact5 = \x -> map fact' [0..] !! x where fact' 0 = 1 fact' n = fromIntegral n * fact' (n-1)
> fact5 50000 `seq` pure () (2.57 secs, 2,619,180,432 bytes) > fact5 50000 `seq` pure () (2.52 secs, 2,619,180,432 bytes)
メモ化されない。
何か特別な形である必要があるみたい。
Constant Applicative Form・Super Combinator
Haskell High Performance Programming によると、その特別な形は Constant Applicative Form（定作用形）というらしい。プロファイルを取ると Cost Centre に CAF と書かれてあるやつ。
とりあえず、項がラムダ式であるとダメだそうなので fact5 は CAF ではない。
項がスーパーコンビネーターであるとは、項が定数もしくは、項がコンビネーターであり全ての部分項がスーパーコンビネーターであるものである。
これは次の定義と同値だそう。
任意の
\x1 x2 … xn -> E（Eはラムダ式でない。。）の形の式で次の場合に限りそれはスーパーコンビネーターである。
Eにおける自由変数はx1,x2, …xnのみで、かつEに出現するラムダ式は全てスーパーコンビネーターである。
fact3 が CAF であるかを確認する。
fact3 :: Int -> Integer fact3 = (map fact' [0..] !!) where fact' 0 = 1 fact' n = fromIntegral n * fact' (n-1)
map fact' [0..] !!は定数でないため部分式が全てスーパーコンビネーターであればよい。部分項である
mapは、あ、あれ？定数でないしスーパーコンビネーターでもなくただの変数では……？2つめの定義においてもx1,x2, …xn以外の自由変数だし……
…………
……
…
いかがでしたか？関数がメモ化関数になるためには定義が CAF でないといけないようです 😎
なんで fact3 が CAF なのか教えてください 🙏
Haskell-jp で回答をもらいました。
（Markdown モードで引用の中でコードブロック書くのどうやるんだ……）
@mizunashi-mana
スーパーコンビネータは，一般の文脈では確かにコンビネータで部分項がスーパーコンビネータであるものを指しますが， CAF の文脈では，
- ラムダ式でない
- ローカル関数が全てグローバルに出しても問題ない定義になっている
だと思うのが良いと思います．厳密には，
https://gitlab.haskell.org/ghc/ghc/wikis/commentary/rts/storage/gc/CAFs
に書いてある通り，要はサンクとなる static closure のことを指しています．
ところでメモ化の要因は，確かに fact3 が CAF であることもありますが，一番の要因として， Core では関数適用の引数は let を通して変数に束縛されることになるので，実際にはこのプログラムは
fact3 = (!!) fact3' where fact3' = map fact' l l = [0..] fact' 0 = 1 fact' n = ...
みたいなものと等価になります (厳密にはこれも怪しいですが) ．で， fact3' が CAF となるからというのが大きいですね (なお実際 GHC 8.6.5 では fact3' が floating out されていて， fact3 自体は最終的に eta expand されて fact3 = \x -> (!!) fact3' x という形になっていました)
