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.
composer require functional-php/trampoline
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);
// 120We 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);
// 120The 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.
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);
// 120The 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);
// 120At 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.
You can run the test suite for the library using:
composer test
A test report will be available in the reports directory.
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.