Re: Idiom for tail recursion?

["John B. Matthews" <nospam@nospam.invalid>]

In article 
<f7ffb7bc-88c9-4c7a-9a79-e08c1d9736a3@v2g2000vbb.googlegroups.com>,
 Gene <gene.ressler@gmail.com> wrote:

> On May 31, 5:04 pm, jpwoodruff <jpwoodr...@gmail.com> wrote:
> > To entertain myself, I'm making a program that implements the DEVS
> > specification for discrete event simulation.  The book I'm studying
> > describes a reference implementation in Scheme.
> >
> > The program proceeds by passing a series of messages among objects
> > that are instances of only a couple class hierarchies.  The messages
> > cycle among the objects in (fairly convoluted) cycles of mutually
> > recursive dispatching calls.  Simulation time advances as the program
> > traverses the outermost cycles of activation.
> >
> > In scheme, the functions are tail-recursive - the last call of each of
> > the respective mutually recursive procedures does the recurse.  This
> > paradigm is crystal clear in that language and the implementation
> > doesn't grow the stack.
> >
> > But in Ada it appears that I'm going to have a stack of calls that
> > won't return.  I guess the program will quit running when I raise an
> > exception for that purpose.  Or maybe it won't halt, who knows :-}.
> >
> > I most definitely do not see a transform to an iterative algorithm.
> >
> > So the question: what idiom comes fairly close to the flavor of the
> > tail-recursion and won't blow stack?
> 
> A few of the standard algorithms texts (I happen to recall Horowitz
> and Sahni, but there are others) talk about how to replace recursive
> calls with jumps and an explicit stack.  The stack isn't needed for
> tail calls.  But I've never seen a general methodology that works with
> mutually recursive sets of procedures. You'd need to inline bodies
> until you're down to one simply recursive function. This would be a
> mess.
> 
> Another possibility is to use a trampoline.

Excellent! I had overlooked the mutual recursion aspect of the problem 
when responding. Thank you for your clear example.

Minor edit:

>   function A return Call_Inst is begin ... return Call_B; end A;
>   function B return Call_Inst is begin ... return Call_C; end B;
>   function C return Call_Inst is begin ... return Call_A; end C;

[...]

-- 
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>