関数型言語入門：副作用のないプログラミング

多くのプログラミング言語は命令型です — 「変数に代入せよ」「繰り返せ」という命令を上から順に実行して、状態を書き換えながら進みます。関数型言語は別の考え方をします。プログラムを「式の評価」として組み立て、数学の関数のように「入力を受け取って出力を返す」ことだけをする関数を部品にするのです。

関数型言語では、関数そのものが値です。変数に入れられ、引数として渡せ、戻り値として返せます（こうした関数を第一級関数（first-class function）と呼びます）。「関数を受け取る関数」「関数を作って返す関数」が、ごく普通の道具として使われます。

ここで核心の概念が出てきます。副作用とは、関数が「戻り値を返す」以外に行う仕事のことです — グローバル変数の書き換え、画面への出力、ファイルへの書き込み。副作用がなく、入力以外の外部の状態にも依存しない関数は、いつ・何回・どこで呼んでも、同じ入力に対して必ず同じ出力を返します。この性質を参照透過性（referential transparency）と呼びます。

利点は実感しやすいものばかりです。第一に、テストが簡単です — 入力と出力だけ見ればよく、「事前にどんな状態にしておくか」を気にせずに済みます。第二に、理解が局所的で済みます — 関数呼び出しの前後で世界が変わらないので、コードを部分ごとに読めます。第三に、並行処理で安全です — 共有された状態を書き換えないので、複数の処理を同時に走らせても壊れません。

関数型言語の元祖が Lisp です。1958 年に John McCarthy が考案し、今も使われている高級言語としては FORTRAN に次ぐ古さです。Common Lisp・Scheme・Clojure といった方言が現役で使われています。

Lisp の構文は驚くほど小さく、S 式（S-expression）— (関数 引数 引数 ...) という括弧の式 — だけでできています。そしてこの形はリストというデータ構造そのものでもあります。コードとデータが同じ形をしているため、「プログラムを生成するプログラム」が自然に書けます。

以降のコード例には方言のひとつ Common Lisp を使います。

フィボナッチ数列 0, 1, 1, 2, 3, 5, 8, 13, … は、「前の 2 つの和が次の項になる」数列です。数学では漸化式で定義されます：F(0) = 0、F(1) = 1、F(n) = F(n−1) + F(n−2)。

関数型言語の魅力がここに表れます。この数学の定義が、ほぼ字面のままコードになるのです。

if が「場合分け」、再帰呼び出しが「漸化式の右辺」にそのまま対応しています。仕様（数学の定義）と実装の距離が、これ以上ないほど近い書き方です。ただし、この素朴な定義には重大な問題が潜んでいます。

呼び出しの木を描いてみると、(fib 3) が 2 回、(fib 2) が 3 回 — 同じ計算が何度も現れています。n が大きくなると重複は指数的に増え、計算量はおよそ O(1.62ⁿ)。fib 40 あたりから、待ちきれないほど遅くなります。

解決策は単純です。一度計算した結果を表に覚えておき、同じ引数が来たら計算せずに表から返す — これをメモ化（memoization）と呼びます。

各 n の計算は 1 回きりになり、計算量は O(1.62ⁿ) から O(n) に落ちます。fib 100 でも一瞬です。