Comparison between Functional and Imperative

Comparison between Functional and Imperative

Character strings (of Objective CAML type string) and linked lists (of Objective CAML type 'a list) will serve as examples to illustrate the differences between ``functional'' and ``imperative.''

The Functional Side

The function map (see page ??) is a classic ingredient in functional languages. In a purely functional style, it is written:


# let rec map f l = match l with 
      []   ->  []
   | h::q  ->  (f h) :: (map f q)  ;;
val map : ('a -> 'b) -> 'a list -> 'b list = <fun>

It recursively constructs a list by applying f to the elements of the list given as argument, independently specifying its head (f h) and its tail (map f q). In particular, the program does not stipulate which of the two will be computed first.

Moreover, the physical representation of lists need not be known to the programmer to write such a function. In particular, problems of allocating and sharing data are managed implicitly by the system and not by the programmer. An example illustrating this follows:


# let example = [ "one" ; "two" ; "three" ] ;;
val example : string list = ["one"; "two"; "three"]
# let result = map (function x -> x) example  ;;
val result : string list = ["one"; "two"; "three"]

The lists example and result contain equal values:


# example = result ;;
- : bool = true

These two values have exactly the same structure even though their representation in memory is different, as one learns by using the test for physical equality:


# example == result ;;
- : bool = false
# (List.tl example) == (List.tl result) ;;
- : bool = false

The Imperative Side

Let us continue the previous example, and modify a string in the list result.


# (List.hd result).[1] <- 's' ;;
- : unit = ()
# result ;;
- : string list = ["ose"; "two"; "three"]
# example ;;
- : string list = ["ose"; "two"; "three"]

Evidently, this operation has modified the list example. Hence, it is necessary to know the physical structure of the two lists being manipulated, as soon as we use imperative aspects of the language.

Let us now observe how the order of evaluating the arguments of a function can amount to a trap in an imperative program. We define a mutable list structure with primitive functions for creation, modification, and access:


# type 'a ilist = { mutable c : 'a list } ;;
type 'a ilist = { mutable c: 'a list }
# let icreate () = { c = [] }
 let iempty l = (l.c = []) 
 let icons x y = y.c <- x::y.c ; y
 let ihd x = List.hd x.c
 let itl x = x.c <- List.tl x.c ; x ;;
val icreate : unit -> 'a ilist = <fun>
val iempty : 'a ilist -> bool = <fun>
val icons : 'a -> 'a ilist -> 'a ilist = <fun>
val ihd : 'a ilist -> 'a = <fun>
val itl : 'a ilist -> 'a ilist = <fun>
# let rec imap f l = 
   if iempty l then icreate()
   else icons (f (ihd l))  (imap f (itl l)) ;;
val imap : ('a -> 'b) -> 'a ilist -> 'b ilist = <fun>

Despite having reproduced the general form of the map of the previous paragraph, with imap we get a distinctly different result:


# let example = icons "one" (icons "two" (icons "three" (icreate()))) ;;
val example : string ilist = {c=["one"; "two"; "three"]}
# imap (function x -> x) example ;;
Uncaught exception: Failure("hd")

What has happened? Just that the evaluation of (itl l) has taken place before the evaluation of (ihd l), so that on the last iteration of imap, the list referenced by l became the empty list before we examined its head. The list example is henceforth definitely empty even though we have not obtained any result:


# example ;;
- : string ilist = {c=[]}

The flaw in the function imap arises from a mixing of the genres that has not been controlled carefully enough. The choice of order of evaluation has been left to the system. We can reformulate the function imap, making explicit the order of evaluation, by using the syntactic construction let .. in ..


# let rec imap f l = 
   if iempty l then icreate()
   else let h = ihd l  in  icons (f h)  (imap f (itl l)) ;;
val imap : ('a -> 'b) -> 'a ilist -> 'b ilist = <fun>
# let example = icons "one" (icons "two" (icons "three" (icreate()))) ;;
val example : string ilist = {c=["one"; "two"; "three"]}
# imap (function x -> x) example ;;
- : string ilist = {c=["one"; "two"; "three"]}

However, the original list has still been lost:


# example ;;
- : string ilist = {c=[]}

Another way to make the order of evaluation explicit is to use the sequencing operator and a looping structure.


# let imap f l = 
   let l_res = icreate ()  
   in while not (iempty l) do 
        ignore (icons (f (ihd l)) l_res) ;
        ignore (itl l)
      done ;
      { l_res with c = List.rev l_res.c } ;;
val imap : ('a -> 'b) -> 'a ilist -> 'b ilist = <fun>
# let example = icons "one" (icons "two" (icons "three" (icreate()))) ;;
val example : string ilist = {c=["one"; "two"; "three"]}
# imap (function x -> x) example ;;
- : string ilist = {c=["one"; "two"; "three"]}

The presence of ignore emphasizes the fact that it is not the result of the functions that counts here, but their side effects on their argument. In addition, we had to put the elements of the result back in the right order (using the function List.rev).

Recursive or Iterative

People often mistakenly associate recursive with functional and iterative with imperative. A purely functional program cannot be iterative because the value of the condition of a loop never varies. By contrast, an imperative program may be recursive: the original version of the function imap is an example.

Calling a function conserves the values of its arguments during its computation. If it calls another function, the latter conserves its own arguments in addition. These values are conserved on the execution stack. When the call returns, these values are popped from the stack. The memory space available for the stack being bounded, it is possible to encounter the limit when using a recursive function with calls too deeply nested. In this case, Objective CAML raises the exception Stack_overflow.


# let rec succ n = if n = 0 then 1 else 1 + succ (n-1) ;;
val succ : int -> int = <fun>
# succ 100000 ;;
Stack overflow during evaluation (looping recursion?).

In the iterative version succ_iter, the stack space needed for a call does not depend on its argument.


# let succ_iter n = 
   let i = ref 0 in 
     for j=0 to n do incr i done ;
     !i ;;
val succ_iter : int -> int = <fun>
# succ_iter 100000 ;;
- : int = 100001

The following recursive version has a priori the same depth of calls, yet it executes successfully with the same argument.


# let succ_tr n = 
   let rec succ_aux n accu = 
     if n = 0 then accu  else succ_aux (n-1) (accu+1) 
   in 
     succ_aux 1 n ;;
val succ_tr : int -> int = <fun>
# succ_tr 100000 ;;
- : int = 100001

This function has a special form of recursive call, called tail recursion, in which the result of this call will be the result of the function without further computation. It is therefore unnecessary to have stored the values of the arguments to the function while computing the recursive call. When Objective CAML can observe that a call is tail recursive, it frees the arguments on the stack before making the recursive call. This optimization allows recursive functions that do not increase the size of the stack.

Many languages detect tail recursive calls, but it is indispensable in a functional language, where naturally many tail recursive calls are used.