PHPでYコンビネータの応用をしてみた（関数の連鎖適用，ジェネレータetc...）①

PHPでYコンビネータの応用をしてみた（メソッドチェーン編）

＊記事の中で，「Yコンビネータ」と「Yコンビネータを使って生成された再帰関数」を，ごちゃまぜにして解説している箇所があるかも知れませんが，あまり気にしないでください．
本来は，不動点を求めるための関数(Y関数)を「Yコンビネータ（不動点演算子・パラドキシカル結合子）」と呼ぶ（らしい）のですが，Yコンビネータを使って作った再帰処理関数も「Yコンビネータ」と呼んだり呼んでいなかったり，まちまちかもしれません．
詳しくはWikipediaまでどうぞ．

「Yこんびねーた」って何ぞ？？？

プログラミングの世界では，再帰処理を実現する方法がいくつか存在します．
再帰処理ってのは，実行すると自分自身を再帰的に呼んで繰り返し構造を作り出すアレです．
「Yコンビネータ」は，ラムダ計算やら不動点定理やらの小難しい話は抜きにして，この「再帰処理」を実装するための魔法の一つです．

こんなの↓がYコンビネータです．
- このY関数（Yコンビネータ)自体には，深くは踏み込みませんよ念のため

PHPでのYコンビネータの例

YCombinator.php

function Y(callable $F){
    return $F(
        function() use (&$F){
            $result = call_user_func_array(Y($F), func_get_args());
            return $result;
        }
    );
}

この「魔法の関数(Y関数)」に関数を渡してやると，その関数で再帰処理ができるようになります．
あら不思議・・・

Y関数の定義中で，関数をよくわからん方法で入れ子にして返しています．
一番内側の関数にはuseが使われていますが，これは「その関数の外側の変数を関数の中で使えるようにする」PHPの言語機能です．
Javascriptのレキシカルスコープと似たような考え方(同じではないよ)なのですが，&を付けると「参照渡し(渡し元で値が更新されると，渡された値も更新される)」になり，&をつけないと「値渡し(渡された時の値のまま変わらない)」になります．
(Yコンビネータでは，再帰処理関数の生成時に指定した関数を，最内の関数内で使えるようにするために，このようなコード実装を行います．)

とりあえずよくあるやつ

さて，その「Yコンビネータ」の使い方ですが，そこかしこのブログやナレッヂなんかで↓のような例をよく見かけますね．

factorial.php

// Yコンビネータを使って，階乗を計算する例
$factorial = function(callable $callback){
    return function($val) use(&$callback){
        return ($val === 0) ? 1 : $val * $callback($val - 1);
    };
};
$result = Y($factorial)->__invoke(6);

このコードのうち

Y($factorial)->__invoke(6)

に登場する__invokeメソッドは，関数を呼ぶためのマジックメソッドの一つです．
Y(\$factorial)は，Yコンビネータを使って作った，\$factorialを再帰化した関数です．

このコードを実行すると，6の階乗である「720」が得られます．

変数を無駄に使うのが気持ち悪いのであれば，こんな書き方でもOK！

factorial2.php

// Y関数に直接関数をブッコんだ方が，シンプルでいいよね？
$result = Y(function(callable $callback){
    return function($val) use(&$callback){
        return ($val === 0) ? 1 : $val * $callback($val - 1);
    };
})->__invoke(6);

一つ前の例では，「\$factorial」変数に一旦関数を格納してからYコンビネータを作って
いましたが，この例では，Yコンビネータ(Y関数)の引数に関数を直接渡しています．
こっちの方が幾分かすっきりしてません？

で，何がうれしいのさ！？

再帰処理を実装するには，例えば関数を一回定義して，その関数の中で「自分自身」を呼ぶ
など，Yコンビネータなんかより遥かに「素直」な方法があるのですが，なぜわざわざこんな小難しい関数で再帰処理を定義するんでしょう？

「システムは．誰にでも理解できるような平易な方法で実装すべき（建前？）」

な大原則に逆行しています．

実は，この複雑さを補って余りある絶大な威力をもつのが，「Yコンビネータ」なのです．
その「絶大な威力」の一つが

「Yコンビネータで作った関数は，中の関数に渡ってきたコールバックを実行すると自分自身が呼ばれる」

というYコンビネータ自体の性質（不動点演算子の性質）によるものです．
（何を当たり前のことを・・・と言いたいのはわかりますけど，今しばらくお付き合いください）

Yコンビネータを使った処理を思いっきり単純化した例が↓のコードです

most_simple_recursive.php

$result = Y(function(callable $callback){
    return function($val) use(&$callback){
        // ここに，$val引数の値に従って
        // 再帰を実現できるようなコードを書く
        // 基本的には「もう一回繰り返したい場合」は
        // $callbackを呼び，処理を終えたい場合は呼ばないように
        // します
    };
})

コードのコメントにも書いた通り，\$callbackを呼べば，自分(最内の関数)が再度呼ばれます．
（\$callbackは，自分自身の関数を呼ぶためのクロージャで，Yコンビネータによって自動的に提供されます．）

これを利用して，\$callbackを呼んだり呼ばなかったりすることで，再帰を実現するわけです．
(ちなみに，\$callbackを引数付きで呼んだ場合は，\$valにその引数の値が入ってきます)

この「上手い具合に制御が自分に戻ってくる」性質と「ただ関数を渡せばそれで再帰関数を作り出せる」
という性質は非常に便利で，かつかなり応用が利くのです．

念のため繰り返しますが，Yコンビネータ(Y関数)の仕組み自体は，この際深く考えないでください．
Google先生に質問すれば，「Yコンビネータってなんぞや？」ってポストが腐るほど出てくるので，
仕組み自体に興味のある方は先生に聞いてください．
今のところは，「特定の形の関数を渡すと再帰処理をうまい具合に行ってくれる魔法の関数」程度の認識でOKです．

別に返す値は関数だっていいじゃないのさ！

Yコンビネータ（というか，再帰処理全般）の例で良く見かけるのは，階乗を計算したり，フィボナッチ数列を求めたりするような所謂数学の「漸化式」チックな解説じゃないでしょうか？
数学の授業で印象深い漸化式と再帰処理は，切っても切れない関係にあるため，サンプルとして丁度良いのでしょう．

基本的には，上の例にあるような「数列」の計算を行ったり，ある種の木構造(XMLとかJSONとかファイルシステム構造だとか)を探索するのに絶大な威力を発揮するYコンビネータですが，別に数や文字列”だけ”を返さなきゃいけないルールなんて無いはずです．

返すのが関数だっていいじゃない？

例えばこんな具合に．．．

get_func.php

$combinator = Y(function(callable $callback){
    return function() use(&$callback){
        return function(){
            return 100;
        };
    };
});

$result = $combinator->__invoke();

このコードを実行すると，\$resultの値は何になると思います？
正解は↓な感じです

\$resultの中身

function() {
   return 100;
}

Yコンビネータは，本来は再帰（ループ）処理をするために使うものなので，基本的には処理を投げたら投げっぱなし(全部終わるまで待たされる)なのですが，このサンプルコードでは\$callbackを関数の中で呼んでいない(←これ重要！！テストに出るぞ）ため，すぐに値が帰ってきます．
-これは，あまりにもシンプルすぎる例なのですが，これがすべての基本です！！！

Ｙさんとこに”いってこい”

上の例では全く面白味が無い（単に「100を返す関数」を返すだけ）のですが，ここで一工夫．
こんな例はいかがでしょうか．

ちょっと工夫

$combinator = Y(function(callable $callback){
    return function() use(&$callback){
        return function() use(&$callback){
            showLog("関数がコールされました！！！");
            $callback();
        };
    };
});

この例で，

php

$combinator->__invoke();

を実行するたびに，ログに「関数がコールされました！！！」と出力されます．
いや，正確には，「ログを出力し，ついでにログを出力する関数を返し」ます．
-showLogメソッドは，ログに文字列を出力する関数だと思ってください．

ポイントは，ログ出力をした後に\$callbackを実行している部分です．

例えば

$func = $combinator->__invoke();

のように実行すると，\$funcの中身は

function() use(&$callback){
    showLog("関数がコールされました！！！");
    $callback();
}

となるはずですね（だって，関数自体を返しているんだし・・・）
つまり，$funcは，実行するとログにメッセージを出力し，また同じ
関数を返す(ログ出力して，自分自身を返す)性質を持っているわけです．

function() use(&$callback){
    showLog("関数がコールされました！！！");
    $callback();
}

の中では，\$callbackが呼ばれています．
\$callbackは，useによって外から渡されるコールバックに束縛されているため
結果的に実行するたびに同じ処理(ログ出力)を行い，毎回同じ関数を返すことになるわけですね.

$combinator
    ->__invoke()
    ->__invoke()
    ->__invoke()
    // 以下，すきなだけ繰り返し

とすれば，好きなだけ「関数がコールされました！！！」とログ出力できるようになりました．

やったぜ父ちゃん！！！

そして時は動き出す

この例だと，毎回必ず同じログが出力されるだけですが，useを使うと，もっと面白い
ことができます．

少し面白い例

$cache = array();
$gettime = function(){
    return date( "Y年m月d日 H時i分s秒" );
};
$combinator = Y(function(callable $callback) use(&$cache, &$gettime){
    return function() use(&$callback, &$cache, &$gettime){
        return function() use(&$callback, &$cache, &$gettime){
            $count = count($cache) + 1;
            $now = $gettime();
            showLog("[$now][$count回目の処理]関数がコールされました！！！");
            $cache[] = "ほげほげ";
            $callback();
        };
    };
});

少し複雑になりました．
ポイントは，\$cacheという配列と，\$gettimeという「現在時刻を取得する関数」を
useを使って，スコープの最外から順繰り再帰の本処理部分まで渡しているところです．

この関数を使って

$combinator
    ->__invoke()
    ->__invoke()
    ->__invoke()
    // 以下，すきなだけ繰り返し

のように処理すると...

[2017年05月27日 10時30分20秒][1回目の処理]関数がコールされました！！！
[2017年05月27日 10時30分22秒][2回目の処理]関数がコールされました！！！
[2017年05月27日 10時30分25秒][3回目の処理]関数がコールされました！！！
[2017年05月27日 10時30分29秒][4回目の処理]関数がコールされました！！！
...

のように，呼べば呼ぶだけ無限にログ出力できるはずです．
しかも，先ほどの単純なログ出力の例と違って，今度は出力内容を可変にすることができるようになりました．

因みに，この例では再帰処理の引数はありませんが，$combinator->__invoke("ログメッセージ");の
ような改造を施すと，それだけで簡単なログ出力機構が完成します！
"ログメッセージ"は，当然最内の関数の引数としてわたってくるはずなので，その値を
showLogメソッドに食わせればいいだけですね．

究極のバケツリレー

この基本的なアイデア（ループをわざと回さずに，呼び出し元に一旦制御を戻す）を使って，「関数をどんどん合成していって，最後に一気に計算する」ような関数を返すクラスが次のようなものです．

WCombinator.php（汎用関数合成コンビネータ）

/**
 * 簡単に関数合成を行うための機能を提供するクラスです
 * @author kose_likes_nuda
 *
 */
class WCombinator {
    private $w = null;

    /**
     * 新しくWコンビネータのインスタンスを生成します
     */
    public static function newInstance() {
        return new self();
    }

    /**
     * このコンビネータに対して，引数に指定されたクロージャをバインドします．
     * クロージャは何回でもバインドすることができます
     * @param callable $callback バインドされるクロージャ
     * @return WCombinator Wコンビネータインスタンス
     */
    public function bind(callable $callback) {
        // 既存のWコンビネータにクロージャをバインドし
        // 更新された状態のWコンビネータをフィールドに再セットする
        // 第二引数がtrueの場合は，関数バインドモード
        $this->w = $this->w->__invoke($callback, true);

        // メソッドチェーンが行えるように
        // this参照を返却する
        return $this;
    }

    /**
     * 引数に指定されたパラメータをWコンビネータに適用し
     * コンビネータにバインド済のクロージャ群に対して
     * 連鎖的に関数適用を行います
     * @param mixed $parameter パラメータ
     * @return mixed 評価結果
     */
    public function resolve($parameter) {
        return $this->w->__invoke($parameter, false);
    }

    private function __construct() {
        // bind処理で追加したクロージャを保持するキャッシュ
        $cache = array();

        // Wコンビネータ本体
        $this->w = Y(function(callable $callback) use(&$cache){
            return function($param, $bindFlg) use(&$callback, &$cache) {
                // ここから関数本体 =============================================================
                // $args = func_get_args(); // 可変長引数を扱うことも可能だが．．．
                if($bindFlg === true) {
                    // 関数バインドモード
                    if($param instanceof \Closure) {// クロージャでなければ無視
                        $cache[] = $param;// キャッシュに，関数を追加
                        // 呼び出し元に，自分自身の関数を返却する
                        return function() use(&$param, &$callback, &$cache) {
                            $args = func_get_args();
                            $count = count($cache);
                            // ↑↑↑こんな風に大外から値をもってこれるので
                            // 好きなように料理できます
                            return call_user_func_array($callback, $args);
                        };
                    }
                } else {
                    // $bindFlg=falseの場合は，評価モード
                    // resolveメソッドに渡された引数がparamにわたってくるので
                    // 一番最初の評価対象として設定する
                    $result = $param;
                    for($i = 0; $i < count($cache); $i++) {
                        // バインドした関数分だけループ
                        if($cache[$i] instanceof \Closure) {
                            // $cache[$i]をコールして，実際の値評価（バインドされた関数の実行）
                            // を行う．
                            // 評価結果は，次にバインドした関数の入力に化ける．
                            // 戻り値は１つなので，基本１変数の関数を想定していますが
                            // 処理を工夫すれば，多変数関数でもいけます
                            $result = call_user_func($cache[$i], $result);
                        }
                    }
                    // 最終評価値を，呼び出し元に返却する
                    return $result;
                }
                // ここまで関数本体 =============================================================
            };
        });
    }
}

このクラスは，次のようにして使います．

$wCombinator = \WCombinator::newInstance();
$result = $wCombinator->bind(function($val){
    return $val * 2;
})->bind(function($val){
    return $val * 3;
})->bind(function($val){
    return $val * 5;
})->bind(function($val){
    return $val * 7;
})->bind(function($val){
    return $val * 13;
})->resolve(1);

評価順序は，bindメソッドで関数をバインドした順で，順繰り関数が合成されていきます．
bindメソッドは，関数の合成を行うだけで，何か計算処理を行うことはありません．
最後のresolveメソッドを実行することで，はじめて関数が評価されます．
-みんな大好き遅延評価の登場です．

resolveメソッドを実行することで，\$resultは次のようになります．

$result = 1 * 2 * 3 * 5 * 7 * 12;

上手い具合に，関数が合成されているはずです．

こんな具合に，jQueryライクなメソッドチェーン機構を，Yコンビネータで実現することができました．
Yコンビネータ使う必要ないじゃんて，身も蓋もないこと言わないでね（笑）

可能性は無限大

上で長々説明してきた通り，呼び出し元に逐一制御を戻しながら，再帰関数と行ったり来たりするような制御構造にする
ことで，メソッドチェーンのような構造を簡単に作成することができます．
（しかも，bindする関数は好きに作成できるため，極めて汎用的です）

これらの例とは逆に，通常のYコンビネータの使い方（制御を戻さずに，$callbackを呼んで再帰処理を行う方法）
で実装しつつ，関数を返すような構造をとることもできます．
（前の方で示した，ログ出力の例みたいな）

この場合，再帰関数自体の引数には好きな型（＋好きな引数の数）を渡せるため
例えば，木構造や複雑な多次元配列自体を受け取って最終的な値(配列の要素値)を関数で包んで
呼び出し元に返すこともできます．

こんな実装をすると，「ただの”値”が格納されたデータ構造」を，「”値”を返す関数が要素値となるデータ構造」
にすり替えるようなこともできます．
（データの洗い替えができるので，追加の引数に関数を渡せば，関数適用も可能です）

構造のすべての子要素を関数（型）で包むような，ある種モナドチックな制御構造を実現することもできてしまいますが
それはまた別の話．．．

さいごに

次回は，これをさらに拡張して，ジェネレータ（無限に要素を生成できる処理実装）を，Yコンビネータを使って
実装してみたいと思います．

いや，次回あるかなぁ・・・