Previous Contents Next

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:
  1. Choose a pivot: This is the index of an element of the vector;
  2. 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;
  3. 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.
  1. Place the pivot at the beginning of the vector to be permuted;
  2. Initialize i to the index of the second element of the vector;
  3. Initialize j to the index of the last element of the vector;
  4. 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;
  5. While i<j, repeat the previous operation;
  6. 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. 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.


Previous Contents Next