Functions with fun,
Part 1: Models of computation

This article marks the beginning of the series Functions with fun, in which I want to cover several fascinating aspects of the notion of a function, as encountered by computer scientists day by day. The title of the series is tongue in cheek, for you can't spell functions without fun anyway, and apart from that, most functions I know can't take a joke… as input.

The aim of Part 1 is to illustrate a simple, but important distinction between functions in programming (henceforth formal functions) and mathematical functions: a formal function is a recipe for computation, and a mathematical function isn't.

I will illustrate this point along the following problem statement:

Given any natural number n, what is the sum of the first n squares?

For instance, for n = 3, the first squares are 1 (1*1), 4 (2*2), and 9 (3*3), and their sum is 14.

Mathematical function

Using the notion of a function, the problem statement reads:

For any given natural number n, compute f(n) where f(n) = ∑i=1n i*i.

Here f is a function from the natural numbers into the natural numbers, as suggested by the naming of the variable n. The expression f(n) is read f of n or f applied to n, and it is referred to as a function application.

I said initially that a mathematical function does not specify a computation. This may sound strange, for the equation above is pretty instructive, no? It tells us to sum the values that we obtain from substituting i into i*i, going from i = 1 up to i = n.

But the equation that defines the function is not a part of the function.

Repeat after me: the equation that defines the function is not a part of the function.

Let me show you everything that's part of the function (abbreviated for lack of space):

{(1, 1), (2, 5), (3, 14), (4, 30), (5, 55), …}

Take a good look. Would you say that this thing computes anything, let alone the sum of the first squares? I wouldn't. That is because a function does nothing – it is rather us who has to compute the function! In fact, the most succinct wording for our problem statement is simply: compute f.

The function and the equation live in entirely different realms: f is a mathematical object, but neither are the equation nor the symbol f themselves – they are part of the metalanguage that we call mathematics. This language allows us to write f down with finitely many pencil strokes, even though f is actually infinite (that is why I abbreviated it above).

To make our life – and our language – more palatable, we take the liberty to say the function maps n to f(n), even though that sounds as if the function did anything.

In our example, it may be obvious from the defining equation how f can be computed. That is not the case in general. For instance, consider the function g from the reals into the reals with

g(x) = min{cos(x')  |  |x' - x| ≤ 0.5}.

Here we have to compute the minimum of a set, but we can't just look at every member, for the set is infinite. We have to use our knowledge of the cosine function to deduce that the minimum is either -1 (if an odd multiple of π is in the interval in question) or it lies at the boundaries of the interval. This logic, then, is easy to implement.

As a side note, not every mathematical function is computable. To make this statement rigorous enough for a proof, one has to define what is meant by to compute. At first, such a move may seem kind of arbitrary, for to compute is much less tangible than, say, function. But the established definition, which is based on the notion of a Turing machine, is widely believed to capture the intuitive concept of computation (Church-Turing thesis).

Alan Turing was not only the man who invented the model of computation that today bears his name, but also the first to come up with a function that is not computable. What he, a mathematician by profession, did, was computer science at its finest. Unfortunately, these days computer science is so mainstream in academia that work of Turing's caliber is to be expected from neither mathematicians nor computer scientists.

Python function

We can rephrase the problem statement by using a Python function instead of the mathematical function; then the function definition might look like this:

def f(n): return sum([ i * i for i in range(1, n + 1) ])

Don't let the n + 1 surprise you; it is because the interval is right-open.

Let me show you everything that's part of the function this time:

def, f, (, n, ), :, return, sum, (, [, i, *, i, for, i, in, range, (, 1, ,, n, +, 1, ), ], )

Yes, that's true: the function is merely a string of identifiers – such as n, f, i, and range – and symbols – such as parentheses, brackets, colon, comma; even def, return, in, and for are technically symbols. So how is this a recipe for computation?

The short answer is: the Python specification interpreter assigns a meaning to this string, in fact to any Python statement, and this meaning is the recipe.

Let me expand on that a little.

The model of computation that underlies Python assumes a processor that executes a sequence of instructions one by one, using an instruction pointer (IP, also program counter) to keep track of the next instruction in the sequence. For most instructions, the IP is merely advanced to the next place. One instruction, however, known as CALL, instructs the processor to stash the current value of the IP away and move the IP to a given point, continuing execution there until it arrives at a RETURN instruction, at which point the IP is restored to the old value. Additionally, upon RETURN, some value is made available for the subsequent instruction.

The meaning of a Python function is such a sequence of instructions. For instance, our very function is compiled by Python 2.7 into the following sequence, as determined via dis:

  1           0 LOAD_GLOBAL              0 (sum)
              3 BUILD_LIST               0
              6 LOAD_GLOBAL              1 (range)
              9 LOAD_CONST               1 (1)
             12 LOAD_FAST                0 (n)
             15 LOAD_CONST               1 (1)
             18 BINARY_ADD          
             19 CALL_FUNCTION            2
             22 GET_ITER            
        >>   23 FOR_ITER                16 (to 42)
             26 STORE_FAST               1 (i)
             29 LOAD_FAST                1 (i)
             32 LOAD_FAST                1 (i)
             35 BINARY_MULTIPLY     
             36 LIST_APPEND              2
             39 JUMP_ABSOLUTE           23
        >>   42 CALL_FUNCTION            1
             45 RETURN_VALUE        

CALL_FUNCTION (what I refer to as CALL) is used to enter a function and RETURN_VALUE (what I refer to as RETURN) to return (both execution and some value) to the call site; for instance, the call in line 19 enters range (supplying two arguments), and the call in line 42 enters sum (supplying one argument). It is because of this CALL-RETURN mechanism that the Python expression range(1, n + 1) may be referred to as a function call. For a mathematical function, however, this would not make sense at all, and we stick to function application.

Haskell function

In Haskell, we say

f n = sum [ i * i | i <- [1..n] ]

In Haskell, function application is denoted by f n instead of f(n), and a Haskell program is essentially a sequence of equations such as the above.

For the purposes of this article, we may imagine a grossly simplified model of computation for Haskell programs. This model is based on simplifying expressions, not unlike we all used to do in school, only that we say reduce instead of simplify. The processor reduces an expression by substituting equations until it obtains a special form of expression (termed weak-head normal form) that is generally deemed simple enough. For instance:

f 3
= sum [ i * i | i <- [1..3] ]
= 1 * 1 + sum [ i * i | i <- [2..3] ]
= 1 + sum [ i * i | i <- [2..3] ]
= 1 + 2 * 2 + sum [ i * i | i <- [3..3] ]
= 1 + 4 + sum [ i * i | i <- [3..3] ]
= 1 + 4 + 3 * 3 + sum [ i * i | i <- [] ]
= 1 + 4 + 9 + sum [ i * i | i <- [] ]
= 1 + 4 + 9 + sum []
= 1 + 4 + 9 + 0
= 1 + 4 + 9
= 1 + 13
= 14

In the second step, one might also reduce the list [1..3] instead of the sum:

sum [ i * i | i <- [1..3] ]
= sum [ i * i | i <- [1, 2, 3] ]

But that is not the way of the Haskell programmer, for Haskell adherents are lazy people, and who can tell whether the list [1, 2, 3] is going to be needed in the remaining computation?

Joking aside, whenever an expression admits several reductions, Haskell favors reduction at the outermost level. This strategy is referred to as call by need, or indeed lazy, because it avoids computing parts that aren't going to be used. The specifics are beyond the scope of this article, but if you are interested in learning more, I recommend the article on graph reduction at Wikibooks.

The lazy strategy enables programming with infinite data structures, which is one of Haskells key features and sources of elegance. On the other hand, it tends to produce rather long intermediate expressions, such as the monster 1 + 4 + 9 + sum [] above. Haskell programmers sometimes go to great lengths to manage this, if they don't want to keep the runtime garbage collector occupied. For example, the actual sum function does not produce monsters like the one above, but at the price that its implementation is not too straightforward.

In summary, unlike the mathematical functions, a formal function is a recipe for computation. Still I think it's a stretch to say that a function computes something. 😉

Matthias Büchse
last edited 2016-01-09

Imprint