Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site bu-cs.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!think!harvard!bu-cs!hen
From: hen@bu-cs.UUCP (Bill Henneman)
Newsgroups: net.lang
Subject: Re: Checking for Recursions
Message-ID: <653@bu-cs.UUCP>
Date: Wed, 18-Sep-85 09:21:36 EDT
Article-I.D.: bu-cs.653
Posted: Wed Sep 18 09:21:36 1985
Date-Received: Fri, 20-Sep-85 04:24:08 EDT
References: <250@mot.UUCP> <4302@alice.UUCP>, <1124@kestrel.ARPA>
Organization: Boston Univ Comp. Sci.
Lines: 22

Call path checking can be done pretty efficiently: while worst cases of
order n**2 exist, it would require an IQ in 14 digits to maintain a
large application program that had such rich interconnections amongst
routines.  Experience analyzing LISP routines (where recursion is the
much more popular than in other languages) shows that you need n*log(n):
using a scheme analogous to interval analysis gets you below n in every
case I've seen.

More typical, I just finished a project which involved analyzing (as a
prelude to translating) 4.5 megalines of code written in a dialect of
FORTRAN which had been modified to support recursion.  There was only
one loop in the call graph of length > 2.  Although the graph could have
had 3500 nodes, it never grew beyond 30.

Just because it *could* be done doesn't mean it *should* be done.  A
stand-alone utility to inform the user (or supply the declarations for
the user) might not be a bad idea, but sinking it down into the compiler
doesn't seem reasonable. Path checking forces a monolithic compile mode,
where all source code must be processed (and I don't know what the
compiler would do about calls to assembler programs).  Having to
recompile all the source every time you make a change to the code makes
building big applications kind of expensive.


Brought to you by Super Global Mega Corp .com