Re: Request: Ref to Scott's proof of recursive structure minimality

Terrence Brannon (brannon@rana.usc.edu) writes:


> I am reading a book called "Functional Programming" by
> B.J. Maclennan. He states:
>
> "Scott(1974) showed that recursive structure declarations
> always have a unique minimum solution."
>
> However, there is no ref to this paper in his biblio. Can anyone point
> me to the proper paper?


I'm guessing that "recursive structure declaration solutions" means
finding a minimal set of declarations that builds structures with the
same connectivity as the original (in ANSI-ish: compatible):


    struct foo {
        int a;
        struct bar *x;
    };
    struct bar {
        int a;
        struct foo *x;
    };


can be solved as:


    struct foobar {
        int a;
        struct foobar *x;
    };


You can view each structure declaration has being a node in a graph,
with the pointer type declarations as being edges. The edges are
labeled with the field name & order; non-pointer types represent
constant information that has to be matched as well. Two nodes are
equivalent if they have the same constant information, and their edges
point to equivalent nodes. This is a recursive definition, and in
fact trivally equal to the problem of finding a minimal DFA. There is
always a minimal DFA (Myhill-Nerod theorem, "Intro to Automata Theory"
by Hopcroft & Ullman), and it can be found in O(n log n) time. A
more modern use of this algorithm is in Alpern, Wegman & Zadeck's
"Detecting Equality of Variables in Programs", '88 POPL.


Within a compilation unit, ANSI uses name-equivalence, so that a
program which defines a foo*, but uses it as a bar* is undefined (and
probably elicits a compiler error). _Across_ compilation units, only
compatibility is required. Thus creating a foo* in one file and
passing it to a function in another file that treats it as a bar* is
legal and defined, because foo and bar are compatible. If you are
building an interprocedural, inter-file-unit optimizer you must
correctly handle the case where a user passes a foo* to a compatible
bar* without error (and hopefully with better code) and ALSO not dump
core when a user passes a foo* to an INcompatible baz* (perhaps
generating a warning on the way). Compatible but not name-equivalent
declarations can arise because some #include'd header file accidently
macro-renames one of your field names for a structure declaration in
one file, but not in another: the programmer isn't even aware (and
probably doesn't desire) the renaming, but there it is.




Cliff


P.S. This is not to say that Scott didn't prove it in '74, it's just
that I also don't have a reference to Scott.


--
Cliff Click Compiler Researcher & Designer
RISC Software, Motorola PowerPC Compilers
cliffc@risc.sps.mot.com (512) 891-7240
--

Return to the comp.compilers page.
Search the comp.compilers archives again.