Why are functional programs considered slower than procedural counterparts asymptotically, if the opposite appears true?

Question

I've read and been told way too many times that functional algorithms and data structures have an obligatory O(log(N)) slowdown in respect to their procedural (for-loop/array-based) counterparts. But, after thinking about it, I don't see how that could be true. Mind this for loop

int arbitrary_sum(int* arr, int size, int n){ 
    int sum = 0;
    for (int i=0; i<n; ++i) 
         sum += arr[(int)(random()*size)];
    return sum; 
} 

That sums N random elements of an array. You'd saiy this is O(N), but that is taking in account array indexing is O(1), which can't be true. For simplicity, assume memory cells are stored linearly. Since that chip must occupy a linear amount of space, and since a signal requires a linear amount of time to travel given space, then it is obvious an indexing operation takes at least O(S) time to complete. That is the time a signal takes to go from the CPU to the memory cell and come back. This means that the complexity of a for-loop is O(N*S), where N is the number of interactions and S is the size of the state that is visible on that for-loop. This way, the textbook int sum(int* array, int size) function, for example, can't be O(N) - it is, actually, O(N^2), for any reasonable implementation of for, as far as physical laws apply. Using layers of caches we are able to shrink the initial S factor and amend this effects, but that has a runtime cost and doesn't change the asymptotics. Now, lets look at the functional counterpart. The most obvious way to sum a container of numbers functionally is folding over a list. For simplicity, lets examine the sum of 0 to 4 using church lists:

((λc.(λn.(c 0 (c 1 (c 2 (c 3 (c 4 n))))))) + 0)

We can optimally evaluate a λ program is using an interaction net, so, lets encode that program as one:

Now, let me propose a new model of computer. Instead of separating the CPU and the memory, we instead store a simplistic computing unit together with each memory cell, each one capable of sending/receiving signals and processing local reductions. On this system, we can reduce the ((λ ...list...) +) abstraction by sending parallel signals from the topmost λ node to each corresponding application. We can also reduce the outermost abstraction by sending 0 to the last application of the list. All that takes no more than 2 runs through the list, and the result is:

From here on, it is clear that the rest of the computation will take a linear amount of time to complete. After all, each redex is local, and the redexes are reduced one by one, producing the result from the tail of the list up to its head.

Under this point of view, it seems to me that functional programs are actually asymptotically faster than imperative counterparts, so, why is the opposite considered the truth?

Answer 1

Without fully answering your question, I would like to answer it at least partially by remarking that computation cost can be evaluated only with respect to an abstract model of computation.

If you want to use two different models, for two different programs, than you have to determine the complexity of reducing each model to the other, in order to have a meaningful comparison.

Another point is that physics does not well qualify as a computation model for several reasons:

• it is not clear enough what physics allows and does not allow regarding of computation, computation speed, storage, etc.

• computation models are defined with various assumptions about unit operations and their costs, and about infinity and asymptotics, which are not meant to be a reflection of reality, but only an approximation of reality intended to facilitate the analysis of some phenomena, whether abstract or physical.

  This is why Turing machines are more appropriate than finite automata theory to analyse the behavior of devices with very large, though still finite memory. For example, the powerset construction of DFA may exist in theory when the memory is finite, however big, but may also quickly exceed the capacity of our limited universe, thus hardly making any sense.

Considering your first example about the "physical" time cost of executing a for loop on an array of size $n$. If we are to do asymptotic physics, we have to do it right, or at least as right as current knowledge in physics will allow. Due to universe expansion, the part of the universe that we can ever hope to access is bounded by a radius of some $z$ zillion light-years (corresponding to a distance at which the expansion speed relative to us equals the speed of light), so that nothing relevant to us can be further away.

You can see that as good news: distances being bounded, access is asymptotically in constant time, so that the classically accepted cost analysis does hold, despite your remarks.

Of course, since you still want to have arbitrarily large memory, you have to assume that this finite sphere can hold infinitely many bits of information ... which I fear physicists cannot really tell. But let's be optimistic.

Another way to do away with your remark is to consider that the access time is small enough that it will not really impact the computing time, unless you have specific reasons to think otherwise.

Some high speed computer do have to be programmed taking into account physical distances, in particular to memory. But why should functional program be exempted from such physical limitations. How much computational capacity do you store with each cell? Instead of the $+$ operator, can you pass any arbitrarily complex fuction as parameter and still have it reduced locally in each memory cell.

Or to put it differently, what prevents an imperative program from taking advantage of an architecture that has computing power in each memory cell. This is remindful of various specialized architectures, such as vector processors.