:julianbrowne

Menu

Make room for Functional Programming (1)

FP for real people

By on August 25, 2008. Filed Under: development

I’ve spilt this post into two so I can cover one concept from a couple of different angles. What I want to do first is explain the major elements of Functional Programming (FP) to those who, like me, might struggle with a lot of mathematical hoopla, Haskell and Lisp code, and second show by simple example where all this stuff is useful in the real world.

Meaning I have struggled through the hoopla to write this so you don’t have to - you’re welcome.

Why Functional Programming?

Why should you be interested? Well FP is both an idea and an implementation. Understanding the idea promises to help you write better code, whatever language you use for your day job, and if you’re keen to get into an FP-friendly language (F#, Haskell, Lisp, ML, Erlang, Ruby) the ideas represent the standard idioms found in these languages. The examples here happen to be in JavaScript, primarily because it’s easy to read even if you are not familiar with the syntax, but it also makes it easy for me to test that they work.

And why would you want to get into an FP-friendly language? Well, because functional programming promises a revolution in the way we manage complexity in programming. You can’t help but notice that things can be complex in software development. You write some code that seems pretty straightforward and it grows and grows and before you know it there’s a support nightmare on the loose, the bigger the support overhead for any piece of code the less time there is to make it do more useful stuff.

Structure

Part one covers the concepts, with as little of the associated jargon as possible, and the second works through a toy coding example to show the techniques in action. I recognise that simplifying FP to this level will annoy proponents and purists, so I’ve added a further reading section at the end to cover my shortcomings.

Enough chatter. Let’s start.

Global Variables (again)

Hopefully we all understand why global variables can be risky in development, but in case in not let’s quickly recap:

If you have a variable called my_greeting defined as a string, and that string is accessible (as in, changeable) from anywhere in your code, it’s called a global variable. Having access to my_greeting from anywhere is enormously convenient. To set it to “Hello, World!” you just write:

my_greeting = "Hello, World!";

and you can do that from anywhere you like. You can reset it (””), extend it (“Hello, World! Good Morning!”), or modify it (“Hello, cruel World!”) at any point in your code. And here’s where the risks come in.

If the code is thousands of lines long then my_greeting starts to lose its context. Someone needing to bug-fix the code won’t easily know what my_greeting actually contains at any one point, they might not even know what type of variable it is. Someone might, accidentally, set it to an integer (and languages like Ruby or JavaScript won’t complain) within an if-statement that rarely fires, introducing a bug that escapes testing. You can’t change its name as part of a later refactoring exercise easily, because it could be used anywhere, so over time my_greeting may start to represent something at odds with what’s it’s called. You also can’t reuse the name, raising the risk that someone new to the code might create another my_greeting, which also won’t necessarily get picked up in compilation or test. And finally, when your code runs there is a risk that multiple threads access my_greeting at the same time with unpredictable results (making global variables not thread safe).

A simpler way to put this is that there are outright errors, which will either fail compilation or cause the program to crash at runtime, and there are risks which allow the program to run, but with “side effects” such as producing a report that tells the CEO the company has made a big profit when in fact there’s been a screw-up in the code that didn’t result in a compilation error, crash or exception.

Encapsulation (again)

Rather than allow anything to be anywhere, encapsulation) says that it’s better to keep like things together, and control access to them via an interface. This has two benefits: it’s good logically because it makes support easier and it’s good technically because it addresses those issues we get with global variables. Java, for example, encapsulates everything in classes. There are no global variables in the sense that you can’t just type mygreeting = “Hello, World!”_ outside of a class in Java.

But most languages, like Java, are not intrinsically thread safe. There are plenty of techniques to make it so, but it doesn’t come for free. And, just as with global variables, where there’s no thread safety there’s the risk of unpredictable results.

So, what does thread safety look like? Wikipedia has a nice definition:

A subroutine is re-entrant, and thus thread-safe, if it only uses variables from the stack, depends only on the arguments passed in, and only calls other subroutines with similar properties.

This is sometimes called a “pure function”, and is much like a mathematical function.

Let’s break that up a little. Thread safety means only using variables from something called the stack, and if we do this we have something called a pure function. There’s no need to get into a protracted look at memory management here (much of it is implementation dependent, so see further reading for that) but it is worth talking about stacks and heaps quickly. Every thread (i.e. a task or a function) that runs in a computer has some local RAM assigned to it called the stack. For all the other stuff that isn’t associated with one thread, or might be passed between threads, there’s the heap. For the purposes of this intro, think of the stack as extending the concept of encapsulation, that we would apply to how we use my_greeting in the source code, to where it’s actually stored in memory.

Pure Functions

A simple pure function, that’s both encapsulated and thread-safe, is this:

function add_two_numbers(a,b) { 
	return (a + b);
}

add_two_numbers(7,35); // returns 42

Nice, but not terribly useful. Its power is limited because its interface contract is fixed - I can only ever add two numbers. However I can add three numbers if I wanted to by embedding a call to the function within a call to the function, like this:

add_two_numbers(10,add_two_numbers(20,30)); // returns 60

More useful, but not very readable. And if I want to do other things (like find the average of ten numbers) I have to write more functions and very quickly my function list will get long and unwieldy and some of those support issues we saw with global variables will creep back in.

Good design tells us that, if we’re in the business of performing lots of simple calculations with numbers, then a level of abstraction in our interface design will improve things. For example:

function add_numbers(number_array) { 

	if(number_array.length == 0) return 0;
	var sum = 0;
	var i;

	for(i in number_array) {
		sum = sum + number_array[i];
	}

	return sum;
}

As a side note here - FP purists are generally in favour of recursion over iteration in cases like this. You could write the code above like this:

function add_numbers(number_array) { 
	if(number_array.length == 0) return 0;
	return number_array.shift() + add_numbers(number_array);
}

Same result, fewer lines and many would say more elegant. I’m going to sidestep the loop-or-recurse argument for this intro, except to say recursion is usually more intensive from a compute point of view but easier to debug, whereas the iterative approach can sometimes be easier to read at the expense of mathematical precision.

What we did, when we abstracted from a function contract that enforced two parameters (a,b) to one that allowed one (number_array) is allowed more information to be passed in, giving the caller more control. The more control the caller has, the more useful the function is in a variety of circumstances. The ultimate level of control for the caller would be to pass in not just variables but calculation logic.

Lambda Functions

A Lambda Function is one which is pure, encapsulated and thread-safe and which can be created, managed, and passed around just as a variable would. There are variations on the theme, but Lambda Functions are the basis of Functional Programming.

To pass calculation logic (i.e. other functions) between functions requires them to be treated like variables, that is to say first-class objects that can be created, stored and accessed at run time. These are called Lambda Functions and there are a few ways to use them.

Functions as Variables

The simplest way to create and pass a lambda function is to assign it to a variable and use it to call another function.

// function that adds numbers

function add_numbers(number_array) {				
	if(number_array.length == 0) return 0;
	return number_array.shift() + add_numbers(number_array);
}

// function that multiplies numbers

function multiply_numbers(number_array)	{			
	if(number_array.length == 0) return 1;
	return number_array.shift() * multiply_numbers(number_array);
}

// function that takes an array and a function

function calculator(input_number_array,operation) {	
	return operation(input_number_array);
}

var my_numbers = [ 1, 2, 3, 4, 5 ];		// an array of numbers

var my_calculation = add_numbers;		// assign addition function to variable

calculator(my_numbers,my_calculation);		// returns 15

var my_numbers = [ 1, 2, 3, 4, 5 ];		// an array of numbers

var my_calculation = multiply_numbers;		// assign multiply function to variable

calculator(my_numbers,my_calculation);		// returns 120

Although we’ve barely scratched the surface, hopefully that starts to show the power of lambda functions. We’ve created an extensible and reusable calculator function that operates on any array of numbers as long as it’s passed an appropriate function to perform on them.

Incidentally, the calculator example is using what in FP is known as a fold technique - that is it’s taking a list, applying a calculation to each item and folding up (summing) the result as it goes. Alternatives are find (return a list of items that match certain conditions) and map (return a list of items, each one having had an operation performed on it).

Anonymous Functions

Although you can assign existing functions to variables it’s more common to assign the function logic directly to a variable without naming it, using a so-called anonymous function. In the example above calling the function add_numbers is largely redundant, so I could just write:

my_calculation = function(number_array) {
	if(number_array.length == 0) return 0;
	return number_array.shift() + add_numbers(number_array);
}

it’s even possible to skip the variable altogether and insert the logic directly into the call to the calculator function:

calculator(my_numbers,
	function(number_array) { 
		if(number_array.length == 0) return 0;					
		return number_array.shift() + add_numbers(number_array);
	}
);

which is right depends on the circumstances in which it’s used. Personally I find the latter option hard to read for all but the simplest lambda functions. Anonymous functions are good for defining a function that only has short life span, or to make code more readable, or to support other FP techniques as we’ll see in a minute.

Functions that write functions

As well as passing functions into functions it’s possible to return them too (if it works for variables, then in FP it works for functions). A simple example might be:

// a function that returns a function

function function_maker() {

	// a function that adds two numbers

	var myfunc = function(a,b) { 
		return (a + b);
	}
	
	return myfunc;
}

var my_add_func = function_maker();	// assign returned function to variable

var my_numbers = [ 5, 5 ];		// an array of numbers

calculator(my_numbers, my_add_func);	// returns 10

Returning functions from functions might initially seem like a good way to add unnecessary indirection. In the example above there’s no value in having a function_maker() function - it would be simpler just to assign that internal function to a variable and do away with function_maker() altogether.

But what if there were other things going on within function_maker() that could be used to modify how that returned function (myfunc), operates when it’s finally used by that calculator() function. We already saw that a calculator function becomes more useful if we can dynamically pass into it instructions on what we need it to do. If we can also modify the context in which those instructions are used we can exert an even finer degree of control. And for that we need a closure.

By the way, if you’re starting to sense that there’s a kind of Russian doll being created here, of functions taking in functions that come from other functions, all stacked up on the .. er.. stack, then you already get functional programming.

Closures

A closure is a function, defined inside another function, that brings with it the local environment from its parent function. It allows local variables that existed when the function was created to remain accessible, and changeable, even though the parent function has completed.

Here’s an example:

function closure_maker() { 

	var fred="fred";	// fred is "local" to closure_maker()

	function are_you_local() { 
		alert(fred);
	}

	are_you_local();	// displays "fred" because we're still local								

	return are_you_local;	// returns the function
}

var closure=closure_maker();

closure();	// displays "fred" even though we're not local

The variable fred is local to the closure_maker() function. When closure_maker() is called it defines a function called are_you_local() and runs it. The screen displays the word “fred”, as you would expect because are_you_local() is accessing the local variable called fred. Then closure_maker() completes, returning a reference to the the are_you_local() function, which we assign to a variable called closure.

What’s weird is that when we run closure() we can still see the value of fred, even though it was local to closure_maker() which has finished.

Closures are hugely powerful and come with a number of gotchas if not used appropriately. It’s possible to have multiple sub-functions defined in the one parent function, all accessing the same local variables which, by assigning them to global variables, makes them closures.

Because a closure is accessed in effect by reference all those functions access the same closure data - great if that’s what you want, but dangerous if you don’t realise that one function can change fred before another reads it. One (of the many) criticisms thrown at JavaScript is that creating a function within a function by default results in a closure.

This is a mere whistle-stop tour of functional concepts so we’ll leave closures here (lots more to get through yet). For now just get comfortable with the idea that a function can return a function to a calling function that indirectly gives the calling function access to the internal state of the called function, and that when used appropriately this state can be useful.

Time for a curry.

Currying

A word I’ve avoided using so far is composability, but it’s a key concept in functional programming. If all we do is make nice, neat, little functions then they only become useful if they can be composed into bigger, more powerful, functions. It’s like the Russian doll analogy I mentioned earlier - if you have a doll made up of functions that can do calculations, transformations, matching, etc and it can be composed and recomposed in many ways then it’s a pretty useful doll.

What’s more, if all those functions run without risky side effects then we’ve got something useful and safe. One technique that takes a first step to composability is called currying.

Currying is the ability to partially complete an existing function such that the partially-completed function becomes a reusable function in itself

Let’s look at an example, curry it, then see what’s happening. The add_two_numbers() function I started this article with looks like this:

function add_two_numbers(a,b) {
	return (a + b);
}

In Functional Programming, when you have a simple function that you want to use a lot, you can use anonymous functions (functions with no names) and closures (functions that return functions that retain access to their original locally-scoped variables) to make a curried version of the function. If I rewrite the add function as:

function add_two_numbers(a) {
	return function(b) { return a + b; }
}

It takes only one variable and returns a closure function that adds another variable to it. So I can use it like this:

var addTen = add_two_numbers(10);

addTen(1);		// returns 11

addTen(10);		// returns 20

addTen(9);		// returns 19

If that were doing something more fancy than just adding ten to something you can already see the code becomes much more readable. Strictly speaking, a curried function allows itself to be called in both the add_two_numbers(a,b) and the add_two_numbers(a) forms, containing the logic to work out whether to just add two numbers, or return a function that represents a half-finished calculation in need of the final bit of information. I’ve not done this to make it easier to see what’s going on, but in the next article I’ll show how to add currying to any function.

Continuations

Another way to compose functions is to use a continuation

A continuation is a mechanism to explicitly manage (rather than leave implicit) the flow of control between functions

One way of implementing a continuation is called the continuation-passing style and in fact it’s exactly like the lambda function example earlier, except that the function that gets passed in isn’t used to control the internal calculation, but to decide what to do next. A classic what to do next conundrum is when a function encounters a special event.

function add_two_numbers(a,b,c) { 
	if (a + b < 100)
		return (a + b);
	else
		c(a,b)
}

var hwhap = function(a,b) { 
	alert("Houston we have a main bus B undervolt reading " + a + " and " + b);
}

add_two_numbers(10,25,hwhap);		// returns 35

add_two_numbers(10,99,hwhap);		// returns "Houston we have a main bus B
					// undervolt reading 10 and 99"

Aside from the terminology there’s nothing very complex about continuations, but something strange has happened here. Our function add_two_numbers(), which up until now has reliably taken an integer and another integer, added them, and returned another integer, now sometimes returns an integer (such as 35 in the example above) or a string (“Houston we have..”). Functions passing functions and returning functions is all very well if what goes in and what comes out is the same type (i.e. integers in this case) but if other things can come out then we might start getting those side-effects we so desperately want to avoid.

For example we can do this:

add_two_numbers(1,add_two_numbers(2,add_two_numbers(3,
	add_two_numbers(4,add_two_numbers(5,6)))))

which will return 21 (i.e. 1 + 2 + 3 + 4 + 5 + 6). But if anything in that chain of functions goes awry we’re in trouble. If, instead of one of those add_two_numbers(a,b), we inserted a divide_by(a,b) and b was a zero we get a null, or an undef, or an infinity, or something else pretty bad. Continuations could be an answer but if every function had to have something passed into it to handle every error condition we stand to lose all that elegance and supportability.

Fasten your seatbelts ladies and gentlemen, we are about to experience monads.

Monads

If trying to understand functional programming, with all those functions flying around instead of pinned neatly inside a method call, can give you a bit of a headache, then trying to understand monads can put you in hospital. The web is full of home-spun posts purporting to be the one easy way to explain them and yet every one I have ever read has failed in that respect. But each post has added a different perspective which fills in another part of the picture.

Because, you see, I don’t think I understand them either, even though I have written some and even though they are really very very simple indeed.

In our last example we had a simple function that took in integers and spat out integers. The great thing about functional programming is that really this is all we ever care about. What goes on inside a function (as long as it’s not playing with global variables and creating side-effects) is just programming.

Integers in and integers out, means that this works:

func1(func2(func3(func2(func1(func42(some_integer))))));

And it will work for strings, lists, chars etc as long as each function obeys the rule that “what goes in is the same as what comes out”. One problem, as we saw, is that sometimes things goes wrong inside our Russian doll structures. func3(), for example, could return something unexpected to func2() creating an unpredictable ripple of errors up the chain to func1().

There’s also another problem which should be obvious from the examples - functions calling functions calling functions is all very well but the final result still has to go somewhere, or else we can’t see it. It’s no coincidence that sometimes I’ve had to use global variables in my examples, despite starting this whole thing by saying they are bad.

In regular (i.e. non-functional or imperative) programming you call a function (or method) and you put its result into a variable. You can chain methods, or functions, but ultimately the result ends up in a variable, or on the screen, or in a file, or a database, or on the network. It has to leave the elegant world of functions at some time. If you could zoom in with a microscope you see that as functionX() passes its integer result like a baton in the relay race to functionY() it’s also temporarily out of functionland and just a plain old integer (albeit baton-shaped and into another function before we know it).

What we’re saying is that underneath all this function stuff is still a type system that knows about integers, and strings and things, and there are still screens, and networks, and databases, and errors and exceptions that conspire to lay siege to this beautiful pure-functions-only club.

And the functional programming way of dealing with this is to create a sort of smart type system that wraps up the regular types of integers and lists and chars and makes them clever. A clever integer for example, becomes a storage area (or container) for integers that can cope with the fact that maybe the function that was meant to return an integer will return a null. If it gets a null then it can do something about it, instead of passing the buck up the functional command chain. Even if it gets an integer as expected, because it’s smart, it can display it to the screen, or whatever you want. And of course to be smart like this, our smart integer container has to have some standardised interfaces, so that regular functions can pass stuff in and take stuff out.

And that’s it. Those smart containers are monads.

Because monads can do different things they have different names. There’s the Maybe Monad, so called because it contains maybe and integer but can also cope with exceptions, like a divide by zero result. There’s the IO Monad, which deals with (you guessed it) input and output. The List Monad deals with lists. Really they’re just like functions, just a bit more abstract and more standardised in how they are defined. They’re like the glue that binds together all your functions and relates them to the outside (side-effecting) real world. In non-FP, most of us have defined an array, assigned entries to it and used some built-in functions that let us do something with it (iterate over it, find it’s length, etc) and yet we never question where array.length or array.foreach() comes from. It’s just a list monad. Monads are everywhere, but in functional programming, because we need to get all highfalutin about pure functions and steer clear of side-effects they start to become more explicit.

As the barest possible introduction to monads, let’s leave them here. Like I say there’s lots and lots of descriptions and explanations on the web, and you’ll find that depending on how you look at them (what they are, what they’re not, their standard interfaces, how they relate to category theory) they can appear different each time. All they are though is a necessary class of function, using all the features we’ve already looked at (lambda functions, anonymous functions, continuations) to hold it all together. As you read each aspect the bigger picture becomes clearer. A few places I found useful (and still go back to) are Monads are Elephants which nicely explains why everybody can have a different definition and yet still be correct, the Wikipedia Definition and this video by Brian Beckman on MSDN. If you don’t know Haskell (and I don’t) then some of the examples look a bit terse but it’s worth sticking with it. If you get to feeling like it’s time to call the ER then go and find another source and come back later.

Summary

That’s all the time we have for this episode. I’m still ploughing through a worked example to show functional programming in action which should be ready in a few weeks. This has really been a taster menu. If you get all of this then you are well on the way. As I said at the beginning, all of the areas I have described are necessarily light in detail and, as in any subject, as you explore the detail the underlying precision emerges. There’s a Russian saying that goes “the only free cheese is in the mousetrap” and by adding in the free cheese of accessibility, I’ve left the mousetrap of mathematical precision as an exercise for the interested reader.

Further Reading

  1. Why Global Variables are bad

  2. Thread-Safety in Java

  3. Stack-Based Memory Allocation

  4. The heap in memory management

  5. Nice article on recursion vs. iteration in code

  6. Lambda Calculus in Programming Languages

  7. Find, Fold & Map in JavaScript and Ruby

  8. Nice summary of closures in JavaScript

  9. Monads in Functional Programming

The title of this two-parter is derived from a November 1999 article on javaworld.com by Eric Freeman and Susanne Hupfer called ”Make room for JavaSpaces”. It was reading this that led me to functional programming - I’ve always thought of the blackboard pattern in the JavaSpaces model as being a kind of meta-functional programming engine as it allows encapsulated, and memory-shared, space objects to be acted on by distributed specialised workers.