Which Style to Choose?

Which Style to Choose?

This is no matter of religion or esthetics; a priori neither style is prettier or holier than the other. On the contrary, one style may be more adequate than the other depending on the problem to be solved.

The first rule to apply is the rule of simplicity. Whether the algorithm to use implemented is written in a book, or whether its seed is in the mind of the programmer, the algorithm is itself described in a certain style. It is natural to use the same style when implementing it.

The second criterion of choice is the efficiency of the program. One may say that an imperative program (if well written) is more efficient that its functional analogue, but in very many cases the difference is not enough to justify complicating the code to adopt an imperative style where the functional style would be natural. The function map in the previous section is a good example of a problem naturally expressed in the functional style, which gains nothing from being written in the imperative style.

Sequence or Composition of Functions

We have seen that as soon as a program causes side effects, it is necessary to determine precisely the order of evaluation for the elements of the program. This can be done in both styles:

functional:: using the fact that Objective CAML is a strict language, which means that the argument is evaluated before applying the function. The expression (f (g x)) is computed by first evaluating (g x), and then passing the result as argument to f. With more complex expressions, we can name an intermediate result with the let in construction, but the idea remains the same: let aux=(g x) in (f aux).
imperative:: using sequences or other control structures (loops). In this case, the result is not the value returned by a function, but its side effects on memory: aux:=(g x) ; (f !aux).

Let us examine this choice of style on an example. The quick sort algorithm, applied to a vector, is described recursively as follows:

Choose a pivot: This is the index of an element of the vector;
Permute around the pivot: Permute the elements of the vector so elements less than the value at the pivot have indices less than the pivot, and vice versa;
sort the subvectors obtained on each side of the pivot, using the same algorithm: The subvector preceding the pivot and the subvector following the pivot.

The choice of algorithm, namely to modify a vector so that its elements are sorted, incites us to use an imperative style at least to manipulate the data.

First, we define a function to permute two elements of a vector:


# let permute_element vec n p = 
   let aux = vec.(n) in vec.(n) <- vec.(p) ; vec.(p) <- aux  ;;
val permute_element : 'a array -> int -> int -> unit = <fun>

The choice of a good pivot determines the efficiency of the algorithm, but we will use the simplest possible choice here: return the index of the first element of the (sub)vector.


# let choose_pivot vec start finish = start ;;
val choose_pivot : 'a -> 'b -> 'c -> 'b = <fun>

Let us write the algorithm that we would like to use to permute the elements of the vector around the pivot.

Place the pivot at the beginning of the vector to be permuted;
Initialize i to the index of the second element of the vector;
Initialize j to the index of the last element of the vector;
If the element at index j is greater than the pivot, permute it with the element at index i and increment i; otherwise, decrement j;
While i<j, repeat the previous operation;
At this stage, every element with index <i (or equivalently, j) is less than the pivot, and all others are greater; if the element with index i is less than the pivot, permute it with the pivot; otherwise, permute its predecessor with the pivot.

In implementing this algorithm, it is natural to adopt imperative control structures.


# let permute_pivot vec start finish ind_pivot = 
    permute_element vec start ind_pivot ;
    let i = ref (start+1) and j = ref finish and pivot = vec.(start) in
    while !i < !j do 
      if vec.(!j) >= pivot then decr j 
      else
        begin
          permute_element vec !i !j ;
          incr i
        end
    done ;
    if vec.(!i) > pivot then decr i ;
    permute_element vec start !i ;
    !i 
 ;;
val permute_pivot : 'a array -> int -> int -> int -> int = <fun>

In addition to its effects on the vector, this function returns the index of the pivot as its result.

All that remains is to put together the different stages and add the recursion on the sub-vectors.


# let rec quick vec start finish = 
    if start < finish 
    then 
      let pivot = choose_pivot vec start finish in 
      let place_pivot = permute_pivot vec start finish pivot in 
      quick (quick vec start (place_pivot-1)) (place_pivot+1) finish
    else vec ;;
val quick : 'a array -> int -> int -> 'a array = <fun>

We have used the two styles here. The chosen pivot serves as argument to the permutation around this pivot, and the index of the pivot after the permutation is an argument to the recursive call. By contrast, the vector obtained after the permutation is not returned by the permute_pivot function; instead, this result is produced by side effect. However, the quick function returns a vector, and the sorting of sub-vectors is obtained by composition of recursive calls.

The main function is:


# let quicksort vec = quick vec 0 ((Array.length vec)-1) ;;
val quicksort : 'a array -> 'a array = <fun>

It is a polymorphic function because the order relation < on vector elements is itself polymorphic.


# let t1 = [|4;8;1;12;7;3;1;9|] ;;
val t1 : int array = [|4; 8; 1; 12; 7; 3; 1; 9|]
# quicksort t1 ;;
- : int array = [|1; 1; 3; 4; 7; 8; 9; 12|]
# t1 ;;
- : int array = [|1; 1; 3; 4; 7; 8; 9; 12|]
# let t2 = [|"the"; "little"; "cat"; "is"; "dead"|] ;;
val t2 : string array = [|"the"; "little"; "cat"; "is"; "dead"|]
# quicksort t2 ;;
- : string array = [|"cat"; "dead"; "is"; "little"; "the"|]
# t2 ;;
- : string array = [|"cat"; "dead"; "is"; "little"; "the"|]

Shared or Copy Values

When the values that we manipulate are not mutable, it does not matter whether they are shared or not.


# let id x = x ;;
val id : 'a -> 'a = <fun>
# let a = [ 1; 2; 3 ] ;;
val a : int list = [1; 2; 3]
# let b = id a ;;
val b : int list = [1; 2; 3]

Whether b is a copy of the list a or the very same list makes no difference, because these are intangible values anyway. But if we put modifiable values in place of integers, we need to know whether modifying one value causes a change in the other.

The implementation of polymorphism in Objective CAML causes immediate values to be copied, and structured values to be shared. Even though arguments are always passed by value, only the pointer to a structured value is copied. This is the case even in the function id:


# let a = [| 1 ; 2 ; 3 |] ;;
val a : int array = [|1; 2; 3|]
# let b = id a ;;
val b : int array = [|1; 2; 3|]
# a.(1) <- 4 ;;
- : unit = ()
# a ;;
- : int array = [|1; 4; 3|]
# b ;;
- : int array = [|1; 4; 3|]

We have here a genuine programming choice to decide which is the most efficient way to represent a data structure. On one hand, using mutable values allows manipulations in place, which means without allocation, but requires us to make copies sometimes when immutable data would have allowed sharing. We illustrate this here with two ways to implement lists.


# type 'a list_immutable = LInil | LIcons of 'a * 'a list_immutable ;;
# type 'a list_mutable = LMnil | LMcons of 'a * 'a list_mutable ref ;;

The immutable lists are strictly equivalent to lists built into Objective CAML, while the mutable lists are closer to the style of C, in which a cell is a value together with a reference to the following cell.

With immutable lists, there is only one way to write concatenation, and it requires duplicating the structure of the first list; by contrast, the second list may be shared with the result.


# let rec concat l1 l2 = match l1 with 
     LInil -> l2
   | LIcons (a,l11) -> LIcons(a, (concat l11 l2)) ;;
val concat : 'a list_immutable -> 'a list_immutable -> 'a list_immutable =
  <fun>

# let li1 = LIcons(1, LIcons(2, LInil))
 and li2 =  LIcons(3, LIcons(4, LInil)) ;;
val li1 : int list_immutable = LIcons (1, LIcons (2, LInil))
val li2 : int list_immutable = LIcons (3, LIcons (4, LInil))
# let li3 = concat li1 li2 ;;
val li3 : int list_immutable =
  LIcons (1, LIcons (2, LIcons (3, LIcons (4, LInil))))
# li1==li3 ;;
- : bool = false
# let tlLI l =  match l with 
   LInil       -> failwith "Liste vide" 
 | LIcons(_,x) -> x ;;
val tlLI : 'a list_immutable -> 'a list_immutable = <fun>
# tlLI(tlLI(li3)) == li2 ;;
- : bool = true

From these examples, we see that the first cells of li1 and li3 are distinct, while the second half of li3 is exactly li2.

With mutable lists, we have a choice between modifying arguments (function concat_share) and creating a new value (function concat_copy).


# let rec concat_copy l1 l2 =  match l1 with 
     LMnil  -> l2
   | LMcons (x,l11) -> LMcons(x, ref (concat_copy !l11 l2)) ;;
val concat_copy : 'a list_mutable -> 'a list_mutable -> 'a list_mutable =
  <fun>

This first solution, concat_copy, gives a result similar to the previous function, concat. A second solution shares its arguments with its result fully:


# let concat_share l1 l2 = 
  match l1 with
    LMnil -> l2
  | _     -> let rec set_last = function
                LMnil       -> failwith "concat_share : impossible case!!"
              | LMcons(_,l) -> if !l=LMnil then l:=l2 else set_last !l
             in
               set_last l1 ;
               l1 ;;
val concat_share : 'a list_mutable -> 'a list_mutable -> 'a list_mutable =
  <fun>

Concatenation with sharing does not require any allocation, and therefore does not use the constructor LMcons. Instead, it suffices to cause the last cell of the first list to point to the second list. However, this version of concatenation has the potential weakness that it alters arguments passed to it.


# let lm1 = LMcons(1, ref (LMcons(2, ref LMnil)))
 and lm2 = LMcons(3, ref (LMcons(4, ref LMnil))) ;;
val lm1 : int list_mutable =
  LMcons (1, {contents=LMcons (2, {contents=LMnil})})
val lm2 : int list_mutable =
  LMcons (3, {contents=LMcons (4, {contents=LMnil})})
# let lm3 = concat_share lm1 lm2 ;;
val lm3 : int list_mutable =
  LMcons (1, {contents=LMcons (2, {contents=LMcons (...)})})

We do indeed obtain the expected result for lm3. However, the value bound to lm1 has been modified.


# lm1 ;;
- : int list_mutable =
LMcons (1, {contents=LMcons (2, {contents=LMcons (...)})})

This may therefore have consequences on the rest of the program.

How to Choose your Style

In a purely functional program, side effects are forbidden, and this excludes mutable data structures, exceptions, and input/output. We prefer, though, a less restrictive definition of the functional style, saying that functions that do not modify their global environment may be used in a functional style. Such a function may manipulate mutable values locally, and may therefore be written in an imperative style, but must not modify global variables, nor its arguments. We permit them to raise exceptions in addition. Viewed from outside, these functions may be considered ``black boxes.'' Their behavior matches a function written in a purely functional style, apart from being able of breaking control flow by raising an exception. In the same spirit, a mutable value which can no longer be modified after initialization may be used in a functional style.

On the other hand, a program written in an imperative style still benefits from the advantages provided by Objective CAML: static type safety, automatic memory management, the exception mechanism, parametric polymorphism, and type inference.

The choice between the imperative and functional styles depends on the application to be developed. We may nevertheless suggest some guidelines based on the character of the application, and the criteria considered important in the development process.

choice of data structures: The choice whether to use mutable data structures follows from the style of programming adopted. Indeed, the functional style is essentially incompatible with modifying mutable values. By contrast, constructing and traversing objects are the same whatever their status. This touches the same issue as ``modification in place vs copying'' on page ??; we return to it again in discussing criteria of efficiency.
required data structures: If a program must modify mutable data structures, then the imperative style is the only one possible. If, on the other hand, you just have to traverse values, then adopting the functional style guarantees the integrity of the data.
Using recursive data structures requires the use of functions that are themselves recursive. Recursive functions may be defined using either of the two styles, but it is often easier to understand the creation of a value following a recursive definition, which corresponds to a functional approach, than to repeat the recursive processing on this element. The functional style allows us to define generic iterators over the structure of data, which factors out the work of development and makes it faster.
criteria of efficiency: Modification in place is far more efficient than creating a value. When code efficiency is the preponderant criterion, it will usually tip the balance in favor of the imperative style. We note however that the need to avoid sharing values may turn out to be a very hard task, and in the end costlier than copying the values to begin with.
Being purely functional has a cost. Partial application and using functions passed as arguments from other functions has an execution cost greater than total application of a function whose declaration is visible. Using this eminently functional feature must thus be avoided in those portions of a program where efficiency is crucial.
development criteria: the higher level of abstraction of functional programs permits them to be written more quickly, leading to code that is more compact and contains fewer errors than the equivalent imperative code, which is generally more verbose. The functional style is better suited to the constraints imposed by developing substantial applications. Since each function is not dependent upon its evaluation context, functional can be easily divided into small units that can be examined separately; as a consequence, the code is easier to read.
Programs written using the functional style are more easily reusable because of its better modularity, and because functions may be passed as arguments to other functions.

These remarks show that it is often a good idea to mix the two programming styles within the same application. The functional programming style is faster to develop and confers a simpler organization to an application. However, portions whose execution time is critical repay being developed in a more efficient imperative style.