Richard Lemmens website

Copyright:
PublicDomain
This text content and maps on this page are in the public domain. This means you are free to copy, adapt, share, distribute and even capitalize on it.

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 all the time. 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 has been slowly working its way into the mainstream for some time. This very short 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', which can be a building block of them. 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 imperative languages. The functional equivalent of "if x = 1 then A else B" may be written as:

        
(if (= x 1) A B)
        
    

where 'if' and '=' are of course functions themselves, 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.

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 typical functional program starts branching out into various function calls quite soon, increasing 'parallelizability' at the same rate.

One need not fear that one 'branch' / 'process' / 'thread' overwrites values of variables where another one is working on at the same time. Functional programs do not have variables like imperative programs do. This usually comes as a shock to many programmers, yet there is no need to panic. 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! Once you wrap your mind around this paradigm, functional programming actually shows itself to be cleaner and more intuitive than imperative programming.

Conclusion

This has been an ultra-short intoruction into functional programming. If you are interested in real world programs, there is much more to know and learn. There are several functional programming languages available. The most pure and well known are Haskell, Lisp and Scheme, though there are many more. Even XSLT turns out to be a functional language!
Several universities have published books and courses online and there are also programmers who have written introductions that are more extensive than this one. If you want not just to absorb the theory, but try your hands at functional programming, you can download a compiler or interpreter. Some are even available online, like http://rextester.com/l/common_lisp_online_compiler. Note that you will have to use 'special' functions like "print" in order to direct the results of function calls to your screen.