OOP SLA99

Information about OOP SLA99

Published on June 17, 2007

Author: Moorehead

Source: authorstream.com

Content

A domain specific language for Traversal Specification:  A domain specific language for Traversal Specification Johan Ovlinger Mitchell Wand Northeastern University Problem Statement:  Problem Statement The traversal pattern is useful removing structural assumptions from programs, by separating navigational and behavioral concerns Unfortunately, the Visitor Pattern serializes the hierarchical structure of the object being traversed into a series of events. Recurring Example:  Recurring Example Compilers create object structures (ASTs) representing the expression being compiled. The visitor pattern is often used to traverse the AST. A common task is to verify that all variables have been declared before use. AST Class Diagram:  AST Class Diagram Compilers want to traverse AST to find undeclared variables Prog Let Ref Fun Exp String Bind Empty BindList A Simple, useless, Example:  A Simple, useless, Example We'll use a running example. We traverse the AST of a simple language that is only able to declare and reference variables. AST for a small program:  AST for a small program Let Bind Bind Empty Let Ref foo bar Fun Ref x Ref y foo Bind Empty grok Ref bar grok LET foo = FUN (x) {y} bar = foo IN LET grok = bar IN grok Prog Finding Undeclared Variables:  Finding Undeclared Variables Using the visitor pattern and a global traversal. (Middle is called between each part of object.) Strategy Keep a list (Vector) of variables that are in scope. Need to restore old list when exiting scopes. We'll assume no shadowing animation:  animation andlt;here we show an animation of the visitor traversing our example, and the various actions that occur.andgt; andlt;note the dependence on the order of the visitsandgt; Visitor’s view of Traversal:  Visitor’s view of Traversal Let Bind Bind Empty Let Ref foo bar Fun Ref x Ref y foo Bind Empty grok Ref bar grok Prog before Prog Variables in scope: andlt;noneandgt; Visitor’s view of Traversal:  Visitor’s view of Traversal Let Bind Bind Empty Let Ref foo bar Fun Ref x Ref y foo Bind Empty grok Ref bar grok Prog before Prog before Let Variables in scope: andlt;noneandgt; Visitor’s view of Traversal:  Visitor’s view of Traversal Let Bind Bind Empty Let Ref foo bar Fun Ref x Ref y foo Bind Empty grok Ref bar grok Prog before Prog before Let before Bind Variables in scope: andlt;noneandgt; Visitor’s view of Traversal:  Visitor’s view of Traversal Let Bind Bind Empty Let Ref foo bar Fun Ref x Ref y foo Bind Empty grok Ref bar grok Prog before Prog before Let before Bind before Fun Variables in scope: andlt;noneandgt; Visitor’s view of Traversal:  Visitor’s view of Traversal Let Bind Bind Empty Let Ref foo bar Fun Ref x Ref y foo Bind Empty grok Ref bar grok Prog before Prog before Let before Bind before Fun before Ref Variables in scope: x Visitor’s view of Traversal:  Visitor’s view of Traversal Let Bind Bind Empty Let Ref foo bar Fun Ref x Ref y foo Bind Empty grok Ref bar grok Prog before Prog before Let before Bind before Fun before Ref after Ref Variables in scope: x Visitor’s view of Traversal:  Visitor’s view of Traversal Let Bind Bind Empty Let Ref foo bar Fun Ref x Ref y foo Bind Empty grok Ref bar grok Prog before Prog before Let before Bind before Fun before Ref after Ref after Fun Variables in scope: andlt;noneandgt; Visitor’s view of Traversal:  Visitor’s view of Traversal Let Bind Bind Empty Let Ref foo bar Fun Ref x Ref y foo Bind Empty grok Ref bar grok Prog before Prog before Let before Bind before Fun before Ref after Ref after Fun middle Bind Variables in scope: andlt;noneandgt; Visitor’s view of Traversal:  Visitor’s view of Traversal Let Bind Bind Empty Let Ref foo bar Fun Ref x Ref y foo Bind Empty grok Ref bar grok Prog ... middle Bind before Bind before Ref after Ref middle Bind before Empty after Empty after Bind Variables in scope: andlt;noneandgt; Visitor’s view of Traversal:  Visitor’s view of Traversal Let Bind Bind Empty Let Ref foo bar Fun Ref x Ref y foo Bind Empty grok Ref bar grok Prog ... before Bind before Ref after Ref middle Bind before Empty after Empty after Bind after Bind Variables in scope: andlt;noneandgt; Visitor’s view of Traversal:  Visitor’s view of Traversal Let Bind Bind Empty Let Ref foo bar Fun Ref x Ref y foo Bind Empty grok Ref bar grok Prog ... before Ref after Ref middle Bind before Empty after Empty after Bind after Bind middle Let Variables in scope: foo, bar Visitor’s view of Traversal:  Visitor’s view of Traversal Let Bind Bind Empty Let Ref foo bar Fun Ref x Ref y foo Bind Empty grok Ref bar grok Prog ... middle Bind before Empty after Empty after Bind middle Let before Ref after Ref after Let Variables in scope: foo, bar, grok Visitor’s view of Traversal:  Visitor’s view of Traversal Let Bind Bind Empty Let Ref foo bar Fun Ref x Ref y foo Bind Empty grok Ref bar grok Prog ... before Empty after Empty after Bind middle Let before Ref after Ref after Let after Let Variables in scope: andlt;noneandgt; Visitor’s view of Traversal:  Visitor’s view of Traversal Let Bind Bind Empty Let Ref foo bar Fun Ref x Ref y foo Bind Empty grok Ref bar grok Prog ... after Empty after Bind middle Let before Ref after Ref after Let after Let after Prog Variables in scope: andlt;noneandgt; Visitor Analysis:  Visitor Analysis The hierarchical structure has been reduced to a series of visits Strategy: Calculate new bindings for one level and also analyze their bodies at same time Remember scope and partial list of new bindings when entering a Let (Partial) Visitor Code in Java:  (Partial) Visitor Code in Java class UDVisitor extends Visitor { Vector inscope,boundbylet; Stack oldscope, oldbound; void before(Ref host) { if (!inscope.contains(host.str)) complain(host); } void before(Bind host) { boundbylet.addElement(host.str); } void before(Fun host) { inscope.addElement(host.str); } void after(Fun host) { inscope.removeElement(host.str); } Code Cont:  Code Cont 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(); } Critique:  Critique The structure cannot be ignored -- the programmer needs to know when state needs to be saved/restored. Programmer needs to save and restore state manually. This forces an imperative style. Critique Cont:  Critique Cont The hierarchical nature of the structure iterated over is lost. Many types of behavior (capacity check) require the programmer to re-impose the structure on the series of visits. The programmer needs to have at least half an eye on the object structure anyway. Traversal Specification:  Traversal Specification Assume Local knowledge of the object structure. Non-local knowledge cannot be expressed in Traversal Spec. Promotes use of recursive style together with Visitor pattern. Traversal Spec for Example:  Traversal Spec for Example traversal unbound(Vector scope) = Program =andgt; traverse exp (scope) Ref =andgt; visit checkref(scope) Let =andgt; Vector bound = traverse bindings(scope) Vector newscope = visit concat(scope,bound) traverse exp(newscope) Binding =andgt; Vector bound = traverse bindings(scope) visit addtobound(bound) traverse exp(scope) bound Empty =andgt; visit emptybound Fun =andgt; visit addvar(scope) taverse exp(scope) visit remvar(scope) Visitor for Example:  Visitor for Example 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); } Visitor Cont:  Visitor Cont class UBVisitor implements unbound_visitor { void checkref(Ref host, Vector inscope) { if (!inscope.contains(host)) complain(host); } Vector concat(Let host,Vector a,Vector b) {...} 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); } } Critique:  Critique Traversal code is external to application. The traversal code is specialized, and easy to specialize because it is localized. Named visits, rather than before, after, which force the use of state variables or separate traversals. Features of our approach:  Features of our approach Specify which parts of an object are to be traversed, and which order Dynamic control of traversal behavior Synthesize results from sub-results Convenient iteration over collections Traversals are named for re-use Syntax of the Language:  Syntax of the Language A Traversal is a named set of TraversalEntries. Each TraversalEntry describes how to traverse objects of a certain class, using a list of Actions. The most specific TraversalEntry for an object is executed on entering it. It is executed by performing the Actions in order and returning the result. Source Code Independence:  Source Code Independence The traversal specification is separate from the definitions of the classes over which it traverses, so we are able to traverse 3-rd party libraries. Recursive Programming:  Recursive Programming The tree example, this time returning sub-results from visitor, and combining them with the visitor. New requirements on the Visitor. Type Checking Mixing Navigation and Behavior:  Mixing Navigation and Behavior We still separate the navigation and the behavior We let the traversal have local knowledge only. We have no way of expressing remote object structures. Tradeoffs:  Tradeoffs We have traded ignorance of class graph and imperative programming for local knowledge of the classgraph and functional programming. We had local knowledge before anyway. Going into Greater Detail:  Going into Greater Detail Other actions than just traversing allow us to express interesting algorithms Super classes:  Super classes The 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. Class Graph Modifications:  Class Graph Modifications For all but the most trivial modifications to the class graph, the traversal specification must be modified as well. However, the local-only nature of traversal specifications make these modifications benign. no Pitfalls Dynamically Controlling Behavior:  Dynamically Controlling Behavior Thunks encode current object and a list of actions for later invokation. 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. Example: Recursive Lets:  Example: Recursive Lets Recursive Lets add all bound vars to scope before checking binding bodies. Boolean variable indicates whether Let is recursive. Strategy: First calculate variables bound by Let Add these to scope at appropriate time during processing In Java:  In Java Separate traversal, launched from before(Let) collects bound vars, with separate visitor (because all visits are named before and after, and we don't need to collect vars when processing bound exps.) The new traversal doesn't enter bodies of Let or Bindings Recursive Lets in Java:  Recursive Lets in Java 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(); } GBVisitor:  GBVisitor class GBVisitor extends Visitor { Vector boundbylet = new Vector(); void before(Bind host) { boundbylet.addElement(host.var); } } Critique:  Critique Hardcoded traversal_bindings in visitor Traversal Spec:  Traversal Spec traversal unbound(Vector scope) = Program =andgt; traverse exp (scope) VarRef =andgt; visit checkvarref(scope) Let =andgt; 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 =andgt; Vector bnd = traverse bindings(scope) traverse exp(scope) Empty =andgt; visit emptybound Fun =andgt; visit addvar(scope) taverse exp(scope) visit remvar(scope) Traversal Spec, cont:  Traversal Spec, cont and getbnd() = Binding =andgt; Vector bnd = traverse bindings() visit addtobound(bnd) bnd Empty =andgt; 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(); } } The interfaces generated:  The interfaces generated 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); } Thunks:  Thunks Allow complicated behaviors to be programmed Traversals over cyclic structures Fixpoint iterations Searches in Binary Trees Close over (for reading only) traversal variables at definition site Can be nested, and can be returned from thunks Are typed by return value Are first class objects. Calling Other traversals:  Calling Other traversals Can just invoke a traversal in the standard way from a visitor, but this hardcodes the traversal in the visitor Othertrav allows mutually recursive traversals to be written to share the same visitor. Encoding State:  Encoding State functional langauges encode state in function names; even vs odd f.ex We have mutually recursive traversals This allows us to encode traversal state in traversal name The Alternative is to pass many thunks at each stage to visitor. Inlaws:  Inlaws use traversal to encode state Traversing Collections:  Traversing Collections We have a for-each Action which allows us to iterate over collections Impacts on visitors. Traversing Variables:  Traversing Variables We want to traverse dynamically generated objects So we are able to traverse not only parts but also results from visitors. Semantic Issues:  Semantic Issues In this section we describe the semantics of the Traversal Specifications Type Checking:  Type Checking Need simple type checking to aleviate explicit type annotation Most Precise Wrapper:  Most Precise Wrapper Can't use inheritance; not in class graph Dynamically search object Translation to Java:  Translation to Java Details Future Work:  Future Work Multiple directions of inheritance Extending traversals and extending objects traversed Compare to existing systems

Related presentations


Other presentations created by Moorehead

gis technology2
16. 11. 2007
0 views

gis technology2

customs courtesies
28. 02. 2008
0 views

customs courtesies

bfahome
04. 10. 2007
0 views

bfahome

CSW04 DDoSWormsUnderground v1
10. 12. 2007
0 views

CSW04 DDoSWormsUnderground v1

Hour8
02. 11. 2007
0 views

Hour8

Big 12 Lean Approach 2
07. 11. 2007
0 views

Big 12 Lean Approach 2

legal
14. 11. 2007
0 views

legal

B2 Vitev
15. 11. 2007
0 views

B2 Vitev

Rabies 3
20. 11. 2007
0 views

Rabies 3

Sep 2005 Hispanic Heritage
21. 11. 2007
0 views

Sep 2005 Hispanic Heritage

lecture3B
08. 11. 2007
0 views

lecture3B

HISTORY OF RUSSIA1
23. 11. 2007
0 views

HISTORY OF RUSSIA1

k 12toolkit
29. 11. 2007
0 views

k 12toolkit

08 BdM 3e WT
13. 12. 2007
0 views

08 BdM 3e WT

AHDA2005 White
25. 12. 2007
0 views

AHDA2005 White

India Since Indepencence
01. 01. 2008
0 views

India Since Indepencence

ZhangJianbo
12. 10. 2007
0 views

ZhangJianbo

CP17284
27. 12. 2007
0 views

CP17284

01Tipos de cuerpos
02. 01. 2008
0 views

01Tipos de cuerpos

Master Winter QPB
28. 11. 2007
0 views

Master Winter QPB

ENGR 4060 Italy1stmtg
01. 11. 2007
0 views

ENGR 4060 Italy1stmtg

lecture01 welcome
30. 12. 2007
0 views

lecture01 welcome

wah
07. 01. 2008
0 views

wah

handout 185951
05. 11. 2007
0 views

handout 185951

Tema 02 Tareas GQ
16. 11. 2007
0 views

Tema 02 Tareas GQ

China Presentation
11. 10. 2007
0 views

China Presentation

NR6 1
04. 03. 2008
0 views

NR6 1

Filarial Nematodes
19. 11. 2007
0 views

Filarial Nematodes

FirstProgresMeeting
01. 12. 2007
0 views

FirstProgresMeeting

403
14. 03. 2008
0 views

403

alex
30. 12. 2007
0 views

alex

Gussmagg COLD
18. 03. 2008
0 views

Gussmagg COLD

CITIgroup
21. 03. 2008
0 views

CITIgroup

ExploreFair
26. 03. 2008
0 views

ExploreFair

mark robertson blackwell
27. 03. 2008
0 views

mark robertson blackwell

2007 MacCracken
07. 04. 2008
0 views

2007 MacCracken

lect17
01. 01. 2008
0 views

lect17

7th October presentation 1
24. 02. 2008
0 views

7th October presentation 1

7274117
30. 03. 2008
0 views

7274117

WCU07 SlipsTrips Falls
04. 01. 2008
0 views

WCU07 SlipsTrips Falls

alena
09. 04. 2008
0 views

alena

history lecture2
10. 04. 2008
0 views

history lecture2

CYDE 3
13. 04. 2008
0 views

CYDE 3

El Codigo da Vinci
05. 01. 2008
0 views

El Codigo da Vinci

DECA Prep for Competitive Events
22. 04. 2008
0 views

DECA Prep for Competitive Events

JSC Energizer 12 Days of Fitness
05. 12. 2007
0 views

JSC Energizer 12 Days of Fitness

NPAPSP Analysis
20. 11. 2007
0 views

NPAPSP Analysis

Slides3
04. 01. 2008
0 views

Slides3

science
10. 10. 2007
0 views

science

AFD 070926 096
05. 11. 2007
0 views

AFD 070926 096

SLNspring2003
27. 09. 2007
0 views

SLNspring2003

XwalkProgress
12. 12. 2007
0 views

XwalkProgress

issues to watch 2006
10. 10. 2007
0 views

issues to watch 2006

pdhpe in cogs 07
24. 11. 2007
0 views

pdhpe in cogs 07

Novenato StEdmund
17. 06. 2007
0 views

Novenato StEdmund

Nash1
17. 06. 2007
0 views

Nash1

nanwise august06
17. 06. 2007
0 views

nanwise august06

names yalit
17. 06. 2007
0 views

names yalit

names rowling
17. 06. 2007
0 views

names rowling

names ethnic
17. 06. 2007
0 views

names ethnic

Nairne MC CH07
17. 06. 2007
0 views

Nairne MC CH07

MMR v2004PPT
17. 06. 2007
0 views

MMR v2004PPT

mitacf lg 20060929 vision
17. 06. 2007
0 views

mitacf lg 20060929 vision

oef 9
17. 06. 2007
0 views

oef 9

oef 8 opl
17. 06. 2007
0 views

oef 8 opl

oef 7 opl
17. 06. 2007
0 views

oef 7 opl

oef 6 opl
17. 06. 2007
0 views

oef 6 opl

oef 5 opl
17. 06. 2007
0 views

oef 5 opl

oef 3
17. 06. 2007
0 views

oef 3

oef 2
17. 06. 2007
0 views

oef 2

frederic
05. 11. 2007
0 views

frederic

pasher orgs and fun
17. 06. 2007
0 views

pasher orgs and fun

parody 000
17. 06. 2007
0 views

parody 000

Orientation Leaders 2007
17. 06. 2007
0 views

Orientation Leaders 2007

off train
17. 06. 2007
0 views

off train

pbr04 forecasts
17. 06. 2007
0 views

pbr04 forecasts

oef 8
17. 06. 2007
0 views

oef 8

oef 7
17. 06. 2007
0 views

oef 7

oef 6
17. 06. 2007
0 views

oef 6

oef 5
17. 06. 2007
0 views

oef 5

oef 4 opl
17. 06. 2007
0 views

oef 4 opl

oef 4
17. 06. 2007
0 views

oef 4

oef 3 opl
17. 06. 2007
0 views

oef 3 opl

oef 1 opl
17. 06. 2007
0 views

oef 1 opl

oef 1
17. 06. 2007
0 views

oef 1

6 APO
28. 12. 2007
0 views

6 APO

eva dimmock stim4 wok fields 04
06. 12. 2007
0 views

eva dimmock stim4 wok fields 04

soportes ago06
16. 11. 2007
0 views

soportes ago06

bORrB
03. 01. 2008
0 views

bORrB