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