Idiom for tail recursion?

Idiom for tail recursion?

[jpwoodruff]

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?

John

Re: Idiom for tail recursion?

[John B. Matthews]

In article 
<814eff38-3e01-4f70-aeb7-48a1ae651dfc@h23g2000vbc.googlegroups.com>,
 jpwoodruff <jpwoodruff@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.

IIUC, Scheme compilers are required to optimize tail recursion using 
iteration [1], when the recursion occurs in a tail context [2].

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

If the functions are indeed tail-recursive, I'd think the 
conversion to iteration would be straightforward [3, 4].

> So the question: what idiom comes fairly close to the flavor of the 
> tail-recursion and won't blow stack?

[1]<http://en.wikipedia.org/wiki/Tail_recursion>
[2]<http://www.biglist.com/lists/dssslist/archives/199907/msg00389.html>
[3]<http://www.refactoring.com/catalog/replaceRecursionWithIteration.html>
[4]<http://rosettacode.org/wiki/Factorial_function#Ada>

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

Re: Idiom for tail recursion?

[Gene]

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.  If you have

procedure Main is

procedure A is begin ... B; end A;
procedure B is begin ... C; end B;
procedure C is begin ... A; end C;

begin
 A;
end Main;

you'd translate to

procedure Main is

  type Call_Inst is (Call_A, Call_B, Call C);

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

  Next_Call : Call_Inst := Call_A;
begin
  -- The trampoline...
  loop
    case Next_Call is
      when Call_A => Next_Call := A;
      when Call_B => Next_Call := B;
      when Call_C => Next_Call := C;
    end case;
  end loop;
end Main;

Re: Idiom for tail recursion?

[John B. Matthews]

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>

Re: Idiom for tail recursion?

[Jean-Pierre Rosen]

jpwoodruff a �crit :
> To entertain myself, I'm making a program that implements the DEVS
> specification for discrete event simulation. 
I understant that it's for entertainment, but you can be interested in
Degas (http://degas.sourceforge.net/)

-- 
---------------------------------------------------------
           J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr