Hi Shriram: Thank you for your message about doing the otherwise clause in Java. Let me comment on one paragraph that Mitch wrote: >As far as I am concerned, this is the $64 question. Johan and I got >about this far and came to the conclusion that in the examples where >one needed to combine values, an "otherwise" clause would rarely be >useful. This is an empirical question, of course, and I have asked >Karl many times to think about getting some quantitative data on this >kind of issue. I think that Mitch underestimates the noise that can exist in class graphs modulo a given behavior. At all those noise classes an otherwise clause would do the job. (Remember the bus simulation example where we find all people waiting at some bus stop.) I don't have any hard data but here is one family of situations where an otherwise clause is very useful: Take APPCs where the behavior is written without strategies, for example using Java (e.g., with a traversal automata style). Strategies are only used in the connectors that map the abstract class graphs to concrete class graphs without talking about the details of the concrete class graphs. In this case the otherwise clause will be very useful: concatenate the results of all the subtrees and pass back the result. I agree with Mitch and Johan that separating traversal code from visitor code is even useful when you explicitly write the traversal code. The HP project: http://www.ccs.neu.edu/research/demeter/evaluation/conventional-env/hp.html shows that traversal/visitor style programming is useful. -- Karl >From wand@ccs.neu.edu Mon Mar 15 13:08:51 1999 >From: "Mitchell Wand" >To: shriram@cs.rice.edu, lieber@ccs.neu.edu, johan@ccs.neu.edu >Subject: Adaptive Programming and functional combination >Cc: dougo@ccs.neu.edu, lieber@ccs.neu.edu, lorenz@ccs.neu.edu, > matthias@cs.rice.edu, mira@informatik.uni-siegen.de > >Dear Shriram, > >I've been following the correspondence between you & Karl and now I've >finally gotten a few minutes to post some reactions. > >I'm going to recap your solution in the terms that I like to think in; >I assume that you know most of what I'm about to say. > >You wrote: > > SK> Overall Solution: > > SK> * Retain strategies as unchanged as possible. We want to > SK> reuse the knowledge about compiling traversals, but change the > SK> behavior of what happens at each node during the traversal. > SK> That is, we want to modify the visitors. > > SK> * The specification must include code corresponding to *each > SK> kind of node* the computation may encounter on the the > SK> traversal. (More on this below.) > > SK> * Each traversal has a "type". The type is a pair, consisting of the > SK> "downward" and "upward" types. > > SK> The code that corresponds to a node has the form > > SK> \ . ... . [where \ = lambda] > > SK> = var(s) of type "downward type" > SK> ... = specified below > SK> = any old code, return type "upward type" > >This is sort of the obvious thing to do-- it corresponds to giving a >denotational semantics for the object (as a tree), by giving a >semantics for each kind of node. The meaning of a tree is a function >from the downward type to the upward type. (In attribute grammar >lingo, the downward type is the inherited attribute, the upward type >is the synthesized attribute). > >The semantics of a node is a function that takes the meaning of the >subtrees and produces the meaning of the whole tree; typically what >happens is that the meaning of a subtree is invoked on some suitably >modified value of the inherited attribute. > >(define meaning-of-node1 > (lambda (meaning-of-subtree1 meaning-of-subtree2 ...) > (lambda (the-inherited-attribute) > (blah-blah-blah > (meaning-of-subtree1 the-inherited-attribute) > (meaning-of-subtree2 (+ 1 the-inherited-attribute)))))) > >I notice that your version switches the order of these arguments-- I >think (though I'm not sure) that the order above leads to a neater >formulation. > > SK> Where do these "child" arguments come from? That's what the traversal > SK> strategy compiler gives us. It analyzes the class graph to figure out > SK> which paths to take and, at a given node, which children to > SK> *potentially* visit. Now it turns these traversals into something > SK> that the visitor at that node has control over. > >Yes, a traversal strategy is essentially a guy who stitches the >meanings of the nodes into a meaning for the whole tree. In the >default case, when every node is visited, this is the fold of the >tree, or the Church encoding. For example the Church numeral for 3 >takes two arguments: the meaning of successor and the meaning of >zero, and returns the meaning of two: > >(define meaning-of-two > (lambda (meaning-of-successor) > (lambda (meaning-of-zero) > (meaning-of-successor (meaning-of-successor meaning-of-zero))))) > >Note that in this formulation one needn't worry about the inherited >attributes-- that's the advantage of the order of arguments I used >above. > >One could easily imagine traversals that assembled these meanings in >other ways, eg "every other element of a list". > > > > SK> - In principle, the child arguments should be "lazy". This is > SK> what gives you real power. For instance, you can look at the > SK> down argument and decide which order in which to evaluate the > SK> children. Or you could evaluate the left branch, and if the > SK> capacity is already too great, you don't need to traverse the > SK> right branch. Etc. But in practice, you will have many cases > SK> where you want to visit everyone and just collect up the > SK> results of visiting them. > > SK> One convenient way to handle this issue would be to let > SK> programmers to tag individual actions as "strict" or "lazy". > SK> A strict action propagates its "downward" arguments > SK> unchanged, has its children automatically evaluated, and > SK> gets as arguments values of "upward type". A lazy action > SK> gets to make all evaluation choices, and gets as arguments > SK> the computations. It must invoke these to get results. > > SK> Note that this is a completely local modification, and requires no > SK> global knowledge or cooperation with other actions. > >I don't quite see this. If you think of the traversal as assembling >meaning functions, then it's up to the meaning function of a node to >determine which of the subtree meanings to invoke. When there are >inherited attributes to pass, this is always a decision to be made, >since you have to decide what value of the inherited attribute to pass >to the subtree (do they all get the same value, a la environments, or >do they get threaded through, a la stores? Monads lurk here). > > SK> - This model is too restrictive. The whole point is sometimes the > SK> user may not know (or want to know) all the kinds of intermediate > SK> nodes. In such cases, the user can say "otherwise" for the node > SK> type. > >As far as I am concerned, this is the $64 question. Johan and I got >about this far and came to the conclusion that in the examples where >one needed to combine values, an "otherwise" clause would rarely be >useful. This is an empirical question, of course, and I have asked >Karl many times to think about getting some quantitative data on this >kind of issue. > >(Another issue: what do you do with the inherited attributes at an >otherwise node?) > > SK> Typical values attached to "otherwise" would be: > > SK> identity = send the child values upward (if there are multiple > SK> children, this presupposes some sort of "multiple value return" > SK> mechanism) > > SK> void = I'm doing it all w/ effects down below, so traverse all and > SK> ignore values > SK> (Note: this corresponds to current adaptive programming.) > >I think you're on the right track here, though this doesn't quite >characterize it. As near as I can tell, the whole reason that the >current AP approach works is that if you work out the semantics of an >adaptive program, it comes out looking much like your scheme, with > >downtype = uptype = stores > >Hence there is a meaningful "otherwise" operation: > >(define default-node-meaning > (lambda (meaning-of-subtree1 meaning-of-subtree2 ...) > (lambda (store) > (let* ((store1 (meaning-of-subtree1 store)) > (store2 (meaning-of-subtree2 store1)) > .. > (store_n (meaning-of-subtree-n store_n-1))) > store_n)))) > >which threads the store through the subtrees. This corresponds to the >identity action if the new node has only one subtree, but is different >if it has several. (I said monads lurked here!) > > SK> append/flatten/etc = these are intermediate nodes that use > SK> standard combinators to collect up answers > > SK> Therefore, another way to write the third version above is > > SK> Leaf -> \ depth . () . (list ) > SK> Node -> \ depth . children ... . > SK> (apply append children) > > SK> Then no matter how many additional types of nodes you add, leaves > SK> will always return a list, and the intermediate nodes will append > SK> together as many as it gets. > >Well, this assumes that any new nodes that are added have some sort of >homogeneity properties. This is another assumption I have always >found dubious. > >Consider, for example, the problem of determining whether an >expression is closed (This is the real example of which the >nested-container example is a simplification). So you start with >nodes called Var_Exp, App_Exp, Lambda_Exp, and Let_Exp. No problem so >far. > >Now, what do you do when somebody adds a Let*_Exp or a Letrec_Exp to >the language? First you have to figure out what to do with the body >vs what to do with the declarations (you *might* be able to make some >reasonable guesses here on type grounds). Then you have to figure out >something reasonable to do with the bindings. And, oh yes, I forgot >to mention-- the original grammar dealt with Let_Exps that looked like >this (in com3351 sllgen notation): > > (expression ("let" (arbno decl) "in" expression) let-exp) > (decl (identifier "=" expression) a-decl) > >but letrec's look like > > (expression ("letrec" (arbno procdecl) "in" expression) letrec-exp) > (procdecl > (identifier "(" (separated-list identifier ",") ")" "=" expression) > a-procdecl) > >which are entirely different. > >So for the kinds of problems that I think about, it is extremely >implausible that adding new nodes can be handled by any kind of >default reasoning. > >Indeed, if you think of the visitor as providing the *semantics* of a >node, then it becomes even less plausible that one could have a >"default meaning" for some new kind of node. > >So I decided that the right thing to do was to give up on being able >to remain ignorant of all the kinds of intermediate nodes, and rely >instead on the software engineering principle of "Fail Forward Fast". >This led us to isolate these dependencies in a traversal object >separate from the visitor object. The job of the traversal object is >to translate the nodes of the object to be traversed into (a sequence >of) actions chosen from the visitor object. That way, if new nodes >are added, the failures will be localized to the traversal object. We >characterized the traversal object by a DSL, but surely other ways are >possible. > >I see a couple of paths on which forward progress can be made: > >1. We need some better communications pattersn between the visited > object, the traversal object, and the visitor object, to allow for > suitable collaboration when the actual sequence of calls is > data-dependent. We had some of this in early drafts of our paper, > but they didn't survive the translation to Java. > >2. It may be that for other combinations of types, useful "otherwise" > actions are possible. (But of course new nodes may have different > types than the old ones!). On a related note, I sat down once to > work out the types for the standard AP story to see whether > Wadler's parametricity theorems would give any interesting > results, but things got so complicated that I couldn't see my way > through it. > >I agree, however, that all this stuff should be doable in Java. > >I hope these remarks are useful. > >--Mitch > >