Re: Proper Tail Recursive C++

William D Clinger wrote:
> [ sample of a tail recursive routine ]


<snip>


> int f (int n) {
> int A[1000];
> A[0] = n;
> A[999] = n;
> return g (A); // tail-recursive call to g
> }


This function cannot translate the call to g tail-recursively, because
the array A is still alive on entry of g. The ARM C++ compiler
generates:


f__Fi
                STMDB sp!,{lr}
                SUB sp,sp,#&fa0
                STR a1,[sp,#0]
                STR a1,[sp,#&f9c]
                MOV a1,sp
                BL g__FPi
                ADD sp,sp,#&fa0
                LDMIA sp!,{pc}


In order to be able to generate a tail-recursive call to f, a C/C++
compiler needs to know the following:


A It is OK to access data *below* the current stack frame. In other
    words, the stack is not used by interrupts, exception handlers, etc.


B The function which is called, nor it's decendants do use the stack in
    a way which may overwrite the live parts of the array. Or, simply,
    the function which is called must be a simple leaf function (doesn't
    use stack).


For many runtime systems A can never hold, and B is simple too hard to
check at compile time (except for the case that g was before f in the
source). Only if the above statements are true f can be translated to:


f__Fi
                SUB sp,sp,#&fa0
                STR a1,[sp,#0]
                STR a1,[sp,#&f9c]
                MOV a1,sp
                ADD sp,sp,#&fa0
                B g__FPi


Your Scheme example is most probably not 'proper tail-recursion', but
more an example of garbage collection: function f marks the vector as
collectable just before it calls f, causing the parameter A to be the
only reference to the vector. Thus the program will never run out of
memory as A will be freed before the next recursive call to f.
C++ allows you to do the same: you just have to allocate A on the heap
and use an explicit destructor in g.


--
-----------------------------------------------------------------------
Wilco Dijkstra Advanced RISC Machines Ltd
Software Engineer Fulbourn Road
Wilco.Dijkstra@armltd.co.uk Cherry Hinton, CB1 4JN
Phone: +44 1223 400 518 Cambridge, UK
[The Scheme example is indeed tail recursive, because there's no new stack
frame allocated for the tail call, so the call stack doesn't grow. It's
quite true that it's a lot easier to optimize tail recursion if you can
count on a garbage collector to do your deallocations. -John]


--

Return to the comp.compilers page.
Search the comp.compilers archives again.