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 XAA08230 for caml-red; Thu, 27 Jul 2000 23:28:20 +0200 (MET DST)
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id UAA05380 for <caml-list@pauillac.inria.fr>; Thu, 27 Jul 2000 20:24:40 +0200 (MET DST)
Received: from thresher.xpsystems.com ([207.171.47.5])
	by concorde.inria.fr (8.10.0/8.10.0) with ESMTP id e6RIOc520476
	for <caml-list@inria.fr>; Thu, 27 Jul 2000 20:24:39 +0200 (MET DST)
Received: by THRESHER with Internet Mail Service (5.5.2650.21)
	id <PDVJ7Q3W>; Thu, 27 Jul 2000 11:24:50 -0700
Message-ID: <EDFD2A95EE7DD31187350090279C6767C25C35@THRESHER>
From: Brent Fulgham <brent.fulgham@xpsystems.com>
To: John BEPPU <beppu@lineo.com>, caml-list@inria.fr
Subject: RE: help an o'caml beginner
Date: Thu, 27 Jul 2000 11:24:46 -0700
X-Mailer: Internet Mail Service (5.5.2650.21)
Sender: weis@pauillac.inria.fr

> I happen to be a fan of the other camel (Perl), but I hope you don't
> hold that against me.  ;-)
>
Not at all -- I happen to be a fan of using the right tool for the job.

> I tried out the recursive fibonacci number program that's in the
> manual. 
> 
>     let rec fib n =
>         if n < 2 then 1 else fib(n-1) + fib(n-2);;
>     let main () =
>         let arg = int_of_string Sys.argv.(1) in
>         print_int(fib arg);
>         print_newline();
>         exit 0;;
>     main ();;
> 

[ ... snip C version ... ]

> What surprised the fsck out of me was how fast the O'Caml version
> was compared to the C version.  I checked the asm output of ocamlopt,
> and that was some lean code.  I was not expecting results like this,
> so I was quite pleasantly surprised.  The performance of ocamlopt is
> yet another reason I'm here.
> 
Yes -- the OCaml team has done a fantastic job of creating an efficient,
well-optimized compiler.  It's a good example that shows that functional
languages need not be slow.

[ ... snip iterative C ... ]

> This was much faster than any of the recursive versions, because it 
> doesn't have to recompute the same values over and over again.  
> 
> Next, I tried to fumble my way through making an O'Caml version of
> this iterative algorithm, but I failed due to my lack of knowledge
> about this language.  (I hesitate to print the tutorial, because
> that's a lot of paper -- I wish the tutorial were available in HTML.
> I just may have to print it, though.)
> 
The first thing you should learn about is "tail-recursion".  This is
a form of recursion that saves some state between iterations so that
you don't have to recompute values.  For example, a tail-recursive
version of the fibonacci function could be:

     let rec fib_aux n result next =
          if n = 0 then result
               else fib_aux (n-1) (result+next) result;;

     let fib n =
         if n < 2 then 1 
              else fib_aux n 1 1;;

     let main () =
         let arg = int_of_string Sys.argv.(1) in
         print_int(fib arg);
         print_newline();
         exit 0;;

     main ();;
 
This is quite a bit faster than the pure-recursive version on my
system.

Let me know if it works for you.

Thanks,

-Brent