Note by Karl Lieberherr.
This is a DRAFT report which contains interesting ideas about
LoD for AP and metrics.
The final version of this paper is probably on Brad Appleton's site.
One basic idea is that in the context of AP we can simplify the LoD
further because we no longer need to allow this.getX().getY().
Those metrics are useful in the context of a reenginering
project.
###########################################
The Law of Demeter for Propagation Patterns
by Bradford Appleton
Software Engineer, Motorola PNSB
December 5, 1995 ***DRAFT VERSION***
###########################################
Abstract
========
The Law of Demeter for Functions is analyzed and then reformulated for
Propagation Patterns. A metric is then proposed to evaluate the
structure-shyness of a propagation pattern and the appropriate use of
the metric is then discussed.
Keywords: Adaptive Object-Oriented Programming, Class Graph, Demeter,
Law of Demeter, Propagation Pattern, Structure-Shy Algorithms
1.0 Introduction
=================
One of the primary goals of adaptive object-oriented programming using
the Demeter method is to employ the use of structure-shy algorithms
which assume only a partial knowledge of a software system's class
structures and hierarchies. Using a "class graph" that is defined by
the inheritance and containment relationships between the classes in a
system, functional behavior and data structure are loosely coupled
through the use of constrained navigation specifications over the
graph. For each operation which represents a necessary or desired
behavior of the system, the operation is propagated to all classes that
participate in the traversal defined by the navigation specification.
These operations are called "propagation patterns" (PPs). If any class
in the traversal needs to do *more* than simply forward the operation
message request to its subparts and/or subclasses, code fragments
called "wrappers" may be used to specify any additional required
behavior on behalf of the operation. Each such wrapper will become part
of the implementation for a member function of one or more classes.
The use of constrained navigation specifications, taken by itself, is
*not* enough to ensure that a propagation pattern makes only minimal
assumptions about the structure of the class graph. It is also
necessary that the member functions of each class make as few
assumptions as possible about the class structure. This fact was
discovered early on in the course of Demeter research and was presented
as a design rule for object-oriented programs called the "Law of
Demeter".
2.0 The Law of Demeter
=======================
2.1 The Law of Demeter for Functions
-------------------------------------
The Law of Demeter (as it applies to class member functions) states
that:
A method (member function) "M" of a class "C" should invoke only
the methods of its arguments (including itself), its immediate
subparts, and of any objects that are created by the method "M".
The basic idea is to make as few assumptions as possible about the
structure of any classes that are not *directly* available to the
method so that only minimal modifications are needed when changes are
made to the structure of such classes. Rather than assume knowledge of
the availability of such indirectly accessible classes or of their
interface it is better to simply delegate the access and use of such an
object to the object itself. This provides much better encapsulation
and serves to better insulate the method from any changes to the
structure of such indirectly accessible objects. It also has the
drawback of creating a *lot* of class methods that do little more than
simply delegate the method's implementation to its subparts. Such
methods commonly contain only one or two lines of code.
Using the Demeter method and tools, most of these two line methods can
be generated automatically. The only code that needs to be written for
a propagation pattern is the code that implements the essential
behavior of the operation that is contributed from each essential
class. All code that merely propagates an operation from a class to
its subparts is automatically generated by the Demeter tools.
2.2 Adapting the Law of Demeter to Propagation Patterns
--------------------------------------------------------
Since the Demeter tools automatically generate most of the trivial
function calls for propagating an operation to its subparts, there
should be little or no need to invoke such methods a wrapper for the
method of the containing class. In other words, if I have a class "C"
that contains a subpart of class "D" named "d" which are both part of
the same traversal, then a propagation pattern such as the following:
*operation* void f()
*traverse*
*from* A
*to* Z
// Assume C = D. is part of the traversal
*wrapper* C
(@
this->get_d()->g();
@)
Can easily be re-written as:
*operation* void f()
*traverse*
*from* A
*to* Z
// Assume C = D. is part of the traversal
*wrapper* D
(@
this->g();
@)
and the re-written version makes fewer assumptions about the class structure.
Notice that the previous version did *not* violate the Law of Demeter
for Functions. We would like to strengthen the Law of Demeter for
functions when applying it to propagation patterns. Since almost all
accesses by a method to any of its subparts can be automatically
generated, it would seem that there should be no need for a wrapper for
a class method to access the methods of any of its subparts. Note
however that in the previous example, we did *not* need to modify the
traversal specification. This will not always be the case when we make
such a change. It may be that the traversal will need to be extended to
include class "D" as part of the traversal.
2.3 The Law of Demeter for Propagation Patterns
------------------------------------------------
Having just seen how to adapt the Law of Demeter for Functions to
propagation patterns, we can formulate a new "law" that serves as a
design guideline for writing propagation patterns:
A wrapper "W" which implements part of a method (member function)
"M" of a class "C" should invoke only the methods of its arguments
(including itself), and of any objects that are created by the
method "M".
This applies to all wrappers including wrappers for construction, repetition,
and alternation edges, as well as wrappers for vertices. However, since
the Demeter tools do not permit the programmer to add any member functions
to terminal classes, we need to make the following exception:
A wrapper "W" which implements part of a method "M" of a class "C"
may invoke any method of an immediate subpart that is an instance of
a Demeter tools' terminal class.
We call this new law the "Law of Demeter for Propagation Patterns" and
abbreviate as "LoD-PP". The Law of Demeter for Propagation Patterns is
a *stronger* statement than the Law of Demeter for Functions. This is
precisely because the Demeter method and tools allow us to program
adaptively and avoid the need to call most trivially implemented
functions (since the Demeter tools can automatically generate them for
us in a reproducible manner).
2.4 How to use LoD-PP
----------------------
The LoD-PP is a very *strong* recommendation! When an adaptive
programmer is writing code for a wrapper of a propagation pattern, the
programmer should use LoD-PP to help decide which code to include as
part of the wrapper and which code can be deferred to other classes
further down the traversal of the class graph. There may be some
situations however when it might be advisable to violate LoD-PP. If,
in order to conform to LoD-PP you are forced to modify a traversal
specification in such a way that it makes more assumptions about class
structure then the fragment of code which violated LoD-PP, it may be
suitable to leave the offending code fragment alone and let the LoD-PP
violation remain. Keep in mind however, that such situations are
*extremely* rare and can usually be solved by modifying the traversal
specification in some other manner, or by splitting the propagation
pattern up into two or more distinct but related operations. It would
be nice if we had some method to evaluate the number and "strength" of
structural assumptions made by a propagation pattern so that, when we
try to modify it to avoid a violation of LoD-PP, we can determine
whether or not the result makes fewer assumptions about the structure
of the class graph.
3.0 Measuring the Structural Dependency of a Propagation Pattern
=================================================================
Suppose that when writing a propagation pattern we find ourselves about
to violate LoD-PP. In order to avoid this, suppose that we end up
modifying the traversal such that it makes a great deal more
assumptions about class structure than did the original traversal. How
can we decide whether or not we are making fewer critical structural
assumptions by adding constraints to the traversal than by violating
LoD-PP in a single wrapper? If we had some way of measuring the number
and type of assumptions made in the two different versions of the
propagation pattern, then we could make an informed decision about
which version is more adaptable. To this end, we would like to come up
with a metric for measuring the dependency of a propagation pattern
upon the structure of a class graph used to customize it. We call such a
metric the "Structural Dependency of a Propagation Pattern" and
abbreviate it as "SD-PP".
3.1 Benefits of an SD-PP metric
--------------------------------
One of the primary benefits of an SD-PP metric is that it would help
adaptive programmers apply LoD-PP in a systematic manner in order to
increase the structure shyness of a propagation pattern. By measuring
SD-PP of two different versions of the same PP, the adaptive programmer
can determine which variation makes the fewest structural assumptions.
If the SD-PP metric could somehow take into account the size and/or
complexity of the class dictionary used to customize a PP, it could
also be used as a means of comparing different PPs in the same adaptive
program, or even in different adaptive programs. Keep in mind however
that the nature of some operations require them to make more structural
assumptions than other operations, so it would be dangerous to use
SD-PP as the sole measure of how "good" a propagation pattern is either
by itself or with respect to another PP. In fact, sometimes a a PP can
be made *more* adaptable by *adding* a traversal constraint so that the
PP works for a larger number of class dictionaries.
3.2 Formulating the SD-PP metric
---------------------------------
The first thing we want to do when devising the SD-PP metric is to determine
all the different kinds a structural assumptions that a PP can make about
a particular class dictionary graph (CDG). A PP makes a structural assumption
about a CDG every time that it does any of the following:
1. Refers to the name of a vertex in the CDG
2. Refers to the name of a label in the CDG
3. Refers to an edge in the CDG
4. Violates LoD-PP
Some structural assumptions may be stronger than others. For example, a
fully qualified construction edge assumes the existence of two vertices
and label as well as the type of relationship between the two vertices
(namely containment). By itself, the use of a single vertex or a single
label (without knowledge of its associated vertices) are roughly equivalent
in the *strength* of the structural knowledge they assume. We would like
to assign a weight to each type of structural assumption, and then associate
a cost with each structural assumption that can be made.
3.2.1 Vertices
~~~~~~~~~~~~~~~
Since we have to start somewhere, we will arbitrarily assign an
explicit reference to a vertex as having a weight of 1.0 and having a
cost equal to its weight. When a vertex is denoted using the wildcard
character '*', we do not consider this to be an explicit reference
and we assign it a cost of 0.
3.2.2 Labels
~~~~~~~~~~~~~
Since a label represents roughly the same amount of structural
knowledge as a vertex (it is some "name" in the class graph) we will
assign a label the same weight and cost as a vertex. When a label is
denoted using the wildcard character '*', we do not consider this to be
an explicit reference and we assign it a cost of 0.
3.2.3 Edges
~~~~~~~~~~~~
There are four different types of edges. Each fully qualified edge
assumes the knowledge of two vertices and zero or more labels. However
certain types of edges represent stronger structural assumptions than
others. Hence, each type of edge will have its own weight associated with it.
This will be the first factor of the cost of an edge.
The more vertices and labels that are referenced by an edge
specification, the more structural assumptions it makes. Furthermore, a
single edge that assumes knowledge of two vertices is a stronger
assumption than two edges that each assume knowledge of only a single
vertex. The former assumes knowledge of a direct relationship between
the two vertices where as the latter does not. When determining the
"cost" of an edge, we would like our metric to take this fact into
consideration. In order to do this, one factor of the cost of an edge
will be the square of the sum of the cost of each label and vertex
referenced by the edge. by taking advantage of the mathematical
inequality that the square of the sum is always greater than or equal
the sum of the squares, we can guarantee than a navigation constraint
such as:
*through* A,c,D
will be considered to make more structural assumptions than:
*through* A,c,*
*through* *,*,D
which is exactly what we want. So, the cost of an edge will be it
weight multiplied by the square of the sum of the number of vertices
and labels explicitly referenced by the edge specification.
3.2.3.1 Construction Edges
...........................
Construction edges are the one of the strongest structural assumptions
that can be made about a class graph. In fact, a violation of LoD-PP is
in a sense an assumption of a construction edge from the source class
to the subpart class as well as an assumption about the interface
and/or structure of the subpart. For this reason, we will assign all
construction edges a weight of 1.5.
3.2.3.2 Repetition Edges
.........................
At first, repetition edges would seem to be just as "bad" as
construction edges since both make assumptions about a containment
relationship between two classes. However, there is key a difference.
A repetition edge represents a homogeneous collection of objects (all
objects are of the same type). When we encapsulate a container object,
we do not employ information hiding to hide the knowledge that the
container contains objects of a given type, only to hide the
implementation used to represent the containment relationship and *how*
the elements in the collection are accessed. In general, one of the "secrets"
of a class is the data that it contains and how it is used. This is *not*
the case for a collection class: its secret is *not* *what* it contains,
but *how* it contains it.
For this reason, we do not consider a repetition edge to be as strong
an assumption as a construction edge. In fact, a repetition edge does
little more than assume the existence of some way of grouping together
its elements. Hence, we assign a repetition edge the same weight as a
vertex, namely 1.0.
3.2.3.3 Alternation and Inheritance Edges
..........................................
Alternation edges and inheritance edges or pretty much equivalent. Each
assumes the existence of a subclass relationship between two classes.
The only difference is in the implied direction of the subclass
relationship. Thus we will want them both to have the same weight. We
want inheritance to be regarded as a weaker assumption than
construction since we want to encourage the reuse of code through the
use common structure and/or common behavior. For this reason, we will
assign alternation and inheritance edges a weight of 1.25.
3.2.3 Violations of LoD-PP
~~~~~~~~~~~~~~~~~~~~~~~~~~~
Violations of LoD-PP are also very strong structural assumptions. As
was stated earlier, violating LoD-PP assumes knowledge of how to
traverse to a vertex and access one of its methods or data members.
This is similar to assuming the knowledge of a fully qualified
construction edge (source vertex, label, target vertex) plus knowledge
of the existence of the invoked method (which is similar to a label).
We will assign LoD-PP violations the same weight as construction edges
(namely 1.5) and we will determine the cost of an LoD-PP violation to
be its weight times the square of the sum of the total number of
vertices and labels whose existence is explicitly assumed by the
violation. We consider a member function call to be the equivalent of
a label in this situation.
As an example, suppose I have a class "A" that has a part "B" named
"b" which has a member function named "f". Then the following wrapper
would be a violation of LoD-PP:
*wrapper* A (@
this->get_b()->f();
@)
The above wrapper assumes the knowledge vertices "A" and "B" and of
the labels "b" and "f". Hence its cost would be:
1.5 * (1 + 1 + 1 + 1)^2 = 1.5 * (4^2) = 1.5 * 16 = 24.0
Note that programmatically detecting a violation of LoD-PP is much
harder then detecting the use of vertices or edges in traversal
constraints. It requires the ability to not only parse (possibly
incomplete) fragments of C++ code but the ability to semantically
analyze them as well.
3.3 The Proposed SD-PP Metric
------------------------------
Now that we have assigned a weight and cost to each kind of structural
assumption that a propagation pattern may contain, we define the SD-PP
metric as the sum of the costs of all such distinct assumptions. By
distinct, we mean that if the same edge or vertex specification appears
more than once, its cost is only computed and added to the result once only.
We do not penalize twice for making the exact same assumption. As an example,
suppose we have the following PP:
*operation* int f()
*traverse*
*from* A
*via* B
*through* ->B,c,D
*through* ->D,e,*
*through* =>F,G
*through* =>*,H
*through* ~>H,I
*through* ~>*,J
*to* X
*wrapper* ->B,c,D (@
++return_val;
@)
*wrapper* K (@
++return_val;
@)
*wrapper* X (@
return_val += this->get_y()->get_z()->func();
@)
Then the structural dependency of PP is written "SD(PP)" and is computed as
follows:
1. Collect all distinct vertex specifications that aren't part of an
edge specification. This gives us the set {A, B, K, X}. Note that
X appears twice (once as the target of a "*to*" clause and then as
part of a wrapper specification) but is counted only once.
2. Collect all distinct edge specifications. This gives us the set
{->B,c,D; ->D,e,*; =>F,G; =>*,H; ~>H,I; ~>*,J}. Note that the
edge ->B,c,D occurs twice but is counted only once.
3. Find all LoD-PP violations. In this case, the only one is in the
code fragment of the wrapper for the vertex "X".
4. Compute the sum of the cost of each vertex from the set we determined
in step 1:
cost(A) = 1.0
cost(B) = 1.0
cost(K) = 1.0
cost(X) = 1.0
+______________
TOTAL = 4.0
5. Compute the sum of the cost of each edge from the set we determined in
step 2:
cost(->B,c,D) = 1.5 * (1 + 1 + 1)^2 = 1.5 * 3^2 = 1.5 * 9 = 13.5
cost(->D,e,*) = 1.5 * (1 + 1 + 0)^2 = 1.5 * 2^2 = 1.5 * 4 = 6.0
cost(=>F,G) = 1.25 * (1 + 1)^2 = 1.25 * 2^2 = 1.25 * 4 = 5.0
cost(=>*,H) = 1.25 * (0 + 1)^2 = 1.25 * 1^2 = 1.25 * 1 = 1.25
cost(~>H,I) = 1.0 * (1 + 1)^2 = 1.0 * 2^2 = 1.0 * 4 = 4.0
cost(~>*,J) = 1.0 * (0 + 1)^2 = 1.0 * 1^2 = 1.0 * 1 = 1.0
+_____________________________________________________________________
TOTAL = 30.75
6. Compute the sum of the cost of each LoD-PP violation from the set we
determined in step 3:
cost(this->get_y()->get_z()->func()) =
1.5 * (1 + 1 + 1 + 1)^2 = 1.5 * 4^2 = 1.5 * 16 = 24.0
+______________
TOTAL = 24.0
7. Compute the sum of the totals from steps 4 through 6:
4.0
30.75
24.0
+______________
TOTAL = 58.75
The result of step 7 is the value of SD(PP).
3.4 Possible Variations
------------------------
There are a few subtle variations that we could try using when determining
SD-PP. Once would be to count duplicate edge and vertex specifications,
and another we be to attempt to normalize the SD-PP so that it could be
used to compare different propagation patterns from different programs.
3.4.1 Counting Duplicate Specifications
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
By counting duplicate edge or vertex specifications, we would in effect
be penalizing the user for every time a specific structural assumption
was made (regardless of how many times the same assumption was used).
While such a duplication doesn't really make any *extra* assumptions
about the structure of the class graph, it does in a sense make the PP
depend more strongly on that assumption than if it was referenced only
once. The effect of counting duplicate specifications would serve to
encourage the adaptive programmer to use "constants" to represent each
distinct vertex and edge specification which is probably a good thing.
It promotes the use of "components" which state up front the structural
dependencies of a group of PPs.
3.4.2 Normalizing SD-PP using Class Graph Size
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
As proposed, the SD-PP metric merely measures the number and strength
of structural assumptions that are made in a given PP. It does not take
into consideration the all of assumptions that it would have been
possible to make. Since propagation patterns from different programs
may need to make different assumptions or work with more complex
class dictionaries, if we want to be able to compare them against
one another, we need to use some kind of "normalization factor".
One possibility would be to divide the currently proposed SD-PP
for a propagation pattern by the size of the class graph that
is used to customize it. The metric for the "size" of a class
graph is already established in the Demeter method. We might call
the result of dividing the SD-PP by the class graph size the
"Normalized SD-PP with respect to a class graph".
It should be noted however, that a good propagation pattern should be
adaptable and be able to work with several different class graphs, so
it might not be useful to normalize SD-PP in this manner.
3.5 Using the SD-PP Metric
----------------------------
This author recommends using the SD-PP metric without normalization
with respect to a class graph. The primary use would be to compare
differing versions of the same propagation pattern in order to find the
one that makes only those structural assumptions that are both
necessary and sufficient to perform the desired behavior. We would like
to minimize the dependency of the PP upon the class structure as much
as possible, while bearing in mind that certain structural assumptions
may be necessary to make a PP adaptable enough for use with a larger
set of class graphs (even though the assumption may not be necessary
for a smaller set). When a violation of LoD-PP is detected, using the
SD-PP metric may be useful in helping determine whether or not the
violation is justifiable.
4.0 Conclusion
===============
When writing a wrapper for a propagation pattern, adaptive programmer's
should attempt to follow the Law of Demeter for Propagation Patterns.
More generally, the adaptive programmer should try to minimize the
number of structural dependencies of a propagation pattern upon any
particular class graph. To assist in this endeavor, the SD-PP metric
should be used to help the programmer decide which modifications to a
PP will cause it to be the most structure-shy.
As of this writing, the SD-PP metric has not yet been subjected to
regular use. It is this author's recommendation that it be implemented
and used in practice both with and without counting duplicate
specifications. The SD-PP usage results should then be analyzed to see
if the weights of each type of structural assumption should be adjusted
and to see if better results are obtained with or without counting
duplicate edge and vertex specifications.
References
==========
Karl J. Lieberherr, Northeastern University
Adaptive Object-Oriented Software: The Demeter Method with Propagation Patterns
PWS Publishing Company, 1996
Bibliography
============
Berard, Edward V.
Essays on Object-Oriented Software Engineering
Prentice-Hall, 1993
Coplien, James O and Schmidt, Douglas C., editors
Pattern Languages of Program Design
Addison-Wesley, 1995
Booch, Grady
Object-Oriented Analysis and Design with Applications (2nd edition)
Benjamin Cummings, 1994
Gamma, Erich, et al.
Design Patterns: Elements of Reusable Object-Oriented Software
Addison-Wesley, 1994
Henderson-Sellers, Brian and Edwards, Julian
BOOKTWO of Object-Oriented Knowledge: The Working Object
Prentice-Hall, 1994
Lieberherr, Karl J.
Adaptive Object-Oriented Software: The Demeter Method with Propagation Patterns
PWS Publishing Company, 1996
Martin, Robert C.
Designing Object-Oriented C++ Applications using the Booch Method
Prentice-Hall, 1995
Pree, Wolfgang
Design Patterns for Object-Oriented Software Development
Addison-Wesley, 1994
Rumbaugh, James, et al.
Object-Oriented Modeling and Design
Prentice-Hall, 1991
Walden, Kim and Nerson, Jean-Marc
Seamless Object-Oriented Software Architecture
Prentice-Hall, 1995
Wirfs-Brock, Rebecca, Wilkerson, Brian, and Wiener, Lauren
Designing Object-Oriented Software
Prentice-Hall, 1990