Tail Call Optimization in guile

Tail Call Optimization in guile

[jjh02]

Hi,

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. If this
is true, this seems like a major, crippling constraint, since most non-trivial
use of guile as an extension language will involve calling native code, and
many simple functions aren't feasible without tail call optimization. But the
guile documentation doesn't seem to mention this drawback anywhere, and I know
that other scheme to C interfaces, like gambit-c, have no problem with this.

The conclusion I've drawn is that the Wikipedia article is far too vague, and
that in fact guile can optimize tail calls in all cases except when C code and
scheme code are mutually recursive; that is, scheme code calls C code which
calls the scheme code again. This makes much more sense to me. Is this correct?
Are there other situations where guile has trouble with tail calls?

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!)

The guile documentation has a chapter called "Functional and performance
constraints," which is currently completely empty. I assume it is meant to
cover issues such as these.  If somebody can point me towards some answers,
I'll go and set the record straight on Wikipedia.

Thanks,

Josh


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-user

Re: Tail Call Optimization in guile

[Ludovic Courtès]

Hi,

jjh02@hampshire.edu 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.



_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-user