help an o'caml beginner

help an o'caml beginner

[John BEPPU]

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.

Re: help an o'caml beginner

[Alain Frisch]

On Wed, 26 Jul 2000, 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.
> >>>

(I guess there will be many answers ..)

Here is a solution:

let fibo n =
  let rec aux last x i =    (* x is u_i; last is u_{i-1} *)
     if (i = n) then x
     else aux x (x + last) (i + 1)
  in
  if (n = 0) then 1 else
  aux 1 1 1


> 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.
> 
>     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;
>     }

Well, this function is not tail-recursive (the recursive call
can't be implemented as a jump). I didn't try it, but I am pretty sure
the OCaml version will be more efficient.

-- 
Alain Frisch

Re: help an o'caml beginner

[Markus Mottl]

On Wed, 26 Jul 2000, 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.

Here a collection of three fibonacci algorithms. The first one is the
"simple-minded" one, the second uses tail-recursion, which removes some
redundant computations, too. The third one - well, try it out ;-)

---------------------------------------------------------------------------
let rec fib1 = function
  | n when n <= 1 -> 1
  | n -> fib1 (n-1) + fib1 (n-2)

let fib2 n =
  let rec fib2_aux n2 n1 = function
    | m when m = n -> n1
    | m -> fib2_aux n1 (n2+n1) (m+1) in
  if n <= 1 then 1 else fib2_aux 1 2 2

let rec fib3_aux = function
  | 0 -> 1, 0
  | 1 -> 0, 1
  | n ->
      let k = n/2 in
      let a, b = fib3_aux k in
      let aa = a*a and bb = b*b and ab2 = 2*a*b in
      let ab2bb = ab2 + bb in
      if 2*k = n then aa + bb, ab2bb
      else ab2bb, ab2bb + aa + bb

let fib3 n =
  if n <= 1 then 1
  else
    let k = n/2 in
    let a, b = fib3_aux k in
    let ab = a + b in
    if 2*k = n then ab*ab + b*b
    else ab*ab + 2*b*ab

let _ = Printf.printf "%d\n" (fib3 1000000)
---------------------------------------------------------------------------

Btw., algorithms 2 + 3 can both be generated by automatic program
transformation. If you want to learn more about this, read:

@Article{Pettorossi-Proietti96,
  key =          "Pettorossi \& Proietti",
  author =       "Alberto Pettorossi and Maurizio Proietti",
  title =        "Rules and Strategies for Transforming Functional and
                  Logic Programs",
  journal =      "ACMCS",
  volume =       "28",
  number =       "2",
  pages =        "360--414",
  month =        jun,
  year =         "1996",
  annote =       "Many references.",
}

Best regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl

Re: help an o'caml beginner

[Remi VANICAT]

John BEPPU <beppu@lineo.com> writes:

> Hi.
> 

[...]


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

it easy : you have to use an auxiliary function :

let fib n =
  let rec aux n n1 n2 =
      if n <= 2 then (n1 + n2) 
      else aux (n - 1) (n1 + n2) n1 in
  if (n < 3) then 1 else aux (n - 1) 1 1

(an exact translation of your c function would be :
let fib n =
   if (n < 2) then n
   else 
     let rec aux i val n1 n2 =
        if i < n then val 
        else aux (i + 1) (n1 + n2) (n1 + n2) n1

the idea here is for each variable of the c function have an argument
to the recursive caml function, and, instead of changing the variable,
to call the aux function with the new value.

Then I've done some clean up and removal of unused arguments)


-- 
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat

Re: help an o'caml beginner

[Jean-Christophe Filliatre]

In his message of Wed July 26, 2000, John BEPPU writes: 
> 
> Next, I wrote an iterative C version.
> [...]
> This was much faster than any of the recursive versions, because it 
> doesn't have to recompute the same values over and over again.  
> [...]
> 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.

First,  you  can  write it  exactly  as  in  C, since  ocaml  supports
references and imperative programming constructs.

But there  is an even more direct  way of writing it,  in a functional
way, which could be the following:

======================================================================
let rec fib_aux v1 v2 n =
  if n = 0 then
    v1
  else
    fib_aux v2 (v1 + v2) (pred n)

let fib n = fib_aux 0 1 n
======================================================================

(In a general way, a C  loop becomes a recursive function with as many
arguments as variables involved in the loop.)

By  the way,  if you  are interested  in computing  Fibonacci numbers,
there are even more efficient ways to do that. Here is a pointer (code
by Xavier Urbain, documentation in French):

	http://www.lri.fr/~filliatr/pub/lucas.ps

-- 
Jean-Christophe Filliatre    
  Computer Science Laboratory   Phone (650) 859-5173
  SRI International             FAX   (650) 859-2844
  333 Ravenswood Ave.           email filliatr@csl.sri.com
  Menlo Park, CA 94025, USA     web   http://www.csl.sri.com/~filliatr

  

Re: help an o'caml beginner

[Laurent Chéno]

Le 26/07/00 à 11:51, beppu@lineo.com (John BEPPU) écrivait :

> Hi.

--- Please excuse my poor english --- 
> 
> 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.  
> 

the basic translation can be for example :

let fib n =
    let val = ref 2
    and n1  = ref 2
    and n2  = ref 1
    in
    if n < 2 then n
    else for i = 2 to n - 1 do
            val := !n1 + !n2 ;
            n2 := !n1 ;
            n1 := !val
         done ;
         !val ;;

But I prefer a recursive and efficient version like this :

let fib n =
    let rec fibaux n p q =
        if n = 0 then p
        else fibaux (n - 1) q (p + q)
    in
    fibaux n 0 1 ;;

this is a terminal recursion : try it !

-- 
Laurent Chéno                   Paris (France)
<http://pauillac.inria.fr/~cheno/>
-- 

Re: help an o'caml beginner

[Michel Quercia]

Le Wed, 26 Jul 2000, John BEPPU a écrit :
> I tried out the recursive fibonacci number program
> ...
> 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.

Below are three translations of your iterative C code :

------------------------------------------------------------
(* iterative Caml code *)
let fib(n) =
  let a = ref(1) and b = ref(1) in
  for i=2 to n do
    let x = !a + !b in
    a := !b;
    b := x
  done;
  !b
;;

-------------------------------------------------------------
(* recursive Caml code, fib2(n) returns (fib(n-1),fib(n)) *)
let rec fib2(n) = 
  if n <= 1 then (n,1)
  else let (a,b) = fib2(n-1) in (b,a+b)
;;

let fib(n) = let (_,x) = fib2(n) in x;;

-------------------------------------------------------------
(* tail-recursive Caml code, fib3 a b n computes a*fib(n) + b*fib(n-1) *)
let rec fib3 a b n = if n <= 1 then a + b*n else fib3 (a+b) a (n-1);;
let fib(n) = fib3 1 0 n;;
--------------------------------------------------------

Note that there are also divide-and-conquer algorithms for computing Fibonacci
numbers that achieve logarithmic computing time with respect to the input.

> I wish the tutorial were available in HTML.

There is atutorial included in the html documentation.

Regards,
-- 
Michel Quercia
23 rue de Montchapet, 21000 Dijon
http://pauillac.inria.fr/~quercia
mailto:quercia@cal.enst.fr

Re: help an o'caml beginner

[John BEPPU]

[  date  ] 2000/07/27 | Thursday | 08:56 PM
[ author ] Markus Mottl <mottl@miss.wu-wien.ac.at> 

> let rec fib3_aux = function
>   | 0 -> 1, 0
>   | 1 -> 0, 1
>   | n ->
>       let k = n/2 in
>       let a, b = fib3_aux k in
>       let aa = a*a and bb = b*b and ab2 = 2*a*b in
>       let ab2bb = ab2 + bb in
>       if 2*k = n then aa + bb, ab2bb
>       else ab2bb, ab2bb + aa + bb
> 
> let fib3 n =
>   if n <= 1 then 1
>   else
>     let k = n/2 in
>     let a, b = fib3_aux k in
>     let ab = a + b in
>     if 2*k = n then ab*ab + b*b
>     else ab*ab + 2*b*ab
> 
> let _ = Printf.printf "%d\n" (fib3 1000000)

This one was faster than the C version I posted.
The others were pretty close, too.  I continue to
be impressed.  I have a hard time believing fib3
was created by a mechanical transformation...  it
doesn't look anything like the other implementations.
I mean, I believe you as a matter of good faith, but
I'm amazed.

<question type="stupid">
    What does the keyword "in" mean?
</question>

> Btw., algorithms 2 + 3 can both be generated by automatic program
> transformation. If you want to learn more about this, read:

[snipped the reference...]

Thanks for the article...  I'll hit up the local universities,
and see if I can't track it down.

Re: help an o'caml beginner

[Markus Mottl]

On Sat, 29 Jul 2000, John BEPPU wrote:
> This one was faster than the C version I posted.

It should be, because it computes the fibonacci function in logarithmic
time, whereas the "usual" function does it in linear time (fib2). The
"simple" fibonacci implementation (fib1) is even worse: exponential time.

> The others were pretty close, too.  I continue to
> be impressed.  I have a hard time believing fib3
> was created by a mechanical transformation...  it
> doesn't look anything like the other implementations.
> I mean, I believe you as a matter of good faith, but
> I'm amazed.

No, the OCaml-code was not generated by automated transformations, but the
techniques are known and presented in the reference I mentioned - I just
took their "transformed" solution and translated it to OCaml. But it is
principally possible to apply such transformation techniques to functional
languages in general, because of their nice mathematical properties.

Since implementing such transformation systems correctly is a fairly
difficult task, there are not yet many around, and those that exist
normally operate on simplified languages to make life for researchers
easier...

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

Best regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl

Re: help an o'caml beginner

[Vitaly Lugovsky]

On Thu, 27 Jul 2000, Markus Mottl wrote:

> Btw., algorithms 2 + 3 can both be generated by automatic program
> transformation. If you want to learn more about this, read:
> 
> @Article{Pettorossi-Proietti96,

 Can this article be found on a WEB?

--

   V.S.Lugovsky aka Mauhuur (http://ontil.ihep.su/~vsl) (UIN=45482254)

Re: help an o'caml beginner

[Markus Mottl]

On Mon, 31 Jul 2000, Vitaly Lugovsky wrote:
> > @Article{Pettorossi-Proietti96,
> 
>  Can this article be found on a WEB?

Yes, it can:

  http://www.iasi.rm.cnr.it/~proietti/reports.html

Grab technical report 423 there: this is a nice overview of the topic...

Best regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl

Printable Caml manual

[Walid Taha]

Dear collegues,

I am writing an article about imperative programming, and would like to
use Caml for examples.  It's been a bit hard to work from the manuals on
the web (partly because the network keeps doing fishy things).  I would
really appreciate it if you could point me to a comprehensive manual that
covers things like IO, and which I can also easily print and put on my
desk (i.e., something in .ps or .dvi format, for example).

Also, I would certainly appreciate your input on the first draft when it
is ready, so let me know if you are interesting in a taking a look.

Many thanks in advance,

Walid.

RE: help an o'caml beginner

[Brent Fulgham]

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

Re: help an o'caml beginner

[John BEPPU]

Thanks to everyone who replied.

I did not expect this many replies, but I'm glad I got them.
It was probably an easy question for seasoned O'Caml programmers.
In the future, I hope my questions will be harder.  :-)

Re: help an o'caml beginner

[John R 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.

re: help an o'caml beginner

[Lenny Gray]

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 -

RE: help an o'caml beginner

[Brent Fulgham]

> 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