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