PR

弱頭部正規形

 ここまで名前呼び出しや必要呼び出しについて見てきました。ただこれだけでは第1回で説明したような「無限の長さを持ち得る値から必要な部分だけ取り出して計算する仕組み」を説明できません。これは一体どのような仕組みによって実現されているのでしょうか?

 それについて説明する前に,まず必要となる用語を説明しておきましょう。簡約可能な式のことを簡約項(redex,「reducible expression(簡約可能な式)」の略)というのに対し,もうそれ以上簡約できない式のことを「標準形(canonical form)」または「正規形(normal form)」といいます。例えば,上でも出てきた数値や[11,12]のようなデータ型の値は,これ以上簡約できないので正規形です。なお,数値リテラルは型クラスで定義されているため,浮動小数リテラルのように正規形ではない場合もあります(参考リンク1参考リンク2)。

 定義上,簡約項はすべて正規形になるまで簡約されなければなりません。これは逆にいえば,正規形とみなされるための制約を緩めることで,より柔軟な簡約モデルを構築できることを意味します。Haskellでは一般的に,制約を緩めた「弱頭部正規形(WHNF:Weak Head Normal Form)」が使われています。

 f e1 e2 ... en
のような式があるとき,m<=nとなるm個の変数を持つ以下の式が簡約項でなければ,上の式は弱頭部正規形です。

 f e1 e2 ... em

 弱頭部正規形を採用することで,10:11:[12..] や("Ring:" ++ " ring-ring") ++,\x -> 4+8のような式であっても正規形として扱えるようになります。その結果,項を必要以上に簡約することを防げるのです。

 ではtake 5 $! [10..]という式を使って,実際にどうなるかを試して見ましょう。takeはリストからn個の先頭部分(initial segment)を取得する関数です。演算子$!は値を正規形に変えてから関数を適用するので,もし弱頭部正規形までで簡約を止めないのであれば無限の長さのリストを生成することになります。そうなれば,答えはいつまでたっても返ってこないでしょう。

Prelude> take 5 $! [10..]
[10,11,12,13,14]

 すぐに答えが返ってくるので,$!による簡約の強制はきちんと弱頭部正規形までで止まっていることがわかりますね。

 さて,弱頭部正規形という名前からわかるように,これは「頭部正規形(HNF:Head Normal Form)」の制約をさらに緩めたものになっています。弱頭部正規形と頭部正規形では何が違うのでしょうか?

 弱頭部正規形と頭部正規形の間に違いが生じるのは,ラムダ抽象のような組み込みの関数(built-in function)ではない関数を扱う場合です。\x -> ((\y -> y ++ x) "Ring:")のような式があったとします。この式は弱頭部正規形ですが,頭部正規形ではありません。頭部正規形にするためには,必ず\x -> "Ring:" ++ xのように内側のラムダ抽象を簡約する必要があります(参考リンク)。

 ここまで遅延評価の基本的なモデルについて説明してきました。どうでしたか? 弱頭部正規形という概念の導入によって,$!演算子などを使って「正格評価(strict evaluation)」を強制することが,必ずしも遅延評価を妨げることではないことがわかりました。このことから,もし他の言語と同じように「先行評価(eager evaluation)」に基づいた簡約を行わせたければ,DeepSeqやNFDataのようなデータ型の中身をすべて正規形にしていくための型クラスが必要になることも理解できるのではないでしょうか?(参考リンク1参考リンク2参考リンク3

 また,Haskellの評価モデルを単に遅延評価としてとらえるのではなく,その仕組みの中にグラフ簡約(メモ化)も含まれるということを理解することで,それを利用した最適化の可能性に気がついたかもしれません(参考リンク)。

 このように,弱頭部正規形および必要呼び出しはプログラムの効率化を考えるうえで重要なモデルなので,覚えておいてください。これらの性質をうまく利用することで,簡約段数のみならずアルゴリズムやデータ構造の計算量さえも減らすことができます。そのような関数型言語に向いた効率的なデータ構造を実現する方法について説明している「Purely Functional Data Structures」という本(その基となった論文)があるので,興味のある方は読んでみるとよいと思います。そのうちキュー(Queue)の作り方については,「入門Haskell」の著者である向井淳さんが2007年2月20日から書き始めています(参考リンク)。