Re: help an o'caml beginner

[John R Harrison <johnh@ichips.intel.com>]

Several people have given good translations of the more efficient Fibonacci
algorithm. Perhaps it's helpful to think more generally and see all these
(well, excluding Markus Mottl's more ingenious third variant) as particular
instances of a general way of converting imperative to functional code.

If you have an imperative program using state consisting of variables
x1,...,xn (of whatever type, including arrays) then you can easily convert
the program to a pure (tail) recursive function simply by making the entire
state, including a "program counter" to log where you are in more complex
cases, an explicit parameter.

 let prog state =
   if state.pc=end_of_program
   then (whichever bits of state you want to return)
   else let state' = update(state) in prog state';;

where "update" gives the new state after executing the current imperative
command. In the Fibonacci example, the relevant state consists of three
variables (once n is fixed) and these can be passed as a tuple or as 
separate arguments to a curried function. You can see how the recursive
call in Markus's:

  let rec fib2_aux n2 n1 = function
    | m when m = n -> n1
    | m -> fib2_aux n1 (n2+n1) (m+1) in

corresponds exactly (ignoring the renaming "i"|->"m" and the non-use of a
temporary variable "val") to the C code:

  for (i = 2; i < n; i++) {
      val = n2 + n1;
      n2 = n1;
      n1 = val;
  }

One might say that imperative programming is just functional programming
using a notation that makes state changes implicit. For many programmers,
this is often a more natural way to think, but the complications tend to
re-emerge when one tries to analyze the semantics of imperative code. In
fact, ascribing a denotational semantics to a program essentially just
involves making manifest this implicit state.

John.