Strict<->Lazy?

[Richard A. O'Keefe]

Siegfried Gonzi <siegfried.gonzi@kfunigraz.ac.at> wrote
	
	Yesterday I wrote a little program for calculating the fibonacci
	numbers. I do know from Maple that, e.g. evaluating the fibonacci number
	40 is done in "real time" (and also e.g. the fibonacci number 100 is
	done in real time; be aware that this is not a built in function). And
	also Omikron Basic 6.3 (Basic for the Macintosh) makes the job in "real
	time". And then I was shocked, because Clean requires 30sec! (and
	curiously calculating the fibonacci number with real number is not
	faster; the opposite is the case; maybe this is due to the fact that my
	Macintosh 603e processor is good for integers).
	
I was a bit surprised by this, so I tried it on a SPARCstation 5 running
Solaris 2.6.  What I found was that Clean was *faster* than C:

8.0 sec   C version (cc -native -fast -xO5)
5.7 sec   Clean version (clm version 1.3.1)

The code was

    #include <stdio.h>

    unsigned long fib(int n) {
        return n < 2 ? 1 : fib(n-1) + fib(n-2);
    }

    int main(void) {
	int n = 35;
	printf("fib(%d) = %lu\n", n, fib(n));
	return 0;
    }

for the C version and

    module fib
    import StdEnv

    fib :: !Int -> Int
    fib n = if (n < 2) 1 (fib (n-1) + fib (n-2))

    Start :: Int
    Start = fib 35

for the Clean version.

	After that I printed out the "Clean Language Report". I found in it that
	it is possible to make a "strict" evaluation. But calculating the
	fibonacci numbers in a strict fashion is n o t faster!
	
Well, no, because for this program, if you erase the function type and
strictness declarations, the compiler automatically infers exactly the
same declarations again.

	I often read benchmarks that Clean is not much slower than C. And I am
	not a friend of benchmarking  into the last detail. But what the people
	do in their benchmarks?

The question is, what did YOU do?  Because when I tried it, Clean wasn't
slower than C, it was faster!

	But if someone needs really fibonacci numbers in a program how
	can he wait 30sec!

If someone really needs Fibonacci numbers in a program, they certainly
won't use the naive exponential time code:  they'll use the O(1) method.