INTERFACE AST;

(***************************************************************************)
(*                      Copyright (C) Olivetti 1989                        *)
(*                          All Rights reserved                            *)
(*                                                                         *)
(* Use and copy of this software and preparation of derivative works based *)
(* upon this software are permitted to any person, provided this same      *)
(* copyright notice and the following Olivetti warranty disclaimer are     *) 
(* included in any copy of the software or any modification thereof or     *)
(* derivative work therefrom made by any person.                           *)
(*                                                                         *)
(* This software is made available AS IS and Olivetti disclaims all        *)
(* warranties with respect to this software, whether expressed or implied  *)
(* under any law, including all implied warranties of merchantibility and  *)
(* fitness for any purpose. In no event shall Olivetti be liable for any   *)
(* damages whatsoever resulting from loss of use, data or profits or       *)
(* otherwise arising out of or in connection with the use or performance   *)
(* of this software.                                                       *)
(***************************************************************************)

(* Copyright (C) 1990, Digital Equipment Corporation           *)
(* All rights reserved.                                        *)
(* See the file COPYRIGHT for a full description.              *)

(* This interface defines the root type of an Abstract Syntax Tree (AST),
and explains the conventions for declaring new, language-specific, ASTs.

   Although we speak of a "tree", an AST is really a graph, with only
the syntactic component likely to be a pure tree. The graph consists of a set
of connected nodes which are all instances of subtypes of the object type NODE,
declared in this interface. Nodes can have attributes, which are ultimately 
represented as object fields or methods.  Typically, an attribute is a 
reference or connection to some other node in the AST.

   An AST for a specific language is specified as a set of interfaces,
which share the naming convention LLAST, where LL is a language-specific
prefix, e.g. M3, for the Modula-3 AST. Within this set, it is also
conventional to specify the AST as a series of views, each of which provides
some new nodes (possibly none) and new attributes on nodes defined in other 
layers.  To avoid interface circularities and also to provide for flexibilty
in how the attributed are represented, the declarations of the node types
and the specifications of the node attributes are divided into separate
interfaces. The node types for each view are defined in an interface named 
LLAST_VV, where VV is a tag denoting the view, e.g. AS for the syntactic layer.
The fundamental attributes on these nodes are specified in an interface named 
LLAST_VV_K, where K is a tag which denotes either the kind of attribute that 
is being added or indicates a sub-view. For example, F is conventionally
used to indicate attributes represented as object fields, and M indicates
methods that are applicable to this view. 

   Using these conventions, interfaces are constructed as follows. First the
opaque declarations:

  INTERFACE LLAST_VV;
  IMPORT AST;
  TYPE SomeNode <: AST.NODE;
       SomeSubNode <: SomeNode;

   For each node to be attributed, define a concrete object type with the same
name as the abstract type, and then REVEAL the abstract type to be some subtype
of that. E.g.

  INTERFACE LLAST_VV_F;
  IMPORT AST, LLAST_VV;
  TYPE SomeNode = AST.NODE OBJECT fields END;
       SomeSubNode = SomeNode OBJECT fields END;
  REVEAL LLAST_VV.SomeNode <: SomeNode;
         LLAST_VV.SomeSubNode <: SomeSubNode;

   When this interface is imported, it allows access to "fields", and the
REVEAL statement tells the compiler that the actual node will have all these 
fields, and possible some more. In the above example "fields" are the
fundamental attributes defined by this view, and the supertypes of "SomeNode"
and "SomeSubNode" are the same as was declared in the LLAST_VV interface.  
Additional attributes are added by subsequent views like this:

  INTERFACE LLAST_WW_F;
  IMPORT AST, LLAST_VV, LLAST_VV_F;
  TYPE SomeNode = LLAST_VV_F.SomeNode OBJECT fields END;
       SomeSubNode = LLAST_VV_F.SomeSubNode OBJECT fields END;
  REVEAL LLAST_VV.SomeNode <: SomeNode;
         LLAST_VV.SomeSubNode <: SomeSubNode;

   Notice that in this case the supertype comes from the previous view,
LLAST_VV_F. Since REVEAL does not propagate through multiple levels
of interface, a client of LLAST_WW_F, does not see the fields that
were defined in LLAST_VV_F, unless it is also explicitly imported. 

   Owing to the constraints of Modula-3 object subtyping, it is regrettably
necessary to know the name of the view that last added attributes to the node.
If you get this wrong you will get an error message complaining about
incompatible revelations at some point. However, whether this occurs
at compile, link, or run-time depends on the implementation. 

   It is possible to avoid knowing exactly which view last refined a node by 
adopting the convention that each layer pass through all node types that it
does not refine by a declaration of the form:

  TYPE NODE = LLAST_VV_F.NODE;

   This requires only that the previous view is known, but generates a 
substantial number of pass-though declarations. It also enforces
more connectivity between views than might strictly be necessary.

   Ultimately, there must be an interface or module which chooses which views
will actually exist in a given program, by making a concrete revelation
containing the corresponding declaration in the lowest view that
is to be included. E.g.

  INTERFACE LLAST_all;
  IMPORT LLAST_VV, LLAST_WW;
  IMPORT LLAST_VV_F, LLAST_WW_F;

  REVEAL LLAST.SomeNode = LLAST_VV_W.SomeNode BRANDED OBJECT END;;
  REVEAL LLAST.SomeSubNode = LLAST_VV_W.SomeSubNode BRANDED OBJECT END;;

   If all such revelations are collected in this interface, it can be 
consulted when adding a new view to ascertain which view last added attributes
to the node.

   So what is the point of all this? There are two reasons. First, since
AST specifications for real compilers and tools are inherently complex,
there is much value to be gained in separating the specification into
more manageable pieces. For example, the syntactic, semantic and
code-generator attributes can be specified independently. To understand
the syntactic specification, there is no need to see or understand the
other two. Secondly, it is possible to replace a view without
affecting any of its ancestors, or add a completely new view, for example
to support a new programming environment tool. The key point to note
is that although there may be many views of a node, there is only one
actual node type. Whenever an instance of a node is created it
has all the sum of all the attributes that were specified in the
contributing views. So, although a parser might be separately compiled
against the syntactic view, it need only be relinked to incorporate
a new tool with its own view. This greatly facilitates the extensibility
of the environment. Its just too bad that Modula-3 doesnt have multiple
inheritance, which would avoid the nuisance of the view linearisation.
*)

  TYPE NODE <: ROOT;        (* all nodes an AST are subtypes of this *)

(* See AST_MMMM for the set of standard (abstract) methods on a NODE,
   where MMMM=
   
    Init            (dynamic) node initialisation
    Name            return print name for node
    Iter            attribute iterator
    WalkRep, 
    DisplayRep,
    CopyRep         support for tree-walks, pretty-printing and copying.
 *)

END AST.