Functional Programming with Python

By Pramode C.E.

Programs written in a functional programming language (like say Scheme) mirror the structure of mathematical expressions; math expressions are composed of strings of functions, each one computing a value and producing absolutely no side effects. The same function, called with the same arguments, yields the same result whatever be the context in which it is called. There is elegance in structuring code in this way (and also, a certain amount of simplicity). The Python programming language has all the features necessary to make it good at functional programming (FP). In this article, we examine a few interesting FP ideas like higher order functions, closures, lambda, currying, etc. from the `Pythonic' point of view!

What is Functional Programming?

The functions we write as part of our programs are only superficially similar to mathematical functions. Let's say we write a function:

int current_balance = 100;
int withdraw(int w)
{
   current_balance = current_balance - w;
   return current_balance;
}

An invocation of `withdraw(10)' results in a value of 90 being returned. A subsequent invocation of `withdraw(10)' returns 80. Had `withdraw' been a `pure' mathematical function, it would have returned the same result for both invocations as the value being passed is the same. Our program basically `remembers' the earlier invocations (it has `state') and returns a new value every time. A mathematical equation like:

y = f(a) + g(b) + f(a)

has the nice property that it can be reduced to:

y = 2*f(a) + g(b)

It is virtually impossible for us to perform such reductions on computer programs which are written as collections of functions which modify global variables. Reasoning about the correctness of computer programs becomes more of an activity of exploring all kinds of what-if situations rather than generating mathematical proofs.

The `assignment' operator creates its share of problems. Let's look at a simple loop to compute the factorial:

/* Compute factorial of `n' */
int f = 1, n = 5;
while (n > 0) {
   f = f * n;
   n = n - 1;
}
return f;

A common mistake which we make is interchanging the two statements within the body of the loop. The assignment operator, by changing the value assigned to symbols, forces us to be careful about the order in which we perform each and every action in our program.

The functional programming paradigm encourages us to structure our programs as collections of `pure' functions which do not have any global state and which do not make use of the assignment operator (note that this is not possible in all situations; a banking system will surely have to `remember' lots of stuff). Functional programmers use recursive invocation of functions (iteration is considered to be a special case of recursion and specific iteration constructs like the `while' or `for' loop may be absent altogether) to program repetitive behaviour. Functions are considered `first class', ie, they can be passed to other functions and returned from other functions thereby facilitating the creation of what are called `higher order functions' - a powerful idea which can capture concisely many complex computational patterns when combined with the idea of `closures'.

Expressing recursion

There is nothing magical about defining recursive functions in Python. Here is the classical factorial written as a Python function:

def fact(n):
   if (n == 0): return 1
   return n * fact(n - 1)

Functions as first class objects

Let's define two functions at the interactive Python prompt and try some experiments:

>>>
>>>def sqr(x): return x*x
...
>>>def cube(x): return x*x*x
...
>>>sqr
<function sqr at 0x402ba10c>
>>>a = [sqr, cube]
>>>a[0](2)
>>>def compose(f, g): return f(g(x))
...
>>>compose(sqr, cube, 2)
64
>>>

We first store the two functions in an array and then invoke `sqr' as `a[0][2]'. We then define a function called `compose' and call it with the two functions `sqr' and `cube' as arguments. Note the absence of any special notation; we are manipulating functions as if they were objects like arrays and numbers.

The power of the higher order function

Structure and Interpretation of Computer Programs, the legendary `wizard book' by Abelson and Sussman, has a detailed description of the utility of higher order functions. A `function' (or a subroutine, subprogram, procedure) is considered to be a mechanism for capturing patterns. If we have many statements of the form

a*a*a
b*b*b
c*c*c
.....

we can think of defining a function called `cube' which captures the essence of the pattern and gives it a name. The ability to pass functions as arguments to functions greatly broadens the scope of this `pattern capturing' mechanism. Let's examine a simple function, `sum':

def sum(a, b):
   if (a > b): return 0
   else: return a + sum(a+1, b)

The function sums all numbers from `a' to `b'. We try to broaden the scope of the function by making it capable of manipulating arbitrary sequences, like say:

1/(1*3) + 1/(5*7) + 1/(9*11) + ...

We note that the above sequence and a sequence like:

1 + 2 + 3 + 4 + ...

are similar in the sense that both are `summations'. We visualize a quantity `a' changing from 1 to 2, 2 to 3 and so on. The change from 1 to 2 can be captured by means of a function (a simple `add 1' function). In the case of the first series, this quantity is seen to be changing from 1 to 5, 5 to 9, 9 to 11 and so on. Here, the change can be captured by an `add 4' function. Another small problem. The terms of the series are not the numbers 1, 5, 9, 11 etc but the numbers 1/(1*3), 1/(5*7)... But then, this transformation also can be expressed in terms of a function! These observations result in the formulation of the function `sigma':

def sigma(term, a, next, b):
   if(a > b): return 0
   return term(a) + sigma(term, next(a), next, b)

And here's how we call `sigma' to compute the sum of the sequence:

1/(1*3) + 1/(5*7) + 1/(9*11) + ...

We shall define two functions:

def term(x): return 1.0/(x * (x+2))
def next(x): return x + 4

and call:

sigma(term, 1, next, 1000)

That should do the trick! Now it becomes possible for us to sum any sequence provided we define two auxiliary functions.

That's not the end of the story. We should think of generalizing `sigma'. We note that `sigma' is simply `combining' terms of a sequence using the combination function `add'. Why not have a general procedure which will combine the terms of a series according to a user defined function which is passed as an argument? Readers should try this as an exercise!

Using `lambda'

We shall try the following at the Python prompt:

>>>
>>>lambda x: x+4
<function <lambda;> at 0x402ba25c>
>>>f = lambda x: x+4
>>>f(3)
7
>>>

The lambda keyword is used for creating anonymous functions. The body of a lambda should be composed of simple expressions only. In the above example, we use lambda to create a function which accepts an argument and returns it after adding four. We should think of using `lambda' whenever we need to define a function just for the purpose of passing it over to another function. As an example:

>>>
>>>map(lambda x:x*x, [1,3,7,9])
[1, 9, 49, 81]
>>>filter(lambda x: x%2 == 0, range(10))
[0, 2, 4, 6, 8]
>>>

The map function accepts a function and a list as argument and returns the list obtained by applying the function on each element of the original list. Filter is similar; it returns a list composed of only those elements for which the function returns true.

Closures

Python allows function definitions to be nested.

def add(x):
   return lambda(y): x+y

Invoking add(3) will result in a function of one argument being returned. Now, this function has a peculiar property - it's capable of remembering the environment in which it was created. The value of `x' in the body of the function is the value supplied when `add' was invoked. You call such functions `closures'. Invoking add(3)(4) will result in this function executing with value of x = 3 and y = 4.

You might have noticed something interesting here. Instead of defining a function `add' which accepts two arguments, we were able to get the same effect by nesting a one-argument function within another one argument function. It's possible to take this to any level:

def add3(x):
   return lambda y: lambda z: x+y+z

Now, we can call `add3(1)(2)(3)'! This idea goes by the name `currying' in the FP community.

Let's try to write a function for doing `numerical' differentiation.

def differentiate(f):
   return lambda x: (f(x+0.001) - f(x))/0.001

The function can be tested out as follows:

>>>
>>>p = differentiate(cube)
>>>p(2)
12
>>>

Calling differentiate with argument `cube' will result in a one-argument function being returned which remembers the value of `f' to be equal to `cube'. Now, calling this function with argument say 2 will result in the evaluation of:

(cube(2+0.001) - cube(2))/0.001

A bit more lambda fun

The idea of functional programming being `computing with functions' can be taken to its extreme; one might even go so far as to say that EVERYTHING (yes, I mean even things like integers, truth, falsehood, literally EVERYTHING) can be expressed as functions. A really smart guy called Alonzo Church had figured out how to do this and produced a remarkable piece of work called the `Lambda Calculus'. We shall not go into the details of Church's work - but will simply look at a few functions just for the fun of it.

Let's have our own definitions for `true' and `false':

true = lambda x, y: x
false = lambda x, y: y
iff = lambda p, x, y: p(x, y)

We define true as a function which accepts two arguments and returns the first one; false returns the second argument. The logic of this definition becomes clear when we look at the context where we make use of `true' and `false'; calling iff(true, 2, 3) will result in the number 2 being returned and calling iff(false, 2, 3) will result in 3 being returned.

The claim is that all computational constructs can be defined in terms of lambda. Let's try building up an elementary data structure, a `pair'.

pair = lambda x, y: lambda f: f(x, y)

The definition is a bit tricky: a `pair' is a function which accepts two arguments and returns another function; this time, a function which accepts one argument and applies that on x and y. The idea becomes clear when we define two other functions:

first = lambda p: p(true)
second = lambda p: p(false)

Now, we turn a bit philosophical and ask the question: "what is a pair?" The answer is, "P is a pair of two objects x and y if there are two functions `first' and `second' such that first(P) is x and second(P) is y." Let's now try:

>>>
>>>P=pair(2,3)
>>>first(P)
2
>>>second(P)
3
>>>

And that's magic! Think about it!

Conclusion and Further Reading

If you wish to read the original Scheme version of the Python functions presented in this document, grab a copy of SICP; you are sure to spend many an enjoyable hour reading it. If you are looking for a cool Python project to do in the ample free time which you have, translate SICP into Python! If you wish to read some brain exploding lambda stuff, go to this site by Mark-Jason Dominus. You might also like to read this document written by John Hughes which explains why functional programming is important.

 

---

I am an instructor working for IC Software in Kerala, India. I would have loved becoming an organic chemist, but I do the second best thing possible, which is play with Linux and teach programming!