I've wanted to avoid blowing the stack while creating a system similar to function advice or method combination. This involves tree traversal (in my implementation), conditional recursion, etc. One of the very few methods available for converting recursion into loops is trampolining. I've tried this and then found out that I need to implement eg. short-circuit boolean expression evaluation. In short, I've implemented a combination of a trampoline with continuations, and now I'm trying to find out whether this construction exists and what its name may be - as I've been unable to find any such already existing construct.
My implementation - bounce evaluation with manual stack handling:
function immediate($bounce, $args)
{
$stack = array($bounce->run($args));
while ($stack[0] instanceof Bounce) {
$current = array_pop($stack);
if ($current instanceof Bounce) {
$stack[] = $current;
$stack[] = $current->current();
} else {
$next = array_pop($stack);
$stack[] = $next->next($current);
}
}
return $stack[0];
}
The Bounce class:
class Bounce
{
protected $current;
protected $next;
public function __construct($current, $next)
{
$this->current = $current;
$this->next = $next;
}
public function current()
{
$fn = $this->current;
return $fn();
}
public function next($arg)
{
$fn = $this->next;
return $fn($arg);
}
}
And, as an example, short-circuit AND implementation (ie. in JavaScript first(args) && second(args)). $first and $second are functions that may return Bounces as well.
return new Bounce(
function () use ($first, $args) {
return $first($args);
},
function ($return) use ($second, $args) {
if (!$return) {
return $return;
}
return new Bounce(
function () use ($second, $args) {
return $second($args);
},
null
);
}
);
This allows for general recursion, with overhead of approximately 3 function calls per normal function call (though in the general case for variable iteration count, it is quite cumbersome to write and requires 'lazy recursion').
Has anyone seen such a structure before?
