Published on 24 November 2014 by @mathiasverraes
Let’s have some fun with higher order programming in PHP. I’ll start by showing how to program with Lambdalicious (or λlicious for friends) and introduce the real meat along the way. Don’t worry too much about the dark magic that may appear to power some of the features of Lambdalicious. It’s on GitHub if you’re curious. Just follow along and keep track of all the functions.
But first, something smaller:
@foobar is an atom. You can think of an atom as a constant that has itself as a value. So the value of
(Note that if you combine all the code in this post in a single file, it is executable and all assertions will pass.)
Unlike constants in PHP, atoms don’t need to be defined before you use them. They are global and immutable.
Atoms are very useful for many things. Later on, we’ll use them to refer to global functions, without needing to resort to quotes. In fact, the philosophy of λlicious is to remove syntactical noise, verbosity, and ceremony. To that effect, let’s get rid of the
@ prefix. We can do that by affixing an atom using the
Once an atom is affixed, you can use it everywhere without the prefix.
Let’s affix some atoms and make a list.
cons($head, $tail) constructs a list by adding
$head to the front of the list
$tail. In fact, the square brackets are nothing but a shortcut for a bunch of nested
We can deconstruct lists by taking the
head, which is the first element, or the
tail, which is all the elements without the head.
head always returns an element, and
tail returns a list.
Now let’s make a global function. Global means that we can reach it from anywhere.
If we affix the function’s name, we can refer to it by that atom.
We can also make locally scoped functions. We assign them to a variable that we can use to pass the function to another function.
We’ll need conditionals. In λlicious, they look like this:
In other words, conditions are tried one after another until one of them evaluates to true. The value of the complete expression is the result that follows the first true condition. If none of the conditions evaluate to true, the finalResult is returned.
Now we want to get the halves of a whole list of integers. Our test will look like this:
assert(isequal($halves([2, 4, 6]), [1, 2, 3]));
In λlicious, we only ever assign a value to a variable once. PHP does not constrain this: you can override the value of a variable as much as you like. Worry not: a λlicious-programmer is disciplined and strong-minded, and does not require any hand-holding from the compiler. This also means that we never use loops like foreach, while, …, as they mutate variables. The alternative way to loop, is by using recursion.
$halves takes a list as an argument. We’ll calculate the half of the head of that list, and then recurse to
$halves again with the tail of the list. We cons up the calculated half with the result of the recursive call to
$halves. Here’s our first attempt:
use(&$halves1) deserves some explanation. At this point in the code,
$halves1 is not yet defined. By closing it in our function by reference with
&, we can call it at the point in the code where we reach
$halves1(tail($list)). It’s a little trick in PHP to recurse on locally scoped functions. Don’t worry about it. When you get a
Notice: Undefined variable: foo, just remember to add
If we try to use
$halves1, we crash with a message saying
HeadIsDefinedOnlyForNonEmptyLists. The problem is that we are recursing, but we have not thought about how the loop stops. The λlicious-programmer accepts that mistakes happen, and draws lessons from it. From now on, whenever we recurse, we will think about the termination first.
As we are picking elements of our
$list, it will become empty at some point. We’ll need some place to store elements that we halved, so we add an accumulator called
$acc, which starts as an empty list. Whe
$list becomes empty, we return the accumulated values in
The assert still fails. Closer inspection learns that
$halves([2, 4, 6]) returns
[3, 2, 1]. That makes sense: we keep consing up the halved head of the original list, to the accumulated list, so our
$acc ends up backwards. That’s easy to fix. We simply call
$acc before returning it.
$halves3 passes our test. Recursion is great fun, and can be very rewarding. It’s especially useful for making obvious jokes. If you feel you don’t really get recursion, I advise you to read this wonderful blog post.
$halves3 works, but we’re not quite happy with it.
divide(head($list), 2) duplicates the logic of our
$half function. Let’s inject that function into our 4th version.
$halves4 is a higher order function: it takes another function as an argument. In our case, it applies this function to each element of
$list. This pattern is actually quite common. So common indeed, that it has a name: map. We can simply rename
$half to be more generic.
(Later on we’ll use the built-in global function
map instead of our own
$map, as it’s a little smarter.)
reduce are two other very commonly used higher order functions. They are globally defined in λlicious. The implementation is similar to that of
map, so I’ll leave them as an exercise to the λlicious student. We’ll use them later in this post. Here’s a skeleton to get you started:
Functions that take functions as arguments are just one type of higher order functions. We can also return functions. Let’s make a function that makes
This may seem a little pointless. But this is actually a pattern as well. We’ve hardcoded the division by 2, but what if we want to make that number dynamic? We rename
$divisionMaker and take a number as an argument:
We can make it even more generic. Right now,
division is hardcoded into
$divisionMaker. We can actually pass that function in as well. We rename
$partial takes two arguments: a function
$f and one argument
$y. It returns a new function, which takes another argument
$x, and return the result of
$f($x, $y). Partial function application is a nice example of higher order programming: you create new functions from existing functions.
Wouldn’t it be nice if we had an elegant syntax to partially call functions? In λlicious, many functions already feature partial function application by default:
The double underscores are placeholders: You can think of them as arguments that you don’t know yet, and that you’ll fill in later. Partial function application allows you to define behaviour in one place, and then process data using that behaviour, in another place. It’s great way of writing compact, highly reusable, highly readable code. It might take some getting used to, but once you get it, you don’t want to code without it anymore. Here’s an example with
At the point where we use
$halves5, we don’t need to know that internally, it’s actually a map of
Sometimes you need a function that is composed of other functions. If we want to half a value and then add one, we can make a function that does the work for us:
Once again, we’ll turn our
$halfAndIncrementMaker into a more generic function, called
compose. It’s another example of a higher order function: it takes functions as arguments and returns a new function.
$compose creates a function that calls
$x, and then calls
$g on the result of that. The built–in
compose is a little bit smarter and accepts more than two arguments.
pipe is the same as
compose, but it applies the functions in reverse. In my opinion, it is more natural to read. Think of pipes and filters in Linux. All together now:
If we call
$calculate with a list
[10, 20, 30], the first placeholder is replaced with that list. The outcome is
[5, 10, 15]. That result is fed into the
filter, which removes the
5 from that list. Finally,
reduce adds up
0, and than the adds up
15 to that
10, resulting in
25 which is the final outcome of
A great way to read that code, is to follow the pipe top the bottom. The first placeholder means “fill in a list that we don’t know about yet”. The second placeholder means: “pipe the result of the map to the filter”. The third placeholder means: “pipe the filtered list to reduce”. You can really follow the flow data through the placeholders, without being distracted by the actual data.
We can get rid of
$greaterThanTen, to make it even prettier.
We’ve now expressed a calculation as a composition of partially applied functions. It’s compact, elegant, and to the point. If you have trouble understanding what’s going on, you can inject some
dump functions along the way:
Imagine you had to write all that in traditional procedural PHP. The beauty is that we separates the definition of how data flows through the functions, from having to deal with the actual data. From a small set of primitive functions, we can build ever more complex abstractions. And that is the point of higher order programming.
Keep in mind that, at the time of writing, λlicious is not stable and might already have changed since you read this. Lambdalicious is not fit for any purpose. If you use it in production and everything breaks, your friends will laugh at you behind your back. I will provide a shoulder to cry on at twice my normal consultancy rates, while saying “I told you so.”
The reason it can not work is that PHP is not suitable for recursion. Some languages have something called tail call optimization, which means that if the last expression is recursive, the compiler will make a jump. The call stack does not increase, and all is well.
PHP will either run out of memory (Fatal error: Allowed memory size of X bytes exhausted) or, if you have XDebug installed, it will stop at a 100 calls by default. (PHP Fatal error: Maximum function nesting level of ‘100’ reached, aborting). You can increase
xdebug.max_nesting_level in php.ini. HHVM overflows (Fatal error: Stack overflow). I promise to send some fine Belgian beer or chocolates to whoever fixes this in PHP or HHVM.
Follow @mathiasverraes on Twitter.
This work by Mathias Verraes is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 License.