Functional versus procedural programming

The "functional programming" style that I describe here is not the purist's version of functional programming, where assignment of results to variables does not occur. I have a freer interpretation of the term "functional programming" which is explained by the physical analogy below.

The relationship between functional and procedural programming is succinctly explained by using a physical analogy. Space-time is 4-dimensional and it contains a copy of the 3 spatial dimensions for each and every possible time instant. At each time instant there will be fields recorded throughout the 3-dimensional space, and the evolution of these fields forwards to the next time instant will be governed by whatever laws apply to those fields.

The two styles of programming may then be described thus:

1. Functional programming is the evolution of the fields so that they progressively fill up successive 3-dimensional slices of the 4-dimensional space-time.
2. Procedural programming is the same as functional programming except that at each time instant the 3-dimensional slice containing the evolved copy of the fields overwites the 3-dimensional slice containing the old copy of the fields.

Thus procedural programming reuses storage whereas functional programming does not. A procedural program operates on the state of the world and updates it in place, whereas functional programming makes a copy which it then updates.

A key advantage of functional programming is that the causal chain of updates is laid out explicitly so that an "audit trail" of what has happened during the updates is recorded, whereas in procedural programming this record is overwritten. This means that when a functional program needs to make use of the state of a particular variable at a particular point in time then that state is guaranteed to be available, whereas in a procedural program there is always the danger that the value has been overwritten.

In Mathematica a concrete example of this is as follows:

negativeQ[x_]:=x<0;
f[0]=0;
g[0]=1;
f[t_?negativeQ]:=0;
g[t_?negativeQ]:=0;
f[t_]:=f[t-1]-g[t-1];
g[t_]:=g[t-1]-f[t-2];

where the state of the world at time t is {f[t],g[t]} which depends on the state at the previous two time instants t-1 and t-2. This dependence on various past states is handled completely automatically in functional programming, whereas in procedural programming the overwriting of past states must be carefully buffered in order to ensure that the state at the previous two time instant is available. Clearly, this is a trivial example, but the principle generalises to cases where functional programming is enormously more convenient than procedural programming.

Excessive memory usage by functional programs can be avoided by adopting two strategies:

1. Do as much computation as possible between each time step, because intermediate results that are not assigned to variables are not permanently recorded. The garbage collector will take care of this temporary memory usage.
2. Explicitly erase variables that are no longer required. In effect this creates blank areas in the "audit trail" where parts of the causal chain of updates are "shredded".

Functional programming is a very natural way of writing out discretised evolution equations (as illustrated above). For instance, cellular automata have a completely natural formulation in the functional programming style. More generally, any discretised version of a differential equation can be written out easily in the functional programming style. The key advantage over procedural programming is that you don't need to worry about buffering the past states of the world because they are always available, at least until you erase them.

Functional programming should come naturally to anyone who has been exposed to the space-time way of thinking in physics, where the physicist surveys the whole 4-dimensional record of the world, and thinks in terms of complete histories (i.e. "audit trails").