Functional Programming

What will we Cover?
  • The difference between Functional and more traditional programming styles
  • Python FP functions and techniques
  • Lambda functions
  • Short Circuit Boolean evaluation
  • Programs as expressions

In this topic we look at how Python can support yet another programming style: Functional Programming(FP). As with Recursion this is a genuinely advanced topic which you may wish to ignore for the present. Functional techniques do have some uses in day to day programming and the supporters of FP believe it to be a fundamentally better way to develop software.

What is Functional Programming?

Functional programming should not be confused with imperative (or procedural) programming. 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 very 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.

FP and Reliability
The reliability of Functional Programs comes in part from the very close relationship between FP constructs and formal specification languages such as Z or VDM. If a problem is specified in a formal language it is a fairly straightforward step to translate the specification into an FP language like Haskell. Of course if the original specification is wrong then the resultant program will merely accurately reflect the error!

This principle is known in computer science as "Garbage In, Garbage Out". The inherent difficulty of expressing system requirements in a concise and unambiguous manner remains one of the greatest challenges of software engineering.

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:

spam = ['pork','ham','spices']
numbers = [1,2,3,4,5]

def eggs(item): 
    return item

map(aFunction, aSequence)

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

L = map(eggs, spam)
print L

Results in a new list (in this case identical to spam) being returned in L.

We could have done the same thing by writing:

for i in spam:
   L.append(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 L

Alternatively we can write:

def isOdd(n): return (n%2 != 0)
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.

reduce(aFunction, aSequence)

The reduce function is a little less obvious in its intent. This function reduces a list to a single value by combining elements via a supplied function. For example we could sum the values of a list and return the total like this:

def add(i,j): return i+j
print reduce(add, numbers)

As before we could do this more conventionally like this:

res = 0
for i in range(len(numbers)): # use indexing
   res = res + numbers[i]
print res

While that produces the same result in this case, it is not always so straightforward. What reduce actually does is call the supplied function passing the first two members of the sequence and replaces them with the result. In other words a more accurate representation of reduce is like this:

def reduce(numbers):
  L = numbers[:] # make a copy of original
  while len(L) >= 2:
     i,j = L[0],L[1] # use tuple assignment
     L = [i+j] + L[2:]
  return L[0]

Once more we see the FP technique reducing the complexity of the code by avoiding the need for an indented block of code.

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 add function above could be rewritten as:

add = lambda i,j: i+j
And we can avoid the definition line completely by creating the lambda within the call to reduce, like so:
print reduce(lambda i,j:i+j, numbers)

Similarly we can rewrite our map and filter examples like so:

L = map(lambda i: i, spam)
print L
L = filter(lambda i: (i%2 != 0), numbers)
print L

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. Lets look at some practical examples.

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

>>> [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(i % 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:

>>> 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.

Short Circuit evaluation

Because Python uses short circuit evaluation of boolean expressions certain properties of these expressions can be exploited. 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:

>>>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 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 Pythons 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 recall that in the recursion topic we observed that recursion could be used to replace the loop construct. Thus combining these two effects 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 short circuit evaluation instead of if/else:

>>> factorial = lambda n: ( (n <= 1) and 1) or
...                       (factorial(n-1) * n)
>>> factorial(5)
120

And that really is all there is to it. It may not be quite so intelligible as the more conventional Python code but it does work and is a purely functional style function in that it is a pure expression.

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 practicing 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, reduce 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 rather than conventions 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:

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

Of course in this case we could have done the same thing by just assigning a default parameter value to write() and assigning write to the command value of the Button. However even here using the lambda form gives us the advantage that the single write() function can now be used for multiple buttons just by passing a different string from the lambda. Thus we can add a second button:

b2 = Button(parent, text="Or Me", 
           command = lambda : write("So did I!"))
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"))

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. Neither VBScript nor JavaScript directly support FP but both can be used in a functional style by a determined programmer. The key features being to structure your programs as expressions and not to allow side-effects to modify program variables.

Other resources

If anyone else finds a good reference drop me an email via the link below.

Things to Remember
  • Functional programs are pure expressions
  • Python provides map, filter and reduce as well as list comprehensions to support FP style programming
  • lambda expressions are anonymous (ie unnamed) blocks of code that can be assigned to variables or used as functions
  • Boolean expressions are evaluated only as far as necessary to ensure the result, which fact enables them to be used as control structures
  • By combining the FP features of Python with recursion it is possible (but usually not advisable) to write almost any function in an FP style in Python.


Previous Next Contents
 

If you have any questions or feedback on this page send me mail at: alan.gauld@btinternet.com