The essence of (functional) programming

Functional programming seems to be a hotly debated issue among some programmers. On the one side there are the more academic, computer sciency proponents, who claim that all programming should be functional, since it supposedly reduces bugs and you can reason about the program and do all kind of fancy formal proofs. These proponents also created several purely functional languages to show the world how awesome this way of programming is (including Miranda, OCamML and Haskell). On the other side there are the self-proclaimedly more pragmatic  programmers who bash functional programming as being unusable for any kind of reasonable work in the real world – work that is actually ending up being used by real users and not just as unintelligible papers in the ivory tower.

Who is right? I don’t know. I find the whole discussion moot, so I won’t try to take a side, since I both feel firmly grounded in the real programming world and still use concepts from the functional programming world.

For the sake of a better understanding what the whole thing, in my view, is about, I will introduce a different nomenclature for common programming terms. It was first used for APL-like languages and was introduced originally by Kenneth Iverson – a Turing award winner, best known for his contributions to mathematical notation and programming language theory. His paper Notation as a tool of thought  (Comm. ACM 23 (8): 444–465) is worth reading several times.

A variable (be it a simple one that holds a single value like a number or a character or composite one, like a class or a structure, array, string etc.) is called a noun, since it describes something and holds information thereof. An operator can combine nouns, usually quite clumsily for everything different from elementary arithmetic operations. Examples of operators would include the usual suspects like (+, -, *, /, %, but also other invented symbols like . (concatenation) etc.).

Functions or methods are types, which act on data or nouns, therefore they are called actions or verbs. Opposed to the static nouns, verbs define the dynamics of the program. Operators and verbs can become more powerful by combining, and thus, specializing them with adverbs – those are higher order functions, that is functions which take functions as arguments. Examples would include an APL style reduce, combining the operator add (+) with the over-operator (/), to create +/, which is interpreted as plus-reduce or simply sum.

The power of any computation, be it in the real world or in the ivory tower, comes from defining a proper data structure for the problem at hand and possibly a small set of (helper) variables . The task is then to build a set of actions (i.e. verbs) on this data structure to access and manipulate it. This can be called the building up of a vocabulary specific to this particular data structure. You build, thus, a vocabulary to accurately describe and solve the problem at hand. The vocabulary consists mostly of verbs operating on one maybe two data structures, according to the maxim

It is better to have 100 functions operate on one data structure than 10 functions on 10 data structures.

Alan Perlis

Those hypothetical 100 functions/verbs can be composed and combined together in many different ways, since they all operate on the same data structure. Mixing 10 functions on 10 data structures does not really work very efficiently, since each of them was defined only for their particular data structure. It is the same idea as thinking in terms of higher abstractions that helps to apply those functions to much broader, general problems.

Hence, the vocabulary becomes more and more sophisticated and powerful with every layer of verbs wrapped around the data structure. The verbs tell you what to do with the data. Every layer becomes more specialized and powerful, since it draws from the power of the bottom layers.

The main claim of functional programming is essentially that state, i.e. data stored in global variables, is very bad, both for humans writing, reading and trying to understand the code but also for computers, since it hinders free combination and reproducibility. If the code contains no state, the compiler can automatically precalculate results of functions and store the cached values instead of calling those functions repeatedly, it can change the order of execution and reshuffle computations if this makes sense and it can parallelize the code without you having to do anything. You could even swap certain parts of your code with new code while the program is running – provided again, that there is no state. If there is state, however, all of these marvelous things a compiler could do will cease to work because the compiler does not know if a function call with the same arguments will actually give the same results, thus no caching, no implicit parallelism and certainly no hot swapping of code.

This is, of course, rather obvious: if a program has state and state variables then the outcome of the program does not only depend on the program flow but also on the state of these variables. Thus, a logical conclusion for any sane programmer is to avoid state whenever there is another way to do it. So far, I believe, everybody who has tried to debug a sufficiently complex program agrees. However, the claims of some of the proponents of functional programming go further: in purely functional languages state is completely forbidden. This makes certain things in the real programming world at best awkward and at worst impossible to achieve. State is unfortunately a fact of life in any real world program. Communication, I/O, GUI, etc. depend on state.

However, there is some sanity in reducing state, whenever possible: (state) variables should be for computers only: if at all, only the lowest level of actions should directly access the variables holding the data. All higher level actions should be defined, whenever possible, in terms of their lower level actions (verbs).

Actions and verbs are for humans to write and understand: the program flow is expressed in terms of the highest level actions, without ever having to access any low level actions or even state variables. This is the bottom-up approach used often in functional programming.

Let the compiler shuffle variables as it sees fit. Let the compiler optimize and introduce temporary variables to cache results. You should concentrate on the actions and flows of the program. Occupying yourself with the nitty-gritty ugliness of variables and states down to the lowest level is unhealthy and mostly unproductive. It is an example of premature optimization, which is said to be the root of all evil.

Let the compiler shuffle the variables!

Your task as a mature programmer is to build up a vocabulary for the particular purpose such that the program can be expressed with this particular vocabulary of actions (bottom-up). Conversely, thinking from the top-level, you divide the program into sub-tasks (top-down) and then combine the two approaches.

The cool thing about functions/actions is that they can be arbitrarily nested and combined. Try this with variables, and soon you will hit a wall – of possibilities and complexity. The other cool thing is that you should think in terms of expressions and not statements. Statements end. The C/Algol-family of languages is infamous for making this distinction. It kills a lot of the expressiveness that you could otherwise also have in those languages. Expressions can be nested as deeply as you want, until the program is essentially one huge expression.

Let the compiler unfold code as it sees fit and reason about it – this is something you should not be concerned at all.

The profiler is your friend

In modern programming projects, time is the most crucial and relevant factor. Computational time is practically irrelevant, apart from some extreme examples. Therefore don’t optimize prematurely. Profiling is done on the function level – so use a lot of functions. Your profiler is your friend and tells you nicely where the program spends most of its time.

Functional programming is more like a tool of thought and of the craft than a rigid set of rules that must be built-in on the programming language level to ensure that the (dumb) programmer obeys the rules. This is why I’m not a huge friend of programming languages that enforce a particular, albeit sometimes very useful paradigm on the programmer. Programmers generally don’t feel happy to be chained on a particular paradigm (despite programming language creators trying to enforce it again and again).  This is why purely functional programming languages are not overly popular – it is the general purpose, multi-paradigm languages like C/C++, Java, PHP, Python that provide a large number of libraries and the freedom to program in any way you like that get the most traction. The most popular languages that have built-in support for functional programming (essentially they make no distinction between statements and expressions and support higher order functions easily) are not surprisingly Lisp, Scheme, Ruby and R. They are again general purpose multi-paradigm languages with a sufficiently large number of libraries. However, the concepts of functional programming can be used in every programming language that supports functions (obviously).

So what about the glorious claims of functional programming that it reduces bugs and you can do formal proofs on the code?

Well, in principle those claims are fully correct. However, in order to actually be able to reason and prove your code correct all of it must be written in a purely functional style. And this is the biggest obstacle: you mustn’t use a single state variable or all the claims go out the window. As soon as you introduce any real-world impurity, the wonderful formal reasoning stops working. I have yet to see a useful and non-trivial real world program that is written in a purely functional style. The closest thing I have seen, which I find rather impressive, is a tiling X Windows manager written in Haskell.

As for the the bug reduction: You don’t have to write everything in a purely functional style to profit from a reduced bug count. The less variables you use, in particular the less variables that hold state, the easier it is to read the code. If your code is essentially a series of functional applications instead of a spaghetti code mess with lots of temporary variables, you will easily find that you will be much more productive, the code has generally less bugs and if you find one, you can easily catch it, because your code is so much more readable.

In conclusion I believe that the idea of applying concepts of functional programming saves you from a lot of headaches, leaves you with more readable and maintainable code and makes you think on a more abstract level. Pure functional programming however is mostly incompatible with the real world, but you don’t need to go to that extreme a level to get the most profits of decreased bug counts and better readability and  maintainability from it. Fortunately for all of us, the concepts of functional programming can be applied in every modern programming language.

One thought on “The essence of (functional) programming

  1. Pingback: States and complexity in programming – why functional programming helps to improve your code | Heuristos

Leave a Reply

Your email address will not be published. Required fields are marked *

Current month ye@r day *