Previous Contents Next

Control Structures

Input-output and modifiable values produce side-effects. Their use is made easier by an imperative programming style furnished with new control structures. We present in this section the sequence and iteration structures.

We have already met the conditional control structure on page ??, whose abbreviated form if then patterns itself on the imperative world. We will write, for example: 

# let n = ref 1 ;;
val n : int ref = {contents=1}
# if !n > 0 then n := !n - 1 ;;
- : unit = ()


Sequence

The first of the typically imperative structures is the sequence. This permits the left-to-right evaluation of a sequence of expressions separated by semicolons.

Syntax

expr1 ; ...; exprn
A sequence of expressions is itself an expression, whose value is that of the last expression in the sequence (here, exprn). Nevertheless, all the expressions are evaluated, and in particular their side-effects are taken into account. 

# print_string "2 = "; 1+1 ;;
2 = - : int = 2


With side-effects, we get back the usual construction of imperative languages. 

# let x = ref 1 ;;
val x : int ref = {contents=1}
# x:=!x+1 ; x:=!x*4 ; !x ;;
- : int = 8


As the value preceding a semicolon is discarded, Objective CAML gives a warning when it is not of type unit. 

# print_int 1; 2 ; 3 ;;
Characters 14-15:
Warning: this expression should have type unit.
1- : int = 3


To avoid this message, you can use the function ignore: 

# print_int 1; ignore 2; 3 ;;
1- : int = 3


A different message is obtained if the value has a functional type, as Objective CAML suspects that you have forgotten a parameter of a function. 

# let g x y = x := y ;;
val g : 'a ref -> 'a -> unit = <fun>
# let a = ref 10;;
val a : int ref = {contents=10}
# let u = 1 in g a ; g a u ;;
Characters 13-16:
Warning: this function application is partial,
maybe some arguments are missing.
- : unit = ()
# let u = !a in ignore (g a) ; g a u ;;
- : unit = ()


As a general rule we parenthesize sequences to clarify their scope. Syntactically, parenthesizing can take two forms:

Syntax

( expr )

Syntax

begin expr end
We can now write the Higher/Lower program from page ?? more naturally: 

# let rec hilo n =
   print_string "type a number: ";
   let i = read_int () in 
   if i = n then print_string "BRAVO\n\n"
    else 
      begin
        if i < n then print_string "Higher\n" else print_string "Lower\n"  ;
        hilo n
      end ;;
val hilo : int -> unit = <fun>


Loops

The iterative control structures are also from outside the functional world. The conditional expression for repeating, or leaving, a loop does not make sense unless there can be a physical modification of the memory which permits its value to change. There are two iterative control structures in Objective CAML: the for loop for a bounded iteration and the while loop for a non-bounded iteration. The loop structures themselves are expressions of the language. Thus they return a value: the constant () of type unit.

The for loop can be rising (to) or falling (downto) with a step of one.

Syntax

for name = expr1 to expr2 do expr3 done
for name = expr1 downto expr2 do expr3 done
The expressions expr1 and expr2 are of type int. If expr3 is not of type unit, the compiler produces a warning message. 

# for i=1 to 10 do  print_int i; print_string " " done; print_newline() ;;
1 2 3 4 5 6 7 8 9 10 
- : unit = ()
# for i=10 downto 1 do print_int i; print_string " " done; print_newline() ;;
10 9 8 7 6 5 4 3 2 1 
- : unit = ()


The non-bounded loop is the ``while'' loop whose syntax is:

Syntax

while expr1 do expr2 done
The expression expr1 should be of type bool. And, as for the for loop, if expr2 is not of type unit, the compiler produces a warning message. 

# let r = ref 1 
 in while !r < 11  do
      print_int !r ;
      print_string " " ;
      r := !r+1
    done ;;
1 2 3 4 5 6 7 8 9 10 - : unit = ()


It is important to understand that loops are expressions like the previous ones which calculate the value () of type unit. 

# let f () = print_string "-- end\n" ;;
val f : unit -> unit = <fun>
# f (for i=1 to 10 do  print_int i; print_string " " done) ;;
1 2 3 4 5 6 7 8 9 10 -- end
- : unit = ()
Note that the string "-- end\n" is output after the integers from 1 to 10 have been printed: this is a demonstration that the arguments (here the loop) are evaluated before being passed to the function.

In imperative programming, the body of a loop (expr2) does not calculate a value, but advances by side effects. In Objective CAML, when the body of a loop is not of type unit the compiler prints a warning, as for the sequence: 

# let s = [5; 4; 3; 2; 1; 0] ;; 
val s : int list = [5; 4; 3; 2; 1; 0]
#  for i=0 to 5 do List.tl s done ;;
Characters 17-26:
Warning: this expression should have type unit.
- : unit = ()


Example: Implementing a Stack

The data structure 'a stack will be implemented in the form of a record containing an array of elements and the first free position in this array. Here is the corresponding type: 

# type 'a stack = { mutable ind:int; size:int; mutable elts : 'a array } ;;
The field size contains the maximal size of the stack.

The operations on these stacks will be init_stack for the initialization of a stack, push for pushing an element onto a stack, and pop for returning the top of the stack and popping it off. 

# let init_stack n = {ind=0; size=n; elts =[||]} ;;
val init_stack : int -> 'a stack = <fun>
This function cannot create a non-empty array, because you would have to provide it with the value with which to construct it. This is why the field elts gets an empty array.

Two exceptions are declared to guard against attempts to pop an empty stack or to add an element to a full stack. They are used in the functions pop and push. 

# exception Stack_empty ;;
# exception Stack_full ;;

# let pop p = 
   if p.ind = 0 then raise Stack_empty
   else (p.ind <- p.ind - 1; p.elts.(p.ind)) ;;
val pop : 'a stack -> 'a = <fun>
# let push e p = 
   if p.elts = [||] then 
     (p.elts <- Array.create p.size e;
      p.ind <- 1)
   else if p.ind >= p.size then raise Stack_full
   else (p.elts.(p.ind) <- e; p.ind <- p.ind + 1) ;;
val push : 'a -> 'a stack -> unit = <fun>


Here is a small example of the use of this data structure: 

# let p = init_stack 4 ;;
val p : '_a stack = {ind=0; size=4; elts=[||]}
# push 1 p ;;
- : unit = ()
# for i = 2 to 5 do push i p done ;;
Uncaught exception: Stack_full
# p ;;
- : int stack = {ind=4; size=4; elts=[|1; 2; 3; 4|]}
# pop p ;;
- : int = 4
# pop p ;;
- : int = 3


If we want to prevent raising the exception Stack_full when attempting to add an element to the stack, we can enlarge the array. To do this the field size must be modifiable too: 

# type 'a stack = 
   {mutable ind:int ; mutable size:int ; mutable elts : 'a array} ;;
# let init_stack n = {ind=0; size=max n 1; elts = [||]} ;;
# let n_push e p = 
   if p.elts = [||] 
   then 
     begin
       p.elts <- Array.create p.size e;
       p.ind <- 1 
     end 
   else if p.ind >= p.size then 
     begin
       let nt = 2 * p.size in 
       let nv = Array.create nt e in 
       for j=0 to p.size-1 do nv.(j) <- p.elts.(j) done ;
       p.elts <- nv;
       p.size <- nt;
       p.ind <- p.ind + 1
     end
   else 
     begin
       p.elts.(p.ind) <- e ;
       p.ind <- p.ind + 1 
     end ;;
val n_push : 'a -> 'a stack -> unit = <fun>


All the same, you have to be careful with data structures which can expand without bound. Here is a small example where the initial stack grows as needed. 

# let p = init_stack 4 ;;
val p : '_a stack = {ind=0; size=4; elts=[||]}
# for i = 1 to 5 do n_push i p done ;;
- : unit = ()
# p ;;
- : int stack = {ind=5; size=8; elts=[|1; 2; 3; 4; 5; 5; 5; 5|]}
# p.stack ;;
Characters 0-7:
Unbound label stack


It might also be useful to allow pop to decrease the size of the stack, to reclaim unused memory.

Example: Calculations on Matrices

In this example we aim to define a type for matrices, two-dimensional arrays containing floating point numbers, and to write some operations on the matrices. The monomorphic type mat is a record containing the dimensions and the elements of the matrix. The functions create_mat, access_mat, and mod_mat are respectively the functions for creation, accessing an element, and modification of an element. 

# type mat = { n:int; m:int; t: float array array };;
type mat = { n: int; m: int; t: float array array }
# let create_mat n m = { n=n; m=m; t = Array.create_matrix n m 0.0 } ;;
val create_mat : int -> int -> mat = <fun>
# let access_mat m i j = m.t.(i).(j) ;;
val access_mat : mat -> int -> int -> float = <fun>
# let mod_mat m i j e = m.t.(i).(j) <- e ;;
val mod_mat : mat -> int -> int -> float -> unit = <fun>
# let a = create_mat 3 3 ;;
val a : mat = {n=3; m=3; t=[|[|0; 0; 0|]; [|0; 0; 0|]; [|0; 0; 0|]|]}
# mod_mat a 1 1 2.0; mod_mat a 1 2 1.0; mod_mat a 2 1 1.0 ;;
- : unit = ()
# a ;;
- : mat = {n=3; m=3; t=[|[|0; 0; 0|]; [|0; 2; 1|]; [|0; 1; 0|]|]}


The sum of two matrices a and b is a matrix c  such that   cij = aij + bij. 

# let add_mat p q = 
   if p.n = q.n && p.m = q.m then 
     let r = create_mat p.n p.m  in
     for i = 0 to p.n-1 do 
       for j = 0 to p.m-1 do 
         mod_mat r i j  (p.t.(i).(j) +. q.t.(i).(j))
       done
     done ;
     r
   else failwith "add_mat : dimensions incompatible";; 
val add_mat : mat -> mat -> mat = <fun>
# add_mat  a a ;;
- : mat = {n=3; m=3; t=[|[|0; 0; 0|]; [|0; 4; 2|]; [|0; 2; 0|]|]}


The product of two matrices a and b is a matrix c  such that cij = åk=1k=ma aik. bkj 

# let mul_mat p q = 
   if p.m = q.n then 
     let r = create_mat p.n q.m in
     for i = 0 to p.n-1 do 
       for j = 0 to q.m-1 do
         let c = ref 0.0 in 
         for k = 0 to p.m-1 do  
            c := !c +.   (p.t.(i).(k) *. q.t.(k).(j))
          done;
          mod_mat r i j !c
       done
     done;
     r
   else failwith "mul_mat : dimensions incompatible" ;; 
val mul_mat : mat -> mat -> mat = <fun>
# mul_mat a a;;
- : mat = {n=3; m=3; t=[|[|0; 0; 0|]; [|0; 5; 2|]; [|0; 2; 1|]|]}


Previous Contents Next