---
title: Fibonacci Sequence in PHP
packages: [ 'coreutils', 'ghostscript', 'gnuplot', 'imagemagick', 'php',
'repo-copies', 'time', 'utillinux' ]
---
```{pipe="sh > /dev/null"}
# Grab copies of the git repos we need
for R in php-prelude php-core php-easycheck
do
cp -rL "$(repo-copies)/$R" "./$R"
chmod +w "./$R"
done
# Fake the Composer auto-loading
for v in "vendor" "php-easycheck/vendor" "php-core/vendor" "php-prelude/vendor"
do
mkdir -p "$v"
echo "" > "${v}/autoload.php"
done
```
```{pipe="cat > hide"}
#!/bin/sh
INPUT=$(cat)
echo -e "\n$INPUT" >> code.php
```
```{pipe="sh > /dev/null"}
chmod +x hide
(source "$stdenv/setup" && patchShebangs .)
```
```{pipe="./hide"}
```{pipe="cat > init.php"}
runphp"}
#!/bin/sh
cat init.php /dev/stdin | php
```
```{pipe="sh > /dev/null"}
chmod +x runphp
(source "$stdenv/setup" && patchShebangs .)
```
```{pipe="./runphp 1>&2"}
echo "Testing php-easycheck";
require_once('./php-easycheck/tests.php');
runtests();
echo "Testing php-core";
require_once('./php-core/tests.php');
runtests();
echo "Testing php-prelude";
require_once('./php-prelude/tests.php');
runtests();
```
```{pipe="cat > tag"}
#!/bin/sh
echo "" >> code.php
tee -a code.php
```
```{pipe="cat > eps2png"}
#!/bin/sh
set -e
magick -density 128 "$1.eps" "$1.png"
echo -n '
> "$1.html"
echo -n '" alt="' >> "$1.html"
echo -n "$2" >> "$1.html"
echo -n '" />' >> "$1.html"
pandoc -f html -t json "$1.html"
```
```{pipe="sh > /dev/null"}
chmod +x hide
chmod +x runphp
chmod +x tag
chmod +x eps2png
(source "$stdenv/setup" && patchShebangs .)
```
## Exponential Definitions ##
The Fibonacci sequence is a well-known series of numbers which follow a pattern:
it starts `1, 1`{.php} and each subsequent number is the sum of the two
preceding it. We can calculate the `$n`{.php}th element of the sequence like
this in PHP (using handy functions from [PHP Prelude](/git/php-prelude)):
```{.php pipe="./tag"}
defun('mkFib1', function($n) {
return ($n < 2)? 1 // Base case
: mkFib1($n - 1) + mkFib1($n - 2);
});
```
```{pipe="./hide"}
defun('testFibs', function($n) {
return take($n % 10, [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]);
});
deftest('mkFib1', function($n) {
return eq($lhs = map('mkFib1', upto($n % 10)),
$rhs = testFibs($n))? []
: get_defined_vars();
});
```
This is an incredibly naïve approach, since each call to `mkFib1`{.php} can
involve 2 more calls to `mkFib1`{.php}. This recursion is *well-founded*,
since it will always head towards the *base case* where `$n < 2`{.php}, but
there are two problems:
- It's not *tail-recursive*, so it requires a linear number of stack frames,
leading to *stack overflows*.
- It requires an exponential number of recursive calls to reach a base case,
which gives us an exponential running time:
```{pipe="./hide"}
// An instrumented version of mkFib1
$mkFib1_count_ = function($n) use (&$mkFib1_count_) {
if ($n < 2) return [1, 1]; // Base cases count as 1 call
list($c_1, $n_1) = $mkFib1_count_($n - 1);
list($c_2, $n_2) = $mkFib1_count_($n - 2);
return [$c_1 + $c_2 + 1, $n_1 + $n_2];
};
$mkFib1_count = compose('head', $mkFib1_count_);
deftest('mkFib1_count', function($n) use ($mkFib1_count_) {
return eq($lhs = $mkFib1_count_($n % 10)[1],
$rhs = mkFib1($n % 10))? []
: get_defined_vars();
});
```
```{pipe="./runphp > mkfib1.data"}
$data = array_map(function($n) use ($mkFib1_count) {
return [$mkFib1_count($n), benchmark("mkFib1", $n)];
},
upto(15));
echo tabulate("", [""], $data);
```
```{pipe="gnuplot 1>&2"}
reset
set terminal postscript color solid eps enhanced 20
set output "mkfib1.eps"
set size 1.4,1
unset x2tics
unset y2tics
unset key
set title "mkFib1(N)"
set border 11
set xlabel "N"
set ylabel "Recursive Calls" textcolor rgb "blue"
set y2label "Time (seconds)" textcolor rgb "red"
set tics nomirror
set logscale y
set ytics nomirror tc lt 3 textcolor rgb "blue"
set y2tics nomirror tc lt 1 textcolor rgb "red"
set logscale y2
plot "mkfib1.data" using 1:2 with line title "Recursive calls" linetype rgb "blue" lw 2, \
"mkfib1.data" using 1:3 with line title "Time" linetype rgb "red" lw 2 axes x1y2
```
```{.unwrap pipe="sh"}
set -e
./eps2png mkfib1 "mkFib1 is exponentially slow"
```
What's more, a function is a rather clumsy way of representing a sequence, since
the structure isn't immediately available and must be inferred by our users via
some sort of counter. This violates the *Once and Only Once* rule, and is liable
to cause off-by-one errors and such.
So what's the alternative? The trick is to realise that we don't need to provide
*every* element, since our users will only use a *finite* number. The difficulty
is that we don't know how many they'll need!
One simple approach that may spring to mind is asking the user up front how many
elements they need:
```{.php pipe="./tag"}
defun('mkFibs2', compose(map('mkFib1'), 'upto'));
```
```{pipe="./hide"}
deftest('mkFibs2', function($n) {
return eq($lhs = mkFibs2($n % 10),
$rhs = testFibs($n))? []
: get_defined_vars();
});
```
However, this doesn't do what we want. The requirement to know how many elements
are needed is *too strong*; many useful functions like
[filter](http://en.wikipedia.org/wiki/Filter_%28higher-order_function%29) and
[fold](http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29) (AKA
"reduce") require an unknown number of elements in general; for example, filters
don't know how many elements they'll need to discard before finding a match.
This forces us to generate longer and longer sequences, slowing us down by a
logarithmic factor compared to `mkFib1`{.php}:
```{.php pipe="./tag"}
// Note: Since there are infinitely many fibs, we can't fold all of them.
// Instead, $f returns a pair [$stop, $result], where $stop tells us
// when to cut-off the fold and $result is treated in the usual way.
// Fold a sequence generated by mkFib1
defun('fold1', function($f) {
// Fold over the Naturals $n = 0, 1, 2, ...
return loop(function($x, $n) use ($f) {
return $f($x, mkFib1($n));
});
});
// Prevents us applying $f to too many fibs
defun('shortcircuit', function($f, $x, $fib) {
return $x[0]? $x // If $x says stop, return it as-is
: $f($x[1], $fib); // Else call $f
});
// Fold a sequence generated by mkFib2
defun('fold2', function($f) {
// Fold over the Naturals $n = 0, 1, 2, ...
return loop(function($x, $n) use ($f) {
// Fold over 2^$n fibs
list($s, $y) = array_reduce(mkFibs2(pow(2, $n)),
shortcircuit($f),
[false, $x]);
return [$s, $s? $y // If $s(top), return $y
: $x]; // Else restart with $x
});
});
```
```{pipe="./hide"}
deftests(['fold1' => function($n) {
$m = $n % 10;
$rhs = fold1(function($a, $x) use ($m) {
return [count($a) >= $m, snoc($x, $a)];
}, []);
return eq($m + 1, count($rhs))? []
: get_defined_vars();
},
'fold2' => function($n) {
$m = $n % 10;
$rhs = fold2(function($a, $x) use ($m) {
return [count($a) >= $m, snoc($x, $a)];
}, []);
return eq($m + 1, count($rhs))? []
: get_defined_vars();
}]);
// Substitute fold2 which doesn't calculate fibs
defun('fold2_c', function($f, $_) {
return loop(function($_, $n) use ($f) {
return array_reduce(upto(pow(2, $n)),
$f,
null);
}, null);
});
// Simple fold examples
defun('fold_counter', function($fold, $n) {
$calls = 0;
$fold(function($_, $m) use ($n, &$calls) {
$calls++;
return [$m > $n, null];
}, null);
return $calls;
});
defun('fold1_example', fold_counter('loop'));
defun('fold2_example', fold_counter('fold2_c'));
defun('runmem', function($f, $x) { return mem(runphp($f, $x)); });
```
```{pipe="./runphp > mkfib12.data"}
$data = map(function($x) {
return [fold1_example($x), fold2_example($x)];
},
discard_keys(range(0, 150, 3)));
echo tabulate('', '', $data);
```
```{pipe="gnuplot 1>&2"}
reset
set terminal postscript color solid eps enhanced 20
set output "mkfib12.eps"
set size 1.4,1
unset x2tics
unset y2tics
set title "Folding N fibs"
set xlabel "N"
unset logscale y
set border 3
set key left noautotitle
set ytics nomirror
set xtics nomirror
set ylabel "Fibs generated (ignoring recursion in mkFib1)"
set xrange [0:150]
set style line 1 lc rgb "red" lw 3
set style line 2 lc rgb "blue" lw 3
plot "mkfib12.data" using 1:2 with line title "fold1" ls 1, \
"mkfib12.data" using 1:3 with line title "fold2" ls 2
```
```{.unwrap pipe="sh"}
./eps2png mkfib12 "Fibs generated (ignoring recursion in mkFib1)"
```
In this blog post I'll show how we can improve all these things, ending up with
a structured representation that, for any *unknown* N, can fold N elements in
O(1) memory, O(N) time and O(1) stack frames.
## Inductive Definitions
The problem with `mkFib2`{.php} is that the size of a PHP array must be
specified in advance, but we don't know how many elements we'll need. One simple
alternative to the array is a *list*. Rather than storing all elements in a
single place, a list stores them separately, then links them all together. There
are many different kinds of list, but the simplest is called *tail recursive*
(or "singly-linked") and can be implemented very easily in PHP by nesting
arrays:
```{.php pipe="./tag"}
// $x is our current element, $n is when to stop
defun('mkFibs3_', function($x, $n) {
return ($x < $n)? [mkFib1($x), mkFibs3_($x+1, $n)]
: [];
});
defun('mkFibs3', mkFibs3_(0)); // Always start at 0
```
```{pipe="./hide"}
deftest('mkFibs3', function() {
return eq($lhs = mkFibs3(7),
$rhs = [1, [1, [2, [3, [5, [8, [13, []]]]]]]])
? []
: get_defined_vars();
});
```
The results look like this:
```{pipe="./runphp"}
dump(mkFibs3(5));
```
The results of `mkFibs3`{.php} still have a finite size, but we're no longer
at the mercy of PHP's implementation details. Each array has a known size
(`0`{.php} or `2`{.php}), no matter how many elements we ask for. Like
`mkFib1`{.php}, `mkFibs3`{.php} isn't tail recursive, so it may overflow
the stack if we ask for too many elements. Folding lists is a little awkward in
PHP, since there's no built-in equivalent to `array_reduce`{.php}:
```{.php pipe="./tag"}
defun('fold3', function($f, $x) {
return trampoline(y(
function($g, $n, $fibs, $acc, $_) use ($f, $x) {
// If we've run out of $fibs, start again with more
if ($fibs === [])
return [false, $g($n+1, mkFibs3(pow(2, $n+1)), $x)];
// Apply $f to the next $fib
list($stop, $acc) = $f($acc, $fibs[0]);
return [$stop, $stop? $acc
: $g($n, $fibs[1], $acc)];
}, 0, [], null));
});
```
We can now do away with the exponentially-inefficient `mkFib1`{.php}. If we
log the arguments we're sending to `mkFib1`{.php}, we can see that
`mkFibs3`{.php} is asking for the same values over and over:
```{pipe="./hide"}
// Recurse like mkFib1 but just log our arguments
defun('mkFib1_log', function($n) {
return cons($n, ($n < 2)? []
: merge(mkFib1_log($n-1),
mkFib1_log($n-2)));
});
// Recurse like mkFibs3, but collects calls to mkFib1_log
defun('mkFibs3_log_', function($x, $n) {
return ($x < $n)? merge(mkFib1_log($x),
mkFibs3_log_($x+1, $n))
: [];
});
defun('mkFibs3_log', mkFibs3_log_(0)); // Always start at 0
```
Recursive calls in mkFibs3
```{.unwrap pipe="./runphp | pandoc -f markdown -t json"}
echo "mkFibs3(...) mkFib1(...)\n";
echo "------------ -----------\n";
foreach (upto(7) as $n) {
echo "$n ";
echo implode(", ", mkFibs3_log($n));
echo "\n";
}
echo "\n\n";
```
We can actually remove all of these calls, since `mkFibs3`{.php} has all of
the data it needs to construct each Fibonacci number itself. If we pass this
data along the recursive calls, our runtime becomes linear:
```{.php pipe="./tag"}
defun('mkFibs4_', function($fib_2, $fib_1, $x, $n) {
if ($x >= $n) return []; // Stopping condition
$fib = ($x < 2)? 1 : ($fib_2 + $fib_1);
return [$fib, mkFibs4_($fib_1, $fib, $x+1, $n)];
});
defun('mkFibs4', mkFibs4_(null, null, 0));
```
```{pipe="./runphp > mkfibs34.data"}
echo tabulate('N', 'mem3 mem4 time3 time4',
map(fanout([runmem('mkFibs3'),
runmem('mkFibs4'),
benchmark('mkFibs3'),
benchmark('mkFibs4')]),
upto(15)));
```
```{pipe="gnuplot 1>&2"}
reset
set terminal postscript color solid eps enhanced 20
set output "mkfibs34.eps"
set size 1.4,1
set title "mkFibs3(N) vs mkFibs4(N)"
unset logscale y;
unset logscale y2;
set key left bottom noautotitle
set ytics nomirror tc lt 3 textcolor rgb "blue"
set y2tics nomirror tc lt 1 textcolor rgb "red"
set xlabel "N"
set ylabel "Memory (kB)" textcolor rgb "blue"
set y2label "Time (seconds)" textcolor rgb "red"
set style line 1 linetype 3 dashtype 2 lc rgb "blue" lw 3
set style line 2 linetype 1 lc rgb "blue" lw 3
set style line 3 linetype 3 dashtype 2 lc rgb "red" lw 3
set style line 4 linetype 1 lc rgb "red" lw 3
set style line 5 linetype 3 dashtype 2 lc rgb "black" lw 3
set style line 6 linetype 1 lc rgb "black" lw 3
set termoption dash
plot "mkfibs34.data" using 1:2 with line notitle ls 1, \
"mkfibs34.data" using 1:3 with line notitle ls 2, \
"mkfibs34.data" using 1:4 with line notitle ls 3 axes x1y2, \
"mkfibs34.data" using 1:5 with line notitle ls 4 axes x1y2, \
0 with line title "mkFibs3" ls 5 axes x1y2, \
0 with line title "mkFibs4" ls 6 axes x1y2
```
```{.unwrap pipe="sh"}
./eps2png mkfibs34 "mkFibs3(N) vs mkFibs4(N)"
```
## Coinductive Definitions
Now we can deal with the finiteness problem. Every time PHP sees one of our
lists, it does the following:
- Construct the first element (the Fibonacci number, known as the *car* or
*head*)
- Construct the second element (the rest of the list, known as the *cdr* or
*tail*)
- Construct the array containing them
Our problem is that we're forced to construct the whole tail before we know how
long it needs to be. The solution is to *delay* the tail, which we can do using
a *thunk*: a function which returns a constant value. PHP will construct
functions without running them, which gives us time to figure out how many
elements we need.
```{.php pipe="./tag"}
defun('mkFibs5_', function($fib_2, $fib_1, $x, $n) {
if ($x >= $n) return []; // Stopping condition
$fib = ($x < 2)? 1 : ($fib_2 + $fib_1);
return [$fib, function($_) use ($fib_1, $fib, $x, $n) {
return mkFibs5_($fib_1, $fib, $x+1, $n);
}];
});
defun('mkFibs5', mkFibs5_(null, null, 0));
```
Delaying computation this way is known as *lazy evaluation*, and this method of
generating a bit of data and delaying the rest is called *co-induction*. Hence
this kind of structure is known as a *co-data structure*.
The nice thing about codata is that we can define never-ending chains of values,
wrapping each link in a thunk so that it only gets evaluated when needed (known
as *forcing* the value). This is exactly what we need for our Fibonacci
sequence, and all we need to do is throw away the stopping condition!
Notice that I'm giving these thunks a parameter `$_`{.php} which is ignored.
As far as PHP's concerned, I could have defined them as *nullary* functions, ie.
taking no arguments, but that makes them harder to reason about and prevents
some later simplifications:
```{.php pipe="./tag"}
defun('fibsFrom6', function($fib_2, $fib_1) {
$fib = $fib_2 + $fib_1;
return [$fib, function($_) use ($fib_1, $fib) {
return fibsFrom6($fib_1, $fib);
}];
});
defun('fibs6', function($_) {
return [1, function($_) {
return [1, function($_) {
return fibsFrom6(1, 1);
}];
}];
});
```
This is the first of our definitions that's both infinite, like a function, and
structured, like an array. This kind of codata structure is called a *stream*.
Here's how to fold a stream, using a *trampoline* to optimise tail-calls:
```{.php pipe="./tag"}
defun('fold6', function($f, $acc, $stream) {
return trampoline(y(function($y, $acc, $s, $_) use ($f) {
list($h, $t) = $s(null);
list($stop, $acc) = $f($acc, $h);
return [$stop, $stop? $acc
: $y($acc, $t)];
}, $acc, $stream));
});
```
```{pipe="./hide"}
deftest('fold6', function($n) {
$m = $n % 9;
$lhs = testFibs($m+1);
$rhs = fold6(function($acc, $fib) use ($m) {
return [count($acc) >= $m,
snoc($fib, $acc)];
}, [], 'fibs6');
return eq($lhs, $rhs)? [] : get_defined_vars();
});
```
### Refactoring
Now that we've created our infinite Fibonacci sequence, we can refactor the code
to be a little less naff. I debated whether to define the `fibsFrom`{.php}
function inline, but I think it's nice to keep two separate functions since they
correspond exactly to the two rules defining the Fibonacci sequence:
`fibsFrom`{.php} implements "sum the previous two", `fibs`{.php}
implements "start with `1`{.php}, `1`{.php}".
The first refactoring we can do is to notice that we have functions returning
functions, which is a manual form of currying. We can remove this separation,
since our functions are curried automatically by `defun`{.php} (we couldn't
do this if our thunks were nullary):
```{.php pipe="./tag"}
defun('fibsFrom7', function($l, $m, $_) {
$n = $l + $m;
return [$n, fibsFrom7($m, $n)];
});
defun('fibs7', function($_) {
return [1, function($_) {
return [1, fibsFrom7(1, 1)];
}];
});
```
Next we can remove the redundant `1`{.php}s in `fibs7`{.php}. This redundancy
is due to `fibsFrom`{.php} not including its arguments in the stream it returns,
but of course if we naïvely change `fibsFrom`{.php} to include its arguments,
we'd just be shifting around the redundancy, not eliminating it.
The solution is to extrapolate the sequence backwards a couple of steps. In
other words, we need to switch the initial `1, 1`{.php} to some other values
`$x`{.php} and `$y`{.php} such that we get a sequence
`$x, $y, 1, 1, 2, 3, 5, 8, ...`{.php}. We can derive these values straight
from the definition of the Fibonacci sequence:
```php
$y + 1 == 1 // Since $y, 1, 1 is in the sequence
$y == 1 - 1
$y == 0
$x + $y == 1 // Since $x, $y, 1 is in the sequence
$x + 0 == 1 // From the value of $y above
$x == 1
```
Now we can pass `$x`{.php} and `$y`{.php} as arguments to
`fibsFrom`{.php} and get back a stream of all fibs *after* `$x`{.php} and
`$y`{.php}, which is what we want. This simplifies our definition
considerably:
```{.php pipe="./tag"}
defun('fibs8', fibsFrom7(1, 0));
```
Finally, we can collapse `fibsFrom`{.php} into a one-liner, since PHP
evaluates array elements in-order:
```{.php pipe="./tag"}
defun('fibsFrom9', function($l, $m, $_) {
return [$n = $l + $m, fibsFrom9($m, $n)];
});
defun('fibs9', fibsFrom9(1, 0));
```
### Results
This is quite elegant, so let's leave it there and see how well our fold
performs. Note that we can reuse `fold6`{.php}, since our interface hasn't
changed:
```{pipe="./hide"}
$fibs6_9 = map(cat('fibs'), between(6, 9));
deftests(array_combine($fibs6_9,
map(curry(function($f, $n) {
$lhs = stream_take($n % 10, $f);
$rhs = testFibs($n);
return eq($lhs, $rhs)? []
: get_defined_vars();
}),
$fibs6_9)));
// Define "fold_fibsN" for N=6..9
defuns(array_combine(map(cat('fold_'), $fibs6_9),
map(curry(function($f, $n) {
// Pass nulls around $n times
fold6(function($a, $x) use (&$n) {
return [--$n <= 0, null];
}, null, $f);
}), $fibs6_9)));
defun('fibs_base', function($n) {
for ($fib_2 = 1, $fib_1 = 1;
$n--;
list($fib_2, $fib_1) = [$fib_1, $fib_2 + $fib_1]);
});
// Limit how many fibs we use
$fib_max = fold6(function($n, $fib) {
return [$fib > PHP_INT_MAX / 10, $n+1];
}, 0, 'fibs6');
// Take every Nth element
$take_nths = function($n, $input) {
return array_reduce($input,
function($arr, $elem) use ($n) {
return $arr[0]? [$n - 1, array_merge($arr[1], [$elem])]
: [$arr[0] - 1, $arr[1]];
},
[0, []])[1];
};
$fibs_range = $take_nths(2, upto($fib_max));
defun('fib_bench', function($n) use ($fibs_range) {
return tabulate('N', "fibs{$n}_time",
map(benchmark("fold_fibs{$n}"),
$fibs_range));
});
defun('fib_bench_base', function($_) use ($fibs_range) {
return tabulate('N', 'base_time',
map(benchmark('fibs_base'),
$fibs_range));
});
defun('fib_mem', function($n) use ($fibs_range) {
return tabulate('', "",
map(runmem("fold_fibs{$n}"),
$fibs_range));
});
defun('fib_mem_base', function($_) use ($fibs_range) {
return tabulate('', '',
map(runmem('fibs_base'),
$fibs_range));
});
```
```{pipe="sh > /dev/null"}
echo 'echo fib_bench("9");' | ./runphp > fib9time.data
echo 'echo fib_bench_base(null);' | ./runphp > basetime.data
echo 'echo fib_mem("9");' | ./runphp > fib9mem.data
echo 'echo fib_mem_base(null);' | ./runphp > basemem.data
```
```{pipe="gnuplot 1>&2"}
reset
set terminal postscript color solid eps enhanced 20
set output "fibs6_9.eps"
set size 1.4,1
unset logscale y
set logscale y2
set ytics nomirror tc ls 3
set y2tics nomirror tc ls 1
set xlabel "N"
set ylabel "Memory (kB)" textcolor rgb "blue"
set y2label "Time (seconds)" textcolor rgb "red"
set title "mkFibs9(N) vs for-loop"
set key right center noautotitle
set style line 1 lt 1 lc rgb "red" lw 3
set style line 2 lt 3 dashtype 2 lc rgb "red" lw 3
set style line 3 lt 1 lc rgb "blue" lw 3
set style line 4 lt 3 dashtype 2 lc rgb "blue" lw 3
set style line 5 lt 1 lc rgb "black" lw 3
set style line 6 lt 3 dashtype 2 lc rgb "black" lw 3
set termoption dash
plot "fib9time.data" using 1:2 with line notitle ls 1 axes x1y2, \
"basetime.data" using 1:2 with line notitle ls 2 axes x1y2, \
"fib9mem.data" using 1:2 with line notitle ls 3, \
"basemem.data" using 1:2 with line notitle ls 4, \
0 with line title "fibs9" ls 5, \
0 with line title "for-loop" ls 6
```
```{.unwrap pipe="sh"}
./eps2png fibs6_9 "mkFibs9(N) vs for-loop"
```
Note that the memory usage is constant, and it turns out we don't pay any memory
penalty for using streams compared to a hard-coded for-loop. We do pay a time
penalty, most likely from all of the function calls involved, but it's only a
constant factor so, as the log scale shows, the scaling behaviour isn't
affected.
So there we have it, a PHP implementation of the Fibonacci sequence which:
- Has a sequential structure, like the sequence itself
- Is never-ending, like the sequence itself (thanks to co-induction)
- Uses constant stack-space (thanks to tail-call optimisation, manually
implemented with trampolines)
- Uses constant memory (thanks to lexical closures)
- Uses linear time (again, thanks to lexical closures)
- Closely follows the two defining rules of the sequence
- Has a self-contained, abstract, composable, functional interface
- Only requires 4 lines to define, not counting the generic library functions
from `prelude.php`
```{.php}
defun('fibsFrom', function($l, $m, $_) {
return [$n = $l + $m, fibsFrom($m, $n)];
});
defun('fibs', fibsFrom(1, 0));
```
```{.unwrap pipe="./runphp | pandoc -f markdown -t json"}
exit(0);
if ($failures = runtests(null)) {
$stderr = fopen('php://stderr', 'w+');
fwrite($stderr, "Test Failures\n");
fwrite($stderr, tabulate('Test', 'Result', $failures));
fclose($stderr);
exit(1);
}
```
> "$1.html"
echo -n '" alt="' >> "$1.html"
echo -n "$2" >> "$1.html"
echo -n '" />' >> "$1.html"
pandoc -f html -t json "$1.html"
```
```{pipe="sh > /dev/null"}
chmod +x hide
chmod +x runphp
chmod +x tag
chmod +x eps2png
(source "$stdenv/setup" && patchShebangs .)
```
## Exponential Definitions ##
The Fibonacci sequence is a well-known series of numbers which follow a pattern:
it starts `1, 1`{.php} and each subsequent number is the sum of the two
preceding it. We can calculate the `$n`{.php}th element of the sequence like
this in PHP (using handy functions from [PHP Prelude](/git/php-prelude)):
```{.php pipe="./tag"}
defun('mkFib1', function($n) {
return ($n < 2)? 1 // Base case
: mkFib1($n - 1) + mkFib1($n - 2);
});
```
```{pipe="./hide"}
defun('testFibs', function($n) {
return take($n % 10, [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]);
});
deftest('mkFib1', function($n) {
return eq($lhs = map('mkFib1', upto($n % 10)),
$rhs = testFibs($n))? []
: get_defined_vars();
});
```
This is an incredibly naïve approach, since each call to `mkFib1`{.php} can
involve 2 more calls to `mkFib1`{.php}. This recursion is *well-founded*,
since it will always head towards the *base case* where `$n < 2`{.php}, but
there are two problems:
- It's not *tail-recursive*, so it requires a linear number of stack frames,
leading to *stack overflows*.
- It requires an exponential number of recursive calls to reach a base case,
which gives us an exponential running time:
```{pipe="./hide"}
// An instrumented version of mkFib1
$mkFib1_count_ = function($n) use (&$mkFib1_count_) {
if ($n < 2) return [1, 1]; // Base cases count as 1 call
list($c_1, $n_1) = $mkFib1_count_($n - 1);
list($c_2, $n_2) = $mkFib1_count_($n - 2);
return [$c_1 + $c_2 + 1, $n_1 + $n_2];
};
$mkFib1_count = compose('head', $mkFib1_count_);
deftest('mkFib1_count', function($n) use ($mkFib1_count_) {
return eq($lhs = $mkFib1_count_($n % 10)[1],
$rhs = mkFib1($n % 10))? []
: get_defined_vars();
});
```
```{pipe="./runphp > mkfib1.data"}
$data = array_map(function($n) use ($mkFib1_count) {
return [$mkFib1_count($n), benchmark("mkFib1", $n)];
},
upto(15));
echo tabulate("", [""], $data);
```
```{pipe="gnuplot 1>&2"}
reset
set terminal postscript color solid eps enhanced 20
set output "mkfib1.eps"
set size 1.4,1
unset x2tics
unset y2tics
unset key
set title "mkFib1(N)"
set border 11
set xlabel "N"
set ylabel "Recursive Calls" textcolor rgb "blue"
set y2label "Time (seconds)" textcolor rgb "red"
set tics nomirror
set logscale y
set ytics nomirror tc lt 3 textcolor rgb "blue"
set y2tics nomirror tc lt 1 textcolor rgb "red"
set logscale y2
plot "mkfib1.data" using 1:2 with line title "Recursive calls" linetype rgb "blue" lw 2, \
"mkfib1.data" using 1:3 with line title "Time" linetype rgb "red" lw 2 axes x1y2
```
```{.unwrap pipe="sh"}
set -e
./eps2png mkfib1 "mkFib1 is exponentially slow"
```
What's more, a function is a rather clumsy way of representing a sequence, since
the structure isn't immediately available and must be inferred by our users via
some sort of counter. This violates the *Once and Only Once* rule, and is liable
to cause off-by-one errors and such.
So what's the alternative? The trick is to realise that we don't need to provide
*every* element, since our users will only use a *finite* number. The difficulty
is that we don't know how many they'll need!
One simple approach that may spring to mind is asking the user up front how many
elements they need:
```{.php pipe="./tag"}
defun('mkFibs2', compose(map('mkFib1'), 'upto'));
```
```{pipe="./hide"}
deftest('mkFibs2', function($n) {
return eq($lhs = mkFibs2($n % 10),
$rhs = testFibs($n))? []
: get_defined_vars();
});
```
However, this doesn't do what we want. The requirement to know how many elements
are needed is *too strong*; many useful functions like
[filter](http://en.wikipedia.org/wiki/Filter_%28higher-order_function%29) and
[fold](http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29) (AKA
"reduce") require an unknown number of elements in general; for example, filters
don't know how many elements they'll need to discard before finding a match.
This forces us to generate longer and longer sequences, slowing us down by a
logarithmic factor compared to `mkFib1`{.php}:
```{.php pipe="./tag"}
// Note: Since there are infinitely many fibs, we can't fold all of them.
// Instead, $f returns a pair [$stop, $result], where $stop tells us
// when to cut-off the fold and $result is treated in the usual way.
// Fold a sequence generated by mkFib1
defun('fold1', function($f) {
// Fold over the Naturals $n = 0, 1, 2, ...
return loop(function($x, $n) use ($f) {
return $f($x, mkFib1($n));
});
});
// Prevents us applying $f to too many fibs
defun('shortcircuit', function($f, $x, $fib) {
return $x[0]? $x // If $x says stop, return it as-is
: $f($x[1], $fib); // Else call $f
});
// Fold a sequence generated by mkFib2
defun('fold2', function($f) {
// Fold over the Naturals $n = 0, 1, 2, ...
return loop(function($x, $n) use ($f) {
// Fold over 2^$n fibs
list($s, $y) = array_reduce(mkFibs2(pow(2, $n)),
shortcircuit($f),
[false, $x]);
return [$s, $s? $y // If $s(top), return $y
: $x]; // Else restart with $x
});
});
```
```{pipe="./hide"}
deftests(['fold1' => function($n) {
$m = $n % 10;
$rhs = fold1(function($a, $x) use ($m) {
return [count($a) >= $m, snoc($x, $a)];
}, []);
return eq($m + 1, count($rhs))? []
: get_defined_vars();
},
'fold2' => function($n) {
$m = $n % 10;
$rhs = fold2(function($a, $x) use ($m) {
return [count($a) >= $m, snoc($x, $a)];
}, []);
return eq($m + 1, count($rhs))? []
: get_defined_vars();
}]);
// Substitute fold2 which doesn't calculate fibs
defun('fold2_c', function($f, $_) {
return loop(function($_, $n) use ($f) {
return array_reduce(upto(pow(2, $n)),
$f,
null);
}, null);
});
// Simple fold examples
defun('fold_counter', function($fold, $n) {
$calls = 0;
$fold(function($_, $m) use ($n, &$calls) {
$calls++;
return [$m > $n, null];
}, null);
return $calls;
});
defun('fold1_example', fold_counter('loop'));
defun('fold2_example', fold_counter('fold2_c'));
defun('runmem', function($f, $x) { return mem(runphp($f, $x)); });
```
```{pipe="./runphp > mkfib12.data"}
$data = map(function($x) {
return [fold1_example($x), fold2_example($x)];
},
discard_keys(range(0, 150, 3)));
echo tabulate('', '', $data);
```
```{pipe="gnuplot 1>&2"}
reset
set terminal postscript color solid eps enhanced 20
set output "mkfib12.eps"
set size 1.4,1
unset x2tics
unset y2tics
set title "Folding N fibs"
set xlabel "N"
unset logscale y
set border 3
set key left noautotitle
set ytics nomirror
set xtics nomirror
set ylabel "Fibs generated (ignoring recursion in mkFib1)"
set xrange [0:150]
set style line 1 lc rgb "red" lw 3
set style line 2 lc rgb "blue" lw 3
plot "mkfib12.data" using 1:2 with line title "fold1" ls 1, \
"mkfib12.data" using 1:3 with line title "fold2" ls 2
```
```{.unwrap pipe="sh"}
./eps2png mkfib12 "Fibs generated (ignoring recursion in mkFib1)"
```
In this blog post I'll show how we can improve all these things, ending up with
a structured representation that, for any *unknown* N, can fold N elements in
O(1) memory, O(N) time and O(1) stack frames.
## Inductive Definitions
The problem with `mkFib2`{.php} is that the size of a PHP array must be
specified in advance, but we don't know how many elements we'll need. One simple
alternative to the array is a *list*. Rather than storing all elements in a
single place, a list stores them separately, then links them all together. There
are many different kinds of list, but the simplest is called *tail recursive*
(or "singly-linked") and can be implemented very easily in PHP by nesting
arrays:
```{.php pipe="./tag"}
// $x is our current element, $n is when to stop
defun('mkFibs3_', function($x, $n) {
return ($x < $n)? [mkFib1($x), mkFibs3_($x+1, $n)]
: [];
});
defun('mkFibs3', mkFibs3_(0)); // Always start at 0
```
```{pipe="./hide"}
deftest('mkFibs3', function() {
return eq($lhs = mkFibs3(7),
$rhs = [1, [1, [2, [3, [5, [8, [13, []]]]]]]])
? []
: get_defined_vars();
});
```
The results look like this:
```{pipe="./runphp"}
dump(mkFibs3(5));
```
The results of `mkFibs3`{.php} still have a finite size, but we're no longer
at the mercy of PHP's implementation details. Each array has a known size
(`0`{.php} or `2`{.php}), no matter how many elements we ask for. Like
`mkFib1`{.php}, `mkFibs3`{.php} isn't tail recursive, so it may overflow
the stack if we ask for too many elements. Folding lists is a little awkward in
PHP, since there's no built-in equivalent to `array_reduce`{.php}:
```{.php pipe="./tag"}
defun('fold3', function($f, $x) {
return trampoline(y(
function($g, $n, $fibs, $acc, $_) use ($f, $x) {
// If we've run out of $fibs, start again with more
if ($fibs === [])
return [false, $g($n+1, mkFibs3(pow(2, $n+1)), $x)];
// Apply $f to the next $fib
list($stop, $acc) = $f($acc, $fibs[0]);
return [$stop, $stop? $acc
: $g($n, $fibs[1], $acc)];
}, 0, [], null));
});
```
We can now do away with the exponentially-inefficient `mkFib1`{.php}. If we
log the arguments we're sending to `mkFib1`{.php}, we can see that
`mkFibs3`{.php} is asking for the same values over and over:
```{pipe="./hide"}
// Recurse like mkFib1 but just log our arguments
defun('mkFib1_log', function($n) {
return cons($n, ($n < 2)? []
: merge(mkFib1_log($n-1),
mkFib1_log($n-2)));
});
// Recurse like mkFibs3, but collects calls to mkFib1_log
defun('mkFibs3_log_', function($x, $n) {
return ($x < $n)? merge(mkFib1_log($x),
mkFibs3_log_($x+1, $n))
: [];
});
defun('mkFibs3_log', mkFibs3_log_(0)); // Always start at 0
```