Re: Proper Tail Recursive C++

Wilco Dijkstra <Wilco.Dijkstra@armltd.co.uk>
1 Mar 1997 21:43:01 -0500

          From comp.compilers

Related articles
[2 earlier articles]
Re: Proper Tail Recursive C++ hbaker@netcom.com (1997-02-22)
Re: Proper Tail Recursive C++ will@ccs.neu.edu (William D Clinger) (1997-02-23)
Re: Proper Tail Recursive C++ fjh@mundook.cs.mu.OZ.AU (1997-02-23)
Re: Proper Tail Recursive C++ bothner@cygnus.com (1997-02-23)
Re: Proper Tail Recursive C++ andy@wonderworks.co.uk (Andy Armstrong) (1997-02-27)
Re: Proper Tail Recursive C++ gary@wheel.tiac.net (1997-03-01)
Re: Proper Tail Recursive C++ Wilco.Dijkstra@armltd.co.uk (Wilco Dijkstra) (1997-03-01)
Re: Proper Tail Recursive C++ hbaker@netcom.com (1997-03-05)
Re: Proper Tail Recursive C++ njl@cyberpass.net (1997-03-09)
Re: Proper Tail Recursive C++ hbaker@netcom.com (1997-03-13)
Re: Proper Tail Recursive C++ fjh@murlibobo.cs.mu.OZ.AU (1997-03-13)
Re: Proper Tail Recursive C++ ramsdell@linus.mitre.org (1997-03-16)
Re: Proper Tail Recursive C++ danwang@atomic.CS.Princeton.EDU (1997-03-18)
[2 later articles]
| List of all articles for this month |

From: Wilco Dijkstra <Wilco.Dijkstra@armltd.co.uk>
Newsgroups: comp.compilers
Date: 1 Mar 1997 21:43:01 -0500
Organization: ARM Ltd
References: 97-02-111 97-02-131 97-02-141
Keywords: C++, optimize



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]


--


Post a followup to this message

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