Transcript Document

AP/DJ
• AP: a generic technology
• DJ: a low-learning-curve implementation of
AP
Law of Demeter Principle
• Each unit should only have limited
knowledge about other units: only about
units “closely” related to the current unit.
• “Each unit should only talk to its friends.”
“Don’t talk to strangers.”
• Main Motivation: Control information
overload. We can only keep a limited set of
items in short-term memory.
Law of Demeter
FRIENDS
Application to OO
• Unit = method
– closely related =
• methods of class of this/self and other
argument classes
• methods of immediate part classes (classes that are
return types of methods of class of this/self)
• In the following we talk about this
application of the Law of Demeter Principle
to OO
Rumbaugh and the Law of
Demeter
Quote: Avoid traversing multiple links or
methods. A method should have limited
knowledge of an object model. A method
must be able to traverse links to obtain its
neighbors and must be able to call
operations on them, but it should not
traverse a second link from the neighbor to
a third class.
Law of Demeter
(alternative formulation)
A method should have limited knowledge
of an object model.
AP is a reaction to this view of the Law of
Demeter
Agreement that LoD Good Idea
• How to follow LoD: good solutions exist
but not widely known. Two approaches to
following LoD:
– OO approach
– Adaptive approaches
• DJ
• APPC
• Demeter/Java
What if your friends are far
away?
• You pay them to travel to you or you send
an agent to them to collect the information
you need.
– Approximate Directions: You give them or your
agent directions about what kind of information
to collect but you don’t care about accidental
details of the travel.
– Detailed Directions: You give them or your
agent detailed travel directions.
Adaptive Following LoD
A
C
FRIENDS
a
S
X
b
a:From S to A
b:From S to B
c:From S via X to C
c
Traversal specifications create
friends
• Class ClassGraph is an intermediate class
between classes that need to communicate
ClassGraph.fetch(Object o, TravSpec s)
Adaptive Following of LoD:
Key Idea
DJ
• An implementation of AP using only the DJ
library and the Java Generic Library (JGL)
• All programs written in pure Java
• Intended as prototyping tool: makes heavy
use of introspection in Java
• Integrates Generic Programming (a la STL)
and Adaptive programming
Integration of Generic and
Adaptive Programming
• A traversal specification turns an object
graph into a container.
• Can invoke 50+ generic algorithms on those
containers. Examples: add, delete, find, etc.
• What is gained: genericity not only with
respect to data structure implementations
but also with respect to class graph
Algorithm Classes
Applying
Comparing
Copying
Counting
Filling
Filtering
Finding
Applies a function to every
element of a sequence
Mismatches, performs equality
tests, performs lexicographical comparisons
Copies a sequence
Counts unconditionally and conditionally
Fills a sequence with a single element
Filters a sequence
Finds an object or an element
that satisfies a predicate
Algorithm Classes
Hashing
Contains generic hashing algorithms
Heap
Makes, pushes, pops, and sorts a heap
MinMax
Finds the min and max of a sequence
OrderSetOperations
Contains Generic set operation algorithms
Permuting
Cycles through permutations of a sequence
Printing
Prints sequences and containers
Removing
Removes an object or element that satisfies a predicate
Algorithm Classes
Replacing
Reversing
Rotating
SetOperations
Shuffling
Sorting
Swapping
Transforming
Replaces an object or element that satisfies a predicate
Reverses a sequence
Rotates a sequence
Union, intersection, difference, and inclusion
Shuffles a sequence
Sorts a sequence
Swaps elements or sequences
Maps one sequence to another
Collections
JGL includes 11 highly optimized data structures that
satisfy most programmer needs. These data structures
have been engineered for performance and ease of use,
and their performance either meets or beats every
other commercially available Java container library. In
addition, all JGL containers work correctly in
multithreaded situations.
Collection Interface
add(Object) Add an object to myself.
clear()
Remove all of my objects.
clone()
Return a shallow copy of myself.
elements() Return an Enumeration of the components in this container
equals(Object)
Return true if I'm equal to a specified object.
finish()
Return an iterator positioned immediately after my last item.
Collection Interface
isEmpty() Return true if I contain no objects.
maxSize() Return the maximum number of objects that I can contain.
remove(Enumeration)
Remove the element at a particular position.
remove(Enumeration, Enumeration)
Remove the elements in the specified range.
size()
Return the number of objects that I contain.
start()
Return an iterator positioned at my first item.
toString() Return a string that describes me.
com.objectspace.jgl.algorithms.
Filtering
reject(Container, UnaryPredicate)
Reject elements in a container.
reject(InputIterator, InputIterator, UnaryPredicate)
Reject elements in a range.
select(Container, UnaryPredicate)
Select elements in a container.
select(InputIterator, InputIterator, UnaryPredicate)
Select elements in a range.
…
com.objectspace.jgl.algorithms.
Permuting
nextPermutation(BidirectionalIterator, BidirectionalIterator,
BinaryPredicate)
Arrange a sequence to become its next permutation.
nextPermutation(Container, BinaryPredicate)
Arrange a container to become its next permutation.
prevPermutation(BidirectionalIterator, BidirectionalIterator,
BinaryPredicate)
Arrange a sequence to become its previous permutation.
prevPermutation(Container, BinaryPredicate)
Arrange a container to become its previous permutation.
com.objectspace.jgl.algorithms.
Transforming
collect(Container, UnaryFunction) Return a container that is the same
class as the original and contains the result of applying the given
unary function to each element in the original.
transform(Container, Container, Container, BinaryFunction)
Traverse two containers and add the results of invoking a
BinaryFunction on corresponding elements to another container.
Sample DJ code
// Find the user with the specified uid
Container libUsers = new
Container(library,
"from Library to User");
User user = libUsers.find("uid", uid);
Check???
Methods provided by DJ
• On all objects: traverse, fetch,
gather
• On containers: Java Generic Library
algorithms (in progress)
• traverse is the important method; fetch and
gather are special cases
Traverse method: excellent
support for Visitor Pattern
// class ClassGraph
Object traverse(Object o,
Strategy s, Visitor v);
traverse navigates through Object o following
traversal specification s and executing the
before and after methods in visitor v
ClassGraph is computed using introspection
Guidelines
IF you plan to use
1 sg with 1 o and several v
1 sg with several (o or v)
1 o with several (sg or v)
1 tg with 1 o and several v
1 sg with 1 (o and v)
cg
s
tg
o
og
ogs
v
THEN
THEN
THEN
THEN
THEN
freeze(cg,sg,o)->ogs
freeze(cg,sg)->tg
freeze(cg,o)->og
freeze(tg,o)->ogs
inline
class graph
strategy
traversal graph
object
Abreviations
object graph
object graph slice
visitor or generic algorithm
DJ binaryconstruction operations
cg
s
tg
o
og
ogs
cg
*
s
tg
tg,cg *
*
*
*
o
og
*
*
*
og
*
ogs
ogs
*
*
ogs
*
*
*
*
*
*
Who has traverse, fetch, gather?
(number of arguments of traverse)
cg
s
tg
o
og
ogs
cg(3) s
tg(2) o
*
tg,cg *
og
*
*
*
*
*
*
og(2)
*
ogs
ogs
*
*
ogs(1)
*
*
*
*
*
*
Methods returning an
ObjectGraphSlice
•
•
•
•
•
ClassGraph.slice(Object, Strategy)
ObjectGraph.slice(Strategy)
TraversalGraph.slice(Object)
ObjectGraphSlice(ObjectGraph,Strategy)
ObjectGraphSlice(ObjectGraph,TraversalGraph)
Blue: constructors
Traverse method arguments
• ClassGraph
– Object, Strategy, Visitor
• TraversalGraph
– Object, Visitor
• ObjectGraph
– Strategy, Visitor
• ObjectGraphSlice
– Visitor
Traverse method arguments.
Where is collection framework
used?
• ClassGraph
– Object, Strategy, Visitor
• TraversalGraph
– Object, Visitor / asList(Object)
• ObjectGraph
– Strategy, Visitor / asList(Strategy)
• ObjectGraphSlice
– Visitor / asList()
Where is collection framework
used?
DJ unary construction operations
• Class graph from TraversalGraph
• Class graph from all classes in package
Lack of parameterized classes in
Java makes DJ harder to use
• Consider the traversal: from A to B
• Let’s assume that in the class graph between
A and B there is a Java collection class. The
intent is: A = List(B) which we cannot
express in Java. Instead we have: A =
Vector(Object). Object : A | B. Let’s assume
we also have a class X=B.
Lack of parameterized classes in
Java makes DJ harder to use
• We have: A = Vector(Object). Object : A | B
| X. X = B.
• If the vector contains an X object it will be
traversed!!! Vector
*
A
X
B
Object
No X-object is allowed
to be in vector
A
*
X
B
Vector
*
A
X
B
Object
Moral of the story
• If the Collection objects contain only the
objects advertised in the nice class graph of
the application the traversal done by DJ will
be correct.
• However, if the Collection objects contain
additional objects (like an X-object) they
might be traversed accidentally.
Size of traversal graph
• DJ might create big traversal graphs when
collection classes are involved. DJ will plan
for all possibilities even though only a small
subset will be realized during execution.
• To reduce the size of the traversal graph,
you need to use bypassing. In the example:
from A bypassing {A,X} to B.
More info
• DJ Home Page