PHPで関数の末尾呼び出しを最適化する

末尾呼び出し最適化とは、関数の呼び出しをjump命令に書き換えることによる最適化のこと。

通常の関数呼び出しはreturnで呼び出し元の位置に帰ってくる必要がある。
しかし例えば

<?php
function multi($a, $b){
  return $a * $b;
}
function plus($a, $b){
  return $a + $b;
}
function calc($op, $b, $c){
  if ($op === '+')
    return plus($b, $c);
  else if ($op === '*')
    return multi($b, $c);
  else
    return 0;
}
var_dump(calc('*', 3, 5));
// int(15)

この calc という関数から plus や multi という呼び出しにおいて、calc に戻ってくる必要はない。
multi の計算結果がそのまま calc の結果になる。

PHPは（というか基本的に手続き型言語は）関数の末尾呼び出し最適化をしない。
xdebugには関数呼び出しが深くなると中断する機能すらある。
普通は問題にならないが、昨日書いた パーサーコンビネーター では、関数を次々貼りあわせていくので、ひとつのパーサーを連結するだけで関数呼び出しがいくつか入れ子になる。

そこで手動で関数呼び出しをgotoに置き換える。
上の例は

<?php
$ret = 0;
$args = ['*', 3, 5];
goto calc;

plus:
  $ret = $args[0] + $args[1];
  goto ret;

multi:
  $ret = $args[0] * $args[1];
  goto ret;

calc:
  $op = $args[0];
  $args = [$args[1], $args[2]];
  if ($op === '+')
    goto plus;
  else if ($op === '*')
    goto multi;
  else
    goto ret;

ret:
  var_dump($ret);
  // int(15)

このようになる。
plus や multi から calc には戻らない。直接 ret に飛んで結果を表示する。

パーサーの関数を手動でアセンブラっぽく変換していくと

function parserBind(...$args)
{
    return f(function($m, $k){
        $f = function($s, $cok, $cerr, $eok, $eerr) use ($m, $k){
            $mcok = function($x, $s, $err) use ($m, $k, $cok, $cerr){
                $peok = function($x, $s, $err2) use ($cok, $err){
                    return $cok($x, $s, mergeError($err, $err2));
                };
                $peerr = function($err2) use ($cerr, $err){
                    return $cerr(mergeError($err, $err2));
                };
                $a = $k($x);
                if ($a instanceof Any)
                    $a = $a->cast($m);
                $f = $a->unParser();
                return $f($s, $cok, $cerr, $peok, $peerr);
            };
            $meok = function($x, $s, $err) use ($m, $k, $cok, $cerr, $eok, $eerr){
                $peok = function($x, $s, $err2) use ($eok, $err){
                    return $eok($x, $s, mergeError($err, $err2));
                };
                $peerr = function($err2) use ($eerr, $err){
                    return $eerr(mergeError($err, $err2));
                };
                $a = $k($x);
                if ($a instanceof Any)
                    $a = $a->cast($m);
                $f = $a->unParser();
                return $f($s, $cok, $cerr, $peok, $peerr);
            };

            $f = $m->unParser();
            return $f($s, $mcok, $cerr, $meok, $eerr);
        };

        return new Parser($f);
    }, ...$args);
}

このようなパーサーモナドのbind関数は

_call_bind:
    $call = $context[0]->unParser();
    $args = [
        $args[0],
        ['_call_bind_mcok', [$context[0], $context[1], $args[1], $args[2]]],
        $args[2],
        ['_call_bind_meok', [$context[0], $context[1], $args[1], $args[2],
                             $args[3], $args[4]]],
        $args[4]
    ];
    goto _call;

    _call_bind_mcok:
        ;
        $any = $context[1]($args[0]);
        if ($any instanceof Any)
            $any = $any->cast($context[0]);
        $call = $any->unParser();
        $args = [
            $args[1], $context[2], $context[3],
            ['_call_bind_mcok_peok', [$context[2], $args[2]]],
            ['_call_bind_mcok_peerr', [$context[3], $args[2]]]
        ];
        goto _call;

        _call_bind_mcok_peok:
            ;
            $call = $context[0];
            $args = [$args[0], $args[1], mergeError($context[1], $args[2])];
            goto _call;
        _call_bind_mcok_peerr:
            ;
            $call = $context[0];
            $args = [mergeError($context[1], $args[0])];
            goto _call;

    _call_bind_meok:
        $any = $context[1]($args[0]);
        if ($any instanceof Any)
            $any = $any->cast($context[0]);
        $call = $any->unParser();
        $args = [
            $args[1], $context[2], $context[3],
            ['_call_bind_meok_peok', [$context[4], $args[2]]],
            ['_call_bind_meok_peerr', [$context[5], $args[2]]]
        ];
        ;
        goto _call;

        _call_bind_meok_peok:
            ;
            $call = $context[0];
            $args = [$args[0], $args[1], mergeError($context[1], $args[2])];
            goto _call;
        _call_bind_meok_peerr:
            ;
            $call = $context[0];
            $args = [mergeError($context[1], $args[0])];
            goto _call;
    ;

...


    _call:
    list($label, $context) = $call;

    if ($label === '_call_bind') goto _call_bind;
    if ($label === '_call_bind_mcok') goto _call_bind_mcok;
    if ($label === '_call_bind_mcok_peok') goto _call_bind_mcok_peok;
    if ($label === '_call_bind_mcok_peerr') goto _call_bind_mcok_peerr;
    if ($label === '_call_bind_meok') goto _call_bind_meok;
    if ($label === '_call_bind_meok_peok') goto _call_bind_meok_peok;
    if ($label === '_call_bind_meok_peerr') goto _call_bind_meok_peerr;

...

    _ret:
    return $ret;

このようになる。

そんなわけで昨日書いた問題を解決した。これで複雑なパーサーを書いてもスタックを浪費しない。

初めてgotoを本格的に使ったが、元々のPHPコードが関数型のように書いていたので、機械的に変換できるし何処に飛ぶか分からないようなことにはならなかった。
gotoが無ければ詰んでいたかもしれない。whileとbreakでは無理だよねきっと。
追記：gotoに変数を指定できないのでどこかに分岐をまとめる必要がある。この書き方なら、普通に巨大switchなどでも良いかも。構造化はできずフラットにする必要があり、あまり見た目は変わらないのだが。