正格評価と遅延評価（基本編）

今回からスペースリークに関することに踏み入ります。
まずは正格評価と遅延評価の動作についてです。

型と動的な挙動

まず型についてはここでは触れません。Haskellの型は非常に複雑なものです。型についてメンタルモデルを構築する際もλ計算のシンプルさを念頭におくと非常に理解しやすいとは思いますが、ここでは扱いません。
なので型クラス(type class)や型パラメータ(parametric polymorphism)や型関数(type function)といったものは出てきません。

昔僕も静的な箇所と動的な箇所の違いが見えなかった感覚を少しだけ覚えていますが（スクリプト言語しか書いていないと陥りそうです）、静的な箇所とはプログラムを動作させなくても決定できるところを指すとしましょう。慣れればちゃんと項レベルと型レベルの違いはきちんとわかるものです（ここでは型レベルと項レベルの違いについても扱いません）。

そして型を除くと残りは項レベルでの動作モデルです。
それはプログラムが一歩一歩動作する様子を指します。今回僕たちが知りたいのは、この動的な挙動に関するメンタルモデルです。

正格評価の挙動

public class Main {

	public static int factorial(int n) {
		if (n == 0) {
			return 1;
		} else {
			return n * factorial(n-1);
		}
	}

	public static void main(String arg[]) {
		System.out.println("Result: " + Main.factorial(15));
	}
}

ここで唐突に正格評価の例としてJavaを書いてみたわけですが、僕らはこれの挙動を頭の中で追うことが出来るわけです。つまり、メンタルモデルはすでに獲得出来ているわけです。

• エントリポイントは決まっている(main)
• 関数が呼び出されると関数定義箇所へジャンプする
• 関数の実引数部に関数呼び出しがある際には、先に引数の関数が全て実行され、その後外側の関数が呼ばれる（正格評価）
• 逐次的に文(statements)が上から下へ順々に実行される
• ifがあったら条件部を評価して、その結果によって次に実行される文が決まる
• forがあったら(略)
• 変数宣言があったら(略)

メンタルモデルなので人によって扱いが違うかもしれませんが、ざっとこんなところでしょうか。
関数内部の実行に着目してみましょう。

• 開始位置は決まっている(仮引数の部分)
• 関数呼び出し直後の仮引数の状態は型からおおよそわかる
• 文を上から下へ逐次実行していく
• returnに到達したらその値を返り値として返す

おおよそこんなところです。重要な箇所は「関数呼び出し時に引数の状態は決まっている」「上から下へ順次文が実行されていく」です。
言ってみれば、「一番上の状態が初めに決まり、あとは上から下へ順次実行されていく」のです。

さてこれを遅延評価と比べてみます。

遅延評価の挙動

遅延評価で関数の実行挙動を見てみましょう。遅延評価には色々ありますがここでの挙動はHaskell(GHC)の評価戦略を考えます。
重要なのはおおよそ以下の点です。

• 関数が実行される初期状態、引数にはだいたいサンクが乗っている
• 関数適用すると、サンクが一つ追加される
• パターンマッチ時に項の状態が(WHNFまで)決定する
• 関数内だけで見れば挙動はおおよそ理解出来る（多分）
• 評価時にWHNFがどうなるかは、型からわかる

これだけわかっていれば恐らく挙動はおおよそ理解できます。

まず重要なことはパターンマッチからサンクの評価が始まる、という点です。
関数実装内部の挙動が分かってもその関数自身が評価されるかどうかが分からないと困りますからね。

ということで、パターンマッチがどこで発生しているかを理解する必要があります。

次に最終的な評価結果がどこでそのときどうなっているかを理解する必要があります。
Haskellでの評価はおおよそ、WHNFまで行われます。caseでも、seqや($!)やbang-pattens(!)を使っても。例外はdeepseqくらいでしょうか。
そのためWHNFとはどんなものかを知る必要があります。

そして関数適用です。関数適用ではサンクを作成するだけで実際の関数の実行は遅延されます。関数の引数にサンクが乗っているかもしれないし、返り値にもサンクが乗っているかもしれません。

それでは一つずつ見ていきます。

パターンマッチとは

パターンマッチと言えば最近の言語には搭載されていることがしばしばあり、その説明されるところはおおよそ、

• switch文のすごいやつ
• データ構造を分解するやつ

といったところでしょうか。パターンマッチを関数型言語特有の機能と説明されることも何故か多いですが、実際にはADT(Algebraic Data Type)のデータ構造のコンストラクタに沿った分解を意味しており、「コンストラクタ」の意味するところがOOPLとは異なるのです。

OOPLにおいて、オブジェクトのライフサイクル制御のためにコンストラクタ/デストラクタを用います。

// こんな言語は実際にはありません:)
class SomeClass
{
	__construct()
	{
		// ...
	}

	__destruct()
	{
		// ...
	}
}

それに対し、Haskellのような関数型言語ではデータ構造の構築/分解の際に「コンストラクタ」を用います。分解の際にはパターンマッチ(case)を用います。

data SomeData
	= Const1 Int Int
	| Const2 Int
	| Empty

someAction :: SomeData -> IO ()
someAction dat = case dat of
	Const1 x y -> ...
	Const2 z   -> ...
	Empty      -> ...

コンストラクタが、データを構築するだけでなく分解にも使えるようになっています。
というわけで、パターンマッチが関数型特有というわけではないでしょう。単にOOPLでは言語の指向上、「オブジェクトの分解」を導入しづらいだけでしょう。そういえばScalaでパターンマッチはCase Class限定になってましたね。

Haskellではこのcaseによるパターンマッチが評価に関係してきます。
なぜかと言えばcaseは「分岐」を意味しているからです。いろんな計算を遅延するとしても、分岐路で処理を続行するには、どれか一つを選ばなければいけないのです。複数の分岐路を選ぶようなことは(少なくともGHCでは)しません。なので遅延している処理を分岐が出来るようになるまで必要な分だけ進めます。

パターンマッチの場所

さてパターンマッチはどこで発生するでしょうか。
まずはパターンマッチを行うための言語機能caseそのものです。ifはcaseの構文糖衣なので同様にパターンマッチが発生します。

f :: Maybe a -> a -> a
f dat def = case dat of
	Just x  -> x
	Nothing -> def

g :: Bool -> Int
g b = if b then 1 else 0

そして関数頭での引数のパターンマッチです。これも同様にcaseに脱糖されます。

f' :: Maybe a -> a -> a
f' (Just x) _    = x
f' (Nothing) def = def

また無名関数(ラムダ)での引数でもパターンマッチが発生します。

	... \ (f, x) -> f x

そしてdo構文内での(<-)の変数bind時です。doは脱糖後にλと(>>=)になるため、これは実質無名関数での頭でのパターンマッチに等しいものです。

h p = do
	(x, y) <- action1 p
	action2 x
	action3 y
	...

let等での変数の束縛時ですが、コンストラクタを用いて束縛すると、評価時にパターンマッチが発生します。

j :: IO ()
j = do
  let (x, y) = (Just 4, False)
  print x

おおよそこれくらいでしょうか。これらのパターンマッチは、Core言語では全てcaseで表現されます。

WHNFとは

WHNFとは、Weak Head Normal Formの略です。なのですが、並行並列Haskellプログラミング本にて、Simon Marlowが「その名前は歴史的なものなので気にしなくて良いです云々」と言っているため、僕も気にしないことにします。

先ほどパターンマッチにおいて、分岐路にて分岐が出来るようになるまで必要な分だけ進める、と書きました。その到達点がWHNFです。

• a constructor (eventually applied to arguments) like True, Just (square 42) or (:) 1
• a built-in function applied to too few arguments (perhaps none) like (+) 2 or sqrt.
• or a lambda abstraction \x -> expression.

要するにコンストラクタかλが先頭に(Head)見える地点です。

パターンマッチでは「コンストラクタ」を用いてデータを分解、分岐をするのでした。
つまりは、「コンストラクタ」が見えればそこで評価は十分ということです。
先の簡単な関数を見てみましょう。

f :: Maybe a -> a -> a
f dat def = case dat of
	Just x  -> x
	Nothing -> def

仮引数datにはサンクがたくさん乗っているかもしれません。caseはそれを評価し、JustかNothingが見えるところまで持っていきます。なのでxはまだサンクが乗っているかもしれませんし、defはそもそも何も触っていないため、サンクが乗っていればそれがそのままサンク付きで返されるでしょう。

コンストラクタでない場合のλというのは例えば関数の評価結果が関数であるような高階関数の場合です。
関数は引数がなければそれ以上評価できないため、評価結果が関数であるなら、そこで止まるしかありません。

WHNFと型

型を見ればWHNFの状態が分かります。
先ほどの関数fの引数datの評価ではMaybe aだったので、そこにどれだけエグいサンクが乗っていようが（その挙動の中身はこの関数の外のことなので情報不足で追えないが、無限ループしなければ）Just aかNothingまで落ちてきます。
Intであるなら全て評価されて3とか42まで到達します。
Tuple(,)は少し特殊ですが、これもコンストラクタなので、コンストラクタが見えるまで評価されます。つまり、タプルの中身は評価されるとは限りません。

Boolの定義は大まかに言って

data Bool = False | True

といったものですが、TrueもFalesもコンストラクタです。なのでBoolの型が付くようなサンクは、WHNF時には全て評価されます。

サンク

サンクとは内部的には引数のないクロージャです。
評価前のブラックボックス、という説明をされることがあるかもしれません。
それでは不十分だと思うので、もう少し具体的なイメージを構築してみましょう。

i :: IO ()
i = do
	let thunkX = Just $ succ $ succ $ succ $ succ (42 :: Int)
		thunkDefault = succ $ succ $ succ 5
	...

さてここで変数thunkXのサンクの状態を想像してみましょう。
だいたい以下のような感じでしょう。

Just (succ (succ (succ (succ 42))))

そのままじゃん、と言われそうですが、重要なことは

• 引数が埋まっている関数が実行されずにいる
• そんな「実行されない状態」で変数を束縛している
• そんな「実行されない状態」で変数を束縛して、プログラム中を引き回される

ということをイメージすることです。thunkXをcaseで評価するとどうでしょう？

• 型はMaybe Int
• WHNFまで評価されるとJust, Nothingが見えるまで評価される

つまり、関数fにthunkXとthunkDefaultを渡して評価すると、

f :: Maybe a -> a -> a
f dat def = case dat of
	Just x  -> x
	Nothing -> def

仮引数dat, defに「サンクが乗った状態で渡される」ということがイメージできるでしょうか。
そしてcaseでパターンマッチし、

• fではsucc $ succ $ succ $ succ 42の部分は評価されない
• 評価されない部分は、そのまま他に引き回される
• defに乗ったサンクは評価されることなく捨てられる

ということが想像できるでしょうか。

基本編おわりに

基本は以上です。

• パターンマッチから評価が開始される
• 関数内でサンクがcaseによってWHNFまで評価され、
• 残りのサンクが返り値として返される

というようなイメージが持てれば大丈夫だと思います。

もう少し詳しく見た方がいい挙動に関してはまた明日扱います。