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

PHPでYコンビネータの応用をしてみた（ジェネレータ編）

まえがき

この記事を読む前に・・・

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

前回までの投稿

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

前回のおさらい

本題に入る前に，この記事を読まれる方は，前回の投稿内容をサラッとでも良いので，読んでおくことをオススメします．

前回，「割と簡単に実装できるであろうメソッドチェーンを，わざわざYコンビネータを無意味に使って実装する」という中々不毛なことをやっていたのですが，今回は不毛（お遊び）な投稿第二弾．

題して

Yコンビネータを使って，PHPで車輪の再開発しよう！（ジェネレータ編）

をお届けします．

といっても，「とりあえず前の記事読んどけや！」という投げっぱなしな態度は如何なものかと思いますので，前にやったことをかいつまんでおさらいしておきましょう．

まず，そもそもYコンビネータってのは何かってーと，「関数を渡すと，その関数が再帰できるように加工されて帰ってくる，そんな魔法の関数」です．

終わり！
定義は↓↓↓こ～んな↓↓↓感じです

Yコンビネータ（例）

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

で．使い方は↓↓↓こ～んな↓↓↓感じ

使い方

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

Yコンビネータのコード注釈に「例」と書いてありますが，実はYコンビネータは一つじゃありません．
いろいろな定義の方法があるのですが，この投稿では↑の方の定義をYコンビネータとしておきます．
とりあえず，このY関数をPHPソースのどっかに定義して使えるようにすれば，それで自在に遊ぶことができるようになります．

前回も説明しましたが，基本的には，Yコンビネータは「無名関数」を渡して「再帰（ループ処理）」を実現するもので，計算機科学に端を発して，極めて現実的な要請で生まれた由緒正しきプログラミングテクニックです．

ただ，その論理背景はそこそこ難解なので，そっちまで踏み込むことはしません．（完全に理解するためには，ラムダ計算の知識が必須です．僕はそのあたりまで踏み込んで解説するような知識は持ち合わせていないので，深くは掘り下げません）

閑話休題．
前回Yコンビネータを使って遊んだテクニックが，次のコードのようなものです．

前回使ったテクニック

$result = Y(function(callable $callback){
    return function($val) use(&$callback){
        // $valで何か処理する
        $val = someOperation($val);

        return function() use(&$callback, &$val){
            return $callback($val);
        };
    };
});

前回は，この再帰関数に対して無意味に大幅な肉付けをして，「メソッドチェーンできたでぇ！」なんてことをやっていたわけですが，ざっくりまとめると

本来再帰（ループ）で使うはずのYコンビネータを，ループしないで使ってみよう

ってな趣旨で遊んだわけでした．

今回のお遊び第二弾は，遊びをほどほどに，少し本質に迫ってみることにします．

そもそも，前回ってどんなことをやってたんだっけ？

前回の投稿を読んで下さった方ならご理解頂けると思いますが，前回のアレはいわゆる「お遊び」で，Yコンビネータで面白いことしてみたよ！の域を抜け出ないわけですが，ただ一つだけ，すごく真面目に実装していた箇所があります．

それが，少し上に載せたコード．
今回の話で，すごーーーく重要な概念となるので，念のためもう一度載せておきます

これ，すごーーーく重要！！！

$result = Y(function(callable $callback){
    return function($val) use(&$callback){
        // $valで何か処理する
        $val = someOperation($val);

        return function() use(&$callback, &$val){
            return $callback($val);
        };
    };
});

見た目，Yコンビネータっぽい使い方はしているような気はするんですが，よくよく見ると，こいつはすぐ値を返してしまいます・・・
そう，こんな値が帰ってきます．

再帰関数を実行したはずなのに，すぐにこんなのが帰ってきた・・・

function() use(&$callback, &$val){
    return $callback($val);
}

帰ってくるのは関数ですよね，それはまぁいいです．
でも，関数の中がちょっと変・・・

「return $callback($val);」ってなんだよ・・・

いや，勿体ぶった言い回しはさすがにウザいのでやめましょう．

「$callback」は，自分自身を呼ぶためのコールバックなのでした．

これが「自分自身」

function($val) use(&$callback){
    // $valで何か処理する
    $val = someOperation($val);

    return function() use(&$callback, &$val){
        return $callback($val);
    };
}

普通の使い方であれば，この$callbackを直接呼んで，階乗を求めたりフィボナッチ数を求めたりXMLを解析したりフォルダを探索してごにょごにょしたりするわけです．

それがドノーマルな使い方なのですが，上のような感じでクロージャで包んで返すと

（とりあえず処理続けるつもりはあるんだけども）一旦こちらからは以上で～す

な状況を作れます．

こういうのを「"一旦"制御を戻す」と呼ぶことにしましょう．

この「”一旦”制御を戻す」というのが，今回の投稿の最大のキモです．

ジェネレータってなんぞ？

ジェネレータてのは，平たく言うと「好きな条件で好きなだけ値を返してくれる制御構造」のことを言います．

高校の数学の授業を覚えていますか？
こんな風な定義が出てきたはずです．

[x|x\in Z, 10\leq x < 100]

これは

xはとりあえず整数な．
あ，言っとくけど，10以上100未満じゃないと叩くよ，念のため・・・

みたいな意味になるって，皆さん覚えてらっしゃいます？

こんな感じの，数学で言う集合の定義のようなルール通りに，その要素を自動で作り出してくれるような機能を，一般にジェネレータ(Generator:生成器)と呼んだりします．

例えば，関数型言語で有名なHaskellでは，こんな感じでジェネレータ（リスト内包表記といいます）を使ったりします．

Haskellのリスト内包表記

 [x | x <- [1 ..], x >= 10, x < 100]

上のリスト内包表記は，数学の集合表記とほぼ同様の意味をもちます．
そして，最終的には

[10, 11, .. 99]

のように評価されます．
（実際には，Haskellは遅延評価のため，このように集合の条件を満たす全ての要素が含まれるリストが，一遍に得られるわけではありません．ほしい分だけ，順繰り提供してくれる感じで，無駄な計算をしないのです）

PHP(ver 5.5以上)にも，このジェネレータの機能は備わっておりまして，Haskellほど柔軟に（しかもわかりやすく）条件指定できるわけではないですが，Haskellのように無限のリストを用意することも可能です．

上の例をPHPで書くと，こんな感じになります．

PHPのジェネレータ

$generator = function(){
    for($i = 1; $i < 100; $i++) {
        if($i >= 10) {
            yield $i;
        }
    }
};

foreach($generator() as $value) {
    // $valueには，10以上100未満の値が入ってきて
    // 99が帰ってきたらループ終了
}

なんか関数を作って，それをforeachに渡している所が変態的ですが，これでしっかりと上のHaskellの例と同じように（Haskellの場合は，リスト内包表記はリストが生成されるけども）動きます．
ポイントは，$generator関数の中にあります．

yieldって，見慣れないキーワードが出てきていますね．
yieldは「産出」とか「生み出す」って意味があるのですが，yieldキーワードの行にコードが到達すると，一旦ジェネレータからforeachを実行している側に制御が戻ります．
で，$valueに，yieldされた（生み出された）値が入ってくるって寸法です．

ちなみに，$generator関数みたいな形式の関数（yieldを使っている関数）のことを「ジェネレータ関数」と呼んだりしまして，PHPの内部的には，この関数が呼ばれたときにGenerator型という型のインスタンスが帰ってくるようです．

このGenerator型は，Iteratorインタフェースを実装しているため，foreachループで問題なく回せるって理屈だとか．

上のforeachループでは，かっこ内の左辺で$generator関数をコールしているため，結果としてGeneratorクラスのインスタンスに対してforeachしていることになるわけですね．

ちなみに，こんな定義でもOKです．

$generator = function(){
    yield 1;
    yield 2;
    yield 3;
    yield 4;
    yield 5;
};

この場合，foreachループに$generator()を渡せば，$valueには「1, 2, 3, 4, 5」がわたってきて，もうyieldする（生み出す）ものが無いため，ループは終了します．

ついでに，こんな風にすると，Haskellの無限リスト（のようなもの）も実現できます．

PHP版無限リスト（のようなもの）

$generator = function(){
    $i = 1;
    while(true) {
        yield $i;
        $i = $i + 1;
    }
};

ジェネレータ関数自体は，whileループで無限に回るので，決して終わることはありません．
これを使って，呼び元のforeach側で，条件付けでbreakするなどすれば良いわけですね．

PHP版無限リスト（のようなもの）を使う例

foreach($generator() as $value) {
    var_dump($value);
    if($value >= 10000) {
        break;
    }
}

この例では，1から順にvar_dumpしていき，10000を出力したところでループを抜けます．

ほかにも，Generatorには制御元からジェネレータに対して値を書き込んだり（send），ジェネレータ内部で強制的に例外を発生させたり（throw）といった機能が備わっています．
これらは，呼び元のforeach側から，ジェネレータ関数自体を制御するために使えるメソッド達なのですが，この説明は後々にします．

ＯＫ！　Yコンビネータで再開発じゃ

さて，こんな制御構造をYコンビネータで実装してみるのが本稿の趣旨なのですが，まず作る対象の「ジェネレータ」の特徴を洗い出してみましょうか．
何事にも言えることですが，作る「何か」がわかっていないと，絶対にその「何か」は作れないもんね♪

まず，ジェネレータとして振る舞うためには何が必要でしょうか？
PHPのジェネレータ関数は，叩くとGenerator型のインスタンスが帰ってくるのでしたね．
で，このGenerator型はIteratorインタフェースを実装しているのでした（ちなみに，Generator型はインタフェースではなくクラスです）．

作る「何か」は，Iteratorインタフェースを実装せよ

まずこんな感じかな？
というか，Generatorクラスも実装すべきなんですが，Generator型のクラスはnewできないきまりになっているので，それっぽく振る舞うようにメソッドだけ追加しちゃいましょう．

getReturn，throw，sendメソッドを，それぞれ模倣せよ．

これは，割とめんどそうなので，後で考えることにしましょう．

それよりも何よりも，まずやるべきことがあるんですよ奥さん．
これです↓

特定の条件下で処理を中断でき，必要に応じて再開できるような機能を提供せよ．

はい，yieldですね．

ん？処理を中断して再開？？？
それって，前にやったような・・・

ジェネレータとYコンビネータの不思議なカンケイ

前の章の，ジェネレータになる条件を，改めて見てみましょう
ジェネレータとなるには，こんな条件が必要なのでした．

1. Iteratorインタフェースを実装していること
2. getReturn, throw, sendメソッドを持っていること
3. 特定の条件下で処理を中断でき，必要に応じて再開できるような機能を持っていること

1番目に関しては，ジェネレータと言うより，foreachループで回せるようにするための必要条件です（逆に言えば，あるクラスがIteratorインタフェースを実装していれば，foreachループで回せるようになります）

2番目の条件は，Generator独自で提供している機能を提供するものです．

PHPのジェネレータは，コンストラクタにエラーを発生させる機構が仕込んであるらしく，newでオブジェクトを生成することはできません．
また，Generatorクラス自体がfinalであるため，Generatorを継承したクラスも作れない模様．
そのため，今回の実装では，ジェネレータ自体に用意されている「getReturn」「throw」「send」の３つのメソッドを，同様のシグニチャで，独自実装することとします．

でですが，ジェネレータとしての要件を満たすための条件の３つめ

特定の条件下で処理を中断でき，必要に応じて再開できるような機能を持っていること(yield)

実はこれ，限りなく近いことをすでにやっているんです．

まず，状況を確認するために，ジェネレータ関数を今一度見ておきましょう．

ジェネレータ関数

$generator = function(){
    $message = 'ステップ1開始';
    yield 1;
    $message = 'ステップ2開始';
    yield 2;
    $message = '処理終了';
};

話を単純にするために，思いっきり簡単なジェネレータ関数にしてみました．
このジェネレータ関数をforeachで回すと，1, 2と値が取得でき，ループが終了するわけです．
そのループを回るたびに，内部の$message変数が書き換わっていくわけですが．．．

これを↓こんなforeachループで回してみます

foreachループ

foreach($generator() as $value) {
    var_dump($value);
}

面倒くさいのでvar_dumpの出力結果は載せませんが，次のような処理順でループが動作するはずです．

処理順	処理内容	処理される場所
1	$messageに"ステップ1開始"が入る	ジェネレータ関数内
2	1がyieldされる	ジェネレータ関数内
3	$valueに1が入る	foreachで回す側
4	1がvar_dumpされる	foreachで回す側
5	$messageに"ステップ2開始"が入る	ジェネレータ関数内
6	2がyieldされる	ジェネレータ関数内
7	$valueに2が入る	foreachで回す側
8	2がvar_dumpされる	foreachで回す側
9	$messageに"処理終了"が入る	ジェネレータ関数内
10	ループを抜けて処理終了	foreachで回す側

実際は，Iteratorでは状態を，初期の状態に設定したり(rewind)，もう一回ループを回していいかどうか確かめたり(valid)，イテレータから値を取得したり(current)するような処理が実施されるわけですが，細かいことを抜きにすると，上の表のような処理順で，処理が進んでいきます．

注目したいのは処理順2と処理順7のyieldコールされる箇所です．
ジェネレータは，yieldがコールされると，自分から一旦制御が離れ，呼び出し元(foreach)へと戻るわけです．
さて，ここで質問．

処理順2でyeildされて，foreachに制御が戻ってきたとき，果たしてジェネレータ関数内の$message変数は，何になっているでしょう？

正解は

"ステップ1開始"

ですね．

yieldされた場合は，「"一旦"制御が戻る」ため，そこはforeachループの領域です．
ジェネレータ関数内の$messageは触りようがないため，yield直前の状態のままのはずなわけです．

次に$messageが更新されるタイミングは，処理順5．

つまり，「１回目のループが終わって，次のループに入った時」になります．

そこで重要なのが，以下のような事実です．

処理順4の処理が終わって，処理順5が開始されるまでの間，$messageの状態は"ステップ1開始"

つまり，いくら次のループに入っても，実際に$messageに値が書き込まれるまでは，前の状態を保持しているのです．

この例では，変数は$messageしか出てきませんでしたが，もしほかにも変数があれば，それらの状態は，yieldで，一旦完全に保存されます．

そして，ループ再開と同時に，それらの状態をまとめて復活させるのです．

もしそれができないと，上のような簡単なジェネレータならまだしも，複雑な条件でジェネレータを動かせなくなってしまいます．
(ちなみに，実際にループを一つ進めるのは，Iteratorインタフェースのnextメソッドの役割なので，nextが呼ばれると，ジェネレータ関数の内部状態が復活すると考えても差し支えありません．)

そんな事実を踏まえつつ，以下のコードをご覧ください．

$combinator = Y(function(callable $callback) use(&$state){
    return function($param, $state) use(&$callback) {

        $result = someOperation($param, $state);
        $state['result'] = $result;

        return function($param)use(&$callback, &$state){
            return $callback($param, $state);
        };
    };
});

冒頭でおさらいしたコードブロックに少し毛が生えた程度のコードです．
このコードは，Yコンビネータを使ってはいますが，繰り返し説明した通りずっとぐるぐると回ることはありません．
再帰関数(と言っていいのか？)内でreturnしているため，すぐに値が帰ってきます．

ただ，帰って来る値は，もう一度自分を呼ぶための関数ってだけです．
これ，実はジェネレータ関数のyieldと同じような構造になっているんです．

まず，事実の1つ目

必要に応じて処理を中断でき

ですが，Yコンビネータに渡した関数内ですぐreturnしているため，処理を中断したと言えなくもありませんね．

そして

必要に応じて再開できるような機能を～

の部分なのですが・・・

この再帰関数を一回実行して，戻り値を何かに入れるとしましょう

一回だけ実行

$some = $combinator->__invoke('hogehoge', []);

さて，このとき$someは関数の形になっているはずですね．
こんなのが帰ってきているはずです．

$someの中身

function($param)use(&$callback, &$state){
    return $callback($param, $state);
};

今まで，何度か見てきた話です．
(当然，$callbackを呼べば，もう一回処理が繰り返されますね）

では，$stateの値はどうなっているんでしょうか？？？

正解はコチラ

someOperation関数によって，$paramと$stateが料理された「何か」が，$state['result']に入っているはず

です．

$stateは，プログラム実行中の何らかの状態である．

という見方をすると，このYコンビネータ(で作った関数)を実行すると帰ってくるのは

"直近の状態を伴って"，引き続き処理を続行させる能力のある関数

であると言えます．

2回実行

$some = $combinator->__invoke('hogehoge', []);
$some = $some->__invoke('fubafuga');

とすれば，この(Yコンビネータで作られた)関数は
「'fugafuga'」と「直前の状態($state）」を引数として，もう一回ど頭から処理されます．
そして，その時に入ってくる$stateは，初回呼び出し時に指定した[ ]ではなく，計算された$stateですね．

これが

必要に応じて，（前の状態を保持したまま）処理を再開できる

と言い切れる所以です．

さいごに

というわけで，ジェネレータを作るための達成条件３つをどうにかクリアすることができそうです．
では，早速実装していきましょう！

と言いたい所ですが，長くなったので続きはまた今度♪

お付き合い，ありがとうございました．