不動点コンビネータと無名再帰

基本的に前提知識は不要ですが，JavaScript を用いて説明するので，基礎的な構文の知識は仮定します．

はじめに

プログラミングにおいて再帰関数を定義する場合，我々は当たり前のように「関数自身の名前」を使います．例えば，階乗を求める関数を JavaScript の再帰呼び出しで素朴に定義しようとすると，次のようになるでしょう．

const fact = n => n === 0 ? 1 : n * fact (n - 1);

このコードでは，const fact = ... と名前を付けて関数を定義し，その関数の中で fact(n - 1) と自分自身の名前を指定して呼び出しています．これは JavaScript の関数を定義する際に，自分を指す名前が提供されているからこそ可能な記述です．

ところで，みなさんはゲームで縛りプレイをすることはありますか？強力な装備を禁止したり，レベルを上げずにボスに挑んだりと，自らに制約を課すことで奥深さを味わう遊び方です．ひと昔前のゲームはデフォルトで難しくて，最後までクリアできずに終わることもしばしばでしたが，令和のゲームは簡単なモードから玄人向けのモードまで難易度を選択できたり，ドラクエなんかは「全ての敵が強い」なんてモードもあるようです．

それでは，もし「関数の定義で自分の名前を参照できない」という縛りでプログラムを書くことを強いられたらどうしますか？通常の開発ではあまり遭遇しない状況ですが，無名関数しか存在しない世界 (ラムダ計算など) や，変数の定義すら許されない純粋な計算の世界では，自分自身を参照して呼び出すことができません．このように，名前を使うことができない状況で繰り返しを実現するには，少し工夫が必要です．

Open Recursion

前述したような状況では，自分自身を直接参照するのではなく，繰り返しのロジックを引数として外部から受け取る形をとることで繰り返しを実現できます．言葉で説明するよりも，具体例を見たほうが早いでしょう．

引き続き階乗関数について，まずは繰り返しの中身のロジックだけを記述してみましょう．

const factLogic = next => n => n === 0 ? 1 : n * next(n - 1);

この factLogic は，どう繰り返すかという制御のことは一旦忘れ，引数として渡される next を再帰ステップで呼ぶことだけに専念しています．これは階乗計算のルールそのものですが，あくまでも部品であり，単体では再帰することができません．

たとえば，引数の next に対して「受け取った値をそのまま返す (何もしない) 関数」を渡して実行してみたとします．

// 何もしない関数
const id = x => x;

// factLogic で包む (1層)
const fact0 = factLogic(id);

// 実行してみる
fact0(0); // => 1 (成功)
fact0(1); // => 1 * id(0) => 0 (失敗: 正しくは 1)

このとき n が 0 であれば 1 を返して終了しますが，n が 1 以上の場合は n * next(n - 1) を計算しようとします．next はただの id なので，再帰呼び出しは発生せず，そこで計算が止まってしまいます．

では，この fact0 に factLogic をさらに重ねてみましょう．

// 先ほどの fact0 をさらに factLogic で包む (2層)
const fact1 = factLogic(fact0);

// 実行してみる
fact1(0); // => 1 (成功)
fact1(1); // => 1 (成功)
fact1(2); // => 2 * fact0(1) => 0 (失敗: 正しくは 2)

この場合は n が 1 までであれば，正しく計算してくれます．しかしながら，n が 2 以上となると，やはり factLogic の在庫が切れてしまい，最後は id が呼び出されて計算が不完全なまま終わってしまいます．

このように factLogic を重ねれば重ねるほど，より大きな n に対応できそうなことがわかります．具体的には factLogic を重ねて factN を定義すると，n が N 以下であれば正しく計算できそうです．この続きは，みなさんも考えてみてください．

仕組みが見えてきました．どんな大きな n が与えられても対応するには，factLogic の next に factLogic を，そのまた中身にも factLogic を … と，無限に供給し続ける必要がありそうです．イメージとしては，次のように関数適用のマトリョーシカを作ってから，最後に n を渡す形でしょうか？

// 疑似コード
const factInf = factLogic(factLogic(factLogic(...)));

// 定義した関数に数値を渡す
factInf(n);

ここで手詰まりになりました．factLogic を定義するためには，無限の factLogic の連なりが必要です．一方で，ソースコードの長さは有限なので，長さが無限の式を書き下すことはできません．それでは，無限に自分自身を供給し続ける仕組みを有限の記述で定義するには，どうすればよいのでしょうか？

不動点コンビネータ

ここでタイトル回収です．不動点コンビネータというものを定義します．概念的には，次のように表現できます．

const fix = f => f(fix(f));

fix は関数 f を受け取り，その f に対して fix(f) (再帰能力を持った自分自身) を引数として渡し続けます．この fix が，関数 f が引数を必要とするたびに，即座に自分自身 (fix(f)) をコピーして引数に適用し続ける無限の供給源として機能すれば，名前を持たない関数であっても，構造の中に自分自身を埋め込み続けることができるでしょう．

ちなみに，この fix を定義するのに fix 自身を参照しているじゃないか，というツッコミがあるかもしれません．しれっと「名前を使わない」縛りプレイのレギュレーションに違反していますね．パズルのようですが，以下のように定義すれば，名前を使わずに同じ仕組みを作れます．ラムダ計算の世界で「Y コンビネータ」とよばれる有名な式です．

const Y = f => (x => f(x(x))) (x => f(x(x)))

重要なのは x(x) の部分です．関数 x が引数として x 自身を受け取っています．こうすることで，自分がまた自分自身を受け取って… と，無限に自分を再生産できるわけですね．

これで理論上は，名前を使わずに再帰ができるようになりました．

プログラミング言語の評価戦略

これまで定義した fix や Y を JavaScript で動かしてみると，残念なことにスタックオーバーフローで止まってしまいます．

> fix(factLogic)
Uncaught RangeError: Maximum call stack size exceeded
    at fix (REPL1:1:18)
    at fix (REPL1:1:20)
    at fix (REPL1:1:20)
    at fix (REPL1:1:20)
    at fix (REPL1:1:20)
    at fix (REPL1:1:20)
    at fix (REPL1:1:20)
    at fix (REPL1:1:20)
    at fix (REPL1:1:20)

RangeError: Maximum call stack size exceeded というエラーが出ていますが，これはメモリ領域を使い切ってしまったことを意味します．なぜ計算が始まる前に，このような事態に陥るのでしょうか？この原因は，プログラムをどのように解釈して実行するかという，プログラミング言語の評価戦略にあります．

JavaScript は「正格評価」とよばれる評価戦略を採用しています．この戦略において，関数を呼び出す際には，関数自身を実行する前に，渡された引数をすべて計算して値を確定させておかなければなりません．

先ほどの fix(factLogic) の実行を追ってみましょう．fix の定義は f => f(fix(f)) でした．fix(factLogic)(n) を実行しようとすると，まずは定義に従って factLogic(fix(factLogic))(n) という式を実行しようとします．ここで JavaScript エンジンは，外側の factLogic を呼び出そうとしますが，正格評価の戦略により，関数の中身を実行するよりも先に引数として渡されている fix(factLogic) が何なのかを先に突き止めようとします．

factLogic(fix(factLogic))(n) を呼ぶには，引数 fix(factLogic) の値を知りたい
fix(factLogic) を計算しようとすると，fix の定義より factLogic(fix(factLogic)) となる
これを呼ぶには，また factLogic の引数 fix(factLogic) の値がほしい (以降無限ループ)

このように，いつまでも factLogic の中身 (n === 0 ? ...) を実行できず，引数の計算だけでメモリを食いつぶしてしまうわけですね．Y コンビネータについても，みなさんで計算を追ってみてください．

このような無限の計算に陥らない言語もあります．例えば Haskell のように「遅延評価」を採用している言語ならば，引数は「関数の中で実際にその値が必要になる瞬間」まで評価が先送りされるため，このような定義のままでも問題なく動作します．しかしながら，JavaScript, Python, Java, C# など，我々が普段使っている多くの言語は「正格評価」であり，このままでは動きません．これを何とかするための明示的な工夫が必要です．

イータ変換と Z コンビネータ

前述したように，引数の計算の連鎖が爆発するのを，どうすれば食い止められるでしょうか？正格評価の言語において，ある処理の実行を遅らせるための定石は，その処理全体を関数の中に閉じ込めることです．

例えば，crash() という関数を考えます．

const crash = function() { throw new Error(); }

そのまま crash() と書けば即座に実行されてプログラムは停止します．一方で () => crash() のように，crash() を関数の中に包んで (Thunk の構造にして) おけば，その外側の関数が呼び出されるまで，中のコードは実行されません．

このように f を x => f(x) の形に変形することを，ラムダ計算の言葉で「イータ変換 (の逆変換)」や「イータ展開」とよびます．理論上は「同じ働きをする関数」としての等価性 (外延性) を保つための変換ですが，JavaScript のような正格評価の言語においては，この関数で一枚包むという構造が，評価を遅らせるためのカプセルとして機能します．

前述した通り fix と Y を変換すると，以下のような形になります．後者は Z コンビネータとよばれます．

// 引数 f を適用する部分を x => ... (x) で包む
const fix = f => f(x => fix(f)(x));

// x(x) の結果を v => ... (v) で包む
const Z = f => (x => f(v => x(x)(v))) (x => f(v => x(x)(v)))

例によって fix(factLogic) の実行を追ってみましょう．fix の定義は f => f(x => fix(f)(x)) でした．fix(factLogic)(n) を実行しようとすると，定義に従って factLogic(x => fix(factLogic)(x))(n) という式を実行しようとします．ここで JavaScript エンジンは，外側の factLogic を呼び出す前に，その引数を明らかにしようとします．しかしながら，引数の x => fix(factLogic)(x) は関数なので，評価がストップするわけです．

factLogic(x => fix(factLogic)(x))(n) を呼ぶ前に，引数 x => fix(factLogic)(x) を評価する
x => fix(factLogic)(x) は関数なので評価をストップして，外側の factLogic(x => fix(factLogic)(x))(n) を計算する
factLogic の定義により，n が 1 以上であれば n * next(n - 1) となる
next は x => fix(factLogic)(x) なので fix(factLogic)(n - 1) の計算が始まる (n := n - 1 として 1 に戻る)

こうして最終的に n := 0 のとき factLogic の定義が分岐して，計算が終了します．

このように，引数の計算を止めることで，factLogic の中身 (n === 0 ? ...) を実行するフェーズに移れるわけですね．Z コンビネータの計算についても，みなさんで追ってみてください．

なぜそこまでして再帰するのか

ここまで読んで「普通に名前をつけて再帰すればいいじゃないか」とか「while や for ループで書けば済むだろ」と感じた方も多いでしょう．実務的には JavaScript でわざわざ不動点コンビネータを書くことはまずありません．

しかしながら，再帰の仕組み (コンビネータ) と具体的な処理 (ロジック) を切り離すという考え方には，単なる道楽のパズルに留まらない，ソフトウェアの設計における重要な示唆が含まれています．

ロジックと制御の分離

例として，木構造のデータを探索して，すべてのノードの名前を表示する処理を考えてみましょう．これを一般的な while ループで実装すると，次のようになるでしょうか．

function traverseLoop(root) {
    const stack = [root]; // スタックを管理
    while (stack.length > 0) {
        const node = stack.pop();

        console.log(node.name); // 本質的な処理はこれだけ

        // 以下は「どう繰り返すか」のためのコード
        if (node.children) {
            // 右側の子からスタックに積むことで，左側から順に処理される
            stack.push(...[...node.children].reverse());
        }
    }
}

このコードはちょっと微妙で「ノードを表示したい」という本来の目的 (i.e. ビジネスロジック) が「スタックの出し入れ」というループ制御のボイラープレートに埋もれています．

ここで，先ほどの factLogic に倣って，ロジックだけを抽出してみましょう．

const traverseLogic = next => node => {
    console.log(node.name); // やりたいこと

    if (node.children) {
        // 子要素に対して自分と同じことをさせる
        node.children.forEach(child => next(child));
    }
};

// Z コンビネータで再帰能力を注入する
const traverse = Z(traverseLogic);

traverseLogic 自身は，自分がどういう順序で，どのような仕組みで呼び出されるのかを知りません．ただ「ここにあるノードを今どうするか」と「次はどこへ進むか」という純粋なロジックだけを記述することで，コードの責務が精査されています．

テストも容易になるでしょう．具体的には，再帰処理全体を走らせることなく「1階層分のロジック」だけを切り出して単体テストを行うことが可能になります．

通常の再帰関数では，テスト時に「本当に再帰呼び出しが行われたか」や「無限ループしないか」を検証するのは骨が折れますが，今回の traverseLogic であれば，引数の next にダミーの関数 (i.e. モック関数) を渡せば，依存関係を断ち切ったテストを書けます．

const node = {
    name: "Root",
    children: [
        { name: "Child A", children: [] },
        { name: "Child B", children: [] },
    ],
};

// next に，呼び出しを記録するだけのモック関数を渡す
let callCount = 0;
const mockNext = child => {
    console.log(`${child.name} が渡されました`);
    callCount++;
};

// 再帰させずに，1層分のロジックを検証
traverseLogic(mockNext)(node);

この例では「名前が表示されること」や「子どもの数だけ next が呼ばれること」の検証を，再帰によって木構造探索せずに実行できます．複雑な再帰構造自体のテストと，個々のロジックのテストを分離 (i.e. DI) できるというわけです．

モジュール性

ロジックと制御を分離したことで，ロジックには一切手を加えずに，再帰の挙動だけを調整することもできます．

例えば，フィボナッチ数を計算するロジック fibLogic があったとします．

const fibLogic = next => n => n <= 1 ? n : next(n - 1) + next(n - 2);

フィボナッチ数列の本質的なロジックを定義したわかりやすいコードですが，これに対して素朴に Z(fibLogic) を動かすと計算量が爆発 ( $O(2^n)$ ) してしまいます．こういった再帰は，メモ化するのが定石なのですが，今回は fibLogic 自体を書き換える必要はありません．再帰を制御するコンビネータの方を，メモ化できるものに差し替えれば解決です．

const memoFix = f => {
    const cache = new Map();
    // 再帰関数を定義
    const rec = n => {
        if (cache.has(n)) return cache.get(n); // キャッシュにあれば返す

        // ロジック f に自分 (rec) を渡す
        // rec はキャッシュ機能付きなので，再帰呼び出しもキャッシュ経由
        const result = f(rec)(n);

        cache.set(n, result); // 結果をメモする
        return result;
    };
    return rec;
};

// ロジックを変更せずに，メモ化再帰能力を注入する
const fibMemo = memoFix(fibLogic);

通常の const fib = n => 1 <= n ? 1 : fib(n - 1) + fib(n - 2) のような定義では，メモ化しようとすると関数の定義自体を書き換える必要があります．しかしながら，今回のアプローチなら「計算の定義」と「計算の実行戦略 (メモ化するか，ログを取るか，…)」を独立した部品として扱うことができるわけです．

再帰を支える技術と他言語の例

今回は JavaScript で無理やり実装しましたが，JavaScript は再帰が得意な言語ではありません．途中で RangeError が出たように，多くの再帰呼び出しはメモリ (スタック) を消費し続けてしまうからです．

しかしながら，関数型プログラミングが主軸の言語 (Standard ML, OCaml, Scheme, Haskell, …) では，このようなスタイルに対するサポートが備わっています．

末尾呼び出し最適化

関数型プログラミングが想定される言語では，計算の最後に行われる呼び出し (末尾呼び出し) を，新しいスタックを積むのではなく，現在の場所を上書きするジャンプ処理 (i.e. ループ) などに最適化してくれます．どういう書き方になるかというと，計算結果を引数として次の再帰に渡していくスタイルです．ためしに JavaScript で書いてみましょう．

// 素朴な再帰の場合
// 後から n * ... を計算する必要があるため，スタックを残さないといけない
const fact = n => n === 0 ? 1 : n * fact(n - 1);

// 末尾再帰の場合
// 計算結果の acc を引数で持ち回るので，後から戻ってくる必要がない
const factTR = (n, acc = 1) => n === 0 ? acc : factTR(n - 1, n * acc);

残念ながら JavaScript では基本的にこの最適化は行われません．一応 ES6 の仕様には入っていますが，一部の処理系 (Safari など) を除いて，主要な処理系 (Chrome V8, Node.js, Firefox, …) には実装されていません．つまり Node.js などで末尾再帰コードを実行しても，結局はスタックが溢れてしまいます．これを回避するには，トランポリン最適化などの工夫が必要になるのですが，今回は割愛します．

一方で Standard ML や Haskell などの言語では，後者のように再帰を書くことで，内部的には while ループのように動きます．これにより，幾ら再帰してもスタックが溢れず，とても嬉しいです．

遅延評価による定義

JavaScript で Y コンビネータなどが動かず，これを変換する必要があったのは，正格評価の戦略で，引数が即座に計算されてしまうからでした．一方で，Haskell のような「遅延評価」を採用している言語では，値が必要になるまで計算が走らないため，不動点コンビネータを定義そのままに記述できます．

fix :: (a -> a) -> a
fix f = f (fix f)

また fix (1:) や fix ([2, 5] ++) のようにして，無限リストを表現することもできます．ちなみに Data.Function をインポートすれば，ライブラリとして提供されている fix (fix f = let x = f x in x と定義は異なる) も利用できます．

型推論のサポート

Standard ML, OCaml, Haskell などの言語には，強力な型推論の機能が備わっており，プログラマが型を明示的に書かなくても，処理系が文脈から自動的に (汎用的な) 型を特定してくれます．例えば Standard ML で fix や末尾再帰 fact を定義したい場合，単に

fun fix f x = f (fix f) x;
fun go fact n acc = if n = 0 then acc else fact (n - 1) (n * acc);
fun fact n = fix go n 1;

と定義すれば

fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b
go : (int -> int -> int) -> int -> int -> int
fact : int -> int

といったように，自動的に型が付いてくれます．

Z コンビネータについても，以下のように定義すると fix と同じ型が付きます．Standard ML では t = t -> u のような循環する型が許容されないため，データ型でラップして循環を断ち切る工夫が必要ですが，あまり本質的ではないので説明は割愛します．(TaPL の Part IV に iso-recursive とか equi-recursive とか再帰型の説明があると思う…)

datatype 'a Rec = REC of ('a Rec -> 'a);
val Z = fn f => (fn REC x => f (fn y => x (REC x) y)) (REC (fn REC x => f (fn y => x (REC x) y)));

エラーを分かりやすくしたり，推論能力を補ったりするために，明示的に注釈を書くこともしばしばありますが，便利な機能です．JavaScript のように動かしてみないとわからないのではなく，書いた瞬間に正しさが保証されて，コードはスクリプト言語のように短く済むという点が，再帰やコンビネータを扱うのに適しています．

さらなる抽象化

今回は再帰自体を抽象化するために，不動点コンビネータを紹介しましたが，関数型プログラミングの世界では，これをさらに推し進めた概念が利用されます．深入りはしませんが，Haskell のような言語では，単なる再帰だけでなく，リストや木構造を畳み込む操作 (Catamorphism) や，種となる値からデータを生成する操作 (Anamorphism) など，再帰のパターンごとの概念が用意されています．

for 文や while 文のように明示的な制御構造を，プログラマが主要なロジックで書くことは少なく，純粋なロジックをパズルのように組み合わせることで，複雑な処理を堅牢かつ簡潔に記述します．

不動点コンビネータは，一見すると難解なパズル遊びに見えるかもしれませんが，計算の構造そのものを部品化するという，現代のプログラミングにも通じる強力なアイデアです．

まとめ

この記事では「関数の定義で名前を再帰的に参照できない」という縛りプレイから始まって，不動点コンビネータの仕組みや，その応用について簡単に紹介しました．

一見すると難解なパズルですが，関心を分離して「何を計算するか」と「どう制御するか」を切り離す，実践的な設計の示唆に富んだ概念であることを，簡単な例を通して感じ取っていただけたでしょうか．

奇妙で奥ゆかしい無名再帰が，単なるパズル遊びではなく，よい抽象の入り口となれば幸いです．Standard ML はいいぞ！