compilation order of generic body & instantiation

compilation order of generic body & instantiation

[gate.ready.com!taurus.cs.nps.navy.mil!erickson]

I ran into a compilation problem that I don't understand: the package below 
compiles, but if I attempt to instantiate it in a procedure ("driver"), the 
compiler (Meridian Sparc Ada) will produce an error listing at the point of 
instantiation.  The error is:
"driver.a", 3: identifier not found "binary_tree" [LRM 4.1/3]

If the compilation order is changed (the original order is package spec,
body and driver) to spec, driver then body, the compilation produces no
errors, but the linking stage produces:
bamp: "driver" must be recompiled [LRM 10.3/2]
bamp: "driver" has unresolved generic instantiations
bamp: the body of "driver" must be compiled [LRM 10.3/2]

I found that if I move the definition of TRAVERSE so that it comes prior 
to function PARENT (which includes an instantiation of TRAVERSE), the error 
goes away. 

So what is the cause of the problem?  Does Ada require that the body of a 
generic procedure come before an instantiation?  Or is this a bug
in the Meridian compiler?

I tried compiling the same program using Verdix Ada, and had no problems
with either ordering of TRAVERSE and PARENT.

generic
  type ATOM is private;
package BIN_TREE is
  type BINARY_TREE is private;
  type TRAVERSAL_TYPE is (PRE_ORDER, IN_ORDER, POST_ORDER);
  TREE_ERROR: exception;

  function EMPTY(T : BINARY_TREE) return BOOLEAN;
  function PARENT(P, T : BINARY_TREE) return BINARY_TREE;

  generic
    with procedure PROCESS(T: in out BINARY_TREE) is <>;
  procedure TRAVERSE(T    : in out BINARY_TREE;
                     MODE : TRAVERSAL_TYPE);
private
  type NODE;
  type BINARY_TREE is access NODE;
end BIN_TREE;

package body BIN_TREE is
  type NODE is record
    A: ATOM;
    L,R: BINARY_TREE;
  end record;

  function EMPTY(T : BINARY_TREE) return BOOLEAN is
  begin
    return T = null;
  end EMPTY;

  function PARENT(P, T : BINARY_TREE) return BINARY_TREE is
    -- Returns the position in T of P's parent (or null if P is not in
    -- T). Precondition: P /= T and P is non-empty.
    ROOT : BINARY_TREE := T; -- local copy of T used as in out parameter
    RESULT : BINARY_TREE;

    procedure TEST_PARENT(T : in out BINARY_TREE) is
      -- uses non-local P and RESULT (which are declared in PARENT) in
      -- order to conform to the specifications for PROCESS.  Likewise,
      -- T is in out
    begin
      if (T.L = P) or (T.R = P) then
        RESULT := T;
      end if;
    end TEST_PARENT;

    procedure FIND_PARENT is
      new TRAVERSE(PROCESS => TEST_PARENT);
    -- FIND_PARENT does a traverse, and sets non-local variable RESULT

  begin       -- PARENT
    if P = ROOT or EMPTY(P) then
      raise TREE_ERROR;
    else
      FIND_PARENT(ROOT, PRE_ORDER);
      return RESULT;
    end if;
  end PARENT;

  procedure TRAVERSE(T    : in out BINARY_TREE;
                     MODE : TRAVERSAL_TYPE) is
    -- visits every node in T in preorder, inorder or postorder.
    -- T is an in out parameter, since Process requires an in out 
    -- parameter.
  begin
    if not EMPTY(T) then
      if MODE = PRE_ORDER then
        PROCESS(T);
        TRAVERSE(T.L, MODE);
        TRAVERSE(T.R, MODE);
      elsif MODE = IN_ORDER then
        TRAVERSE(T.L, MODE);
        PROCESS(T);
        TRAVERSE(T.R, MODE);
      else
        TRAVERSE(T.L, MODE);
        TRAVERSE(T.R, MODE);
        PROCESS(T);
      end if;
    end if;
  end TRAVERSE;
end BIN_TREE;

with BIN_TREE;
procedure DRIVER is
  package MY_TREE is new BIN_TREE(CHARACTER);  -- error occurs here
  use MY_TREE;
  T: BINARY_TREE;
begin
  if EMPTY(T) then
    return;
  end if;
end DRIVER;

Re: compilation order of generic body & instantiation

[agate!howland.reston.ans.net!newsserver.jvnc.net!netnews.upenn.edu!prijat]

In article <C2o4zF.M7o@taurus.cs.nps.navy.mil>, erickson@cs.nps.navy.mil (David
 Erickson) writes:
|> I ran into a compilation problem that I don't understand: the package below 
|> compiles, but if I attempt to instantiate it in a procedure ("driver"), the 
|> compiler (Meridian Sparc Ada) will produce an error listing at the point of 
|> instantiation.  The error is:
|> "driver.a", 3: identifier not found "binary_tree" [LRM 4.1/3]
|> 

I ran into a similar problem some time ago when I was porting components
from a PC (using Meridian's compiler) to a SUN (Using Meridian's compiler).
Code that compiled on the PC would not compile on the SUN.  I was able to
resolve the problem by moving the body of a generic procedure to the front
of the body of the generic package!  Apparently for some reason it was 
looking for the body of the generic procedure in another procedure that was
instantiating it. Once the body of the generic package was reorganized, my 
error message vanished.  It appears from the code included in the posting, 
the problem is identical to the one I encountered.

+------------------------------------------------------------------+
|  John (Jack) Beidler				                   |
|  Prof. of Computer Science Internet: BEIDLER@JAGUAR.UOFS.ED      |
|  University of Scranton              beidler@guinness.cs.uofs.edu|
|  Scranton, PA 18510	      Bitnet : BEIDLER@SCRANTON            |
|                                                                  |
|          Phone: (717) 941-7446	 FAX:   (717) 941-4250     |
+------------------------------------------------------------------+

Re: compilation order of generic body & instantiation

[emory!europa.eng.gtefsd.com!howland.reston.ans.net!usc!cs.utexas.edu!uwm.]

In article <C2o4zF.M7o@taurus.cs.nps.navy.mil>, erickson@cs.nps.navy.mil (David
 Erickson) writes:
|> I ran into a compilation problem that I don't understand: the package below 
|> compiles, but if I attempt to instantiate it in a procedure ("driver"), the 
|> compiler (Meridian Sparc Ada) will produce an error listing at the point of 
|> instantiation.  The error is:
|> "driver.a", 3: identifier not found "binary_tree" [LRM 4.1/3]
|> 
|> If the compilation order is changed (the original order is package spec,
|> body and driver) to spec, driver then body, the compilation produces no
|> errors, but the linking stage produces:
|> bamp: "driver" must be recompiled [LRM 10.3/2]
|> bamp: "driver" has unresolved generic instantiations
|> bamp: the body of "driver" must be compiled [LRM 10.3/2]
|> 
|> I found that if I move the definition of TRAVERSE so that it comes prior 
|> to function PARENT (which includes an instantiation of TRAVERSE), the error 
|> goes away. 
|> 
|> So what is the cause of the problem?  Does Ada require that the body of a 
|> generic procedure come before an instantiation?  Or is this a bug
|> in the Meridian compiler?
|> 
|> I tried compiling the same program using Verdix Ada, and had no problems
|> with either ordering of TRAVERSE and PARENT.
|> 
|> generic
|>   type ATOM is private;
|> package BIN_TREE is
	...
|>   generic
|>     with procedure PROCESS(T: in out BINARY_TREE) is <>;
|>   procedure TRAVERSE(T    : in out BINARY_TREE;
|>                      MODE : TRAVERSAL_TYPE);
	...
|> end BIN_TREE;
|> 
|> package body BIN_TREE is
	...
|>   function PARENT(P, T : BINARY_TREE) return BINARY_TREE is
	...
|>     procedure FIND_PARENT is
|>       new TRAVERSE(PROCESS => TEST_PARENT);
|>   begin       -- PARENT
	...
|>   end PARENT;
|> 
|>   procedure TRAVERSE(T    : in out BINARY_TREE;
|>                      MODE : TRAVERSAL_TYPE) is
	...
|>   begin
	...
|>   end TRAVERSE;
|> end BIN_TREE;
|> 
|> with BIN_TREE;
|> procedure DRIVER is
|>   package MY_TREE is new BIN_TREE(CHARACTER);  -- error occurs here
	...
|> begin
	...
|> end DRIVER;
|> 

First we need to consider whether there are elaboration order problems,
because an instantiation of TRAVERSE occurs textually prior to its body.
Presumably the procedure DRIVER is the main program, so the body of BIN_TREE
will be elaborated before BIN_TREE is instantiated (otherwise, you would need
to put a pragma ELABORATE (BIN_TREE) to ensure BIN_TREE's body is elaborated
in time).  The elaboration of BIN_TREE's body causes the body of TRAVERSE to
be elaborated before the function PARENT is called (since there is no call to
PARENT prior to the elaboration of TRAVERSE), so when PARENT is called the
body of TRAVERSE has been elaborated and the instantiation should proceed
correctly.  My point in discussing elaboration order is that putting the body
of TRAVERSE textually after an instantiation of TRAVERSE always raises the
possibility of elaboration order errors arising, so it's probably not good
style even if it works out this time.

Some implementations require that the body of a generic unit be compiled
before any instantiations of the unit are compiled.  AI-00506 allows such an
assumption for generic units that are compilation units, but does not go so
far as to extend this permission to cases like the above, I think in part
because the ARG didn't consider the above example.  The trend of
thinking at the time of AI-00506's approval was to allow implementations to
make this assumption, so maybe it is too strict to say that Meridian's
compiler is in error on this point.

John B. Goodenough					Goodenough@sei.cmu.edu
Software Engineering Institute				412-268-6391