Re: Idiom for tail recursion?

[Gene <gene.ressler@gmail.com>]

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;