Re: CAS, Lambda Calculus, Continuation and Functional Programming

From: Joachim Durchholz (jo_at_durchholz.org)
Date: 03/18/05 

Date: Fri, 18 Mar 2005 17:21:18 +0100

Robert A Duff wrote:

> Joachim Durchholz <jo@durchholz.org> writes:
>
>>> Is there anything that would
>>> prohibit using the same optimizations in an imperative language.
>>
>>Partly. Imperative aspects of a language may require global program
>>analysis to make sure that a tail call can indeed be eliminated, and
>>that makes tail call elimination less attractive for compiler writers.
>>I don't recall the full range of things that can prevent tail call
>>elimination, but the two that I do recall are exception handling and
>>setjmp/getjmp. I dimly recall that there were also issues with
>>destructors in C++, but I may be confusing things here.
>
> I don't know why exception handling should prevent tail-call
> elimination. Would someone care to enlighten me?
>
> Setjmp/longjmp is similar to exception handling. And destructors
> require something like an implicit exception handler -- when an
> exception occurs, catch it, call the destructor, and then re-raise the
> same exception. So these all seem like the same issue.

On second thinking, I recalled what the issue was.

In all cases, there's some implicit action done in a function. Those
that catch exceptions must unwind the exception catching machinery,
setjmp places data on the stack that must be unwound at longjmp or
return time, and if a local object is constructed, it must be destructed
on function exit.

These mechanisms are all nice and dandy, but they add some action after
the end of the last explicit instruction - and the tail call isn't a
tail call anymore.

> I think garbage collection makes tail call elimination easier,
> and many imperative languages don't have GC, so that might be
> part of the problem.

It would eliminate the destructor problems. The rest would remain.

> In any case, I know that some compilers for some imperative languages do
> tail-call elimination in some cases.

It has been tried on gcc. With rather limited results - the majority of
tail calls couldn't be optimized out. Given that tail call elmination
doesn't play nice with debuggers, it's probably not very attractive for
the gcc folks now...

> On the other hand, some functional languages *require* tail-call
> elimination. Is this really a formal requirement? I mean, can one
> write a test case that fails if and only if the compiler doesn't
> eliminate tail calls?

Yes, easily. Make a function that allocates a lot of stack memory (some
local variable with a megabyte of memory or so). Also add a counter
that's well beyond the disk size of contemporary computers (say, a
million - that will give a total stack requirement of a terabyte - well,
a billion would be safer), that's decremented on each operation, and
goes to zero finally.
Allocation should be fast, so a local array would be best (in languages
that support arrays).

Regards,
Jo

Relevant Pages

  • Re: Iteration in lisp
    ... Nearly all compilers seem to do tail call elimination ... My remarks were directed not any user making a properly informed ... Common Lisp, I generally mean "any Common Lisp"; when I want to talk about ...
    (comp.lang.lisp)
  • Re: Was not making tail recursion elmination a mistake?
    ... >> I have recently been annoyeed by the fact that tail recursion ... >> elimination and must use loops or some simular structue. ... > have been an optional feature. ...
    (comp.lang.lisp)
  • Mandatory tail call elimination (was: Needed features in upcoming standards to support VMs & lan
    ... Note that I've never written more than a toy compiler, ... Do anyone know of a language with mandatory tail call elimination but no ... An ordinary function call never has _TailCall semantics. ...
    (comp.std.c)
  • Re: Iteration in lisp
    ... recursive function can run out of stack since CL does not guarantee ... In the absence of guaranteed tail call elimination, ...
    (comp.lang.lisp)
  • Re: CAS, Lambda Calculus, Continuation and Functional Programming
    ... > that catch exceptions must unwind the exception catching machinery, ... > tail call anymore. ... it can eliminate destructors whose purpose is to free memory. ... stack frame of the callee might be of different size than the stack ...
    (sci.math.symbolic)