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.