2011-04-01

Imperative vs. functional: the conditional construct

Slowly I am acquiring some experience with functional paradigms. In this post I shall do a comparison of how a common construct like if is handled in imperative and functional programming languages. This stuff is probably well-known to any expert in computer languages, but for me this has been an interesting discovery!

Let's start by explaining roughly what are the differences between ``imperative programming'' and ``functional programming''. In the first case you put together a set of instructions, which must be executed in some well-defined order and alter locations of memory to accomplish some task. In the second case you build a set of ``functions'' whose purpose is to take some input and produce some output, without altering the state of the machine (more or less).

The most part of modern languages incorporate some elements of iterative programming and others of functional programming: of course, each language has its own preference regarding how to do things. For instance, C, Pascal, Python, Ruby and so on are more imperative, while OCaml, Haskell, Scheme are more functional (although they support imperative constructs). Even GNU R, a language for doing data analysis, has some important functional characteristics, as we shall see.

Conditional constructs

In order to explain the difference between functional and iterative programming, I shall concentrate on how you specify a conditional expression using different languages. My example is extremely practical, and it deals with the way Planck/LFI radiometers are labeled. LFI has 22 radiometers but only 11 antennas: the radiation entering each antenna is split into two polarised components and each of them enters a separate radiometer, called either ``main'' or ``side'' and labeled with M or S. To indicate a radiometer, one append the number of the antenna to the string LFI, then it appends either M or S, depending on the radiometer. So for instance the ``main'' radiometer fed by the twentieth antenna is LFI20M.

Of course, since it is much easier to deal with numbers than with letters (e.g. to implement cycles), many codes used within the Planck/LFI collaboration internally use 0 and 1 to represent the main and side radiometers. A very common task is therefore to build the name of the radiometer given two integer variables horn and rad (the number of the antenna and of the radiometer, the latter being either 0 or 1). Let's see how we can implement this in Python:

if rad == 0:
    rad_letter = 'M'
else:
    rad_letter = 'S'

name = "LFI%d%s" % (horn, rad_letter)

This is a rather naive approach employing the if conditional statement. We can reduce the number of lines by throwing away the else part:

rad_letter = 'M'
if rad == 1:
    rad_letter = 'S'

name = "LFI%d%s" % (horn, rad_letter)

The best solution is however to forget about the if and use a dictionary:

rad_letter = { 0: 'M', 1: 'S' }
name = "LFI%d%s" % (horn, rad_letter[rad])

This is the shorter solution, but likes the ones above it forces us to define a new variable, rad_letter. It is not elegant if we are going to use it in the following line only.

Other imperative languages do not allow many alternatives: they usually require the very same code seen above. Here is e.g. the solution in Pascal (another imperative language which does not support dictionaries natively):

if rad = 0 then
    rad_letter := 'M'
else
    rad_letter := 'S';

name := 'LFI' + str(horn) + rad_letter

What offer functional languages in this context? Well, for any functional language every statement is an expression and can be therefore composed with other expressions. So the above example in Scheme would be rewritten in this way:

(string-append "LFI" (number->string horn) (if (= rad 0) "M" "S"))

A very similar expression can be coded using Haskell:

"LFI" ++ (show horn) ++ (if rad == 0 then "M" else "S")

(the ++ function concatenates strings.) Note that in both cases we do not need to define an ancillary variable: everything can be put in one line.

Conceptually, the Scheme/Haskell solution would be the same as the following pseudo-Python code:

name = 'LFI' + str(horn) + (if rad == 0: 'M' else 'S')

with the difference that this is not accepted by Python: it will generate a ``bad syntax'' error. Note that GNU R has no problems in accepting this construct:

name <- paste("LFI", horn, if(rad == 0) "M" else "S", sep = "")

(the paste command joins strings): this suggests that GNU R is more functional than Python.

You might have noticed that I left C outside of this discussion. Well, it turns out that C/C++ do not allow to include an if within an expression, but it has a useful shorthand, the ``question-mark operator'':

sprintf(name, "LFI%d%c", horn, rad == 0 ? 'M' : 'S');

The syntax of this operator is: cond ? iftrue : iffalse. Note however that this is not really the if operator, but something else that behaves exactly like it. (And it is a second-class operator, as you cannot use it with C++ strings.) Moreover, the generalisation of the if statement is the switch statement (where the decision is not based on a true/false value, but on arbitrary values): and the latter cannot be used in a C expression. On the other side, the analogue of switch in Scheme (cond), Haskell (case) or OCaml (match) can be used in expressions exactly like if.

This post has shown that even in simple cases functional constructs can lead to shorter code. To see some striking example, be sure to have a look at the site Bonsai code. Its author, Remco Niemeijer, posts the shortest possible Haskell program which solves each problem posted in Programming praxis. Sometimes I am astonished how short the Haskell solution is!

No comments:

Post a Comment