Re: CAS, Lambda Calculus, Continuation and Functional Programming

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

  • Next message: Alec Mihailovs: "Re: A day of a CAS super-hero" 
    Date: 18 Mar 2005 20:55:15 -0500

    Joachim Durchholz <jo@durchholz.org> writes:

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

    Ah, I see, that makes sense. Thank you.

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

    Well, it can eliminate destructors whose purpose is to free memory.
    Destructors that (say) close file handles remain an issue.

    But that's not what I meant. I meant that when you do a tail call, the
    stack frame of the callee might be of different size than the stack
    frame of the caller, so the tail call might need to allocate some space
    on the stack. But if you have GC, and "stack" frames are actually heap
    allocated, this becomes easier. True?

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

    Hmm. The debugger issue. I'd like to trace back my calls, but I might
    also want to trace back through 'while' loops in an imperative
    language. For that matter, I might like backward execution... ;-)

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

    Sorry, but I don't follow you here. (I'm being language-lawyerly in
    this part, not practical.) If the thing you describe runs out of
    memory, what does that prove, in a formal sense? Maybe the
    implementation does not eliminate tail calls. Or, maybe, it just ran
    out of memory for some other reason. How do we know?

    - Bob

  • Next message: Alec Mihailovs: "Re: A day of a CAS super-hero"

    Relevant Pages

    • Re: Why my application(exe) exit without any information
      ... It mean no exception dialog,no memory illegal access ... Stack corruption is one of the most typical reasons, ... Unhandled C++ exception ...
      (microsoft.public.vc.debugger)
    • Re: How to troubleshoot bugchecks on my own?
      ... To confirm, I would extract the exception record, from the stack, ... memory errors are close to impossible. ... You wrote "- to use verifier ON for suspicious driver". ...
      (microsoft.public.win32.programmer.kernel)
    • Controlled types and exception safety
      ... I can classify the stack's operations by assigning them any of the above four levels, so that I know what can be expected when an exception is thrown for any reason (like inability to allocate more memory, or alike). ... For example, if the Push method of the stack gives me the strong guarantee, then I *know* that by calling this method either the new element will be appended to the stack, or the stack will remain unchanged, so that even if the exception is thrown, I don't have to worry about the stack's internal consistency. ... Since stack can be a dynamic data structure, assigning one stack object to another may involve destroying one existing data structure *and* creating a new one in its place. ...
      (comp.lang.ada)
    • Re: Controlled types and exception safety
      ... exception safety. ... Interestingly, in the Stack example there is no performance tradeoff - you *have* to do both cleanup and state duplication anyway, no matter what's the provided guarantee, but by introducing the temporary object I can force the specific *order* of those operations (first duplicate, then clean up) that gives me the strong guarantee - which means commit-or-rollback. ... OK, you can argue that in this scheme you have to first create a duplicate and then destroy the old state, which means that for some short period of time we consume more memory ) and that can result in lower cache hit rates and this kind of stuff. ...
      (comp.lang.ada)
    • Re: Weird 0x80010105 error
      ... This is memory corruption at its best. ... code is not in the call stack. ... I will try to run my server in the debugger to ... >> I think it's very weird that the exception doesn't occur when I'm ...
      (microsoft.public.vc.atl)