From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-0.9 required=5.0 tests=BAYES_00,FORGED_GMAIL_RCVD,
	FREEMAIL_FROM autolearn=no autolearn_force=no version=3.4.4
X-Google-Thread: a07f3367d7,f0f0d8e1d84a1aae
X-Google-Attributes: gida07f3367d7,public,usenet
X-Google-NewGroupId: yes
X-Google-Language: ENGLISH,ASCII
Path: 
 g2news2.google.com!postnews.google.com!v2g2000vbb.googlegroups.com!not-for-mail
From: Gene <gene.ressler@gmail.com>
Newsgroups: comp.lang.ada
Subject: Re: Idiom for tail recursion?
Date: Sun, 31 May 2009 18:32:34 -0700 (PDT)
Organization: http://groups.google.com
Message-ID: <f7ffb7bc-88c9-4c7a-9a79-e08c1d9736a3@v2g2000vbb.googlegroups.com>
References: 
 <814eff38-3e01-4f70-aeb7-48a1ae651dfc@h23g2000vbc.googlegroups.com>
NNTP-Posting-Host: 74.44.132.155
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-Trace: posting.google.com 1243819954 1378 127.0.0.1 (1 Jun 2009 01:32:34
 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Mon, 1 Jun 2009 01:32:34 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: v2g2000vbb.googlegroups.com; posting-host=74.44.132.155;
	posting-account=-BkjswoAAACC3NU8b6V8c50JQ2JBOs04
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10_5_7; en-us)
	AppleWebKit/525.28.3 (KHTML,
 like Gecko) Version/3.2.3 Safari/525.28.3,gzip(gfe),gzip(gfe)
Xref: g2news2.google.com comp.lang.ada:6149
Date: 2009-05-31T18:32:34-07:00
List-Id: <comp.lang.ada>

On May 31, 5:04=A0pm, jpwoodruff <jpwoodr...@gmail.com> wrote:
> To entertain myself, I'm making a program that implements the DEVS
> specification for discrete event simulation. =A0The 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. =A0The messages
> cycle among the objects in (fairly convoluted) cycles of mutually
> recursive dispatching calls. =A0Simulation 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. =A0This
> 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. =A0I guess the program will quit running when I raise an
> exception for that purpose. =A0Or 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 :=3D Call_A;
begin
  -- The trampoline...
  loop
    case Next_Call is
      when Call_A =3D> Next_Call :=3D A;
      when Call_B =3D> Next_Call :=3D B;
      when Call_C =3D> Next_Call :=3D C;
    end case;
  end loop;
end Main;