プログラマが知るべき97のこと/関数の「サイズ」を小さくする

Kevlin Henney(編)、和田卓人(監修)『プログラマが知るべき97のこと』(オライリー・ジャパン、2010年)を出典とする。各エッセイはCC-by-3.0-USによってライセンスされている。

正しいコードを書きたいというのは誰もが思うことです。そして自分の書いたコードが間違いなく正しいという証拠も欲しいでしょう。そういう意味で、役立つのは、関数の「サイズ」という指標です。この「サイズ」は、関数を実装しているコードの量という意味ではありません(もちろん、それも重要なのですが)。そのコードが表現している数学関数のサイズという意味です。

たとえば、囲碁のプログラムを書くとします。囲碁には「アタリ」と呼ばれる用語があります。これは、「相手に石を固まれ、取られる一歩手前の状態」のことです。石の周りにまだ2箇所以上の隙間が空いている場合には「アタリ」とは言いません。あくまで、あと1個だけ石を置けば完全に固まれてしまう状態をアタリと言うのです。あといくつ隙間が残っているかを数えるのは、ルールを覚える必要があるので少し難しいですが、それさえ数えられれば、アタリかどうかの判定は簡単です。アタリかどうかの判定のために次のような関数を書いたとしましょう。

boolean atari(int libertyCount)
    libertyCount < 2

これは見た目よりも「サイズの大きい」関数です。数学関数は、引数(ここではint)と返り値(ここではboolean)がとりうる値の組み合わせの部分集合と捉えることができます。この値の集合のサイズは、たとえばJavaで表すと、​2L*(Integer .MAX_VALUE+(-1L*Integer.MIN_VALUE)+1L)​となり、つまり、この​int×boolean​の集合には、8,589,934,592個の要素があるということになります。この要素のうちの半分は、上の関数に対応する部分集合の要素なので、関数が完全に正しいという証拠を得るには、4.3×10^9もの例を調べる必要がある、ということになります。

こういう場合は、いくらテストをしたとしても、確かにバグがないという証明はできません。テストは、持つべき機能を持っていることを確かめるのに役立つだけです。サイズが大きいことは、そういう点で問題だと言えます。

助けになるのは、問題領域についての知識です。実は、囲碁の場合、石の周りの隙間の数は無限に増えるわけではありません。実際には​{1,2,3,4} ​のいずれかです。つまり、上の関数は次のように書き直せます。

LibertyCount = {1,2,3,4}
boolean atari(LibertyCount libertyCount)
    libertyCount == 1

これだとはるかに扱いやすくなります。数学関数は、最大で8つの要素を持つだけの集合になりました。4つの例について調べるだけで、関数が完全に正しいという証拠が得られます。組み込み型の代わりに、問題領域固有の型を使うのは、こういう意味でも良いことだと言えるでしょう。問題領域固有の型を使うと、関数のサイズを大幅に小さくすることができます。どういう型を使うのがいいかは、関数を書く前に、問題領域についての知識を基に考えるべきでしょう。確認すべき例の数をどこまで減らせるかを考えるのです。