Tail Recursion does not work

[DrDub]

The code in https://gist.github.com/beberlei/4145442 changes the recursive call in line 49 to be a call to the instance variable $func, which in turn is changed in the line 19. Through that then the recursive calls return immediately, storing the arguments in the $acc instance variable. The re-implementation in functional-php does not do that, rendering the tail_recursion a noop.

Compare the output of these two scripts:

functional-php code

<?php

function tail_recursion(callable $fn): callable
{
    $underCall = false;
    $queue = [];
    return function (...$args) use (&$fn, &$underCall, &$queue) {
        $result = null;
        $queue[] = $args;
        if (!$underCall) {
            $underCall = true;
            while ($head = \array_shift($queue)) {
                $result = $fn(...$head);
            }
            $underCall = false;
        }
        return $result;
    };
}

function fac($n, $acc = 1) {
    if ($n == 1) {
        echo (new Exception())->getTraceAsString()."\n";
        return $acc;
    }
    
    return fac($n - 1, $acc * $n);
};

$fac_tr = tail_recursion('fac');

echo $fac_tr(10)."\n";

The output is:

#0 tailrec_functional.php(27): fac()
#1 tailrec_functional.php(27): fac()
#2 tailrec_functional.php(27): fac()
#3 tailrec_functional.php(27): fac()
#4 tailrec_functional.php(27): fac()
#5 tailrec_functional.php(27): fac()
#6 tailrec_functional.php(27): fac()
#7 tailrec_functional.php(27): fac()
#8 tailrec_functional.php(27): fac()
#9 tailrec_functional.php(13): fac()
#10 tailrec_functional.php(32): {closure}()
#11 {main}
3628800

highlighting 10 stack frames are used.

While the gist linked:

<?php
class TailRecursion
{
    public $func;
    public $acc;
    public $recursing;

    public function tail()
    {
        return call_user_func_array($this->func, func_get_args());
    }

    public function getClosure($fn)
    {
        $this->acc = array();
        $this->recursing = false;
        $fn = $fn->bindTo($this);

        return $this->func = function() use ($fn) {

            $this->acc[] = func_get_args();

            if ( ! $this->recursing) {
                $this->recursing = true;

                while ($this->acc) {
                    $ret = call_user_func_array($fn, array_shift($this->acc));
                }

                $this->recursing = false;

                return $ret;
            }
        };
    }
}

function tailrec($func)
{
    $tail = new TailRecursion();
    return $tail->getClosure($func);
}

$fac = tailrec(function($n, $acc = 1) {
    if ($n == 1) {
        echo (new Exception())->getTraceAsString()."\n";
        return $acc;
    }

    return $this->tail($n - 1, $acc * $n);
});

echo $fac(10)."\n";

produces:

#0 tailrecursion.php(27): Closure->{closure}()
#1 tailrecursion.php(53): TailRecursion->{closure}()
#2 {main}
3628800

Maybe a solution can be implemented using reflection and renaming the function?

[DrDub]

moving the recursive call to tail_recursion doesn't work either:

function fac($n, $acc = 1) {
    if ($n == 1) {
        echo (new Exception())->getTraceAsString()."\n";
        return $acc;
    }
    
    return tail_recursion('fac')($n - 1, $acc * $n);
}

[DrDub]

Hmm, looking at https://github.com/functional-php/trampoline, a full solution might need two functions.