Mailing list for all users of the OCaml language and system.
 help / color / mirror / Atom feed
* help an o'caml beginner
@ 2000-07-26 17:51 John BEPPU
  2000-07-27 18:47 ` Alain Frisch
                   ` (5 more replies)
  0 siblings, 6 replies; 17+ messages in thread
From: John BEPPU @ 2000-07-26 17:51 UTC (permalink / raw)
  To: caml-list

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.



^ permalink raw reply	[flat|nested] 17+ messages in thread
* RE: help an o'caml beginner
@ 2000-07-27 18:24 Brent Fulgham
  0 siblings, 0 replies; 17+ messages in thread
From: Brent Fulgham @ 2000-07-27 18:24 UTC (permalink / raw)
  To: John BEPPU, caml-list

> 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 



^ permalink raw reply	[flat|nested] 17+ messages in thread
* re: help an o'caml beginner
@ 2000-07-27 18:43 Lenny Gray
  0 siblings, 0 replies; 17+ messages in thread
From: Lenny Gray @ 2000-07-27 18:43 UTC (permalink / raw)
  To: 'caml-list@inria.fr'

At 11:51 7/26/2000 -0600, John BEPPU wrote:
>
>  ...
>
>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.

Of course a trivial approach would be to accept the fact
that O'Caml _has_ true assignable variables, via references.

However, since you sound like you want the _functional_
answer, the insight you're looking for is:

let rec  f v1 v2 i  =  if i=0 then v2   else f v2 (v1+v2) (i-1);;

then:  f 0 1 0  == 1
       f 0 1 1  == 1
       f 0 1 2  == 2
       ...
       f 0 1 10 == 89


- Lenny -



^ permalink raw reply	[flat|nested] 17+ messages in thread
* Re: help an o'caml beginner
@ 2000-07-27 22:50 John R Harrison
  2000-07-28 12:49 ` John BEPPU
  0 siblings, 1 reply; 17+ messages in thread
From: John R Harrison @ 2000-07-27 22:50 UTC (permalink / raw)
  To: caml-list; +Cc: John Harrison


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.



^ permalink raw reply	[flat|nested] 17+ messages in thread
* RE: help an o'caml beginner
@ 2000-08-02 17:28 Brent Fulgham
  0 siblings, 0 replies; 17+ messages in thread
From: Brent Fulgham @ 2000-08-02 17:28 UTC (permalink / raw)
  To: John BEPPU; +Cc: caml-list

> > <question type="stupid">
> >     What does the keyword "in" mean?
> > </question>
> 
> It is just a keyword to prevent ambiguities when writing 
> expressions. E.g.:
> 
>   let x = y z ...
> 
> is not the same as
> 
>   let x = y in
>   z ...
>

It's a way to "hide" functions inside of other functions.
Like in the tail-recursive case I posted, I cluttered the
namespace with the second "internal" recursive function.
In a real program it is better to hide that "internal" function
from the outside world:

let firstFunction x = blah blah
  in
     secondFunction y = blah blah (uses firstFunction);;

Thanks,

-Brent



^ permalink raw reply	[flat|nested] 17+ messages in thread
end of thread, other threads:[~2000-08-03 13:14 UTC | newest]

Thread overview: 17+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2000-07-26 17:51 help an o'caml beginner John BEPPU
2000-07-27 18:47 ` Alain Frisch
2000-07-27 18:56 ` Markus Mottl
2000-07-29 17:03   ` John BEPPU
2000-07-29 17:23     ` Markus Mottl
2000-07-31  7:11   ` Vitaly Lugovsky
2000-07-31  8:43     ` Markus Mottl
2000-08-02 16:58     ` Printable Caml manual Walid Taha
2000-07-27 18:57 ` help an o'caml beginner Remi VANICAT
2000-07-27 19:08 ` Jean-Christophe Filliatre
2000-07-27 21:31 ` Laurent Chéno
2000-07-27 23:47 ` Michel Quercia
2000-07-27 18:24 Brent Fulgham
2000-07-27 18:43 Lenny Gray
2000-07-27 22:50 John R Harrison
2000-07-28 12:49 ` John BEPPU
2000-08-02 17:28 Brent Fulgham

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox