Re: Mutually dependent private types

[John Volan <johnv@ac3i.dseg.ti.com>]

Fergus Henderson wrote:
> 
> Geoff Bull <gbull@acenet.com.au> writes:
> 
> >How does a compiler that uses a non source based compilation library
> >"with" a package that hasn't been compiled yet?
> >(i.e. would allowing circular dependencies introduce a big headache
> >for just about every Ada compiler, except for Gnat?)
> 
> You can implement this by breaking up "compilation" into several
> stages.  For example, the Mercury compiler (which supports a module
> system similar to that of Ada) supports circular dependencies
> with a non-source-based compilation library by breaking compilation
> into the following stages:

Without knowing anything about Mercury as a language, I can make the
following observations:

>         mmc --make-short-interface foo
>                 Does rudimentary syntax checking.
>                 Records the names of types defined in the module foo
>                 in the compilation database.
>                 Preconditions: none.

Roughly speaking, this corresponds to the compiler automatically
extracting and processing forward class declarations (type names) out of
the source code module.  It's also taking the opportunity to do a syntax
check, but neither of these processes require access to semantic
information about other modules.


>         mmc --make-interface foo
>                 Checks the interface for type correctness (i.e.
>                 checks that there are no undefined types, etc.).
>                 Records the interface of module foo in the compilation
>                 database.
>                 Preconditions: the "short interfaces" of all imported modules
>                 must have already been generated.

Here, the compiler is clearly processing the full interfaces ("specs")
of the classes (types) in the module.  When it encounters a parameter of
a type from a different module, it has to be able to get access to
semantic information about that other module, but that only has to be
the processed forward declarations (short interfaces), and not
necessarily the full interface semantics.

>         mmc --compile foo
>                 Does full semantic checking.
>                 Generates object code for the module foo.
>                 Preconditions: the interfaces of all imported modules
>                 must have already been generated.

Here, the compiler is processing the implementations ("bodies") of the
classes in the module. At this point it needs full semantic information
about the interfaces of imported classes, because it actually needs to
generate code for any calls it makes to imported methods, as well as for
passing imported-type parameters into its own methods.

These three levels of compilation are completely consistent with the
inter-class dependency model I described in my diagram in
http://bluemarble.net/~jvolan/WithingProblem/FAQ.html#missing_feature. I
am certain that these three compilation passes are exactly what occurs
implicitly inside compilers for languages such as Eiffel and Java, where
each class only has one source file and there is no explicit separation
of forward declaration, interface, and implementation.  The only
difference is that apparently the Mercury compiler needs to be
explicitly told when to do which compilation passes on which modules in
which order.  This compilation-order dependency is definitely
reminiscent of old-style Ada compilation systems.

> Actually our "compilation database" is just a subdirectory containing
> plain ASCII files.  

That's also reminiscent of an old-style Ada "library", which was
essentially a database of compilation products.

> The above preconditions are recorded in dependency
> files, and then we use a tool based on GNU Make to ensure that the
> compiler is invoked with the appropriate options in the appropriate order.

Old-style Ada compilation systems usually included a "make" tool that
was able to do approximately the same thing. These usually had to do an
"analysis" pass over the source files in a library to determine what
units they contained and what dependencies there were between the units.

> Whether or not doing this kind of thing would be a "big headache" for
> existing Ada compilers is another question -- that would depend a lot
> on exactly how they were implemented.  But I thought that the other
> Ada95 front-ends all used the same kind of source based model that GNAT
> uses anyway.

Ada requires the programmer to explicitly separate interfaces (specs)
from implementations (bodies). There's a clear distinction in how specs
and bodies should be compiled.  Obviously, Ada compilers have been
designed from the bottom-up to deal with this distinction.  But Ada
doesn't provide a corresponding way to explicitly separate out forward
declarations from full specs. In fact, the semantics of Ada don't even
allow compilers to implicitly extract forward declarations out of a spec
-- otherwise there'd be no such thing as a "withing problem".  So
obviously there's been nothing to motivate Ada compiler-writers to
design in a separate pass for processing forward declarations. (In fact,
if any have tried, they might have been criticized in some circles as
"unnecessarily complicating" the compiler design.)  Maybe the "make
analysis" pass in old-style Ada compilation systems carried the germ of
such a "forward-extraction" pass, but I'd be very surprised if source
based compilation systems would have bothered with it.  

(Note that Matthew Heaney's "Mutual" pragma suggestion would essentially
change the semantics of the Ada language to allow/require compilers to
do a "forward-extracting" pass.)

-- 
Signature volanSignature = 
  new Signature
  ( /*name:      */ "John G. Volan",
    /*employer:  */ "Raytheon Advanced C3I Systems, San Jose",
    /*workEmail: */ "johnv@ac3i.dseg.ti.com",
    /*homeEmail: */ "johnvolan@sprintmail.com",
    /*selfPlug:  */ "Sun Certified Java Programmer",
    /*twoCents:  */ "Java would be even cooler with Ada95's " +
                    "generics, enumerated types, function types, " +
                    "named parameter passing, etc...",
    /*disclaimer:*/ "These views not packaged in COM.ti.dseg.ac3i, " +
                    "so loading them throws DontQuoteMeError. :-)" );