Re: Tail Call Optimization in guile

[Ludovic Courtès]

Hi,

address@hidden writes:

> I'm a little confused. The Wikipedia entry on guile has a vague statement 
> about
> how guile can't do tail call optimization in functions that use C
> code.

First, we have to differentiate between tail call and _recursive  tail
call---one usually cares more about the latter.  Recursive tail calls
are always optimized in Scheme code, as mandated by R5RS (Section 3.5).
For example:

  (let loop ((x 10))
    (if (<= x 0)
        #t
        (loop (1+ x))))

Guile optimizes the tail-recursive call to `loop', so iterations of the
above loop do not consume any additional stack space.

Now, non-recursive tail calls certainly be optimized when the called
function is implemented in C.  For instance:

  (define (foo x)
    (1+ x))

Here, `1+' is implemented in C, so the call to `1+' is not
tail-optimized (i.e., it consumes additional stack space).  Hmm,
actually, if the C compiler used to compile Guile implements tail-call
optimization, then even such code might be tail-optimized.

I'm not sure whether tail calls to Scheme-implemented procedures are
optimized.

Anyway, the important point is that Guile does optimize tail-recursive
calls, fortunately.

> Wikipedia also says that guile has difficulties with call/cc, and I assume 
> this
> is a similar issue, calling a continuation that was captured in scheme code
> that was called from a different C function than the currently running scheme
> code. Right? (confusing sentence, I know!)

AFAIK `call/cc' works "as expected" in Guile.  The only problem is that
it is inefficient because the whole call stack has to be copied, as
mentioned in the manual.

Thanks,
Ludovic.