Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/17/84; site opus.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!think!harvard!seismo!hao!nbires!opus!rcd
From: rcd@opus.UUCP (Dick Dunn)
Newsgroups: net.lang
Subject: Re: Recursion
Message-ID: <55@opus.UUCP>
Date: Wed, 18-Sep-85 02:08:46 EDT
Article-I.D.: opus.55
Posted: Wed Sep 18 02:08:46 1985
Date-Received: Fri, 20-Sep-85 04:06:04 EDT
References: <712@gitpyr.UUCP> <250@mot.UUCP>
Organization: NBI,Inc, Boulder CO
Lines: 17

...discussion of detecting indirect recursion in compiler; response:
> Actually, it's not too bad.  You just set up an n-by-n Boolean matrix
> where n is the number of subroutines under consideration and the
> ij element is 1 iff routine i calls routine j.  Then take the
> transitive closure by Warshall's algorithm.  1's on the diagonal of
> the result indicate which routines are indirectly recursive.

This only detects potential indirect recursion.  As (I think) has been said
before, the facts that A calls B and B calls A do not together imply that A
and B are mutually recursive (but only that they might be).

By the way, don't forget that in traditional systems you also end up either
bagging the check across modules or building the transitive-closure
algorithm (PLUS figuring out "what is a procedure?") into your linker.
-- 
Dick Dunn	{hao,ucbvax,allegra}!nbires!rcd		(303)444-5710 x3086
   ...Lately it occurs to me what a long, strange trip it's been.


Brought to you by Super Global Mega Corp .com