Message Boards Message Boards

GROUPS:

Comparisons between procedural and functional programming

Posted 11 days ago
295 Views
|
10 Replies
|
10 Total Likes
|

I would like to know (for teaching purposes) of examples where the efficiency of functional programming is overwhelmingly greater than procedural programming.

10 Replies

By efficiency, do you mean the efficiency of the code (performance), or efficiency of the programmer (productivity)?

This has been a very long-standing debate in the programming languages community. There is no definitive answer to your question. Many who advocate for functional or declarative approaches emphasize that languages that adopt that model often are more productive once a programmer has some level of mastery for the language, and often the compilers/interpreters for those languages can achieve respectable performance. That is highly subjective though: it often is nuanced, since one needs to consider the person, what constitutes “mastery”, and the kind of problem they are trying to solve. Regarding performance, it’s also hard to say. On some problems, a functional language can compile to code that meets or exceeds hand tuned code in a classical imperative language. On other problems, the functional languages perform significantly worse. Again, like the productivity topic, it’s highly subjective. It also can be highly dependent on which language and which toolchain one considers.

One thing is for certain though: the functional vs non-functional language question is one of the easiest ways to start a flame war online. People get pretty passionate about their favorite tools. You are more likely to get anecdotal “data” and opinions than objective, generalizable answers to this kind of question.

Functional programming does not, in general, result in more efficient code. In fact, the opposite is true:

https://en.wikipedia.org/wiki/Functional_programming#Efficiency_issues

What you may be referring to is that functional style is a better fit for the Wolfram Language specifically. When there is a direct functional equivalent for a procedural construct in Mathematica, the functional version will typically be faster. One reason for this is that the functional way to solve a task is often higher level and conceptually closer to the task itself. The procedural way often requires spelling out specific details. There are often multiple ways to do this and not all of them are equally efficient. If the problem is expressed at a higher level, that gives Mathematica more leeway to choose an efficient way to do the computation.

Example:

Sum the elements of an array.

The procedural way is something like this, in pseudocode:

sum = 0
i = 0
while i < length(array):
    sum = sum + array[i]
    i = i+1

This is a very specific way to solve the summing problem. Spelling out all the steps constrains the order of operations. This can't easily be parallelized automatically.

However, if there is a single command to sum a list, that can have a more efficient multi-core implementation.

More generally, if we say that we want to reduce the array (Fold operation) with the + operator, knowing that + is associative, and knowing that evaluating + has no side effects, the problem can be straightforwardly and automatically parallelized. Associativity tells us that the order of operations does not matter, so we are not constrained to sequential evaluation.

Here's a related discussion:

https://mathematica.stackexchange.com/questions/134609/why-should-i-avoid-the-for-loop-in-mathematica

This is not about functional vs procedural, but about why it is better to avoid For in Mathematica. However, many of the things mentioned there illustrate the disadvantages of procedural approaches, or rather low-level approaches.


You might notice that I am not so much talking about functional vs procedural here, but about higher or lower level ways to express a concept. In inherently slow interpreted languages, such as the Wolfram Language, higher level expression typically results in better performance than lower level expression, simply because a low-level expression of an algorithm involves more (slow) interpreted steps, while the high-level expression can make use of highly optimized atomic operations. (In a low-level fast language often the opposite is true.)

I'd say that one reason why functional code is better in such languages is that functional code naturally produces a higher-level expression. Additionally, what Matthew said is that it is often close to the way one thinks.

Here are some concrete examples:

In[58]:= array = RandomInteger[10000, 5000000];

In[67]:= RepeatedTiming[
 sum = 0;
 i = 1;
 len = Length[array];
 While[i <= len,
  sum += array[[i]];
  i++
  ];
 sum
 ]
Out[67]= {4.860, 24992515511}

In[68]:= Fold[Plus, 0, array] // RepeatedTiming
Out[68]= {0.25, 24992515511}

In[69]:= Total[array] // RepeatedTiming
Out[69]= {0.0015, 24992515511}

The real reason for why the fast ones are fast is that they run fewer operations that are "atomic" in the Wolfram Language. I mean "atomic" in the sense that Total is a single operation whose internals are not accessible.

seems to me that functional programming code is easier to debug

How easy one coding style or the other is to debug depends on the background of the coder doing the debugging! If a programmer has spent years writing and debugging procedural coding but only a relatively short time writing functional code, then it may indeed be quicker for that programmer to debug code that is procedural, even though it is much longer (with lots of nested loops). I have seen that phenomenon in action, including by students coming to Mathematica after extensive experience with a procedural language. (I saw the same thing regarding array-oriented programming in APL and J vs. procedural programming in "conventional" languages.)

In general, using built-in Wolfram Language functions is going to be faster than rolling your own. This is particularly true for any type of for-next loop construction. The trick is to understand what you want to do in terms of these functions. The utility of Wolfram Language is that you can mix programming styles to match what you want to do.

Also, the "best" code is code where you have to write the least. I have seen this mantra for other languages (objective-c and Swift -- I am/was a Mac developer). The people writing the code behind Wolfram Language probably spend a lot more time understanding the deep details of the computer science behind algorithms, even if the code is eventually written in c or some other imperative language. In a sense, these people are your collaborators, and it makes sense to use the resource.

Just as there are beautiful and ugly proofs in Mathematics, there is beautiful and ugly code. I have written plenty of ugly code, but my experience is that beautiful code is generally more robust and easier to maintain (and understand), and it is worth a minor performance hit. It was worth the time and effort to rewrite the code to make it beautiful.

It also depends on what you are using the code for. For a single use application, the faster you can write good code, the better. For "production" code, robustness wins out over speed in almost all cases. It is only when you are pushing the envelope that execution speed is primary.

It is instructive to throw a glance at Rosetta Code: Pick a random programming task, and you will almost always find that Mathematica needs the shortest piece of code. And this is IMHO precisely because of the functional programming paradigm.

I greatly appreciate the various answers in response to my question. I am not a computer scientist and parts of those answers are well above my level of understanding. I have been a user of Mathematica for some time, and was in the process of preparing an introductory talk for students when I thought I might benefit from other users experience, looking for a few examples where the power of functional programming could be best shown, both in terms of operational power (i.e. speed of execution, import and export facilities, storing results - not only programs or notebooks, but also intermediate results) and of course the quality of the language and how easy it is to get programs up and running, testing code, combining text, code, images, etc. Far from me the idea of starting a flame war, as Matthew says. I am essentially a Mathematica-oriented practitioner, and rather than trying to promote or sell the advantages of the language (in which I firmly believe, perhaps because I practically know nothing else), I wish to provide clear-cut examples where functional programming is faster to write, easier to understand and very good in performance terms (and also, as Frank says, easier to debug) than procedural or imperative languages. All this said, I must add that reading the replies has been extremely useful and I sincerely thank you all. Szabolcs provides a lot of ideas and useful examples, although some of the references he gives were hard to understand. George's position, I fully agree with. And Henrik, thanks for the link to Rosetta Code: quite interesting.

Far from me the idea of starting a flame war

I think there's a very low chance of that happening on this forum :-) The topic is just not that controversial here.

Indeed! Very unlikely...

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract