Saturday, July 9, 2011

Functional Programming ?

Do you know functional programming ?

Functional programming (FP) is an interesting subject for a lot of reasons. Those of us that have used (and still used) functional programming languages  (FPL) often pointed out two disappointing facts:

  1. Lots of programmers doesn't really understand what is it
  2. Despite the fact that FP and FPL are pleasant to use but also quite efficient, it is still not largely used

Am I a FP fan ? the quick answer is "no more", the longest one is more complicated. I have used OCaml for now more than 10 years, I've found it very useful and pleasant many time. But, I've also found a lot of unsatisfactory points. It is hard to really explain why, but on bigger project, the absence of constraints on global program structure often leads to unreadable code, some syntax choices are annoying ... Other FPL haven't convince me yet ...

So, here are my humble opinion (how I hate this expression ... )


First, I'll attempt to define FP and what should be an FPL. You should right now forget the erroneous idea that FP is about recursion and recursive functions !
FP arise from early days of formal languages (before computers in fact), exactly λ-calculus is (at least for me) the starting point of FP. So what is the main characteristic of λ-calculus ? Function as first class value ! In fact, functions are the only value in λ-calculus !
First class value are language entities that can be passed (and returned) to (by) functions. So, λ-calculus can directly manipulate functions, this is what we call higher-order. So, the first requirement of a FPL is higher-order.

λ-calculus, being a mathematical model, have no notion of mutable entities and side effects (in fact mutable and side effects can be expressed in pure functional semantics.) Thus, languages inspired by λ-calculus try to avoid these notions to match the original model, but it's a matter of style. 

Another aspect of FP and FPL is the notion of everything evaluate to a value: we should always return something and there's no difference between statement and expression as in imperative languages. This is strongly linked with the absence of side-effect: you don't modify a state, you return a new value.

What about loops in FP ? The fact that in FP we prefer recursion over loops, is a consequences of the everything is an expression: a loop does not return a value. But, FOR-loops (i.e. bounded iterations) can exist without mutable entities and thus fit in the model (we can somehow handle the loop returns nothing, since in FPL nothing can be something) on the other hand, integrating WHILE-loops in the semantics of a pure FPL is far more difficult (we need to express a changing state.)

So, to summarize: an FPL is language with higher-order where everything is expression and where we prefer to limit mutable entities and side-effect. Everything else is comes from those facts (partial evaluation and curryfied functions, recursion rather than loop and even lazy evaluation.)

Is there good FPL ? This is hard and dangerous question. I tend to prefer strongly typed FPL, and thus my list of good FPL will be limited to the ML family (and derived languages.) My favorite is OCaml for various reason: I learnt FP with it, it is not too purist (in OCaml you have imperative aspects and even objects), it has a good module approach (functors ... ) and resulting code works well. I found Haskell interesting but too extremist to my taste. Lisp and scheme derivatives haven't convince me (but again, I prefer typed languages ... )


Interesting FPL features: except for pure FP aspects, many FPL have interesting features.:

  • Pattern Matching: this probably the most impressive features, it lets you describe complex cases and extract values. Combined with variants, it offers the best way to traverse abstract syntax trees.
  • Module systems: to organize your code, module are very useful and some FPL provides very powerful framework. For example, the module system of OCaml lets you define nested modules, independant module interfaces and the powerful functors (function over modules.)
  • Lazy evaluation: lazy values is mix between functions and expressions, as functions it is not evaluated when defined, but as expressions, it is evaluated only once. This lets you define expressions that will be evaluated only when needed but then resulting value is memoized. A good
    example is infinite generated lists: elements of the lists are generated only when traversed, but then you don't need to compute it for each access.

Now, how about the lack of users of FPL ? Since, I'm myself a disappointed user of FPL, I can understand the relatively low audience of FPL.

First of all, most FPL are research projects and as such are never quite yet finished: the language changes too often, priority is put on new features rather than production necessity ... Thus, it is hard to develop a long and stable project using an FPL.
On the side of the languages them selves, there are also some disturbing points. Even compiled FPL have an original syntax designed for interpretors, thus program written with those syntax are often badly organized. For example, there's no explicit entry point in OCaml, you must carefully organize your code so that the execution flow go directly where you want.

From a syntaxic point of view, language history has shown that language with explicitly delimited blocks and instructions have a better impact than too permissive one. Most FPL are syntactically permissive languages.

So, I think that despite being very interesting programming languages, FPL are not a good choice for practical reason. These reasons are not tied to the FP model but to the implementations of this model. If we want to see FPL regarded as usable as other main languages some day, we need a more stable language with something like a C syntax.