Darren Mothersele

Software Developer

Warning: You are viewing old, legacy content. Kept for posterity. Information is out of date. Code samples probably don't work. My opinions have probably changed. Browse at your own risk.

Playing with Infinity in PHP

Feb 18, 2016

web-dev

I’ve been playing around with lazy evaluation in PHP. This is made possible by using Generators, added to PHP 5.5 and refined in PHP 7. You can do some cool stuff with infinite (or very large) data sets, and avoid getting stuck in infinite loops.

Imagine you want to create an infinitely long array of the same value. Here’s a simple bit of code that would do this. Obviously don’t try this. Just read the code and imagine a world where this is a good idea…

function repeat($i)
{
    $output = [];
    while (true)
    {
        $output[] = $i;
    }
    return $output;
}

This function would never terminate. You get stuck in an infinite loop. while(true) is not something you ever want to see in a program, right?

Well, not if you do lazy evaluation. In this context lazy means you only evaluate as much code as you need to get the result. So you can have large, even infinite, sets of data, without getting stuck in long, or infinite, loops.

PHP has a feature for lazy evaluation. It’s called a Generator, summoned into being using the magical yield keyword. Here’s the stupid repeat, but this time as a generator…

function repeat($i)
{
    while (true)
    {
        yield $i;
    }
}

You have to be careful using infinite sets. You can still easily create an unterminating program if you tried to print out the whole of this Generator function.

But, what if we just wanted to work with the first 5 items from our infinite computation. This is now possible because of lazy evaulation. Here’s a take function that will take any number of items from any Generator:

function take($i, Generator $generator)
{
    while ($i-- > 0 && $generator->valid())
    {
        yield $generator->current();
        $generator->next();
    }
}

Let’s take 5…

foreach (take(5, repeat('Hello')) as $item)
{
    echo $item, PHP_EOL;
}

OK, that was a stupid example. What about something a bit more interesting? How about the classic fibonnacci sequence generator?

For some reason the examples I found on both Stack Overflow and the PHP Manual were more complex than they needed to be.

Here is the simplist infinite fibonacci generator I can think of…

function fib()
{
    yield $i = 0;
    yield $j = 1;
    while (true) {
        yield $k = $i + $j;
        $i = $j;
        $j = $k;
    }
}

And here’s the first 50 fibonacci numbers…

foreach (take(50, fib()) as $item)
{
    echo $item, PHP_EOL;
}

And, here’s the first 10, skipping the first 0 using a tail function:

function tail(Generator $list)
{
    $list->next();
    yield from $list;
}

foreach (take(50, tail(fib())) as $item)
{
    echo $item, PHP_EOL;
}

In case you’re curious, there are actual use cases for this. For example, this Quad Tree data structure implementation.

Generators may not offer better performance in terms of execution speed. But, generator based algorythms offer a much lower memory overhead as you’re not having to pass around the full data sets.