Trampoline

Trampolines are a technique used to avoid blowing the call stack when doing recursive calls. This is needed because PHP does not perform tail-call optimization.

For more information about what is tail-call optimization (or TCO), you can read : http://stackoverflow.com/questions/310974/what-is-tail-call-optimization#answer-310980

For a more in depth definition of trampolines and recursion as a whole, I can recommend you read http://blog.moertel.com/posts/2013-06-12-recursion-to-iteration-4-trampolines.html which is using Python but should be easy enough to understand.

Installation

composer require functional-php/trampoline

Basic Usage

If we have the following recursive function:

<?php

function factorial($n, $acc = 1) {
    return $n <= 1 ? $acc : factorial($n - 1, $n * $acc);
};

echo factorial(5);
// 120

We need to simply replace the recursive call by a call to the bounce function:

<?php

use FunctionalPHP\Trampoline as T;

function factorial($n, $acc = 1) {
    return $n <= 1 ? $acc : T\bounce('factorial', $n - 1, $n * $acc);
};

echo T\trampoline('factorial', 5);
// 120

The bounce and trampoline functions accepts anything that is deemed a valid callable by PHP.

The trampoline function will also accept an instance of Trampoline created by bounce but will ignore any arguments in this case.

Helpers

You can also call statically any function from the global namespace on the Trampoline class if you prefer this style:

<?php

use FunctionalPHP\Trampoline\Trampoline;

echo Trampoline::factorial(5);
// 120

echo Trampoline::strtoupper('Hello!');
// HELLO!

This will however not work for functions inside a namespace.

If you want to have a ready to call function when using a trampoline, you can use the trampoline_wrapper helper. It will create a wrapper function that will call trampoline for you and return the result.

<?php

use FunctionalPHP\Trampoline as T;

function factorial($n, $acc = 1) {
    return $n <= 1 ? $acc : T\bounce('factorial', $n - 1, $n * $acc);
};

$fact = T\trampoline_wrapper('factorial');

echo $fact(5);
// 120

Alternative method

The library also contain an alternative implementation to run tail recursive function without risking a stack overflow based on an argument queue instead of a trampoline.

You will need to use the $this variable as the recursive function. Here is the factorial example using this second method.

<?php

use FunctionalPHP\Trampoline as T;

$fact = T\pool(function($n, $acc = 1) {
    return $n <= 1 ? $acc : $this($n - 1, $n * $acc);
});

echo $fact(5);
// 120

At this time, only anonymous functions (ie instance of the Closure class) are supported. But as soon as PHP 7.1 is released you will be able to use any callable.

From a performance standpoint, there is no measurable difference between the two approaches.

Testing

You can run the test suite for the library using:

composer test

A test report will be available in the reports directory.

Contributing

There shouldn't be much to contribute except the potential bug but any kind of contribution are welcomed! Do not hesitate to open an issue or submit a pull request.