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.