Saturday 20 September 2014

PHP: generators

G'day:
Duncan's my muse today. Like me, my mate Duncan has recently moved from our defunct CFML team to the PHP team. And like me, Dunc now needs to learn PHP. He's logging his progress as well, and if this sort of thing interests you (following our progress), then maybe keep an eye on what he's doing too.



Part of Dunc's problem today ("Project Euler: problem 2 (PHP)") involves the Fibonacci sequence, and this quickly gave me an in to blog about something I noticed PHP had the other day: generators (PHP's implementation). This is a concept CFML doesn't have, and I've raised this with both Railo (RAILO-2942) and Adobe (3555025).

Basically a generator is a function which defines logic which describes a sequence, and return an Iterator to traverse the sequence. This is implemented by using a yield statement to return the next value in a sequence; the difference being the next time the function is called, processing resumes after the yield statement, rather than from the beginning of the function. PHP wraps all this up in an Iterator object, so one fetches the current value by calling current() on the iterator, and progresses to the next item in the sequence by calling next().

The logic behind the Fibonacci sequence is a sitter for this sort of thing:

// fibonacci.php

function createFibonacciSequence(){
    $queue = [0,1];
    while (true){
        $currentSum = array_sum($queue);
        array_push($queue, $currentSum);
        $nextInSequence = array_shift($queue);
        yield $nextInSequence;
        // the next call will resume here
    }
}

Notes:

  • The logic behind the Fibonacci sequence is the next number is the sum of the preceding two numbers. So at any given time I need to remember only the last two numbers, as we can generate the next one from those.
  • I seed an array with the first two elements in the sequence;
  • and loop for the full length of the possible sequence (which is "forever" in the case of the Fibonacci Sequence);
  • Whilst we have these two numbers, we need to remember what their sum was...
  • ... and it'll be the value the sequence returns in two values' time, so stick it at the end of the array.
  • The next value to return is the first element in the array, so extract it...
  • ... and return it.
  • The next time the function is called, it'll resume after the yield... so go back to the top of the loop.

That's pretty simple logic.

To create a new Fibonacci iterator is just a matter of calling the function:

$fibonacciSequence = createFibonacciSequence();

Now I can call methods from the Iterator interface on $fibonacciSequence. In this case I just need current() and next() to get the first ten numbers in the sequence:

for ($i=1; $i++ <= 10;){
    $nextFibonacciNumber = $fibonacciSequence->current();
    echo "$nextFibonacciNumber "; 
    $fibonacciSequence->next();
}

This outputs:

0 1 1 2 3 5 8 13 21 34

Cool.

The code to do the sequence is more complicated than Duncan's, but I think it makes for cleaner code (I'm still trying to coerce Dunc into reading Clean Code...), as it nicely separates-out the logic behind the Fibonacci stuff from the rest of the logic of his exercise which is to conditionally tally them. For such an easy exercise this might be overkill, but I think compartmentalising one's code as a general practice is a good starting point when writing any code.

But, anyway, this article is not a critique of Dunc's work, it was simply an excuse to try out generators. I think they're the sort of thing that initially one goes "hmmm... yeah, OK?" in a not very convinced way, but after one gets a handle on them, I think they're the sort of thing one will start finding uses for all over the place. Besides that, I've learned a few more things about PHP today, which is a definite win. I think I deserve a Guinness now (I'm in Galway today).

--
Adam