Re: CAS, Lambda Calculus, Continuation and Functional Programming

From: Robert A Duff (bobduff_at_shell01.TheWorld.com)
Date: 03/16/05 

Date: 16 Mar 2005 13:55:05 -0500

Joachim Durchholz <jo@durchholz.org> writes:

> Recursion that's equivalent to loops can always be optimized back into
                                           ^^^^^^
> loop form when it comes to emitting code. This is not a problem with any
> single functional programming language that I know.
>
> The technique is called "tail call elimination", in case you wish to
> google for it.

I don't think that's *quite* true. I agree that tail calls can be
eliminated, and that tail calls are equivalent to loops.
But there are recursive algorithms that are not tail recursive,
but that are equivalent to loops. For example, the most natural
(IMHO) way to write the "factorial" function is recursive, but
not tail recursive. It is equivalent to a less-readable
tail-recursive version, which is in turn equivalent to a loop.

Sorry if that sounds like nitpicking, but I'm curious:
Which compilers can optimize that "most natural" implementation
of factorial into a loop? And to what extent can compilers
optimize non-tail-recursion into loops? Obviously not always
(a tree walk, for example, fundamentally requires keeping track
of where you've been, which requires a stack of some sort).

> > 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.

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.

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

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? How can such a test case distinguish between
that, and simply using up too much memory (given that most language
standards don't say anything about how much memory any given feature
will use)?

- Bob

Relevant Pages

  • Re: CAS, Lambda Calculus, Continuation and Functional Programming
    ... >>Recursion that's equivalent to loops can always be optimized back into ... and that tail calls are equivalent to loops. ... If a loop is formulated in a recursive way then ... >> that makes tail call elimination less attractive for compiler writers. ...
    (sci.math.symbolic)
  • Re: Term Rewriting vs. Functional Programming
    ... > programs assume that tail recursion runs in constant space. ... > tail call elimination. ... Reasonable implementations, of course, ... > fun loop b = loop ...
    (comp.lang.functional)
  • Re: OT: Obama sets "top salary" for Executives that take Stimulus money
    ... we would suggest that a National Easy Language Week be ... We would therefore urge the elimination of al unesesary ... Sins bai this taim it would hav ... ben four years sins anywun had used the leter "c", ...
    (rec.gambling.poker)
  • Re: Letter to US Sen. Byron Dorgan re unpaid overtime
    ... >> considered to be a convenience by those who use the C language. ... I make no claims to being a VB.NET programmer. ... Ritchie SCREWED UP in designing the for loop because ... I do not believe that you are capable of writing a conforming C compiler. ...
    (comp.programming)
  • Re: Letter to US Sen. Byron Dorgan re unpaid overtime
    ... > Hey, idiot, read my lips - the CONDITION is evaluated before each loop ... expressed my hope that you actually know the sequence of evaluations ... inappropriately with commercial promotion of the C language when I ... Programming Style: code what you mean. ...
    (comp.programming)