TheCaseForD-ja.ch5.txt

関数型プログラミング

簡単な質問です。フィボナッチ関数を、関数型のスタイルで定義してください。

uint fib(uint int n)
{
    return n < 2 ? n : fib(n - 1) + fib(n - 2);
}

私は空想にふける事があるのですが、その一つに、時間をさかのぼって上記のようなフィボナッチの実装を何とかして根絶し、計算機科学の教師が誰もそれを教えなくなるようにする、というものがあります。
(その次のターゲットは、バブルソートと、空間計算量 O(n log n) なクイックソートの実装です。
しかしフィボナッチの方がはるかにデカいです。
また、ヒトラーやスターリンを殺害すると予想のつかない結果につながりかねませんが、<b>fib</b> 抹殺は良いことづくめです。)
<b>fib</b> は、計算に指数関数的な時間がかかるので、計算の複雑さやコストを軽視することにつながり、「テキトーでもカワいけりゃいいじゃん」な態度や、SUV車を乗り回す粗野な連中を蔓延させてしまいます。
指数関数的な時間というものがどんなに酷いかご存知ですか?
私のマシンでは <b>fib(10)</b> や <b>fib(20)</b> にはごく僅かな時間しかかかりませんが、 <b>fib(50)</b> となると19分半かかります。
<b>fib(1000)</b>を評価している内には、ほぼ間違いなく人類が絶滅してしまうでしょう。酷いプログラミングを教え続けていたら本当にそうなっちゃうよ、と思うと慰めになります。

よろしい、ではフィボナッチの「地球にやさしい」関数型な実装とはどのようなものでしょう?

uint fib(uint n)
{
    uint iter(uint i, uint fib_1, uint fib_2)
    {
        return i == n
            ? fib_2
            : iter(i + 1, fib_1 + fib_2, fib_1);
    }
    return iter(0, 1, 0);
}

こちらの改訂版だと、 <b>fib(50)</b> にも僅かな時間しかかかりません。
この実装は計算時間が O(<i>n</i>) となり、末尾呼び出しの最適化 (Dはこれを実装しています) のおかげで空間計算量の問題もありません。
問題は、新たな <b>fib</b> は、ある意味、その栄光を失ってしまったという点です。
改訂版の実装では、関数のパラメータという形になってはいますが実質的に、状態をもつ変数が2つあります。
このことを認めてしまえば、 iter が無駄に分かりにくくしているループを明快な形に書き直してしまっても同じことでしょう:

uint fib(uint n)
{
    uint fib_1 = 1, fib_2 = 0;
    foreach (i; 0 .. n)
    {
        auto t = fib_1;
        fib_1 += fib_2;
        fib_2 = t;
    }
    return fib_2;
}

ギャー! これではもう関数型とはいえません!
ループの中で値が書き換えられているのがムカつきますね!
ほんの一歩間違えただけで、数学的純粋さの頂点から、粗野な下層民の野暮ったさへと真っ逆さまに転落してしまいました。

しかしちょっと考えてみましょう。繰り返し型の <b>fib</b> は、 <i>そんなに</i> 粗野なものでしょうか。
<b>fib</b> をブラックボックスだと考えれば、ある入力に対しては常に同じ出力を返すわけですし、挙動が純粋ならば結局は純粋なのです。
内部で状態を使っているので、名実ともに関数型であるとは言いにくいのですが、実質的に関数型であるとは言えます。
この考え方を注意深くつき詰めると、次のような非常に興味深い結論が出てきます:
関数内の可変な状態が厳密に <i>短時間限り</i> のものであり (つまり、スタックに割り当てられたものであり)、<i>その関数専用のものである</i> (つまり、その状態を変更するような関数へ参照渡しされることがない) ならば、その関数は純粋であると見做してよい。

これが、Dにおける関数の純粋さの定義です。
純粋な関数の中でも、短時間限りかつその関数専用のものならば、値を書き換えてよいのです。
このような関数のシグニチャに pure と付けておけば、あとはコンパイラが問題なくコンパイルしてくれます:

pure uint fib(uint n)
{
    〜繰り返し型の実装〜
}

Dは、純粋さの定義をゆるめたおかげで、関数型な純粋さは厳密に保証されるのに、繰り返しで実装すると便利な場合にはそうしてもよい、という良いとこ取りが出来るようになりました。
こんなに素晴らしいことはありません。

最後に、これも重要なのですが、関数型言語でフィボナッチ数列を定義する方法はもう一つあります。いわゆる無限リストです。
これは、関数を定義する代わりに、読み出すたびにフィボナッチ数を得ることができるような遅延評価の無限リストを定義する、というものです。
Dの標準ライブラリを使うと、このような遅延評価リストを綺麗に定義することができます。
最初の50個のフィボナッチ数を出力するコード例を以下に示します (<b>std.range</b> をインポートする必要があります):

foreach (f; take(50, recurrence!("a[n-1] + a[n-2]")(0, 1)))
{
    writeln(f);
}

これはワンライナーというより半ライナーですね!
この recurrence の呼び出しは、漸化式 <b>a[n] = a[n-1] + a[n-2]</b> を使って、0と1で始まる無限リストを作りなさい、という意味です。
その際には、メモリを動的に割り当てることもなく、間接的に関数を呼び出すこともなく、また再利用できない資源を使うこともありません。
このコードは、繰り返し型の実装にあったループとほぼ等価です。
どうしてこんな事ができるのか、それは次の節で説明しましょう。

ジェネリック・プログラミング

(大好きな映画や本や音楽のことを友達に話す時に、あまり褒めすぎるとかえって嫌がられるから注意しよう、と思うことがありますね?
Dのジェネリック・プログラミングという話題については、まさにこれが私の気をつけている点です。)
ジェネリック・プログラミングには定義がいくつかあって、本稿執筆時点では、Wikipediaのそのページの中立性さえもが議論の対象となっています。
ジェネリックプログラミングを「パラメータ化された型を使ってプログラミングすること、いわゆるテンプレイトやジェネリック」と定義する人もいれば、「複雑さの保証 (complexity guarantee) を保ちつつ、アルゴリズムを最も一般的な形態で表現すること」と定義する人もいます。
本節では前者について少し説明し、後者についても次節で少し説明します。

D offers parameterized structs, classes, and functions with a simple syntax, for example here's a <b>min</b> function:
Dでは、パラメータ化された構造体やクラスや関数が、簡単な文法で使えるようになっています。例えば、 <b>min</b> 関数はこうなります:

auto min(T)(T a, T b) { return b < a ? b : a; }
...
auto x = min(4, 5);

<b>T</b> は型パラメータで、 <b>a</b> と <b>b</b> は通常の関数パラメータです。
返値型の <b>auto</b> は、 <b>min</b> が返す型が何になるかをコンパイラに考えさせるという意味です。
Here's the embryo of a list:
次の例は、リストの骨組みの部分です:

class List(T)
{
    T value;
    List next;
    ...
}
...
List!int numbers;

面白いのはここからです。
記事のスペースの都合上、このテーマについて十分に語りつくすことは出来ませんので、以下の段落では「差分」のみ、つまりジェネリックのある従来の言語との違いについて説明します。

<b>パラメータの種類</b>。
ジェネリックのパラメータとして受け付けられるのは型だけではありません。数 (整数型および浮動小数点型)、文字列、コンパイル時に決まる <b>struct</b> 型の値、そして <b>別称</b> (alias) も受け付けられます。
別称のパラメータとはプログラム中のあらゆる記号的な実体のことで、それ自体が値や型や関数を参照したり、テンプレイトさえをも参照したりすることがあります。
(That's how D elegantly sidesteps the infinite regression of template template template. . . parameters; just pass it as an alias.)
別称パラメータはまた、ラムダ関数を定義する際にも便利です。
可変長のパラメータリストも使えます。

<b>文字列操作</b>。
コンパイル時に文字列をろくに操作できないならば、テンプレイトに文字列を渡してもほとんど意味がありません。
Dでは、コンパイル中に、文字列操作機能が豊富に使えるようになっています。 (結合、添字を使ったアクセス、部分文字列の選択、繰り返し、比較、などなど)

<b>コード生成 ＝ ジェネリック・プログラミング界のアセンブラ</b>。
コンパイル中の文字列操作も面白いかもしれませんが、それはまだデータいじりの次元の話です。
<b>mixin</b> 式を使うと、この次元から飛び出して、文字列をコードへと変換することができます。
<b>recurrence</b> の例を思い出しましょう。
あの例では、フィボナッチ数列の漸化式を、文字列としてライブラリへ渡していました。
ライブラリはそれを受けて、文字列をコードへ変換し、そこに実引数を与えるのです。
別の例として、Dで範囲をソートする例を見てみましょう:

// 整数の配列を定義する
auto arr = [ 1, 3, 5, 2 ];
// 昇順でソート (ディフォルト)
sort(arr);
// ラムダ式を使って降順で
sort!((x, y) { return x > y; })(arr);
// コード生成を使って降順で。比較式は文字列で与えるが、
// そのパラメータにはaやbを使う約束になっている
sort!("a >  b")(arr);

コード生成を使うと、言語レベルのサポートがなくても機能を完全に実装できるので、これは非常に強力だと言えます。
例えば、Dにはビットフィールドがありませんが、標準モジュールの <b>std.bitmanip</b> はコード生成を利用してその機能を完全かつ効率的に定義しています。

<b>イントロスペクション</b>。
イントロスペクション (コードの実体について調べる機能) は、コード生成を補うものだと考えることもできます。コードを生成するのではなく、それを調べるのですから。
イントロスペクションは、コード生成の助けとなることもあります。
例えば、列挙型の値をパーズする関数を生成する際には、イントロスペクションで分かる情報が使えるでしょう。
現時点では、イントロスペクションのサポートはまだ限定的なものにとどまっています。
より優れた設計が進んでおり、その実装も「リストに載っている」状態ですので、ぜひこの件には注目しておいてください。

<b>is と static if</b>。
C++である程度複雑なテンプレイトを書いたことがある人なら誰でも知っていることですが、(a) あるコードについて「コンパイルが通る」かどうかを判定し、通る場合と通らない場合それぞれの処理を書くこと、(b) 論理型の条件を静的に調べ、その結果に応じたコードをコンパイルすること、という面倒な処理がどうしても必要になります。
Dでは、論理型のコンパイル時の式 <b>is(typeof(expr))</b> は、 <b>expr</b> が正しい式であれば <b>true</b>を、そうでなければ <b>false</b> を返します。
(なお、後者の場合でもコンパイルは止まりません。)
また <b>static if</b> というものもあり、これはif文にそっくりなのですが、Dのコンパイル時の論理式で正しいものならばどんな物にでも使えます。
(<b>#if</b> を正しく実装するとこうなるのです。)
この2つの機能だけで、ジェネリックなコードの複雑さは半分にまで下がったと言っていいでしょう。このどちらも C++0x には含まれていないと思うと、悔しさで胸がいっぱいになります。

<b>そして更に... いや、もうお分かりですね</b>。
ジェネリック・プログラミングで遊べることはまだまだたくさんあり、Dでは意外なほど数少ない概念でこれをカバーできているのですが、それでも、議論をこれ以上進めるためには、ずっと込み入った情報が必要になってきます。
Dにはもっと機能があります。例えばエラーメッセージのカスタマイズや、C++のコンセプト風な制約付きテンプレイト (ただしちょっと簡単になっています − what's a couple of orders of magnitude between friends?)、タプル、「ローカルな実体化」というユニークな機能 (これは柔軟かつ効率のよいラムダ式のためには極めて重要です) といったものです。
そして、あと5分以内に電話すれば、凍ったソーダ缶さえ切り裂けるナイフも付いてきます。


# A Word on The Standard Library の前まで
# eof