草稿の段階です。間違いや説明不足があります
この文章では関数型プログラミングにどのような利点があるか、個々の関数型言語実装に触れずに！簡潔に述べる。 簡潔性のため、細かい点は無視する事にした事に注意してほしい。 最大公約数的な主張になるように努めたつもりであるが、各点について必ず異論があるはずである。
特定のプログラミング言語を採用して例を語るということをしないので、 抽象的な説明で終ってしまう。これは、もう致し方ない。
関数型プログラミングとは、プログラムを式として表すプログラミング手法である。
例えば、式 e1 と式 e2 を関数呼出によって組合せ f(e1, e2) という式を作ることで、
小さなプログラムを組合せて、大きなプログラムを構築していく。
関数型プログラミングとは、これだけである。
関数型プログラミングの利点、難点を含む性質は全てこのプログラム構成法から導かれる。
関数型プログラミングをそのプログラム構成法として推奨するプログラミング言語の事である。
上の関数型プログラミングの「定義」と対比すると、手続き型プログラミングとは、
プログラムを手続きの列として記述するプログラミング手法である。
手続き s1 と手続き s2 を逐次実行によって組合せ s1; s2 という手続を作ることで、
小さなプログラムを組合せて、大きなプログラムを構築していく。
これはとても大雑把な議論であって、手続型プログラミングでも条件分岐やループなどがあるから、
プログラムは単なる一列に連なる逐次実行の列となるわけではない。
この文章では関数型プログラミングとオブジェクト指向の比較は行わない。 世の中の大抵の関数型プログラミングとオブジェクト指向の対比は、 関数型プログラミングと手続き型プログラミングの差違の話だからである。
関数型プログラミング上でのオブジェクト指向というものは実際に存在する。 そのようなオブジェクト指向と通常の関数型プログラミングとの比較は、 クラスやモジュールといったもう一段上のプログラム構成レベルで語られるべきであろう。 ここではこのレベルの話はしない。
関数型プログラミングの理論的モデルとしてまず採用されるは、チャーチの λ計算である。 λ計算については多くの数学的研究があり、関数型プログラミングの種々の性質はこれを受け継いでいる。 λ式が樹状構造を取るように、関数型のプログラムも樹状構造になる。
これは、手続き型プログラミングにはまともな理論的モデルがない、ということを意味しない。 関数型のチャーチのλ計算との対比を念頭にすると、手続き型プログラミングのモデルは、 チューリング機械にまで還元できる。 チューリング機械のテープのように、手続き型プログラムは一本の手続き列になりがちである。
関数型プログラミングは式と式を関数で組合せていくプログラミング手法であるため、 この手法を守っていく限り、手続き型プログラミングにおいては常套手段である、 「再代入可能な変数(assignable)」への破壊的更新、という概念がそもそも存在しない。
つまり、関数型プログラミングには assignable にまつわるバグは存在しない。 これは手続き型プログラミングにおいて、いかに多くのバグがプログラム実行中の assignable に格納された値に対する間違った仮定から生れているかを考えると、 非常に大きい利点である。
このような複雑な挙動を記述するためには関数の再帰呼出と高階関数(関数を引数に取る関数)の サポートがほぼ必須となる。関数型プログラミングのモデルであるλ計算は再帰と高階関数を表現可能であるし、 ほとんどの関数型言語はこの二つを備えている。
関数型プログラミングは関数適用によりプログラムを組合せていくが、この関数適用だけで、 手続型では様々な「コントロールフロー構文」として提供されている条件分岐や繰返しを 参照透明性を保ったまま実現することができる。 さらに、もし新しい「構文」が必要になれば、関数適用を組合せてそのための 新しい関数を作成することもできる。
世の中のコンピューターは巨大なチューリング機械のお化けのようなもので、 関数型プログラミングで書かれたプログラム、つまりλ式をそのまま実行するようにはできていない。 そのため関数型プログラミングで書かれたコードをチューリング機械に実行しやすい形、 つまり手続き型のコードに翻訳(コンパイル)する必要がある。 このコンパイルは自動的なものであるが、プログラマは関数の再帰呼出しについて、 気をつけなければいけない事がある。
通常、手続き型プログラムや手続き型言語に翻訳された関数型プログラムは、関数呼出しでスタックを消費する。
例えば、 g(x) = f(x) + 1 という関数定義の右辺式の評価では、
「結果に1を足す」というコードのアドレスをスタックに記憶しておいてから、f(x) を評価する。
その結果 r が得られたら、スタックから継続コードへのアドレスを取り出して実行をそこへ移し、
最終的に r + 1 の結果を得る。
スタックは有限であり、コンピューターの総メモりサイズと比べると通常はとても少ない。 あまりに関数呼出しの入れ子が深くなると、スタックを全て使い切ってしまい、スタック溢れの実行時エラーとなる。 複雑な処理を関数呼出しではなく、繰返しを使って主に実装する手続き型プログラミングでは スタックを使い切る事はほとんどないが、 関数型プログラミングでは、繰返しの代りに再帰的な関数呼び出しを多用する。 再帰関数呼出しひとつひとつでスタックを消費していくとすると、 手続き型では何の問題も無かったコードが、再帰を用いた同等の関数型のコードでは、 繰返し数が大きくなると簡単にスタックを使い切ってしまうことになる。
この問題の回避策として末尾呼出し最適化(TCO)がある。関数定義内部で、 関数呼出しがその結果を継続して処理する必要が無い位置にあるとき、これを末尾呼出しという。 例えば、
g(x) = if x == 0 then 0 else f(x+1)
という関数定義での f(x+1) という関数呼出しは末尾呼出し位置にある。 f(x+1) を評価した後、
g(x) はその結果を使って何か計算をしない。その結果を自身の結果とするだけである。
この様な場合、f(x+1) の呼出しで継続コードへのアドレスをスタックに保存する意義はない。
そこで、スタックにアドレスを記憶させずに f(x+1) の結果をそのまま g(x) の結果とする
スタックを消費しないコードに置き換えるのが TCO である。
この TCO は末尾呼出し一般に有効な最適化であるが、末尾再帰呼出しに適用する事で 関数型コードでの再帰呼出しのスタック溢れの問題を回避することができる。 これは、関数型プログラムを手続き型コードにコンパイルし、コンピューター上で実行させる上で 必須の技術である。
TCO は非末尾位置にある関数呼出しには適用できない。そのため、非末尾再帰呼出しは 再帰が深くなるとスタック溢れをするリスクから逃れられない。このため、関数型プログラミングでは コード中の非末尾再帰呼出しを末尾再帰呼出しに置き換える作業が必要となる。 関数型プログラマはこれを何度か演習問題でしっかりと訓練する必要がある。
なお、非末尾再帰呼出しはスタック溢れの恐れがあるにも拘わらず、ほとんどの関数型言語ではこれを禁止しない。 これは非末尾再帰呼出しでも常に小さな再帰サイズでしか呼び出されないという確信があれば スタック溢れの恐れは全くないし、末尾再帰化したコードと比べると定義が簡単ですみ、 実行速度も速い事が多いからである。
Assignable はバグの元、とは言え、やはり便利なのである。