No tail call optimization in PHP (yet)
By Steve Claridge on 2014-03-15.
In a previous post about functional programming in PHP I used an example of reading a text file to show how a functional style of programming is different from 'normal' PHP coding. The example was functional in that it used first-class functions (a function treated like a variable) but there was one bit that still used an imperative style, the while loop at the end:
while ( ( $l = $line() ) != null )
{
echo $l;
};
This while loop is a sequence of statements that change a program state, whereas we want to write some code that describes how the next line will be read from the file. To do this we need to write a recursive function instead of the while loop and this is where we run into trouble because PHP doesn't have tail-call optimisation.
A tail-call is simply a function that calls another function (or itself) as its last statement, like this one:
function a()
{
//do some stuff
return b();
}
What is tail call optimisation (also know as tail call elimination)? The Wikipedia article linked above does a good job of explaining it but I'll have a go anyway: When an OS creates a new function (called subroutine at assembler/OS level) it allocates some memory for that function to run in; the memory space that is allocated for this comes from 'the stack' and is called a 'stack frame'. When a subroutine is called the stack frame is allocated and when the subroutine is finished the stack frame is released.
But what about if you have a function that calls itself recursively? Something like this:
function a( $v )
{
$v = $v + 1;
if ( $v == 100000 )
{
return $v;
}
return a( $v );
}
Memory gets allocated for a() but a() then calls itself 100000 times to increment the value of $v and none of the a() calls complete until $v = 100000. So we've created 100000 stack frames for all of our functions. Well, actually we haven't created 100000 at all because PHP throws this error:
PHP Fatal error: Maximum function nesting level of '100' reached, aborting! in /tmp/one.php on line 8
The PHP interpreter sees the recursion and kills it off after 100 calls; not very useful! So how do other languages deal with this? They don't actually create 100000 stack frames either, instead they use tail-cal optimisation, which basically means that the compiler/interpreter is smart in that it sees that the same function is being called and re-uses the one stack frame. I would guess it does that by (I'm not about to go poking through Python or Ruby's source code to find out) modifying the tail-call to be a GOTO statement instead of a function call, something like:
function a( $v )
{
JMP:
$v = $v + 1;
if ( $v == 100000 )
{
return $v;
}
goto JMP;
}
Functional-programming features are being added to PHP but it's not ready for functional prime-time without tail-call optimisation.