\begin{abstract}
We introduce a simple, programming 
language independent rule (known in-house as the Law of \demsign) 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 ?
You tend to get the following related benefits when you 
follow the Law of Demeter while minimizing simultaneously code duplication,
the number of method arguments and the number of methods per class:
Easier software maintenance, 
less coupling between your methods,
better information hiding,
narrower interfaces,
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}

%\begin{abstract}
%We introduce a simple rule (known in-house as the Law of \demsign) which
%encodes the ideas of encapsulation and modularity in an easy to follow form
%for the \oo \/ programmer. 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.
%\end{abstract}
\medskip
\noindent
{\bf Keywords}:
Object-oriented programming, programming style, design style,
software engineering principles, software maintenance and
reusability.

\medskip
\noindent
A short version of this paper appeared in IEEE Computer, June 1988, Open
Channel, page 79.
%\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 asked ourselves many stylistic questions such as,
\bv
Copyright (C) 1988 ACM

Appears in OOPSLA '88,
San Diego, California,
Sept. 25-29

\end{verbatim}

``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. Indeed,
we hope to provide a guiding principle to help such developments. 
We have examined
our own code (about fourteen thousand lines of Lisp/Flavors) 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 after the Demeter system which provides
a high-level interface to class-based \oos s. 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) which impressively simplify the programming task. Examples
of generated utilities are: application development plans, 
application skeletons,
parsers, pretty printers, type checkers, object editors, LL(1) corrections
\cite{karl1:class} \cite{lieber-riel:oop}.
The explanations and examples presented in this paper are written in the notation
of Demeter, a modified EBNF notation 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
being written 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 not only relevant 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}.  
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 programs
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.

In addition, we believe that programs which obey the Law will be more amenable
to program verification (along the lines of \cite{hoare:72}) and 
parameterization by
example techniques.  By the latter, we mean techniques which will allow
us to take an existing class hierarchy and associated software and
produce a more general system by treating some classes as parameters.


We challenge \oo\ programmers to check whether their programs
follow our Law and where they do not, to consider whether they should.
We welcome any comments and/or examples which require a contradiction to
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.  We present a proof which
states that any \oo\ program\footnote{The proof is phrased in Lisp/Flavors
notation but can be generalized to cover other syntax.} 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}
The class hierarchy in Demeter is described using three kinds of production
rules. A collection of these production rules is called a class dictionary.

\begin{enumerate}
\item A {\em construction} production is used to build a class from a number
of other classes and is of the form
%$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 an identifier $id_{i}$ (called an
instance variable name) and a type
$SC_{i}$ (called an instance variable type).  This means that
for any instance (or member) of C the identifier 
$id_{i}$ refers to a member of 
class $SC_{i}$.  We use class and type
as synonyms. The following example describes a library class as consisting
of a reference section, a loan section, and a journal section. 
\bv
Library = 
  <reference> Reference-Sec 
  <loan> Loan-Sec
  <journal> Journal-Sec.
\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} production allows us to express
a union type. A 
production of the form $C : A | B. $ states that a member of C is a member
of class A or class B (exclusively). For example,
\bv
Book-Identifier : 
  ISBN | Library-of-Congress.
\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} production is simply a variation of the construction
production where all the instance variables have the same type and we do not
specify the number of instance variables involved. The production 
 $C \sim \{A\}$ defines members of C to be lists of zero or more instances of
A. 


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

\begin{verbatim}
Reference-Books-Sec = 
  <ref-books> List-of-Books 
  <ref-catalog> Catalog.
List-of-Books ~ {Book}.
Catalog ~ {Catalog-Entry}.
Book = 
  <title> String 
  <author> String 
  <id> Book-identifier.
\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 {\tt Math-Text} is also a member of {\tt 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 so the methods are written in the Lisp/Old-Flavors notation.

Before we introduce the Law, two definitions are appropriate:
\begin{itemize}
\item
We call the set formed by taking the union of the set of methods 
attached to a class C and  the set of methods attached to C's super 
classes, the {\em signature} of C.
\item 
We define a set of classes associated with a given class,
called {\em associated(C)}.
If $C$ is defined by an alternation production (e.g. $C : A | B. $)
then the set {\em associated(C)}
is the union of the classes associated with the alternatives
in the \rhs\ of $C$'s production.
If $C$ is defined by a construction or repetition  production 
$associated(C)$ is $C$ itself.
\end{itemize}


\section{The Law of Demeter}
\rule{81mm}{2mm}
{\bf
For all classes C, and for all methods M attached to C, all
objects to which M sends a message must be 
%In any method M attached to a class C only send messages to 
instances of classes  associated 
with the following classes:

\begin{enumerate}
\item The argument classes of M (including C).
\item The instance variable classes of C.
\end{enumerate}
(Objects created by M, or by functions or methods which M calls, and objects in global variables are considered
as arguments of M.)}
\rule{81mm}{2mm}

\noindent This Law has two primary purposes:
\begin{enumerate}
\item Simplifies modifications. It simplifies the updating of a program
when the class dictionary is changed.

\item Simplifies complexity of programming.  It restricts the number of types
the programmer has to be aware of when writing a method.
\end{enumerate}

The Law of Demeter, when used in coordination with three	
key constraints, enforces
good programming style.  These constraints require 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 this Law 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 (generic 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 a 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.  Our 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 (generic 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 focusses 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 Narrow interfaces. 

  The maintenance of narrow interfaces between interacting entities
  is also important (see e.g. \cite[page 303]{liskov-guttag:1986}).
  A method should have access to only as much information as it needs
  to do its job. If a method gets too much information, 
  it has to destructure 
  this information (via many nested sends)
  which the Law of Demeter discourages. Therefore
  The Law promotes narrow interfaces between methods.

\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}

The Law is stated in terms of types and, as the following pathological
example shows, its formulation does allow situations which violate the
the principles that it is to enforce. 
Consider the class dictionary
\begin{verbatim}
A = <first> B <second> C 
  <third> D <fourth> E.
B = <fifth> C <sixth> D.
D = <seventh> E.
\end{verbatim}
and the method
\bv
(defmethod (A :bad-style)()
  (send (send (send-self :first) 
    :sixth) :seventh))
\end{verbatim}
All of the types in the body of this method,  {\tt B}, {\tt D}, and 
{\tt E}, are valid message
receivers according to the Law. Yet the method looks two levels deep
into the structure of 
instance variable {\tt first}, 
violating the ideals of information-hiding and maintainability.

This problem can be removed by formulating the Law in terms of objects.\\
\rule{81mm}{2mm}
{\bf
For all classes C, and for all methods M attached to C, all
objects to which M sends a message must be 
%In any method M attached to a class C only send messages to 
%the following objects
\begin{itemize}
\item
M's argument objects, including the self object or
\item
The instance variable objects of C.
\end{itemize}
(Objects created by M, or by functions or methods which M calls,
and objects in global variables are considered
as arguments of M.)}
\rule{81mm}{2mm}

By an argument object we mean an object passed by an argument. By an 
instance variable object we mean the object stored in an instance variable.
From a conceptual point of view this seems the most natural way to state
the Law.  However, checking this Law at compile-time is complicated since
it would involve a detailed analysis of aliases.

Consider
\bv
;A = <x> B.
(defmethod (A :alias) (t)
  (send self :set-x (send t :x)))
   
;T = <x> B.
(defmethod (T :m2) (a)
  (send (send a :x) :m3))
\end{verbatim}
      
Is this in good style? It depends on the context.
       The following is o.k.
\bv
(send iA :alias iT) (send iT :m2 iA)
\end{verbatim}
But \verb?(send iT :m2 iA)? by itself violates the Law.

So, to retain easy compile-time checking we require the Law's formulation
in terms of types.  We feel that such pathalogical cases as the one
above will not occur often enough to cause problems.

\section{Example}

We expand the Library definition in the above example into a nearly complete
class dictionary.

\begin{verbatim}
Library = 
  <reference> Reference-Sec 
  <loan> Loan-Sec
  <journal> Journal-Sec.
Reference-Sec = 
  <ref-book-sec> Books-Sec 
  <archive> Archive.
Archive = 
  <arch-microfiche> Microfiche-Files 
  <arch-docs> Documents.
Microfiche-Files = 
  <micro-list> List-of-Microfiche 
  <micro-cat> Microfiche-Catalog.
Books-Sec = 
  <books> List-of-Books 
  <book-catalog> Catalog.
List-of-Books ~ {Book}.
Catalog ~ {Catalog-Entry}.
Book = 
  <title> String <author> String 
  <id> Book-identifier.
Book-Identifier : ISBN | Library-of-Congress.  
\end{verbatim}

Suppose we wish to attach a method to the class {\tt Library}
which will
search its reference section for a specific book.  

\begin{verbatim}
(defmethod (Library :Ref-Search) 
    (book :type Book-Identifier)
  (send reference :Ref-search book))

\end{verbatim}
   
The class {\tt Library} simply passes the message on to class 
{\tt Reference-Sec}.

\begin{verbatim}
(defmethod (Reference-Sec :Ref-search) 
    (book :type Book-Identifier)
  (or (send ref-book-sec :search book)
(**)  (send 
        (send archive :arch-microfiche) 
	  :search book)
(**)  (send 
	(send archive :arch-docs) 
	  :search book)))


(defmethod (Microfiche-Files :search) 
  (book :type Book-Identifier)
         ...... )
(defmethod (Documents  :search) 
  (book :type Book-Identifier)
         ...... )
(defmethod (Books-Sec  :search) 
  (book :type Book-Identifier)
         ...... )
\end{verbatim}

The {\tt Ref-search} method attached to {\tt Reference-Sec} passes the message 
on to its book, microfiche and document
sections as explained below. This method breaks the Law of Demeter.  The first message marked
(**)  sends the message ``arch-microfiche'' to ``archive'' which returns
an object of type ``Microfiche-Files''.  The method next sends this returned object 
the ``search'' message.
However, ``Microfiche-Files'' is not an instance variable or 
argument type of class
``Reference-Sec''.
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
Archive = <cd-rom-arch> CD-Rom-File.
CD-Rom-File = 
  <cd-c-system> Computer-system 
  <discs> CD-Rom-Discs.
\end{verbatim}
We now have to search all of the methods, including the
{\tt Ref-search} 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 {\tt Archive}.
We accomplish this by rewriting the methods in good style.

\begin{verbatim}
(defmethod (Reference-Sec :Ref-Search) 
    (book :type Book-Identifier)
  (or (send ref-book-sec :search book)
      (send archive :search book)))

(defmethod (Archive :search) 
    (book :type Book-Identifier)
  (or (send arch-microfiche :search)
      (send arch-docs :search)))
\end{verbatim}

Notice how the coupling with respect to the ``uses'' relation has been reduced.
{\tt Reference-Sec} was coupled with {\tt Books-Sec}, 
{\tt Archive}, {\tt Microfiche-Files} and 
{\tt Documents} in the original version.  Now it is coupled only with 
{\tt Books-Sec} and
{\tt Archive}.

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

\bv
(defmethod (C :M) ()
  (send (send a :m1) :m2))
\end{verbatim}
where {\tt a} is an instance variable of {\tt C} and {\tt m1}
and
{\tt m2} are user-defined methods (not instance variable access methods).
Let's assume that {\tt m1} does not return an object which is of an instance variable type 
of {\tt 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
(defmethod (C :M) ()
  (send self :m3 (send a :m1)))

(defmethod (C :m3) (arg :type Argtype)
  (send 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{The Trade-off}
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{The Interface}
Suppose we want to send a message to a reference section which is to return
its book catalog.  The method definition might look like the following.

\begin{verbatim}
(defmethod (Reference-Sec :return-book-cat) ()
  (send ref-book-sec :book-catalog))
\end{verbatim}

The above method appears to obey the Law of Demeter, since we are sending an
instance variable type of {\tt Reference-Sec} a message.  However,  on closer 
inspection we see that 
the message being sent is the name of an instance variable which is 
not a part of {\tt Reference-Sec}.  This creates a situation in which the above 
method is sensitive to changes within the structure 
of the {\tt Books-Sec} class.
This clearly violates the spirit of the Law.  The solution to this 
problem is to rewrite the methods as follows.

\begin{verbatim}
(defmethod (Reference-Sec :return-book-cat) ()
  (send ref-book-sec :return-book-cat))

* (defmethod (Books-Sec :return-book-cat) ()
    (send-self :book-catalog))
\end{verbatim}

The method marked with an asterisk at first sight seems to be just a renaming
of the instance variable name at the cost of one more method look-up. This
is true but is better explained as the introduction of an
interface between the {\tt Reference-Sec} 
object and the {\tt Books-Sec} object. This
kind of interface has some very real advantages when it comes around to future
updating of the software \cite{snyder:wegner-87}. CLOS allows automatic
generation of such an interface. A full interface 
of this sort
would provide methods for accessing and setting the
instance variables and thus hiding all the implementation details. Should the
class be modified at a later stage these interface methods may be changed
in an upward compatible way.  The approach can also be taken when creating
objects. 

The 
Flavors mechanism for creating new objects (make-instance)
uses the class instance variable names as keyword parameters in the
make-instance call. This implies that a change in the structure of a 
class requires a search through the software 
for the make-instance calls for this class.
One way of avoiding this is to use special ``factory objects'' (similar to 
those found in Objective-C \cite{cox:oop}).
For each application class, the interface has an associated ``factory class''
with one instance and one
method called ``make''.  This method contains the only make-instance
call for the application class.  The programmer can then 
change
the ``make'' methods should a change in the class-dictionary be 
necessary.


\section{The Weak and Strong Law of Demeter}

The Law of Demeter shares many characteristics with other man-made laws.
One such characteristic is that the Law is ambiguous and therefore open
to interpretation.  The source of the ambiguity is the rule which states
that messages may only be sent to 
objects which are instances of classes associated with 
instance variable types of the class to which
the method is attached.
When we use the term instance variables do we mean
the instance variables which make up the class exclusively, or are inherited
instance variables also allowed.  The question divides those who
follow the Law of Demeter into two fundamental groups.  The first group follows
the Weak Law of Demeter while the second group adheres to the Strong Law of
Demeter.  The two versions of the Law are defined as follows.
%\medskip
\begin{itemize}
\item
The Strong Law of Demeter:
The Strong Law of Demeter defines instance variables as being 
ONLY the instance variables which make up a given class.  Inherited instance
variable types may not be passed messages.
%\medskip
\item
The Weak Law of Demeter:
The Weak Law of Demeter defines instance variables as being BOTH
the instance variables which make up a given class AND any instance variables
inherited from other classes.
\end{itemize}
%\medskip

%In choosing which version of the Law to adhere to, a user should keep in
%mind that 
Each version carries certain implications.  When the Strong Law
of Demeter is adopted then it is guaranteed that any change to the underlying
data structure will only affect methods attached to the changed classes.  
All methods which are attached to unaltered classes will not require
modification.  This allows the user to easily detect code which may require 
updating due to changes in the class hierarchy.  Similarly, users which 
adopt the Weak Law of Demeter will gain certain advantages in program
maintenance.  However, these advantages are not as powerful as those gained
in adopting the Strong Law.  
In the event of a change to the
underlying data structure, the methods which may 
need modification
are those attached to the altered classes OR any class which is inherited 
by an altered class.
While the Strong Law appears to have a great advantage we will see that 
this advantage is not entirely free.
The code which is written under the Strong Law tends to have extra 
methods for a given solution.  This can render the code less readable in some
cases.  

The following example illustrates the issues 
% which surround the use of
%the Weak and Strong Laws of Demeter 
through a sample solution to the 
problem of weighing a basket of Fruit.  In this problem a basket of fruit 
is defined as a basket and a collection of various fruits.  Each 
fruit has an attribute called {\tt weight} which is assumed to be a number representing
the weight.  For simplicity we assume the basket doesn't have a weight.
The underlying data structure is shown in the following class dictionary.
%\medskip
\bv 
FruitBasket = Basket Fruits.
Fruits ~ { Fruit }. 
Fruit : Apple | Orange | Plum 
  *common* <weight> Number.
Basket = . Apple = . Orange = . Plum   = .
\end{verbatim}
%\medskip
It is important to note that the classes Apple, Orange, and Plum all inherit
from Fruit, and as a consequence also inherit
the instance variable {\tt weight}.  We assume that the weight for each piece of
fruit has been stored in this inherited instance variable (possibly by
some other method).  We now want to write a method which will compute the
prepared weight of a basket of fruit.  The prepared weight of a piece of
fruit is the weight of the fruit less the skin, core, and/or pit.  Each
fruit has a different formula for computing the prepared weight from
the gross weight.  In our example we will assume that the prepared weights of
apples, oranges and plums are 85, 80, and 65 percent of gross 
weight (respectively).
If we assume the weak interpretation of the 
Law then we get the following code.
%\medskip
\bv

(defmethod (FruitBasket :compute-weight) ()
   (send Fruits :compute-weight))

(defmethod (Fruits :compute-weight) ()
   (loop for each-fruit in child sum
      (send each-fruit :compute-weight)))

(defmethod (Apple :compute-weight) ()
   (* weight 0.85))

(defmethod (Orange :compute-weight) ()
   (* weight 0.80))

(defmethod (Plum :compute-weight) ()
   (* weight 0.65))
\end{verbatim}

%\medskip
It is useful to note the use of the inherited instance variable {\tt weight}
within the {\tt :compute-weight} methods attached to {\tt Apple}, 
{\tt Orange}, and {\tt Plum}.  This
is in violation of the strong interpretation of the Law.  The solution to this
problem which is within the strong interpretation of the Law of Demeter would 
be as follows.
%\medskip
\bv
(defmethod (FruitBasket :compute-weight) ()
   (send Fruits :compute-weight))

(defmethod (Fruits :compute-weight) ()
   (loop for each-fruit in child sum
      (send each-fruit :compute-weight)))

(defmethod (Apple :compute-weight) ()
   (send self :get-percent-weight 0.85))

(defmethod (Orange :compute-weight) ()
   (send self :get-percent-weight 0.80))

(defmethod (Plum :compute-weight) ()
   (send self :get-percent-weight 0.65))

(defmethod (Fruit :get-percent-weight) 
    (percent)
   (* weight percent))

\end{verbatim}
%\medskip

The latter solution requires one extra method called {\tt :get-percent-weight}
which is attached to {\tt Fruit}.  
This is to force the computation on the weight
instance variable into a method which is attached to the {\tt Fruit} class.  
This method is activated when either an {\tt Apple}, {\tt Orange}, or 
{\tt Plum} object
sends itself the {\tt :get-percent-weight} message since those classes do not
have this method name defined for them and they inherit from {\tt Fruit}.

The two programs defined above both seem to work equally well.
%as a solution
%to the proposed problem.  
The advantage of the latter program will show up
as we modify the underlying data structure.  Let us assume that we will
now expand our original problem.  Many years have passed since we wrote 
the code and now mankind no longer finds itself earth bound.  He has the
ability to take fruit baskets to any number of different planets around the
galaxy.  Clearly the weight of an object can no longer be a simple number
which represents the weight of the object on earth.  Our notion of weight
must include a calculation based on two factors, mass and gravity.  Our
underlying data structure will change to:
%the following.
%\medskip

\bv
FruitBasket = Basket Fruits.
Fruits ~ { Fruit }.
Fruit : Apple | Orange | Plum 
  *common* <weight> PlanetWeight.
PlanetWeight =  
  <mass>  Number <gravity> Number.
Basket = . Apple = . Orange = . Plum = .
\end{verbatim}
%\medskip
The only modified class in this class dictionary is {\tt Fruit}.  The Strong Law 
guarantees that only the methods attached to {\tt Fruit} 
will need modifications.
In this example we need only change the {\tt :get-percent-weight} method.
%\medskip
\bv
(defmethod (Fruit :get-percent-weight) 
    (percent)
  (send weight :get-percent-weight percent))

(defmethod (PlanetWeight :get-percent-weight) 
    (percent)
  (* (* mass gravity) percent))
\end{verbatim}
%\medskip
The set of methods written under the Weak Law require the modification of 
methods attached to {\tt Apple}, {\tt Orange}, and {\tt Plum}.  
In this simple example these
changes are not extensive, but consider problems with many alternatives (
e.g. 100 different fruits) or a more complicated class dictionary.

The Trellis/Owl system \cite{schaffert:trellis-86} provides the concept of 
subtype-visibility which
acts as a nice intermediate between the strong and weak interpretations
of the Law.  With the subtype-visibility concept they can fine-tune 
which operations (instance variables and methods) should follow 
the weak Law and which the strong Law.
C++ \cite{stroustrup:c++} can achieve the same with private and protected
data members.




\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? We outline an algorithm for transforming
any \oo\ program into an equivalent program which satisfies the Law.
In other words, we show that we can translate any \oo\ program
into a ``normal form'' which satisfies 
the weak
Law.\index{normal form for \oo\ programs}

We assume first that the only variables used in a method are instance variables
and arguments. We exclude local variables. The violation of the Law will happen in a nested method application.

\begin{verbatim}
(send ... (send 
    (send (send b :m1) :m2)
	:m3) ...)
\end{verbatim}

Here {\tt b} is an instance variable or an argument.
If {\tt b} is not {\tt self} we rewrite it as
\bv
(send b :n1) ...

(defmethod (B :n1) ()
  (send ... 
    (send (send (send self :m1) :m2) :m3) ...)
\end{verbatim}

Let the type of the object returned from method {\tt m1} be {\tt A1}. 
We can rewrite 
the above method application as
\bv
(send (send self :m1) :m2-new)

(defmethod (A1 :m2-new) ()
  (send ... (send (send self :m2) :m3) ...)
\end{verbatim}
The method {\tt m2-new} has a nesting level which is by 1 smaller than the
nesting level of the original nested method application.
By repeatedly applying the transformations given, we can transform
all the violations of the Law to the form

\bv
(send (send self :m1) :m2)
\end{verbatim}

This is a helpful reduction in the complexity of studying the removal of bad style.
Instead of having to consider all nested method applications,
we have to study only double nesting.
We distinguish between two cases.
\begin{itemize}
\item
{\tt m1} is an instance variable access method (i.e. it is an explicit
setting or retrieving of an instance variable value). The nested application
is in good style by definition.

\item
{\tt m1} is not an instance variable access method.
The violation is of the form:

\bv
(defmethod (C :M) ()
...
  (send (send self :m1) :m2)
...)
\end{verbatim}
We rewrite it in good style in the following form:
\bv
(defmethod (C :M) ()
...
  (send self :M1 (send self :m1))
...)

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

When we allow local variables in our methods, we can use a similar
transformation. 

%Consider
%\bv
%(defmethod (C :M) ()
%  K
%  (let ((auxiliary (send a :n1)) 
%  L))
%
%\end{verbatim}
%where K and L are program segments.
%
%We can rewrite the above as 
%\bv
%(defmethod (C :M1) ()
%  (send self :M2 (send a :n1)))
%
%(defmethod (C :M2) (arg :type Argtype)
%  K ; where we have to 
%    ; rename any occurrence of arg
%  L ; where we substitute arg for auxiliary
%)
%\end{verbatim}
%where {\tt Argtype} is the type of {\tt (send a :n1)}.
%
%A similar transformation can be applied when a local variable
%is updated.
%Consider
%\bv
%(defmethod (C :M) ()
%  (let ((auxiliary (send a :n1)))
%    L
%    (setq auxiliary (send b :n2))
%    (send c :n3)))
%\end{verbatim}
%We rewrite this as
%\bv
%(defmethod (C :M1) ()
%  (send self :M2 (send a :n1)))
%
%(defmethod (C :M2) (arg :type Argtype)
%  L ;where we substitute arg for auxiliary
%  (let ((auxiliary (send b :n2)))
%    (send c :n3)))
%\end{verbatim}

%The last method is transformed further, using the rules presented
%above. In all those transformations we have to watch out that a substitution
%or a new argument does not introduce a conflict with an existing name.
%
% \section{Conforming to the Law in Practice}

The transformations given above allow us to translate a given program
in bad style into good style.  There are two other, though less automatic, ways
to achieve this goal which may help in arriving at more
readable or intuitive code.  These two techniques, called Pushing and
Popping also may help in minimizing
the number of arguments passed to methods and 
occurrences of code duplication.
With lifting we lift a method up in the class hierarchy and with
pushing we push it further down.

%The following outlines two other transformation techniques.
%\begin{itemize}
%\item Lifting. We lift a method up in the class hierarchy.
%
%We need the following recursive definition:
%
%{\tt B} is a part-subtype of {\tt A}, 
%if {\tt B} is an instance variable type of {\tt A} or is a part-subtype of
%an instance variable type of {\tt A}\footnote{This expresses the 
%desired intuitive
%notion. A more correct definition requires more Demeter machinery than is
%appropriate here}. 
%% See \cite{karl:demeter} \cite{lieber-riel:oop}}.
%
%Consider the method:
%\bv
%(defmethod (C :M) ()
%  (send (send self :m1) :m2))
%\end{verbatim}
%
%Let {\tt T} be the type of the object returned from {\tt (send self :m1)}.
%We distinguish  three cases:
%\begin{enumerate}
%\item
%  {\tt T} is a part-subtype of {\tt C}.
%  \item
%  {\tt C} is a part-subtype of {\tt T}.
%  \item
%  {\tt T} and {\tt C} are not related.
%\end{enumerate}
%
%We can attempt the following transformations:
%\begin{itemize}
%\item Lifting.
%
%This is applicable if {\tt T} is a part-subtype of {\tt C}.
%The idea is to make {\tt m1} return an object of an
%instance variable or argument type of {\tt C} and
%adjust {\tt m2} accordingly.  So the method {\tt m2} is being lifted
%up in the class hierarchy from being attached to class {\tt T} to
%being attached to an instance variable type of {\tt 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
%; Grammar ~ {Rule}.
%; Rule = Body.
%;
%
%(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) :Body))
%
%(defmethod (Body :parse-details) ()
%   .........
%)
%
%\end{verbatim}
%
%The problem with the above is that {\tt look-up} returns an object of type
%{\tt Body} which is not an instance variable type of {\tt Grammar}.
%To transform the first method into good style, we make the {\tt look-up} method
%return an instance of {\tt Rule} and we adjust {\tt parse-details}.
%
%\bv
%; Grammar ~ {Rule}.
%; Rule = Body.
%;
%
%(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 :Body) ...
%)
%
%\end{verbatim}
%
%This lifting approach does not always work. Consider:
%\bv
%; Grammar = <ruleList> RuleList.
%; RuleList ~ {Rule}.
%; Rule = Body.
%;
%
%(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}
%
%Here we cannot transform the first method into good style by lifting
%the type of the {\tt 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 
%{\tt parse-details} message.  This task is really the responsibility
%of {\tt RuleList} who knows more about {\tt Rule} details than {\tt 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}
%\end{itemize}
%
%Methods which return a newly created instance 
%get a special treatment by the Law.
%The types of the returned objects are viewed as parameter types
%by the Law.
%Consider the following example:
%\bv
%;ConsNew = <carNew> L <cdrNew> List.
%(defmethod (ConsNew :count) ()
%  (send (send carNew :count) :add
%    (send cdrNew :count)))
%\end{verbatim}
%We assume that {\tt count} is a method which returns an object of
%type Number which has been created during the execution
%of {\tt count}. Therefore {\tt Number} is an argument type of this
%method and therefore it satisfies the Law.
%
%The basic types, such as Number, Ident, String are often hidden 
%argument types in the sense described above.
%
%In general any object returned from a method which is not related to 
%{\tt self} (i.e. in the sense of case 3 above) can
%be treated in this way.
%
%

The above proof demonstrates that any object-oriented program written in
bad style can be rewritten in a form which follows the Law of Demeter.
However, such programs may contain messages to inherited instance variables, 
therefore violating the constraints of the Strong Law of Demeter which insists
that only direct (non-inherited) instance variables be sent messages inside of
a method.  We present the following proof that any object-oriented program
written to obey the Weak Law of Demeter can be automatically rewritten to
obey the Strong Law of Demeter.  This proof together with the previous proof
guarantees that any object-oriented program written in poor style can be
rewritten to obey the Strong Law of Demeter.

The difference between programs which follow the Weak Law and the Strong Law
of Demeter is that those following the Weak Law may contain message sends
to inherited instance variables.  These may look like:

\begin{verbatim}
(defmethod (SubtypeClass :sample) ()
  (send price ':xyz))
\end{verbatim}

\noindent where price is an inherited instance variable from a class called 
``InheritedClass'' (from which SubtypeClass inherits).
All such message sends can be automatically rewritten such that the offending
message is sent to self and delegated to the inherited class as follows:

\begin{verbatim}
(defmethod (SubtypeClass :sample) ()
  (send self ':price-xyz))

(defmethod (InheritedClass :price-xyz) ()
  (send price ':xyz))
\end{verbatim}


\section{Compile Time Checking of the Law}

The Law of Demeter (the original version, not the object version)
can be checked at compile-time for useful subsets of object-oriented
languages. Checking the Law is closely related to static type checking.
When a language supports static type checking, we can enforce the Law.
It is not necessary that the user gives a type to all the
variables.
This checking requires only that the class dictionary for the
application be available at compile-time 
and that
all the arguments and
return values of methods are typed by the user.  

In not strongly typed languages there are several cases
which cannot be checked at compile-time.  

\begin{itemize}

\item
Class and/or Method Definitions at Run Time

This occurs in some languages such as Lisp/Flavors and CLOS.

\item
Passing a Message as an Argument

The following example demonstrates the passing of a method as an argument to
another method.  In the receiver method, the passed message is sent to an 
object ``o''.
\begin{verbatim}
(defmethod (X :xyz) (m)
  (send (send o m) ':m2)))
\end{verbatim}
If we don't know the argument types  and the result type of 
{\tt m} we cannot check the Law at compile-time.

\item
Dynamic Message Name Calculation

The following example demonstrates a case which cannot be tested at 
compile-time.
\begin{verbatim}
(send 
  (send o (concat ': some-string)) ':m)
\end{verbatim}
The string named ``some-string'' could be read in at run time in which case
there is no way of knowing the signature of the message sent to ``o''.  
\end{itemize}






\section{Minimum Documentation}
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, as a minimum,
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 and an indication whether the methods return
newly created  instances.
\item
the types of objects created by the method (directly or indirectly)
\end{itemize}

This documentation gives the reader of the method a list of types he or she
has to know about for understanding the method and for following the Law.

\input appendix.tex

\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 data 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.  
These trade-offs are clearly visible in the discussion
of the weak and strong versions of the Law.  The strong version implies
greater data and information hiding at the cost of extra methods and
method arguments.
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.

%The addition of type information to the arguments help show more explicitly
%the dependencies between classes which  are implied by the semantics of the
%application system.  This information together with appropriate documentation
%with the methods should make future updating of the software a less onerous
%task.

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 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 the proof above) 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 will be 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. 

We are looking for companies who are interested in benefitting from
Demeter technology. It is an easy ``add-on'' solution
which allows you to continue to work with your favorite \oos.
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 pointed
out the relationship between the Law and the Principle of Compositionality.
He was also 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. He provided the example we used to motivate
the object version.

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.

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