ࡱ>   n-aQЋ# #I*9 1RPNG  IHDR77"tPLTE񘘘###vtq___GGqqһBBBt!7y\9 o 9 oU_yd_9k__-/\-d-W@_yy@_y__;_9__9@___+G++2-2@__9_9_ 99r9vq}9SZ9I7_y2jXbKGDHIDATxeV //Yn5ne@{@5w{_@r;nۮ P ;ή-l+I~Lt¨2d0_dܮ}(쀻fgH^7=HsT#0˲m>R@q nUp]'иkE"4CCq<]<˜eρQE@jnl=.B+ &'QK@EYT&K6Ԋ.U/{Q9h_`%;֘P^S`Us9%[zfN, *"T4LjP^{2dFl* 1p~aI̤(|1H_[K2;]AԀf: eQs3B CwpE汯uxd)SO_7Ԡҫny?7N|+B.y qEK'}'3O{.{. #ēEVܟ: f.oV%fؓN#yKQOOe,CJӐH448y^ oUk~47ƅk-y.MId4z~O gb:3wcUϳЋ*VuzkQ {;st6H֨-G1=Esh8@Vl=}WyS}ANAnB+^/O1$m>w2~pan6HK >{=Ee#)UÄ#ICp_b+8*sX5?U+X2*' LxNٺΕR:Yh/{$ҕ /I\}~e쭫BJj-8먰pn9Y?6+⍇DLIENDB`n[(4 T/ 00DArial0Dbdtvbb(b0LbLb 0"DTimes New Romanbb(b0LbLb 0 DCourierw Romanbb(b0LbLb 0 10DCourier Newmanbb(b0LbLb 01("   @n?" dd@  @@``_@,WHOOSH.WAV.WAV 10103RIFFWAVEfmt ++data~~~~~~~~~~~~~~~~~~~~~~~~~~~|||~~~~~zvtvxz|~zvrnlrv||vtrpptz~|xvtv|~~zxvvvz|~xrlhntzzvrrpprrx~|j[QU_|bICCYn[ICY~zlnh]_r|]SUSSjz|x__l~v_]drnUb|nfd_]d]5=rrnj]jz~lMldrx[[_f|YQfWK_xh[zx[CIjzxxdSQz|_fI9WӹM;QnvK;OUx~xj]]YS~ɵlM?plM;CGpٵ[)Kh|% %;xtKQS]ɖbGr|lSnvz~nfS[nëx;Az=+AYݻ|=/1r_ ?|潄W5/Czãf)/pvbMQr|O=OtjdhjlG?G_ɊK3לdQCMppW;1SŷAMz/#?bx͖SAM[hvhYp~~zrvt[]ptWOUtxxd]v~vvxzd_xzh_nrSQltbdp~_lrQ_l][tf]W]~hWfp|fWhnhbU[hzlSCWbYbnxpdhjvjM9Ot]GQ[dpp~hhhdpx~xh]Yntnrp]dlvjQMb|vdjpzxzztljr||_[r~~jb_j|z|xpp~~v]Wh||zx|x|zzndhpxr]Yfntzjl|z||~vppnrzphrxz|~|xtrjjtv~~vz|z||xrrv~xrprtz|||vzxvx|xtx~~~~~~~zxxxx|zxz~~~rrz~|xz~~|vtx|zxz|~~~||zx|||~~zz|zz~~~~|~~||~~||zz|~||z~~~~zxzz|~~~~|~~~|~||~~~~~~~~~~~~~|||~~~~~~~~~~~~~||~~||~||~~~~|||~~~~||||~~~~~~||||~~~~~~~~~~~|~~~~|zz~~~~~~~||||~~||~~~~~|||~~~~~|||~|~|~~~~|z|~~~~~~~|||~~~~~~~~||~~~~~~~~ ^$%+,-597:;<=>?+@ -  !"./0123468 1 3111128551180@B3C.D0FG HKMNPQ RTUVWXYZ[\]^_ `a bc  h i  n op qr st uv w/X$zb$*9 1R z 0e0e     A@  AԔ 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||@ g4UdUdXb 0Pbpp@ <4dddd,vb<4!d!d,vb2g4?d?dXb 0Pbrpk p? %O =F6A domain specific language for Traversal SpecificationQJohan Ovlinger Mitchell Wand Northeastern University Center for Software Sciences$R4UR Talk OutlineIntroduction introduce visitor pattern point out some of its shortcomings introduce our motivating, and running, example show how it is unsatisfactorily solved by visitor pattern, despite the obvious applicability. $  Introducing the Visitor PatternVisitor pattern is useful for removing structural assumptions from programs, by separating navigational and behavioral concerns adding behavior over classes independently of their definition.$DBCritiquing Traversals+Visitor is guided around object graph by traversal (iterator, strategy) Unfortunately, the traversal serializes the hierarchical structure of the object being traversed into a series of visits. One global traversal is typically hard-coded into classes, restricting its interface to Visitors to LCD. Motivating ExamplevTaken from real world experience, writing a compiler. We want to verify that all variables have been declared before use. Obvious use of visitor pattern (suggested in  Design Patterns ). ECUseless languageOur example is a very simple language that only has the ability to bind and reference variables. Lets are non recursive No Shadowing (for simplicity) Epitomizes a common task: Finding undeclared variables. Leave grammar up to imagination.AST Class Diagram!A small AST objectCAVisitor ConsiderationsjStrategy: Calculate new bindings for one level and also analyze their bodies at same time Remember which variables are in scope when entering a Let, and reset on exiting. Since body of binding may also include Lets, must also remember List of new bindings to be added to scope. Calculate list of bindings to add from let and process their bodies simultaneously.$ a a#  animation 536Visitor s view of Traversal646Visitor s view of Traversal756Visitor s view of Traversal866Visitor s view of Traversal976Visitor s view of Traversal:86Visitor s view of Traversal>>6Visitor s view of Traversal;96Visitor s view of Traversal<;6Visitor s view of Traversal?<6Visitor s view of Traversal@=6Visitor s view of Traversal=:6Visitor s view of TraversalFD6Visitor s view of TraversalGE6Visitor s view of TraversalHF6Visitor s view of TraversalIGImplementation in JavaWe assume a  typical traversal distributed through classes which calls appropriate accept method on Visitor. Visitor is a superclass of all visitors, and has default do-nothing accept methods. Visitor in Java $! Visitor Cont %"Visitor Interface Critique[Since all traversal code is outside our control, visitors have to pass parameters to subsequent visits by side-effecting own variables. Very imperative. We assume a more intricate interface than normally accepted -- rather than just accept, we have before, middle and after. Otherwise, it would be hard to know when to add new bindings to scope. b\ JJHStructural CritiqueThe structure cannot be ignored -- the programmer needs to know when to save/restore the parameter passing variables. Programmer needs to save and restore state manually Restoring state depends on our non-standard visitor interface. The order of traversing parts is vitally important.Visitor Critique SummaryVisitors want to return results and accept arguments like recursive functions The visitor needs to control the order in which parts are traversed. A more elaborate traversal/visitor interface is desirable. accept is least common denominator. & `S Talk Outline>Introduction Traversal Specifications compare to std traversal$&&Traversal Specification-Define traversals with domain specific language. Traversal is external to classes, and can be tailored to just one visitor, or be generic. Traversal is explicit about traversing all parts. Assume only local knowledge of the object structure. Non-local knowledge cannot be expressed in Traversal Spec...Features of our LanguageSeparate Behavior, Navigation, and Class Definition Specify which parts of an object are to be traversed, and which order Traversals and Visitors return results Traversal may bind intermediate results Behavior may influence Navigation Iterate over collections automaticallyKIGo Everywhere TraversalSQThe Go Everywhere TraversalWill generate an interface with before, after, middle methods, just like the traversal will impose its p Each traversal imposes different requirements on visitors it is used with By generating Java interfaces instead of abstract classes, a visitor may be used with several traversals.N gW Talk OutlineGIntroduction Traversal Specifications compare to std traversal overview$&"&" Syntax of the LanguageVariables are declared with C/C++/Java syntax, with optional types A Traversal is a named set of TraversalEntries, named after the class of objects they traverse. TraversalEntry describes how to traverse objects of a certain class, using a list of Actions including visit and traverse. :  QO More syntaxOn entering an object, the most specific TraversalEntry for that object is executed, by performing the Actions in order and returning the result of the last one. Visit actions name the visitor method to invoke, and which arguments to pass (current object is always passed). Traversal actions specify the part of the current object to traverse, along with arguments to the traversal. iX Talk OutlineIntroduction Traversal Specifications compare to std traversal overview running example detailed interface to visitor recursion6&2(&2(PN Our StrategyWrite a traversal that calls specific methods on visitor, at appropriate time. Visits return their results to traversal. Generate a Java Interface from the traversal to be implemented by visitor. Traversal uses recursion to save/restore visitor variables automatically. &#Traversal Spec for AST (%Interface for AST Traversal )&Visitor Definition RPCompare to Visitor patternSurprisingly, we much prefer the separation of our version. Navigation and Behavior are specified separately, but are tailored kY Talk OutlinenIntroduction Traversal Specifications compare to std traversal overview running example influencing navigation$&I&IbTBehavior influences Navigation In several cases, it is necessary to decide dynamically the navigational details. The only way to do this with the visitor pattern is to hard code another traversal both in the classes, and even worse, in the visitor.*'Example: Recursive LetsRecursive Let adds bound variables to scope before checking bodies. Let has boolean variable indicating whether it is recursive. Strategy: First calculate variables bound by Let Add these to scope at appropriate time during processing$``+(In JavaSeparate traversal, launched from before(Let) collects bound vars, with separate visitor. The new traversal doesn't enter bodies of Let or Bindings.,*Recursive Lets in Java -+ GBVisitor 21 Java CritiqueThe traversal_bindings is hard-coded in visitor, mixing navigation and behavior. We need another visitor, as we do not want to calculate bindings twice, and the before, middle, after interface is to simple to allow two different modes of use for visitor &ImZ Talk OutlineIntroduction Traversal Specifications compare to std traversal overview running example influencing navigation Done right with Traversal Specifications Thunks Calling other traversalsH&I)!&I)!MKIn Traversal Specs#Named visits make it easy to use the same (extended) visitor with both traversals. Auxiliary traversal is called from main traversal, not visitor. Thunks make objects out of Traversal Snippets, allowing the visitor to decide which option to use, without knowledge of navigational details. .,Traversal Spec /.Traversal Spec, cont  Dynamically Controlling BehaviorThunks encode current object and a list of actions for later invocation. Thunks are first class objects that can be passed as arguments to visitors. The return type of the Thunk's actions determines the type of the Thunk.1/The interfaces generated ThunksClose over (for reading only) traversal variables at definition site. Can be nested, and can be returned from traversals and other thunks. Are typed by return value. Are first class objects.NLUses of Thunks|Allow complicated behaviors to be programmed Traversals over cyclic structures Fixpoint iterations Searches in Binary Trees$-P-P30Calling Other traversalsCould just invoke a traversal in the standard way from a visitor, but then navigational details enter the visitor. othertrav allows mutually recursive traversals to be written to share the same visitor. Used this to collect the bound variables&s yEncoding State in Traversals$We have mutually recursive traversals This allows us to encode traversal state in traversal name When we entered Let, we were in  check state, then entered  collect state to get bindings, and then exited that to  check state again. We don t have tail recursion of course.$aa42Inlawsuse traversal to encode stateo[ Talk OutlineIntroduction Traversal Specifications compare to std traversal overview running example influencing navigation Wrapping up modifying the class graph Miscellania6&U&&U&Class Graph ModificationsFor all but the most trivial modifications to the class graph, the traversal specification must be modified as well. Traversals can only express local knowledge, so the modifications will be local as well.OMOther abilitiesATraversing Enumerations Visitor must provide combine method to combine traversal results for each element to one result for whole traversal. Traversing Results Can invoke traversal on values returned from visits or traversals, not just parts of the host object Traverse TraversalEntries for superclasses. Extend behaviorluf,uf,Traversing CollectionsZWe have a for-each Action which allows us to iterate over collections Impacts on visitors.Traversing Variables{We want to traverse dynamically generated objects So we are able to traverse not only parts but also results from visitors. Super classesThe super directive allows a traversal entry to invoke the next most precise Traversal Entry; the Traversal Entry defined on its super class. The root has a do-nothing entry implicitly, so there is always something to invoke.Semantic IssuesIIn this section we describe the semantics of the Traversal Specifications Type Checking@Need simple type checking to alleviate explicit type annotation Most Precise WrapperCCan't use inheritance; not in class graph Dynamically search objectTranslation to JavaDetailsp\ Talk OutlineDIntroduction Traversal Specifications Conclusion future work summary$11 Conclusion<Future work Investigate Multiple Extension Dimensions Visitors can be subclasses TraversalEntries for superclasses Traversal should be extensible Summary We allow Traversals and Visitors to have more detailed interface to visitors be more recursive -- return results, pass args Behavior needs to influence Navigationl *\$ *\$/VWXYZ[\]^_ c h jlnqr  ` ̙33` ` ff3333f` 333MMM` f` f` 3>?" dd@,|?" dd@   " @ ` n?" dd@   @@``PR    @ ` ` p>>   7(    Zdp@j  Bd@j  Bd@  6Tv P v T Click to edit Master title style! !  0v  v RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  0v `` v =*  0tv `  v ?*  0v `  v ?*  < v  v4Center for Software Sciences Northeastern University&54  t  c LA(C:\tmp\nu-logo2.gif6JH  0޽h ? ff3 ,Blank Presentation.pot 0 Pp4(  p p B$ ?    A*   p B3 ? @  > C*( p p 0 ?HP  >( p B2 ? @0 > RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S p H$1 ?  > A*   p Hd- ? @ > C*( H p 0j ? ̙33 0(  l  C p v l  C t `   v H  0޽h ? ̙33   D<(  |  Tdp@d  <d@d  <d@l  C D)P   l  C 4 v    <T  v4Center for Software Sciences Northeastern University&54  t  c LA(C:\tmp\nu-logo2.gif6JB  s *޽h ? ff3  @ (   l  C P  v l  C  v H  0޽h ?   `(  l  C -P   l  C $.  H  0޽h ? ff3  Px(  xl x C TP   l x C   H x 0޽h ? ff3  (  l  C tP   l  C t  H  0޽h ? ff3!  p*pa( }@a pl p C D/P    p 6. @ BProg" p 60P  ALet" p 6d0P  ARef"  p 60P@ AFun"jB p BD8c pB p HDԔ0 0 P p  BCDEFԔ @`P p 61 @ DString" p 61 0  BBind" p 6D2 p CEmpty" p # BCDEFԔ @  pB p HDԔ  jB p BD8c jB  p BD8c @  !p # BC DEF8c3    @m 1 "p # BC6DEF8c66 @@jB #p BD8c jB $p BD8c0   &p 3 B0CZDEF8c+0ZZ @  4 'p 3 BCDEF8c  @W j (p B ? @ )p BDP?   CExp$ *p B?  p  HBindList$ H p 0޽h ? ff3%  Q%I%,,$( Ajff r  S 4P     64  9Let  6D5 :Bind  65s :Bind  666V  ;Empty  6d6    9Let  66   9Ref  6$7  ;foo  67s  ;bar  67  9Fun  6D8s  9Ref  68  9x  6Ԥ 9Ref  6ԡ Iy,  6s  Kfoo,  6$   :Bind  6   ;Empty  6    <grok  6D   9Ref  6   ;bar  6   Jgrok*B   `D8c?@ @B   `D8c?@ @B   `D8c?@ @B   `D8c?@@B   `D8c? B   `D8c? B   `D8c?  B   `D8c? B   `D8c? B   `D8c?` !  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @  B "  `D8c?@B #  `D8c?@  B $  `D8c? B %  `D8c?@   &  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ @  '  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @0@  (  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ 0 # B )  `D8c?  @ * Td8c? 0  DLET foo = FUN (x) {y} bar = foo IN LET grok = bar IN grok\E + 6p :ProgB ,  `D8c?H  0޽h ? ff3  (    l  C P   l  C   H  0޽h ? ff3  (  l  C P   l  C   H  0޽h ? ff3'  &&.0Q&(  r  S P     6$  9Let  6 :Bind  6s :Bind  6D6V  ;Empty  6    9Let  6   9Ref  6d  ;foo  6s  ;bar  6$  9Fun  6s  9Ref  6  9x  6D 9Ref  6 Iy,  6s  Kfoo,  6d   :Bind  6d<   ;Empty  6<    <grok  6$=   9Ref  6=   ;bar  6=   Jgrok*B   `D8c?@ @B   `D8c?@ @B   `D8c?@ @B   `D8c?@@B   `D8c? B   `D8c? B   `D8c?  B   `D8c? B   `D8c? B   `D8c?` !  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @  B "  `D8c?@B #  `D8c?@  B $  `D8c? B %  `D8c?@   &  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ @  '  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @0@  (  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ 0 # B )  `D8c?   + 6D>p :ProgB ,  `D8c? - NԔ?@0,$ 0 . T?8c? Z& k%before Prog visit in scope to add*& 0 HdQ))?   ~6administrator: these are missing the Bind middle visit,7 2)H  0޽h ? ff3&  %%-2N%(  r  S $@P     6@  9Let  6@ :Bind  6DAs :Bind  6A6V  ;Empty  6B    9Let  6dB   9Ref  6B  ;foo  6$Cs  ;bar  6C  9Fun  6Cs  9Ref  6DD  9x  6D 9Ref  6E Iy,  6dEs  Kfoo,  6E   :Bind  6$F   ;Empty  6F    <grok  6F   9Ref  6DG   ;bar  6G   Jgrok*B   `D8c?@ @B   `D8c?@ @B   `D8c?@ @B   `D8c?@@B   `D8c? B   `D8c? B   `D8c?  B   `D8c? B   `D8c? B   `D8c?` !  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @  B "  `D8c?@B #  `D8c?@  B $  `D8c? B %  `D8c?@   &  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ @  '  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @0@  (  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ 0 # B )  `D8c?   * 6Hp :ProgB +  `D8c? , NԔ?P,$ 0 1 Tv8c?: Z& w1before Prog before Let visit in scope to add*2H  0޽h ? ff3&  %%-0Z%(   0 Tw8c?T Z& =before Prog before Let before Bind visit in scope to add*>'r  S P     6t  9Let  6Ժ :Bind  64s :Bind  66V  ;Empty  6    9Let  6T   9Ref  6  ;foo  6s  ;bar  6t  9Fun  6Խs  9Ref  64  9x  6 9Ref  6 Iy,  6Ts  Kfoo,  6   :Bind  6   ;Empty  6t    <grok  6   9Ref  64   ;bar  6   Jgrok*B   `D8c?@ @B   `D8c?@ @B   `D8c?@ @B   `D8c?@@B   `D8c? B   `D8c? B   `D8c?  B   `D8c? B   `D8c? B   `D8c?` !  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @  B "  `D8c?@B #  `D8c?@  B $  `D8c? B %  `D8c?@   &  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ @  '  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @0@  (  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ 0 # B )  `D8c?   * 6p :ProgB +  `D8c? , NԔ?P,$ 0H  0޽h ? ff3C&  %%-0%(  f 0 0 Tw8c?n Z& Jbefore Prog before Let before Bind before Fun x visit in scope to addFK2r  S P     64  9Let  6/ :Bind  6T0s :Bind  606V  ;Empty  61    9Let  6t1   9Ref  61  ;foo  642s  ;bar  62  9Fun  62s  9Ref  6T3  9x  63 9Ref  64 Iy,  6t4s  Kfoo,  64   :Bind  645   ;Empty  65    <grok  65   9Ref  6T6   ;bar  66   Jgrok*B   `D8c?@ @B   `D8c?@ @B   `D8c?@ @B   `D8c?@@B   `D8c? B   `D8c? B   `D8c?  B   `D8c? B   `D8c? B   `D8c?` !  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @  B "  `D8c?@B #  `D8c?@  B $  `D8c? B %  `D8c?@   &  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ @  '  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @0@  (  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ 0 # B )  `D8c?   * 67p :ProgB +  `D8c? , NԔ? ,$ 0H  0޽h ? ff3`&  &&-0%(  M 0 T8c? Z& Wbefore Prog before Let before Bind before Fun x before Ref x visit in scope to addVX2 r  S 8P     68  9Let  6T9 :Bind  69s :Bind  6:6V  ;Empty  6t:    9Let  6:   9Ref  64;  ;foo  6;s  ;bar  6  9Fun  6Ts  9Ref  6  9x  6 9Ref  6t Iy,  6s  Kfoo,  64   :Bind  6   ;Empty  6    <grok  6T   9Ref  6   ;bar  6   Jgrok*B   `D8c?@ @B   `D8c?@ @B   `D8c?@ @B   `D8c?@@B   `D8c? B   `D8c? B   `D8c?  B   `D8c? B   `D8c? B   `D8c?` !  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @  B "  `D8c?@B #  `D8c?@  B $  `D8c? B %  `D8c?@   &  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ @  '  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @0@  (  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ 0 # B )  `D8c?   * 6tp :ProgB +  `D8c? , NԔ?P,$D 0H  0޽h ? ff3^&  &&-0%( N B K 0 Tu8c?Z& abefore Prog before Let before Bind before Fun before Ref x after Ref x visit in scope to addJb= r  S P     6T  9Let  6 :Bind  6s :Bind  6t6V  ;Empty  6    9Let  64   9Ref  6  ;foo  6s  ;bar  6T  9Fun  6s  9Ref  6  9x  6t 9Ref  6 Iy,  64s  Kfoo,  6   :Bind  6?   ;Empty  6T@    <grok  6@   9Ref  6A   ;bar  6tA   Jgrok*B   `D8c?@ @B   `D8c?@ @B   `D8c?@ @B   `D8c?@@B   `D8c? B   `D8c? B   `D8c?  B   `D8c? B   `D8c? B   `D8c?` !  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @  B "  `D8c?@B #  `D8c?@  B $  `D8c? B %  `D8c?@   &  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ @  '  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @0@  (  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ 0 # B )  `D8c?   * 6Ap :ProgB +  `D8c? , NԔ? ,$D 0H  0޽h ? ff3u&  %&& -0%(  b 0 TD8c?Z& lbefore Prog before Let before Bind before Fun before Ref x after Ref x after Fun visit in scope to addVm=  r  S TCP     6C  9Let  6D :Bind  6tDs :Bind  6D6V  ;Empty  64E    9Let  6E   9Ref   6E  ;foo   6TFs  ;bar   6F  9Fun   6Gs  9Ref   6tG  9x  6G 9Ref  64H Iy,  6Hs  Kfoo,  6H   :Bind  6TI   ;Empty  6I    <grok  6J   9Ref  6tJ   ;bar  6J   Jgrok*B   `D8c?@ @B   `D8c?@ @B   `D8c?@ @B   `D8c?@@B   `D8c? B   `D8c? B   `D8c?  B   `D8c? B   `D8c? B    `D8c?` !  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @  B "  `D8c?@B #  `D8c?@  B $  `D8c? B %  `D8c?@   &  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ @  '  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @0@  (  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ 0 # B )  `D8c?   * 64Kp :ProgB +  `D8c? , NԔ? ,$D 0H  0޽h ? ff3&  N&F&0-1%(     1 T 8c?Z& ybefore Prog before Let before Bind before Fun before Ref x after Ref x after Fun before Bind visit in scope to addrz=   r  S pP     6$q  9Let  6q :Bind  6qs :Bind  6Dr6V  ;Empty  6r    9Let  6s   9Ref  6ds  ;foo  6ss  ;bar  6$t  9Fun  6ts  9Ref  6t  9x  6Du 9Ref  6u Iy,  6vs  Kfoo,  6dv   :Bind  6v   ;Empty  6$w    <grok  6w   9Ref  6w   ;bar  6Dx   Jgrok*B   `D8c?@ @B   `D8c?@ @B   `D8c?@ @B   `D8c?@@B   `D8c? B   `D8c? B   `D8c?  B   `D8c? B   `D8c? B   `D8c?` !  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @  B "  `D8c?@B #  `D8c?@  B $  `D8c? B %  `D8c?@   &  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ @  '  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @0@  (  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ 0 # B )  `D8c?   * 6xp :ProgB +  `D8c? , NԔ?`P,$D 0H  0޽h ? ff3;(  ''@/4{'( **   4 T8c?>Z& @... before Bind before Fun before Ref x after Ref x after Fun x before Bind before Ref after Ref before Empty after Empty after Bind bar visit in scope to add&  Hr  S $zP     6z  9Let  6z :Bind  6D{s :Bind  6{6V  ;Empty  6    9Let  6T   9Ref  6  ;foo  6s  ;bar  6t  9Fun  6s  9Ref  64  9x  6 9Ref  6 Iy,  6Ts  Kfoo,  6   :Bind  6   ;Empty  6t    <grok  6   9Ref  64   ;bar  6   Jgrok*B   `D8c?@ @B   `D8c?@ @B   `D8c?@ @B   `D8c?@@B   `D8c? B   `D8c? B   `D8c?  B   `D8c? B   `D8c? B   `D8c?` !  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @  B "  `D8c?@B #  `D8c?@  B $  `D8c? B %  `D8c?@   &  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ @  '  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @0@  (  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ 0 # B )  `D8c?   * 6p :ProgB +  `D8c? , NԔ?`P,$D 0 / NԔ?` ,$D 0 1 NԔ?P ,$D 0H  0޽h ? ff3 '  &&P-4L&(   4 TD 8c?>i& u... before Fun before Ref x after Ref x after Fun x before Bind before Ref after Ref before Empty after Empty after Bind bar after Bind foo,bar visit in scope to add  H r  S tP     6  9Let  64 :Bind  6s :Bind  66V  ;Empty  6T    9Let  6   9Ref  6  ;foo  6ts  ;bar  6  9Fun  64s  9Ref  6  9x  6TS 9Ref  6S Iy,  6Ts  Kfoo,  6tT   :Bind  6T   ;Empty  64U    <grok  6U   9Ref  6U   ;bar  6TV   Jgrok*B   `D8c?@ @B   `D8c?@ @B   `D8c?@ @B   `D8c?@@B   `D8c? B   `D8c? B   `D8c?  B   `D8c? B   `D8c? B   `D8c?` !  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @  B "  `D8c?@B #  `D8c?@  B $  `D8c? B %  `D8c?@   &  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ @  '  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @0@  (  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ 0 # B )  `D8c?   * 6Vp :ProgB +  `D8c? , NԔ?P,$D 0H  0޽h ? ff38'  &&`-0x&(  % 0 T8c?>i& ... before Ref x after Ref x after Fun x before Bind before Ref after Ref before Empty after Empty after Bind bar after Bind foo,bar middle Let foo,bar visit in scope to add  H  r  S 4XP     6X  9Let  6X :Bind  6TYs :Bind  6Y6V  ;Empty  6Z    9Let  6tZ   9Ref  6Z  ;foo  64[s  ;bar  6[  9Fun  6[s  9Ref  6T\  9x  6\ 9Ref  6] Iy,  6t]s  Kfoo,  6]   :Bind  64^   ;Empty  6^    <grok  6^   9Ref  6   ;bar  6T   Jgrok*B   `D8c?@ @B   `D8c?@ @B   `D8c?@ @B   `D8c?@@B   `D8c? B   `D8c? B   `D8c?  B   `D8c? B   `D8c? B   `D8c?` !  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @  B "  `D8c?@B #  `D8c?@  B $  `D8c? B %  `D8c?@   &  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ @  '  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @0@  (  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ 0 # B )  `D8c?   * 6p :ProgB +  `D8c? , NԔ?P,$D 0H  0޽h ? ff3;*  ))p07{)(   7 T 8c?>i& ... after Bind bar after Bind foo,bar middle Let foo,bar before Let foo,bar before Bind foo,bar before Ref foo,bar after Ref foo,bar before Empty foo,bar after Empty foo,bar after Bind Let foo,bar grok middle Let foo,bar,grok visit in scope to addv          r  S 4P     6  9Let  6 :Bind  6Ts :Bind  66V  ;Empty  6    9Let  6t   9Ref  6Խ  ;foo  64s  ;bar  6  9Fun  6s  9Ref  6T  9x  6 9Ref  6 Iy,  6ts  Kfoo,  6   :Bind  64   ;Empty  6    <grok  6   9Ref  6T   ;bar  6   Jgrok*B   `D8c?@ @B   `D8c?@ @B   `D8c?@ @B   `D8c?@@B   `D8c? B   `D8c? B   `D8c?  B   `D8c? B   `D8c? B   `D8c?` !  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @  B "  `D8c?@B #  `D8c?@  B $  `D8c? B %  `D8c?@   &  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ @  '  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @0@  (  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ 0 # B )  `D8c?   * 6p :ProgB +  `D8c? / NԔ? @ ,$D 0 1 NԔ? P ,$D 0 3 NԔ? P@ ,$D 0 4 NԔ? P@ ,$D 0H  0޽h ? ff3(  '' -2$X'( $ F $ $ TT8c?>Z& ... middle Let foo,bar before Let foo,bar before Bind foo,bar before Ref foo,bar after Ref foo,bar before Empty foo,bar after Empty foo,bar after Bind Let foo,bar grok middle Let foo,bar,grok before Ref foo,bar,grok before Ref foo,bar,grok visit in scope to add^            r $ S yP    $ 6p  9Let $ 6K :Bind $ 64Bs :Bind $ 6B6V  ;Empty $ 6B    9Let  $ 6   9Ref  $ 64  ;foo  $ 6s  ;bar  $ 6t7  9Fun  $ 648s  9Ref $ 67  9x $ 6t 9Ref $ 6 Iy, $ 6s  Kfoo, $ 6T   :Bind $ 6   ;Empty $ 6    <grok $ 6   9Ref $ 6T   ;bar $ 6>   Jgrok*B $  `D8c?@ @B $  `D8c?@ @B $  `D8c?@ @B $  `D8c?@@B $  `D8c? B $  `D8c? B $  `D8c?  B $  `D8c? B  $  `D8c? B !$  `D8c?` "$  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @  B #$  `D8c?@B $$  `D8c?@  B %$  `D8c? B &$  `D8c?@   '$  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ @  ($  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @0@  )$  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ 0 # B *$  `D8c?   +$ 6?p :ProgB ,$  `D8c? 2$ NԔ?P P,$D 0H $ 0޽h ? ff3(  ''0--(V'(  ( ( Td?8c?>Z& ... before Let foo,bar before Bind foo,bar before Ref foo,bar after Ref foo,bar before Empty foo,bar after Empty foo,bar after Bind Let foo,bar grok middle Let foo,bar,grok before Ref foo,bar,grok before Ref foo,bar,grok after Let foo,bar visit in scope to add^            r ( S 4P    ( 6  9Let ( 6t :Bind ( 6Ts :Bind ( 6"v6V  ;Empty ( 6w    9Let  ( 6w   9Ref  ( 6Tx  ;foo  ( 6xs  ;bar  ( 6y  9Fun  ( 6tys  9Ref ( 6y  9x ( 64z 9Ref ( 6z Iy, ( 6zs  Kfoo, ( 6T{   :Bind ( 6{   ;Empty ( 6|    <grok ( 6t|   9Ref ( 6|   ;bar ( 64}   Jgrok*B (  `D8c?@ @B (  `D8c?@ @B (  `D8c?@ @B (  `D8c?@@B (  `D8c? B (  `D8c? B (  `D8c?  B (  `D8c? B  (  `D8c? B !(  `D8c?` "(  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @  B #(  `D8c?@B $(  `D8c?@  B %(  `D8c? B &(  `D8c?@   '(  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ @  ((  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @0@  )(  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ 0 # B *(  `D8c?   +( 6}p :ProgB ,(  `D8c? -( NԔ? P@ ,$D 0H ( 0޽h ? ff3(  <(4(@./,'(   , , T8c?>Z& C... before Ref foo,bar after Ref foo,bar before Empty foo,bar after Empty foo,bar after Bind Let foo,bar grok middle Let foo,bar,grok before Ref foo,bar,grok before Ref foo,bar,grok after Let foo,bar after Let after Prog visit in scope to add2          r , S P    , 6  9Let , 6t :Bind , 6Ԃs :Bind , 646V  ;Empty , 6r    9Let  , 6$   9Ref  , 6ļ  ;foo  , 6ds  ;bar  , 6  9Fun  , 6s  9Ref , 6D  9x , 6 9Ref , 6 Iy, , 6$s  Kfoo, , 6Ĺ   :Bind , 6d   ;Empty , 6    <grok , 6   9Ref , 6D   ;bar , 6$    Jgrok*B ,  `D8c?@ @B ,  `D8c?@ @B ,  `D8c?@ @B ,  `D8c?@@B ,  `D8c? B ,  `D8c? B ,  `D8c?  B ,  `D8c? B  ,  `D8c? B !,  `D8c?` ",  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @  B #,  `D8c?@B $,  `D8c?@  B %,  `D8c? B &,  `D8c?@   ',  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ @  (,  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @0@  ),  0e0e    BCDEF 8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ 0 # B *,  `D8c?   +, 6 p :ProgB ,,  `D8c? -, NԔ?P,$D 0 ., NԔ?@0,$D 0H , 0޽h ? ff3  `4(  4l 4 C DP   l 4 C d   H 4 0޽h ? ff3  H@(  l  C P   ,  N8c?p zclass UDVisitor extends Visitor { Vector inscope,boundbylet; Stack oldscope, oldbound; void before(Ref host) { if (!inscope.contains(host.str)) complain(host); } void after(Bind host) { boundbylet.addElement(host.str); } void before(Fun host) { inscope.addElement(host.str); } void after(Fun host) { inscope.removeElement(host.str); } {{H  0޽h ? 9  y(  l  C DP     T8c? Z  I void before(Let host) { oldscope.push(inscope.copy()); oldbound.push(boundbylet.copy()); boundbylet = new Vector(); } void middle(Let host) { inscope.add_from(boundbylet); } void after(Let host) { inscope = oldscope.pop(); boundbylet = oldbound.pop(); }H  0޽h ? ff3  S( }@\@ l  C P   l  C d v 3  H ))? p]  badministrator: We could do with just accept by adding bound at empty and checking on the way down.,c 2UH  0޽h ? ff3  p8R(  8l 8 C d P   l 8 C      8 HT))?0   ^administrator: the fact that Binding s body may contain lets forces Let to s/r bound. Also imp is when not to restore vars,{ 2mv  8 HD))?    ;administrator: if we s/r around Bindings, then all is lost ,< 2.0 8 H))? P  _administrator: to restore state with only accept would be hard. We know after will close before,` 2R 8 H4))?pe  s+administrator: who ever said that it could?,, 2 8 H))?p e  j"administrator: Bindings before exp,# 2H 8 0޽h ? ff3.  n( o[+ l  C $P   l  C   N  H))?@01  }administrator: it is natural to expect that complex behavior will need more complicated behavior than before / middle / after,~ 2pH  0޽h ?    PH(  |  Tdp@d  <d@d  <d@r  S P   r  S     <4  v4Center for Software Sciences Northeastern University&54  t  c LA(C:\tmp\nu-logo2.gif6JB  s *޽h ? ff3e   (  l  C D P   l  C      H4))? 3  administrator: surprisingly, we don t have the faults we pointed out with visitor pattern.,[ 2MH  0޽h ?   @*( s l  C d$P   l  C $ `     H))?   9administrator: There is a lot of talking about this slide,: 2,B  s *޽h ?   <( ܽ  <n < TO8c?`Z traversal everywhere() = Program => visit before () traverse exp () visit after () Ref => visit before () visit after() Let => visit before () traverse bindings() visit middle () traverse exp() visit after () Binding => visit before () traverse exp () visit middle () traverse bindings() visit after () ...l < C WP    < H$R))?`0  dadministrator: this makes an interface everywhere_visitor that looks just like the Visitor class. Interface, not class, because we will have many traversals, with different requirements, while the std model has just one traversals, or if several, all w/ subsets of one big interface., 2 < HT))?@   x0administrator: introduce concept of subtraversal,1 2#H < 0޽h ? ff3  @l( f3L ll l C P   l l C t  H l 0޽h ? ff3   PH(  |  Tdp@d  <d@d  <d@r  S P   r  S T    <T  v4Center for Software Sciences Northeastern University&54  t  c LA(C:\tmp\nu-logo2.gif6JB  s *޽h ? ff3  P((  (l ( C D&P  v l ( C &P v H ( 0޽h ?   `( 90 `l ` C tP   l ` C    H ` 0޽h ? ff3  PH( @ |  Tdp@d  <d@d  <d@r  S uP   r  S Ds    <s  v4Center for Software Sciences Northeastern University&54  t  c LA(C:\tmp\nu-logo2.gif6JB  s *޽h ? ff3  \( AtD)) \l \ C T P   l \ C    H \ 0޽h ? ff3W  (  l  C !P     Td!8c?`Z g3traversal unbound(Vector scope) = Program => traverse exp (scope) Ref => visit checkref(scope) Let => Vector bound = traverse bindings(scope) Vector newscope = visit concat(scope,bound) traverse exp(newscope) Binding => Vector bound = traverse bindings(scope) visit addtobound(bound) traverse exp(scope) bound Empty => visit emptybound Fun => visit addvar(scope) traverse exp(scope) visit remvar(scope)44H  0޽h ? ff3K  (  l  C !P     T$"8c?  ['interface unbound_visitor { void checkref(Ref host, Vector scope); Vector concat(Let host,Vector a,Vector b); void addtobound(Binding host, Vector bound); Vector emptybound(Empty host, Vector bound); void addvar(Fun host,Vector scope); void remvar(Fun host,Vector scope); }((H  0޽h ? ff3    `( eq, l  C "P     T"8c?  0class UBVisitor implements unbound_visitor { Vector concat(Let host,Vector a,Vector b) {...} void checkref(Ref host, Vector inscope) { if (!inscope.contains(host)) complain(host); } void addtobound(Binding host, Vector bound) { bound.addElement(host.var); } Vector emptybound(Empty host, Vector bound) { return new Vector(); } void addvar(Fun host,Vector scope) { scope.addElement(host.var); } void remvar(Fun host,Vector scope) { scope.removeElement(host.var); } }H  0޽h ? ff3   d(  dl d C P   l d C   H d 0޽h ? ff3  PH(  |  Tdp@d  <d@d  <d@r  S  P   r  S T    <  v4Center for Software Sciences Northeastern University&54  t  c LA(C:\tmp\nu-logo2.gif6JB  s *޽h ? ff3  0(  l  C TP   l  C ~  H  0޽h ? ff3  ( \w<4 l  C :P   l  C t:  H  0޽h ? ff3  1)( X l  C T<P   l  C <    HS))?    administrator: so this example needs two traversals, as if we enter the bodies of bindings, we re hosed.,i 2[H  0޽h ? ff3  *(  r  S TP   x  T8c?`Z class UDVisitor extends Visitor { ... void before(Let host) { oldscope.push(inscope.copy()); oldbound.push(boundbylet.copy()); GBVisitor gbv = new GBVisitor(); host.traverse_bindings(gbv); boundbylet = gbv.boundbylet; if (host.rec) inscope.add_from(boundbylet); } void middle(Let host) { if (!host.rec) inscope.add_from(boundbylet); } void after(Let host) { inscope = oldscope.pop(); boundbylet = oldbound.pop(); }H  0޽h ? ff3  ZR(  l  C P   >  Nt8c?0:  class GBVisitor extends Visitor { Vector boundbylet = new Vector(); void before(Bind host) { boundbylet.addElement(host.var); } } H  0޽h ? ff3=   }( i$ l  C 4P  v l  C  v ]  HT3))?0   administrator: and although we would get the same result with just two travs (by duplicating binding collection), that would be inefficient., 2H  0޽h ? ff3  PH (  |  Tdp@d  <d@d  <d@r  S xP   r  S t    <y  v4Center for Software Sciences Northeastern University&54  t  c LA(C:\tmp\nu-logo2.gif6JB  s *޽h ? ff3  H(  Hl H C 4P  > l H C 2` > H H 0޽h ? ff3  QI (  l  C    5  T48c? }traversal unbound(Vector scope) = Program => traverse exp (scope) VarRef => visit checkvarref(scope) Let => Vector bnd = othertrav genbnd bindings() Vector newscope = visit concat(scope,bnd) Thunk_void reccase = Thunk { Vector traverse bindings(newscope) } Thunk_void normcase = Thunk { Vector traverse bindings(scope) } visit choosecase(reccase,normcase) traverse exp(newscope) Binding => Vector bnd = traverse bindings(scope) traverse exp(scope) Empty => visit emptybound Fun => visit addvar(scope) traverse exp(scope) visit remvar(scope)~~H  0޽h ? ff3  B:0(  r  S       N8c?pD0 nand getbnd() = Binding => Vector bnd = traverse bindings() visit addtobound(bnd) bnd Empty => visit emptybound class UBVisitor implements unbound_visitor, getbnd_visitor { ... void choosecase(Let Host, Thunk_void reccase, Thunk_void normcase) { if (host.rec) reccase.invoke(); else normacase.invoke(); } }ooH  0޽h ? ff3  H( p] Hl H C 48P   l H C 8  H H 0޽h ?   me@(  ra l  C TP   Q  T8c?pT interface getbnd_visitor { Vector emptybound(Empty host, Vector bound); void addtobound(Binding host, Vector bound); } interface unbound_visitor { void checkvarref(VarRef host, Vector scope); Vector concat(Let host,Vector a,Vector b); void addvar(Fun host,Vector scope); void remvar(Fun host,Vector scope); void choosecase(Let Host, Thunk_void reccase, Thunk_void normcase); }H  0޽h ? ff3  PL(  Ll L C P   l L C t  H L 0޽h ?   P(  Pl P C $OP  > l P C : > H P 0޽h ? ff3  `( P l  C 4P   l  C   H  0޽h ? ff3  pT(  Tl T C P   l T C t  H T 0޽h ?   ( l l  C P   l  C T  H  0޽h ? ff3  PH@(  |  Tdp@d  <d@d  <d@r  S P   r  S     <  v4Center for Software Sciences Northeastern University&54  t  c LA(C:\tmp\nu-logo2.gif6JB  s *޽h ? ff3  zD( PtN Dl D C 6P   l D C 7  B D s *޽h ?   T( +1 Tl T C 8P  > l T C '` > H T 0޽h ? ff3  P(  ݆˄ ܆ Pl P C P   l P C   H P 0޽h ?   X(  Xl X C P   l X C 4  H X 0޽h ?   z@( HX @l @ C 4P   l @ C 45  B @ s *޽h ?   \(  \l \ C 4nP   l \ C n  H \ 0޽h ?   `(  `l ` C nP   l ` C To  H ` 0޽h ?   d(  dl d C pP   l d C tp v H d 0޽h ?   h( u@  hl h C pP   l h C 4q  H h 0޽h ?   PH`(  |  Tdp@d  <d@d  <d@r  S  P   r  S t    <  v4Center for Software Sciences Northeastern University&54  t  c LA(C:\tmp\nu-logo2.gif6JB  s *޽h ? ff3  l(  ll l C qP   l l C q  H l 0޽h ? " 0 nf`t(  tR t 3 pPP   >l t C p @0  > H t 0j ? ̙33! 0 nfpx( ĥ+ xR x 3 pHP   l x C Op @0   H x 0j ? ̙33 0 nf|( (y@@r@ |R | 3 pHP   >l | C DSp @0  > H | 0j ? ̙33G 0 nf( (y@@r@ R  3 pHP   >l  C t1p @0  > H  0j ? ̙33F 0 nf( (y@@r@ R  3 pHP   >l  C 4;p @0  > H  0j ? ̙33E 0 nf( #@ R  3 pHP   >l  C $%p @0  > H  0j ? ̙33D 0 nf( #@ R  3 pHP   >l  C *p @0  > H  0j ? ̙33: 0 nf( @*7@ R  3 pHP   >l  C $(p @0  > H  0j ? ̙33= 0 nf( Ё@@N@ R  3 pHP   l  C (p @0   H  0j ? ̙33R 0 nf( <  R  3 pHP   >l  C dyp @0  > H  0j ? ̙33S 0 zr  (  X  C pHP   vr  S p @0  v H  0j ? ̙33W 0 zr (  X  C pHP   r  S p @0   H  0j ? ̙33X 0 zr (  X  C pHP   r  S $xp @0   H  0j ? ̙33Y 0 zr (  X  C pHP   r  S p @0   H  0j ? ̙33Z 0 zr0 (  X  C pHP   r  S dzp @0   H  0j ? ̙33[ 0 zrP (  X  C pHP   r  S 4p @0   H  0j ? ̙33\ 0 zrp (  X  C pHP   r  S p @0   H  0j ? ̙33rv[lss/! 1*nsoy+z3w!#@n ;(*@}C PQvUhYej1 p\wO{(QNtB^7CŰSuy<Z $M@du9c3G* gn w-Oqb -N'g,C5Im__/G}purb Oh+'0, px ,8 X d p |7A domain specific language for Traversal SpecificationkedarinCC:\Program Files\Microsoft Office\Templates\Blank Presentation.potadministratores93iMicrosoft PowerPointoso@ jiV@T@@4T X G +oM  }&& &&#TNPPp0D v & TNPP &&TNPP    f- "-- !-- "-&h`&--e2- $hh $``c1- $hh  $ ``a0- $ h h  $ ` `^/- $hh $``Z-- $hh $  ``U*- $ hh$ $ $ $'$'` `O'- $'$h$h*'* $'*-*-`'`H$- $-*h*h0-0 $-0404`-`@ - $40h0h646 $46:6:`4`8- $:6h6h<:< $:<A<A`:`/- $A<h<hBAB $ABGBG`A`&- $GBhBhHGH $GHNHN`G`{- $NHhHhNNN $NNTNT`N`q - $TNhNhTTT $TT[T[`T` j- $[ThThZ[Z $[ZaZa`[`f- $aZhZh`a`---&&&X`&-- j- $`` $ZX`X`Zq - $ZZ $TXZXZTz- $YTYT $NXTXTYNY&- $2N2NYY $HXNXN2H2.- $ H H22 $BXHXH B 7- $BB   $<XBXB<?- $<< $6X<X<6G#- $66 $0X6X60O'- $l0l0 $*X0X0l*lU*- $E*E*ll $$X*X*E$EZ-- $$$EE $X$X$^/- $ $XXa0- $ $XXc1- $ $ XX e2- $  $X X f3- $XX---&&&`X&-- j- $`RRX`X $RRq - $`MMR`R $TMTMz- $`GTGTM`M $TTGG&- $`BBG`G $BB.- $`<<B`B $<<7- $`77<`< $|7|7?- $`1|1|7`7 $F||1F1G#- $`,F,F1`1 $FF,,O'- $`&&,`, $&&U*- $`!!&`& $!!Z-- $`!`! $nn^/- $`nn` $8nn8a0- $`88` $88c1- $`  ` $ e2- $` ` $f3- $``---&&&G& - &Gy& --1x-- Times New Roman- .12 Center for Software Sciences   . .*2 'Northeastern University  .&8C7777(77??~||||<>>~?Ç?||gx> ~?ßf~??w>ww? #a΍L<~=y>yx<~>?>&C7777(77 n +@UZvy!-79GS@W_ __;___oqy-o 9_9\2###+-/2-799@BBBGGI9\_____dqq9rtqtvy9}€dɚ±__k_9>>>>>mmmmmZ>>>>>>>>>>>mmSmmZmZmm>>>>>>>>>>>ImmmmmS>>>>ZImmmmm]mSmmSmSmmSmmmm]Smmmmm>]mSmmSmZhmmmmmm>Z>mmmmZ]mSmmSm]]mBmmmmZS]mmmm5mmImmSm]]m>Zmmmm5S5mmmmBmmSmmSm]]m>5mmmmBSIImmmhmmSmmSmhZm>Immm]>mmBmmmm>mmSmmSmmSm>mmmm>1hmmm>>mmmZ>mhSmmSmmSmS>mmmSmmmmmm5Zmmm>m]]mmSmmSmSZmmm5Zmmmmmmm15mmmB>m]]mmSmmImS5mmmBSmmmmmmmmZImm]>m]]mmSmmSm]Bmm]BmmmmmmmmmmSmmm5ImZhmmSmmSm]mmm>>mmmmmmBmmmmmB>mmSSmSmmmSmmSm]>mmZ,mmmmmZS>mmmmm>]mmSmSmmmSmmIm]Zmm55mmmmmZZ>mmmmm>5mmBSmSmmmSmmSmm5mmBZmmmmBS5mmmmm1ImZ]mImmmSmmSmmBm]Zmmmm>ZZmmm]mm5]mSmmmSmmSmm]m>Bmmmm>SZmmmZ>mS]mSmmmSmmSmm55mS>mmmm5SBmmmIZm]mhmmm]mmmmm>Sm99mmm]5Sh>>mmmB5mBmmmmmmmmmmmm>mB5mmmS5SmmmZ5>mmm>IZ]]]]]]]]]]]]>B]hmmBBmmmmmmmI5]mm5]I>Zmm>5]mmmmmmmmm]>Zmm5I]]]]]]]]]]]]]Imm>,SmmmmmmImmmmmmS,ImZ>Smmmmmmmmmm]>5Bmm5>mmmmmmZZ>ZmmmmmBBmS5I>]mmmmmmmmm5S>>m]55ZmmmmmB5S5Zmmmm]5>m>ZmS]mmmmmmmmmmmmSImmmmZ>ZBZmmmS55]]>]mmmmmmmmm>]]>>9mmmmS9S5Zmmm95>>>mmmmmmmmmmI>>>5SmmZBShSB5B]mZ5I]]]]]]]]]]]]]]]]]BmmS9>S]mmmmmhZB,>]5ZB>S]mmmmmmmmmmmmmmZB5>]]I>]]]]]]]]]Z>B]]B1BS]mmmmmmmmmmmmmmmmmmmmmhZB5Zmm5Zmmmmmm]hmmhmmm5>SmmmmmmmmmmmmmmBZSZ]]]mmmmmmmm>mmmmmmmmmmh>mmmBBmmBZmmmmmmm]]]ZSZBZ5>>BZ5mm]5mmmmmmmm>hmmhmmS>I>>>Z5mm]>mmmmmmmmS]mmmhmZS>>>BSS5mm]mmmmmmmmSSmmmmmI>>5SSZ]]]mmmmmmmmmmBZmhmmmmmmmmSSmmZmm55mmmmmmm]]]]SSSSZmmmmmmmmmmmmmZB5Bmm>ImmmmmmmB]mmBBmS5BZ]mmmmmmmmmmmmmmmmmmmmmmZB5mmZ1mmmmmmm,mmm5Zm5>Z]mmmmmmmmmmmmm]Z>5BmB>mm5]mmmmmZ>mmZ5m>ZhS5>MZmmmmmZM>9Zmmm]Z]5mmmmmBBmm5]SmmmZB5BZh5ImmmmmB5ZmmmmmZ5>]mmmmS9ZBZmmmmmZ5BZ5mmm>I55SBmmmmmmB5S5Smmmmmm]>Smm5I>mmB5>Bmh59SmmmmmmZ>S5B]mmmmmmmB,]mm55mZSZh>5mB]mh>>]mmmmmmhI5SmmmmmmmmS5>mmm>]m>>mZ5mm55mmmBBmmmmmmmmhmmmmmm]>Bmmm>Imm5]mSmZ5hmmS5SmmmmmmmmmmmmBSmmmB5mmB5h]m>5mmB>mmmZ,>]mmmmmmmmZ55ZmmmIZmm55hmSmZZmm5>mmmm>Bmmmmm]>5hmmmZBmmSIm]Zm]>mmSBmmmmB5ZmmB>mmmm]5mmm9Zm]Smmmmm>BmmmmI>hBmmmmhZmmZmmSBmm>Immm1ZmmmmZ,ZZmmmmm59mmm>>mmS>mmS5mmmSZmmmmm5S5mmmmmm55mmmhImmS>mm]Zmmm>Zmmmmm>S&--iyH-- "Arial0- ..2 yA domain specific language' !1 ! !   !! !!! . .02 efor Traversal Specification!$!! '!   ! !!.--Q1-- "Arial0- .2 QJohan Ovlinger ! . .2 [ Mitchell Wand$  )."Arial0- .*2 +cNortheastern University      . .12 MDCenter for Software Sciences      .--"System-&TNPP & ՜.+,D՜.+, @     On-screen ShowoCCS, NEU, USAoMK j PArialTimes New RomanCourier Courier NewBlank Presentation.pot7A domain specific language for Traversal Specification Talk Outline Introducing the Visitor PatternCritiquing TraversalsMotivating ExampleUseless languageAST Class DiagramA small AST objectVisitor Considerations animationVisitors view of TraversalVisitors view of TraversalVisitors view of TraversalVisitors view of TraversalVisitors view of TraversalVisitors view of TraversalVisitors view of TraversalVisitors view of TraversalVisitors view of TraversalVisitors view of TraversalVisitors view of TraversalVisitors view of TraversalVisitors view of TraversalVisitors view of TraversalVisitors view of TraversalImplementation in JavaVisitor in Java Visitor ContVisitor Interface CritiqueStructural CritiqueVisitor Critique Summary Talk OutlineTraversal SpecificationFeatures of our LanguageGo Everywhere TraversalThe Go Everywhere Traversal Talk OutlineSyntax of the Language More syntax Talk Outline Our StrategyTraversal Spec for ASTInterface for AST TraversalVisitor DefinitionCompare to Visitor pattern Talk Outline Behavior influences Navigation Example: Recursive LetsIn JavaRecursive Lets in Java GBVisitorJava Critique Talk OutlineIn Traversal SpecsTraversal SpecTraversal Spec, cont!Dynamically Controlling BehaviorThe interfaces generatedThunksUses of ThunksCalling Other traversalsEncoding State in TraversalsInlaws Talk OutlineClass Graph ModificationsOther abilitiesTraversing CollectionsTraversing VariablesSuper classesSemantic IssuesType CheckingMost Precise WrapperTranslation to Java Talk Outline Conclusion  Fonts UsedDesign Template Slide TitlesK 6> _PID_GUIDAN{A61DEDC1-8A88-11D3-8363-080036BA1603}%_) badministrator  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~   Root EntrydO)PicturesCurrent UserSummaryInformation(,PowerPoint Document(MDocumentSummaryInformation8