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 TAA04234 for caml-red; Thu, 27 Jul 2000 19:41:15 +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 TAA03965 for <caml-list@pauillac.inria.fr>; Wed, 26 Jul 2000 19:48:13 +0200 (MET DST)
Received: from yukari.lineo.com (yukari.lineo.com [207.179.37.69])
	by concorde.inria.fr (8.10.0/8.10.0) with ESMTP id e6QHmAD17997
	for <caml-list@inria.fr>; Wed, 26 Jul 2000 19:48:11 +0200 (MET DST)
Received: by yukari.lineo.com (Postfix, from userid 440)
	id E96889B020; Wed, 26 Jul 2000 11:51:52 -0600 (MDT)
Date: Wed, 26 Jul 2000 11:51:52 -0600
From: John BEPPU <beppu@lineo.com>
To: caml-list@inria.fr
Subject: help an o'caml beginner
Message-ID: <20000726115152.A6102@yukari.lineo.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
User-Agent: Mutt/1.2i
Sender: weis@pauillac.inria.fr

Hi.

Recently, there have been discussions about functional programming
on sites like slashdot, kuro5hin, and advogato.  This made me want
to investigate functional languages further.  I decided on O'Caml,
because there was a guy on slashdot who was very enthusiastic about
Standard ML.  There was also mention of O'Caml which was said to be 
a free dialect of ML and people generally had good things to say,
so I checked out the home page.  I happen to be a fan of the other
camel (Perl), but I hope you don't hold that against me.  ;-)

I've been trying to practice funcional techniques in Perl (mostly
by using recursion more often than I normally would and using
closures to make iterators).  However, I felt that I would not ever 
get a good understanding of the functional way if I didn't program 
in a (more) pure language.  That's another reason why I'm here.

Anyway, I hope you guys can help me.  

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 ();;

I wrote a C implementation of the same recursive algorithm. 

    #include <stdio.h>

    int fib(int n)
    {
        if (n < 2) {
            return 1;
        } else {
            return fib(n - 1) + fib(n - 2);
        }
    }

    int main(char *argc, char **argv)
    {
        printf("%d\n", fib(atoi(argv[1])));
        return 0;
    }

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.

Next, I wrote an iterative C version.

    #include <stdio.h>

    int fib(int n)
    {
        int val = 2;
        int n1 = 2;
        int n2 = 1;
        int i;
        if (n < 2)
            return n;

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

    int main(char *argc, char **argv)
    {
        printf("%d\n", fib(atoi(argv[1])));
        return 0;
    }

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.)


>>>
If anyone out there could implement an O'Caml fibonacci number
generator that doesn't make redundant calculations, I would really
appreciate it.  I just need something to study.
>>>


I wrote a recursive Perl version that doesn't make redundant
calculations, and I'd be interested to see how different in
structure an O'Caml version would be.

    #!/usr/bin/perl -w

    use strict;

    sub fib_pair {
        my $n = shift;
        my @seq;
        if ($n < 2) {
            @seq = (1, 1);
        } else {
            @seq = fib_pair($n - 1);
            @seq = ($seq[1], $seq[0] + $seq[1]);
        }
        return @seq;
    }

    sub fib {
        my $n = shift;
        return (fib_pair($n))[1];
    }

    print fib($ARGV[0]), "\n";


Thanks for reading this far.  I understand that English is a foreign
language to many of you, and I'm terribly sorry I had to write so
much.