簡約と正規形

すべての関数適用が展開されるまで式を評価するプロセスを簡約と呼び、これ以上簡約できない結果としての式を正規形と呼びます。 この意味を理解するために、例を見てみましょう。

square :: Int -> Int
square x = x * x
 
fst :: (a, b) -> a
fst (x, y) = x

これで必要な関数を定義したので、特定の式に対してどのように簡約が行われるかを見てみましょう。

fst (sqare 3, square 4)
-- -> fst (3*3, square 4) (square)
-- -> fst (9, square 4) (*)
-- -> fst (9, 4*4) (square)
-- -> fst (9, 16) (*)
-- -> 9 (fst)

上記の簡約の過程で結果として9が得られましたが、これはこれ以上簡約できない正規形の例です。より正確には、 この簡約の過程はすべての関数の引数を簡約してから関数を適用する最内簡約の例です。しかし、上からわかる通り、このような 簡約戦略はsquare 4を不必要に計算してしまうため最適ではありません。ここでは、簡約ステップを減らすため代わりに最外簡約を使用できます。

-- 最外簡約
fst (sqare 3, square 4)
-- -> square 3 (fst)
-- -> 3*3 (square)
-- -> 9 (*)

上記の簡約ステップが示すように、最外簡約は関数定義を適用してから、関数の引数を簡約することを目的としています。最外簡約の素晴らしい点は、 チャーチ・ロッサーの定理が、1つの終了する簡約法がある場合、最も外側の簡約も終了すると示している点です。つまり、最外簡約を使用することで、 簡約できるすべての式を簡約できることが保証されているということです。これを直感的に理解するために、例を見てみましょう。

loop = 1 + loop
 
-- 最外簡約
fst (4, loop)
-- -> 4 (fst)
 
-- 最内簡約
fst (4, loop)
-- -> fst (4, (1+loop)) (loop)
-- -> fst (4, (1+(1+loop))) (loop)
-- :
-- 終了しません！

上記の例は、最外簡約が終了できる場合でも他の簡約戦略には終了できないことが多いことを示しています。 これは、最外簡約が不必要な引数の簡約を破棄できるからです。

グラフ最外簡約

チャーチ・ロッサーの定理を活用するために最外簡約を常に使いたいところですが、最内簡約の方が計算が少ない場合もあります。

-- 最内簡約
square (1+2)
-- -> square 3 (+)
-- -> 3*3 (square)
-- -> 9 (*)
 
-- 最外簡約
square (1+2)
-- -> (1+2)*(1+2) (square)
-- -> 3*(1+2) (+)
-- -> 3*3 (+)
-- -> 9 (*)

上記からわかるように、最外簡約は最内簡約に比べてステップが多くなることがあります。これは、最外簡約が同じ引数に 対して別々に計算を行わなければならないことがあるためです。最外簡約が最内簡約と最低でも同じステップ数になるようにするためには、 引数が同じ場合は計算の結果を共有すれば良いです。最外簡約に計算結果の共有を組み合わせたものをグラフ最外簡約と呼びます。

-- グラフ最外簡約
square (1+2)
--     sqare
--      / \
--     _   _
--      \ /
--       +
--      / \
--    1     2

引数が重複しているケースを認識し、サンク_を（変数に値を格納し、複数の場所でそれを使用するletバインディングのように）使用することで、 計算の結果を格納し、その結果を適切に共有することで、不必要な計算を排除することができます。Haskellはこのグラフのグラフ最外簡約を使用することで、 簡約の終了と最小の計算ステップを行う遅延評価を実現しています。

弱頭部正規形

遅延評価がどのように実装されているかを理解したところで、seq関数がどのように実装されているかを見てみましょう。前回の記事では、seq関数は最初の 引数が評価されてから2番目の引数を返すように定義されていると紹介しました。しかし、より正確には、seq関数は最初の引数が弱頭部正規形 (WHNF) になるまで評価 されてから2番目の引数を返すように定義されています。

普通のデータであれば、データが少なくとも一つのデータコンストラクタまで評価されていれば、それはWHNFであると言えます。 WHNFの例をみてWHNFがどのようなものか理解しましょう。

1+1 -- -> 2
(1, 2+2) -- -> (1, 2+2) 
-- タプルの内部を評価する必要はありません
[True && False] -- -> _ : _
-- リストの内部を評価する必要はありません (_はサンク)
data myData = Data Int
Data (2+2) -- -> A _
-- MyDataの内部を評価する必要はありません (_はサンク)

タプルもリストもデータコンストラクタでありすでにそれが明らかになっているため、さらに評価する必要はありません。これは、myDataのような独自のデータ型にも適用されます。 関数も無名関数の形式で完全に表現されている場合、WHNFに分類されます。

f x = <expr> --- Not WHNF
f = \x -> <expr> --- WHNF
 
-- Not WHNF
f [] = 0
f x:xs = x + f xs
 
-- WHNF
f = \xs -> 
  case xs of 
  [] -> 0
  x:xs' -> x + f xs'

seqは、最初の引数がWHNFになるまでのみ評価されるため、seqは次のように動作します。 （注: GHCiの:sprintコマンドは、式を評価せずに表示することができます。）

swap :: (a, b) -> (b, a)
swap (x, y) = (y, x)
 
x = 1 + 2 : Int
a = (x, x+1)
b = swap a
 
-- ghci> :sprint a
-- a = _
 
-- ghci> :sprint b
-- b = _
 
-- ghci> seq a ()
-- a = (_, _)
 
-- ghci> seq b ()
-- b = (_, _)
 
-- ghci> seq a ()
-- a = (_, _)

最初、aとbは全く評価されていないため、WHNFではありません。そのため、seqを呼び出すと、一度だけ評価されてWHNFの(_, _)になります。 しかし、seqをaやbに再び実行しても、(_, _)は既にWHNFであるため、さらに評価は行われません。実際に表示するなどして結果が必要になって初めて、 サンクが評価され、全てが正規形に簡約されます。

クイズ

この記事では、学習した内容を確認するためのクイズを設けます。記事のメイン部分を読んだ後に、ぜひ自分で問題を解いてみることを強くお勧めします。各問題をクリックすると答えが表示されます。

リソース

• Philipp, Hagenlocher. 2020. Haskell for Imperative Programmers #31 - Weak Head Normal Form. YouTube.
• nd. Haskell/Graph reduction. Wikibooks.