randy@oresoft.UUCP (Randy Bush) (09/25/87)
One-pass Compilation Issues
25 Sep 87
This is not complete, and comes to no clear conclusion. The intent is to
provoke and focus discussion. This is excerpted from an internal paper of 28
September 86, with some small additions.
Overview
A Modula-2 compiler, given the language defined in PIM-2.3, requires more
than one pass, as Modula-2 allows declaration after use in a procedure body.
Pascal's approach of adding FORWARD procedure declarations solves the worst
of the problems, but mutually importing internal modules would be the major
loss. A number of popular current compilers have the one-pass restriction,
including that of Professor Wirth.
It is worth noting that multi-pass compilers may have the one-pass
restrictions. The real question is not how many passes the compiler makes
(whatever a 'pass' may be), but how it resolves forward references. Thus,
'one-pass restrictions' may be a misnomer, but, for lack of a clearer term,
it will be used here.
Use of a Variable Before Declaration
PIM-2.3 does not allow a declaration of a variable (except of a pointer) to
require forward resolution. On the other hand, a statement may use a
variable or constant before it is declared. Thus
PROCEDURE p ();
VAR x : T;
BEGIN
x := 42
END p;
TYPE T = CARDINAL
is not legal, while the following is.
PROCEDURE p ();
BEGIN
x := 42
END p;
TYPE T = CARDINAL;
VAR x : T
Worse, the following is legal.
VAR x : INTEGER;
PROCEDURE p ();
PROCEDURE q ();
BEGIN
x := 42
END q;
VAR x : CARDINAL;
BEGIN END p;
As use before declaration is not kind to the reader of a program (one
net.@hole has called it abomination :-), its loss may be considered of little
consequence.
Forward Reference to Procedures
PIM-2.3 would allow forward reference to procedures, thereby allowing mutual
recursion of procedures, e.g.
PROCEDURE p ();
BEGIN
q ()
END p;
PROCEDURE q ();
BEGIN
p ()
END q;
This was allowed in early specifications of Pascal, but was not implemented
by any compilers to my knowledge. The common work-around for one-pass
restrictions in Pascal is predeclaration using the FORWARD directive, e.g.
PROCEDURE q (); FORWARD;
PROCEDURE p ();
BEGIN
q ()
END p;
PROCEDURE q ();
BEGIN
p ()
END q;
Don Baccus reminds me that Wirth's Pascal "Report" does not mention FORWARD,
but leaves it for Jensen's "User Manual".
Mutually Importing Internal Modules
What one-pass compilation can not provide is mutually importing internal
modules. E.g.
MODULE a;
MODULE b;
IMPORT x;
EXPORT y;
CONST y = 42;
END b;
MODULE c;
IMPORT y;
EXPORT x;
CONST x = 77;
END c;
END a.
The above is actually quite useful, and lack of the ability forces formation
of library modules to circumvent the restriction. Mutually importing
internal modules have been used in the ETH multi-pass compiler, as well as
some code in the real world.
This also includes the case where code wishes to use objects exported from a
following internal module, and that module wishes to use objects declared
above. E.g.
VAR s,t : CARDINAL;
PROCEDURE p ();
BEGIN
Init (t)
END p;
MODULE m;
EXPORT Init;
PROCEDURE Init ( VAR c : CARDINAL );
BEGIN
IF s = 0 THEN
c := s
END
END Init;
END m;
Wirth's One-pass Compiler
In his recent one-pass compiler for the MC68000, NSC32000, and 8x8y family,
Professor Wirth adds FORWARD to procedure declarations. At first he tried to
move mutually recursive procedures to the definition module, but received
very negative feedback. The one-pass restrictions seem to be acceptable to
his user community for the moment. Many current implementations are derived
from Professor Wirth's one-pass compiler.
Volition's Implementations
Volition's p-code system (they also did a completely different MC68000
native system) was derived from the one-pass P2 compiler, and therefore
could not implement the language as specified in PIM-2.3. They added
FORWARD to procedure declaration, disallowed use before declaration, and
did not support mutually importing internal modules.
There was no negative user feedback on these restrictions. As the p-code
compiler was quite fast for an interpretive implementation (2,000 lpm on
a floppy based 68000 at 8MHz), the users seemed to feel the trade was worth
it. This was in '81.
Volition's native code compiler for the 68000 was written with the same
restrictions. This product has been acquired and developed further by
Masthaven, and their impressions of user feedback would be useful in
evaluating the impact of one-pass restrictions.
The Modula-2 Validation Suite
When writing the M2VS, PSG had serious qualms and questions about this issue.
As it could not be clearly resolved, it was decided that the suite as a whole
should not rely on either mode, but specific tests would be included which
determined whether or not the implementation had one-pass restrictions.
These tests were classified as quality tests, rather than conformance or
deviance. This may be a reasonable compromise.
The BSI
One-pass restrictions have been discussed in committee, and were generally
received positively. Many small changes in recent drafts indicate someone
has an eye on one-pass compilation. The question is will they add FORWARD,
disallow declaration after use, and disallow mutually importing internal
modules?
Conclusion
I come to none (and you had to read all this!?!). All in all, it's a tough
issue. Existing implementions of both sorts exist, and, presumably,
considerable user code exists that relies on both styles of implementation.
Maybe the PSG M2VS decision, that it is a quality issue not a conformance
issue, was correct.
--
randy%oresoft.UUCP@tektronix.tek.com Fidonet:1:105/6 1+(503) 245-2202