From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id CAA11784 for caml-red; Fri, 28 Jul 2000 02:07:04 +0200 (MET DST)
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id AAA11173 for <caml-list@pauillac.inria.fr>; Fri, 28 Jul 2000 00:50:24 +0200 (MET DST)
Received: from ganymede.or.intel.com (ganymede.or.intel.com [134.134.248.3])
	by nez-perce.inria.fr (8.10.0/8.10.0) with ESMTP id e6RMoNL28460
	for <caml-list@inria.fr>; Fri, 28 Jul 2000 00:50:23 +0200 (MET DST)
Received: from ichips-jf.jf.intel.com (ichips-jf-hme1.jf.intel.com [134.134.100.112])
	by ganymede.or.intel.com (8.9.1a+p1/8.9.1/d: relay.m4,v 1.30 2000/06/08 18:25:35 dmccart Exp $) with ESMTP id PAA08242
	for <caml-list@inria.fr>; Thu, 27 Jul 2000 15:50:16 -0700 (PDT)
Received: from dtthp127.pdx.intel.com (dtthp127.pdx.intel.com [134.134.102.82])
	by ichips-jf.jf.intel.com (8.9.1a/8.9.1/d: internal.m4,v 1.2 1998/11/09 19:18:37 iwep Exp iwep $) with ESMTP id PAA04001;
	Thu, 27 Jul 2000 15:50:21 -0700 (PDT)
Received: from ichips.intel.com (johnh@localhost [127.0.0.1])
	by dtthp127.pdx.intel.com (8.9.1a/8.9.1/d: client-jf.m4,v 1.1 1998/12/24 19:00:41 jamesw Exp jamesw $) with ESMTP id PAA19230;
	Thu, 27 Jul 2000 15:50:21 -0700 (PDT)
Message-Id: <200007272250.PAA19230@dtthp127.pdx.intel.com>
To: caml-list@inria.fr
cc: John Harrison <johnh@ichips.intel.com>
Subject: Re: help an o'caml beginner
Date: Thu, 27 Jul 2000 15:50:14 -0700
From: John R Harrison <johnh@ichips.intel.com>
Sender: weis@pauillac.inria.fr


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.