Wednesday, January 31, 2007

Is Functional Programming Feasible?

I find Functional Programming quite natural. Recursion is trivial, and higher order functions are not such a big deal. Except I have forgotten how long it took me to fully grasp these concepts. I forgot that the first time I saw map and fold in action, I had a hard time understanding what the program actually did.

I often read that functional programs are easier to read, maintain, and debug. I also hear the same about imperative programs (Object Oriented as well as simply procedural ones). Currently, I am not sure which side is right. Personally, if I am given a powerful functional language, I will program faster and cleaner. End of discussion. But what about my fellow programmers? Will they do any good? Do they think they can do any good? I think there is some kind of trade-of: functional programs often use more powerful abstractions than imperative ones. The result is more concise code. On one hand, that mean less code to write, maintain, and debug. On the other hand, each piece of code carries more meaning, and is therefore likely to be more difficult to write, maintain, and debug. My point is to find which is more practical. By "practical", I mean usable in the "real world", where the big money is.

Let's start with an overview of the abstractions used by the imperative, procedural programming style, that the functional style lack.

Side effect. A side effect is something that defines a before, and an after. For example, printing "Hello World!" on the screen is a side effect: before, nothing is displayed. After, the message is visible on the screen. The state of the screen has been modified. (Note that side effects are ill-named : more often than not, we mean them).

Flow. An imperative program do things, one at a time, in a precise given order. The first thing to do comes first, the second comes second, an so on. When the program has to do things repeatedly, it is still in a precise given order. We need the notion of flow because these things are mostly side effects.

Assignment. An assignment is a particular kind of side effect: storing a new value in a variable, overwriting the old. It is the most important thing imperative programs do. (This is different from initialization, were the value is stored in a new variable as it is created.)

Flow control structures. Basically, we have three of them : "if", "while", and "for". I will not insult you by explaining those. (Functional languages have an "if", actually: it works the same as the C ternary operator "?:".)

To sum up quickly, Functional style is an imperative style without side effect. No flow of time, each variable is constant, and we don't have loops. Now, what can be done under such drastic restrictions? Computations. Given an input (a value), I can produce an output (another value). I just have to call some function or write some expression. Of course, if a program need to perform IO or user interaction, we need imperative features. However, large parts of many programs are mere computations.

Conclusion: there is a room for functional style. Now, is it a good idea to actually use it were we can? To answer this, I remember the most important questions: Is my code correct? Is it readable? Correctness and readability are always an issue when writing software, for code is rarely bug free, and programmers rarely work alone. Readability is often considered most important. For instance, If some piece of code looks scary, common wisdom say it can't be readable. Then, we can't check it's correctness. Conclusion, it belongs to the garbage, for we can't risk money and jobs in scary code. So, if functional programming is scary, we can't use it. To many, functional programming is scary: to actually compute anything interesting, functional programming encourages the use of features which are, for some reason and many people, scary. (These people often say: impractical.)

The first of these features is recursion. Functions can be defined in terms of themselves. Recursion looks quite foreign, almost magic: how the hell can I use something I have not defined yet? If we need to check the correctness of a recursive function, for example, we first have to assume it is correct. This kind of "bootstrapped" proof often look insane, although it is common in mathematics (I know it since high school).

Currently, any decent programming language, functional or not, support recursion. I think this is because sometimes, recursion is the only reasonable option (when implementing a sort, for example). Anyway, scary recursion is not encouraged by imperative languages. Some people still say it is inefficient (sadly, some implementations still prove them right). We have while loops, and we know them for a long time so why bother?

The second of these features is first class functions. That is, a function is a value like any other. Like any other value, it can be computed, stored in a variable (a new one, unless the language has imperative features) or passed as argument. Very few imperative languages support that. Who would ever want to pass a function as argument? Actually, we do : we have listeners and callbacks, data structures are accessed through iterators, objects are used to mimic closures... We just don't think about these as functions. Because of this, higher order functions are still perceived as an alien concept good for research, experts, or the garbage (remember the big money).

I remember the first time I really wondered if any programmer can handle a powerful language. My brother, who were studying set theory at the time, came to me to solve a problem. He haven't grasped the difference between "A belongs to B" and "A is included in B". First, it was easy to explain that in the former, "A is an element of the set B" and in later, "A is a subset of the set B". There, one can imagine the world as little crosses, the elements, surrounded by circles, the sets. Then, we saw in horror this description: "the set of the subsets of A". So we have some sets (the subsets of A), each of those included in another set (A), while being an element of some "superset". My brother, still thinking in terms of crosses and circles (utterly inappropriate in this case), had a hard time understanding these "higher order sets". As I have no problems with those, I tried to explain. I failed.

I think the main problem with recursion and higher order functions is self reference. With recursion, we have objects referencing themselves. With higher order functions, we have a concept referencing itself. Self reference is scary. Self reference leads to paradoxes and contradictions. I really hope I am wrong here, because self reference is a powerful tool for computing. It leads to recursion, which is convenient. It leads to higher order functions, which are powerful. It leads to macros (of the lisp kind: programs that write programs), which may be the best way to factor out code.

OK, Functional programming is scary. Why imperative, procedural programming is not? Because each line of a procedural code is very simple. The most complicated are the assignment and the function call. A procedural program do one thing at a time, so each step can be understood easily. We don't even have to talk about the flow or the state of the program. These are implicit, intuitive. To represent them, one can imagine a little worker, or robot, or whatever, performing each action described by the code, one by one. To understand the hole program, one has just to step from the beginning to the end, step by step. If the program is carefully documented, calls to procedures and functions can be understood without looking at their code. And most important, we can avoid scary features. We don't even have to think about them.

However, not being scary does not mean being better : the flow of time, while intuitive, is quite complicated to describe mathematically. Because of that, proving the correctness of even the simplest imperative program is a pain (try to prove some while loop). Variables must be checked against unexpected changes, and even expected changes must occur in the right order. Each line is very simple, but one have to embrace the whole program in her head to understand it anyway.

My conclusion is simple. As long as powerful abstractions are scary, functional programming will be considered impractical. Whether they are scary for good reasons or not, I do not know.


Aurette, qui cherche la petite bête said...

"the flow of time, while intuitive, is quite complicated to describe mathematically"

Tu peux me le décrire de façon plus complexe et plus utile que "t appartient à R, avec t exprimé dans une unité judicieusement choisie, et le point d'origine judicieusement choisi" ?

Loup said...

Rough translation of the above (from French):

Can you describe this in a more complex and useful way than "t belong to R, with t expressed in a wisely chosen unit, and the origin point wisely chosen"?


Actually, t (the time itself) is not much interesting (real time applications aside). What really matters is the state of the program (let's call it S(t)).

When I am talking about the flow of time, I am talking about each evolution of S(t) that occur while the program executes.

Basically, S(t) is the data the program has available at time t (a set of values). The changes that can occur to S(t) are the addition of a value, a modification of a value, and the withdrawal of a value. (With a garbage collector, we have no withdrawal, and in a functional setting, we have no modification as well.)

The main problem with S is that it rapidly grows complicated. More and more values are added and modified, and values can (and do) refer to one another. The nightmare begins when further updates of S(t) depend of older values. This kind of update depend on earlier updates, which depends on earlier updates... Soon, one have to track down a whole dependency tree.

In a functional setting, the relevant nodes are the creation of a value, which happens before any use of that value. Therefore, the dependency tree is readily deductible from the source code.

In an imperative setting, the relevant nodes are the creations of values and the modification of these values. Unlike creations, modifications can occur after a use. Therefore, it is no longer clear what piece of code contributed to some value at a given time, unless we execute it.

Ginzu said...

peux tu traduire ca, pour les lecteurs anglo-saxon:
"- touche moi pas tu vas me salir!"
"- ben casse toi alors! hein casse toi sale con!!!"


Loup Vaillant said...

So, the asked English translation:
"Don't you touch me, there's enough filth on me"
"Out of here. Yeah, out of here, you filthy bastard!"
Sweet name calling, Vincent (see, I can call names too! :-), but may I point out that Functional programming is precisely about keeping one's hands clean?