Richard Lemmens website

# Functional programming

The vast majority of popular programming languages are imperative, i.e. they consist of a sequence of 'statements' that are executed more or less sequentially, meanwhile changing the program's state. Of course there is branching with if-then-else statements, there are loops and subroutines, but in essence those programs are sequences of statements. This is a paradigm that almost all programmers are infinitely familiar with. Some juniors actually think that that is how every programming language looks like. However there are alternatives, and interesting ones too.
One of the most prominent of those is functional programming, based on the theory of lambda calculus. Included in serious computer science curricula for decades because of its close relationship with mathematics, it is now slowly working its way into the mainstream. This article shows some basic features of function programming for novices. More extensive material can be found on other websites and in books. Throughout the text the syntax of Lisp, the mother of all functional programming languages, is used.

### Functions

Central to functional programming is the concept of a function. These are like mathematical functions, which take a handful of parameters as input, do their work and finally produce output. A simple example can be drawn from arithmetic, like the 'add' function that adds two numbers together. It takes two numbers as input, adds them up and produces the sum as output. It is common to use infix notation to write sums, like "1 + 1 = 2", though a mathematician may well want to use prefix notation and write something like "add(1, 1) = 2". In Lisp the parentheses are put on the outside and the commas are omitted, so the expression is written as:

```    		```
(+ 1 1)
```
```

still resulting in 2 of course.

### Functions calling functions

Full functional programs tend to be a lot more complex, and of course also more capable, than a small simple function like 'add'. They achieve this not by adding more functions sequentially, but by subdividing the work into more functions, without specifying an order of execution. For example a combination of an addition and a multiplication such as "1 * 2 + 3 * 4" may be written as:

```    		```
(+ (* 1 2) (* 3 4))
```
```

A fundamental observation from this example is that the arguments of a 'higher order' function can be function calls themselves. Likewise, the output of functions can be functions too. Some modern iterative programmings languages like Python and C# have also added this concept. But with functional languages this has been a feature right from the start, because this is the way that a functional program is structured: one big 'main' function that breaks down in smaller functions, which may break further down, etcetera.
Keen observers will note that such a program can be presented not only with text, but graphically as a tree. In such a tree each function call is a node and its parameters are the children of the node. Again the example from above, as a tree with indentation representing the layers:

```    		```
+
*
1
2
*
3
4
```
```

### Control flow and recursion

There are no sequences of statements in functions, but branches are just as common as in imperatiev languages. The functional equivalent of "if x = 1 then A else B" may be written as:

```    		```
(if (= x 1) A B)
```
```

where 'if' is of course a function itself, with boolean instead of numeric output.

Loops are achieved through recursion, which is another fundamental concept in functional programming. In recursion a function calls itself, though with different parameter values than in the original call. A first function call can trigger a second, a third and so on until an end condition is met, which terminates the recursion, preventing it from going on forever. Here is an example of a function that can multiply two positive integer values:

```    		```
(defun multiply (x y) (if (= y 1) x (+ x (multiply x (- y 1)) ) ) )
```
```

This function recursively calls itself, each time with a value for y that is 1 lower than the previous one. When y reaches a value of 1, the recursion ends and x is returned. On the way back up trough the recursion tree, the result of the underlying function call is added to x and that result is passed to the function call that triggered the current one. The result is y - 1 times adding x to itself, or more commonly known as x * y.

### Mind bending

Many programmers who are used to iterative programming languages are shocked to find that there is no such things as variables, i.e. memory cells whose value can change over time, in functional programming. All 'variables' are either input values set to fixed values when the program starts, constants or function calls. There is simply no need for variables!

### Parallelism

Functional programs are very easy to 'parallelize'. When a function calls other functions, it must wait until those other function calls are resolved. But the order in which that is done is irrelevant. And as there are no global variables, those function calls are effectively independent of each other, which means they can be executed in parallel. A typcial functional program starts branching out into various function calls quite soon, increasing 'parallelizability' at the same rate.