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,ASCII-7-bit Path: g2news2.google.com!news4.google.com!feeder.news-service.com!feeder.motzarella.org!news.motzarella.org!news.eternal-september.org!not-for-mail From: "John B. Matthews" Newsgroups: comp.lang.ada Subject: Re: Idiom for tail recursion? Date: Sun, 31 May 2009 21:01:33 -0400 Organization: The Wasteland Message-ID: References: <814eff38-3e01-4f70-aeb7-48a1ae651dfc@h23g2000vbc.googlegroups.com> Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Trace: news.eternal-september.org U2FsdGVkX1/KlL/f6aXZu6QG1OoIpU/SWZM9dXSUKtKscl4ASpVYPhCgHXotSK64l6v8e2HZ4R9armW2TO4VacAMmi2dzqmVyhjUU7jZEoKiGfc9zjh+7zQMBU+WxpVVZwDp460X2XxcZ2NZA3k1WQ== X-Complaints-To: abuse@eternal-september.org NNTP-Posting-Date: Mon, 1 Jun 2009 01:01:33 +0000 (UTC) X-Auth-Sender: U2FsdGVkX1+aBDQtK+yYCuqhcM5KBLrQ4EOhBzumc0au9ZTty3ckvg== Cancel-Lock: sha1:Biixb4tOsUaU4EwtInK/s+A+EUo= User-Agent: MT-NewsWatcher/3.5.3b3 (Intel Mac OS X) Xref: g2news2.google.com comp.lang.ada:6148 Date: 2009-05-31T21:01:33-04:00 List-Id: In article <814eff38-3e01-4f70-aeb7-48a1ae651dfc@h23g2000vbc.googlegroups.com>, 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. 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] [2] [3] [4] -- John B. Matthews trashgod at gmail dot com