Functional programming: what’s it all about?

pheaven — Mon, 03 Dec 2007 02:35:32 -0700

Most programmers today will be familiar with a number of programming paradigms. The age-old procedural programming paradigm, where a program is broken down into a number of procedures or routines, is still very much alive and the right solution for a number of problems. Object Oriented programming is one of the most popular and fashionable paradigms today, allowing for a good level of code re-use through mechanisms such as instance management (one class can be instantiated many times to give many objects), data hiding (think private variables in a class) and inheritance.

Another paradigm cross-cuts these two: that of imperative programming. This simply means that a program consists of a sequence of instructions that are executed one after the other (or at least appear to be; both the compiler and the CPU may well re-order instructions to improve performance when it does not affect the behavior of the program). In fact, when I was younger my definition of a computer program included the words “a sequence of instructions”.

At that time, probably like many programmers today, I hadn’t been exposed to any programming languages that worked differently to this. Java, C#, all of the many dialects of Basic, Pascal…all of these frequently used languages are imperative. This is not a bad thing; in fact, it’s psychologically comfortable for us as humans, since we tend to plan how to achieve a task by breaking it down into a set of steps or follow sequences of instructions ourselves (for example, when making food).

Today I’m going to talk a little about functional programming. If you’ve seen it before this may be nothing new. If you have not, then hopefully it challenges a few assumptions you may have made about programming and arms you with another approach to solving some problems. Just as you can fake out object orientation somewhat in languages without direct OOP support, you can use functional techniques in some non-functional languages.

=== ML ===
It is going to be useful to have a language to provide examples in. I have selected the Standard ML language, and you can download the Moscow ML interpreter for free, should you want to try some of the examples for yourself.

=== Yes, functional programming uses functions ===
A function takes one or more parameters and, based upon them, computes a value. This is sounding somewhat like procedural programming so far, but remember that we’re not supposed to be writing our programs as sequences of instructions. Instead, we will write programs by writing functions that call other functions to build up their result.

Let’s start off with a simple example: the function double, which multiplies a number by 2.

- fun double(x) = 2 * x;
> val double = fn : int -> int

The “-“ is the prompt in the Moscow ML interpreter. The rest of the first line is what I typed to define the function. The “x” in the brackets is the name of the parameter the function takes. Following the “=” is the computation that the function performs: multiplying the value passed as the parameter “x” by 2. I can apply this function to a value, for example the number 21:

- double(21);
> val it = 42 : int

Giving the answer 42, surrounded by words of cryptic wonder. But what on earth are these responses that the ML interpreter gives us?

=== An Aside On Type Inference ===
After I specified the function “double” the ML interpreter gave me a somewhat cryptic looking response.

> val double = fn : int -> int

Notice that I did not specify the type of the parameter “x” or the type of the function “double”. Instead, ML has worked out the type of the function for me. Intuitively, it has looked at the function, seen that we have multiplied the parameter by an integer (type “int”) and therefore inferred that the parameter “x” must be an integer too, and that the overall result of the function is also going to be an integer. It has therefore given it the type “int -> int”, the arrow symbol “->” denoting that this is a function type (rather than just the type of a simple value, such as the number 42 with just has type “int”) that takes a value of the type to the left of the arrow and returns a value of the type to the right of the arrow.

This is called type inference. Type inference is a process by which a compiler can determine the types of your variables and functions. This is unlike languages like C, C# and Java, where we write the types ourselves and the compiler just checks them. It is often (but not always) found in functional languages. The type that is inferred will always be displayed after a colon.

It’s worth noting that functional languages often have elaborate type systems, and if you want to really understand a language like ML then you have to understand the type system too. We’re simply using ML to understand functional programming here, so we will put the type system aside for today.

=== Composing functions ===
I said earlier that we build functions up from other functions. Here is an example of us defining a “triple” function in terms of the double function:

- fun triple(x) = x + double(x);
> val triple = fn : int -> int

We can see something in this program, however, that does not appear to be a function – the “+” operator. In other functional languages, you would be forced to write something more like:

+(x, double(x))

ML provides some nicer syntax, but conceptually you can think of it as just that – syntax that really maps to calling some addition function. In fact, if we have a language that only gives us functions (and no other built-in data types, such as the integers), it is possible to write a program to perform any computation that you would be able to in any other language you might have worked in. This property is called Turing Completeness, and I mention it here so you can see the true power of functional programming. Of course, a language with no basic data types would be impractical for any real world usage.

=== Name Binding – Liberation From Assignment ===
In a pure functional programming language, the concept of assigning a value to a variable does not exist. That is, there are no storage locations. When I have been using the “=” operator, it has not been doing assignment; instead, it has been doing something known as name binding. I can, for example, write the following code:

- val a = 21;
> val a = 21 : int
- triple(a);
> val it = 63 : int

You may be thinking “there is a storage location with name a”, but actually the correct way to think of this is “the name a is bound to the value 21”. When I use “a” as the parameter for the function “triple”, it is as if the value “21” is textually substituted in for “a”. If I later write the following:

- val a = "badger";
> val a = "badger" : string

Then the name “a” is now bound to the string value “badger”. Notice that the result of this is to give “a” a different type. This is fine because “a” does not refer to some storage location of a given type, it is just a name that refers to a value. To really make the semantics clear, consider this example:

- val multiplier = 5;
> val multiplier = 5 : int
- fun multiply(x) = multiplier * x;
> val multiply = fn : int -> int
- multiply(5);
> val it = 25 : int
- val multiplier = "badger";
> val multiplier = "badger" : string
- multiply(5);
> val it = 25 : int

Everything is as expected for the first six lines. However, when I re-bind the name “multiplier” to the string “badger”, the “multiply” function continues to use the value that the name was bound to when it was defined. Therefore the outcome of the multiply function does not change. This behavior is very different to the behavior you would get with assignment.

Having modifiable storage locations actually makes programs harder to reason about formally and to understand intuitively. Most programmers have learnt not to use global variables unless they really need to, since they can be modified by any part of the program at any point in time. Even the best C programmers have likely screwed up with pointers and spent hours tracking down the resultant problems at some point. It’s clear that assignment has its issues, and that getting away from it can help.

I’m not by any means saying that name binding is a good answer for all problems. Indeed, ML does provide you with references and a mutable (modifiable) store. Sometimes you need that for performance, or now and then because doing without it is just plain hard. You can comfortably write a lot of programs free of assignment, however.

Name binding is hard to take to everyday languages because they don’t really do it a great deal. Where they tend to do it, at least conceptually, is when passing parameters to a procedure or method. We can probably learn that assigning to parameters is a bad idea. I really don’t want to advocate not using any variables in a procedure and just expressing it entirely in terms of the parameters, but it follows that shorter procedures will need to introduce less extra variables. Writing many shorter procedures or methods rather than a single big long one has been common advice for ages anyway, though.

=== Recursion Replaces Iteration ===
The fact that there is no mutable storage means that loops as they exist in non-functional languages are not really possible. There is no way to have a counter for a for loop, for example. Therefore recursion tends to be used in its place. For example, we can re-write the following loop (written in pseudo code):

for i = 1 to x
    sum += i
next i

As the following functional program using recursion:

- fun sumfirst(x) = if x = 0
                    then 0
                    else x + sumfirst(x - 1);
> val sumfirst = fn : int -> int
- sumfirst(10);
> val it = 55 : int

A common response to this is that “recursion is slow”. This is true, but if we re-organise the program to maintain and pass on a running total:

- fun sumfirst(x,t) = if x = 0
                      then t
                      else sumfirst(x - 1, t + x);
> val sumfirst = fn : int * int -> int
- sumfirst(10,0);
> val it = 55 : int

Then the result of calling the function, in the recursive case, only depends on the function “sumfirst” itself. Therefore ML is able to make an optimisation called a tail call. This means that instead of making a new call frame, we re-use the current one, since it is no longer needed. This makes the program run faster than a recursive program normally would and, most importantly, it will not build up a large call stack and use a lot of memory. (While on the subject, Parrot, a virtual machine for dynamic languages, has a JIT compiler that can spot tails calls and sometimes can optimize them to loops at the machine code level, meaning recursively defined functions can be as fast as their loop-based counterparts.)

A recursive solution to a problem can often be very elegant, though be aware that tail calling isn’t implemented in many non-functional languages. Interestingly, the .Net CLR supports it.

=== List Processing and Pattern Matching ===
We can introduce a list containing the numbers from one to ten like this:

- val onetoten = [1,2,3,4,5,6,7,8,9,10];
> val onetoten = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] : int list

A list, unlike an array, is not mutable. We do not index into it at a certain point as we would with an array; instead we recursively move through the list. We can use the “cons” (written “::”) constructor to break a list into its first element (called the head) and the rest of the list (called the tail). The following function extracts the head of the list:

- fun head(h::t) = h;
! Toplevel input:
! fun head(h::t) = h;
!     ^^^^^^^^^^^^^^^
! Warning: pattern matching is not exhaustive
> val 'a head = fn : 'a list -> 'a
- head(onetoten);
> val it = 1 : int

We have been given a warning here, which cryptically tells us that we did not specify what to do in the case of an empty list. This means that we will get an exception if we try to pass an empty list to this function:

- head([]);
! Uncaught exception:
! Match

We may choose to return zero when the list is empty:

- fun head(h::t) = h
    | head([])   = 0;
> val head = fn : int list -> int
- head(onetoten);
> val it = 1 : int
- head([]);
> val it = 0 : int

The vertical bar introduces a highly powerful technique called pattern matching. You can think of it somewhat like overloading methods with the same name and different parameter lists. However, we specify all of the behaviors within the one function – only writing the name once. Here we use pattern matching to specify what to do in each of the possible cases: when there is an element in the list that we can extract and when there isn’t (one of which must always be the case). Inductive proofs of program correctness can often quite closely follow the structure of code like this.

=== Programs And Data Are Equivalent ===
Many programmers like to keep their program and the data it works on separated in their mind. We have variables that hold data and we pass them to procedures or methods that make up the program. In functional programming, however, functions are just another form of data too. That is, you can pass a function as a parameter to another function. We already saw this the other way round earlier, when I stated that you could encode any other data type (such as the integers) just using functions.

Some of the most useful examples involve dealing with lists. Let’s take our previous list of the integers between 1 and 10.

- val onetoten = [1,2,3,4,5,6,7,8,9,10];
> val onetoten = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] : int list

Now suppose I wanted to extract just the even elements of the list; I could write the following function:

- fun justevens ([])    = []
    | justevens (x::xs) = if x mod 2 = 0
                          then x :: justevens(xs)
                          else justevens(xs);
> val justevens = fn : int list -> int list
- justevens(onetoten);
> val it = [2, 4, 6, 8, 10] : int list

I could define a function to get just the odd elements of the list in a similar way:

- fun justodds([])    = []
    | justodds(x::xs) = if x mod 2 = 1
                        then x :: justodds(xs)
                        else justodds(xs);
> val justodds = fn : int list -> int list
- justodds(onetoten);
> val it = [1, 3, 5, 7, 9] : int list

However, we’ve now duplicated all of the code that moves through the list. It would be good to separate the condition that we want to use when choosing items from the list from the code to move through the list. We start by writing two “predicate” functions (a fancy name for functions that return a boolean) that will test whether a single integer is even or odd:

- fun iseven(x) = x mod 2 = 0;
> val iseven = fn : int -> bool
- fun isodd(x) = x mod 2 = 1;
> val isodd = fn : int -> bool
- iseven(2);
> val it = true : bool
- isodd(2);
> val it = false : bool

These return true or false depending on whether the number is even or odd. We will now write a function that takes a list and one of these predicate functions and uses the predicate to decide whether the element should be in the result list.

- fun filter([], p) = []
    | filter(x::xs, p) = if p(x)
                         then x :: filter(xs, p)
                         else filter(xs, p);
> val 'a filter = fn : 'a list * ('a -> bool) -> 'a list

We can now pass the “iseven” and “isodd” functions to the “filter” function. Then, when we call “p”, passing it the parameter “x”, it will call whatever function we passed. In fact, if you were to substitute the body of “iseven” or “isodd” in place of “p”, you’ll find that we get back to the same code as we had for the original two “justevens” and “justodds” functions we wrote earlier. The behaviour is the same, too:

- filter(onetoten, iseven);
> val it = [2, 4, 6, 8, 10] : int list
- filter(onetoten, isodd);
> val it = [1, 3, 5, 7, 9] : int list

However, our program is now shorter and exhibits better code re-use. A function that takes another function as a parameter is usually called a higher order function. When you are using this kind of technique, you are doing higher order programming.

=== Anonymous Functions ===
Anonymous functions are also commonly used in functional programming. That is, you can define a function without giving it a name. The syntax for this is “fn parameter list => body”. In the following example we define and pass a predicate function that checks if the value is less than 5.

- filter(onetoten, fn x => x < 5);
> val it = [1, 2, 3, 4] : int list

The ability to pass functions is one of the most useful techniques we can lift out of functional programming, and many languages have. C and C++ had function pointers. C# 1.0 had delegates, C# 2.0 introduced anonymous methods and C# 3.0 introduces syntax almost identical to the ML anonymous function syntax shown here. Perl, Python and Ruby all allow for higher order programming too.

=== So What Have We Learnt? ===
Functional programming isn’t scary nor solely for academics. It provides some pretty neat ideas, and the languages that most programmers are used to working in are starting to incorporate them. Here’s a summary.
* Writing a sequence of instructions isn’t the only way to write a program.
* A programming language that only had functions and nothing else would be totally impractical but you could still write any program in it that you wished.
* There is life without variables and assignment.
* Recursion can replace iteration, and with tail recursion that can be efficient.
* Lists are a way to do array like stuff in a functional language, and free us from worrying about bounds checking.
* Pattern matching is mighty and powerful and makes functional languages great for writing compilers. And writing compilers is fun and good for the soul, right?
* Higher order functions are making their way into everyday languages and can improve code re-use.

Posts Tagged With 'Type Inference' RSS Feed

Functional programming: what’s it all about?