続・正格性解析

Haskell Clean

GHCも正格性の解析を行っているということを
本体サイトの掲示板やこちらのほうでご指摘頂いた。
いいかげんなことを書いて申し訳ないです。
こう、書けば書くほどボロが出るのがこのページでして…。
というわけで、もうちょっとちゃんと考えてみることにした。


foldl'とか、seqの存在から誤解をしてしまっていたのかもしれない。
これらはCleanで言うところの正格性の明示に当たるのだろうか。
掲示板で教えていただいたところによれば、具体的には

sum' = foldl (+) 0

このあたりが最適化されるとのことで、
実際にやってみたところ、

main = print $ sum' [1..1000000]

これが確かにちゃんとあふれずに計算できた。
ちなみに、最適化オプションなしだとあふれてしまった。


しかし、以前書いたHaskell版wcがうまく行かなかったのも事実である。
以前書いたものは多少前回のCleanのソースより解析されにくいかもしれないので、
今回、Cleanのものとほとんど同じようなwcを実装しなおして
再度GHCにかけてみた。
(どうでもいいけど、もう何度wcを実装したことやら…)

main = do
  (nl,nw,nc) <- wc stdin
  putStrLn $ show nl ++ " " ++ show nw ++ " "++ show nc

wc f = inner 0 0 0 True where
  inner nl nw nc prev = do
    b <- hIsEOF f
    if b
      then return (nl,nw,nc)
      else do
        c <- hGetChar f
        let nprev = isSpace c
            nnl   = nl + if c=='\n' then 1 else 0
            nnw   = nw + if prev&&not nprev then 1 else 0
            nnc   = nc + 1
        inner nnl nnw nnc nprev

EOF検出のために多少冗長であるが、基本的に同じものである。
これを最適化オプションつきでコンパイルして実行したところ、
ヒープがあふれてしまった。このレベルでは最適化できないのだろうか。


ちなみに、上のコードはinnerという関数について、
すべての代替部にてnl,nw,ncの3つの引数が評価されているので
この3つは正格な引数だといえる。
nprevであるが、これはnnwの評価時に評価する必要があるので、
ここがnwが遅延しなければnprevも遅延することは無い。
そういうわけで、Cleanではこういうコードが最適化できて、
Haskellではこういうコードが最適化されないということは、
GHCは正格性解析を行うがCleanが行っているほどではない、
というように思われる。


そこで、CleanとGHCの境界はどこにあるのか?
或いは本当にCleanの方がアグレッシブな最適化を行っているのかどうか
私なりに実験してみることにした。


まず、GHCにて最適化できたfoldlの例に対して。
適当にfoldlを定義してみる。

my_foldl f v []     = v
my_foldl f v (x:xs) = my_foldl f (f v x) xs

これを用いて、

main = print $ sum'' [1..1000000]
sum'' = my_foldl (+) 0

こうしたところ、これはどうも最適化できなかったようである。
じゃあ、GHCでのfoldlの定義はどうなってるのか?ということで、
GHCのソースからfoldlの定義を引っ張ってきてみた。

ghc_foldl        :: (a -> b -> a) -> a -> [b] -> a
ghc_foldl f z xs = lgo z xs
	     where
		lgo z []     =  z
		lgo z (x:xs) = lgo (f z x) xs

GHCでの定義はこうなっていた。
fをたらいまわしにするのを嫌っただけにも見えるが…。
とりあえずこれを使ってsumを作ると、なんと、
というか当たり前というか、最適化された。
これは一体全体どういうことなんだろうか。


疑問を引きずりつつ、今度はCleanのほうを調べてみる。
まずは、Cleanでの小手調べを。

Start = my_sum [1..1000000]
my_sum = foldl (+) 0

これは当たり前のように実行できた。
次に、foldlの定義である。

my_foldl f v [] = v
my_foldl f v [x:xs] = my_foldl f (f v x) xs

Haskell版と同じである。
Cleanならいけるかな…と思って実行したのだが、
なんとこれが最適化されないのである。
Heapがあふれて計算できないと出た。


では、Haskellでの定義のようにすればどうなのか?

my_foldl2 f v xs = lgo v xs
where
  lgo v [] = v
  lgo v [x:xs] = lgo (f v x) xs

定義はこの通り。これも全くの同一であるが…
果たして実行してみたところ、なんとこれも最適化されないのである。
このあたりでよく分からなくなる。
GHCとCleanでの正格性解析には得手不得手があるのか。


では、気になるのはCleanのfoldlの定義である。
Cleanでのfoldlの定義は次のようになっていた。
(名前とかは実物の通りではありませんが…)

clean_foldl op r l :== lgo r l
where
  lgo r []    = r
  lgo r [a:x] = lgo (op r a) x

これはGHCでのfoldlの定義とほとんど同じなのだが、
":==" なる胡散臭い記号の部分がGHCのものと異なる。
これは確かシノニムを表していたはずだが、
(型の定義とか、定数の定義とかで)
ここを:==にすることで=とどのように違うのかは残念ながら私には分からない。
しかし、これがCleanの正格性解析に影響を与えているのは間違いない。


Cleanにて、foldlの型は(ソース中ではコメントアウトされていたが)

foldl :: (.a -> .(.b -> .a)) .a ![.b] -> .a

このように成っていた。
(ピリオドってなんだったっけ…こういうのがいっぱいあるから
Haskellに気持ちが移っちゃったんだよなぁ…)
第三引数が正格なのは自明としても、
第二引数が正格じゃないのが興味深い。
ぱっと見たときrは正格になると思ったのだが、
第一代替部(lがのとき)では普通にrが値になっているが、
第二代替部(lがじゃ無いとき)ではrはopの引数として用いられている。
opが第一引数に対して正格ではない場合、
foldlの第二引数は正格では無いわけで、
結局foldlの第二引数を正格ということは出来ず、
このCleanの定義はやはり正しいようである。


と、ここまで考えて若干話が見えてきた。
単純に正格性の判断を関数に対して行う場合、
Cleanでのfoldl程度にしか行えない。
つまり、例えば+が適用されて

foldl (+) v (x:xs) = foldl (+) ((+) v x) xs

このようになった場合でも、"foldlが"第二引数に対して正格でないために
正格に評価されなくなってしまう。
(つまり、部分適用された式に対してワザワザ正格性の解析を
やり直したりはしないということだろう)


ところが、GHC版のHaskellの定義では事情が異なる。

ghc_foldl f z xs = lgo z xs
	     where
		lgo z []     =  z
		lgo z (x:xs) = lgo (f z x) xs

これに(+)を適用した場合、

lgo z xs
  where
    lgo z []     =  z
    lgo z (x:xs) = lgo ((+) z x) xs

このように成るが、ここでのlgoの引数の正格性は、
(+)が2つの引数ともに正格である、つまり、+の型がClean流に書くのなら

(+) :: !Int -> !Int -> Int

とできることにより、
lgoがzに対して正格であると判断することが出来る。


というわけで、foldlの定義をこのようにしないと
最適化がかからない仕組みは自分なりになんとなく理解したのだが、
(Cleanで:==にしなければならない理由はイマイチ分からないが…)
この見極めは相変わらず難しいように思う。
GHCでwcが最適化されない理由は結局分からず。
結局のところやはりCleanのほうがアグレッシブといえるのだろうか。


ただしまぁ、Cleanで適当に書いて最適化されなかったとしても、

my_foldl :: (a b -> a) !a ![b] -> a
my_foldl f v [] = v
my_foldl f v [x:xs] = my_foldl f (f v x) xs

こう書いてやればある程度は問題ないので、
(元のプログラムと若干停止性に違いが出てしまうような気がするが…)
Cleanのほうがやはり速いプログラムを書きやすいといえるだろう。