functional-php / trampoline
Trampoline implementation for PHP.
Installs: 16 606
Dependents: 1
Suggesters: 0
Security: 0
Stars: 35
Watchers: 3
Forks: 3
Open Issues: 0
Requires
- php: >=5.6.0
Requires (Dev)
- atoum/atoum: *
This package is auto-updated.
Last update: 2024-10-21 20:51:50 UTC
README
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.