[net.lang] Checking for Recursions

hen@bu-cs.UUCP (Bill Henneman) (09/18/85)

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.

franka@mmintl.UUCP (Frank Adams) (09/20/85)

[Not food]

As several people have pointed out, checking for recursions really needs to
be done by the linker, not the compiler.  This requires, at minimum, some
expansion and/or redesign of the relocatable files produced by the compilers.

There are other good reasons for such a redesign.  Most especially, one would
like the linker to check number, direction, and type of subprogram arguments.
(Doing this for enumeration types and structure or record definitions is a
non-trivial design problem.)

The next question is, how do you get there from here?  I think the
development path would be:

1) specify the new file format

2) write a linker which can process objects in either format.  When making
   comparisons involving mixed styles (e.g., a new style call to an old
   style routine), assume it is correct.

3) modify existing compilers and assemblers to generate new style files.
   For assemblers, this will require additional statements in the source.

This all assumes that you are modifying an existing OS; for a new OS, this
can all be done right in the first place.

Frank Adams                           ihpn4!philabs!pwa-b!mmintl!franka
Multimate International    52 Oakland Ave North    E. Hartford, CT 06108