Y Conbinator (不動点コンビネータ) をJSで表現しよう

自己紹介

Kaiと申します。ベトナム人です。日々、ユーザーの体験を高めるために努めるフロントエンドエンジニアとして、技術の探求を続けております。私の日々の生活は、コーディングやデザインのみにとどまらず、カラオケで心を込めた歌声を披露することや、没頭してゲームの世界に浸ることで豊かになっています。

このブログを通じて、技術の世界と趣味の世界をつなぎ、共に歩んでいきましょう。どうぞよろしくお願いいたします。

Introduction

ソフトウェアエンジニアならよく「Y combinator」どこかで聞いたことあると思っているだろうか。

自分は最初に 「Y combinator」と聞いたら Hacker News https://news.ycombinator.com すぐ思い浮かんだが、「Y combinator」は別の意味がありそうだ。一体どういう意味だろう？

ChatGPTさんに聞いてみたらこういう答えを返した。

In programming, the term "Y Combinator" also refers to a specific concept related to functional programming and recursion theory. The Y Combinator is a higher-order function that allows for the creation of anonymous recursive functions in languages that lack built-in support for recursion. It was first introduced by Haskell Curry, and its name is a tribute to the mathematical concept of combinatory logic.

プログラミングでは、「Y コンビネーター」という用語は、関数型プログラミングと再帰理論に関連する特定の概念も指します。 Y コンビネーターは、再帰のサポートが組み込まれていない言語で匿名再帰関数の作成を可能にする高階関数です。 これは Haskell Curry によって初めて導入され、その名前は組み合わせ論理の数学的概念に敬意を表しています。

Wikipedia からは

In combinatory logic for computer science, a fixed-point combinator (or fixpoint combinator) is a higher-order function (i.e. a function which takes a function as argument) that returns some fixed point (a value that is mapped to itself) of its argument function, if one exists.

不動点コンビネータ（ふどうてんコンビネータ、英: fixed point combinator、不動点結合子、ふどうてんけつごうし）とは、与えられた関数の不動点（のひとつ）を求める高階関数である。不動点演算子（ふどうてんえんざんし、英: fixed-point operator）、パラドキシカル結合子（英: paradoxical combinator）などとも呼ばれる

など、という難しい言葉で説明されていた。

本ブログでは、なるべく簡単な言葉で step-by-step 的に「Y combinator」をJSで実装してみよう。

Disclaimer: 関数型・ロジック・再起周りに興味ある人々向けの内容である。

簡単な説明

簡単に説明していくと、Y combinatorを使って、変数や関数の宣言がなくても、関数とパラメーターだけで再帰ができるということだ。

より具体的に見てみよう。

より具体的

まずは factorial 関数（階乗）を作ろう。

var fact = function(n) {
    if (n < 2) return 1;
    else return n * fact(n-1);
};

単純な再帰関数だが、n が 1 なら1 を返し、そうでなければ n に fact(n-1) を掛ける。

Yコンビネータを作るには、すべての宣言を削除する必要がある。

fact() 関数はそれ自身の中でfact()を参照している。しかし、階乗関数への参照を作成せずに階乗関数を再帰的に呼び出すにはどうすればよいだろうか？

答: fact() 関数をパラメータとして渡し、fact() 関数を宣言するのではなく、fact() 関数を返す関数を用意すればよい。

var makeFact = function(givenFact) {
    var fact = function(n) {
        if (n < 2) return 1;
        else return n * givenFact(n-1);
    }
    return fact;
};

問題は、givenFact 関数がなければ makeFact を呼び出せない。すでに階乗関数がないと makeFact を使って階乗関数を作ることはできないだろう。

だが、makeFact が作る階乗関数は必ずしも givenFact を呼び出すとは限らないので、上のことができそうだ。

事前に作られた givenFact を渡す代わりに、makeFact が givenFact を呼び出す必要のない時まで、givenFact 自身に makeFact を使わせることができる。

var makeFact = function(givenFact) {
    var fact = function(n) {
        if (n < 2) return 1;
        else return n * givenFact(n-1);
    }
    return fact;
};

// 将来的にY関数になる関数
var makeRealFact = function(makeFact) {
    var tryFact = function(n) {
        var nextTryFact = makeFact(tryFact);
        return nextTryFact(n);
    };
    return makeFact(tryFact);
};

新しい関数 makeRealFact（Y関数）を作り、makeFact を使って実際の階乗関数を作る。

tryFact 関数は makeFact に渡され、givenFact 関数として使われる。

makeFact が givenFact を使う必要があれば、再度 tryFact を呼び出し、tryFact は makeFact を使って別のtryFact を作る。

だが、tryFact は自分自身を参照しているので、変数や関数の宣言を取り除くという問題はまだ解決しない。

tryFactが自分自身を参照することなくすために、tryFact-nextTryFactを循環させ続けるためには、別の関数を作る必要がある。

var makeRealFact = function(makeFact) {
    var getNextTryFact = function() {
        var tryFact = function(n) {
            var nextTryFact = getNextTryFact();
            var result = nextTryFact(n);
            return result;
        };
        var nextTryFact = makeFact(tryFact);
        return nextTryFact;
    };
    return getNextTryFact();
};

tryFact が不要になるまで makeFact に自分自身を渡す代わりに、getNextTryFact を呼び出し、makeFact に tryFact を渡す。

しかし、 getNextTryFact は自分自身を参照しているというところまだあるので、宣言せずに getNextTryFact を参照する方法が必要だ。

getNextTryFactを自分自身にパラメータとして渡せば、すべての自己参照関数を削除
することができる。

var makeRealFact = function(makeFact) {
    var getNextTryFact = function(getNextTryFactRef) {
        var tryFact = function(n) {
            var nextTryFact = getNextTryFactRef(getNextTryFactRef);
            var result = nextTryFact(n);
            return result;
        };
        var nextTryFact = makeFact(tryFact);
        return nextTryFact;
    };
    return getNextTryFact(getNextTryFact);
};

これで、 makeFact 関数を使って階乗関数を再帰的に作ることができる関数ができ、ラベルを使って自分の変数や関数を参照する必要がなくなった。

宣言がまだ使われているのは明らかだが、今度はそれをリファクタリングして、パラメータだけを使う関数に仕上げることができる。

ここからは、関数の可読性はかなり低下するが、変数宣言が本当に不要であることを示す。

まず、tryFact 関数は宣言されずに直接 makeFact に渡す。

var makeRealFact = function(makeFact) {
    var getNextTryFact = function(getNextTryFactRef) {
        var nextTryFact = makeFact(
            function(n) {
                var nextTryFact = getNextTryFactRef(getNextTryFactRef);
                var result = nextTryFact(n);
                return result;
            }
        );
        return nextTryFact;
    };
    return getNextTryFact(getNextTryFact);
};

次に、一番内側の nextTryFact 関数が、宣言されずに結果を生成するために使われる。

var makeRealFact = function(makeFact) {
    var getNextTryFact = function(getNextTryFactRef) {
        var nextTryFact = makeFact(
            function(n) {
                var result = (getNextTryFactRef(getNextTryFactRef))(n);
                return result;
            }
        );
        return nextTryFact;
    };
    return getNextTryFact(getNextTryFact);
};

次に、結果は宣言されずに返される。

var makeRealFact = function(makeFact) {
    var getNextTryFact = function(getNextTryFactRef) {
        var nextTryFact = makeFact(
            function(n) {
                return (getNextTryFactRef(getNextTryFactRef))(n);
            }
        );
        return nextTryFact;
    }
    return getNextTryFact(getNextTryFact);
};

次に、 nextTryFact 関数は宣言されずに直接返される。

var makeRealFact = function(makeFact) {
    var getNextTryFact = function(getNextTryFactRef) {
        return makeFact(
            function(n) {
                return (getNextTryFactRef(getNextTryFactRef))(n);
            }
        );
    };
    return getNextTryFact(getNextTryFact);
};

getNextTryFact は同じ行で2回使用されるため、同じものを2回参照するためのラベルが必要です。そのためには、関数にパラメータとして渡す必要があります。パラメータは、同じものを2回参照するためのラベルとして使用できる。

var makeRealFact = function(makeFact) {
    var getNextTryFact = function(getNextTryFactRef) {
        return makeFact(
            function(n) {
                return (getNextTryFactRef(getNextTryFactRef))(n);
            }
        );
    };
    return function(getNextTryFactRef) {
        return getNextTryFactRef(getNextTryFactRef);
    }(getNextTryFact);
};

最後に、 getNextTryFact 関数は、再帰を開始するために getNextTryFact を呼び出す無名関数に直接渡される。

var makeRealFact = function(makeFact) {
    return function(getNextTryFactRef) {
        return getNextTryFactRef(getNextTryFactRef);
    }(
        function(getNextTryFactRef) {
            return makeFact(
                function(n) {
                    return (getNextTryFactRef(getNextTryFactRef))(n);
                }
            );
        }
    );
};

tryFact 、 nextTryFact 、戻り値、 getNextTryFact の宣言を取り除き、宣言のないパラメータだけの関数になった。

より「uglify」にするとこうになる🤔

var y = function(le) {
    return function(f) {
        return f(f);
    }(function(f) {
        return le(
            function(x) { return (f(f))(x); }
        );
    });
};

階乗関数のために作ったが、Y関数はどんな再帰関数にも使うことができ、再帰が変数なし、副作用なしでできることを示している。以下、同じY関数を使って階乗関数とフィボナシ関数を作る。

var makeFact = function(givenFact) {
    return function(n) {
        if (n < 2) return 1;
        else return n * givenFact(n - 1);
    }
};
var fact = y(makeFact);
console.log(fact(5)); // Outputs 120

var makeFib = function(givenFib) {
    return function(n) {
        if (n <= 2) return 1;
        else return givenFib(n - 1) + givenFib(n - 2);
    }
};
var fibbonaci = y(makeFib);
console.log(fibbonaci(5)); // Outputs 5

結論

関数型・再起など興味ある方はここまで読んで面白いと思うかもしれないが、
productionコードでYを使わない方がいいじゃないかと思った🤔

参考

• Fixed-point combinator - Wikipedia
• functional programming - What is a Y-combinator? - Stack Overflow
• The Y Combinator (Slight Return) - Mike's World-O-Programming — LiveJournal
• The Y Combinator explained with JavaScript
• Deriving the Y Combinator in 7 Easy Steps — igstan.ro