Feedback is appreciated.

Paper (in several formats).

Notes by Karl

Definition of negation for strategies:

D  is a strategy 
  with sources S and targets T satisfying constraint C =
!D is a strategy D1 || D2 where
  D1 = with sources S and targets T satisfying constraint !C 
  D2 = with sources S and targets !T

                     class graph -              object graph
class graph for pl - object graphs = programs - execution trees

program defines 	meta information about execution trees
class graph defines 	meta information about object trees

static call graph : a simple abstraction of the program

cflow(call(A)) ||  cflow(call(B))
&&
!cflow(call(A)) ||  cflow(call(B))
&&
cflow(call(A)) ||  !cflow(call(B))
&&
!cflow(call(A)) ||  !cflow(call(B))

(|| binds stronger)
is this satisfiable?
is it satisfiable when we delete the last clause?

On page 493 of my book, there is the notion of 
when a set of strategies is contradictory.
When is a set of pcds contradictory?

About the pcd to strategy reduction:

Prove that if pcd is satisfiable then the strategy is satisfiable.

What is the notion of satisfiability?

New operator for strategies: &&

[A,B,C] && [A',C'] = [A&&A',B,C&&C']
(intersection of source and target sets)

The resulting strategy is of the form:
A via B bypassing edgesB via C bypassing edgesC 

!cflow(cflow(p1)) = !cflow(p1)
! nodes(from(nodes(from P1 to *)) to *)
=
! nodes(from P1 to *)

nodes(from(nodes(from P1 to *)) to *)
=
nodes(from P1 to *)
for all class graphs.

nodes(from (P1||P2) to *) =
nodes(from P1 to *) || nodes(from P2 to *)
for all class graphs.

nodes(from P1 to *) && nodes(from P2 to *) =
nodes(from (P1 && nodes(from P2 to *)) to *) || 
nodes(from (P2 && nodes(from P1 to *)) to *) 
for all class graphs.

cflow(P1) = join(str(P1),target(str(P1) to *)

cflow(P1) = set of all nodes reachable from some node in P1
(nodes in P1 must be reachable from a distinguished node Main)

====

We must make a convincing argument how the traversal graph construction
is different from "standard" automata-theoretic constructions
that show that the regular languages are closed under the regular operations:
union, concatenation, star and intersection.

Why is this wrong:
We translate a pcd to a NDFA and use it to recognize 
which join points belong to the pcd.

Or: We translate a pcd to a NDFA N1, translate the static
program structure to an NDFA N2, compute the intersection
of N1 and N2 to regognize which join points
belong to the pcd.

What are the differences between automata and traversal graphs?
Traversal graphs are about selecting a subtree.
Automata are about selecting a set of strings.


Automata theory			Traversal theory
alphabet S			class graph
defines sentences S*		defines object graphs
automaton			strategy
defines subset of sentences	selects subgraph for each object graph
decide: poly			compute: poly
				decide for node: no, maybe: poly

				Traversal graph gives the maybe space
				constant-time one-step decision

In terms of automata: may this step still lead to an acceptance? 
Not just one sentence but a sequence of sentences forming a tree.

Other view:
Automata theory			Graph theory
alphabet S			set of nodes S
defines sentences S*		defines node sequences S*
automaton			graph (add edges), source and target
defines subset of sentences	selects subset of node sequences: path set

Can we reduce traversal theory to automata theory?
Two step application:
Class graph + strategy = path set = regular set = traversal graph
path set + object graph = subgraph of object graph


Connections:
automaton			class graph
automaton			strategy graph
intersection			traversal graph
regular set			from A to B
transitions			path set

automaton 			traversal graph
automaton			object graph
intersection			subgraph selected?

Abstract form of problem solved:
Given is a class graph G and a strategy S. 
Consider DFS traversal of object graph conforming to G. 
Decide for every node in
the traversal whether it is out of scope or in scope.
If a node is out of scope, no processing is needed for successors.
If a node is in scope, need to update token set upon transition to
successors. When returning need to go back to old token set.
Need to push and pop token sets as we go through object graph?

Generic Terminology	AspectJ			Demeter
Selector		Pointcut designator 	Strategy
Graph			Static call graph	Class Graph
Tree			Dynamic call tree	Object Graph

The purpose of a selector (pointcut designator) is to select a set of nodes in a tree and to expose appropriate contextual information at each node. The selector is expressed in terms of a graph which defines a family of "similar" trees (the instances of the graph). Our approach for defining a set of nodes is as follows: 1. We use primitives to define "connected" sets of nodes by defining for each tree a subtree. This is accomplished by strategy graphs and the intersection operator on strategy graphs. 2. We provide a Nodes operator to select all nodes from a tree. 3. We provide predicates that select subsets of nodes based on attributes of the nodes. 4. we provide the standard set operators on sets of nodes.

Examples:
Nodes(from Main via B to C) && Nodes(name = C)

SelectorLanguage = List(Def).
Def =  Variable  Body.
Body : StrategyBody | NodeSubsetBody.
...

The contextual information that is available:
1. nodes back up to the root of the tree.
2. with respect to the traversal policy of the tree (e.g., depth first)
   a) the most recently visited node of a particular kind (the kinds are 
   programmer defined, e.g., calls to a particular method on objects
   of a particular class).
   b) The contextual information may be programmer defined by having the programmer
   collect information in a "visitor" object.

Related work: http://citeseer.nj.nec.com/509011.html

Represent UML design in XML using XMI. Refer to sets of methods, parameters, attributes using XPath. Translate XPath to AspectJ.

Translate pcds to XPath instead of translating to selector specifications (including strategies).

The Monadic Second-order Logic on finite binary trees (M2L) is an interesting logic to define sets of trees. Each formula in M2L denotes a set of trees which is a regular tree set. But the M2L representation may be non-elementary more succinct than the corresponding automaton.

(in a different space, strategies play a similar role: they are a succinct representation fo a regular set of paths.)

M2L is decidable; yet most extensions lead to an undecidable logic.

See the following TAPOS and OOPSLA paper: http://citeseer.nj.nec.com/cache/papers/cs/280/ftp:zSzzSzftp.ccs.neu.eduzSzpubzSzpeoplezSzlieberzSztaposzSzrev2.pdf/klarlund97formal.pdf

Since this paper a lot of progress has been made:

http://citeseer.nj.nec.com/327523.html

http://citeseer.nj.nec.com/cache/papers/cs/16299/http:zSzzSzwww.brics.dkzSz~amoellerzSzpaperszSzsecretszSzpaper.pdf/klarlund00mona.pdf

A Domain-Specific Language for Regular Sets of Strings and Trees (1997) Abstract: We propose a new high-level programming notation, called FIDO, that we have designed to concisely express regular sets of strings or trees. In particular, it can be viewed as a domain-specific language for the expression of finite-state automata on large alphabets (of sometimes astronomical size). FIDO is based on a combination of mathematical logic and programming language concepts. http://citeseer.nj.nec.com/cache/papers/cs/8330/http:zSzzSzwww.usenix.orgzSzpublicationszSzlibraryzSzproceedingszSzdsl97zSzfull_paperszSzklarlundzSzklarlund.pdf/klarlund97domainspecific.pdf

@article{ klarlund99domainspecific,
author = "Nils Klarlund and Michael I. Schwartzbach",
title = "A Domain-Specific Language for Regular Sets of Strings and Trees",
journal = "Software Engineering",
volume = "25",
number = "3",
pages = "378--386",
year = "1999",
url = "citeseer.nj.nec.com/klarlund97domainspecific.html" }