\documentstyle{article}
%\documentstyle[12pt]{article}

\begin{document}
\input common.tex
\bibliographystyle{alpha}
%\bibliographystyle{abbrv}
\raggedbottom

\title{Object-Oriented Programming: \\An Objective Sense of Style}

\author{Karl J. Lieberherr, Ian M. Holland\\
\\161 Cullinane Hall, College of Computer Science\\
Northeastern University, 360 Huntington Ave., Boston MA 02115}
\maketitle
\input time.tex 
\centerline{Texed at \thetime\ \today}
\centerline{Copyright \copyright 1988 Karl Lieberherr}
\begin{abstract}

%To appear in IEEE Software:
%It will be copy-edited, but we are looking for feedback regarding
%accuracy and understandability.

\medskip
We introduce a simple, programming 
language independent rule (known in-house as the Law of Demeter) which
encodes the ideas of encapsulation and modularity in an easy to follow form
for the \oo \/ programmer.
% WHAT IS IN THE PAPER FOR THE USER ?
The rule achieves
the following related benefits if 
code duplication,
the number of method arguments and the number of methods per class are
minimized:
Easier software maintenance, 
less coupling between your methods,
better information hiding,
methods which are easier to reuse,
and easier correctness proofs using structural induction.
%We show relationships between the Law and software
%engineering techniques, such as coupling control, information hiding,
%information restriction, localization of information, narrow interfaces
%and structural induction. 
%We discuss two important interpretations of the
%Law (strong and weak)
% and we prove that any \oo \/ program can be transformed
% to satisfy the Law.
We express the Law in several languages which support object-oriented
programming, including Flavors, Smalltalk-80, CLOS, C++ and Eiffel.
\end{abstract}

\medskip
\noindent
{\bf Keywords}:
Object-oriented programming, programming style, design style,
software engineering principles, software maintenance and
reusability.

\medskip
\noindent
Short versions of this paper appeared in IEEE Computer, June 1988, Open
Channel, page 79 and in the proceedings of OOPLSA '88, pages 323-334.
%\newpage
\section{Introduction}

For the past two years we have been using \oop\  techniques in 
our research and in our
teaching at the undergraduate and graduate levels.  During
this time we have posed many stylistic questions such as,

``When is an
object-oriented program written in good style?'', ``Is there some formula or
rule which one can follow in order to write good object-oriented programs?'',
``What metrics can we apply to an object-oriented program to determine if it is
`good'?'', and ``What are the characteristics of good object-oriented programs?''.

In this paper we put forward a simple rule (now known
in-house as the {\em Law of Demeter} or the {\em Law of 
Good Style}) which, we believe, answers these
questions and helps to formalize the existing ideas that can be found in the
literature \cite{kaehler-patterson:taste} \cite{snyder:wegner-87}.
%\cite{emblay-woodfield:quality}.
We claim that our Law promotes maintainability and comprehensibility.  To
prove this in absolute terms would require a large experiment with a
statistical evaluation.  As the field of \oop\ is new, large \oo\
software developments which are able to provide such data are rare. 

We have examined
our own code (about fourteen thousand lines of Lisp/Flavors and C++ code) 
and are
convinced of the Law's benefits.  The close relationships and implications
between the Law and software engineering principles such as coupling
control, information hiding and narrow interfaces are pointed out below.
These provide the  support for our claim.

The Law of Demeter is named
%\footnote{However, we don't necessarily intend our `Law' to be
%an instance of the classes of natural, legal or scientific laws!
%} 
after the \demsign\ system which provides
a high-level interface to class-based \oos s. 
The key contribution of the Demeter system is to improve programmer 
productivity by several factors for an important part of the development
process. The key idea behind the Demeter system is to view class definitions
as language definitions and to provide a notation which can handle both
aspects.
%The most novel aspect of the 
%Demeter system is that we view a (parameterized) class definition as a 
%(parameterized) language definition. 
This point of view allows us to
provide a large number of useful utilities 
(written in a specific object-oriented 
language, currently Old Flavors and C++) which impressively simplify the programming task. 

Examples of utilities which are generated or provided generically
are: class definitions in a programming language, 
application skeletons,
parsers, pretty printers, type checkers, object editors, 
recompilation minimizers, pattern matchers and unifiers.
The Demeter system supports the user in defining the classes (both their
structure and functionality)
with the following support tools: Consistency checker (semantic rules and type
checking at the design level), learning tool which learns
class definitions from example 
object descriptions, LL(1) corrector, script generator based on
wishlist, application development plan generator
\cite{karl1:class} \cite{lieber-riel:oop}.
The explanations and examples presented in 
this paper are written in the notation
of Demeter which is described later in this paper.

One of the primary goals of the Demeter system is to develop an environment 
which facilitates the evolution of a class hierarchy.  Such an environment
must provide tools for the easy updating of existing software (i.e.
the methods (operations) which are defined on the class hierarchy).
We are striving to produce an environment which will allow 
software to be `grown' in a continuous fashion rather than in
sporadic jumps, which undoubtably leads to major rewrites.  
This will lead to the fast prototyping and updating
system development cycle which is common in the 
Artificial Intelligence community.

In order to achieve this flexibility we would like the programs
written in the Demeter environment
to be `well behaved' or `well formed' in some sense.  
In other words, we would like the
programs to follow a certain style which enables them 
to be modified easily.  This ease of modification is one criterion which
characterizes a good object-oriented programming style.

This issue is relevant not only to the Demeter world, but is one which 
should be adopted by all programmers which use object-oriented 
programming techniques.
In addition, every object-oriented
programmer should know what is considered `good object-oriented programming
style' in order to write easily maintainable 
systems 
just as procedural programmers are aware of the top-down
programming paradigm, the ``thou shalt not use a goto'' rule and others 
\cite{kernighan-plauger:style}.  
%A The Law can be understood without knowledge of Demeter, but the best 
The Law can be understood without knowledge of Demeter.
%, but the best 
%formulation which is compile-time enforceable 
%for a large class of object-oriented languages
%requires basic Demeter concepts.
%Even though the Law of Demeter 
%is written in terms of types and
%a programmer using a non-typed object-oriented system will not be able to
%follow the letter of the Law he/she will be able to adhere to its spirit.
We challenge \oo\ programmers to check whether their programs
follow our Law and where they do not, to consider whether they should.

%A
We use several formulations of the Law of Demeter which we briefly
motivate here.

\begin{itemize}
\item
class/object formulation: The class formulation is compile-time enforceable
for statically typed languages. The object formulation expresses what we
``really'' want but is hard to enforce at compile-time.
%\item
%weak/strong formulation: The strong formulation leads to better encapsulation
%of inheritance and reduces the impact of change.
\item
minimization formulation: This is the most flexible formulation of the
Law of Demeter which allows for exceptions in a controlled way.
\end{itemize}

%The formulations can be freely combined: Therefore, we have 8 different
%formulations of the Law of Demeter.

The examples in this paper are written in the notation of Demeter, therefore
section two is dedicated to a description of this notation.
The sections
which follow will define the Law of Demeter both formally and through examples,
examining both practical and theoretical issues.  In \cite{LHLR:law-paper}
we presented
a proof which
states that any \oo\ program
written in bad style can be transformed systematically
into a structured program obeying the Law of Demeter.  The implication of this
proof is that the Law of Demeter does not restrict what a programmer can solve,
it only restricts the way he or she solves it.


\section{Notation}
Classes are described
in Demeter using three kinds of class definitions.\footnote{
We use two notations in the Demeter system: A concise notation based
on EBNF and an extended notation which is largely self-explaining. In this paper
we use the extended notation. The abstract syntax of the concise and 
the abstract syntax of the 
extended notation are identical: only the ``syntactic sugar'' is changed.}
A collection of these class definitions is called a class dictionary.

\begin{enumerate}
\item A {\em construction} class definition 
is used to build a class from a number
of other classes and is of the form
\bv
class C has parts
  part_name_1 : SC_1
  part_name_2 : SC_2
  ...
  part_name_n : SC_n
end class C.
\end{verbatim}
%$C = <id_{1}> SC_{1} \ldots < id_{n}> SC_{n}. $
%\verb|C=<|$id_{1}$\verb|>| $SC_{1} \ldots$ \verb|<|$id_{n}$\verb|>| $SC_{n}. $
Here \verb|C|  is defined as being made up of $n$ parts (called its instance
variable values), each part has a name (called an
instance variable name) followed by a type
(called an instance variable type).  
This means that
for any instance (or member) of class {\sf C} the name 
\verb|part_name_i| refers to a member of 
class \verb|SC_i|.
The following example describes a library class as consisting
of a reference section, a loan section, and a journal section. 
\bv
class Library has parts
  reference : ReferenceSec
  loan : LoanSec
  journal : JournalSec
end class Library.
\end{verbatim}
The following naming convention is used : Instance variable names
will begin with a lower case letter and class names will begin with
a capital letter.
\item An {\em alternation} class definition allows us to express
a union type. A 
class definition of the form 
\bv
class C is either
  A or B
end class C.
\end{verbatim}
states that a member of {\sf C} is a member
of class {\sf A} or class {\sf B} (exclusively). For example,
\bv
class Book_Identifier is either
  ISBN or LibraryOfCongress
end class Book_Identifier.
\end{verbatim}
which expresses the notion that when we refer to the  identifier of a book we 
are actually referring to its ISBN code or its Library of Congress code.
\item A {\em repetition} class definition is simply a variation of the construction
class definition where all the instance variables have the same type and we do not
specify the number of instance variables involved. The class definition 
\bv
class C is list
  repeat {A}
end class C.
\end{verbatim}
 defines members of {\sf C} to be lists of zero or more instances of
{\sf A}. 


We partially define a reference section in the library class in the following
class dictionary.

\begin{verbatim}
class ReferenceSec has parts
  ref_book_sec : BooksSec
  archive : Archive
end class ReferenceSec.

class Archive has parts
  arch_microfiche : MicroficheFiles
  arch_docs : Documents
end class Archive.

class BooksSec has parts
  ref_books : ListofBooks
  ref_catalog : Catalog
end class BooksSec.

class ListofBooks is list
  repeat {Book}
end class ListofBooks.

class Catalog is list
  repeat {Catalog_Entry}
end class Catalog.
       
class Book has parts
  title : String
  author : String
  id : BookIdentifier
end class Book.
\end{verbatim} 
\end{enumerate}

%To express inheritance we use the notation \verb?*inherit*? with a 
%construction production.  For example, every mathematics text book is
%a member of the class Book (as defined above), but it has some additional
%characteristics.  We can express this by
%\bv
%Math-Text = 
%  <math-cat> Math-Category 
%    *inherit* Book.
%Math-Category : 
%  Algebra | Calculus | Statistics.
%\end{verbatim}
%An instance of {\sf Math-Text} is also a member of {\sf Book} 
%and will therefore
%contain the instance variables of both.
%
%The following naming convention is used : Instance variable names
%will begin with a lower case letter and class names will begin with
%a capital letter.

%Currently the Demeter  system ``sits on top of'' Old-Flavors and C++ 
%and so the methods are written in the notation of these languages.

\section{Clients, suppliers and dependencies}

In this section we explain the Law of Demeter by 
adapting 
the client/supplier terminology from \cite{meyer:book-88}.
This terminology is useful for explaining the consequences of the Law
and also for formulating it. Before we get into the technical details,
we give intuitive formulations of the Law.

The goal of the Law of Demeter is to organize and reduce dependencies
between classes.
We can informally summarize the Law with the following three formulations:

\begin{itemize}
\item
Each method can only send messages to a limited set
of objects, namely to the {\em argument objects} and to the {\em immediate
subparts} of {\sf self}  (or {\sf this} in C++).
 
\item
 Each method is ``dependent'' on a limited set of objects 
(organize dependencies).
  
\item
  Each method ``collaborates'' with a limited set of objects
  (organize collaborations).
\end{itemize}


\subsection{Definitions and formulations}

\begin{definition}
A {\em B-object} is an object belonging to class B.
\end{definition}

\begin{definition}
The {\em protocol} of a class C is the set of messages that can be sent
to C and its instances.
\end{definition}

\begin{example}
The protocol of class A consists of messages m1 and m2.
\bv
class B has parts
  x : Ident
  implements interface
    m1() returns Ident
end class B.

class A has parts
  ; none of its own
  inherits from classes B;
  implements interface
    m2() returns Number
end class A.
\end{verbatim}
\end{example}


In the
above example, method m1 is attached to class B.
The return type of m1 is class Ident.
To send a message, we use C++ function call notation: e.g.,
\verb|s->f()| is the same as ``send s the message f''.

We view the instance variables of a class to be private (in the C++ sense)
and, if necessary,
accessible through public methods for modification or reading.

\begin{definition}
A method {\em uses the protocol of a class C} if inside the method a message
is sent to a C-object or to C.
\end{definition}


\begin{definition}
Method M is a client of class B and B is a supplier of method M,
if M uses the protocol of B.\footnote{Our notion of {\em client}
is slightly more restrictive than Meyer's notion of client.}
%if a B-object or B itself are sent a message in method M or if an
%instance variable of B is accessed or modified.
\end{definition}

According to this definition, a method M which gets passed an object
of class B and which passes the object further without directly sending
a message to the object or to B, is {\em not}
viewed as a client of class B.

In the last definition we used the Smalltalk-80
approach which allows us to send a message to a class.
Sending a message to a class B activates a class method
of B (a method of B's ``metaclass'') which might, e.g., create instances of B or initialize a class
variable of B.

\begin{example}
\emptyspace
\bv
class B has parts
  x : Ident
  implements interface
    m1() returns String
end class B.
\end{verbatim}
If method m1 sends a message to x then m1 is a client of Ident and class
Ident is a supplier of method m1.
\bv
               METHOD m1
          |        |                 
client of |        | (sends message 
          |        |  to instance of)
          V        V                
               class Ident
\end{verbatim}
\end{example}

Every class in the system is a potential supplier of any 
method.  However, we want to limit the suppliers to a method to a
small set of preferred classes.  
These are called preferred supplier classes of method M.
To define them we introduce the concept of an
{\em acquaintance class} of a method (\cite{sakkinen:law-88}, 
\cite{hewitt:law}).
The
acquaintance classes of a method are declared 
explicitely in the ``heading'' of the method.

\begin{definition}
A class C1 is an {\em acquaintance class} of a given method M attached
to class C2, if C1's
protocol is used in M, and C1 is not 
\begin{itemize}
\item
the same as C2
\item
an argument class of M
\item
instance variable class of C2
\end{itemize}
\end{definition}

If a class appears as an acquaintance class of several methods,
it is counted as many times as it appears.
We are now ready to give the most permissive formulation of the Law
of Demeter:

\begin{definition}
Minimization form of Law of Demeter:
Minimize the number of acquaintance classes over all methods.
\end{definition}

Acquaintance classes are used for
two typical reasons:
\begin{itemize}
\item
Stability: If a class is stable and/or if its interface will be
kept upward compatible, it makes sense to use it as an acquaintance class
in all methods. The user specifies such ``global'' acquaintance classes
separately and they are included in all acquaintance classes.

\item
Efficiency: To gain efficiency the user might need access to the
instance variables of certain other classes.
In C++ terminology, these are classes of which M is a friend function.
\end{itemize}

We will discuss acquaintance classes further in section 6.
In the following we develop the other, more restrictive, formulations 
of the Law of Demeter:

\begin{definition}
Class B is called a 
preferred supplier of method M (attached to class C) if
B is a supplier of M and 
one of the following conditions holds:
\begin{itemize}
\item
  B is an instance variable class of C or
\item
    B is an argument class of M, including C or
\item
B is a special acquaintance class of M where 
        B is either a class of objects created directly in M or
          B is a class of a global variable used in M.
\end{itemize}
\end{definition}

%One might be tempted to also view a class from which C 
%inherits as a preferred supplier of method M. Our definition, however, excludes
%those ``inheritors'' from the potential preferred suppliers. 

%The reason that we use the two kinds of special acquaintance classes in
%this definition is that later we want to allow other acquaintance classes
%as well.
To match this definition of preferred suppliers we 
have a corresponding definition of preferred clients.

\begin{definition}
Method M is called a preferred client of class B if 
class B is a preferred supplier of method M.
\end{definition}

\begin{example}
In the following 5 examples,
class B is a 
preferred supplier of method M and M is a 
preferred client of B.
We use \verb|;| as the comment character which starts a comment line.

\bv
;instance variable class:
class C has parts
  s : B
  implements interface
    M() returns Ident
      {calls s -> f()}
end class C.

;argument class:
class C has parts
  ; none
  implements interface
    M(s : B) returns Ident
      {calls s -> f()}
end class C.

;argument class:
class B has parts
  ; none
  implements interface
    M() returns Ident
      {calls self -> f()}
      ; in C++ self is called this
end class C.

;newly created object class:
class C has parts
  ; none
  implements interface
    M() returns Ident
      ; new_object is new B-object
      {calls new_object -> f()}
end class C.

; s is of type B, global 
class C has parts
  ; none
  implements interface
    M() returns Ident
      {calls s -> f()}
end class C.
\end{verbatim}
\end{example}

%For describing the benefits of the Law we also need the following 
%definition
%which describes a special kind of clients 
%and and a special kind of suppliers.
%
%\begin{definition}
%Class B is a preferred supplier of method M and M is a preferred client
%of B if B is
%a potential preferred supplier of M whose potential has been realized,
%i.e. B is a supplier of M.
%\end{definition}
%
%The supplier/client terminology is explained in Fig. ``General Store''.
%\begin{figure}
%\vspace{100mm}
%
%\caption{General Store}
%\end{figure}
%
%\subsection{The Law}

\begin{definition}
Law of Demeter :
All methods M  may only have preferred supplier classes.
\end{definition}


Since the protocol of a class includes both messages
to objects and to classes, the Law restricts the use of the
protocol of classes and metaclasses (a metaclass has instances which are
classes; this terminology comes from Samlltalk).
Restricting the protocol of metaclasses might be misleading since
we need to be able to make instances of classes wherever we like. 
Indeed, a close inspection of the Law reveals that it does not
impose any restriction on where we are allowed to make new instances.

%The following reformulation of the Law of Demeter shows the protocol
%restriction aspects.
%
%\begin{fact}
%The following statement is equivalent to the Law of Demeter:
%For all classes B, all client methods of class B must be preferred.
%
%%For all classes B, all clients must be preferred
%%the protocol of class B can only be used in potential 
%%preferred client methods of B.
%\end{fact}
%
%\noindent
%Note that B's protocol includes the protocols of B's superclasses,
%although the methods of B's superclasses are not necessarily
%preferred client methods of B.
%
%%To underline the dependency control aspects of the Law, we
%%need the following definition:
%%
%%\begin{definition}
%%A method M is dependent on class C, if M sends a message
%%to a C-object or to C.
%%\end{definition}
%%
%%Intuitively, if a method M is dependent on class C then changes to
%%C's definition or protocol may also demand changes to M.  Reducing
%%these dependencies is important in controlling the impact and cost
%%of change and maintenance.
%%
%%\begin{fact}
%%Method M is dependent on B if and only if M is a client of B.
%%Method M is dependent on class B if and only if
%%M uses B's protocol.
%%\end{fact}
%%
%%The following reformulation of the Law of Demeter shows the dependency
%%control aspects.
%%
%%\begin{fact}
%%The following statement is equivalent to the Law of Demeter: 
%%Only a potential preferred client method M of class B is allowed 
%%to be dependent on class B.
%%\end{fact}
%
%In \cite{LHLR:law-paper} we stated the Law of Demeter in the following way
%which is a simple expansion of the above definitions.  This form is
%useful for presenting a stronger restriction than the above.
%
%\begin{fact}
%The following statement is equivalent to the Law of Demeter:
%In all methods M attached to class C use only the protocol of the 
%following classes:
%
%\begin{enumerate}
%\item
%  instance variable classes of C or
%\item
%    argument classes of M, including C or
%\item
%special acquaintance classes of M.
%(The special acquaintance classes of M are 
%the classes of objects created directly in M and the classes
%of global variables used in M.)
%\end{enumerate}
%\end{fact}

%The user may add other acquaintance classes:
%Two typical reasons, which are discussed later, are:
%\begin{itemize}
%\item
%Stability: If a class is stable and/or if its interface will be
%kept upward compatible, it makes sense to use it as an acquaintance class
%in all methods. The user specifies such ``global'' acquaintance classes
%separately and they are included in all acquaintance classes.
%
%\item
%Efficiency: To gain efficiency the user might need access to the
%instance variables of certain other classes.
%In C++ terminology, these are classes of which M is a friend function.
%\end{itemize}

%\begin{definition}
%Strong Law of Demeter:
%If we interpret in the Law of Demeter
%``instance variable classes of C'' as meaning the
%classes of instance variables defined for C explicitly and not
%the inherited ones, we get the strong Law of Demeter.
%\end{definition}
%
%The `Strong Law' is useful for protecting the users of inherited
%information from changes to the definition or protocol of 
%superclasses.  Changes to super classes (or base classes) can cause
%subtle and expensive bugs in code that used to work perfectly.
%This more restrictive Law is explained in depth in \cite{LHLR:law-paper}.

\subsection{Conceptual guideline}
So far, we have discussed the class version of the Law of Demeter which can be
enforced at compile-time. For example, it is easy to extend a C++
compiler to check for the Law of Demeter. The price we pay for compile-time enforceability
is that some programs which violate the ``spirit'' of the Law will pass
the test or that some programs which follow 
the ``spirit'' of the Law will be rejected.
Therefore, we present now the object version of the Law which expresses
the spirit of the Law and which serves as a conceptual guideline to be
approximated in programming. We first need to 
define preferred supplier objects.

\begin{definition}
A supplier object of a method M is an object to which a message is sent in M.
The preferred supplier objects of method M 
are:
\begin{itemize}
\item
the immediate parts of {\sf self} or
\item
the argument objects of M or
\item
the objects which are either
objects created directly in M or
objects in global variables.
\end{itemize}
\end{definition}
Notice that we use the phrase ``immediate subparts of {\sf self}'' the
sensible interpretation of which
is left to the user. By illustration, the immediate parts of a list class
are the elements of the list. The immediate parts of a ``regular'' class
are the objects stored in instance variables.

\begin{definition}
Law of Demeter (object version): All methods may only have
preferred supplier objects.
\end{definition}

The object version of the Law expresses {\em what we really want}, but
unfortunately it is hard to enforce at compile-time (this is discussed
in more detail in \cite{LHLR:law-paper}).
The object version serves as an additional guide whenever the class version of the Law accepts a program which appears to be in bad style or when the class
version of the Law rejects a program which appears to be in good style.

\subsection{Benefits of the Law}
Now we are ready to state an important benefit of the Law in
a formal way. There are many other benefits which are harder
to state formally.

%We first give simple
%benefits; the most significant one is the last one.

\begin{fact}
If the Law of Demeter is followed and if
class A's protocol is changed then only the preferred client  methods of 
A and A's subclasses require modification provided that the changes
implied in the preferred client methods do not change the protocol
of those classes.
\end{fact}

This benefit clearly shows that the Law of Demeter limits the impact of change.

%A class consists of objects, the protocol and the composition.
%By the composition of a class we mean the detailed structure of
%its parts, subparts etc.

%By a constructor of a class A we mean a function or method which
%returns a new object of class A taking the some or all subparts as
%arguments.

%\begin{fact}
%If the Law of Demeter is followed and
%if the composition of class A changes (not modifying A's protocol),
%then at most the
%methods of A and A's subclasses need modification.
%\end{fact}

%By ``not modifying A's protocol'', we mean that the public interface of A
%remains invariant.

%following code needs modification:
%\begin{itemize}
%\item
%constructors of A and its subclasses and
%\item 
%methods of A and
%its subclasses.
%\end{itemize}

%\begin{fact}
%If the strong Law of Demeter is followed and
%if the composition of class A changes (not modifying A's protocol),
%then at most the preferred client methods of A need 
%modification.
%\end{fact}
%
%keeping the protocol
%invariant, then at most the the constructors and methods
%of A need modification.

%It is interesting to notice that traditional information hiding can 
%achieve the same as the strong Law in the special case when the composition
%of a class is completely 
%hidden. The composition of a class B is completely hidden if
%all instance variables of B are private (in the C++ sense)
%and any change to the instance variables does not affect the public
%protocol of B.
%In this special case we can state: {\em If the composition of a class is
%completely hidden and if the composition of class A changes then at most
%the methods attached to A need modification}.

%Now we state an important 
%benefit of the Law in the case the protocol of a class changes:
%
%\begin{fact}
%If the weak or strong Law of Demeter is followed and if the protocol of class A
%changes,
%% (keeping the composition invariant), 
%then only preferred client methods of A and its subclasses
%need to be modified and
%only methods in the set of potential preferred clients of
%A and its subclasses need to be added.
%\end{fact}

We can also informally state the following benefit which shows how the
Law controls the complexity of programming:
{\em
When reading a method M, the programmer has only to be aware
of the functionality of the preferred supplier classes of M.
}
The preferred suppliers of a method M are usually a small subset of all
classes of the application and furthermore, they are ``closely related''
to the class to which M is attached. This relationship makes it
easier for the programmer to remember those classes and their functionality.

%The Law of Demeter, when used in coordination with three       
%key constraints, enforces
%good programming style.  These constraints include minimizing
%code duplication, 
%minimizing 
%the number of arguments passed to methods and 
%minimizing the number of methods 
%per class.

\section{The Motivation and Explanation}

The motivation behind the Law of Demeter is to ensure that the software is
as modular as possible.  
%Any method written to obey this Law will only
%know about the immediate structure of the class to which it
%is attached.  
%The structure of the arguments and the sub-structure of C are hidden 
%from M.  Therefore,  should a change to the structure of the class C be
%necessary we need only to look at those methods attached to C and its
%subclasses for
%possible conflicts.  
The Law effectively reduces the occurrences
of certain 
nested message sendings (function calls) and simplifies the methods.

%The Law {\em prohibits} the nesting of generic accessor function calls,
%which return objects that are not instance variable objects.
%It {\em allows} the nesting of constructor function calls.
%An {\em accessor} function is a function which returns an object which
%did exist before the function is called. A {\em constructor} function
%returns an object which did not exist before the function is called.

The Law of Demeter has many implications regarding  widely known 
software engineering principles. 
Our contribution is to condense many of the proven
principles of software design into a single statement which can easily
be used by the object-oriented programmer and which
can be easily checked at compile-time.

Some of the inter-related principles covered by the Law are the following:

\begin{itemize}
\item Coupling control. 

  It is a well-known principle of software design to have minimal coupling 
  between abstractions 
  (e.g., procedures, modules, methods).
%  \cite{emblay-woodfield:quality}.
  The coupling can be along several links. An important link for methods
  is the ``uses'' link (or call/return link) which 
  is established when one method calls another method.
  The Law of Demeter effectively reduces the methods we can call
  inside a given method and therefore limits the coupling of methods
  with respect to the ``uses'' relation. The Law therefore facilitates
  reusability of methods and the abstraction level of the software.

\item Information hiding. 

  The Law of Demeter
  enforces one kind of information hiding: structure hiding. 
  In general, the Law prevents a method from directly retrieving a subpart
  of an object which lies deep in that object's ``part-of''
  hierarchy.  Instead, intermediate methods must be used to traverse
  the ``part-of'' hierarchy in controlled small steps
\cite{liskov-guttag:1986}.
% \cite{emblay-woodfield:quality}.

  In some \oo\ systems, the user can protect some of the instance 
variables or methods of a class from outside access by making them private.
This important feature complements the Law to increase modularity but 
is orthogonal to it.  The Law promotes the idea that the instance variables 
and methods which are public should be used in a restricted way. 


\item Information restriction.

Our work is related to the work by Parnas et al. \cite{parnas:mod-struct}
%\cite {parnas:reuse-83} 
on the modular
structure of complex systems. To reduce the cost of software changes
in their  operational flight program for the A-7E aircraft,
the use of modules that provide information that is subject to change 
is restricted.
We take this point of view seriously
in our object-oriented programming and assume that any class could change.
Therefore, we restrict the use of message sendings (function calls)
by the Law of Demeter.
Information restriction complements information hiding.
Instead of hiding certain methods, we make them public but we restrict
their use.

\item Localization of information.\footnote{Peter Wegner pointed out this aspect
   of the Law.}

  The importance of localizing information
  is stressed in many software engineering
  texts. The Law of Demeter focuses on localizing type information.
  When we study a method we only have to be aware of types which
  are very closely related to the class to which the method is attached.
  We can effectively be ignorant (and independent) of
  the rest of the system and as the old proverb goes: ``Ignorance is bliss''.
  This is an important aspect which helps to reduce the complexity
  of programming. 
  
  From another point of view related to localization,
  the Law controls the visibility of message names.  In a given method
  we can only use message names which are in the signatures of the 
  instance variable types and argument types.


\item Structural induction.

The Law of Demeter is related to the fundamental thesis of Denotational 
Semantics.  That is, ``The meaning of a phrase is a function of the meanings
of its immediate constituents''.  This goes back to Frege's work on the
principle of compositionality in his Begriffsschrift 
\cite{frege:begriffsschrift}.  
The main motivation behind the compositionality principle is that it
facilitates structural induction proofs.
\end{itemize}

\section{Example}

We consider the following class dictionary fragment for a Library.

\bv
class Library has parts
  reference : ReferenceSec
  loan : LoanSec
  journal : JournalSec
end class Library.

class ReferenceSec has parts
  ref_book_sec : BooksSec
  archive : Archive
end class ReferenceSec.

class Archive has parts
  arch_microfiche : MicroficheFiles
  arch_docs : Documents
end class Archive.

class MicroficheFiles has parts
   ...
end class MicroficheFiles.

class Documents has parts
   ...
end class Documents.
 
class BooksSec has parts
   ...
end class BooksSec.

\end{verbatim}

%In this subsection we don't assume that all data members are private.
For the following example we use message passing
terminology to explain 
a C++ program. In C++, sending a message means calling a (virtual)
member function.
To keep the example small, we use direct access to instance variables
instead of using access methods.

Consider the following fragment of
a C++ program in which we search the reference section for a 
particular book:
%see file viol.c
\bv

class ReferenceSec {
public:
  Archive* archive;
  BookSec* ref_book_sec;

boolean search_bad_style(Book* book) {
  return
      ( ref_book_sec->search(book) ||
    archive->arch_microfiche->search(book) ||
    archive->arch_docs->search(book));
        }

boolean search_good_style(Book* book) {
  return archive->search_good_style(book);
  }
};
                                 
class Archive {
public:
  MicroFicheFiles* arch_microfiche;
  Documents* arch_docs;

boolean search_good_style(Book* book) {
  return
      (arch_microfiche->search(book) || 
       arch_docs->search(book));
       }
};
                          
class MicroFicheFiles {
public:
  boolean search(Book* book) {}
};

class Documents {
public:
  boolean search(Book* book) {}
};

class Book { .... };

\end{verbatim}  

The {\sf search\_bad\_style} function attached to {\sf ReferenceSec} passes the message 
on to its book ({\sf BooksSec}), microfiche ({\sf MicroFicheFiles}) 
and document
sections ({\sf Documents}).
This function breaks the Law of Demeter.  The first message marked
  sends the message ``arch\_microfiche'' to ``archive'' which returns
an object of type ``MicroficheFiles''.  The method 
next sends this returned object the search message. 
However, ``MicroficheFiles'' is not an instance variable or 
argument type of class
``ReferenceSec''.
Since the structure of all the classes are clearly defined by the class 
dictionary, we might be tempted to accept the above methods as a reasonable
solution.  
Let us consider a change to the class dictionary.  Assume the library installs
new technology and replaces the microfiche and document sections of the archive
with CD-ROMs or Video-Discs.
\bv
class Archive has parts
  cd_rom_arch : CD_ROM_File
end class Archive.

class CD_ROM_File has parts
  cd_c_system : ComputerSystem
  discs : CD_ROM_Discs
end class CD_ROM_File.
\end{verbatim}
We now have to search all of the methods, including the
{\sf search\_bad\_style} method, for references to an archive with microfiche
files.
It would be easier to contain the modifications only to those methods which are
attached to class {\sf Archive}.
We accomplish this by rewriting the methods in good style resulting in
search\_good\_style functions attached to ReferenceSec and Archive.

Notice how the coupling with respect to the ``uses'' relation has been reduced.
{\sf ReferenceSec} was coupled with {\sf BooksSec}, 
{\sf Archive}, {\sf MicroficheFiles} and 
{\sf Documents} in the original version.  Now it is coupled only with 
{\sf BooksSec} and
{\sf Archive}.

Next we visualize the consequence of the Law of Demeter by showing
the good and the bad program for the search problem in a picture.
We translate a program into a graph as follows:
The nodes of the graph are classes.
An edge from class A to class B has an integer label which indicates
how many calls are written in the text of the
functions of A to the functions of B. 
If a label is omitted from an edge, it means that
its value is 1. Access to an instance variable
is interpreted as a call to read the instance variable.

Fig. ``Bad design'' shows the graph for the program which violates
the Law of Demeter.

\begin{figure}
\vspace{40mm}
\bv
                 1
            --------> Documents      
            |
            |    1
ReferenceSec ------> MicroficheFiles
|           |
|1          |2
|           |
V           V
BooksSec   Archive  
\end{verbatim}
\caption{Bad design, with 2 acquaintance classes}
\end{figure}

\begin{figure}
\vspace{40mm}
\bv
ReferenceSec 
|           |
|1          |1
|           |
V           V
BooksSec   Archive  
            |
            |    1
            |--------> Documents
            |
            |    1
            |--------> MicroficheFiles

\end{verbatim}
\caption{Good design, no acquaintance classes}
\end{figure}

From now on we give examples in both Flavors and C++, but we 
use Smalltalk/Flavors terminology to explain the examples.
In C++, instance variables are called data members and methods are called
member functions. In the C++ examples which we use, the types of data 
members and function arguments are pointer types to classes.

For a discussion of the complexity of programming
point, consider the following example:

\bv
Flavors:
(defmethod (C :M) ()
  (send (send a :m1) :m2))
\end{verbatim}

\bv
C++:
void C::M()
  {a -> m1() -> m2();}
\end{verbatim}

where {\sf a} is an instance variable of {\sf C} and {\sf m1}
and
{\sf m2} are user-defined methods (not instance variable access methods).
Let's assume that {\sf m1} does not return an object which is of an instance variable type 
of {\sf C}. Therefore, the nested send expression is in bad style.
But this expression does not make it easier nor harder to modify the
methods when the \dd\ changes. 
However, it requires the programmer to think about other types 
than the instance variable types of C.
The above method can be rewritten in good style as
\bv
Flavors:
(defmethod (C :M) ()
  (send self :m3 (send a :m1)))

(defmethod (C :m3) (arg :type Argtype)
  (send arg :m2))
\end{verbatim}

\bv
C++:
void C::M()
  {this -> m3(a -> m1()); // ...  }

void C::m3(Argtype* arg)
  {arg -> m2(); // ...  }
\end{verbatim}

Here the additional type is made explicit as an argument type.
Sometimes it is possible to rewrite a program of the above form
without introducing additional arguments.

\section{Anarchy: valid violations of the Law}
The Law is intended to act as a guideline and not as
an absolute restriction.  The programmer has the choice
whether to follow it or not.  In this section, we outline
a few situations when the cost of obeying the Law may be greater
than the benefits.  However, when the Law is willingly violated, the
programmer takes on the responsibility to provide future
maintainers support, with documentation, which
otherwise would have been provided by the Law.  Consider
the following prototypical method which
is in bad style:
\begin{verbatim}
Flavors:
(defmethod (C :M) (p)
   ( .... (send (send p :F1)  :F2) ....))
\end{verbatim}

\bv
C++:
void C::M(D* p)
  {p -> F1() -> F2();
    // ...
  }
\end{verbatim}
where p is an instance of class A and F1 returns
a subpart of p.  If the immediate composition of A changes the
method M may have to change also because of F1.  Here are two
situations when it is reasonable to leave the above as it is:
\begin{itemize}
\item
F1 is intended to serve as a ``black box"  and the programmer
knows only about the types of its arguments and the return type.
In this case, the maintainer of F1 has the responsibility to ensure that
any updates to F1 are upward compatible so as not to punish any
users of the function.
\item
If run-time efficiency is important to the application, the use
of mechanisms like friend functions of C++ may be necessary. 
Friend functions should be used carefully, since whenever the private members
of a class change, the friend functions of the class
also might change.
\end{itemize}

In an application which solves differential 
equations the following definitions may occur:
\begin{verbatim}
class Complex_Number has parts
  real_part : Real 
  imaginary_part : Real
end class Complex_Number.

Flavors:
(defmethod (Vector :R) (c :Complex_Number)
   ( .....  
     (send (send c :real_part) 
       :project self) ....))
\end{verbatim}

\bv
C++:
void Vector::R(Complex_Number* c)
  { 
    c -> real_part -> project(this)
  }
\end{verbatim}

The method R is in the same form as M above and is in
bad style for the same reason.  The question is whether it is important
to hide the structure of complex numbers and to rewrite the method.
In this application where the concept of a complex number is well
defined and well understood it is unnecessary to rewrite the method
so that the Law is obeyed.
   
In general, if the application concepts are well defined and the
classes which implement those concepts are stable, in the sense that
they are very unlikely to change, then such violations as the above
are acceptable.

We introduced earlier the concept of an 
{\em acquaintance class} of a method. The motivation for this
concept is to have a systematic,
compile-time enforceable control of adhearance to the Law. The
acquaintance classes of a method are declared in the ``heading'' of a method
and they are added to the preferred suppliers of the method.
When a method has acquaintance classes declared, the programmer is warned that there
are ``unusual'' dependencies between the classes.
The compile-time
Law enforcement program has the necessary information to suppress
Law violation messages. 

We repeat here the most flexible formulation of the Law of Demeter:

\begin{definition}
Minimization form of Law of Demeter:
Minimize the number of acquaintance classes over all methods.
\end{definition}

%With the presence of acquaintances we formulate
%the Law (class version) as follows: In all methods M attached to class C, use only the protocol
%of the following classes:
%\begin{itemize}
%\item
%instance variable classes of C or
%\item
%argument classes of M, including C or
%\item
%acquaintance classes of M.
%\end{itemize}
%
%The goal is to write methods with a minimal number of acquaintances.
We can prove that any \oo\ program can be written without acquaintance classes,
except the ones needed to create objects
\cite{LHLR:law-paper}.

To easily check the Law at compile-time, the user has to provide the
following documentation for each method:

\begin{itemize}
\item
the types of each of the arguments and the result,
\item
the acquaintance classes.
\end{itemize}

The Law enforcement program has to keep 
track additionally of the following information
about each method:
\begin{itemize}
\item
the message sendings inside the method and
\item
the classes of the objects created directly by the method.
\end{itemize}

%Since our primary goal is to produce guidelines for the production of
%software which can be easily maintained we should also consider how the
%software should be documented.   
%The documentation of a method should include the production which
%defines the class to which the method is attached.
%This production defines all the instance variable types.
%In addition, a method documentation should contain
%\begin{itemize}
%\item
%the types for each of the arguments
%\item
%the return types of methods which create and return new instances.
%\item
%a list of acquaintance classes.
%\end{itemize}

The documentation gives the reader of the method a list of types he or she
has to know about for understanding the method.

Writing programs which follow the the Law of Demeter decreases the 
occurrences of nested message sending and decreases the complexity of
the methods, but it increases the number of methods.  
The latter is related to the problem outlined in \cite{liskov-guttag:1986}
which
is that there can be too many operations in a type.
In this case the abstraction may be less comprehensible, and
implementation and maintenance are more difficult.
There might also be an increase in the number
of arguments passed to some methods.  

One way of correcting this
problem is to organize all the methods associated with a particular
functional (or algorithmic) task into ``Modula-2 like'' module structures
as outlined in \cite{lieber-riel:oop}.
So the functional abstraction is no longer a method but a module
which
will hide
the lower-level methods  which caused the original
confusion.

\section{Conforming to the Law}

Given a method which does not satisfy the Law, how can we transform it
so that it conforms to the Law? In \cite{LHLR:law-paper}
we described an algorithm for transforming
any \oo\ program into an equivalent program which satisfies the Law.
In other words, we showed that we can translate any \oo\ program
into a ``normal form'' which satisfies 
the weak
Law.\index{normal form for \oo\ programs}

The transformations given in that paper allow us to translate a given program
in bad style into good style.  There are other, though less automatic, ways
to achieve this goal which may help in arriving at more
readable or intuitive code.  These also may help in minimizing
the number of arguments passed to methods and 
occurrences of code duplication.
The following outlines two other transformation techniques.

We need the following recursive definition:

{\sf B} is a part-class of {\sf A}, 
if {\sf B} is an instance variable class of {\sf A} or {\sf B}
is a part-class of
an instance variable class of {\sf A}.
%\footnote{This expresses the 
%desired intuitive
%notion. A more correct definition requires more Demeter machinery than is
%appropriate here.} 
%See \cite{lieber-riel:oop}\cite{karl:demeter}}.

Consider the method:
\bv
Flavors:
(defmethod (C :M) ()
  (send (send self ':m1) ':m2))
\end{verbatim}

\bv
C++:
void C::M()
  {this -> m1() -> m2();}
\end{verbatim}

Let {\sf T} be the class of the object returned from {\sf (send self ':m1)
(this -\verb|>| m1())}.
We distinguish  three cases:
\begin{enumerate}
\item
  {\sf T} is a part-class of {\sf C}.
  \item
  {\sf C} is a part-class of {\sf T}.
  \item
  {\sf T} and {\sf C} are not related.
\end{enumerate}

We can attempt the following transformations:
\begin{itemize}
\item Lifting.

This is applicable if {\sf T} is a part-class of {\sf C}.
The idea is to make {\sf m1} return an object of an
instance variable or argument class of {\sf C} and
adjust {\sf m2} accordingly.  So the method {\sf m2} is being lifted
up in the class hierarchy from being attached to class {\sf T} to
being attached to an instance variable class of {\sf C}.

Example:  Suppose we wish to parse an input with respect to some grammar.
A grammar is made up of a list of rules indexed by rule name.

\bv
; class Grammar is list
;   repeat {Rule}
; end class Grammar.

; class Rule has parts
;   body : Body
; end class Rule.

Flavors:
(defmethod (Grammar :parse) (rule_name :type Symbol)
  (send (send self ':look_up rule_name) ':parse_details))

(defmethod (Grammar :look_up) (rule_name :type Symbol)
  ... (send (send rule ':look_up rule_name) ':get_body))

(defmethod (Body :parse_details) ()
   .........
)
\end{verbatim}

\bv
C++:
void Grammar::parse(Symbol* rule_name)
  {this -> look_up(rule_name) -> parse_details();}

Body* Grammar::look_up(Symbol* rule_name)
  {...
    return rule -> look_up(rule_name) -> get_body();
  }

void Body::parse_details()
  { ... }
\end{verbatim}

This program fragment uses one acquaintance class
(class {\sf Body} in the method {\sf parse} for
Grammar) and is represented by Fig. Design Grammar 1.

\begin{figure}
\bv
|---<---|
|      1|
|       |
|--->---Grammar
        |     \
       2|     1\
        |       \
        V        V
      Rule      Body
\end{verbatim}
\caption{Design Grammar 1}

\end{figure}

The problem with the above is that method {\sf look\_up} 
of {\sf Grammar} returns an object of type
{\sf Body} which is not an instance variable type of {\sf Grammar}.
To transform the first method into good style, we make the {\sf look\_up} method
return an instance of {\sf Rule} and we adjust {\sf parse\_details}.

%; class Grammar is list
%;   repeat {Rule}
%; end class Grammar.
%
%; class Rule has parts
%;   body : Body
%; end class Rule.

\bv
(defmethod (Grammar :parse) (rule_name :type Symbol)
  (send (send self ':look_up rule_name) ':parse_details))

(defmethod (Grammar :look_up) (rule_name :type Symbol)
  ... (send rule ':look_up rule_name))

(defmethod (Rule :parse_details) ()
   ..(send self ':get_body) ...
)
\end{verbatim}

\bv
C++:
void Grammar::look_up(Symbol* rule_name)
  {this -> look_up(rule_name) -> parse_details();}

Rule* Grammar::look_up(Symbol* rule_name)
  {...
     return rule -> look_up(rule_name);}

void Rule::parse_details()
  {... this -> get_body(); ...}

\end{verbatim}
This improved program fragment does not use any acquaintance class and
is represented by Fig. Design Grammar 2.

\begin{figure}
\bv
|---<---|
|      1|
|       |
|--->---Grammar
        |     
       2|   
        |  
        V 
|---<---Rule    Body
|      1|
|       |
|--->---|
\end{verbatim}
\caption{Design Grammar 2}
\end{figure}

This lifting approach does not always work. Consider:
\bv
; class Grammar has parts
;   ruleList : RuleList
; end class Grammar.

; class RuleList is list
;   repeat {Rule}
; end class RuleList.

; class Rule has parts
;   rule : Rule
; end class Rule.

(defmethod (Grammar :parse) (rule_name :type Symbol)
  (send (send-self ':look_up rule_name) ':parse_details))

(defmethod (Grammar :look_up) (rule_name :type Symbol)
; returns object of type Rule
  ...
  (send ruleList ':look_up rule_name))

(defmethod (RuleList :look_up) (rule_name :type Symbol)
  .........
)

(defmethod (Rule :parse_details) ()
  .........
)
\end{verbatim}

\bv
C++:
void Grammar::parse(Symbol* rule_name)
  {this -> look_up(rule_name) -> parse_details();}

Rule* Grammar::look_up(Symbol* rule_name)
  { ...
     ruleList -> look_up(rule_name);
  }

void RuleList::look_up(Symbol* rule_name)
  { ... }

void Rule::parse_details()
  { ... }
\end{verbatim}

This program fragment uses one acquaintance class
(class {\sf Rule} in method {\sf parse} of {\sf Grammar})
and is represented by Fig. Design RuleList 1.

\begin{figure}
\bv
|---<---|
|      1|
|       |
|--->---Grammar
        |     \
       1|     1\
        |       \
        V        V
    RuleList   Rule
\end{verbatim}
\caption{Design RuleList 1}
\end{figure}

Here we cannot transform the first method into good style by lifting
the return type of the {\sf look\_up} method.

\item Pushing.
This technique is applicable in cases 1 and 2\footnote{Case 2 is slightly
more complicated as it involves traveling up the object hierarchy but
the general technique is the same as for case 1.} above.
It is just a variation of the top-down programming technique of
pushing the responsibility for doing the work to a 
lower level procedure.

In the above example the problem arises because the Grammar class has the 
task of sending the 
{\sf parse\_details} message.  This task is really the responsibility
of {\sf RuleList} who knows more about {\sf Rule} details than {\sf Grammar}.  
\bv
(defmethod (Grammar :parse) (rule_name)
  (send self ':look_up_parse rule_name))

(defmethod (Grammar :look_up_parse) (rule_name)
  (send ruleList ':look_up_parse rule_name))

(defmethod (RuleList :look_up_parse) (rule_name)
  (send (send-self ':look_up rule_name) ':parse_details))
\end{verbatim}

\bv
C++:
void Grammar::parse(Symbol* rule_name)
  {this -> look_up_parse(rule_name);}

void Grammar::look_up_parse(Symbol* rule_name)
  {ruleList -> look_up_parse(rule_name);}

void RuleList::look_up_parse(Symbol* rule_name)
  {this -> look_up(rule_name) -> parse_details();}
\end{verbatim}
\end{itemize}

This improved design does not use any acquaintance classes and is
represented in Fig. Design RuleList 2.

\begin{figure}
\bv
|---<---|
|      1|
|       |
|--->---Grammar
        |     
       1|   
        |  
        V         1 
|---<---RuleList-----> Rule
|      1|
|       |
|--->---|
\end{verbatim}
\caption{Design RuleList 2}
\end{figure}

Remark: The redesign has introduced an additional method. If we view
list classes as stable (which is for example the case in Smalltalk),
there is no need for the redesign and it is justified to keep
the acquaintance class of Design RuleList 1.

\section{Conclusion}
In this paper we have introduced a simple rule which we believe
helps the production of structured and maintainable software.
This rule, which we call the ``Law of Demeter'', encodes the ideas
of data hiding and encapsulation in an easy to follow form for the \oo\/
programmer.  The Law can be easily checked at 
compile-time for a large class of \oo\ programs.
The style of modular programming encouraged by the Law leads
naturally to the construction of an interface between the application
software and the implementation details of the class and object hierarchies.
It is this interface which, together with the Law, enables the programmer to
redesign the data structures and still leave most of the existing software
intact.  We require this level of flexibility in any scenario which exhibits
a high rate of modification.  Effectively reducing the impact of 
local changes to a software system can reduce many of the headaches of
software maintenance. 

We have seen that there is a price to pay.  The greater the
level of protocol restriction (a refinement of hiding), the greater the penalties are in terms of the
number of methods, speed of execution, number of arguments to methods and
sometimes readability of the code.  
But in the long term these are not 
fatal penalities.  Using ``Modula-2 like'' modules to collect related
methods and definitions together helps significantly in organizing
the increased number of smaller methods into maintainable packets.
%We have already implemented such a structure within the
%Demeter system.  
This facility along with the support of an 
interactive CASE environment can erase some of the penalties.  The
execution deficit can be removed by preprocessor or compiler
technologies like inline code expansion or code optimization similar
to the way tail recursion optimization is done at the moment.


In the past year, over one hundred undergraduate and graduate students
scrutinized, challenged and tested the Law of Demeter.  We have applied
the Law in the ongoing development of the Demeter system (now over fourteen
thousand lines of Lisp/Flavors and C++ code).  Some  very recent 
developments have also been some of the more intricate, e.g., a generic
parser capable of parsing any input with respect to any class
dictionary.  The Law never prevented us from achieving our algorithmic goals
(as guaranteed by our proof) however it was sometimes the case that
the methods had to be rewritten to comply with it.  This task was not
difficult and the results were generally more satisfying.  In the context
of the Demeter system which is an energetically growing system the Law
is an invaluable asset.  We have been using the Demeter system itself
to automate the porting of the system to C++ and this task is made
very much simpler because of the uniform, modular structure of the
existing code.

We are continuing our investigation of modular \oo \/ programming and we
believe that the Law and its consequences will lead to the future development
of ``good'' software.  In addition, the Law allows us to consider 
a normal form for \oo \/
programs which we hope will form a basis for the development of \oo \/ 
program verification techniques. 
The Demeter team can be reached electronically on CS net:
lieber@corwin.CCS.northeastern.EDU

\paragraph{Acknowledgements}
We would like to thank Gar-Lin Lee for her feedback and contributions
during the development of the ideas in this paper.  Thanks also to Jing
Na who, along with Gar-Lin, tested the practicality of using the Law during
the production of some of the Demeter system software.  
%Mitch Wand 
%was instrumental in initiating the investigation into the weak and
%strong
%interpretations.
Carl Woolf suggested that the object version of the Law is the one
to be followed conceptually. 
Special thanks are due to Arthur Riel who was a 
principal author on earlier versions of this paper.

Members of the CLOS community (Daniel Bobrow, Richard Gabriel, 
Jim Kempf, 
Gregor Kiczales, 
Alan Snyder, 
etc.) have participated in the debate and/or formulation
of the CLOS version of the Law.

We would like to thank Markku Sakkinen for his interesting paper
\cite{sakkinen:law-88} and his helpful mail messages about the Law
of Demeter.

Cindy Brown and Mitch Wand convinced us that we should use a more readable
notation than EBNF
and they helped us in designing it. Paul Steckler and Ignacio
Silva-Lepe made several contributions to the extended Demeter notation.

The references not given below are in \cite{benefits:law-89}.

%\bibliography{/fiona/csfaculty/lieber/papers/new-obj/bibliography/biblio}
%\bibliography{biblio}
%\end{document}



\bibliography{biblio}
\section{Appendix: Formulations for existing languages}

We give the formulation of some of the Law of Demeter 
versions in a few object-oriented languages.
Each formulation adapts the Law to the terminology of the particular language.
\begin{itemize}
\item
LAW OF DEMETER (Smalltalk-80 \cite{goldberg:smalltalk-l-i}, object version) 

In all message expressions inside a method M 
the receiver must be one of the following objects:
\begin{enumerate}
\item
an argument object of M including objects in 
      pseudo variables "self" and "super" or
\item
an immediate part of self
      or
\item
an object which is either
an object created directly by M 
or an object in a global variable.
  \end{enumerate}

%\item
%C++:
%type, 
%message passing.
%
%C++ allows overloading of function names
%with respect to several arguments.
%But run-time implicit case analysis is done only with the first argument.
%\bv
%----- LAW OF DEMETER (C++, type version) -------------
%Every member or friend function M of a 
%class C is only allowed to call member
%or friend functions of the following classes:
%  - The argument classes of M (including C),
%  - The data member classes of C,
%  - The classes of objects created by M (directly, 
%      by calling a constructor function or indirectly, 
%      by calling a function which will call 
%      eventually a constructor function)
%  - The classes of global objects.
%----------------------------------------------------------
%\end{verbatim}

\item
CLOS \cite{clos:bobrow-88}: We assume that the user can determine 
for each generic function the number of method selection
arguments (not necessarily all required ones) and that this number is
part of the interface of the generic function.
A method selection argument is an argument which is used
for identifying the applicable methods.

\noindent
LAW OF DEMETER (CLOS, object version) 

All function calls inside a method M must use only the 
following objects as method selection arguments:
\begin{enumerate}
\item
M's argument objects or
\item
immediate parts of
method selection arguments of M or
\item
an object which is either
an object created directly by M
or an object in a global variable.
\end{enumerate}

Note that this formulation implies that the only legal use of
function slot-value is on method selection arguments.

%\bv
%----- LAW OF DEMETER (CLOS, pure type version) -----------
%In all function calls inside a method M all method 
%selection argument objects must belong to one of the 
%following classes:
%  - argument classes of M
%  - slot classes of method selection argument classes of M.
%----------------------------------------------------------
%\end{verbatim}

\item
LAW OF DEMETER (Old Flavors, object version) 

In any method M attached to class C send only messages 
to the following objects:
\begin{enumerate}
\item
M's argument objects or
\item
the instance variable objects of C or
\item
an object which is either 
an object created directly by M 
or an object in a global variable.
\end{enumerate}

\item
LAW OF DEMETER (C++, class version)
In all member functions M of class C use only members (function and data)
of the following classes and their base classes:
\begin{enumerate}
\item
C
\item
data member classes of C
\item
argument classes of M
\item
special acquaintance classes of M which are either classes whose constructor
functions are called in M or the classes of  global variables used in M.
\end{enumerate}

\item
LAW OF DEMETER (Eiffel \cite{meyer:book-88}, object version) 

In all calls of routines inside a routine M 
the entity object must be one of the following objects:
\begin{enumerate}
\item
  an argument object of M or
\item
  an attribute object of the class in which M is defined or
\item
  an object created directly by M.
\end{enumerate}

\end{itemize}

%\bibliography{/fiona/csfaculty/lieber/papers/new-obj/bibliography/biblio}
%\tableofcontents
%\input appendix.tex

\end{document}