\section{Clients, suppliers and dependencies}

In this section we explain the Law of Demeter from
a new point of view 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 and we
outline the space of possibilities for formulating 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 the class to which the method is attached.
 
\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}


To formulate the Law we can choose from the following
independent possibilities. We refer the reader to \cite{LHLR:law-paper}
for more details.
\begin{itemize}
\item 
object/class: We can formulate the Law in terms of objects  or in terms 
of classes. The class formulation is intended to be compile-time
checkable. 
%The class formulation is subdivided into the ``pure classes''
%and the ``associated classes'' formulation. The ``pure classes'' formulation
%is easier to understand and does not require any Demeter terminology.
The ``object'' formulation is intended to be followed conceptually
and not to be enforced statically by a tool.

\item
messages/generic functions/methods: We can formulate the Law in terms
of message sending, generic function calls or methods.
The generic function call formulation distinguishes between two alternatives:
one method selection arguments and several method selection arguments.

\item
weak/strong: Depending on how we interpret the term ``instance variable''
we get two different formulations of the Law. If we interpret it as all instance variables, including the inherited ones, we get the weak form of the Law.
If we exclude the inherited instance variables, we get the strong form 
of the Law.
\end{itemize}

In this section we use the ``pure classes'' and ``message sending''
terminology for explaining both the weak and strong
Law of Demeter and its consequences.
We then explain the translation to C++, using some of the other
formulations.

The discussion in this section concentrates on a formulation of the
Law which can be enforced statically or
at ``compile-time''. This is useful for
statically typed languages with user-defined type declarations,
such as C++.
It is also useful for dynamically typed languages, such as Lisp/Flavors and 
Smalltalk, 
with the Demeter type system imposed on them.
In this case, the classes are defined by a class dictionary and
the signatures of methods are
   described by Demeter type notation.
   The type of every statement or expression can be inferred at compile-time
   through type inferencing. 

We adopt the following terminology from \cite{sakkinen:law-88}:
Given a style rule and a compile-time checking algorithm for checking
the rule, and
a suitable constant \(c\), 
we say that a program of size \(s\) is 
\begin{itemize}
\item
in good style, 
if the checking algorithm proves in time \(c s^2\)
that the program obeys the rule;
\item
in bad style, 
if the checking algorithm proves in time \(c s^2\)
that the program disobeys the rule;
\item
in questionable style otherwise.
\end{itemize}

The choice of a quadratic upper bound on the running time
of the style checker is arbitrary, but indicates that we
look for a formulation of the Law of Demeter which can be enforced 
efficiently.
The class version of the Law of Demeter can be enforced in
linear time for languages such as C++
and therefore it does not leave C++ programs in questionable
style. However the object version of the Law is difficult
to enforce statically due to aliasing complications and therefore
it leaves some programs in questionable style. Nevertheless,
the object version is useful as a conceptual formulation of the Law:
It is a goal to be approximated in programming.

To formally introduce the Law and its consequences, we need a few definitions.
Those definitions are for a pure object-oriented system, such as 
Smalltalk-80. Later when we translate the Law to other languages, such as C++,
we deal with the mixed paradigm wrinkles.

\subsection{Definitions}

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

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

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

\begin{example}
The protocol of class A consists of messages m1 and m2.
\bv
B = <x> Ident.
METHOD m1 (<self> B) Ident.
A = *inherit* B.
METHOD m2 (<self> A) Number.
\end{verbatim}
\end{example}

We use the following terminology: A (construction) class is defined
by a production of the form
\bv
A = B <x> C [D] E.
\end{verbatim}
This means that an object of class A has four parts:
an object of class B, called B, an object of class C, called x,
optionally an object of class D, called D and an object of class E.
For further details, see \cite{lieber-riel:oop}.

For method headings we also use the construction class notation. In the
above example, method m1 has one argument, called self, which
is of type B. The return type of m1 is class Ident.
To send a message, we use generic function call notation: e.g.,
f(s) is the same as ``send s the message f''.

We adapt the client/supplier terminology from \cite{meyer:book-88} to
our needs.

\begin{definition}
Method M is a client of class B and B is a supplier of method M,
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.

We use in the last definition 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
B = <x> Ident.
METHOD m1 (<self> B) Ident.
\end{verbatim}
If method m1 sends a message to x then m1 is a client of Ident.
\end{example}

Next we define potential preferred supplier classes of method M.
These classes are potentially suppliers of method M. A potential preferred
supplier class B of method M becomes a supplier and a preferred supplier
of M, if M chooses to 
send a message to B or one of its instances.

\begin{definition}
Class B is called a potential
preferred supplier of method M (attached to class C) if
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 class of objects created in M (directly or indirectly by
	calling a method which creates and returns a new object) or
\item
	  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. 

Next we define potential preferred client methods of class B.
These methods are potentially clients of B. A potential preferred
client method M of class B becomes a client and a preferred client of B,
if M sends a message to B or one of B's instances.

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

\begin{example}
In the following 5 examples,
class B is a potential
preferred supplier of method M and M is a potential
preferred client of B.

\bv
instance variable class:
// C = <s> B ...
METHOD M (<self> C ...)
  { ... f(s) ... }

argument class:
METHOD M (<self> C <s> B ...)
  { ... f(s) ... }

argument class:
METHOD M (<self> B ...)
  { ... f(self) ... }

newly created object class:
METHOD M (...)
  { ... f(new(B)) ... }  

// s is of type B, global to M
METHOD M (<self> A ...)
  { ... f(s) ... }
\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 both a supplier of M
and a potential preferred supplier of M.
\end{definition}

In the last example (all 5 subcases),
class B is not only a potential preferred supplier of
method M but also preferred supplier.

%We can prove the following facts:
We notice that
class B is a potential
preferred supplier of method M attached to B. 
%If M sends a message to
%a B-object then B becomes a preferred supplier of M.
Also, method M attached to class B is a potential preferred client of class B.

\subsection{The Law}

\begin{definition}
Law of Demeter (class version):
In all methods M use only the protocol of the potential preferred
supplier classes of M.
%In all classes C and in all methods M attached to C, use only the protocol of
%the potential preferred suppliers of M.
\end{definition}


Since the protocol of a class includes both the messages
to objects and to the class, the Law restricts the use of the
protocol of classes and metaclasses.
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.

%\begin{fact}
%Reformulation 1 of Law of Demeter (selective information hiding):
%For all classes B,
%only a potential preferred client method of class B is allowed 
%to use the protocol of class B.
%\end{fact}

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 (class version):
For all classes B,
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
potential 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}

\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 (class version):
Only a potential preferred client method M of class B is allowed 
to be dependent on class B.
\end{fact}

%If A is a client of B then A is not necessarily dependent on B since
%no method of A might use A's protocol. (An object of type A might
%be passed as second argument and never sent a message.)

%The Law reduces the dependency between classes since only a preferred
%client class of a class B is allowed to use the protocol of B.
%Using the dependency concept, we can give the following equivalent
%formulation of the Law:

%\begin{fact}
%Only a preferred client class of B is allowed to be dependent
%on B.
%\end{fact}

%Yet another definition:
%\begin{fact}
%In any method M attached to class C use only the protocol
%of classes of which C is a preferred client.
%\end{fact}

%The following formulation of the Law also shows the protocol restriction
%aspects.
%
%\begin{fact}
%The following statement is equivalent to the Law of Demeter:
%In any method M use only the protocol
%of potential preferred suppliers of M.
%\end{fact}

%The current definition of preferred client and supplier does not
%deal with associated classes.
%Refined definition:
%
%\begin{definition}
%A is a preferred client of class B if B sends a message to an instance 
%The preferred clients A of class B are the classes which
%send a message
%to an instance of the classes associated with the following classes:
%  instance variable classes of B or
%  argument classes of methods of B or
%  classes from which B inherits or
%  classes which create
%
%A inherits from B or
%	B creates an object of class A or
%	  B has a method which uses a global variable which is of class A.
%	    Every class is a preferred client and a 
%	    preferred supplier of itself.
%\end{definition}

To formulate a stronger version of the Law
of Demeter, we give here the Law in expanded form:

\begin{fact}
Law of Demeter (class version):
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
classes of objects created in M (directly or indirectly) or
\item
classes of global variables used in M.
\end{enumerate}
\end{fact}

\begin{definition}
Strong Law of Demeter (class version):
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}

\subsubsection{Conceptual guideline}
So far we discussed the class version of the Law of Demeter which can be
enforced at compile-time. 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 potential preferred supplier objects.

\begin{definition}
The potential preferred supplier objects of method M which is
attached to class C, are:
\begin{itemize}
\item
the immediate parts of C or
\item
the argument objects of M or
\item
the objects created in M (directly or indirectly) or
\item 
objects in global variables.
\end{itemize}
\end{definition}
Notice that we use the phrase ``immediate subparts of C'' whose
sensible interpretation is left to the user. E.g., 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): In all methods M send only messages to
potential preferred supplier objects of M.
\end{definition}

The object version of the Law expresses {\em what we really want}, but
unfortunately it is hard to enforce at compile-time \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 important benefits of the Law. We first give simple
benefits; the most significant one is the last one.

\begin{fact}
If the weak or strong Law of Demeter is followed and if
class A's protocol is renamed then at most the preferred client  methods of 
A and A's subclasses require modification.
\end{fact}

By the ``renaming'' of a protocol we mean the changing of some message
names.

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 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.

\subsection{Justification}

Having seen the benefits of the Law, we have to justify now the
4 clauses of the Law. Clearly, we still get the benefits described above,
if we delete all four clauses. But then we could no longer write
useful programs. We justify now each clause of the potential
preferred supplier definition. The goal is to convince the
reader that we need all 4 clauses for writing
useful programs:
\begin{itemize}
\item
instance variable classes: If we cannot use the protocol of instance variable
classes, we cannot delegate to subparts.
\item
argument classes: If we cannot use the protocol of argument classes,
the classes could not collaborate through arguments: arguments
could only be passed without ever be sent a message.  
\item
classes of objects created: Why do we need to send messages to newly
created objects? \cite{sakkinen:law-88} writes: ``including them
seems to run counter to the purposes of the Law, viz. to simplify
modifications and to simplify the complexity of programming''.
Consider a purely object-oriented language in which we can write
\((*(+ 2 ~~ 3) 4 )\). Here the addition of 2 and 3 returns a new
object, namely 5 to which we send the multiply message. Clearly,
we want not to exclude such expressions.

Another reason is that the transformation of an instance variable
access method
into a method which computes the value from other instance variables
should not affect the adherence to the Law.

\item
classes of global variables:
Some object-oriented languages, such as Eiffel\cite{meyer:book-88}, don't even have global
variables and for those this clause is not needed. In languages
which have global variables we allow messages being sent to
the objects for programming convenience. Certainly, the old
rule applies: global variables are considered harmful.
\end{itemize}

\subsection{Translation to C++}

C++ does not have messages, therefore we formulate the
Law in terms of methods which are called member functions in C++.
We also refine the Law to restrict access to data members.
C++ does not have metaclasses, but it has constructors and static
data members instead. Therefore we drop the use of metaclasses from the
C++ version of the Law.

%We make the assumption that all data members are private and that their
%values are accessible and settable through member functions. This
%is a good approach for large applications and simplifies the
%formulation of the Law for C++.
%Since in C++ not only member functions but also friend functions

\begin{definition}
In all member functions M of class C use only members (function and data)
of the following classes and their base classes:
\begin{itemize}
\item
C
\item
data member classes of C 
\item
argument classes of M
\item
classes of objects created in M 
(directly,
      by calling a constructor function or indirectly,
	    by calling a function which will call
		  a constructor function and return a new object)
\item
classes of global variables used in M.
\end{itemize}
\end{definition}

Using the potential preferred client classes terminology, we can abbreviate the
Law for C++:
\begin{definition}
In all member functions M use only members (function and data)
of the potential preferred supplier classes
and their base classes.
\end{definition}

We have to include the phrase
``their base classes'' since the formulation in terms
of the protocol implicitly involves inheritance.
Another reason for using ``their base classes'' is that C++ has the
:: scope resolution operator to call member functions which are hidden.
This allows to call a member function of a base class directly in the
code of a derived class, although the 
member function might have been redefined (overriden).

% In C++: use virtual functions if we want dynamic member function selection.
% Need virtual for alternations.
% A = *inherit* B. here we don't need virtual functions; still
% get inheritance.

C++ supports the friend function concept. A friend function of a class
has privileged access to the private data members in the same
way as a member function of the class. A function can be a friend of several
classes. Friend functions are provided for efficiency reasons.
We have decided not to include friend functions in the formulation of the
Law of C++. When friend functions are used and the composition
of a class B changes then  potentially all friend functions of B
need to be modified. Users of friend functions have to be aware
of the dependencies which they create.

C++ allows non-class types for
data members. We need to explain
how the Law applies to such classes. To represent objects of
variable size, it is necessary to use pointers. When a data member d is
of type B* d, where B is some class, we view B as a data member class
for the purpose of the Law. 
When a data member is a vector of pointers to D-objects, then D
is viewed as a data member class.
Similarly, when a data member is a vector of D-objects, then D
is viewed as a data member class.

C++ allows overloading of function names
with respect to all arguments.
But run-time dynamic member function
selection is done only with the object whose member function
is called (for virtual member functions).
Therefore we don't allow in the formulation of the Law
for C++ to call member functions of the
argument classes of a member function.

%In the Demeter system, we use non-class data members in a very restricted
%way. Either they are are of a built-in data type of C++ (e.g., int, char


Next we discuss the translation of benefits:
We have to assume that {\em data member names and calls to member functions
are not used outside of member functions, except in the main program (the function main())}. This assumption
is necessary for two reasons:
\begin{itemize}
\item
C++ is a mixed paradigm language. Therefore member functions
can be used in regular functions.

\item
C++ has friend functions which have privileged access to data members.
\end{itemize}

Under this assumption we can prove:

\begin{fact}
If the weak or 
strong Law of Demeter is followed and if the member functions
of class B change,
then at most the main program and the preferred client member functions of B
and its subclasses 
need to be modified and only member functions in the set of potential preferred
clients of B and B's subclasses need to be added.
\end{fact}

The preferred client member functions of class B are
member functions which use a member (function or data) of a B-object or
a constructor or destructor of B and which
\begin{itemize}
\item
are member functions of classes who have B or a pointer type to B (or an array of those types)
as a data member type or
\item
which are member functions which have B or a pointer type to B (or an array of those types)
as an argument type or
\item
which call a constructor of class B (directly or indirectly) or
\item
which use a global variable of type B or a pointer type to B (or an array of those types).
\end{itemize}

\subsubsection{Violations of the Law}

%In this subsection we don't assume that all data members are private.
Consider the following fragment of
a C++ program:
%see file viol.c
\bv
class MicroFicheFiles {
public:
  boolean search(Book* book) {}
};

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

class Archive {
public:
  MicroFicheFiles* m;
  Documents* d;     
  boolean search_good_style(Book* book) {
    return
      (m->search(book)) ? true :
	d->search(book);
  }
};

class ReferenceSec {
public:
  Archive* a;
  boolean search_bad_style(Book* book) {
    return
      (a->m->search(book)) ? true :
        a->d->search(book);
  }
  boolean search_good_style(Book* book) {
    return a->search_good_style(book);
  }
};

class Book {
};
\end{verbatim}  
Here member function {\tt search\_bad\_style(Book*)} violates the Law of Demeter
since it calls a member function of classes {\tt MicroFicheFiles} and 
{\tt Documents}
which are both not preferred supplier classes of member function
{\tt search\_bad\_style}.
The preferred supplier classes of 
{\tt search\_bad\_style} are: 
{\tt ReferenceSec} (the class for which the member function is defined),
{\tt Book} (from member function 
argument) and {\tt Archive} (data member).

Member functions {\tt search\_good\_style} for {\tt Archive} and
{\tt ReferenceSec} 
satisfy the Law of Demeter.

It is interesting to notice that the member hiding mechanism of C++
is capable of detecting this type of violation of the Law, if we make
the members {\tt m} and {\tt d} private. This, however does
not mean that the Law is superfluous: The Law promotes restricted use
of members which have to be public, while information hiding completely
disallows the use of private member names outside the member (and 
friend) functions
of a class.