関数適用によるスタックとサンク
正格な言語でプログラミングすることを考えましょう。
関数適用の際にスタックが積まれ、深くなっていきます。この際のスタックはもっとも深い時にどの程度になるでしょうか。
言語やドメインによるかもしれないですが、バグを除けば100積むこともそんなにないのではないでしょうか。
Haskellを考えます。関数適用の際にはスタックではなく、代わりにサンクが積まれていきます。先と同様に考えれば、サンクの大きさは高々100程度に収まるはずです。その程度のスペースリークが問題になるでしょうか。そこが問題でないとするならば、スペースリークが発生する状況はそれなりに特徴づけられるはずです。その特徴をもう少し探ってみましょう。
非再帰関数とスペースリーク
スペースリークは再帰関数に発生しやすい、と以前のエントリで書きました。それは再帰関数ならば、関数適用が数十どころか数百数千発生することも珍しくないためです。
Haskellでは再帰関数でないのにやたら使われる関数が存在します。Bind(>>=)です。
(>>=)はもちろんMonadクラスのメソッドですが、do構文に隠れて見えないことがしばしばあります。しかしもちろん使われているし、その度にサンクは生成され潰されています。
よって、(>>=)の実装が問題でスペースリークが発生することは大きな問題になってしまいます。
モノイドとスペースリーク
モノイドは単位元と結合律を満たす閉じた二項演算からなる概念です。モノイドは非常に便利であるわけですが、その便利さはどこから来るのでしょうか。
class Monoid a where
mempty :: a
mappend :: a -> a -> a
mappendに注目します。二つの引数に対して同じ型の値を返します。同じ型を返すということは、得られた結果に対してまたmappendを適用出来るということです。
monoid_chain :: Monoid a => a -> a -> a -> a -> a
monoid_chain mon1 mon2 mon3 mon4 =
mon1 `mappend` mon2 `mappend` mon3 `mappend` mon4
mappendはもちろん関数であるため、monoid_chainは引数を与えても評価されるまでサンクのままです。モノイドは同じ型を返すからこそ、どこまでもスケールし、どこまでもサンクが大きくなり得るのです。
閉じた演算とスペースリーク
一般化します。モノイドは閉じた二項演算の積を持ちますが、「閉じた演算」であることが便利さの元であり、スペースリークの原因であると言えるでしょう。
閉じた演算とは、たとえば自然数(0を含む)に対して和算(+)は閉じている演算ですが、減算(-)は閉じていません。自然数と自然数を足すと必ず自然数になりますが、自然数と自然数を引いても自然数になるとは限らないためです（負数になる可能性がある）。
そしてモノイドなどの様に二項演算でなくとも同様に便利であるし、スペースリークの原因にもなると言えるでしょう。
たとえば
succ :: Enum a => a -> a
negate :: Num a => a -> a
などが挙げられます。これらは単純なのでそこまで大きなサンクになることは稀でしょうけど。
先の記事で扱ったData.Map.Strictを考えましょう。
import Data.Map.Strict
insert :: Ord k => k -> a -> Map k a -> Map k a
update :: Ord k => (a -> Maybe a) -> k -> Map k a -> Map k a
delete :: Ord k => k -> Map k a -> Map k a
Haskellの関数はカリー化されているため、部分適用できるようになっています。そこでいくつか引数を与えると、a -> aの構造が見えてくることが分かります:
-- Ordは省く
insert key val :: Map k a -> Map k a
update f key :: Map k a -> Map k a
delete key :: Map k a -> Map k a
先の記事ではこれらの関数は「偏った入力に対してスペースリークが発生する」という形で紹介しましたが、こちらの方が本質を捉えていると思われます。つまり、閉じた演算に対してスペースリークが発生するということです。
代数を利用することで僕たちは設計上の単純さや動作上のスケーラビリティを手に入れることができますが、同時に遅延評価の言語ではスペースリークの原因になりうるということですね。
ところでOOPLユーザにとっては上記insert, update, deleteの引数の順番に違和感を覚えるかもしれませんが、これは部分適用ができるHaskell上での利便性のためです。他にもOOPLではオプショナルな引数を最後に持ってくることが多いかもしれませんが、Haskellでは第一引数に持ってくること等も良くあります。
一般に、部分適用の利便性のために、引数順序が逆に見えることが良くあるということです。
代数データ型とスペースリーク
代数データ型(ADT)は言うまでもなく代数的構造です。Listに代表される再帰データ型は、知らず知らずの内に大きな構造となりスペースリークの原因となる可能性があるのも、代数的構造の利点であり、遅延言語の特徴でしょう。
大きなADTをfoldする際などにはListのfoldと同様にリークに注意しましょう。
モナドは自己関手の圏におけるモノイド対象だよ
モナドはモノイドなので同様にスペースリークを警戒しましょう。まあモノイドのリークパターンとは質が少し異なる気もしますが。
終わりに
スペースリークの特徴がまたシンプルにまとまったように思います。
- 再帰関数
- 代数的構造に対する演算