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=-1.9 required=5.0 tests=BAYES_00 autolearn=ham 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,UTF8 Path: g2news2.google.com!news4.google.com!feeder.news-service.com!de-l.enfer-du-nord.net!gegeweb.org!aioe.org!nospam From: "John B. Matthews" Newsgroups: comp.lang.ada Subject: Re: Idiom for tail recursion? Date: Tue, 02 Jun 2009 10:00:43 -0400 Organization: The Wasteland Message-ID: References: <814eff38-3e01-4f70-aeb7-48a1ae651dfc@h23g2000vbc.googlegroups.com> NNTP-Posting-Host: ib4TTflHUauJidfWP/+Rjw.user.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Complaints-To: abuse@aioe.org X-Notice: Filtered by postfilter v. 0.7.9 Cancel-Lock: sha1:S1izr9j3vxOoAf0GiKF8n1yJ5D4= User-Agent: MT-NewsWatcher/3.5.3b3 (Intel Mac OS X) Xref: g2news2.google.com comp.lang.ada:6178 Date: 2009-06-02T10:00:43-04:00 List-Id: In article , Gene wrote: > On May 31, 5:04 pm, jpwoodruff 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