\documentclass{llncs}[9pt]
\usepackage{mathrsfs,tikz,algorithm2e,listings,subfig,graphicx,epsfig}
\author{Ahmed Abdelmeged \and Karl Lieberherr}

\newcommand{\code}[1]{\texttt{#1}}
\newcommand{\ajcode}[1]{\code{#1}}


\title{Users Guide}

\begin{document}
\maketitle


\section{Introduction}
Separation of conerns is an important software engineering principle.
Optimization is an important cross-cutting concern. General purpose aspect
oriented programming languages provide suboptimal support for specifying
optimization aspects. Caching computation results is an important general purpose
optimization technique. We develop a domain specific aspect oriented programming
langugae for cahching computation results.

\section{Development of Caching Aspects}
The development of a caching aspect proceeds according to the following process
\begin{enumerate}
  \item Identify an inefficiency in a given program:
  \begin{enumerate}
    \item Identify a method $m$ that could be invoked more than once in
    the same run with related arguments.
    \item Identify the relationship between the arguments $a_1,\ a_2$ of
    two invocations $m(a_1),\ m(a_2)$ of $m$. The relationship could be
    either:
    \begin{itemize}
      \item $a_1$ is the same as $a_2$, or
      \item $a_2$ is an updated version of $a_1$ updated via one or
      more methods from the set $F$.
    \end{itemize}
  \end{enumerate}
  \item For each method $f$ in $F$, develop an incrementalized version
  of $m$ under $f$, denoted as $m_f$. $m_f$ must satisfy the condition
  $m \cdot f\ =\ m_f \cdot m$.
\end{enumerate}

Given $m$, $F$ and $m_F$, an optimization aspect can be systematically
generated. The generated aspect performs two main tasks:
\begin{enumerate}
  \item Memoize $m$.
  \item Trap the calls made to any $f$ in $F$ that update the arguments
  $a_1$ of one of memoized calls to $m$ to $a_2$. Use $m_f$ to
  compute $m(a_2)$ from the memoized result of $m(a_1)$. Add $m(a_2)$ to
  the momization table.
\end{enumerate}

As we shall see below, there are cases where the arguments $a_1,\ a_2$ of two
invocations have a more subtle relation. Both are updated versions of some
third object $b$. Inserting a call $m(b)$ is necessary for exposing the
inefficiency to the aforementioned technique.

Also, It is not always possible to develop an incrementalized version of some
method $m$ under $f$. For example, if $m$ is $median$ and $f$ is $filter$.
The result of $median$ is not so useful in computing $median \cdot filter$.
In this case, it is possible to replace the calls to $m$ with an alternate
implementation $n$ that relies on an auxilary method $aux$ that can be
incrementalized. For example, $median$ can be replaced with a call to $sort$
followd by a retrieval. $sort$ is an auxilary method that can be
incrementalized under $filter$. In fact $sort$ commutes with $filter$.

\section{Benefits of Domain Specific Aspect Oriented Approach}
\begin{enumerate}
  \item Safety: \begin{enumerate}
                  \item Ensuring $m \cdot f\ =\ m_f \cdot m$.
                  \item In a programming language with side effects, ensuring
                  that memoized calls do not go stale.
				\end{enumerate} Both are two key lemmas in proving that the optimized
				program is observationally equivalent to the unoptimized program.
	\item Conciseness: with respect to the generated aspect. with respect to the
	hand woven code? 
	\item Measuring the average runtime improvement?
\end{enumerate}

\section{Case Study I: Topological Ordering}
 Given a directed graph $g$ it is desried to find an ordering of its
 node such that $n$ comes before $m$ in the computed ofrdering if $g$ contains
 an edge from $n$ to $m$. Figure~\ref{code:to} shows a simple algorithm for
 computing the toplogical ordering of a given directed graph. The algorithm
 keeps removing a node with no predecessors from the graph appending it to the
 output list untill there is no more nodes with no predecessors.
 \subsection{Inefficiency}
 There are two sources of inefficiency, the first is the method 
 \lstinline{Graph.sourceNodes()} which is called several times on the same
 graph object updated through the method \lstinline{Graph.remove(Node)}.
 The second source of inefficiency is the method
 \lstinline{Graph.predecessorsOf(Node)} which is called several times on the
 same graph object updated through the method \lstinline{Graph.remove(Node)}
 
  
\begin{figure}[htp]
 \begin{lstlisting}[language=java,tabsize=2,breaklines=true,breakautoindent=true] 
 public class Graph {
	
	List<Node> nodes = new ArrayList<Node>();
	
	public Graph(List<Node> nodes) {
		this.nodes = nodes;
	}

	public List<Node> predecessorsOf(Node node){
		List<Node> predecessors = new ArrayList<Node>();
		for (Node n : nodes) {
			if(n.successors.contains(node)){
				predecessors.add(n);
			}
		}
		return predecessors;
	}
	
	public List<Node> sourceNodes(){
		List<Node> sources = new ArrayList<Node>();
		for (Node node : nodes) {
			if (predecessorsOf(node).size() == 0){
				sources.add(node);
			}
		}
		return sources;
	}
	
	public Maybe<List<Node>> topologicalOrder(){
		List<Node> orderedNodes = new ArrayList<Node>();
		for(List<Node> sources = sourceNodes(); sources.size() > 0 ; sources = sourceNodes()){
			Node n = sources.get(0);
			orderedNodes.add(n);
			remove(n);
		}
		if(nodes.size() > 0 ) return new None<List<Node>>();
		return new Some<List<Node>>(orderedNodes);
	}
	
	public void remove(Node n){
		nodes.remove(n);
	}
}
\end{lstlisting}
\label{code:to}
\caption{Algorithm for Finding The Topological Ordering of a Directed Graph}
\end{figure}

\subsection{Developing An Optimization Aspect}


\section{Case Study II: Finding The Closest Pair of Points in a Plane}
Given a set $S$ of $n$ points in a two dimensional plane, it is desired to find
the closest pair of points. The computaional complexity of the problem is known
to have an asymptotic lower bound of $\Omega(n \cdot log\ n)$\footnote{Via a
straight forward reduction from the element uniqueness problem}. We describe a
divide an conquer algorithm for solving this problem.

In the divide phase, the points are split into two subsets $S_1,\ S_2$ with
roughly the same number of points in each set. The points are split such that the
$x$-coordinate of all the points in $S_1$ is smaller than $x_{median}$ and all
the points in $S_2$ are greater than it. Where $x_{median}$ is the median value
of all $x$-coordinates of the points in $S$. The linear time $x_{median}$

After the split, the closest pair of points in each subset is recursively
computed. Let $P_1,\ P_2$ be the closest pair of points in $S_1,\ S_2$
respectively. When the number of points is suffciently small, the brute force
procedure is used to bottom up from the recursion.

In the combine phase, it is not correct to return one of $P_1$ or $P_2$. It
is necessary to also examine pairs with one point in $S_1$ and the other point in
$S_2$. More precisely, it is enough to examine the set $S'$ of points in either
$S_1$ or $S_2$ with an $x$-coordinate within a distance $\delta$ from $x_{median}$,
where $\delta\ =\ min(\delta_1,\ \delta_2)$, $\delta_1$ is the distance between
the pair of points $P_1$, $\delta_2$ is the distance between the pair of points
$P_2$.

Since the set $S'$ can be as large as $S$, applying the brute force procedure
to the elements in the strip lead to an $\Omega(n^2)$ worst case performance.
Instead, we use a more efficient procedure that relies on the fact that the
points in $S'$ do have a special structure. Namely, they form a $2 \cdot
\delta$ vertical strip and that they are $\delta$-sparse meaning that there is
a \emph{fixed} number of points within a $\delta$ distance from any point in
$S'$.

The solution for the $\delta$-sparse vertical strip case involves
sorting the points by their $y$-coordinate then going through the sorted list
and for each point, a fixed number of its following points are examined.
Figure~\ref{code:cp:CP} showes a Java implementation of the entire algorithm.

\begin{figure}[htp]
\begin{lstlisting}[language=java,tabsize=2,breaklines=true,breakautoindent=true]
class ClosestPair {
	static Result DCCP(List<Point> points){
		int n = points.size();
		if(n<=3){
			return BFCP(points);
		}else{
			final Point xMedian = Utils.median(points, Point.xComparator);
				List<List<Point>> s = Utils.partition(points, Point.xComparator, xMedian);
			Result P1 = DCCP(s.get(0));
			Result P2 = DCCP(s.get(1));

			final Result cpInPartitions = P1.min(P2);
			List<Point> ptsInStrip = Utils.filter(points, new Utils.Predicate<Point>(){
			boolean holdsFor(Point point) {
				return Math.abs(point.x - xMedian.x) > cpInPartitions.getDistance();
			}});
			Result cpInStrip = DCVSCP(ptsInStrip);
			return cpInStrip.min(cpInPartitions);
		}
	}

	static Result DCVSCP(List<Point> points){
		List<Point> ySortedPoints = Utils.sort(points, Point.yComparator);
		Result result = new Result();
		for (int i=0;i<ySortedPoints.size();i++) {
			Point pi = ySortedPoints.get(i);
			for (int j=1;i+j<ySortedPoints.size()&&j<i+7;j++) {
				result = result.min(new Result(pi, ySortedPoints.get(i+j)));
			}	
		}
		return result;
	}

	static Result BFCP(List<Point> points){
		Result result = new Result();
		for (int i=0;i<points.size();i++) {
			Point pi = points.get(i);
			for (int j=i+1;j<points.size();j++) {
				result = result.min(new Result(pi, points.get(j)));
			}
		}
		return result;
	}

}
// ... rest is eldied
\end{lstlisting}
\label{code:cp:CP}
\caption{Divide and Conquer Algorithm for Finding The Closest Pair of Points}
\end{figure}

\subsection{Inefficiency}
% The asymptotic runtime complexity of the aforementioned algorithm is
% $O(n \cdot \log^2 n)$. The source of inefficiency stems from the fact
% that at call depth $i$, the input set of points is partitioned into $2^i$
% partitons, each of them is sorted. It would be more efficient to either reuse
% the sorted partitions either at call depth $i-1$ or $i+1$ to obtain the sorted
% partitons at call depth $i$.

There are two sources of inefficiency in the algorithm specified in
Figure~\ref{code:cp:CP}. The first source is the method
\lstinline{Utils.sort(List<Point>, Comparator<Point>)}
All invocations of this method that take place in the \lstinline{DCVSCP}
method have the same second argument. Namely, \lstinline{Point.yComparator}.
Also, the first argument is an updated version of the input list of points
passed to the top level call to the \lstinline{DCCP} method updated via methods
in the set \{ 
\lstinline{List.get(int)},
\linebreak
\lstinline{Utils.Partition(List<Point> Utils.Predicate<Point>)},
\linebreak
\lstinline{Utils.Filter(List<Point>, Utils.Predicate<Point>)}
\}. It is worth mentioning that this inefficiency worsens the worst case asymptotic
runtime complexity of the algorithm to $O(n \cdot \log^2 n)$.

The second source of inefficiency in the algorithm is the method
\linebreak
\lstinline{Utils.median(List<Point>, Comparator<Point>)} all invocations of
this method that take place in the \lstinline{DCCP}
method have the same second argument. Namely, \lstinline{Point.xComparator}.
Apart from the very first invocation, the first argument is an updated version
of the first argument of a previous invocation to the same method, updated via
methods in the set \{ \lstinline{Utils.Partition(List<Point> Utils.Predicate<Point>)},
\lstinline{List.get(int)} \}.

\subsection{Developing an Optimization Aspect}
Before we develop an optimization aspect targetting the first source of
inefficiency, we need to expose it first. We do so by adding a dummy call to
\lstinline{Utils.sort(a, Point.yComparator)} Where \lstinline{a} is the input
list of points passed to the top level call to the \lstinline{DCCP} method. The
code at the end of Figure~\ref{code:cp:HLOPT1} shows how this can be achieved
using AspectJ.

To formally describe the optimization, we need to specify the method that
is source of inefficiency as well as incermentalized version under the set of
update methods. The first line in Figure~\ref{code:cp:HLOPT1} says that we are
interested in memoizing the computations of \lstinline{Utils.sort} when the
second argument is the object \lstinline{Point.yComparator}. Each of the
following three blocks specifies an incrementalized version of
\lstinline{Utils.sort} under one input update method.

\begin{figure}[htp]
\begin{lstlisting}[language=java,tabsize=2,breaklines=true,breakautoindent=true]
aspect OptSort{

	memoize Utils.sort(List<Point>, Point.yComparator) as SRT;

	Utils.partition(a,p)
	after(List<Point> a, List<Point> b,  Predicate<Point> p, List<Point> d): 
		d = Utils.partition(a, p) && (a, b) in SRT{ 
			store (d, Utils.partition(b, p)) in SRT; 
	}

	after(List<Point> a, List<Point> b, Predicate<Point> p, List<Point> d): 
		d = Utils.filter(a, p) && (a, b) in SRT{ 
			store (d, Utils.filter(b, p)) in SRT;
	}

	after(List<Point> a, List<Point> b, int i, List<Point> d): 
		d = List.get(a, i) && (a, b) in SRT{ 
			if(b instanceof List){ 
				store (d, (List b).get(i)) in SRT; 
			}
	}

	// Auxilary AspectJ code for exposing the inefficiency
	pointcut closestPair(List<Point> a): call(* Result DCCP(..)) && args(a);

	pointcut topLevelClosestPair(List<point> a): closestPair(a) &&
	!cflowbelow(closestPair(List<Point>))

	before(List<Point> a) : topLevelClosetPair(a) {
		Comparator<Point> c;
		List<Point> p = Utils.sort(a, c);
	}
}
\end{lstlisting}
\label{code:cp:HLOPT1}
\caption{High Level Specification For The First Optimization Aspect}
\end{figure}
As we mentioned before, it is not possible to 
We do so by replacing the call to
\lstinline{Utils.median(List,Comparator)} with an inefficient implementation
that sorts the list of elements then retrieves the middle element.  

a dummy call
to \lstinline{Utils.sort(a, Point.yComparator)} Where \lstinline{a} is the
input list of points passed to the top level call to the \lstinline{DCCP}
method. The code at the end of Figure~\ref{code:cp:HLOPT1} shows how this can
be achieved using AspectJ.

To formally describe the optimization, we need to specify the method that
is source of inefficiency as well as incermentalized version under the set of
update methods. The first line in Figure~\ref{code:cp:HLOPT1} says that we are
interested in memoizing the computations of \lstinline{Utils.sort} when the
second argument is the object \lstinline{Point.yComparator}. Each of the
following three blocks specifies an incrementalized version of
\lstinline{Utils.sort} under one input update method.

\begin{figure}[htp]
\begin{lstlisting}[language=java,tabsize=2,breaklines=true,breakautoindent=true]
aspect OptSort{

	memoize Utils.sort(List<Point>, Point.yComparator) as SRT;

	after(List<Point> a, List<Point> b,  Predicate<Point> p, List<Point> d): 
		d = Utils.partition(a, p) && (a, b) in SRT{ 
			store (d, Utils.partition(b, p)) in SRT; 
	}

	after(List<Point> a, List<Point> b, Predicate<Point> p, List<Point> d): 
		d = Utils.filter(a, p) && (a, b) in SRT{ 
			store (d, Utils.filter(b, p)) in SRT;
	}

	after(List<Point> a, List<Point> b, int i, List<Point> d): 
		d = List.get(a, i) && (a, b) in SRT{ 
			if(b instanceof List){ 
				store (d, (List b).get(i)) in SRT; 
			}
	}

	// Auxilary AspectJ code for exposing the inefficiency
	pointcut closestPair(List<Point> a): call(* Result DCCP(..)) && args(a);

	pointcut topLevelClosestPair(List<point> a): closestPair(a) &&
	!cflowbelow(closestPair(List<Point>))

	before(List<Point> a) : topLevelClosetPair(a) {
		Comparator<Point> c;
		List<Point> p = Utils.sort(a, c);
	}
}
\end{lstlisting}
\label{code:cp:HLOPT2}
\caption{High Level Specification For The Second Optimization Aspect}
\end{figure}

\end{document}
