Functional Programming in PHP

The new hype in programming is all about functional programming paradigms. Functional languages are used more and more in greater and better applications. Scala, Haskel, etc. are thriving and other, more conservative languages like Java started to adopt some of the functional programming paradigms (see closures in Java7 and lazy eval for lists in Java8). However, what only few people know is that PHP is quite versatile when it comes to functional programming. All the main functional programming concepts can be expressed in PHP. So, if you are new to functional programming, be prepared to have your mind blown, and if you are already familiar with functional programming, be prepared to have great fun with this tutorial.

Programming Paradigms

Without any programming paradigms we could do whatever we want in whatever way we want. While this would lead to extreme flexibility, it would also lead to impossible architectures and very bloated code. Thus, programming paradigms were invented to help us, programmers, to think in a specific way about a specific program and in this way, limit our ability to express our solution.

Each programming paradigm takes away a freedom from us:

Modular Programming takes away unlimited program size.
Structured and Procedural Programming are taking away the "go-to" and limits the programmer to sequence, selection and iteration.
Object Oriented Programming takes away pointers to functions.
Functional Programming takes away assignment and mutable state.

Functional Programming Principles

In functional programming, you have no data represented by variables.

In functional programming everything is a function. And I mean everything. For example a set, as in mathematics, can be represented as several functions. An array or list is also a function or a group of functions.

In object oriented programming everything is an object. And an object is a collection of data and methods that do actions on those data. Objects have a state, a volatile, mutable state.

In functional programming, you have no data represented by variables. There are no data containers. Data is not assigned to a variable. Some values may be defined and assigned. However, in most cases they are functions assigned to "variables". I've put "variables" between quotes because in functional programming they are immutable. Even though most functional programming languages do not enforce immutability, in the same way most object oriented languages do not enforce objects, if you change the value after an assignment you are not doing pure functional programming any more.

Because you don't have values assigned to variables, in functional programming you have no state.

Because of no state and no assignments, in functional programming functions have no side effect. And because of the three previous reasons, functions are always predictable. This basically means that if you call a function with the same parameters again and again and again... you will always have the same result. This is a huge advantage over object oriented programming and greatly reduces the complexity of multi-threaded and massively multi-threaded applications.

But, if we want to express everything in functions, we need to be able to assign them to parameters or return them from other functions. Thus functional programming requires the support for higher-order functions. This basically means that a function can be assigned to a "variable", sent in as a parameter to another function, and returned as a result of a function.

Finally, because we have no values in variables, while and for loops are unusual to functional programming and are replaced with recursion.

Show Me the Code!

Enough talking and philosophy for one lesson. Let's code!

Set up a PHP project in your favorite IDE or code editor. Create in it a "Tests" folder. Create two files: FunSets.php in the project's folder, and FunSetsTest.php in the Tests folder. We will create an application, with tests, that will represent the concept of sets.

In mathematics, a set is a collection of distinct objects, considered as an object in its own right. (wikipedia)

That basically means that sets are a bunch of things in a single place. These sets can be and are characterized by mathematical operations: unions, intersections, differences, etc. And by actionable properties like: contains.

Our Programming Limitations

So let's code! But wait. How? Well, to respect the concepts of functional programming we will have to apply the following restrictions to our code:

No assignments. - We are not allowed to assign values to variables. We are however allowed to assign functions to variables.
No mutable state. - We are not allowed, in case of an assignment, to change the value of that assignment. We are also not allowed to change the value of any variable that had its value set as the parameter for the current function. So, no changing of parameters.
No while and for loops. - We are not allowed to used PHP's "while" and "for" commands. We, however, may define our own method to cycle through the elements of a set and call it foreach/for/while.

No limitations apply to tests. Because of the nature of PHPUnit, we will use classic object oriented PHP code there. Also, to better accommodate our tests, we will wrap all our production code into a single class.

The Set's Defining Function

If you are a seasoned programmer, but unfamiliar with functional programming, now is the time to stop thinking as you do usually and be ready to leave your comfort zone. Forget all your previous ways of reasoning about a problem and imagine all in functions.

The defining function of a set is its "contains" method.

function contains($set, $elem) {
	return $set($elem);
}

OK... This is not that obvious, so let's see how would we use it.

$set = function ($element) {return true;};
contains($set, 100);

Well, this explains it a little bit better. The function "contains" has two parameters:

$set - represents a set defined as a function.
$elem - represents an element defined as a value.

In this context, all that "contains" has to do is to apply the function in $set with the parameter $elem. Let's wrap all in a test.

class FunSetsTest extends PHPUnit_Framework_TestCase {

	private $funSets;

	protected function setUp() {
		$this->funSets = new FunSets();
	}

	function testContainsIsImplemented() {
		// We caracterize a set by its contains function. It is the basic function of a set.

		$set = function ($element) {return true;};
		$this->assertTrue($this->funSets->contains($set, 100));
	}
}

And wrap our production code inside FunSets.php into a class:

class FunSets {

	public function contains($set, $elem) {
		return $set($elem);
	}
}

You can actually run this test and it will pass. The set we defined for this test is just a function that always returns true. It is a "true set".

The Singleton Set

If the previous chapter was a little bit confusing or looked useless in logic, this one will clarify it a little bit. We want to define a set with a single element, a singleton set. Remember, this has to be a function, and we will want to use it like in the test below.

function testSingletonSetContainsSingleElement() {
	// A singleton set is characterize by a function which passed to contains will return true for the single element
	// passed as its parameter. In other words, a singleton is a set with a single element.

	$singleton = $this->funSets->singletonSet(1);
	$this->assertTrue($this->funSets->contains($singleton, 1));
}

We need to define a function called "singeltonSet" with a parameter representing an element of the set. In the test, that is the number one (1). Then, we expect our contains method, when called with a singleton function, to return true if the sent in parameter equals one. The code that makes the test pass is as follows:

public function singletonSet($elem) {
	return function ($otherElem) use ($elem) {
				return $elem == $otherElem;
			};
}

Wow! That's crazy. So, the function "singletonSet" gets as a parameter an element as $elem. Then it returns another function which has a parameter $otherElem and this second function will compare $elem to $otherElem.

So, how does this work? First, this line:

$singleton = $this->funSets->singletonSet(1);

is transformed into what "singletonSet(1)" returns:

$singleton = function ($otherElem) {
		return 1 == $otherElem;
	};

Then "contains($singleton, 1)" is called. Which, in turn calls whatever is in $singleton. So the code becomes:

$singleton(1)

Which actually executes the code in it with $otherElem having the value one.

return 1 == 1

Which is of course true and our test passes.

Are you already smiling? Do you feel your brain starting to boil? I certainly did when I first wrote this example in Scala and I did again when I first wrote this example in PHP. I think this is extraordinary. We managed to define a set, with one element, with the ability to check that it contains the value we passed in to it. We did all these without a single assignment of value. We have no variable containing the value one or having a state of one. No state, no assignment, no mutability, no loops. We are on the right track here.

Union of Sets

Now that we can create a set with a single value, we need to be able to create a set with several values. The obvious way to do it is to define the union operation on our sets. The union of two singleton sets will represent another union with both values. I want you to take a minute and think about the solution before scrolling to the code, maybe take a peak on the tests below.

function testUnionContainsAllElements() {
	// A union is characterized by a function which gets 2 sets as parameters and contains all the provided sets

	// We can only create singletons at this point, so we create 2 singletons and unite them
	$s1 = $this->funSets->singletonSet(1);
	$s2 = $this->funSets->singletonSet(2);
	$union = $this->funSets->union($s1, $s2);

	// Now, check that both 1 and 2 are part of the union
	$this->assertTrue($this->funSets->contains($union, 1));
	$this->assertTrue($this->funSets->contains($union, 2));
	// ... and that it does not contain 3
	$this->assertFalse($this->funSets->contains($union, 3));
}

We want a function called "union" that gets two parameters, both sets. Remember, sets are just functions for us, so our "union" function will get two functions as parameters. Then, we want to be able to check with "contains" if the union contains an element or not. So, our "union" function must return another function that "contains" can use.

public function union($s1, $s2) {
	return function ($otherElem) use ($s1, $s2) {
				return $this->contains($s1, $otherElem) || $this->contains($s2, $otherElem);
			};
}

This is actually working quite well. And it is perfectly valid even when your union is called with another union plus a singleton. It calls contains inside itself for each parameter. If it's a union, it will recurse. It's that simple.

Intersect and Difference

We can apply the same one liner logic with minor changes to obtain the next two most important functions that characterize a set: intersection - contains only the common elements between two sets - and difference - contains only those elements from the first set that are not part of the second set.

public function intersect($s1, $s2) {
	return function ($otherElem) use ($s1, $s2) {
				return $this->contains($s1, $otherElem) && $this->contains($s2, $otherElem);
			};
}

public function diff($s1, $s2) {
	return function ($otherElem) use ($s1, $s2) {
				return $this->contains($s1, $otherElem) && !$this->contains($s2, $otherElem);
			};
}

I won't flood you with the test code for these two methods. The tests are written and you can check them if you look in the attached code.

Filter Set

Well, this is a bit more complicated, we won't be able to solve this with a single line of code. A filter is a function that uses two parameters: a set and a filtering function. It applies the filtering function to a set and returns another set that contains only the elements that satisfy the filtering function. To better understand it, here is the test for it.

function testFilterContainsOnlyElementsThatMatchConditionFunction() {
	$u12 = $this->createUnionWithElements(1, 2);
	$u123 = $this->funSets->union($u12, $this->funSets->singletonSet(3));

	// Filtering rule, find elements greater than 1 (meaning 2 and 3)
	$condition = function($elem) {return $elem > 1;};

	// Filtered set
	$filteredSet = $this->funSets->filter($u123, $condition);

	// Verify filtered set does not contain 1
	$this->assertFalse($this->funSets->contains($filteredSet, 1), "Should not contain 1");
	// Check it contains 2 and 3
	$this->assertTrue($this->funSets->contains($filteredSet, 2), "Should contain 2");
	$this->assertTrue($this->funSets->contains($filteredSet, 3), "Should contain 3");
}

private function createUnionWithElements($elem1, $elem2) {
	$s1 = $this->funSets->singletonSet($elem1);
	$s2 = $this->funSets->singletonSet($elem2);
	return $this->funSets->union($s1, $s2);
}

We create a set with three elements: 1, 2, 3. And we place it into the variable $u123 so it is easily identifiable in our tests. Then we define a function we want to apply to the test and place it into $condition. Finally, we call filter on our $u123 set with $condition and place the resulting set into $filteredSet. Then we run assertions with "contains" to determine if the set looks how we want. Our condition function is simple, it will return true if the element is greater than one. So our final set should contain only the values two and three, and this is what we check in our assertions.

public function filter($set, $condition) {
	return function ($otherElem) use ($set, $condition) {
				if ($condition($otherElem))
					return $this->contains($set, $otherElem);
				return false;
			};
}

And here you go. We implemented filtering with just three lines of code. More precisely, if the condition applies to the provided element, we run a contains on the set for that element. If not, we just return false. That's it.

Looping Over Elements

The next step is to create various looping functions. The first one, "forall()", will take a $set and a $condition and return true if $condition applies to all the elements of the $set. This leads to the following test:

function testForAllCorrectlyTellsIfAllElementsSatisfyCondition() {
	$u123 = $this->createUnionWith123();

	$higherThanZero = function($elem) { return $elem > 0; };
	$higherThanOne = function($elem) { return $elem > 1; };
	$higherThanTwo = function($elem) { return $elem > 2; };

	$this->assertTrue($this->funSets->forall($u123, $higherThanZero));
	$this->assertFalse($this->funSets->forall($u123, $higherThanOne));
	$this->assertFalse($this->funSets->forall($u123, $higherThanTwo));
}

We extracted the $u123 creation from the previous test into a private method. Then we define three different conditions: higher than zero, higher than one, and higher than two. As our set contains the numbers one, two, and three, only the higher than zero condition should return true, the rest should be false. Indeed, we can make the test pass with the help of another recursive method use to iterate over all the elements.

private $bound = 1000;

private function forallIterator($currentValue, $set, $condition) {
	if ($currentValue > $this->bound)
		return true;
	elseif ($this->contains($set, $currentValue))
		return $condition($currentValue) && $this->forallIterator($currentValue + 1, $set, $condition);
	else
		return $this->forallIterator($currentValue + 1, $set, $condition);
}

public function forall($set, $condition) {
	return $this->forallIterator(-$this->bound, $set, $condition);
}

We start by defining some limits for our set. The values must be between -1000 and +1000. This is a reasonable limitation we impose in order to keep this example simple enough. The function "forall" will call the private method "forallIterator" with the necessary parameters to recursively decide if all elements respect the condition. In this function, we first test if we are out of bounds. If yes, return true. Then check if our set contains the current value and return the current value applied to the condition together with a logical "AND" with a recursive call to ourselves with the next value. Otherwise, just call ourselves with the next value and return the result.

This works just fine, we can implement it in the same manner as "exists()". This returns true if any of the elements satisfies the condition.

private function existsIterator($currentValue, $set, $condition) {
	if ($currentValue > $this->bound)
		return false;
	elseif ($this->contains($set, $currentValue))
		return $condition($currentValue) || $this->existsIterator($currentValue + 1, $set, $condition);
	else
		return $this->existsIterator($currentValue + 1, $set, $condition);
}

public function exists($set, $condition) {
	return $this->existsIterator(-$this->bound, $set, $condition);
}

The only difference is that we return false when out of bounds and we use "OR" instead of "AND" in the second if.

Now, "map()" will be different, simpler and shorter.

public function map($set, $action) {
	return function ($currentElem) use ($set, $action) {
		return $this->exists($set, function($elem) use ($currentElem, $action) {
			return $currentElem == $action($elem);
		});
	};
}

Mapping means we apply an action to all the elements of a set. For map, we need no helper iterator, we can reuse "exists()" and return those elements of "exists" that satisfy the result of $action applied to $element. This may not be obvious at first site, so let's see what is happening.

We send the set { 1, 2 } and the action $element * 2 (double) to map.
It will return a function, obviously, which has a parameter as an element and uses the set and action from one level higher.
This function will call exists with the set { 1, 2 } and the condition function $currentElement equals $elem * 2.
exists() will iterate over all the elements between -1000 and +1000, our bounds. When it finds an element, double of what comes from "contains" (the value of $currentElement) it will return true.
In other words, the last comparison will return true for the call to contains with value two, when the value of the current multiplied by two, results in two. So for the first element of the set, one, it will return true on two. For the second element, two, on value four.

A Practical Example

Well, functional programming is fun but it is far from ideal in PHP. So, I do not recommend you to write whole applications this way. However, now that you've learned what PHP can do functionally, you can apply parts of this knowledge in your everyday projects. Here is an example authentication module. The AuthPlugin class provides a method that receives a user and password and does its magic to authenticate the user and set its permissions.

class AuthPlugin {

	private $permissions = array();

	function authenticate($username, $password) {
		$this->verifyUser($username, $password);

		$adminModules = new AdminModules();
		$this->permissions[] = $adminModules->allowRead($username);
		$this->permissions[] = $adminModules->allowWrite($username);
		$this->permissions[] = $adminModules->allowExecute($username);
	}

	private function verifyUser($username, $password) {
		// ... DO USER / PASS CHECKING
		// ... LOAD USER DETAILS, ETC.
	}

}

Now, this may sound OK, but it has a huge problem. 80% of the "authenticate()" method uses information from the "AdminModules". This creates a very strong dependency.

It would be much more reasonable to take the three calls and create a single method on AdminModules.

So, by moving the generation into AdminModules we managed to reduce three dependencies to just one. The public interface of AdminModules was also reduced from three to only a single method. However, we are not yet there. AuthPlugin still directly depends on AdminModules.

An Object Oriented Approach

If want our authentication plugin to be usable by any module, we need to define a common interface for these modules. Let's inject the dependency and introduce an interface.

class AuthPlugin {

	private $permissions = array();
	private $appModule;

	function __construct(ApplicationModule $appModule) {
		$this->appModule = $appModule;
	}

	function authenticate($username, $password) {
		$this->verifyUser($username, $password);

		$this->permissions = array_merge(
				$this->permissions,
				$this->appModule->getPermissions($username)
		);
	}

	private function verifyUser($username, $password) {
		// ... DO USER / PASS CHECKING
		// ... LOAD USER DETAILS, ETC.
	}

}

AuthPlugin got a constructor. It gets a parameter of type ApplicationModule, an interface, and calls "getPermissions()" on this injected object.

interface ApplicationModule {

	public function getPermissions($username);

}

ApplicationModule defines a single public method, "getPermissions()", with a username as a parameter.

class AdminModules implements ApplicationModule {
	// [ ... ]
}

Finally, AdminModules needs to implement the ApplicationModule interface.

Now, this is much better. Our AuthPlugin depends only on an interface. AdminModules depends on the same interface, so the AuthPlugin became module agnostic. We can create any number of modules, all implementing ApplicationModule, and AuthPlugin will be able to work with all of them.

A Functional Approach

Another way to reverse the dependency, and make AdminModule, or any other module, to use the AuthPlugin is to inject into these modules a dependency to AuthPlugin. AuthPlugin will provide a way to set the authentication function and each application will send in its own "getPermission()" function.

class AdminModules {

	private $authPlugin;

	function __construct(Authentitcation $authPlugin) {
		$this->authPlugin = $authPlugin;
	}

	private function allowRead($username) {
		return "yes";
	}

	private function allowWrite($username) {
		return "no";
	}

	private function allowExecute($username) {
		return $username == "joe" ? "yes" : "no";
	}

	private function authenticate() {

		$this->authPlugin->setPermissions(
				function($username) {
					$permissions = array();
					$permissions[] = $this->allowRead($username);
					$permissions[] = $this->allowWrite($username);
					$permissions[] = $this->allowExecute($username);
					return $permissions;
				}
		);
		$this->authPlugin->authenticate();
	}

}

We start with AdminModule. It does not implement anything anymore. However, it uses an injected object that has to implement Authentication. In AdminModule there will be an "authenticate()" method that will call "setPermissions()" on AuthPlugin and pass in the function that needs to be used.

interface Authentication {

	function setPermissions($permissionGrantingFunction);

	function authenticate();

}

The Authentication interface simply defines the two methods.

class AuthPlugin implements Authentication {

	private $permissions = array();
	private $appModule;
	private $permissionsFunction;

	function __construct(ApplicationModule $appModule) {
		$this->appModule = $appModule;
	}

	function authenticate($username, $password) {
		$this->verifyUser($username, $password);
		$this->permissions = $this->permissionsFunction($username);
	}

	private function verifyUser($username, $password) {
		// ... DO USER / PASS CHECKING
		// ... LOAD USER DETAILS, ETC.
	}

	public function setPermissions($permissionGrantingFunction) {
		$this->permissionsFunction = $permissionGrantingFunction;
	}

}

Finally, AuthPlugin implements Authentication and sets the incoming function in a private class attribute. Then, "authentication()" becomes a dumb method. It just calls the function and then sets the return value. It is completely decoupled of whatever comes in.

If we look at the schema, there are two important changes:

Instead of AdminModule, AuthPlugin is the one implementing the interface.
AuthPlugin will "Call Back" AdminModule, or whatever other module sent in the permissions function.

Which One to Use?

There is no correct answer to this question. I would argue that if the process of determining the permissions is quite dependent on the application module, then the object oriented approach is more appropriate. However, if you think that each application module should be able to provide an authentication function, and your AuthPlugin is just a skeleton providing the authentication functionality but without knowing anything about users and procedures, then you can go with the functional approach.

The functional approach makes your AuthPlugin very abstract and you can depend on it. However, if you plan to allow your AuthPlugin to do more and know more about users and your system, then it will became too concrete, and you don't want to depend on it. In that case choose the object oriented way and let the concrete AuthPlugin depend on the more abstract application modules.

HIGHLIGHTS OF THE DAY