OOP SLA99

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