2011年4月26日火曜日

【まとめ】Haskellでの正格評価とWHNF


Haskellは遅延評価を特徴とする言語ですが、seq関数や!パターンを使うことで正格評価をさせることもできます。

ただし、最終的な値まで完全に評価(deepseq)されるわけではなく、WHNF(Week Head Normal Form)に簡約されるまでの評価です。

WHNFとは、簡単にいうと、以下のいずれかの形をもつ式です。
  • プリミティブである
  • 式の一番左にデータコンストラクタがある
  • 式の一番左にλがある
正格評価を使ったときにコードの挙動がどう変わるのか、具体的には以下のようになります。

ケース1(遅延評価)

$ cat case1.hs
loop 0 i = i
loop n i = loop (n-1) (i+1)

n = 100000000

main = let x = loop n 0
       in putStrLn "1"
$ ghc --make -O case1.hs
$ time ./case1
1

real    0m0.008s
user    0m0.001s
sys     0m0.003s
遅延評価の場合、let式の中のxは評価されません。評価されるのは文字の出力のみのため、実行時間はごくわずかです。

ケース2(xを正格評価)

$ cat case2.hs 
loop 0 i = i
loop n i = loop (n-1) (i+1)

n = 100000000

main = let !x = loop n 0
       in putStrLn "1"
$ ghc --make -O -XBangPatterns case2.hs
$ time ./case2
1

real    0m3.470s
user    0m1.873s
sys     0m0.032s
xに正格フラグ(!)を付けて正格評価にします。xは実際には使われませんが、評価はされるため、その分実行時間が長くなっています。

ケース3(代数データ型を使い、遅延評価)

$ cat case3.hs
data X = X Int

loop 0 i = i
loop n i = loop (n-1) (i+1)

n = 100000000

main = let x = X $ loop n 0
       in putStrLn "1"
$ ghc --make -O case3.hs
$ time ./case3
1

real    0m0.006s
user    0m0.001s
sys     0m0.003s
ケース1と同様に遅延評価ですが、loop関数の結果をデータコンストラクタXに適用してからxに束縛しています。ケース1と同様、xは評価されません。評価されるのは文字の出力のみのため、実行時間はごくわずかです。

ケース4(代数データ型を使い、正格評価)

$ cat case4.hs
data X = X Int

loop 0 i = i
loop n i = loop (n-1) (i+1)

n = 100000000

main = let !x = X $ loop n 0
       in putStrLn "1"
$ ghc --make -O -XBangPatterns case4.hs
$ time ./case4
1

real    0m0.006s
user    0m0.001s
sys     0m0.002s
ケース2と同様に、xに正格フラグ(!)を付けて正格評価にします。注目するのは、ケース2と異なり実行時間がほとんどかかっていない点です。

評価されるのはWHNFまでであるため、xにはデータコンストラクタについての関数適用がサンクとして束縛され、それ以上の評価はされません。そのため、loop関数は評価されていないのです。

もう1つ、ケースを追加してみましょう。

ケース5(代数データ型のフィールドを正格評価にする)

$ cat case5.hs 
data X = X !Int

loop 0 i = i
loop n i = loop (n-1) (i+1)

n = 100000000

main = let !x = X $ loop n 0
       in putStrLn "1"
$ ghc --make -O -XBangPatterns case5.hs
$ time ./case5
1

real    0m1.788s
user    0m0.997s
sys     0m0.020s
ケース4に加えて、型Xのフィールドに正格フラグを付けます。今度は、型Xのフィールドも評価されるため、実行時間が長くなっています。


以上のように、Haskellで正格評価を使う場合には、評価されるのがWHNFまでである点に注意が必要です。

ちなみに、WHNFまででなく完全に評価したい場合には、Control.Strategies.DeepSeqライブラリというものがあるので、そちらを検討してみると良いでしょう。

--