Themes of functional programming
Throughout the examples and concepts discussed in this post there are three key themes:
- Computation as the application of functions
- Avoiding side effects
Computation as the application of functions
Object-oriented programming also uses functions but functional programming is unique in that functions are values (the technical term for this is that functions are “first class”). You can store functions in variables, return them as the value of other functions and pass them in as arguments to other functions. As a result functional programs produce answers by applying these functions in different ways.
Programming languages have the notion of “state”. This is a snapshot of a program’s current environment: all the variables that have been declared, functions created and what is currently being executed.
A stateless expression, on the other hand, is one that does not modify a program’s environment:
Unlike the previous example when we call
increment here we do not change the value of
number we merely return a new value.
Object-oriented programming works by changing program state to produce answers. Conversely, functional programming produces answers through stateless operations. The clearest contrast can be seen in how both methodologies handle looping. An object-oriented approach would be to use a
The loop produces its results by constantly changing the value of
x. A functional approach would involve recursion (covered in more detail later on):
In this case we get our results by calling the
loop function each time with a new value rather than modifying the program’s state.
So, functional programming requires us to write stateless expressions and keep our data immutable.
Avoiding side effects
When a function executes it can change a program’s state aside from returning a value:
The side effect of this function is that it changes the value of
number each time it executes. Functional programming promotes the use of “pure functions”: functions that have no side effects. In the example above changing the value of
number would be disallowed under this paradigm. If we can always write functions that have no side effects our program becomes “referentially transparent”. This means if we input the same value into a program we will always get the same result.
The example above is not referentially transparent because if we always called
sideEffect with 3 we would get a different result each time.
- No assignment i.e. changing the value of something already created with
whileloops (use recursion instead)
- Freeze all objects and arrays (since modifying an existing object or array would be a stateful expression)
Date(since it always produces a new value no matter what the inputs are)
Math.random(same reason as
Why program functionally?
The big advantage functional programming gives us is that we can reason about and test our programs much more easily. This can help us to be more productive, reduce bugs and write better software. It is not always possible to write everything in a purely functional manner but it is something to strive for. John Carmack of Id Software wrote a good article discussing the practical considerations of functional programming.
Concepts in functional programming
First class and higher-order functions
The latter two expressions are examples of “higher-order” functions. These are functions that either return functions as their result or take other functions as arguments.
In this example the function returned by
closure can still access
a since it is in its outer scope.
When functions return they “take a picture” of their current environment which they can read the latest values from. So, in essence, closures are functions which, as well as having an expression body and taking arguments, also record an outer scope or environment. Importantly, closures always have access to the latest value of a variable. If we rewrite the example above to always increment
a we can see how this is the case (although this breaks our functional principles):
A recursive function is a function that quite simply calls itself:
Functional programming favours recursion for looping rather than traditional
for loops since we can maintain statelessness and avoid side effects. For example, to compute the factorial of value
n statefully we might do:
A stateless approach would be:
Tail call optimisation
Most functional programming languages implement “tail call optimisation” for recursive functions. In order to understand this it would be best to begin by looking at what happens when recursion is not optimised in this manner.
console.trace logging you can see the call stack for the
recursiveFactorial function above:
This stack is built up so when a value is returned the program knows where to go back to.
A “tail call” is a call to a function that occurs as the last action of another function. Our recursive calls above are not tail calls since the final action of the function is to multiply what is returned by
n. Let’s change this around so they are:
recur is called.
In programming languages that do support tail call optimisation a large call stack like this would not be built up. The language can determine that if a call is in tail position extra space does not need to be created for it on the stack each time it is called. A Wikipedia example illustrates the procedure quite nicely.
while loops. However, in ECMAScript 6 tail calls will be optimised.
Continuation passing style
For the time being we can still write loops in a recursive manner without taking up extra space on the call stack. This can be done with continuation passing style (CPS).
In this example we pass a continuation to our
get method when the data has been retrieved.
A more complex example is factorial in CPS:
With our original recursive factorial example, once we reached the end of the “loop” each result had to be returned to its original caller meaning the program had to go all the way back through the stack to get the final result.
On the other hand, with CPS once the “loop” is at an end the function returns the result of applying the continuation with 1. This in turn applies the result of that function to another continuation and so on until we get the final result. So, rather than going all the way back through the call stack the
CPSFactorial function creates new functions that each represent the next stage of the computation.
Thunks and trampolines
With CPS there is still some recursion:
CPSFactorial calls itself several times during the computation. We can avoid recursion completely with “thunks” and “trampolines”.
In this case our
thunk stores a function and a list of arguments to be executed at a later time. Thanks to closures thunks have a record of their environment when they are stored. The
thunkValue function simply returns the final value of our computation.
We can handle all of the thunks we create with a trampoline:
trampoline takes a thunk and calls its function with its arguments if it has the correct tag otherwise it returns a value. This example breaks our rule of statelessness (since we reassign
thk to a new value each time) so we could write this as follows:
However, we are then back to using recursion again.
We can use thunks and a trampoline to calculate factorial:
In this example we avoid recursion completely since we’re always creating new thunks to be executed rather than functions invoking themselves.
A fun (but pointless) implementation of this is a jQuery plugin that can act as a replacement for jQuery’s
Optimisations in functional programming
Partial application (currying)
bind simply returns a new function with a custom context and arguments pre-filled:
test creates a new function which when invoked already has the
a argument filled in as 3.
bind as follows:
Exactly like the ES5 method, the
bind function in this case returns a new function which when called applies the function we passed into it with an argument pre-filled.
Functions that are expensive to run can be optimised with memoisation. This involves using a closure to cache the results of previous calls to the function. A very simple example would be:
Here we pass a function to
memoise whose results we wish to cache. When we call
memo it will either retrieve the value from the cache or it will call the memoised function and store its value in the cache. It’s worth noting that in order for us to be able to memoise a function it must be referentially transparent otherwise no results will ever be cached.
Of course this example breaks our rule of avoiding side effects. Unfortunately it is quite problematic to use memoisation without changing state since we have to keep updating our cache. It is easier in a language like Haskell that can use lazy evaluation to memoise.
Memoisation is most useful where a function is likely to be calculating many of the same results such as the fibonacci sequence.
This article has looked at functional programming’s key themes, its main concepts and optimisations the paradigm can make.
In a future post I hope to discuss how all of this can be tied together to create a functional application.