author = "Karl J. Lieberherr and Jeffrey Palm and Ravi Sundaram",
title = {"Expressiveness and Complexity of Crosscut Languages"},
booktitle = "Proceedings of the 4th workshop on Foundations of Aspect-Oriented Languages (FOAL 2005)",
month = mar,
year = 2005

AUTHOR = "Karl J. Lieberherr and Jeffrey Palm and Ravi Sundaram",
TITLE = "Expressiveness and Complexity of Crosscut Languages",
INSTITUTION = "Northeastern University",
YEAR = 2004,
MONTH = "September",
NUMBER = "NU-CCIS-04-10"

Paper .

Errata: p2 = !x1 | x2 in 3.1 in the example that is translated to AspectJ.
In the AspectJ example, the class Target should be renamed to T to be consistent with Figure 1.
There should be a note that !x1 in Figure 1 is represented as Nx1 in the AspectJ program.

Notes by Karl

For designing aspect interfaces for adaptive methods,
the following algorithmic problem needs to be solved.
When designing strategies for a given interface class graph,
we would like to have a design tool that tells us for a given
strategy s which other strategies are equivalent to it.
For example, we might have the interface class graph:

Program = List(ClassDef).
ClassDef = ClassName List(Part).
Part = PartName ClassName.

The strategy s = "from Program to PartName" is equivalent to:
s1 = from Program via ClassDef to PartName
s2 = from Program via Part to PartName
s3 = from Program via ClassDef via Part to PartName

We also want that:
"from Program via ClassDef" is covered by s = s1.
"from Program via Part" is covered by s = s2.
"from Program via ClassDef via Part" is covered by s = s3.

This means that "from Program to PartName" will reach all

It is useful to be able to write very simple strategies and then to
have all equivalent ones generated. The programmer can then choose the
most appropriate strategy. For example, the programmer might select:
s1 = from Program via ClassDef to PartName
as the most suitable strategy for a particular task.
But we also remember that s = s1 = s2 = s3.
These constraints must hold in all implementations of the 
aspect interface.

s1 covers s2 is defined by:
Exists prefix PR: PR(PathSet[G](s2)) = PathSet[G](s1)

PR is a prefix operator on sets of paths.

Definition: Prefix 
(G,s1) is a prefix of (G,s2)
if for every path p in PathSet[G](s2)
there is a prefix in PathSet[G](s1).

Are both strategy equivalence constraints and covers constraints needed or 
are strategy equivalence constraints enough?
It is important to notice that "from Program via ClassDef to Part" =
"from Program to Part" is the same as saying that
"from Program to Part"  covers
"from Program to ClassDef". The latter one says that we reach 
ClassDef when we go to Part. 
The former says that as we go from Program to Part, we always go through ClassDef. 
Can we show that s1 covers s2 iff Exists s3 so that join(s2,s3) = s1??

How do we produce all strategies equivalent to a given one for a particular class graph?
Given strategy: from A to B. Create the traversal graph. Is  there a node  X besides
A and B in the traversal graph so that all paths from A to B lead through X? 
Is "from A to B" = "from A via X to B". Yes, by construction.

What is the connection between:

ForAll p1 in PathSet[G](s1) Exists p2 in PathSet[G](s2): prefix(p1,p2)
ForAll p2 in PathSet[G](s2) Exists p1 in PathSet[G](s1): prefix(p1,p2)
(prefix(p1,p2) = p1 is a prefix of p2)

s1 covers s2 is defined by:
Exists prefix PR: PR(PathSet[G](s2)) = PathSet[G](s1)

Definition: Completion 
(G,s2) is a completion of (G,s1)
if for every path p in the path set
of (G,s1) there is a completion in the path set of (G,s2).

What is the complexity of the Completion decision problem? Given G, s1 and s2: Is (G,s2) a completion of (G,s1)?

What is the complexity of the AllCompletion problem:
Given G and s1, list all strategies s2 so that
(G,s2) a completion of (G,s1).

Point 1:
The paper currently only talks about selector languages for 
general purpose aspect languages and not for selector languages
used by concern-specific aspect languages.

Point 2:
Every abstraction should be motivated by at least three examples:
currently we only have SD and SAJ.

Here is the third example:
We use the selector language in Crista's RIDL. We call it
SRIDL. It has the syntax:

S : A bypass {l1, ... ,lk} |
    A only   {l1, ... ,lk} |
    S1 & S2 |

The meaning of SRIDL is defined in two steps:

1. First we define a reduced class graph that has the forbidden edges removed.
2. We compute all paths from source to target.

What is the complexity of the Satisfiability problem etc. for SRIDL?
How does the expressiveness of SRIDL compare to SAJ and SD?


The next steps will be to explore connections to the XPath work.
Some of the XPath work studies the implication problem (Select-Impl)
without a meta graph. Use the idea of learning the meta graph
from examples to connect to the world where the meta graph is present.
This might unify many of the proofs in the XPath community.

As shown in the paper, some AspectJ pointcuts can be 
expressed in a lower-complexity fragment of SD.
When we translate from a polynomial sublanguage of SD
to SAJ, we end up in an exponential sublanguage of SAJ.
So let's define: A language X with P-time algorithm is more expressive
than a language Y
if there is no translation to Y so that the subset used in 
Y is P-time. SD is more expressive than SAJ because Select-SAT/-/SD
is polynomial but there is no polynomial subset of SAJ
that can express the same. This needs to be polished a bit.

Here is a try:
We have X with polynomial algorithm for some problem PP.
We have Y with a set of sublanguages SS of Y
(based on subsets of operators) and with Y least as expressive as X.
X is better (or "efficiently more expressive for PP" or "more powerful for PP"
or "has an efficient niche for PP with respect to")  than Y, 
if for all operator sublanguages of Y that contain X problem PP is NP-complete.

This sounds best:
X is efficiently more expressive for problem PP than Y,
if X is polynomial for PP and 
if for all operator sublanguages of Y that contain X problem PP is NP-complete.

Note: This is a practically useful notion because tool implementors
have to implement the operators in a general way.

-/SD with bypassing is efficiently more expressive for PP than SAJ
where PP ={Select-Sat, Select-First, etc.}.

Proof: To simulate [A,B],| and join, we need n(l), flow, | and & for which 
Select-Sat etc. is NP-complete.

Is some sublanguage of SAJ efficiently more expressive for Select-Sat than SD?

We should add a new language SXP that contains the essence
of XPath and see how our results carry over or not.

Could start with:

SD + [A.k.B] + [A,B [S]] where B is source of strategy S.
S must select at least one node.

We should add a datalog-based selector language SDL that uses
a logic program to express the pointcuts. Would have polynomial
time decision procedure. Is datalog powerful enough?

Also analyze:
SR ::= A | any | D1.D2 | D1||D2 | D1&&D2 | (D) | !D
This is John Lamping's regular expression language from 1994!
A is a node name. any is any node name.
. is concatenation.
Does not allow "from A to B". Would have:
A.any.any.any.B (3 intermediate nodes).

SG ::= strategy graphs | D1 && D2 | (D) | !D

Add: Change analysis problem

Given selector language expressions p1,p2 and p3,
is there a change in the scope of p3 when we move from p1 to p2.

Given a selector expression p

Add: Refactoring problem

Given instance tree pairs (i1b,i1s), (i2b,i2s), ... , (inb,ins)
where iks is a subtree of ikb for k = 1 ... n with root(iks) = root(ikb) and
ikb for k = 1... n are
instances of the same meta graph G, find a selector expression
s satisfying property X so that s applied to ikb yields iks for k = 1 to n.
X = minimum size.

Strongly connected components:
How does it help to compute the strongly connected component graph
of the meta graph. It helps if the strongly connected component graph
is much smaller than the meta graph.

We use the following symbols:

meta graph G
instance graph I
selector expression S, D, p

Conjecture by Pengcheng:
When we add filtering to SD, the complexity does not increase 
for the problems discussed in the paper.
D1[[D2]], where Target(D1) = Source(D2), selects the target(D1)-objects
so that D2 finds a Target(D2) object. Idea: compute D1.D2. But this
could be inefficient because there are many paths to Target(D1) but only a few
lead further to Target(D2).

Neven and Schwentick: XPath containment in the presence of ... DTD ...
They say: containment of XP(DTD,/,//,|) is hard for EXPTIME.
XP(DTD,/,//,|) is basically SD. Who is right? We or they?
They also say that containment of XP(DTD,//,[] (filtering)) is CONP-hard.
XP(DTD,//,[]) is basically filtering added to straight-line strategies.
Who is right? Pengcheng or they?

Intersection in XPath: