Unfortunately, some time has passed again since the last post. In the last post I wrote something about the history of functional and imperative programming. This one is now to deal with the, compared to imperative programming, different way of thinking. The source code examples shown here are based on Java for the imperative examples and Haskell for the functional examples. I will try to use only functions available in the language standard and not library functions.

In imperative programming, one describes in detail the steps that must be performed by the computer to accomplish the task. In contrast, functional programming does not describe HOW something is to be computed, but WHAT. Not for nothing functional programming languages belong to the declarative programming languages.

By the functions, just as in mathematics, the “world” is represented or defined in the actual state. In general, functional programming with its terminology and concepts is very strongly based on mathematics, which makes it not easy for not math affine humans. If one managed to understand the concepts the large advantage is that one can rely on the mathematical background of these concepts. Thus, the correctness of a program can then be proven with “relatively” little effort, at least compared to imperative programs.

While most imperative algorithms are based on the manipulation of memory areas (called variables), the functional algorithms can be implemented by term substitution. To illustrate this difference, the following example of computation of the sum of 1 to n will server.

Let’s look at the imperative example first:

int computeSumTill(int n) {
  int result = 0;
  for (int counter = 1; counter <= n; counter++) {
    result += counter;
  }
  return result;
}

When executing the upper function, the variables result and counter are changed again and again during each loop pass. For n=3 it looks like this:

-- Initialization
result := 0
counter := 1
-- 1. Loop pass
result := 1
counter := 2
-- 2. Loop pass
result := 3
counter := 3
-- 3. Loop pass
result := 6
counter := 4

By comparison, a function for this computation would look like this:

computeSumTill :: Int -> Int
computeSumTill 0 = 0
computeSumTill n = n + computeSumTill (n-1)

When Haskell is executed, term substitution is now applied and only at the end something is computed:

computeSumTill 3
-- Apply computeSumTill
3 + computeSumTill (3-1)
-- Apply (-)
3 + computeSumTill 2
-- Apply computeSumTill
3 + 2 + computeSumTill (2-1)
-- Apply (-)
3 + 2 + computeSumTill 1
-- Apply computeSumTill
3 + 2 + 1 + computeSumTill (1-1)
-- Apply (-)
3 + 2 + 1 + computeSumTill 0
-- Apply computeSumTill
3 + 2 + 1 + 0
-- Apply (+)
5 + 1 + 0
-- Apply (+)
6 + 0
-- Apply (+)
6

You can already see the different approaches in this simple example. In the imperative example a loop is used and in the functional example recursion. Of course, recursion is also possible in imperative languages, but it is uncommon, since it naturally involves certain dangers that do not disappear even in Haskell. But that is a separate topic, which I hope to take up again sometime.

But one can also see the different way of interpretation. While in the imperative language the variables are changed again and again, with the functional language first the entire formula is built up by term substitution, in order to compute it afterwards. One could also say that the functional approach corresponds to the manual approach. Term substitution is in fact what we also do manually when solving an equation.