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

遅延評価とWHNF(Parallel and Concurrent Programming in Haskell Chapter 2前半まとめ)

Parallel and Concurrent Programming in Haskell という本を以前読書会で読んだが、当時はあまり理解できなかった部分もあったのでもう一度読んでサンプルコードなど書いてみようと思い立った。この本はわかりやすいし並列並行プログラミングに関して必要な要素がまとまっているとてもいい本だと思うので内容をまとつつやってみる。
英語でよければwebですべて読める
http://chimera.labs.oreilly.com/books/1230000000929/index.html

本はこちら

和訳も出ていた(こちらは読んでいないので訳がわかりやすいかは不明)
Haskellによる並列・並行プログラミング

Haskellによる並列・並行プログラミング


今回は第2章について

章のタイトル:Basic Parallelism: The Eval Monad
この章では並列プログラミングの基本的な考え方を説明している。
また、プログラムの性能チェックのやり方についてもこの章で説明されている。

最初は遅延評価とWeak Head Normal Form(WHNF)について
haskellは遅延評価を採用している言語であり各変数は必要とされるまで評価されない。
これについてghciにて確かめていく

>let x = 1 + 2 :: Int
>:sprint x
x = _

:sprintで変数の現在の状態を見ることができる。_は評価されていないことを表す。
上記だとxに1+2を束縛したがそれに対してなんの処理も行っていないためxは未評価となっている

seqを適用すると第一引数をWHNFまで評価することができる
WHNFとは以下のどれかを満たすもの

  • data constructorが先頭に出た形
  • 引数が一つ以上足りないbuild-in関数
  • ラムダ式

上記のxにseqを適用してみると評価されて以下のようになる

> seq x ()
()
> :sprint x
3

ちなみにghc7.8.3だとxの型をIntとして上記のように指定しないとNumとして保持されるため
seqで評価しても:sprintの結果は_のままになるので注意
これはMonomorphismRestrictionというオプションがデフォルトでtrueになったことに依るらしい
http://www.reddit.com/r/haskell/comments/2j56e0/sprint_behaves_differently_in_ghc_783/

リストでやってみると以下のようになる

>let ys = map id [1..3] :: [Int]
>:sprint ys
ys = _
>seq ys ()
>:sprint ys
ys = _ : _
>length ys
>:sprint ys
ys = [_,_,_]
>ys
[1,2,3]
>:sprint ys
ys = [1,2,3]

ysに束縛する際に[Int]を忘れないように注意
seqを適用した段階でdata constructorが出た形(WHNF)になっている
lengthを適用すると中身は_で要素が3つという形に簡約される
lengthの結果に要素自体は必要ないため中身の評価は行われていない
最後にysを表示すると、表示に必要になるため中身まで評価される

2章の後半はEval Monadについてとその具体例
別にまとめることにする