This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

help an o'caml beginner
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2000-07-27 (17:41) From: John BEPPU Subject: help an o'caml beginner
```Hi.

Recently, there have been discussions about functional programming
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
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.

```