Re: OT: functional languages

["Eric G. Miller" <egm2@jps.net>]

On Mon, Jan 20, 2003 at 12:07:31PM -0500, David Z Maze wrote:
> Robert.Land@t-online.de (Robert Land) writes:
> > On Fri, Dec 13, 2002 at 11:23:43AM -0500, Derrick 'dman' Hudson wrote:
> >> "imperative" and "procedural" are the same thing, and C is a prime
> >> example.  It is such because the structure of a C program is a
> >> collection of procedures which start with "main".  Each procedure is a
> >> linear list of statements to be executed in order.
> >
> > Could you specify a "linear list" more clearly? - the 
> > contrary would be a "nonlinear list" which on the first
> > view seems to be self-contradictory.
> 
> For example, in C:
> 
> int fib(int n)
> {
>   if (n < 2)
>     return n;
>   return fib(n-2) + fib(n-1);
> }
> 
> the rules require that fib(n-2) is called before fib(n-1).  In Scheme:

This is incorrect.  There is no sequence point in the statement:

   return fib(n-2) + fib(n-1);

So, it's up to the implementation which side of the '+' is evaluated
first.
 
> (define (fib n)
>   (if (< n 2)
>     n
>     (+ (fib (- n 2)) (fib (- n 1)))))

The C and Scheme functions are essentially identical.  In C, statements
are executed in order.  I'm not too up on functional languages, but I
seem to recall they need special syntax to execute statements
sequentially.

That fib function is painfully slow via recursion and susceptible to
uncaught overflow in the C version (Scheme has big numbers built in).

#include <stdio.h>

unsigned long long
get_nth_fib (unsigned long long count)
{
    unsigned long long last2 = 0ULL;
    unsigned long long last  = 1ULL;
    unsigned long long cur   = count;
    unsigned long long i;

    if (count > 1) {
        for (i = 1; i < count; ++i) {
            cur = last + last2;
            if (cur < last) {
                fprintf (stderr, "get_nth_fib(%llu) overflows!\n", count);
                cur = 0UL;
                break;
            }
            last2 = last;
            last  = cur;
        }
    }
    return cur;
}

Less elegant, but much faster and more robust than the recursive C version.
A table look-up would be even faster up to some 'n' (say, 93 in this case).

-- 
echo ">gra.fcw@2ztr< eryyvZ .T pveR" | rot13 | reverse