\newcommand{\comment}[1]{}

\documentclass{sigplanconf}

\usepackage{url}
\usepackage{multicol}
\usepackage{comment}
\usepackage{listings}
\usepackage{citesort}
\usepackage{epsfig}
\lstloadlanguages{[AspectJ]Java}
\lstset{
    basicstyle=\small,
    columns=fullflexible,
    numberstyle=\tiny,
    numbers=left,
    numberstyle=\tiny,
    stepnumber=1,
    numbersep=5pt,
    language=[AspectJ]Java
}

\newcommand{\llbracket}{[\!\![}
\newcommand{\rrbracket}{]\!\!]}

% Keywords for *2dl generated by
% cat *str | grep 2dl | perl -pe 's/\s|\(/\n/g' | grep 2dl | sort | uniq | fmt | perl -nle 's/ /,/g; print "${s}$_,"; $s="    "'
% in dlpcs/transformation/aj-embed.
%
% List of metavariables obtained by running
% cat metaAJ-variables.sdf  | grep \" | cut -f2 -d\" | perl -pe 's/^(.*)$/$1\n${1}0\n${1}1\n${1}2/g' | fmt | tr ' ' ',' | perl -pe 's/(.)$/$1,/'
% in the same place. Those might have to be updated if rules are rewritten.
\lstdefinelanguage{rewriterules}
 {morekeywords={aj2dl,classnamepat2dl,cmodpat2dl,constrmembpat2dl,exactnamepat2dl,
    expat2dl,fieldmembpat2dl,fieldpat2dl,fmodpat2dl,formals2dl,methconstrpat2dl,
    methmembpat2dl,mmodpat2dl,namepat2dl,pnamepat2dl,potnamepat2dl,snamepat2dl,
    throws2dl,typepat2dl,wcnamepat2dl},
  morekeywords={[2]pc,pc0,pc1,pc2,pcname,pcname0,pcname1,pcname2,pcargspat,pcargspat0,
    pcargspat1,pcargspat2,mmodpat,mmodpat0,mmodpat1,mmodpat2,methmod,methmod0,
    methmod1,methmod2,methmods,methmods0,methmods1,methmods2,cmodpat,cmodpat0,
    cmodpat1,cmodpat2,constrmod,constrmod0,constrmod1,constrmod2,constrmods,
    constrmods0,constrmods1,constrmods2,fmodpat,fmodpat0,fmodpat1,fmodpat2,
    fieldmod,fieldmod0,fieldmod1,fieldmod2,fieldmods,fieldmods0,fieldmods1,
    fieldmods2,typepat,typepat0,typepat1,typepat2,membpat,membpat0,membpat1,
    membpat2,constrmembpat,constrmembpat0,constrmembpat1,constrmembpat2,
    constrpat,constrpat0,constrpat1,constrpat2,fieldpat,fieldpat0,fieldpat1,
    fieldpat2,methconstrpat,methconstrpat0,methconstrpat1,methconstrpat2,
    snamepat,snamepat0,snamepat1,snamepat2,namepat,namepat0,namepat1,namepat2,
    classnamepat,classnamepat0,classnamepat1,classnamepat2,constrnamepat,
    constrnamepat0,constrnamepat1,constrnamepat2,formalspat,formalspat0,
    formalspat1,formalspat2,formalpat,formalpat0,formalpat1,formalpat2,expat,
    expat0,expat1,expat2,throwspat,throwspat0,throwspat1,throwspat2,pred,pred0,
    pred1,pred2,str,str0,str1,str2,predname,predname0,predname1,predname2},
  morekeywords={[3]tx,where,NOT,not},
  keywordstyle=\textbf,
  keywordstyle={[2]\textit},
  keywordstyle={[3]\textbf},
%%  basicstyle=\tiny,
  morecomment=[s]{<}{>},
  columns=flexible,
  commentstyle=\textit,
  literate={->}{$\rightarrow$}2 {=>}{$\Rightarrow$}2 {|[}{$\llbracket$}1 {]|}{$\rrbracket$}1 {tx: }{\emptybox}0 {!=}{$\neq$}1 {:-}{$\leftarrow$}2,
  alsodigit={-},
  alsoletter={.}
}

% get more figures/text on a page
\def\topfraction{.95}
\def\bottomfraction{.95}
\def\dbltopfraction{.95}
\def\dblbottomfraction{.95}
\setcounter{totalnumber}{5}
\def\dbltextfraction{.05}
\def\dblfloatpagefraction{.95}
\def\textfraction{.05}
\def\floatpagefraction{.95}
% less space between
\def\floatsep{.05in}
\def\textfloatsep{.05in}
\def\intextsep{.05in}

\def\mytitle{Semantics of Static Pointcuts in AspectJ}
\title{\mytitle}
% \subtitle{Subtitle Text, if any}

\authorinfo{Pavel Avgustinov \and
            Elnar Hajiyev \and 
            Neil Ongkingco\\ \and 
            Oege de Moor \and
            Damien Sereni \and
            Julian Tibble \and
            Mathieu Verbaere}
           {Programming Tools Group, Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford OX1 3QD, UK}
           {\{pavel.avgustinov,elnar.hajiyev,neil.ongkingco,oege.de.moor,damien.sereni,julian.tibble,mathieu.verbaere\}@comlab.ox.ac.uk}

% \authorinfo{Name2\and Name3}
%           {Affiliation2/3}
%           {Email2/3}

\def\myack{This work was supported by EPSRC}

\begin{document}


\conferenceinfo{POPL'07} {January 17--19, 2007, Nice, France.}
\copyrightyear{2007}
\copyrightdata{1-59593-575-4/07/0001} 
\maketitle


\begin{abstract}
In aspect-oriented programming, one can intercept events by writing
patterns called {\em pointcuts}. The pointcut language of the most
popular aspect-oriented programming language, AspectJ, allows the
expression of highly complex properties of the static program 
structure. 

We present the first rigorous semantics of the AspectJ pointcut
language, by translating static patterns into safe ({\em i.e.}
range-restricted and stratified) Datalog queries. 
Safe Datalog is a logic language like Prolog, but it does not have 
data structures; consequently
it has a straightforward least fixpoint semantics and all 
queries terminate.

The translation from pointcuts to safe Datalog consists of a set
of simple conditional rewrite rules, implemented using the
Stratego system. The resulting queries are themselves executable
with the CodeQuest system. We present experiments indicating that 
direct execution of our semantics is not prohibitively expensive.
\end{abstract}


\category{F.3}{Logics and Meanings of Programs}{Semantics of Programming Languages}

\terms
Design, Experimentation, Languages

\keywords
Aspect-oriented programming, pointcuts, logic programming, Datalog, term rewriting


%%% SECTIONS, one per file
\section{Introduction \label{INTRODUCTION}}
% what is aop
Aspect-oriented programming enables one to intercept events at
runtime by writing patterns called {\em pointcuts}. 
The intercepted events are named {\em joinpoints}.
Whenever
a pointcut matches a joinpoint, extra code (called {\em advice})
is run. The most popular language that embodies these ideas
is AspectJ, an extension of Java \cite{kiczales01}; there is also
a modern aspect-oriented version of C\#, named Eos-U \cite{rajan05}.
Typical applications include runtime verification
of system-wide invariants, the implementation of authentication
and authorisation mechanisms, as well as 
various caching and pooling strategies \cite{laddad03}.

% formal semantics
With the growing popularity of aspect-orientation, numerous
researchers have started to investigate the semantics
of aspect-oriented languages 
({\em e.g.} \cite{aldrich05,walker03,dantas05,dantas06,tucker03,wang06,andrews01,laemmel02,wand04c,bruns04,jagadeesan03,jagadeesan06,hui06,wang06b}).
All such studies have focused on the operational semantics of advice,
taking a very simple pointcut language. For instance, in
\cite{walker03}, the core language identifies program points for
instrumentation through explicit labels, and pointcuts are sets of such labels.

% complexity of pointcut language
Yet in AspectJ itself, the pointcut language is very complex, 
allowing the programmer to capture intricate properties related
to the static structure of the program. This complexity
is a continuing source of serious bugs in AspectJ compilers (cf. the discussion in Section \ref{STATICSEMANTICS}).
Nevertheless the AspectJ user community continues to make
requests for a yet more expressive pattern language,
only exacerbating the problem. 

% what this paper is about: static pointcuts
In this paper, we bridge the gap between existing operational
semantics of advice and current practice, by giving 
a complete semantics of the static matching of AspectJ 1.2.1
pointcuts. In particular, our semantics can be used to
reduce complex pointcuts to sets of labels that refer to
source locations, and then the dynamic part of the story is told
by an operational semantics in the style of \cite{walker03}.

% our semantics = Datalog + rewriting 
Our semantics consists of a translation from AspectJ pointcuts
into Datalog queries over relations defined in the object
program. Datalog is a logic query language that originated
in the theoretical database community \cite{gallaire78}. 
We restrict ourselves
to the {\em safe} fragment that has a straightforward least-fixpoint
semantics; furthermore all safe Datalog queries terminate. 
The translation from pointcuts to Datalog takes the
form of about 90 conditional rewrite rules. The full definition
is thus quite short and elegant. It is available for download as
an accompanying technical report \cite{pointcutsemantics06abc}. 

% putting the semantics to work
This semantics is put to work in three ways. First, it serves
as a crisp definition to discuss tricky points in the language
design, and has enabled us to lay bare several long-standing
bugs in AspectJ implementations. Second, the semantics is executable,
and we present comparative experiments with an industrial-strength
compiler to show the costs of directly executing the semantics are
not prohibitive. Finally, our semantics provides a framework 
for the design and discussion of further language extensions 
that the AspectJ user community is clamouring for
\cite{barzilay04,bodkin06,burke04,hugunin03}. 

% absence of previous formal semantics
It is not possible
to prove a correspondence result with previous semantics, as the
only existing definition of AspectJ is an informal description on the
web \cite{aspectjhome}. However, our testing with respect to the standard
implementation, and subsequent discussion of discrepancies with 
the AspectJ designers,
provide ample confidence that our formal semantics captures the
intended meaning.

% previous work on logic pointcuts
Many previous works have suggested the use of logic programming
for writing pointcuts in aspect-oriented programming, but
invariably they use Prolog
\cite{volder99,gybels03,kw04}. In the present setting, that would
be inappropriate because the semantics of Prolog itself is
quite complex, even with tabled resolution to 
give better termination behaviour. 
Furthermore, we tried to run our experiments with (a tabled variant of)
Prolog, but found that execution times prohibit its application
in practice. 


In summary, this paper makes the following contributions:
\begin{itemize}
 \item The identification of safe Datalog as a suitable intermediate
       form for pointcuts in aspect-oriented programming.
 \item The use of term rewriting to reduce complex pattern-based
       pointcuts to Datalog queries.
 \item The first rigorous semantics of the AspectJ 1.2.1 pointcut language.
 \item Experimental evidence that it is feasible to directly execute
       our semantics, on AspectJ programs of up to 100KSLOC.
\end{itemize}


The structure of the paper is as follows. In Section \ref{ASPECTJ},
we provide a brief introduction to AspectJ, focussing on the
pointcut language. We then proceed to discuss existing semantics for
the aspect-oriented paradigm in Section \ref{AOPSEMANTICS}. In particular,
we enunciate the difference between {\em static} and {\em dynamic} 
pointcuts. Dynamic pointcuts refer to runtime properties such as
the call stack --- they are matched at runtime, and their semantics is
by now well understood (\emph{e.g.} \cite{walker03,wand04c}). By contrast, static pointcuts are matched
against the static structure of the program, and they are the focus
of the present paper. Next, we provide a brief introduction to safe
Datalog in Section \ref{DATALOG}.  We then explain informally how
static pointcuts can be mapped to Datalog queries in Section \ref{QUERIES}.
The heart of the paper is Section \ref{STATICSEMANTICS}, which shows
how a simple set of rewrite rules suffices to translate AspectJ's
static pointcuts into Datalog. Rather than presenting a shallow overview
of the complete semantics, we detail the most complex issues in
AspectJ's design where a rigorous approach is indispensable. 
In Section \ref{EXPERIMENTS}\ it
is demonstrated that this semantics directly leads to a viable 
implementation strategy. We then briefly speculate on the use
of Datalog to directly express new forms of pointcut in Section
\ref{DATALOGPOINTCUTS}. A brief roadmap of related work is provided
in Section \ref{RELATED} before concluding in Section \ref{CONCLUSION}.


\section{AspectJ pointcuts \label{ASPECTJ}}
AspectJ is a variant of Java, extended
with aspect-oriented features \cite{kiczales01}. 
These features allow a 
programmer to write a single piece of code that consistently
affects the behaviour of multiple modules in a program.

The novel contribution of aspect-oriented languages, which was
not present in previous work on class composition
(\emph{e.g.} \cite{tarr02}), is known as ``pointcut and advice''.
A \emph{pointcut} is a predicate over events that occur during
the execution of a program. These events (called \emph{joinpoints})
are composite ---
they have duration and may be nested.  A piece of advice
is a block of code that is executed when a pointcut matches
a joinpoint.  Advice can be run before the matched joinpoint,
after it, or instead of  it.

We will introduce the pointcut notation of AspectJ 
with the aid of an example, taken from the textbook by
Laddad \cite{laddad03}. The task in hand is to
automatically enforce the following requirement
of the Swing GUI library:
\begin{quotation}
``Once a component is visible, the event-dispatching
thread (sometimes called the AWT thread) is the only
thread that can safely access or update the state of
the realized component. The rule exempts certain methods,
allowing them to be safely called from any thread.''
\cite{laddad03}
\end{quotation}
Laddad's solution works by intercepting calls to methods
that would update the state of a component from the wrong
thread, and then queueing them for execution in the
event-dispatching thread. The pointcut \lstinline!routedMethods!,
shown in Figure~\ref{fg:awt-ex-pcs}, matches calls to
just those methods that would violate the invariant.
\begin{figure}
%listings package fails to parse this properly, hence include manual highlight
\lstset{emphstyle={\bf},emph={pointcut}}
%
\begin{lstlisting}
pointcut viewMethodCalls() :
    call(* javax..JComponent+.*(..));

pointcut modelMethodCalls() :
    call(* javax..*Model+.*(..))
 || call(* javax.swing.text.Document+.*(..));

pointcut uiMethodCalls() :
    viewMethodCalls() || modelMethodCalls();

pointcut threadSafeCalls() :
    call(void JComponent.revalidate())
 || call(void JComponent.repaint(..))
 || call(void add*Listener(EventListener))
 || call(void remove*Listener(EventListener));

pointcut excludedJoinpoints() :
    threadSafeCalls()
 || within(SwingThreadSafetyAspect)
 || if(EventQueue.isDispatchThread());

pointcut routedMethods() :
    uiMethodCalls() && !excludedJoinpoints();
\end{lstlisting}
\caption{Pointcuts for Swing thread-safety enforcement}
\label{fg:awt-ex-pcs}
\end{figure}
It relies on five other programmer-defined named pointcuts --- each one
is defined in terms of pointcut primitives, using the Boolean connectives
\emph{and} (\lstinline!&&!), \emph{or} (\lstinline!||!), and \emph{not}
(\lstinline!!!).  Three built-in primitives are also used:

\begin{description}
\item[if] takes a boolean-valued Java expression
          as an argument; it matches a joinpoint if the expression
	  evaluates to true before (or after, depending on the
	  kind of advice) the joinpoint occurs.
\item[within] takes a pattern ranging over types as an argument;
              it matches any joinpoint that was caused by executing
              code lexically within a type that matches the pattern.
\item[call] also takes a pattern as an argument, which ranges
            over method or constructor signatures; it matches any
	    call-joinpoint to a method or constructor that has a signature
	    matching the pattern.
\end{description}

There are several wildcards used in AspectJ patterns. The first
is~\lstinline{*}: it matches any series of characters that
can appear in a Java identifier (not `.'). So, for example,
Line 14 of Figure~\ref{fg:awt-ex-pcs} matches call-joinpoints to
any method with a name that starts with ``add'', ends with ``Listener'',
and takes a single argument of type \lstinline!EventListener!.

A \lstinline{+} wildcard can only appear in a pattern that ranges
over types. It means `match any subtype'. It appears in Line 2
of Figure~\ref{fg:awt-ex-pcs}, which matches any call to a method
on a type matching the pattern \lstinline!javax..JComponent! or
any subtype of such a type.

The wildcard \lstinline{..} matches any sequence of full-stops and Java
identifiers that begins and ends with a full-stop. For example,
\lstinline!javax..*Model! matches ``javax.swing.AbstractListModel'',
but it would not if the pattern were \lstinline!javax..Model!.

Note that the \lstinline{..} wildcard has a special meaning when used in
the formal parameter list of a method pattern, as seen at the end of
Line 2 --- in that case it matches an arbitrary number of parameters of
arbitrary type.


\section{Existing AOP semantics \label{AOPSEMANTICS}}
There is a large amount of work on the semantics of
aspect-oriented programming, {\em e.g.}
\cite{aldrich05,walker03,dantas05,dantas06,tucker03,wang06,andrews01,laemmel02,wand04c,bruns04,jagadeesan03,jagadeesan06,hui06,wang06b}.
None of these works involve a pointcut language that approaches the
complexity of the
pointcut language of AspectJ. We contend, however, that it is
possible to understand the semantics of AspectJ by following the
framework introduced in \cite{walker03}.

A key idea of \cite{walker03} is to make the semantics a two-step process,
involving a surface language and a core language. The surface language
in our case is AspectJ. It has the rich notation for pointcuts that
allows programmers to alter the behaviour of the mainline program
without modifying the program text directly. That property is sometimes
called {\em obliviousness} in the literature on aspect-oriented programming.
The core language, by contrast, augments the mainline program with
explicit labelled instrumentation points. Pointcuts refer directly
to sets of such instrumentation points. The operational semantics of
the core language observes the execution of labelled instrumentation
points and executes advice where labels in pointcuts match labels
at runtime.

In most of the papers that have built on \cite{walker03},
the translation from
surface to core is quite simple \cite{dantas05,dantas06}. Wang {\em et al.}
consider a slightly more complex translation, which involves doing
more of the instrumentation at compile-time \cite{wang06,wang06b}.
The current paper continues that trend by offering a translation from the
AspectJ surface language to a suitable core language, replacing the
rich pointcuts by labelled instrumentation points. We do not
offer an operational semantics with it, as that would require augmenting
a complete operational semantics of Java.

In the literature on compiling aspect-oriented programs
\cite{masuhara03,hilsdale04}, instrumentation
points in the static program are called {\em shadows}, whereas their
runtime counterparts are named {\em joinpoints}. We shall follow that
terminology below.

To illustrate, consider the AspectJ program in Figure \ref{fg:aop-ex}.
It contains a pointcut definition (Lines 14--17), and a piece of advice
(extra code) that is triggered by that pointcut (Lines 19--21).
The pointcut \lstinline|a(n)| makes use of the
\lstinline|cflowbelow(p)| primitive: conceptually this
matches if a joinpoint is properly
nested inside any joinpoint that matches \lstinline|p|. Pointcut
primitives such as \lstinline|cflowbelow| are inherently dynamic, and in
general they
cannot be resolved by static matching of shadows (in the example,
the call to \lstinline|f1| from \lstinline|f2| is advised or not depending on
whether \lstinline|f2| was called from \lstinline|f3|). The same holds true
for \lstinline|args|, which exposes the actual value of an argument at
runtime. Apart from these two primitives, the pointcuts are entirely
static and could thus be replaced by sets of
shadows in the program. This is illustrated in the translated program in
Figure \ref{fg:aop-ex2}. Here the mainline program has been augmented
with explicit labels for shadows (there are actually more shadows than
shown here, for instance for class initialisation). Accordingly,
the static pointcuts have been replaced by sets of labels.

\begin{figure}
\begin{lstlisting}
public class X {
   void f1(int n) { }
   void f2(int n) { f1(n); }
   void f3(int n) { f2(n); }

   public static void main(String[] args) {
     X x = new X();
     x.f3(0);
     x.f2(1);
   }
}

aspect A {
   pointcut a (int n) : 
     call(* f*(..)) 
    && args(n)
    && cflowbelow(execution(* f3(..)));

   before(int n) : a(n) {
    System.out.println(thisJoinPoint + ": n="+n);
   }
}
\end{lstlisting}
\caption{Example AspectJ program.}
\label{fg:aop-ex}
\end{figure}

\begin{figure}
\begin{lstlisting}
public class X {
   void f1(int n) { L1 : {} }
   void f2(int n) { L2 : { L3 : {f1(n);} } }
   void f3(int n) { L4 : { L5 : {f2(n);} } }

   public static void main(String[] args) {
     L6 : { X x = (L7 : {new X()});
            L8 : {x.f3(0)};
            L9 : {x.f2(1)}; }
   }
}

aspect A {
   pointcut a (int n) : 
      label(L3,L5,L8,L9)
   && args(n)
   && cflowbelow(label(L4));

   before(int n) : a(n) {
    System.out.println(thisJoinPoint + ": n="+n);
   }
}
\end{lstlisting}
\caption{Translated program.}
\label{fg:aop-ex2}
\end{figure}

The purpose of the remainder of the paper is to pin down the process by
which AspectJ pointcuts are reduced to this form. We shall show how
each static pointcut is defined in terms of a relational query; 
by running those queries on a mainline program, one obtains the
sets of labels as in Figure \ref{fg:aop-ex2}.


\section{Datalog \label{DATALOG}}
We shall use the Datalog query language
to express the semantics of AspectJ pointcuts. Datalog is
similar to Prolog, and syntactically is a subset of Prolog, but excludes the
ability to construct new data type values such as lists. While we give a brief 
introduction to Datalog, we refer to the reader to \cite{gallaire78}
for more details. 
A Datalog program is a
set of clauses (backward implications) of the form:
\[
p(X_1, \ldots, X_n) \leftarrow q_1(Y_1, \ldots, Y_{m_1}), \ldots, q_k(Y_1, \ldots,
Y_{m_k}) .
\]
where each $X_i$ is a variable, and each $Y_j$ is either a variable or a constant.
Each $q_j$ is a positive or negated occurrence of either a predicate or a \emph{test}
such as $X < Y$. A variable occurs \emph{positively} in a clause if it occurs in
a positive predicate on the right-hand side of the clause, but not if it only occurs
in a test. Intuitively, a test such as $X < Y$ cannot be used to generate values of
$X$ and $Y$ making the test true, unlike a predicate $p(X,Y)$.

The semantics of Datalog programs, at least in the absence of negation, are 
straightforward. 
Each predicate $p(X_1, \ldots, X_n)$ defines an $n$-ary relation,
and clauses are interpreted as inclusions between relations.
The meaning of the program is then
the least solution of this set of inclusions.
For instance, the Datalog program
$p(X) \leftarrow p(X)$, while non-terminating as a Prolog program, is a
\emph{bona fide} definition of the empty relation in Datalog.

\subsection{Safe Datalog}

The use of negation in Datalog programs is more problematic, as negation is not a
monotonic operator, and so the fixpoint need not exist. Concretely, a program such
as $p(X) \leftarrow \lnot p(X)$ does not define a relation $p$, and indeed 
$p(X)$ is neither true nor false for any $X$. 
\emph{Safe}
Datalog is a subset of Datalog that provides a sufficient (but not necessary)
condition that guarantees that every program can be evaluated to a set of relations. 
Safe Datalog imposes two
conditions: range restriction and stratification.

\paragraph*{Range Restriction}

In a {\em range-restricted} Datalog program, each variable in the 
head ({\em i.e.} left-hand side) of a clause must appear
positively on the right-hand side. Furthermore, each variable on the right-hand
side must appear positively at least once. This restriction rules out programs
such as $p(X, Y) \leftarrow q(X)$, as $Y$ is left unconstrained. Programs such as:
\[r(X) \leftarrow \lnot q(X), \textrm{regexpmatch}(
\textrm{``a.*''}, X) . \]
where $\textrm{regexpmatch}(P, X)$ is a regular expression pattern matching test, are likewise disallowed.
Both the above queries are
undesirable as the relations defined cannot directly be computed: the $p(X,Y)$
relation may be infinite (any value of $Y$ can be used), while evaluating
the $r(X)$ relation may require evaluating infinitely many regular expression
matches.

\paragraph*{Stratification}

Furthermore, in a {\em stratified} Datalog program, negation may not be used in recursive
cycles. A program is stratified if there is some strict partial order $<$ on
predicates such that whenever $p$ depends negatively on $q$, then $p > q$.
That is, a predicate may never depend negatively on itself. This prohibits
such programs as $p(X) \leftarrow q(X), \lnot p(X)$.

Any safe Datalog program defines a set of relations as the least fixpoint of
the recursive inclusions in the program. Furthermore, this solution may be
effectively computed, and efficient algorithms are known for
evaluating safe Datalog programs. Finally, all relations evaluated are finite,
provided the \emph{primitive} predicates (undefined predicates providing
access to the database) denote finite relations.

These properties of safe Datalog are highly desirable in our setting. First,
Datalog has a clear and straightforward semantics, unlike Prolog, in which the
operational and declarative semantics do not coincide. This guarantees that
defining the semantics of AspectJ pointcuts by translation to Datalog is valid.
Beyond pure semantics, the efficiency of Datalog allows our translated AspectJ
pointcuts to be evaluated --- leading to a directly implementable semantics.

\subsection{Extensions}

For convenience, we shall make use of a number of extensions to pure Datalog. 
These are just syntactic sugar, and may be eliminated in a translation back to 
pure Datalog (which we omit for space reasons).

\begin{itemize}
\item We use a variant of Datalog in which each variable is annotated with a 
\emph{type}. In any clause, the type of the variables defined in the head
are given explicitly, as follows:
\[p(X_1 : p_1, \ldots, X_n : p_n) \leftarrow E .\]
where the $p_i$ are predicates and $E$ is any Datalog expression. 
This is equivalent to the untyped clause:
\[p(X_1, \ldots, X_n) \leftarrow p_1(X_1), \ldots, p_n(X_n), E .\]
Furthermore, we insist that any free variable appearing on the right-hand side
be introduced by an existential quantifier, again giving its type. We use the
syntax
\lstinline[language=rewriterules]{X : p ^ E}
to represent the existential quantification $\exists X (p(X) \land E)$. 
A typed Datalog program is necessarily range-restricted. 
\item Datalog expressions can use negation arbitrarily, so that 
$\textbf{not}(E)$ is an expression whenever $E$ is. 
\item We allow the use of disjunction, represented by a semicolon.
\end{itemize}


\section{Pointcuts are queries \label{QUERIES}}
We now aim to show how pointcuts in AspectJ can be regarded as
Datalog queries over a relational representation of the program.
The correspondence presented here is informal, and it is only
intended to help the reader build an intuition before diving
into the formal details in the next section.

Consider the example translation from Figure \ref{fg:aop-ex} to
Figure \ref{fg:aop-ex2}. 
The program of Figure \ref{fg:aop-ex} is stored as a set of
primitive relations. That set includes,
for example, a relation for recording method declarations:
\begin{lstlisting}[language=rewriterules,numbers=none,deletekeywords={Name}]
   methodDecl(MethodId,Name,Sig,DeclaringType,ReturnType).
\end{lstlisting}
The first field is the {\em identifier}: this can be thought of as
the identity of the corresponding node in the abstract syntax tree.
The primitive relations also record {\em shadows} in the program:
these are the labels shown in Figure~\ref{fg:aop-ex2}. For instance,
we have a relation
\begin{lstlisting}[language=rewriterules,numbers=none]
   callShadow(ShadowId,Method,RecvType)
\end{lstlisting}
This relates the identity of a shadow (labelled instrumentation
points like \lstinline|L1|, 
\lstinline|L2| in
Figure \ref{fg:aop-ex2}) to a method called at that shadow, and 
the static type of the receiver. Furthermore, there is an extensional
relation that records method bodies, as these are also joinpoints
in AspectJ:
\begin{lstlisting}[language=rewriterules,numbers=none]
   executionShadow(ShadowId,Method)
\end{lstlisting}

We are now ready to express the static pointcuts of Figure
\ref{fg:aop-ex}\ as Datalog predicates. We first consider
\lstset{language=[AspectJ]java,numbers=none}
\begin{lstlisting}
   call(* f*(..))
\end{lstlisting}
This pointcut corresponds to the following Datalog predicate:
\begin{lstlisting}{morekeywords deletekeywords={pc1}}[language=rewriterules,numbers=none]
   pc1(S : shadow) :- M : method ^ N : name ^ 
                       callShadow(S,M,_),
                       methodDecl(M,N,_,_,_),
                       regexpmatch('f.*',N) .
\end{lstlisting}
Evaluating \lstinline|pc1| will yield the following set of
solutions for \lstinline|S|: $\{$ L3,L5,L8,L9 $\}$ -- precisely
the translation in Figure \ref{fg:aop-ex2}.

The other static pointcut in
Figure \ref{fg:aop-ex} is
\lstset{language=[AspectJ]java,numbers=none}
\begin{lstlisting}
   execution(* f3(..))
\end{lstlisting}
It is easy to give a na\"ive translation into Datalog, namely
\begin{lstlisting}{morekeywords deletekeywords={pc1}}[language=rewriterules,numbers=none]
   pc2(S : shadow) :- M : method ^ N : name ^ 
                       executionShadow(S,M),
                       methodDecl(M,N,_,_,_),
                       regexpmatch('f3',N) .
\end{lstlisting}
This time evaluation yields only one solution, namely
\lstinline|S|: $\{$ L4 $\}$.

In order to extend this intuitive correspondence to a full
formal semantics, we need to decide exactly on the set of
primitive relations. Furthermore, the above translation is
na\"ive, because in fact we need to take into account where
a pointcut is declared, as the context determines how names
in the pointcut are resolved. For that reason, in the formal
semantics, \lstinline|pc1| and \lstinline|pc2| would need to
take an additional parameter.


\section{Semantics of static pointcuts\label{STATICSEMANTICS}}
\subsection{Overall structure}\lstset{language=rewriterules,alsolanguage=[AspectJ]Java}

As described above, our goal is to determine, for
each static pointcut, which set of labelled instrumentation points it
denotes, as this will pin down its semantics. We achieve this by giving a
set of rewrite rules that translate the
static pointcuts in AspectJ to Datalog predicates. The 
resulting predicate corresponding
to a given pointcut has two free variables --- the first denotes the Java type
in which the pointcut is being evaluated (this parameter is used to handle
name lookup), and the second ranges
over shadow labels; the values of that variable making the predicate true are
precisely those labels which the pointcut denotes.

The rewriting rules are split up into contexts such as pointcuts, 
method patterns and name patterns. For each such context we introduce
a different term constructor (\lstinline|aj2dl| for pointcuts,
\lstinline|methconstrpat2dl| for method patterns, {\em etc.}), 
and the purpose of the rewriting process
is to eliminate these constructors. When they have all been eliminated,
the translation process is complete.

In our rules we adopt the conventions that both left- and
right-hand side of the rewrite rule are enclosed in brackets
($\llbracket..\rrbracket$) to make reading easier. Identifiers shown in
\textbf{bold font} are term constructors, identifiers in \textit{italics} are
metavariables that capture subexpressions of the current term.

\begin{figure*}[htbp]
\begin{lstlisting}[language=rewriterules]
tx: |[ aj2dl(pc1 && pc2, C, S) ]| -> |[ (aj2dl(pc1, C, S), aj2dl(pc2, C, S)) ]|
tx: |[ aj2dl(pc1 || pc2, C, S) ]| -> |[ (aj2dl(pc1, C, S)); (aj2dl(pc2, C, S)) ]|
tx: |[ aj2dl(!pc, C, S) ]| -> |[ not(aj2dl(pc, C, S)) ]|
\end{lstlisting}
\caption{Rewrite rules for Boolean combinations of pointcuts}
\label{fig:bool-pcs}
\end{figure*}

The \lstinline!aj2dl! constructor is used to rewrite an AspectJ pointcut to
Datalog. More precisely, \lstinline!aj2dl(pc, C, S)! should be interpreted as
a Datalog expression with free variables \lstinline!C! and \lstinline!S!, such that
the expression is true iff \lstinline!S! is a shadow (instrumentation label)
in the denotation of \lstinline!pc!, and \lstinline!C! is the class in which the pointcut
\lstinline!pc! is located. The context information provided by the class parameter
\lstinline!C! is necessary, as
the class in which a pointcut is located affects its semantics (through the use
of Java name lookup in pointcuts).

An expression of the form \lstinline!aj2dl(pc, C, S)! is rewritten to a pure Datalog
expression, in a syntax-directed fashion. The rules in Figure \ref{fig:bool-pcs}
show how logical
operators may be eliminated from pointcuts, and converted into the equivalent 
Datalog logical operators. 

\begin{comment}
In the remainder of this section we shall show how
more complex AspectJ pointcuts may be rewritten to Datalog. For space reasons,
we focus on two examples: pointcuts for method calls and executions, and type
name patterns. These are both commonly used and among the most subtle of 
AspectJ constructs, and thus provide representative examples. 
\end{comment}

\subsection{Primitive predicates}

In order to express pointcuts in Datalog, a set of primitive 
predicates (also referred to as {\em extensional predicates} in the deductive databases literature)
must be supplied to query the structure of the program. The set of
primitive predicates must at least encode as much of that structure
as is required to evaluate AspectJ pointcuts. An extreme viewpoint would
be to just store the abstract syntax tree of the mainline program, and write queries over that structure.
However, we shall need quite complex derived notions, such as the type hierarchy
(represented by a relation \lstinline!hasSubtype!). While this information could be
defined purely in terms of the syntax of the program, it would clutter our
semantics of pointcuts to do so. We therefore abstract away from this irrelevant
detail, and use the set of primitive predicates in
Figure \ref{fg:STATICSEMANTICS:extensional1}.
This set captures just enough information about the structure of the program
to evaluate AspectJ pointcuts.

\begin{figure*}[htbp]
\begin{center}

\begin{tabular}{|l|l|}

\hline
Predicate & Description
\\\hline
packageDecl(P, N)
&
\lstinline!P! denotes a package with name \lstinline!N!.
\\\hline
typeDecl(T, N, IsInt, P)
&
\lstinline!T! denotes a type with name \lstinline!N!, declared in package
\lstinline!P!. \lstinline!IsInt! is true if \lstinline!T! is an interface.
\\\hline
primitiveDecl(T, N)
&
\lstinline!T! denotes a primitive type with name \lstinline!N!.
\\\hline
arrayDecl(T, ET, N)
&
\lstinline!T! denotes an array type with element type \lstinline!ET! and name \lstinline!N!.
\\\hline
methodDecl(M, N, S, DT, RT)
&
\lstinline!M! denotes a method with name \lstinline!N!, signature \lstinline|S|, return type
\lstinline!RT! and declared in type \lstinline!DT!.
\\\hline
constructorDecl(C, S, Cls)
&
\lstinline!C! denotes a constructor with signature \lstinline|S| for class \lstinline!Cls!.
\\\hline
fieldDecl(F, DT, T, N)
&
\lstinline!F! denotes a field with name \lstinline!N!, of type \lstinline!T!, 
declared in type \lstinline!DT!.
\\\hline
compilationUnit(CU, P)
&
\lstinline!CU! denotes a compilation unit in package \lstinline!P!.
\\\hline
singleImportDecl(I, N)
&
\lstinline!I! denotes an import declaration, importing the type with name
\lstinline!N!.
\\\hline
onDemandImportDecl(I, N)
&
\lstinline!I! is an on-demand import declaration, for all types in 
the type or package with name \lstinline!N!.
\\\hline
methodModifiers(M, Mod)
&
Method \lstinline!M! has the modifier \lstinline!Mod!.
\\\hline
fieldModifiers(F, Mod)
&
Field \lstinline!F! has the modifier \lstinline!Mod!.
\\\hline
modifiers(Mod, N)
&
Modifier \lstinline!Mod! has string representation \lstinline!N!.
\\\hline
methodThrows(M, T)
&
Method \lstinline!M! declares throwing exception \lstinline!T!
\\\hline
methodParamTypes(M, T, Pos, Next)
&
Method \lstinline!M! has a parameter of type \lstinline!T! at position \lstinline!Pos!.
\lstinline!Next! is the next position after \lstinline!Pos!.
\\\hline
hasChild(A, B)
& 
Syntactic element \lstinline!B! is a directly lexically enclosed by \lstinline!A!.
\\\hline
hasSubtype(T1, T2)
&
\lstinline!T2! is a direct subtype of \lstinline!T1!.
\\\hline
\end{tabular}
\end{center}
\caption{Primitive Predicates: Program Structure}
\label{fg:STATICSEMANTICS:extensional1}
\end{figure*}


While the use of Datalog usually allows a simple and direct expression of queries, 
our treatment of method parameters shows 
that  an encoding may sometimes be necessary. The \lstinline|methodParamTypes|
predicate is used to obtain, for each method,
the list of types of formal parameters. As Datalog does not allow the use of data structures
such as lists, or indeed arithmetic, this cannot be expressed directly. Instead, we define a 
relation:
\begin{lstlisting}[numbers=none]
    methodParamTypes(Method, Type, Pos, NextPos)
\end{lstlisting}
that holds if the formal parameter of \lstinline!Method! at position \lstinline!Pos! has type 
\lstinline!Type!. The \lstinline!NextPos! field records the position of the \emph{next} parameter of 
\lstinline!M! (\textit{i.e.} \lstinline!Pos + 1!), or $0$ if there is no next parameter. This field is
needed because arbitrary arithmetic is not available in Datalog, and is used to iterate over 
parameter types.

In addition to the primitive database predicates describing the structure of the program, we 
include predicates listing the \emph{shadows} in the program. Shadows represent the static
instrumentation points recognised by the AspectJ language; as such, pointcuts denote sets of
shadows. Again, because our focus is on the matching behaviour of pointcuts, we have chosen
to represent shadows directly as primitive predicates. In the terms of Section \ref{AOPSEMANTICS}, 
this amounts to abstracting from the details of inserting labels at every instrumentation
point of the mainline program. Figure 
\ref{fg:STATICSEMANTICS:extensional2} lists the relevant primitive predicates.
Each of these corresponds to a kind of shadow defined by the AspectJ language --- for instance,
the \lstinline!callShadow! predicate describes method or constructor call shadows. 
The type stored for each call shadow
should be interpreted as the receiver type for virtual method calls, while for static method
calls and constructor calls this is just the declaring type of the callee.

It is worth noting that no part of the matching semantics is preempted by these predicates.
Picking out all call shadows, for example, is a simple mechanical task that can be achieved
by case analysis on the program AST: we just have to collect all method calls. We are concerned
with the matching of pointcuts, \emph{i.e.} the process by which the set of all method calls is
constrained to just those which are matched by a given pointcut. We can think of the predicates
in Figure \ref{fg:STATICSEMANTICS:extensional2} simply as a way of bounding the domain of the
Datalog variable \lstinline!S!.

\begin{figure*}[htbp]
\begin{center}
\begin{tabular}{|l|l|}
\hline
Predicate & Description
\\\hline
callShadow(S, M, Recv)
&
Call to a method or constructor \lstinline!M! with receiver type \lstinline!Recv!.
\\\hline
executionShadow(S, M)
&
Execution of a method \lstinline!M!.
\\\hline
initializationShadow(S, C)
&
Initialisation of an object (body of \lstinline!C! after parent constructor calls).
\\\hline
preinitializationShadow(S, C)
&
Pre-initialisation of an object (body of \lstinline!C! before 
parent constructor calls).
\\\hline
staticinitializationShadow(S, T)
&
Initialisation of the static members of a class \lstinline!T!.
\\\hline
getShadow(S, F, Recv)
&
Read access to a field \lstinline!F!, on an object of static type
\lstinline!Recv!.
\\\hline
setShadow(S, F, Recv)
&
Write access to a field \lstinline!F!, on an object of static type
\lstinline!Recv!.
\\\hline
handlerShadow(S, Exn)
&
Execution of a handler for exception \lstinline!Exn!.
\\\hline
adviceexecutionShadow(S)
&
Execution of advice.
\\\hline
\multicolumn{2}{c}{}
\\\hline
isWithinClass(S, Cls)
&
Shadow \lstinline!S! is contained in class \lstinline!Cls!.
\\\hline
isWithinShadow(S1, S2)
&
Shadow \lstinline!S1! is contained within shadow \lstinline!S2!.
\\\hline
\end{tabular}
\end{center}
\caption{Primitive Predicates: Shadows}
\label{fg:STATICSEMANTICS:extensional2}
\end{figure*}

\subsection{Pre-defined derived predicates}\label{sec:intensional-preds}
Below we shall make use of some pre-defined derived predicates (also called {\em intensional predicates} in the deductive databases
literature),
as a convenient shorthand in defining the semantics of pointcuts.

The simplest examples are those predicates that are used as types,
such as \lstinline!constructor!, \lstinline!method!, 
\lstinline!field!, \lstinline!type!. Most of these are self-explanatory,
but there are some exceptions: \lstinline|callable(M)| holds when 
\lstinline|M| is a method or a constructor; similarly \lstinline|packageOrType(T)|
is the union of the \lstinline[language=rewriterules]|package| and \lstinline|type| predicates.

Other pre-defined predicates include \lstinline|hasName(X,N)|, which is true
when \lstinline|X| is an entity (method, type, package, \ldots) that has name
\lstinline|N|. All of these are obtained via simple projections of the primitive
relations.

A more complex class of pre-defined predicates are those used for traversing
hierarchical data. A typical example is the reflexive transitive closure of the immediate
\lstinline|hasSubtype| relation:

\begin{center}
\begin{lstlisting}[language=Prolog,numbers=none]
hasSubtypeStar(T : type,T : type).
hasSubtypeStar(T : type,S : type) :- 
  U : type ^ ( hasSubtype(T,U), hasSubtypeStar(U,S) ).
\end{lstlisting}
\end{center}

The final category of pre-defined predicates concerns the lookup of type names
in Java. The most important of these is predicate
\lstinline|simpleTypeLookup(C,N,T)|. It relates
a type \lstinline|C|, a name \lstinline|N| and a type \lstinline|T| precisely when
inside \lstinline|C|, looking up a type by name \lstinline|N| would result in \lstinline|T|
according to the Java Language Specification. Furthermore \lstinline|N| is assumed to be
a simple name, not containing dots.

For space reasons, we do not include a list of the pre-defined derived predicates in this paper. The companion technical report contains the details of these predicates.

\subsection{Rewrite rules}
As explained above, we aim to give a semantics to the AspectJ pointcut language
by rewriting it to Datalog in a term-based, purely syntactic fashion. 
The complete set of rewrite rules for doing that
consists of about 90 rules. While it is pleasing
that so few rules suffice to pin down the whole pointcut language, 
space forbids a thorough description of all rules in this paper 
(full details can be found in the companion report \cite{pointcutsemantics06abc}).
Rather than give a cursory overview of all rules, we present an in-depth
discussion of two particular features of the AspectJ pointcut language.
The specific choice of constructs we describe is significant, as we
focus on language features that have been a source both of
confusion among AspectJ users and implementation bugs. This illustrates
the necessity for a precise semantics to clarify the pointcut language. 

In developing our semantics, we felt it was important that the rewrite rules
are directly executable, so they can be easily tested on tricky examples. 
At first we developed the rules by directly rewriting abstract syntax trees
that represent pointcuts,
but in this form the rules quickly became unreadable. We therefore implemented
them using the Stratego system of Visser {\em et al.}; its main attraction is
that rewrite rules can be specified in a concrete syntax \cite{visser02} --- in
our case, concrete AspectJ pattern syntax on the left-hand side of rules, and
concrete Datalog syntax on the right-hand side. Furthermore,
Bravenboer {\em et al.} have developed a grammar for AspectJ that we adopted
for this project \cite{bravenboer06}. The rules shown in this paper are slight
typographical modifications of their implementation in Stratego.


\subsubsection{Call and execution pointcuts}


AspectJ offers two ways to intercept method invocations: one for intercepting
at the call site, and another for intercepting the execution of a method
body in the defining class. For the first alternative, one uses the \lstinline|call| pointcut,
and for the second \lstinline|execution|. The seemingly different matching behaviours
of \lstinline|call| and \lstinline|execution| have led to considerable confusion, and
a comprehensive discussion can be found in \cite{barzilay04} (although it is now somewhat
dated, since it deals with AspectJ 1.1.1 and the language semantics has evolved). To illustrate
the difference between \lstinline|call| and \lstinline|execution|, consider
the following type hierarchy:
{\lstset{language=[AspectJ]Java,numbers=none}
\begin{lstlisting}
   class A { void m() {} }
   class B extends A {}
   class C extends B { void m() {} }
\end{lstlisting}
along with the pointcuts
\begin{lstlisting}
   pointcut c() : call(* B.m(..));
   pointcut e() : execution(* B.m(..));
\end{lstlisting}
and the sequence of calls
\begin{lstlisting}
   (new A()).m();    (new B()).m();    (new C()).m();
\end{lstlisting}
}
The call pointcut \lstinline|c()| will match the latter two calls, whereas
the execution pointcut \lstinline|e()| only matches the definition of 
\lstinline|m()| in \lstinline|C|. The situation is further complicated in
the presence of static methods: if both definitions of \lstinline|m()| are
declared static in the
above example, \lstinline|c()| only matches the second call, and \lstinline|e()|
does not match at all.

This potentially surprising matching behaviour is caused by the difference
between call and execution shadows. Any call statement gives rise to a call shadow,
irrespective of where the called method is actually declared. An execution shadow,
on the other hand, spans an entire method body, and as such by definition can only
be present in those classes that contain a (re-)definition of the method.
In the example above, the different behaviour is caused by \lstinline|B| having no
definition of \lstinline|m()|, not any difference in the interpretation of
the pattern.

The precise semantics 
is easily brought out by writing both pointcuts \lstinline|c()| and \lstinline|e()| 
as Datalog queries. We shall first do that by hand, to give the reader a
sense of what needs to be generated; once the goal
is clear, we shall present the rewrite rules to achieve it.
Consider first the call pointcut \lstinline|c()|:
\begin{lstlisting}[language=rewriterules]
c(Context : type, Shadow : shadow) :-
  M : method ^ Recv : type ^ M_Real : method
   ( matchpat(Context,M,Recv) ,
     overrides(M_Real,M) ,
     callShadow(Shadow,M_Real,Recv) ).

matchpat(Context : type, M : method, Recv : type) :-
  T : type ^ MD : type ^
   ( simpleTypeLookup(Context,'B',T),
     hasSubtypeStar(T,Recv),
     methodDecl(M,'m',_,MD,_),
     ( ( hasStrModifier(M,static),
         equals(MD,T) )
       ;
       ( not(hasStrModifier(M,static)),
         hasSubtypeStar(MD,T) ) ) ) .
\end{lstlisting}
In words, this query consists of two parts: one that matches the
method pattern to find a candidate method \lstinline|M| with a matching signature,
and another that picks out an appropriate call shadow \lstinline|Shadow|.

The subsidiary predicate \lstinline|matchpat| first finds the definition
\lstinline|T| of a type named \lstinline|`B'|, as well as a method \lstinline|M|
named \lstinline|`m'| that is declared in some type \lstinline|MD|.
In order to correctly combine these two results, \lstinline|matchpat| must
ensure that \lstinline|T| has an implementation of \lstinline|M|.
According to the AspectJ rules, ``has an implementation of'' means
``declares, overrides, or inherits'' for virtual methods; for static
methods it just means ``declares''. Therefore, if the method
is static, \lstinline|MD| and \lstinline|T| must be equal; if the method is not
static, \lstinline|T| can also be a subtype of \lstinline|MD|. Note that this picks
out all more general methods \lstinline|m| of \lstinline|B.m()| and their declaring classes
\lstinline|MD| --- they are our representation of the set of signatures that the
method pattern matches.

The parameter
\lstinline|Recv| of \lstinline|matchpat| is intended to bind the static receiver
type of the shadow --- that is, the static type of the receiver for virtual calls,
and the declaring type for static calls. At this stage,
the only requirement is that \lstinline|Recv| is \lstinline!T! or a subtype
of \lstinline|T|, the type mentioned in the pointcut.

The second part of the query is simple in comparison: We find all methods
\lstinline!M_Real! overriding the more general definition \lstinline!M! that we
retrieved in \lstinline!matchpat!, and pick out any call shadows that refer to
\lstinline!M_Real! and have a suitable static receiver type \lstinline!Recv!. It
is worth stressing that the \lstinline!overrides()! predicate we use is reflexive,
as a method could be its own most general definition.

Now contrast the above query \lstinline|c| with the Datalog definition
of the \lstinline|execution| pointcut:
\begin{lstlisting}[language=rewriterules]
e(Context : type, Shadow : shadow) :-
  M : method ^ Recv : type ^ M_Real : method ^
   ( matchpat(Context,M,Recv),
     overrides(M_Real,M),
     hasChild(Recv,M_Real),        // crucial difference
     executionShadow(Shadow,M_Real) ) .
\end{lstlisting}
It is remarkably similar to our earlier pointcut for \lstinline|execution|:
Again, we find overriding methods \lstinline!M_Real! for the result of
\lstinline!matchpat!, but now we also assert that the receiver type of the
shadow (which, for execution pointcuts, is just the type containing the method
body) contains a definition of \lstinline!M_Real!; if it didn't, there would be no
execution shadow. Finally, we pick out all shadows for \lstinline!M_Real! as
matched by the pointcut.

\begin{figure*}[htbp]
\begin{lstlisting}[language=rewriterules]
tx: |[ aj2dl(call(methconstrpat), C, S) ]| -> |[ X : callable ^ Y : callable ^ R : type ^ (methconstrpat2dl(methconstrpat, C, R, X),
                                                        overrides(Y, X), callShadow(S,Y,R))  ]|

tx: |[ aj2dl(execution(methconstrpat), C, S) ]| -> |[ X : callable ^ Y : callable ^ R : type ^ (methconstrpat2dl(methconstrpat, C, R, X),
                                                        overrides(Y, X), hasChild(R, Y), executionShadow(S,Y)) ]|
\end{lstlisting}
\caption{Top-level rewrite rules for call and execution pointcuts}
\label{fig:call-exec}
\end{figure*}

We can now conclude that the seemingly different matching behaviour is based
purely on the difference between call and execution shadows; the method pattern
in either case is matched in exactly the same way, but execution shadows only
arise if a class declares a method, whereas for a call shadow it is sufficient
to simply inherit it.

We are ready, therefore, to present the rewrite rules that give
the semantics of \lstinline|call| and \lstinline|execution| in full 
generality. The rules (Figure~\ref{fig:call-exec}) follow the argument above:
one rule picks out a \lstinline|callShadow|, and the other an
\lstinline|executionShadow| (with the side condition that there needs to be
an actual declaration of the method in the receiver), but the method or constructor
pattern is treated uniformly. 

That pattern is further
rewritten using the \lstinline!methconstrpat2dl! term constructor. Rewrite
rules are given in Figure \ref{fig:methconstrpat} (those shown are for
method patterns --- constructor patterns are very similar). We see that
the method
pattern is further broken down into its constituent parts: a modifier pattern,
a type pattern for the return type, a pattern matching class members, and a
formals-pattern (\emph{i.e.} a pattern over the method's formal parameters),
as well as an optional pattern on the \lstinline!throws!
clause of the method. Each of these is rewritten to Datalog using the appropriate
term constructor, and the resulting Datalog expressions are conjoined in the
natural way.

\begin{figure*}[htbp]
\begin{lstlisting}[language=rewriterules]
tx: |[ methconstrpat2dl(mmodpat typepat membpat(formalspat), C, R, X) ]|
        -> |[ T : type ^(mmodpat2dl([mmodpat], X), typepat2dl(typepat, C, T),
              methmembpat2dl(membpat, C, R, X), formals2dl([formalspat], C, X, 1), returns(X, T)) ]|

tx: |[ methconstrpat2dl(mmodpat typepat membpat(formalspat) throws throwspat, C, R, X) ]|
        -> |[ methconstrpat2dl(mmodpat typepat membpat(formalspat), C, R, X), throws2dl(throwspat, C, X) ]|
\end{lstlisting}
\caption{Rewriting for method patterns --- constructor patterns are similar}
\label{fig:methconstrpat}
\end{figure*}

We refrain from listing all the auxiliary term constructor rewrite rules here,
the interested reader may find our full set of rules in our technical
report \cite{pointcutsemantics06abc}.
For now, we just note that out of the additional constructors,
\lstinline!mmodpat2dl! and \lstinline!formals2dl! are implemented in the natural
fashion, {\em i.e.} they define a set of predicates asserting that the method has a
certain modifier (or a certain formal parameter), recursively working through
the list of modifier (or formal parameter) patterns. \lstinline!typepat2dl! and
\lstinline!methmembpat2dl! ultimately rely on name patterns, and the
implementation of those proved unexpectedly challenging. We discuss it in
Section \ref{sec:type-name-pats}.

Thus, the last remaining term constructor is \lstinline!throws2dl!, and there is
a subtlety that can easily be missed when perusing the AspectJ documentation,
but which appears clearly in our semantics. The rewrite rules are given in
Figure \ref{fig:throws-to-dl}. They are an illustration of the kind of recursive
rewriting that is also employed with \lstinline!mmodpat2dl! and
\lstinline!formals2dl!. An empty exception pattern is rewritten to a dummy
predicate that is later eliminated. In the remaining two clauses, when rewriting
exception patterns we differentiate between the case when the first
character of the pattern is a `!', and when it is not. According to the AspectJ
documentation, in the former case the pattern matches if none of the declared
exceptions of a method match the rest of the pattern, and in the latter case
we match if there is \emph{some} exception in the throws clause that matches the
pattern. So \lstinline|!Ex| is an exception pattern that starts with a `!',
whereas `!' in the \lstinline|(!Ex)| pattern is a part of the class name pattern
and not of the exception pattern and therefore the third clause of the
\lstinline!throws2dl! rule will be applied.

While the authors are of the opinion that it is bad language design to put
substantial meaning into parentheses (the throws pattern
\lstinline|!Ex| has a different meaning from \lstinline|(!Ex)|, as shown above), it poses
no problems for our method of pinning down the semantics. We hope that by
giving a crisp semantics, issues such as these will become easier to discuss
and rectify.

\begin{figure*}[htbp]
\begin{lstlisting}[language=rewriterules]
tx: |[ throws2dl([], C, M) ]| -> |[ true(M) ]|

tx: |[ throws2dl([!classnamepat, throwspat], C, M) ]| -> |[ not(E : type ^(classnamepat2dl(classnamepat, C, E), throwsException(M, E))),
                                                            throws2dl(throwspat, C, M) ]|

tx: |[ throws2dl([classnamepat, throwspat], C, M) ]| -> |[ E : type ^(classnamepat2dl(classnamepat, C, E), throwsException(M, E)),
                                                            throws2dl(throwspat, C, M) ]|
\end{lstlisting}
\caption{Rewrite rules for \lstinline!throws2dl!}
\label{fig:throws-to-dl}
\end{figure*}

\subsubsection{Type name patterns}\label{sec:type-name-pats}

Type name patterns in AspectJ pointcuts allow sets of types to be concisely denoted,
and are invaluable in expressing many commonly-used pointcuts. However, the semantics
of type name patterns is surprisingly subtle, and as such it is useful to examine it
more closely.

Type patterns allow the use of wildcards to denote sets of types. Examples of type patterns
include: \lstinline{Foo}, \lstinline{a*..B} (read: any name starting with \lstinline{a},
followed by a dot-separated list of identifiers, followed by \lstinline{B}) 
and \lstinline{*}. While it is quite clear what set of \emph{strings} is represented by
a name pattern, the subtlety lies in the interpretation of these as names. This has been
a source of confusion in the AspectJ community, and indeed the {\em ajc} 
\cite{aspectjhome}\ and {\em abc} \cite{abc}\
compilers for AspectJ do not implement the same rules. Furthermore, this is the cause of a 
substantial bug in the reference AspectJ implementation \cite{isberg06}. 

To see how this issue arises, consider a name pattern, for
definiteness say \lstinline{a*..B}. There are two possible interpretations of this pattern.
The first possibility is that this should range over \emph{fully qualified} names. In this
case, classes \lstinline{a.B} and \lstinline{aa.c.B} would be matched, but not 
\lstinline{d.a.B} (we use the convention that lowercase identifiers denote packages). 

Alternatively, the name pattern might denote any class that can be referred to by a
name of the form \lstinline{a*..B} \emph{from the aspect}. That is, in this view the
normal Java name lookup rules are used to interpret names. This matches any type matched in
the previous way (any type can be referred to by its fully qualified name), but may match
\emph{more} types. For instance, the simple pattern \lstinline{B} would match any class 
\lstinline{B} in the same package as the aspect. 

In fact, the semantics of AspectJ use either form of matching, depending on context. The
key is the presence or absence of the \emph{wildcards} \lstinline{*} and \lstinline{..}
in the pattern. If a wildcard appears anywhere in the pattern, then the pattern should 
be interpreted as ranging over fully qualified names, and no name lookup is performed.
However, if there are no wildcards in the pattern, then it is interpreted as a Java
name, and denotes whichever types (if any) can be referred to by the given name from 
the context of the aspect. Finally, the name pattern \lstinline{*} (a single asterisk)
is treated as a special case. This matches \emph{any} type, including anonymous types
such as anonymous inner classes, which otherwise would be matched by no name pattern.

We shall now give the semantics of type name patterns in more detail.

Type patterns in AspectJ are built up from the following. A \emph{simple name pattern},
representing an identifier, is just a literal possibly containing the wildcard
\lstinline{*}. A general name pattern is a sequence of simple name patterns, separated
by either \lstinline{.} or \lstinline{..}, where the latter is a wildcard denoting any
sequence of Java identifiers and full-stops beginning and ending with a full-stop.
Given any name pattern \lstinline{pat}, both \lstinline{pat} and \lstinline{pat+}
(representing any subtype of \lstinline{pat}) are type name patterns, and type name
patterns are closed under logical connectives.
Finally, given a type name pattern \lstinline{tpat},
 \lstinline{tpat[]} is a type name pattern representing an
array with element type matching \lstinline{tpat}. 

Type name patterns are translated using the \lstinline[language=rewriterules]{typepat2dl}
term constructor. The top-level rules (excluding logical connectives) are shown in
Figure \ref{fg:STATICSEMANTICS:typepat-to-dl}. The name pattern is translated 
\textit{via} the \lstinline[language=rewriterules]{namepat2dl}, and the appropriate
type (exact match, subtype or array type) is selected. 

\begin{figure*}[htbp]
\begin{lstlisting}[language=rewriterules]
tx: |[ typepat2dl(namepat, C, T) ]| -> |[ namepat2dl(namepat, C, T), type(T) ]|
tx: |[ typepat2dl(namepat+, C, T) ]| -> |[ T1 : type ^(namepat2dl(namepat, C, T1), hasSubtypeStar(T1, T)) ]|
tx: |[ typepat2dl(typepat[], C, T) ]| -> |[ T1 : type ^(typepat2dl(typepat, C, T1), arrayDecl(T, T1, _)) ]|
\end{lstlisting}
\caption{Type Patterns: Subtypes and Array Types}
\label{fg:STATICSEMANTICS:typepat-to-dl}
\end{figure*}

The \lstinline[language=rewriterules]{namepat2dl} rewrite context defines the semantics of
name patterns. As discussed above, the AspectJ semantics separates out the cases of name
patterns containing wildcards from exact name patterns. This is achieved in 
\lstinline[language=rewriterules]{namepat2dl} (Figure \ref{fg:STATICSEMANTICS:namepat-to-dl})
using an auxiliary test \lstinline[language=rewriterules]{contains-wildcard} that checks the
presence of wildcards in a pattern. Note that
the \lstinline{namepat2dl} predicates match by name only, and in particular can
match either packages or types. The end result is constrained to a type in
\lstinline{typepat2dl}. 

\begin{figure*}[htbp]
\begin{lstlisting}[language=rewriterules]
tx: |[ namepat2dl(*, C, T) ]| -> |[ true(T) ]|
tx: |[ namepat2dl(namepat, C, T) ]| -> |[ wcnamepat2dl(namepat, T) ]|
    where contains-wildcard(namepat) ; fqname(namepat) != "*"
tx: |[ namepat2dl(namepat, C, T) ]| -> |[ exactnamepat2dl(namepat, C, T) ]|
    where not(contains-wildcard(namepat)); fqname(namepat) != "*"
\end{lstlisting}
\caption{Name Patterns: Testing for Wildcards}
\label{fg:STATICSEMANTICS:namepat-to-dl}
\end{figure*}

The semantics of simple name patterns and wildcard name patterns are defined in
Figure \ref{fg:STATICSEMANTICS:wcnamepat-to-dl}. Such a name pattern is matched
(including wildcards) to the fully qualified name of an element. 

\begin{figure*}[htbp]
\begin{lstlisting}[language=rewriterules]
tx: |[ snamepat2dl(*, S) ]| -> |[ true(S) ]|
tx: |[ snamepat2dl(snamepat, S) ]| -> |[ N : name ^(hasName(S, N), regexpmatch(snamepat, N)) ]|
    where snamepat != "*"

tx: |[ wcnamepat2dl(snamepat, T) ]| -> |[ P : package ^ (defaultPackage(P), hasChild(P, T), snamepat2dl(snamepat, T)) ]|
tx: |[ wcnamepat2dl(namepat.snamepat, T) ]| -> |[ E : packageOrType ^(wcnamepat2dl(namepat, E), hasChild(E, T), snamepat2dl(snamepat, T)) ]|
tx: |[ wcnamepat2dl(namepat..snamepat, T) ]| -> |[ E : packageOrType ^(wcnamepat2dl(namepat, E), hasChildPlus(E, T), snamepat2dl(snamepat, T)) ]|
\end{lstlisting}
\caption{Name Patterns: Simple Name Patterns and Wildcards}
\label{fg:STATICSEMANTICS:wcnamepat-to-dl}
\end{figure*}

Finally, the rules for wildcard-free name patterns are shown in Figure 
\ref{fg:STATICSEMANTICS:exactnamepat-to-dl}. These are rather more involved, reflecting the complexity
of name lookup in Java. Two predicates are defined: \lstinline{exactnamepat2dl} matches a name
pattern against type or package names, while \lstinline{pnamepat2dl} matches package names only. 
In accordance with the Java
specification, when a name is looked up in a context where it is unknown whether a package
or type is denoted, the name should be interpreted as a type whenever possible, and only
interpreted as a package if no type of that name exists.
Finally, name lookup for simple
names is performed by the \lstinline{simpleTypeLookup} predicate discussed earlier.

\begin{figure*}[htbp]
%
% NOTE: exacttypenamepat2dl is NOT actually required --- I think. DS
%
%tx: |[ exacttypenamepat2dl(snamepat, C, T) ]| -> |[ simpleTypeLookup(C, snamepat, T) ]|
%tx: |[ exacttypenamepat2dl(namepat.snamepat, C, T) ]| -> |[ Pot : packageOrType ^
%        (exactnamepat2dl(namepat, C, Pot),type(T), hasChild(Pot, T), hasName(T, snamepat)) ]|
%  
\begin{lstlisting}[language=rewriterules]
tx: |[ exactnamepat2dl(snamepat, C, T) ]| -> |[ 
         (simpleTypeLookup(C, snamepat, T));
         (not(T1 : type ^(simpleTypeLookup(C, str, T1))), pnamepat2dl(snamepat, T)) ]|
tx: |[ exactnamepat2dl(namepat.snamepat, C, T) ]| -> |[ 
         Pot : packageOrType ^((exactnamepat2dl(namepat, C, Pot), type(T), hasChild(Pot, T), hasName(T, snamepat)) ;
         (not(T1 : type^(exactnamepat2dl(namepat, C, Pot), hasChild(Pot, T1), hasName(T1, snamepat))), pnamepat2dl(namepat.snamepat, T))) ]|

tx: |[ pnamepat2dl(snamepat, P) ]| -> |[ package(P), hasName(P, snamepat), topLevelPackage(P) ]|
tx: |[ pnamepat2dl(namepat.snamepat, P) ]| -> |[ P1 : package ^ (pnamepat2dl(namepat, P1), hasChild(P1,P), package(P), hasName(P, snamepat)) ]|
\end{lstlisting}
\caption{Name Patterns: Exact Name Patterns}
\label{fg:STATICSEMANTICS:exactnamepat-to-dl}
\end{figure*}

\lstset{language=[AspectJ]Java}


\section{Experimental results \label{EXPERIMENTS}}
The Datalog queries we produce in the semantics are executable,
and so it is natural to ask whether that semantics can be used
directly as the basis of an AspectJ implementation. In this section,
we seek to determine whether that is at all feasible in practice,
by running queries that correspond to some realistic pointcuts on
sizable mainline programs.

There are a number of options for executing Datalog queries. Perhaps the
most obvious one is to capitalise on the fact that Datalog is a
subset of Prolog, so we could just use a Prolog interpreter. However,
to stay true to the declarative semantics of Datalog, such an
interpreter must use {\em tabled resolution}, because otherwise non-termination
might occur. That consideration suggests the use of XSB, the leading
optimising, tabled implementation of Prolog \cite{sagonas94}. However,
in a few preliminary experiments we found that the queries corresponding
to pointcuts can take several hours to complete. Moreover, it took
a considerable amount of optimisation done by hand to reduce XSB run
times to such a level. Clearly the point of directly executing the
semantics is lost if hand optimisation is required.

We therefore decided to use CodeQuest \cite{hajiyev06}, our own
implementation of Datalog based on a relational database system.
CodeQuest first optimises Datalog rules to reduce the number of unnecessary 
computations (applying a specialised version of the well-known 
{\em magic sets} transformation). It then translates 
the optimised Datalog queries into SQL to take the advantage
of several decades of research on RDBMS optimisations. 
For the measurements reported below, we used 
Microsoft SQL Server Express 2005 as the RDBMS backend of the CodeQuest system.

\begin{figure}[htb]
    \begin{center}
    \includegraphics[width=\columnwidth]{Figures/system}
    \end{center}
    \caption{Experimental Setup}
    \label{FG:EXPTDIAGRAM}
\end{figure}

For each of the experiments, a customised version of the
 {\em abc}~\cite{aosd05abc} compiler collects the
facts implied by the program's structure, which 
are used to populate CodeQuest's primitive relations. The 
database is then indexed in a straightforward manner, namely
by creating a separate index on each field of every table. 
The {\em abc} compiler also collects
information on the shadows in the program that are matched by 
pointcuts, which is used to verify the correctness of the
result of CodeQuest's evaluation of the Datalog pointcuts. The overall
architecture is shown in Figure~\ref{FG:EXPTDIAGRAM}.

The experiments themselves are run on four AspectJ software projects 
of various sizes. {\sc Weka} \cite{witten00} is a
data mining tool written in Java, consisting about 10KSLOC. It 
is instrumented with an aspect that checks for changes to an 
object's hash code while it is in a hash set. {\sc JHotDraw} \cite{jhotdraw} is 
a popular open source Java drawing program, with approximately 
21KSLOC. It has been instrumented with an aspect that checks
for the safe use of Java enumerations, similar to concurrent
modification exception checks in Java collections. 
{\sc ReWeave} is a set of diagnostic aspects applied to the 
{\em abc} compiler itself, which has 51KSLOC. Finally, 
{\sc Jigsaw} \cite{jigsaw} is the w3c's leading-edge webserver, 
with approximately 101KSLOC, and has been instrumented by an 
aspect that checks for the proper sequence of resource locks.
Figure \ref{fg:EXPERIMENTS:pointcuts}
details the pointcuts in each of the projects above that were
used in the experiments. These are representative of typical 
AspectJ usage.

\lstset{numbers=none}
\begin{figure*}
\begin{center}
\begin{tabular}{|l|l|}
\hline
        Name & 
        Pointcut 
    \\\hline
        {\sc Weka1} & 
        \begin{lstlisting}
!within(RealHashtableNativeAspect) && call(* Map.put(..))
        \end{lstlisting}
    \\\hline
        {\sc Weka2} & 
        \begin{lstlisting}[deletekeywords={get}]
!within(RealHashtableNativeAspect) && 
    (call(* Map.get(..)) || call(* Map.remove(..)) || call(* Map.containsKey(..)))
        \end{lstlisting}
    \\\hline
        {\sc Weka3} & 
        \begin{lstlisting}
!within(RealHashtableNativeAspect) && call(* Map.remove(Object))
        \end{lstlisting}

    \\\hline
        {\sc Jhotdraw1} & 
        \begin{lstlisting}[deletekeywords={set}]
call(* Vector.add*(..)) || call(* Vector.clear()) || call(* Vector.insertElementAt(..)) || 
    call(* Vector.remove*(..)) || call(* Vector.retainAll(..)) || call(* Vector.set*(..))
        \end{lstlisting}
    \\\hline
        {\sc Jhotdraw2} & 
        \begin{lstlisting}
call(Object Enumeration.nextElement())
        \end{lstlisting}
    \\\hline
        {\sc Jhotdraw3} & 
        \begin{lstlisting}
call(Enumeration+.new(..))
        \end{lstlisting}

    \\\hline
        {\sc ReWeave1} & 
        \begin{lstlisting}
set(* *) && !(within(Aspect) || within(IdentityPair) || 
    within(org.aspectj..*) || within(org.aspectbench..*))
        \end{lstlisting}
    \\\hline
        {\sc ReWeave2} & 
        \begin{lstlisting}
get(* *) && !(within(Aspect) || within(IdentityPair) || 
    within(org.aspectj..*) || within(org.aspectbench..*))
        \end{lstlisting}
    \\\hline
        {\sc ReWeave3} & 
        \begin{lstlisting}
execution(* abc.weaving.weaver.Weaver.resetForReweaving())
        \end{lstlisting}
    \\\hline
        {\sc ReWeave4} & 
        \begin{lstlisting}
execution(* abc.weaving.weaver.Weaver.weaveAdvice()) && 
    !(within(Aspect) || within(IdentityPair) || 
    within(org.aspectj..*) || within(org.aspectbench..*)) 
        \end{lstlisting}
    \\\hline
        {\sc ReWeave5} & 
        \begin{lstlisting}
adviceexecution() && 
    within(Aspect) || within(IdentityPair) || 
    within(org.aspectj..*) || within(org.aspectbench..*) 
        \end{lstlisting}

    \\\hline
        {\sc Jigsaw1} & 
        \begin{lstlisting}
execution(* *(..)) && !within(CflowDepth || LockUpdater || LockChecker)
        \end{lstlisting}
    \\\hline
        {\sc Jigsaw2} & 
        \begin{lstlisting}
call(* org.w3c.tools.resources.ResourceReference+.lock())
        \end{lstlisting}
    \\\hline
        {\sc Jigsaw3} & 
        \begin{lstlisting}
call(* org.w3c.tools.resources.ResourceReference+.unlock())
        \end{lstlisting}
    \\\hline
\end{tabular}
\end{center}
\caption{Pointcuts used in experiments}
\label{fg:EXPERIMENTS:pointcuts}
\end{figure*}
\lstset{numbers=left}

Figure \ref{fg:EXPERIMENTS:results} summarises the results of 
the experiments, with the matching time in 
CodeQuest for each of the pointcuts. It is interesting to observe
that the performance scales well with the project size: from one
project to the next, the size roughly doubles, and that is reflected
in query execution times. We should stress at this point that CodeQuest
is a research prototype, and it is easy to envisage many optimisations
that will improve performance.

\begin{figure}
\begin{center}
\begin{tabular}{|l|r|}
\hline
        Pointcut & 
        CodeQuest
    \\\hline
        {\sc Weka1} &
        4.68 s
    \\\hline
        {\sc Weka2} &
        5.91 s
    \\\hline
        {\sc Weka3} &
        5.24 s
    \\\hline
        {\sc JHotdraw1} &
        11.36 s
    \\\hline
        {\sc JHotdraw2} &
        7.83 s
    \\\hline
        {\sc JHotdraw3} &
        7.53 s
    \\\hline
        {\sc ReWeave1} &
        9.61 s
    \\\hline
        {\sc ReWeave2} &
        9.62 s
    \\\hline
        {\sc ReWeave3} &
        13.29 s
    \\\hline
        {\sc ReWeave4} &
        17.45 s
    \\\hline
        {\sc ReWeave5} &
        7.50 s
    \\\hline
        {\sc Jigsaw1} &
        36.93 s
    \\\hline
        {\sc Jigsaw2} &
        31.34 s
    \\\hline
        {\sc Jigsaw3} &
        31.03 s
    \\\hline

\end{tabular}
\end{center}
\caption{Pointcut matching times with CodeQuest}
\label{fg:EXPERIMENTS:results}
\end{figure}

Now that we have established that the pointcut matching times are acceptable,
it is natural to ask what penalty must be paid for storing the program structure
and the shadows in a relational database, and for building indices on those
primitive relations. 
We compare the performance of matching in CodeQuest with that of the industrial AspectJ compiler {\em ajc}. CodeQuest matching times are composed of two parts: the time it takes to populate and index the facts into the database ({\sc PI}), and the time to execute the aggregate query for the project ({\sc AQ}). The aggregate query for a each project is the disjoint union
of the Datalog equivalents of all of its pointcuts. This is then compared to the total compile time for the project in {\em ajc}.
Figure \ref{fg:EXPERIMENTS:ajccomparison} shows the results of this comparison. 

The evaluation times of the aggregate queries are much lower
than the simple total of the individual pointcuts that comprise
it due to the large number of common terms in the Datalog
equivalents of those pointcuts. CodeQuest takes advantage of this
during query evaluation by computing the result of common
terms only once.

The table also shows a ratio comparing {\em ajc}'s total compile
time with that of a hypothetical {\em ajc} compiler that uses Datalog
for pointcut matching. The ratio itself is given by
\[
    {\mbox{\sc ajc} + \mbox{\sc pi} + \mbox{\sc aq} } \over \mbox{\sc ajc}
\]

We compare the query evaluation time to the total compilation
time in {\em ajc} as it is difficult to separate pointcut matching
times in an AspectJ compiler (as an example, name patterns can 
be evaluated prior to matching pointcuts to shadows). 
The intent of this table is to compare Datalog matching times
with an actual industrial-strength AspectJ compiler, and to show
that the performance degradation will not be prohibitive 
if pointcut matching in {\em ajc} were to be replaced 
with Datalog in CodeQuest.

\begin{figure}
\begin{center}
\begin{tabular}{|l|r|r|r|r|}
\hline
        Project & 
        {\sc ajc} &
        \begin{tabular}{c}
        populate \\
        + \\
        index \\
        ({\sc pi})
        \end{tabular} &
        \begin{tabular}{c}
        aggregate \\
        query \\
        ({\sc aq}) 
        \end{tabular}&
        Ratio 
    \\\hline
        {\sc Weka} & 
        5.49 s&
        7.79 s&
        9.15 s&
        4.09
    \\\hline
        {\sc JHotDraw} & 
        5.05 s&
        7.73 s&
        12.15 s&
        4.94
    \\\hline
        {\sc ReWeave} & 
        19.89 s&
        9.94 s&
        26.58 s &
        2.84
    \\\hline
        {\sc Jigsaw} & 
        32.25 s&
        14.93 s&
        43.50 s &
        2.81
    \\\hline

\end{tabular}
\end{center}
\caption{Comparison with {\em ajc}}
\label{fg:EXPERIMENTS:ajccomparison}
\end{figure}

%Additional results
%Weka
%   total abc compile time: 43076 ms
%   total ajc compile time: 5488 ms
%   sql shadow load time: 2320 ms
%   sql index time: 3973 ms
%   aggregate query result: 6619 ms
%Jhotdraw
%   total abc compile time: 41302 ms
%   total ajc compile time: 5054 ms *
%   sql shadow load time: 1625 ms
%   sql index time: 4708 ms
%   aggregate query result: 10713 ms
%Reweave
%   total abc compile time: 596436 ms
%   total ajc compile time: 19894 ms
%   sql shadow load time: 4609 ms
%   sql index time: 7067 ms
%   aggregate query result: 19952 ms
%Jigsaw
%   total abc compile time: 1327417 ms
%   total ajc compile time: 32247 ms
%   sql shadow load time: 5718 ms
%   sql index time: 9895 ms
%   aggregate query result: 30656 ms
%
%ajc does not allow synchronized as a modifier for advice (which occurs in jhotdraw. I just commented it out.

The results show that the matching times for Datalog queries in 
CodeQuest compare favourably with the total compile time of the 
{\em ajc} compiler: they do not exceed the {\em ajc} 
compiler's compilation times by more than a factor of five. 
For a comparison, {\em abc}, which is a research-oriented 
AspectJ compiler designed more for extensibility than speed, can be up 
to 30 times slower than {\em ajc}.
Furthermore, the gap does seem to narrow as the size of the
project increases. 

The times for loading the database are admittedly quite high.
An important property, however, is that this only needs to be done
for each compilation unit separately, and thus when recompilation
occurs, we can incrementally update the relevant database facts. 
In particular, library code would only be loaded once in the database.
Details of this process are described in \cite{hajiyev06}.

In summary, the above experiments show that directly using our semantics
as a basis for an AspectJ compiler is {\em feasible}. Whether it is 
also possible
to make it competitive with existing implementations remains to be seen.
We believe that some penalty in compile time may be acceptable: firstly,
a direct implementation is easily kept in one-to-one correspondence with
the semantics; but also, Datalog is more expressive than the AspectJ
pointcut language --- facilitating useful pointcuts that cannot be
expressed in AspectJ. We expound the latter point in the next section.


\section{Directly expressing pointcuts in Datalog \label{DATALOGPOINTCUTS}}
Datalog, together with the primitive predicates described above, is
a richer language than the AspectJ pointcut language. It is possible
to write recursive pointcuts; bind types, members, and shadows; and
directly query the type and lexical hierarchies of a program.

As a result, it can be beneficial to write pointcuts directly in Datalog.
The richness of the language is useful because it allows a programmer
to express pointcuts in terms of semantic, rather than syntactic,
criteria --- AspectJ pointcuts tend to fall into the second category.
The problems with syntactic criteria, and the uses of logic
languages in alleviating them, have been discussed in the literature before
\cite{volder99,gybels03,kw04}. However, they suggest using a
computationally complete logic language. 

Related work has established the benefits of logic languages for expressing pointcuts (cf. Section \ref{RELATED}).
In this section, we aim to demonstrate that despite the restrictions of safe Datalog to enable strong termination
guarantees, many interesting examples can still be expressed.

Figure~\ref{fg:figure-aspect} shows a well-known aspect for updating
the view of an application structured using the Model-View-Controller
modularisation.
\begin{figure}
\begin{lstlisting}
aspect DisplayUpdating {
  pointcut move():
    call(void FigureElement.moveBy(int,int)) ||
    call(void Point.setX(int))               ||
    call(void Point.setY(int))               ||
    call(void Line.setP1(Point))             ||
    call(void Line.setP2(Point));

  after() returning: move() && !cflowbelow(move()) {
    Display.needsRepaint();
  }
}
\end{lstlisting}
\caption{A famous aspect for decoupling model and view}
\label{fg:figure-aspect}
\end{figure}
The \lstinline!move! pointcut defined on Lines 2--7 is syntactic
in nature: it enumerates all the methods that update the state of
an element in the application-model. A more direct way of expressing
the \emph{intended} set of methods is:
\begin{quote}
All methods that may write to a field that could then
be read in the repainting routine \lstinline!Display.repaint()!.
\end{quote}
Translating this straight into Datalog yields:
\begin{lstlisting}[language=Prolog]
needsDisplayUpdate(M) :-
    typeDecl(DC,'Display',_,_),
    methodDecl(Repaint,'repaint',DC,_,_),
    mayRead(Repaint,F),
    mayWrite(M,F).
\end{lstlisting}
Of course, we must now define exactly what we mean by \lstinline!mayRead!
and \lstinline!mayWrite!. It is not enough to just consider what fields
are read (or written) in one particular method --- we must also
consider any method that could be called transitively from it.
When computing this, we shall also keep in mind the fact that methods can be overridden.
The predicate \lstinline!mayCall!, which contains caller-callee pairs and 
takes into account overriding, is defined as follows.

\begin{lstlisting}[language=Prolog]
mayCall(M,M2) :-
    containsShadow(M,Call),
    callShadow(Call,M3),
    overrides(M2,M3).
\end{lstlisting}

\begin{lstlisting}[language=Prolog]
containsShadow(M,S) :-
    executionShadow(S2,M),
    isWithinShadow(S,S2).
\end{lstlisting}

We are now able to define \lstinline!mayRead! and \lstinline!mayWrite!
in terms of \lstinline!mayCallStar!.
\begin{lstlisting}[language=Prolog]
mayRead(M,F) :-
    mayCallStar(M,M2),
    containsShadow(M2,S),
    getShadow(S,F,_).

mayWrite(M,F) :-
    mayCallStar(M,M2),
    containsShadow(M2,S),
    setShadow(S,F,_).
\end{lstlisting}

Just as in examples in previous sections, we use the convention that, for any predicate \lstinline!pred!,
we write \lstinline!predStar! to denote its reflexive transitive closure.

Finally, it only remains to specify the \lstinline|overrides| predicate. It
is well-known how to do that in a logic language, as demonstrated for
instance in JQuery \cite{mccormick04}. These definitions carry over
to Datalog almost unchanged.

A common complaint about aspects is the lack of clear interfaces
between modules. To a large extent this is a language-independent
issue, and more a matter of software design \cite{griswold06}.
It appears, however, that using semantic pointcuts such as those suggested
above helps to decouple aspects from changeable implementation
details.


\section{Related Work \label{RELATED}}
We have already made comprehensive references to previous work,
so this section provides just a roadmap of the main highlights. The related 
work for this paper falls into four main categories: AOP semantics,
logic pointcuts, logic languages for static analysis, and code queries.

\begin{description}
\item[AOP semantics] In this paper, we have taken our cue from
  the approach of Walker {\em et al} \cite{walker03}. The distinguishing
  characteristic of that semantics is the use of
  a core language with labelled instrumentation points.
  Arguably the semantics of Wand {\em et al.} \cite{wand04c}\ is
  more in line with the spirit of aspect-orientation, as all matching
  of events happens at runtime, thus foregoing that intermediate level.
  The connection between the two styles of semantics is given by
  partial evaluation: partially evaluating Wand's definitional
  interpreter yields a compiler in the style of Walker \cite{masuhara03a}.
  It would have been possible for us to make \cite{wand04c} our starting
  point, but as our focus are queries over the static program structure,
  it would have been a detour.
\item[Logic pointcuts] There is a large amount of previous works,
  including implemented systems, that propose a logic pointcut language
  in lieu of the patterns in AspectJ, notably \cite{gybels03}. 
  In our opinion, the use of a Turing complete pointcut language has
  all the pitfalls associated with undisciplined meta-programming,
  for instance the potential of non-termination at compile time.
  Furthermore {\em just} using a logic language is syntactically
  very cumbersome
  for simple pointcuts that merely refer to method signatures.
  Finally, our experiments show that the use of Prolog is simply
  too inefficient in practice.
\item[Static analysis] Researchers in static analysis have long
  acknowledged that logic programming in general, and Datalog in particular,
  is a suitable notation for expressing static analyses; the work
  by Reps \cite{reps93demand} is an early example. More recently
  Dawson {\em et al} revived that line of work, in \cite{dawson96}.
  Monica Lam and her students have continued that tradition, adding
  the new twist of an implementation via binary decision diagrams
  \cite{lam05b,whaley05using}. We feel much is to be gained from combining
  those insights (mostly directed at traditional applications of static
  analysis), and re-using them in the context of aspect-oriented programming.
\item[Code queries] There is a rich and vast literature on `code queries' in
  the software maintenance community, which
  makes connections to logic programming. It is in that context that the
  idea of storing a program in relational form originated.
  It would take us too far astray
  to review this field here; the interested
  reader is referred to a companion paper
  \cite{hajiyev06} for a comprehensive discussion of how that work
  influenced the design and implementation of our CodeQuest system.
\end{description}


\section{Conclusions \label{CONCLUSION}}
We have presented the first rigorous semantics of a practical
pointcut language, building on the pioneering work of Walker
{\em et al.} \cite{walker03}. 
In doing so, we have sorted out numerous subtle
issues in the semantics of AspectJ, in particular regarding the
matching of name patterns.

Of independent interest is the framework that
we chose for this semantics, namely a translation to safe Datalog.
Safe Datalog is a pure logic programming language,
and it is not Turing complete as all queries are guaranteed to
terminate. At the outset of this project it was not clear to us
that the whole AspectJ pointcut language can be expressed in 
safe Datalog. The
fact that this is indeed possible provides strong evidence that
safe Datalog is a suitable intermediate form for pointcuts in
aspect-oriented programming.

The translation took a pleasingly simple form, namely that of
conditional rewrite rules. We believe that this makes our
semantics accessible to a wide audience, including working
AspectJ developers, as it requires no exotic mathematical machinery.

The semantics are executable, and our experiments provide strong
evidence that a direct implementation is
feasible. At present that still entails a considerable increase in
compile time over an industrial-strength AspectJ compiler, 
but bearing in mind that we used a straightforward research prototype
to evaluate the Datalog queries, we believe substantial further
improvements are within reach. The additional expressive power that
Datalog affords, plus the fact that the semantics {\em is} the
implementation, may well be worth paying a penalty in compile
time.

Finally, we have shown through an example that it is
very useful for developers to have the option of writing 
pointcuts directly in Datalog. Clearly one would not wish to
write {\em all} pointcuts in Datalog, as often AspectJ patterns
are elegant and concise. Our semantics as a simple set of rewrite
rules offers the possibility of a hybrid approach, where the
two notations can be freely mixed as desired. Indeed, it is
easy to envisage a system where
advanced users can define new pointcuts of their own, via
a set of rewrite rules that reduce them to existing primitives,
much in the style of other extensible query languages \cite{cardelli93}.
Dean Wampler and
Ron Bodkin have argued for a `long form' of pointcuts in AspectJ, and
our semantics provides precisely that \cite{bodkin06,wampler06}.


\paragraph*{Acknowledgements}
We would like to thank all members of the {\em abc} team,
in particular Eric Bodden, Laurie Hendren, 
Ond\v{r}ej Lhot\'ak and Ganesh Sittampalam
for many interesting discussions on this paper, 
and also for our very enjoyable joint 
work on the {\em abc} compiler that made the present paper possible.
Martin Bravenboer helped a lot with the use of Stratego. He also
patiently incorporated numerous bug fixes and change requests
into the AspectJ grammar in Stratego. Gregor Kiczales, Luke Ong and
Sam Sanjabi provided helpful feedback on a draft of this paper.

\vspace{-2mm}


\begin{thebibliography}{10}

\bibitem{abc}
abc.
\newblock {The AspectBench Compiler}.
\newblock Home page with downloads, {FAQ}, documentation, support mailing
  lists, and bug database. \url{http://aspectbench.org}.

\bibitem{aldrich05}
Jonathan Aldrich.
\newblock {Open Modules:} modular reasoning about advice.
\newblock In Andrew~P. Black, editor, {\em Proceedings of {ECOOP} 2005}, volume
  3586 of {\em Lecture Notes in Computer Science}, pages 144--168. Springer,
  2005.

\bibitem{andrews01}
James~H. Andrews.
\newblock Process-algebraic foundations of aspect-oriented programming.
\newblock In Akinori Yonezawa and Satoshi Matsuoka, editors, {\em REFLECTION},
  volume 2192 of {\em Lecture Notes in Computer Science}, pages 187--209.
  Springer, 2001.

\bibitem{aspectjhome}
{AspectJ Eclipse home page}.
\newblock http://eclipse.org/aspectj/, 2003.

\bibitem{aosd05abc}
Pavel Avgustinov, Aske~Simon Christensen, Laurie Hendren, Sascha Kuzins,
  Jennifer Lhot{\'{a}}k, Ond\v{r}ej Lhot{\'{a}}k, Oege de~Moor, Damien Sereni,
  Ganesh Sittampalam, and Julian Tibble.
\newblock {\em abc}: An extensible {AspectJ} compiler.
\newblock In {\em Proceedings of {AOSD}}, pages 87--98. ACM Press, 2005.

\bibitem{pointcutsemantics06abc}
Pavel Avgustinov, Elnar Hajiyev, Neil Ongkingco, Oege de~Moor, Damien Sereni,
  Julian Tibble, and Mathieu Verbaere.
\newblock {Datalog Semantics of Static Pointcuts in AspectJ 1.2.1}.
\newblock Technical Report abc-2006-2, AspectBench Compiler Project, 2006.
\newblock \url{http://aspectbench.org/techreports#abc-2006-2}.

\bibitem{barzilay04}
Ohad Barzilay, Yishai~A. Feldman, Shmuel Tyszberowicz, and Amiram Yehudai.
\newblock Call and execution semantics in {AspectJ}.
\newblock In Curtis Clifton, Ralf L{\"{a}}mmel, and Gary~T. Leavens, editors,
  {\em {FOAL}}, pages 19--24, 2004.
\newblock Technical report TR \#04-04, Department of Computer Science, Iowa
  State University.

\bibitem{bodkin06}
Ron Bodkin.
\newblock Pointcuts need a long form.
\newblock
  \url{http://dev.eclipse.org/mhonarc/lists/aspectj-users/msg05971.html}, 2006.

\bibitem{bravenboer06}
Martin Bravenboer, Eric Tanter, and Eelco Visser.
\newblock Declarative, formal, and extensible syntax definition for {AspectJ}
  --- a case for scannerless generalized-{LR} parsing.
\newblock In William Cook, editor, {\em Proceedings of OOPSLA}, page to appear.
  ACM Press, 2006.

\bibitem{bruns04}
Glenn Bruns, Radha Jagadeesan, Alan Jeffrey, and James Riely.
\newblock {$\mu$ABC}: a minimal aspect calculus.
\newblock In Philippa Gardner and Nobuko Yoshida, editors, {\em Proceedings of
  {CONCUR}}, volume 3170 of {\em Lecture Notes in Computer Science}, pages
  209--224. Springer, 2004.

\bibitem{burke04}
Bill Burke.
\newblock {\em has} and {\em hasfield} pointcut expressions.
\newblock
  \url{http://aosd.net/pipermail/discuss_aosd.net/2004-May/000958.html}, 2004.

\bibitem{cardelli93}
Luca Cardelli, Florian Matthes, and Mart\'{\i}n Abadi.
\newblock Extensible grammars for language specialization.
\newblock In Catriel Beeri, Atsushi Ohori, and Dennis Shasha, editors, {\em
  Database Programming Languages}, pages 11--31. Springer, 1993.

\bibitem{dantas06}
Daniel~S. Dantas and David Walker.
\newblock Harmless advice.
\newblock In {\em Conference record of POPL}, pages 383--396. ACM Press, 2006.

\bibitem{dantas05}
Daniel~S. Dantas, David Walker, Geoffrey Washburn, and Stephanie Weirich.
\newblock {PolyAML}: a polymorphic aspect-oriented functional programming
  language.
\newblock In Benjamin Pierce, editor, {\em Proceedings of ICFP}, pages
  306--319. ACM Press, 2005.

\bibitem{dawson96}
Stephen Dawson, C.~R. Ramakrishnan, and David~Scott Warren.
\newblock Practical program analysis using general purpose logic programming
  systems.
\newblock In Kathryn~S. McKinley, editor, {\em Proceedings of PLDI}, pages
  117--126. ACM Press, 1996.

\bibitem{volder99}
Kris de~Volder.
\newblock Aspect-oriented logic meta-programming.
\newblock In Pierre Cointe, editor, {\em {REFLECTION}}, volume 1616 of {\em
  Lecture Notes in Computer Science}, pages 250--272. Springer, 1999.

\bibitem{gallaire78}
Herv{\'{e}} Gallaire and Jack Minker.
\newblock {\em Logic and Databases}.
\newblock Plenum Press, New York, 1978.

\bibitem{jhotdraw}
Erich Gamma.
\newblock {JHotDraw}.
\newblock Available from \url{http://sourceforge.net/projects/jhotdraw}, 2004.

\bibitem{griswold06}
William~G. Griswold, Kevin Sullivan, Yuanyuan Song, Macneil Shonle, Nishit
  Tewari, Yuanfang Cai, and Hridesh Rajan.
\newblock Modular software design with crosscutting interfaces.
\newblock {\em {IEEE} Software}, 23(1):51--60, 2006.

\bibitem{gybels03}
Kris Gybels and Johan Brichau.
\newblock Arranging language features for more robust pattern-based crosscuts.
\newblock In {\em Proceedings of {AOSD}}, pages 60--69. ACM Press, 2003.

\bibitem{hajiyev06}
Elnar Hajiyev, Mathieu Verbaere, and Oege de~Moor.
\newblock {CodeQuest:} scalable source code queries with {Datalog}.
\newblock In Dave Thomas, editor, {\em Proceedings of {ECOOP}}, volume 4067 of
  {\em Lecture Notes in Computer Science}, pages 2--27. Springer, 2006.

\bibitem{hilsdale04}
Erik Hilsdale and Jim Hugunin.
\newblock Advice weaving in {AspectJ}.
\newblock In Karl Lieberherr, editor, {\em Proceedings of {AOSD}}, pages
  26--35. ACM Press, 2004.

\bibitem{hugunin03}
Jim Hugunin.
\newblock Support for modifiers in typepatterns.
\newblock
  \url{http://dev.eclipse.org/mhonarc/lists/aspectj-users/msg01578.html}, 2003.

\bibitem{hui06}
Peter Hui and James Riely.
\newblock Temporal aspects as security automata.
\newblock In Curtis Clifton, Ralf {L\"{a}mmel}, and Gary~T. Leavens, editors,
  {\em {FOAL} workshop at {AOSD}}, Technical Report {\#06-01}, pages 19--28.
  Iowa State University, 2006.

\bibitem{isberg06}
Wes Isberg.
\newblock Type patterns shouldn't match arbitrary suffixes.
\newblock Bug report:
  \url{https://bugs.eclipse.org/bugs/show_bug.cgi?id=141133}, 2006.

\bibitem{jagadeesan03}
Radha Jagadeesan, Alan Jeffrey, and James Riely.
\newblock A calculus of untyped aspect-oriented programs.
\newblock In Luca Cardelli, editor, {\em Proceedings of {ECOOP}}, volume 2743
  of {\em Lecture Notes in Computer Science}, pages 54--73. Springer, 2003.

\bibitem{jagadeesan06}
Radha Jagadeesan, Alan Jeffrey, and James Riely.
\newblock Typed parametric polymorphism for aspects.
\newblock {\em Science of Computer Programming}, To appear, 2006.

\bibitem{kiczales01}
Gregor Kiczales, Erik Hilsdale, Jim Hugunin, Mik Kersten, Jeffrey Palm, and
  William~G. Griswold.
\newblock An overview of {AspectJ}.
\newblock In J.~Lindskov Knudsen, editor, {\em Proceedings of ECOOP}, volume
  2072 of {\em Lecture Notes in Computer Science}, pages 327--353. Springer,
  2001.

\bibitem{kw04}
G{\"u}nter Kniesel, Tobias Rho, and Stefan Hanenberg.
\newblock Evolvable pattern implementations need generic aspects.
\newblock In {\em ECOOP Workshop on Reflection, AOP and Meta-Data for Software
  Evolution}, pages 116--126. 2004.

\bibitem{laddad03}
Ramnivas Laddad.
\newblock {\em {AspectJ} in Action}.
\newblock Manning, 2003.

\bibitem{lam05b}
Monica~S. Lam, John Whaley, V.~Benjamin Livshits, Michael~C. Martin, Dzintars
  Avots, Michael Carbin, and Christopher Unkel.
\newblock Context-sensitive program analysis as database queries.
\newblock In {\em Proceedings of PODS}, pages 1--12. ACM Press, 2005.

\bibitem{laemmel02}
Ralf L{\"a}mmel.
\newblock A semantical approach to method-call interception.
\newblock In {\em Proceedings of AOSD}, pages 41--55. ACM Press, 2002.

\bibitem{masuhara03}
Hidehiko Masuhara and Kazunori Kawauchi.
\newblock Dataflow pointcut in aspect-oriented programming.
\newblock In Atsushi Ohori, editor, {\em Proceedings of {APLAS}}, volume 2895
  of {\em Lecture Notes in Computer Science}, pages 105--121. Springer, 2003.

\bibitem{masuhara03a}
Hidehiko Masuhara, Gregor Kiczales, and Chris Dutchyn.
\newblock A compilation and optimization model for aspect-oriented programs.
\newblock In G{\"{o}}rel Hedin, editor, {\em Compiler Construction}, volume
  2622 of {\em Lecture Notes in Computer Science}, pages 46--60. Springer,
  2003.

\bibitem{mccormick04}
Edward McCormick and Kris~De Volder.
\newblock {JQuery:} finding your way through tangled code.
\newblock In {\em Companion to OOPSLA}, pages 9--10. ACM Press, 2004.

\bibitem{rajan05}
Hridesh Rajan and Kevin~J. Sullivan.
\newblock Classpects: unifying aspect- and object-oriented language design.
\newblock In {\em Proceedings of {ICSE}}, pages 59--68. ACM Press, 2005.

\bibitem{reps93demand}
Thomas~W. Reps.
\newblock Demand interprocedural program analysis using logic databases.
\newblock In Raghu Ramakrishnan, editor, {\em Applications of Logic Databases},
  volume 296 of {\em International Series in Engineering and Computer Science},
  pages 163--196. Kluwer, 1995.

\bibitem{sagonas94}
Konstantinos Sagonas, Terrance Swift, and David~S. Warren.
\newblock {XSB} as an efficient deductive database engine.
\newblock In Richard~Thomas Snodgrass and Marianne Winslett, editors, {\em
  SIGMOD}, pages 442--453. ACM Press, 1994.

\bibitem{tarr02}
Peri~L. Tarr, Harold Ossher, and Stanley~M. Sutton.
\newblock {Hyper/J:} multi-dimensional separation of concerns for {Java}.
\newblock In {\em Proceedings of {ICSE}}, pages 689--690. ACM Press, 2002.

\bibitem{tucker03}
David~B. Tucker and Shriram Krishnamurthi.
\newblock Pointcuts and advice in higher-order languages.
\newblock In Mehmet {Ak{\c{s}}it}, editor, {\em Proceedings of {AOSD}}, pages
  158--167. ACM Press, 2003.

\bibitem{visser02}
Eelco Visser.
\newblock Meta-programming with concrete object syntax.
\newblock In Don~S. Batory, Charles Consel, and Walid Taha, editors, {\em
  Proceedings of {GPCE}}, volume 2487 of {\em Lecture Notes in Computer
  Science}, pages 299--315. Springer, 2002.

\bibitem{jigsaw}
w3c.
\newblock {Jigsaw}.
\newblock \url{http://www.w3.org/Jigsaw/}, 2006.

\bibitem{walker03}
David Walker, Steve Zdancewic, and Jay Ligatti.
\newblock A theory of aspects.
\newblock In Colin Runciman and Olin Shivers, editors, {\em Proceedings of
  ICFP}, pages 127--139. ACM Press, 2003.

\bibitem{wampler06}
Dean Wampler.
\newblock Humane pointcut languages.
\newblock \url{http://blog.aspectprogramming.com/articles/2006/04/21/}, 2006.

\bibitem{wand04c}
Mitchell Wand, Gregor Kiczales, and Christopher Dutchyn.
\newblock A semantics for advice and dynamic join points in aspect-oriented
  programming.
\newblock {\em ACM Trans. Program. Lang. Syst.}, 26(5):890--910, 2004.

\bibitem{wang06b}
Meng Wang, Kung Chen, and Siau-Cheng Khoo.
\newblock On the pursuit of static and coherent weaving.
\newblock In Curtis Clifton, Ralf L{\"a}mmel, and Gary~T. Leavens, editors,
  {\em {FOAL}}, number TR $\#$06-01 in Technical Report, pages 43--52, 2006.

\bibitem{wang06}
Meng Wang, Kung Chen, and Siau-Cheng Khoo.
\newblock Type-directed weaving of aspects for higher-order functional
  languages.
\newblock In John Hatcliff and Frank Tip, editors, {\em Proceedings of {PEPM}},
  pages 78--87. ACM Press, 2006.

\bibitem{whaley05using}
John Whaley, Dzintars Avots, Michael Carbin, and Monica~S. Lam.
\newblock Using datalog and binary decision diagrams for program analysis.
\newblock In Kwangkeun Yi, editor, {\em Proceedings of {APLAS}}, volume 3780 of
  {\em Lecture Notes in Computer Science}, pages 97--118. Springer, 2005.

\bibitem{witten00}
Ian~H. Witten and Eibe Frank.
\newblock {\em Data Mining: Practical Machine Learning Tools and Techniques
  with Java implementations}.
\newblock Morgan Kaufmann Publishers, 2000.

\end{thebibliography}


\end{document}

