See: /proj/adaptive/www/design-decisions/higher-level-constructs/components collection-on-modules for earlier discussion (summer 1997). See: /proj/adaptive/www/design-decisions/traversal-strategies/graph-theory general-pathset.txt for formal definition of conformance. Hi Johan: >From johan@ccs.neu.edu Thu Jul 2 01:42:23 1998 >To: Karl Lieberherr >cc: dougo@ccs.neu.edu, jayantha@ccs.neu.edu, johan@ccs.neu.edu, > mira@ccs.neu.edu, mel@ece.neu.edu, wand@ccs.neu.edu >Subject: Re: checking adaptive programs >From: Johan Ovlinger > >As promised, here is my take on interface class graphs. This relates >to the discussion on substrategies by solving the same goal in a clean >and self contained way. The application to APPCs is incidental. Good. We keep our theory as general as possible so that we can apply it to many other problems than APPCs. At the same time we completely focus on APPCs and their needs. Our plan is to implement APPCs in Demeter/Java. Johan: you provide a good description which goes beyond the formal conformance concept in http://www.ccs.neu.edu/research/demeter/design-decisions/traversal-strategies/graph-theory/general.txt ===== Conformance of graphs Instance: Node-labeled graphs G1 = (V1,E1), G2 = (V2,E2) with source s and target t. p in P[G2](s,t) there exists a path p' in P[G1](N(s),N(t)) such that p' is an expansion of p. Applications: does a class graph conform to a strategy graph? does a class graph conform to an interface class graph? ====== Please can you mention the connection between what you wrote and the conformance defined above. > >I gave basically this explanation in the seminar, so for those of you >who were there, this will flesh out the explanation I gave then. For >those who weren't, I'll try to give a bit of background. Mitch, this >is where my time has gone... > >\section{Intro} > >The problem with programming with OO components is that they all make >assumtions about the shape of the class graph they will be working >on/in. Even demter programs make such assumtions, typically in a more >robust manner than normal OO programs, but assumtions all the >same. Traversals are defined in the assumtion that one class is >reachable from another, and that another always comes before a >third. What we need to do is to define an interface for the class >graph and then program to that interface. I was mumbling about this >last summer, and even worked out a generalish system with mitch that >used parametric polymorphism to perform what is referred to as the >Name Map. Now we need this capabliity for APPCs, so the time has come >to work out a small scale, simplified version, of that system. Excellent description of your task. >This is pretty much version 0.00001 level thinking. > >\section{What APPCs need} > >As already hinted, APPCs need to make assumptions about the form of >the class graph that they will be used with. This leads to the >intuitive defintion of {\em conformance}. An APPC defines an interface >class graph that it assumes will exist. This Interface CG needs to be >mapped to a Concrete CG. We say that the ICG conforms to the CCG if >this is mapping exists (subject to some currently under-debate >constraints). > >Thus, the question is; when {\em does} an ICG conform to a CCG? Some >of our previous suggestions have used PathSets or the Subgraph >Homeomorphism algoritm, but my suggestion is quite a bit simpler than that. >To cut to the chase, I claim an ICG trivially conforms to a CCG if the >default mapping mechanism (explained after I explain what a {\em >mapping mechanism} does) produces traversals that are all non-empty. > >If you are not happy with this, or wish to shoe-horn an ICG into a >CCG, a manual mapping mechanism will be provided. Yes this manual option will be needed because some of the local strategies of an APPC will have uniqueness assumptions which will show up in the ICG. But the CCG might be very dense and then we have to manually say how to get uniqueness. This corresponds to replacing abstract strategies by concrete strategies when a CCG is given. > >So, the conformance property becomes something like "IFG conforms to >CCG if it either automatically or with human help can be made to >conform." Circular, I know. Anyone have a better formulation (can >hardly get worse) I think we should focus on automatic conformance which is a conformance which must always hold. We can do manually-influenced conformance only if automatic conformance holds. I propose, along with Doug, I think, conformance of graphs as conformance whcih must always hold (same as above): Instance: Node-labeled graphs G1 = (V1,E1), G2 = (V2,E2) with source s and target t. p in P[G2](s,t) there exists a path p' in P[G1](N(s),N(t)) such that p' is an expansion of p. > >\section{The Mapping Mechanism} > >As we have stated so many times already, an ICG needs to be mapped to >a CCG. In general, this is performed by mapping class names in the ICG >to class names in the CCG (this is what I had planned to use >parametric polymorphism for) and by replacing each edge in the ICG >with a strategy over the CCG In a first step we replace edge X->Y by strategy X->Y. Later manual intervention may be needed to replace the strategy by something more complex. > \footnote{ > We have to think about the cardinality here. If A->B is an edge of > card 1 in the ICF, then can this be mapped to a strategy that has > several B's in it? This is one of the points that were debated in the > seminar. > }. We have to work on a constraint language. Boaz and I and Gary from Mitre have started on this. See: http://www.ccs.neu.edu/research/demeter/pub-impls/traversal-graph/constraint-check > >So each edge in the ICG becomes a s.c. {\em derived part} that >performs the mapping to the CCG, each time it is used \footnote{We >might want to perform some caching here, and insert hooks into all the >set_ methods to flush appropriate caches when they are called.} More >general approaches, a la functors are imaginable, but this I think >will do nicely for us. Exactly how each edge is mapped is left >unspecified, but not for long... > >\section{The Default Mapping} > >So we have a name map from the names used in the APPCs ICG and the >class names in the CCG. What is the default mapping? Simply, for every >edge A->B in the IFG, and assuming a name map N, make N(A) have a >derived part, suitably name mangled that performs a long-get of >"from N(A) to-stop N(B)". If all such long-gets have non-empty paths, >then the default mapping has worked. I see! we agree. But please make the connection to Doug's conformance definition very explicit. > >\section{What about traversals and such} > >The APPC mentions the classes of the ICG many times, not least of all >to define some strategies that create a s.c. Multi Object (ie, it has >traverals that collect parts from different objects and presents them >to the programmer as if they were local). These strategies are defined >over the ICG, so when they traverse an edge, the appropriate >long-getter is invoked and they arrive at the destination. Imagine the >CCG > > A -> B -> C -> B > >and the ICG > > A ------> C -> B > >(and the identity name map). Then a wrapper on a B will only be called >once traversing the ICG. Notice how I drew the first arrow of the ICG >longer than the rset. This is to signal tha the first B is hidden by >the mapping and thus will NEVER be seen by the APPC. > >\section{ Problems yet to be solved} > >Parsing - we need to parse a structure that is entirely derived parts >Separate compilation - > What needs to be fixed in order to be able to compile an APPC > completely serparately from the class graph? > What about slightly separately (changing the APPC will NOT require > recompiling the CCG) > Where to put generated code - > Where to put the explicit APPC code - > since we wish to maintain complete separation from the CCG, we > and also for reasons of separate compilation, we want to put > our traversal code somewhere other than in the CCG. > >I hope this has clarified some of what I meant. Info, you know where >to come for more info. > >Johan > One more thing: you need to clearly work out the connection to our former substrategy definition. See my list of conjectures. Besides polishing our global view of things, as you have done with this message, we need also develop the underlying theory and prove theorems. -- Karl