Version française
Home     About     Download     Resources     Contact us    

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

Browse thread
[Caml-list] Does Caml have slow arithmetics ?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-07-08 (14:54)
From: Brian Hurt <bhurt@s...>
Subject: Re: [Caml-list] Does Caml have slow arithmetics ?
On Thu, 8 Jul 2004, Andreas Rossberg wrote:

> David Brown wrote:
> > 
> > In some functional languages (Scheme, specifically), tail recursion is
> > required to be implemented iteratively.  It is a common enough idiom,
> > and easy enough to implement, that it is generally done in functional
> > languages.  In fact, gcc does it in C, with enough optimization.
> The latter is, to a certain extent, a myth.
> First, you have to distinguish between simple tail *recursion*, and the 
> much more general concept of tail *call*. I believe Scheme requires to 
> fully optimize the latter, and so it is done by all decent FPL 
> implementations. GCC does not do that, already falling short of mutually 
> recursive functions, IIRC.

GCC has started optimizing tail calls in 3.x.  

I compiled:

int fib(int a, int b, int n) {
    if (n <= 1) {
        return b;
    } else {
        return fib(b, a+b, n-1);

with gcc 3.2.2 -O2, and got:

.globl fib
        .type   fib,@function
        pushl   %ebp
        movl    %esp, %ebp
        movl    12(%ebp), %ecx
        pushl   %ebx
        movl    16(%ebp), %edx
        movl    8(%ebp), %ebx
        .p2align 2,,3
        cmpl    $1, %edx
        jle     .L5
        leal    (%ecx,%ebx), %eax
        decl    %edx
        movl    %ecx, %ebx
        movl    %eax, %ecx
        jmp     .L4
        movl    %ecx, %eax
        popl    %ebx

Notice that it's turned the tail call recursion into a loop.  I don't 
recall it doing this back in 2.95 or 2.96, so it's a pretty recent 
improvement, but it does now exist.

What it's limits are, I haven't determined, but it does exist.

"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: