What is Functional Programming?

Functional programming should not be confused with the imperative (or procedural) style of programming that we have been using in most of the topics so far. Neither is it like object oriented programming. It is something different. Not radically so, since the concepts that we will be exploring are familiar programming concepts, just expressed in a different way. The philosophy behind how these concepts are applied to solving problems is also a little different.

Functional programming is all about expressions. In fact another way to describe FP might be to term it expression oriented programming since in FP everything reduces to an expression. You should recall that an expression is a collection of operations and variables that results in a single value. Thus x == 5 is a boolean expression. 5 + (7-Y) is an arithmetic expression. And "Hello world".uppercase() is a string expression. The latter is also a function call (Or more strictly a method call) on the string object "Hello world" and, as we shall see, functions are very important in FP (You might already have guessed that from the name!).

Functions are used as objects in FP. That is they are often passed around within a program in much the same way as other variables. We have seen examples of this in our GUI programs where we assigned the name of a function to the command attribute of a Button control. We treated the event handler function as an object and assigned a reference to the function to the Button. This idea of passing functions around our program is key to FP.

Functional Programs also tend to be heavily List oriented.

Finally FP tries to focus on the what rather than the how of problem solving. That is, a functional program should describe the problem to be solved rather than focus on the mechanism of solution. There are several programming languages which aim to work in this way, one of the most widely used is Haskell and the Haskell web site ( www.haskell.org) has numerous papers describing the philosophy of FP as well as the Haskell language. (My personal opinion is that this goal, however laudable, is rather overstated by FP's advocates.)

A pure functional program is structured by defining an expression which captures the intent of the program. Each term of the expression is in turn a statement of a characteristic of the problem (maybe encapsulated as another expression) and the evaluation of each of these terms eventually yields a solution.

Well, that's the theory. Does it work? Yes, sometimes it works very well. For some types of problem it is a natural and powerful technique. Unfortunately for many other problems it requires a fairly abstract thinking style, heavily influenced by mathematical principles. The resultant code is often far from readable to the layman programmer. The resultant code is also often much shorter than the equivalent imperative code and more reliable.

It is these latter qualities of conciseness and reliability that have drawn many conventional imperative or object-oriented programmers to investigate FP. Even if not embraced whole heartedly there are several powerful tools that can be used by all.

How does Python do it?

Python provides several functions which enable a functional approach to programming. These functions are all convenience features in that they can be written in Python fairly easily. What is more important however is the intent implicit in their provision, namely to allow the Python programmer to work in a FP manner if he/she wishes.

We will look at some of the functions provided and see how they operate on some sample data structures that we define as:

choices = ['eggs','chips','spam']
numbers = [1,2,3,4,5]

def spam(item): 
    return "Spam & " + item

map(aFunction, aSequence)

This function applies a Python function, aFunction to each member of aSequence. The expression:

L = map(spam, choices)
print( list(L) )

Results in a new list (in this case with a "Spam & " prefix to each item) being returned in L. Notice that we passed the function spam() into the map() function as a value. (That is, we didn't use parentheses to execute the function code, we just used its name as a reference to the function.) You might recall we did the same thing with event handlers in the GUI Topic. This ability to treat functions as values is one of the key features of Functional Programming.

We could have achieved the same effect by writing:

L = []
for i in choices:
   L.append( spam(i) )
print( L )

Notice however, that the map function allows us to remove the need for a nested block of code. From one point of view that reduces the complexity of the program by one level. We'll see that as a recurring theme of FP; that use of the FP functions reduces the relative complexity of the code by eliminating blocks.

filter(aFunction, aSequence)

As the name suggests filter extracts each element in the sequence for which the function returns True. Consider our list of numbers. If we want to create a new list of only odd numbers we can produce it like so:

def isOdd(n): return (n%2 != 0) # use mod operator
L = filter(isOdd, numbers)
print( list(L) )

Again notice that we pass the name of the isOdd function into filter as an argument value rather than calling isOdd() as a function.

Alternatively we can write:

def isOdd(n): return (n%2 != 0)
L = []
for i in numbers:
   if isOdd(i):
      L.append(i)
print( L )

Again notice that the conventional code requires two levels of indentation to achieve the same result. Again the increased indentation is an indication of increased code complexity.

There are a few other functional programming tools in a module called functools which you might like to import and explore at the >>> prompt. (Remember dir() and help() are your friends.)

lambda

One feature you may have noticed in the examples so far is that the functions passed to the FP functions tend to be very short, often only a single line of code. To save the effort of defining lots of very small functions Python provides another aid to FP - lambda. The name lambda comes from a branch of mathematics called Lambda Calculus which uses the Greek letter Lambda (λ) to represent a similar concept.

Lambda is a term used to refer to an anonymous function, that is, a block of code which can be executed as if it were a function but without a name. Lambdas can be defined anywhere within a program that a legal Python expression can occur, which means we can use them inside our FP functions.

A Lambda looks like this:

lambda <aParameterList> : <a Python expression using the parameters>

Thus the isOdd function above could be rewritten as:

isOdd = lambda j: j%2 != 0

L = filter(lambda j: j%2 != 0, numbers)
print( list(L) )

And the call to map can be done using:

L = map(lambda s: "Spam & " + s, choices)
print( list(L) )

By the way, you may have noticed that we have been explicitly converting the results of map() and filter() to lists. This is because map and filter are actually classes that return instances of something called an iterable. An iterable is basically something that acts like a sequence, or collection, when used in a loop and can be converted to a list but is more efficient in the way it uses memory. Our old friend range() is also an iterable. Python makes it possible to create your own iterable types, should you need to, but I won't be discussing that in the tutorial.

List Comprehension

List comprehension is a technique for building new lists borrowed from Haskell and introduced in Python since version 2.0. It has a slightly obscure syntax, similar to mathematical set notation. It looks like this:

[<expression> for <value> in <collection> if <condition>]

Which is equivalent to:

L = []
for value in collection:
    if condition:
        L.append(expression)

As with the other FP constructs this saves some lines and two levels of indentation. Let's look at some practical examples.

First let's create a list of all the even numbers less than 10:

>>> [n for n in range(10) if n % 2 == 0 ]
[0, 2, 4, 6, 8]

That says we want a list of values (n) where n is selected from the range 0-9 and n is even (n % 2 == 0).

The condition at the end could, of course, be replaced by a function, provided the function returns a value that Python can interpret as boolean. Thus looking again at the previous example we could rewrite it as:

>>>def isEven(n): return ((n%2) == 0)
>>> [ n for n in range(10) if isEven(n) ]
[0, 2, 4, 6, 8]

Now let's create a list of the squares of the first 5 numbers:

>>> [n*n for n in range(5)]
[0, 1, 4, 9, 16]

Notice that the final if clause is not needed in every case. Here the initial expression is n*n and we use all of the values from the range.

Finally let's use an existing collection instead of the range function:

>>> values = [1, 13, 25, 7]
>>> [x for x in values if x < 10]
[1, 7]

This could be used to replace the following filter function:

>>> print( list(filter(lambda x: x < 10, values)) )
[1, 7]

List comprehensions are not limited to one variable or one test however the code starts to become very complex as more variables and tests are introduced.

Whether comprehensions or the traditional functions seem most natural or appropriate to you is purely subjective. When building a new collection based on an existing collection you can use either the previous FP functions or the new list comprehensions. When creating a completely new collection it is usually easier to use a comprehension.

Remember though that while these constructs may seem appealing, the expressions needed to get the desired result can become so complex that it's easier to just expand them out to their traditional python equivalents. There is no shame in doing so - readability is always better than obscurity, especially if the obscurity is just for the sake of being clever!

Other constructs

Of course while these functions are useful in their own right they are not sufficient to allow a full FP style within Python. The control structures of the language also need to be altered, or at least substituted, by an FP approach. One way to achieve this is by applying a side effect of how Python evaluates boolean expressions.

You may recall from the branching topic that Python uses short circuit evaluation of boolean expressions. Certain properties of these expressions can be exploited to provide an FP style of program control. To recap on short-circuit evaluation: when a boolean expression is evaluated the evaluation starts at the left hand expression and proceeds to the right, stopping when it is no longer necessary to evaluate any further to determine the final outcome.

Taking some specific examples let's see how short circuit evaluation works:

>>> def TRUE():
...   print( 'TRUE' )
...   return True
...   
>>>def FALSE():
...   print( 'FALSE' )
...   return False
...

First we define two functions that tell us when they are being executed and return the value of their names. Now we use these to explore how boolean expressions are evaluated (Note that the upper case output is from the functions whereas the mixed case output is the result of the expression):

>>> print( TRUE() and FALSE() )
TRUE
FALSE
False
>>> print( TRUE() and TRUE() )
TRUE
TRUE
True
>>> print( FALSE() and TRUE() )
FALSE
False
>>> print( TRUE() or FALSE() )
TRUE
True
>>> print( FALSE() or TRUE() )
FALSE
TRUE
True
>>> print( FALSE() or FALSE() )
FALSE
FALSE
False

Notice that only if and only if the first part of an AND expression is True then (and only then) will the second part be evaluated. If the first part is False then the second part will not be evaluated since the expression as a whole cannot be True.

Likewise in an OR based expression if the first part is True then the second part need not be evaluated since the whole must be True.

There is one other feature of Python's evaluation of boolean expressions that we can take advantage of, namely that when evaluating an expression, Python does not simply return True or False, rather, it returns the actual value of the expression. Thus if testing for an empty string (which would count as False) like this:

if "This string is not empty": print( "Not Empty" )
else: print( "No string there" )

Python just returns the string itself!

We can use these properties to reproduce branching like behavior. For example suppose we have a piece of code like the following:

if TRUE(): print( "It is True" )
else: print( "It is False" )

We can replace that with the FP style construct:

V =  (TRUE() and "It is True") or ("It is False")
print( V )

Try working through that example and then substitute the call to TRUE() with a call to FALSE().

Thus by using short circuit evaluation of boolean expressions we have found a way to eliminate conventional if/else statements from our programs. You may come across these tricks in some older code however, these tricks can backfire so, in more recent versions of Python, a new construct has been introduced that allows us to write an if/else condition as an expression, and it is called a conditional expression, and it looks like this:

result = <True expression> if <test condition> else <False expression>

And a real example looks like this:

>>> print( "This is True" if TRUE() else "This is not printed" )
TRUE
This is True

And using the else:

>>> print( "This is True" if FALSE() else "We see it this time" )
FALSE
We see it this time

You may recall that in the recursion topic we observed that recursion could be used to replace the loop construct. Thus combining recursion with conditional expressions can remove all conventional control structures from our program, replacing them with pure expressions. This is a big step towards enabling pure FP style solutions.

To put all of this into practice let's write a completely functional style factorial program using lambda instead of def, recursion instead of a loop and conditional expressions instead of the usual if/else:

>>> factorial = lambda n: ( None if n < 0 else 
                            1 if (n == 0) else 
                            factorial(n-1) * n )
>>> print( factorial(5) )
120

And that really is all there is to it. It may not be quite so readable as the more conventional Python code but it does work and is a purely functional style function in that it is a pure expression. (Note that I used a set of parentheses around the entire expression, which allows us to spread it over multiple lines to improve readability. I then vertically aligned the 3 possible return values as individual lines - this is a very common idiom borrowed from Lisp languages which tend to use recursion a lot.)

Conclusions

At this point you may be wondering what exactly is the point of all of this? You would not be alone. Although FP appeals to many Computer Science academics (and often to mathematicians) most practising programmers seem to use FP techniques sparingly and in a kind of hybrid fashion mixing it with more traditional imperative styles as they feel appropriate.

When you have to apply operations to elements in a list such that map or filter seem the natural way to express the solution then by all means use them. Just occasionally you may even find that recursion is more appropriate than a conventional loop. Even more rarely will you find a use for short circuit evaluation or, better, a conditional expression rather than conventional if/else - particularly if required within an expression. As with any programming tool, don't get carried away with the philosophy. Rather, use whichever tool is most appropriate to the task in hand. At least you know that alternatives exist!

There is one final point to make about lambda. There is one area outside the scope of FP that lambda finds a real use and that's for defining event handlers in GUI programming. Event handlers are often very short functions, or maybe they simply call some larger function with a few hard-wired argument values. In either case a lambda function can be used as the event handler which avoids the need to define lots of small individual functions and fill up the name space with names that would only be used once. Remember that a lambda statement returns a function object. This function object is the one passed to the widget and is called at the time the event occurs. If you recall how we define a Button widget in Tkinter, then a lambda would appear like this:

b = Button(parent, text="Press Me", 
           command = lambda : print("I got pressed!"))
b.pack()

notice that although the event handler is not allowed to have a parameter, we are allowed to specify a string inside the body of the lambda. Thus we can now add a second button with a completely different string:

b2 = Button(parent, text="Or Me", 
           command = lambda : print("I got pressed too!"))
b2.pack()

We can also employ lambda when using the bind technique, which sends an event object as an argument:

b3 = Button(parent, text="Press me as well")
b3.bind(<Button-1>, lambda ev : write("Pressed"))

FP and JavaScript

While I don't intend to go into detail on how FP is expressed in JavaScript it is important to realise that JavaScript is in fact heavily influenced by FP ideas. In fact, modern usage of JavaScript encourages the use of FP even more than OOP.

The key to FP in JavaScript is that function definitions can be written in a very similar style to lambda expressions. It just requires a tiny change to the style and syntax of a function definition. Consider this example from the Functions and Modules topic:

<script type="text/javascript">
var i, values;

function times(m) {
    var results = new Array();
    for (i = 1; i <= 12; i++) {
        results[i] = i * m;
        }
    return results;
}


// Use the function
values = times(8);

for (i=1;i<=12;i++){
    document.write(values[i] + "<br />");
    }
</script>

Notice that we defined the function by putting the name times after the keyword function. However, it turns out that JavaScript will also allow us to name the function via assignment, just like Python's lambda style above. Like this:

times = function(m) {
    var results = new Array();
    for (i = 1; i <= 12; i++) {
        results[i] = i * m;
        }
    return results;
}

So times is now a variable that holds a reference to a function object. You can call it exactly as you did before

values = times(8);

for (i=1;i<=12;i++){
    document.write(values[i] + "<br />");
    }

In fact function()) can be used to create anonymous functions too, just like lambda, except in Javacript there are no restrictions on the kinds of functions we create. They can be as long and complex as we want. This leads to a style of JavaScript programming that you will probably come across in web pages so I will give a very brief example here. It involves using JavaScript functions that take other functions as parameters. You might recall we saw that in our GUI programs, we called it a callback. Many JavaScript libraries use call backs, usually with the callback function being specified as the last parameter. Here is an example of a callback used in a simple web page, it is a complete example so you can load it and try it in your browser.

<html>
<head>
<title>Callback test</title>
<script type="text/javascript">
window.setTimeout( function() {
       document.write("Now you see me!");
     }, 3000);
</script>
</head>

<body>
<p>Wait for the timeout....<p>

</body>
</html>

Notice that the function executed by the timeout does not have a name, it is actually created as the first argument in the call to setTimeout itself. The delay of 3000ms is then added as a second argument. If you load it into your browser you will see the initial message being replaced by the timeout after 3 seconds.

That style of embedded function definition has become very common in the JavaScript community and is a pure FP style of coding. One of the most widely used JavaScript web libraries is JQuery and it comprises a whole host of functions that take other functions as parameters resulting in very functional style code.

Well, that really is that for Functional Programming. There are lots of other resources if you want to look deeper into it, some are listed below. VBScript does not directly support FP but can be used in a functional style by a determined programmer. The key being to structure your programs as expressions and not to allow side-effects to modify program variables.

Other resources

• There is an excellent article by David Mertz on the IBM web site about FP in Python. It goes into more detail about control structures and provides more detailed examples of the concept.
• Other languages support FP even better than Python. Examples include:: Lisp, Scheme, Haskell, ML and some others. The Haskell web site in particular includes a wealth of information about FP.
• There is also a newsgroup, comp.lang.functional where you can catch up on the latest happenings and find a useful FAQ.
• There are several book references to be found on the above reference sites. One classic book, which is not entirely about FP but does cover the principles well is Structure & Interpretation of Computer Programs by Abelman, Sussman and Sussman. This text focuses on Scheme, a version of Lisp favoured by many academics. My personal primary source has been the book The Haskell School of Expression by Paul Hudak which is, naturally enough, about Haskell.

If anyone else finds a good reference drop me an email via the link at the top of the page.