\section{Corrections made explicit}
The $Demeter^{TM}$ system
is a CASE (Computer-Aided Software Engineering) tool
designed for the development of large software projects.
The primary purpose of the
Demeter system 
is to provide a medium for efficient growth and evolution of software.


Either we are constructing an object in terms of other named objects
(a construction production), or we are defining an object as being an
ordered collection
of zero (one) or more other objects (a repetition production), or we state
that an object is one of several possible objects (an alternation production).

\begin{itemize}
\item A skeleton program (sprout) which defines a sample method for each 
class. Each method includes a reference to all of the
instance variables of the class as well as a comment header describing the
class for which the method is defined.  These methods are the initial working
system.  Its sole function is to walk in pre-order
through the object hierarchy, printing
the value of any class terminals in the hierarchy.  
\end{itemize}

We will present two sets of methods associated
with our Meal environment.  The first is to calculate the cost of a meal
(see Fig.2).  These
methods will walk the object hierarchy and compute the cost of each object in 
the hierarchy.  The methods is very modular, thanks to the object-oriented 
nature of Demeter, so we can use them to compute the cost of any 
component of a meal as well.  

Law of 
Demeter\footnote {The Law of Demeter states that 
for all
classes C, and for all methods M attached to C, all
objects to which M sends a message must be
M's argument objects, including the self object or
instance variable objects of C.
(Objects created by M, or by functions or methods which M calls,
and objects in global variables are considered
as arguments of M.)

This law is discussed in \cite{LHLR:law-paper}}.

subject to a similarity transformation of signatures.



The class T is compatible with class S
if the classes associated with the  class T are a subset of the classes
associated with class S.


A class T is a subtype (or subclass) of class S if 
%T and S
%are related by the transitive closure of the following relations:
\begin{itemize}
\item
T inherits from S or
\item
T is compatible with S.
\end{itemize}
Every class is a subtype (or subclass) of itself.

We can summarize the subtype definition by:
 
 \begin{quotation}
 \fbox{Subtype} =
 \fbox{Inheritance} or 
 \fbox{Compatibility} 
 \end{quotation}

To illustrate the subtype definition,
consider the following example:

\bv
AutoDealer = <cars> List(Car).
Car :
  GasolineCar *override* <fuel> Gasoline |
  CombustionCar *override* <fuel> GasolineOrCoal 
    *common* "speed" <speed> Number 
      *inherit* Machine.
List(S) ~ {S}.
GasolineCar = "gasolinecar".
CombustionCar = "combustioncar".
Machine = 
  "age" <age> Number "fuel" <fuel> FuelType.
FuelType : Coal | Gasoline | Electricity.
GasolineOrCoal : Gasoline | Coal.

Gasoline = "gas".
Coal = "coal".
Electricity = "electricity".
\end{verbatim}

We define a class {\sf Car} which inherits from class {\sf Machine}.
The {\sf Car} class has two alternatives: {\sf GasolineCar} and
{\sf CombustionCar}. Both override the inherited instance variable type
for {\sf fuel}. A machine can have any type of ``fuel'', be it gas, coal
or electricity. A combustion car can use only gasoline or coal.
Since we want to consider a CasolineOrCoal  as a special kind FuelType,
we have introduced compatibility into our definition of subtype.
There are other reasons to have both compatibility and inheritance in
the subtype definition: reduction of inheritance links, avoidance of
multiple inheritance, and efficiency.

The main idea behind the subtype definition is that if a type knows about a message then all 
objects belonging to subtypes of that type also know about that message.  
We want to prove that any combination of compatibility and inheritance will 
support this condition.  The combination of compatibility and inheritance tends
to constrain the form of class dictionaries.  
We will define several semantic rules
to deal with class dictionary structures which violate our definition of 
subtype.

To support our subtype definition we
need need to introduce the
concept of a protocol. 
Informally, protocol(S) for a class S
consists of all messages m to which all classes in S' can react to
by having a method attached to them or by inheritance.

To define the concept of protocol more formally, we use the following notation:

\begin{itemize}
\item
A class $S$ is {\em responsive} to message m if m is attached to S
or there is a class T such that m is attached to T and there are
direct inheritance links from S to T.

\item
A class $S$ knows message m if each class in S' is
responsive to m.

\item
$Protocol(S) = \{m | S$ knows m $\}$.
\end{itemize}

The distinction  between responsiveness and knowledge is useful;
knowledge involves the compatibility relationships while responsiveness
relies on inheritance.
% $attached(S)$ is the set of methods attached to class $S$.

We give now the rules for computing the protocol of a class.
We define
$attached(C)$ to be the set of methods attached to $C$.
We assume that the subtype graph does not contain cycles
and we apply the following rules to a topologically
sorted order of the classes.
We assume that the protocol
of the abstract classes universal, construction, repetition, and terminal
are given.
\begin{itemize}
\item
CONSTRUCTION:

\bv
S = <name> A ...
protocol(S) = 
  {name, set-name, ...} union 
    protocol(construction) union
      attached(S).

S = *inherit* A.
protocol(S) = 
  protocol(A) union 
    protocol(construction) union
      attached(S).

S = <name1> A ... *inherit* B *override* <name2> C ...
protocol(S) = 
  {name1, set-name1, name2, set-name2, ...} union 
    protocol(B) union
      protocol(construction) union
        attached(S).

\end{verbatim}

\item
REPETITION:

\bv
S ~ {R}. 
protocol(S) = protocol(repetition) union
  attached(S).
\end{verbatim}

\item
ALTERNATION:

\bv
   S : A | B.
\end{verbatim}

\bv
protocol(S) = protocol(A) intersection protocol(B) 
\end{verbatim}

\item
ALTERNATION with implied inheritance:

\bv
S : A | B *common* X Y.
A = <b> Ident.
B = <c> Ident.

protocol(S) = 
  (protocol(A) intersection protocol(B)) union
    {X, Y, set-X, set-Y} union
      attached(S).

protocol(A) = 
  {b, set-b} union protocol(S) union
    protocol(construction) union
      attached(S).
protocol(B) = 
  {c, set-c} union protocol(S) union
    protocol(construction) union
      attached(S).
\end{verbatim}
\end{itemize}



We are now ready to prove an important property of the subtype
predicate.

{\rm Name-Protocol-Theorem:}
If {\rm T} is a subtype of {\rm S} then {\rm protocol(T)} is a superset
of {\rm protocol(S)}.



{\rm Subtype-Transitivity-Theorem:}
The subtype relation is transitive.

Proof by case analysis.

\begin{itemize}

\item
If a class C inherits from a class B and the class B inherits from A then
the class C inherits from the class A.  

True by definition of inheritance.

\item
If a class C is compatible with a class B and the class B is compatible with
a class A then the class C is compatible to the class A.

\item
C' $\subseteq$ B' \quad   by def. of compatibility \goodbreak
B' $\subseteq$ A'  \quad  by def. of compatibility \goodbreak
C' $\subseteq$ A'  \quad  by transitivity of subset \goodbreak
C is compatible to A \quad by definition of compatibility \goodbreak
\smallskip

For the last two cases we present class dictionary templates which demonstrate
the relationship between class dictionary structure and subtype links.

\item
If a class C inherits from a class B and a class B is compatible with a class
A then C is compatible with A.

This third case combines inheritance with compatibility such that there exists
a class C which inherits from a class B and the class B is compatible with a
class A.  There are three possible class dictionary templates which will 
produce this type of subtype link.
\bv

            inheritance            compatibility
    C <---------------------- B <---------------------- A

   case 3a:

      A : B | ..... *common*.
      B : C | ..... *common*.

   case 3b:

      A : C | X1 | X2.
      B : C | X1 *common*.
      C = .

   case 3c (disallowed by the semantic rule below): 

      A : B | ......
      B = .....
      C = *inherit* B.

\end{verbatim}


\begin{enumerate}

\item

In case 3a we can prove the subtype relation in two ways.  C is both compatible
with A via the definition of compatibility and C inherits from A via the
definition of inheritance.  This occurs because B is both compatible and 
inherits from A and C is both compatible and inherits from B.

\item
In case 3b the class C is compatible with A by definition of compatibility.  
C' is a subset of A' by inspection.

\item
We disallow the case 3c with the following semantic rule.
\end{enumerate}

\bv
LabeledGraph(Node, EdgeLabel) = 
  *inherit* Graph(Node) 
    *override* <edgeList> 
      List(LabeledEdge(Node, EdgeLabel)).
LabeledEdge(Node, EdgeLabel) = 
  *inherit* Edge(Node) 
    "label" <label> EdgeLabel.
\end{verbatim}
We can use this parameterized class dictionary to define our regional map of towns,
villages, and distances by giving actual parameters to the above class dictionary.
\bv
Map = *inherit* 
  LabeledGraph (=> EdgeLabel Road, 
		=> Node Community).
Community : Village | Town 
  *common* <communityname>, <desc> String.
Village = "village".
Town = "town".
Road = "road" <roadname> String 
       <routeNumber>, <distance>Nnumber.
\end{verbatim}
This class dictionary is expanded by the Demeter system into the following
grammar:

\noindent
{\em Boundedness-Finiteness Theorem

An instance of a bounded parameterized class generates 
a finite number of classes.}

\noindent
{\em Boundedness-Context-Freeness Theorem

The language defined by an instance of a 
bounded parameterized class is context-free.}

\cite{wegner:wegner-87}