Hi Doug and Johan: what do you think about using strategies to describe what we called "interface class graphs" last summer? What do you think about the cyclic strategy below? You had some reservations about backward edges. How do you like the more general approach below? -- Karl ================================================= >From mira@ccs.neu.edu Sat Jun 27 22:55:10 1998 >Subject: Re: for our paper >To: lieber@ccs.neu.edu (Karl Lieberherr) >Date: Sat, 27 Jun 1998 22:54:30 -0400 (EDT) >Cc: mira@ccs.neu.edu >Hi Karl: > >in the following is my first response to your mail on generalized >strategies: > >> From lieber@ccs.neu.edu Sat Jun 27 15:06:51 1998 >> To: mira@ccs.neu.edu >> Subject: for our paper >> >> Hi Mira: >> >> This probably important for our paper. It treats backward edges >> in a uniform way as a side effect. > >> -- Karl >> ====================================== >> >> Generalized Strategies >> >> We generalize traversal strategies by writing them against >> an interface strategy and allowing backward edges >> in a general way. >> >> --- >> Strategy graphs as abstractions of class graphs >> >> So far we have used strategies in the role of >> traversal specifications. Next we are giving strategies a >> second role: abstractions of the class graph we can program against. >> >> This second role is useful for at least two reasons: >> >> 1. A strategy type is an interface to a class graph for an entire >> APPC. All strategies used inside the APPC should be substrategies >> of the interface. >> >> 2. We can use strategies to define the blueprint for >> "new" kinds of traversal specifications. For example, for the >> strategy type {A -> {B,C}} we want to define the traversal >> {B <- A -> C} with backward edge {B <- A}. The backward path >> is well-defined if every A-object can have only one B-object >> associated with it. >> >> Therefore, an APPC should have _one_ strategy type IST >> in its interface to the class structure and the strategies >> local to the APPC are written modulo IST. > >OK. Reading the email a second time and after our discussion over the >phone, I see why you use the term "generalized". > Your summary below is very clear. Expresses what I meant. >APPCs are slices of _generic_ adaptive programs that are defined in >terms of a "fictive" class graphs the interface to which is specified by a >strategy type. The strategy type is: > > 1- a formal parameter to the APPC > 2- is generally a tree, can be specified in a similar way as class graphs > and plays a similar role as class dictionaries played for adaptive > programs without APPCs. "generally a tree" Let's consider the Composite design pattern and let's express that by a strategy type: Composite : Simple | Compound. Simple = . Compound = (0..*) Composite. This strategy type represents the following class graphs: (choose a suitable renaming) Exp : Simple | Compound. Simple = Integer. Compound = Op List(Exp). Op : Mul | Add. Mul = . Add = . PatchworkExp : PrimitiveExp | TurnExp | SewExp *common* ["length" Measure] ["width" Measure]. PrimitiveExp = "primitive" Name. TurnExp = "(turn" PatchworkExp ")". SewExp = "(sew" PatchworkExp PatchworkExp ")". Measure = Integer. Name = Ident. List(S) ~ {S}. We will need to work out a precise definition of the family of class graphs defined by a strategy type. But in any case, the strategy type for the Composite pattern is cyclic. So here we have an example where we want cyclic strategies. Doug: is this similar to what you have been looking for? Using strategies to express structural design patterns is a nice new feature of strategies! Strategies become similar to class graphs with alternation edges. I propose the following syntax for combined strategy and class graphs: Strategy = LabeledGraph. LabeledGraph = List(Adjacency). Adjacency = [VertexLabel] Vertex List(Neighbor) ".". Neighbor : SubClass | LabeledVertex | OptLabeledVertex. SubClass = "|" Vertex. LabeledVertex = [EdgeLabel] Vertex. OptLabeledVertex = "[" LabeledVertex "]". EdgeLabel = "<" LabelName ">". VertexLabel = ":" VariableName. // in strategy graphs: for participants // Terminal Buffer Rule ComponentName = Ident. Vertex = Ident. VariableName = Ident. LabelName = Ident. // parameterized List(S) ~ {S}. // for using sem-check of Demeter/C++ // Ident=DemIdent. > >Within the APPC we use traversal strategies written wrt the interface >strategy type in a similar way as traversal strategies are written now >wrt a concrete cd. That's why you write >"Strategy graphs as abstractions of class graphs". > >Could be that I have repeated what you have written using other words. >Just wanted to write down my understanding. Even better if it is the same >in other words - that would mean, we talk about the same. I like your summary a lot. > >> Let's apply the idea of an interface strategy type to >> backward strategy-graph edges. >> >> It is useful to have backward strategy graph edges to avoid >> lengthy back transportation and searching code. >> While ordinary strategy graphs only express object traversal, >> strategy graphs with backward edges also express object searching. >> The backward edges are expressed modulo an interface strategy type. >> >> Definition of a backward edges: >> >> Given a strategy type IST, a generalized strategy graph wrt IST >> is a substrategy SG of IST with additional backward edges. >> For a backward edge X<-Y to be legal there must be a path >> in IST from Source(SG) to Y and for each such Y there is >> exactly one X reachable. >> >> The backward edge may have a constraint map associated >> with it which restricts the paths from Y to X >> to a unique path. >> >> The object searching consists of traversing from Source(SG) to Y >> and building a hashtable which associates the uniquely >> reachable X with Y. This hashtable allows us to retrieve >> the corresponding Y when we are at an X, effectively replacing >> a search operation. >> >> >> Source(SG)------> .Y. >> ^ >> | >> | >> X > >I like your definitions. Do you see any problems with efficiently checking >"there must be a path in IST from Source(SG) to Y and >for each such Y there is exactly one X reachable" ? This can be checked efficiently. We check whether PathSet[IST]("Source(SG) -> Y") is non-empty and we check whether PathSet[classgraph]("N(Y) -> N(X)") contains exactly one path. PathSet is computed with the traversal graph. > > >> Let's consider our earlier example: >> >> IST: >> Graph -> Adjacency -> Neighbors -> Vertex >> -> Vertex through -> *,source,* >> >> >> generalized SG: >> Graph -> Neighbors -> Vertex <- Adjacency >> | >> | >> constraint: through ->*,source,* >> >> Source(SG) X Y >> Graph -> Neighbors -> Vertex <- Adjacency >> | >> | >> constraint: through ->*,source,* >> >> When we are at Vertex-object, the corresponding Adjacency-object >> will be retrieved automatically. > >I'm a bit confused by the notation here, but I guess, I know what you >mean. Is the following correct? > >IST: >Graph -> Adjacency -> Vertex through neighbors > -> Vertex through *,source,* > >generalized SG: >Graph -> Vertex through neighbors <- Adjacency > | > | > constraint: through *,source,* Yes, mine was wrong; your is correct. IST needs to represent the structure of the class graph. Mine does not. > >Source(SG) X Y >Graph -> Vertex through neighbors <- Adjacency > | > | > constraint: through *,source,* > > > >> Another example in the context of APPCs (see OOPSLA '98 paper): >> >> IST: >> {LineItemParty -> {PricerParty, ItemParty}} >> >> SG: >> {PricerParty <- LineItemParty -> ItemParty} >> >> Here we assume that a LineItemParty-object has exactly one >> PricerParty object associated with it. >> The association between objects is assumed to be static >> and is computed once at the beginning. >> > >By "beginning" you mean when an instance of the root of IST (in this case >an lineitemparty) is provided, right? Yes. And the APPC is active at that point. > >> The concept of an interface strategy graph with >> generalized strategies conforming to the interface >> can be extended to static and dynamic participant definitions. >> >> {pricer:PricerParty <- lineItem:LineItemParty -> item:ItemParty} >> >> allows us to use pricer in ItemParty or item in PricerParty. >> >> See: http://www.ccs.neu.edu/research/demeter/biblio/components > > >VERDICT: > >we must definitively include that stuff in the OOPSLA paper, but >should choose a way to do so that is intuitive and easy to understand so >that the reader does not get distracted from the main message. We should >elaborate that in a more "formal" way in a journal version of the OOPSLA >paper. > Fully agreed. > >I think the whole idea is getting a more clear and consistent shape >everyday, and feel very excited about that :-) > I am also very excited about the progress we are making.