This week's xkcd cartoon raises a can of worms - not a pretty picture. What is functional programming? Surely all our programs should function in some way or other? No - that's not what it means. Functional programming is altogether different....
More cartoon fun at xkcd a webcomic of romance,sarcasm, math, and language
Math - don't you just love it.
So much so that a lot of programmers wish that programming was more like math. There have been lots of attempts to make programming precise in the sense that programs can be verified just like a mathematical proof. The power of math is such that anything that makes messy programming look more like perfect math.
But there are so many ways in which programming isn't like math at all. The big difference is that programming as we practice it mostly includes the ideas of time and state changes.
A program isn't a static statement of some universal truth; rather it is a set of instructions that have a time sequence built in. A program doesn't even follow the same route each time it is executed. It reacts to the state of the environment around it and it can change its own state each time it is run.
A program is so much more than a mathematical proof.
If you want to confuse a mathematician then write on one side of the card:
"The statement on the other side of this card is true"
and on the other side:
"The statement on the other side of this card is false"
and hand it over.
The result is usually a mathematician in melt down.
A programmer on the other hand is happy to think that the state changes as the card is flipped. The statement on the side you are looking at is true. Flip the card over and the statement on the other side becomes false and so on. You have a flip flop that changes state as you turn the card over.
Don't take this example too seriously because if you do you will miss the point and risk vanishing in a puff of logic.
The difference between programming and math is that in programming you can, and probably must, write things like:
but in math this is just silly. So silly that you can use it to prove that 1=0 by subracting x from both sides.
This difference is one of the reasons beginners find programming difficult. Until they learn to see time as an element of what they read and write, it all seems very alien and the idea of a variable is mysterious.
To be fair, math does have variables, but they are used in very restricted ways compared to the way they are used in programming; and where they are used more like as in programming then the math begins to look like programming. Math mostly deals with change by taking a snapshot and making everything static - what else is a function in the f(t) sense other than frozen time? It isn't a dynamic process but a subset of the Cartesian product of two sets.
So what does all this have to do with functional programming?
The simple answer is that functional programming aims to remove the state and mutability out of programming and make it more like static maths. In other words it attempts to freeze time out of programming in the same way maths does.
This is the usual "standard" statement of functional programming, but it isn't quite as pure as this sounds. There is a lot of messiness in functional programming but it is often wrapped up in so much jargon you can't really see it for the clutter.
In math functions are stateless. If you evaluate sin(Pi) at 12 noon today then you will get the same answer when you evaluate it at 12 noon tomorrow. In math functions don't change.
In functional programming functions aren't just ways of grouping things together in a neat package. Function are first class objects and can be used anywhere a number or an expression can be used. They are also "higher order" functions which can accept functions and spit out functions as their result. Most important of all functions never change the state of the system - they don't have side effects.
The no-side effect rule is a bit difficult to stick to because if the system is going to deliver a result or interact with a user then side effects are essential and some state has to change.
You will often hear the term immutable used in connection with functional programming and exactly what it means is often confused with a simpler idea - object immutability.
Object immutability is an easy idea. For example if a String object is immutable it can't be changed but this doesn't mean you can't do:
What happens in this case is that the String object that the variable string1 is referencing is destroyed and a new object created with "A" attached to its right hand end. This is an almost trivial meaning of immutable and if it wasn't pointed out it would go unnoticed.
The real important use of immutable in functional programming is the way variables don't - vary that is. For example in F# if you write
then that's it x is one forever and ever. This is immutability of reference or value depending on the type of data involved.
Hold on a moment doesn't banning variables mean that you can't write things like
You can't increment a variable because there are no variables. Once a symbol is bound to a value it doesn't and can't change.
OK, so how do functional programmers do things that "normal" dysfunctional programmers take for granted - like count how many times something happens or add up the first ten integers?
The answer is that in functional programming no symbol is ever bound to a value until its final value is known. This is the "frozen time" approach of math.
Take, for example, the problem of adding up the first ten integers. In most programming languages you would write something like:
That is, you would use a for or some other sort of loop to form a running sum until you had the answer, i.e. 45. The symbol "total" would change its value all through the loop until it got to the final answer. It is a machine that whirs into life to loop round counting things.
If you want to make symbols immutable then you can't do things in this way. You have to use recursion to put off binding any intermediate results until you have the final answer.
The way to do this is to suppose that we have a function that returns the sum of integers from x to 9, e.g. sumto9(x). Well it's obvious that sumto9(9) is 9, it is also obvious that sumto(8) is 8+9 or 8+sumto(9). You can also see that this generalizes to sumto(x)=x+sumto9(x+1) with sumto(9) defined as 9. Writing this as a recursive function gives:
if(x=9) return x;
Now you can write:
total never has to be set to an intermediate value, it just gets bound to its final value in one go.
You could argue that all of the "variables" of the process are now in the recursion, but notice that x doesn't change - it just gets created in a new context each time the function is called. That's the whole point of function parameters - they allow things to change by being re-created - see object immutability discussed earlier. Function parameters do most of the work that variables do in dysfunctional programming.
As we don't have variables we don't need loops and recursion plays the role of iteration and parameters play the role of loop variables.
OK, but what is this "tail recursion"?
Well if you can arrange your recursive functions so that the call to the next function occurs right at the end of the function i.e. in the tail then the function can be optimized by the compiler into a loop.
Yes that's right - you go to the trouble of thinking recursively and the compiler undoes it all and re-writes it as a loop.
The reason that this can be done is that as soon as the tail of the function is reached the compiler can throw away all of the state information about the function, i.e. its stack frame, and treat the new call as part of the same function call. That is it unwinds:
into something like:
let total=0+(0+1)+(1+1)+(2+1)+(3+1)+(4+1) ... +9
With tail recursion optimization functional languages are as efficient as dysfunctional languages.
There are lots of other related mechanisms for putting off binding a value to a symbol until the value is completely determined but they all have a similar feel and use the same sort of techniques.
Perhaps the most notorious of all functional programming mechanisms for getting things done that are natural in dysfunctional languages is the monad.
To explain the subtleties of the monad would take another article, but what you really need to know is that the monad puts the sequence of operations idea back into functional programming. Monads provide the facilities to implement side effects, I/O, variable assignment and so on in a way that looks static - unless you look very carefully that is.
So is all of this just magic for the dysfunctional programmer to worry about?
Well yes - and no.
It is sadly true that functional programmers have a tendency to use math - category theory in particular - to make simple ideas seem very much more sophisticated.
You need to always keep in mind that programming is essentially practical and hence cannot be as complicated as abstract mathematics.
However there are times when functional programming just seems right. There is also no doubt that some of the tools of functional programming are hard to give up once you have experienced their advantages.
For example, every programming language should have first class and higher functions - it just makes things so much simpler and so much more powerful. Every language should also have some of the handy toolkit of higher order functions that functional languages have - things like map, reduce, filter and so on, the sort of thing you find in say Ruby's functools.
When it comes to some types of computation then a functional approach does seem to work well but when it comes to needing side effects dysfunctional programming does the job. If you want to build a UI there is a lot to be said for object oriented procedural programming.
Finally - should you learn a functional programming language?
After all, what harm can it do and tail recursion would be your reward.