\chapter{Introduction to JStar}\label{ch:introjstar}
JStar is a new declarative language that aims to encourage implicit parallel programming\cite{Utting:2013:JLP:2442992.2442996}.
The semantics of JStar language is a subset of Datalog with negation, and explicitly defines a causality ordering which
ensures the correct sequence of execution flow.\cite{tech:datalog} The JStar compiler has already been implemented to translate
a JStar program into a Java parallel implementation, which can be executed on single-core or multi-core CPUs. Since the
compiler generates parallel codes by default, JStar programmers can focus on the design of their program without making
any parallelism strategy. The separation of program and parallel implementation facilitates people, who have little or
no parallel programming knowledge, to aggressively make use of multi-core computing power. The current version of JStar
(V2.0) includes the following features:\cite{Utting:2013:JLP:2442992.2442996}:
\begin{enumerate}
\item The \keyword{Tuple Order Visualizer} is a graphic user interface that displays the execution sequence of tuples in
a JStar program with a tree structure.
\item The \keyword{Satisfiability Modulo Theories (SMT) Connector} translates the theorems from JStar syntax to Standard
SMT-LIB format, so that the conforming SMT theorem solvers can check their satisfiability and determine their validity.
The theorems in a JStar program include the execution order of rules and tuple invariants. If the rule sequence 
conflicts with the user-defined causality ordering declaration, or the tuple invariants are not preserved during the
execution, then the SMT connector would return the results and show any available counterexamples.
\item A \keyword{Logging system} that can record each table usage and provide a tool to visualize the task dependencies.
\end{enumerate}
\section[The JStar Language (Delta Tree and Gamma Database)]{The JStar Language (Delta Tree and Gamma Database)}
JStar stores all data in main memory rather than on disk as in-memory database provides faster accessing speed.
Since the performance is an important goal for JStar, an in-memory database is the preferable form of data storage.
\par The JStar language supports a relational programming paradigm: data are organized in a relational database. JStar
shares most of the terminology of SQL relational models.  A \keyword{tuple} is used to describe a basic data object. An
\keyword{attribute} defines the property of a tuple, including values, data type and name. A tuple is represented as an
ordered list of attribute values. A set of tuples, which have the same attributes, are grouped in one \keyword{table}.
\par \keyword{Rules} control the flow of a JStar program. Rules can add tuples to or query tuples from these tables. But
they cannot update or delete any existing tuple in the tables. Since tuple values cannot be changed during the
execution, and the use of negation and aggregate operators is restricted to avoid data races, the output of JStar
program depends purely on the input values.
Thus, running a JStar program with the same input values would always produce the same results, though possibly in a
different order. This feature makes JStar similar to a pure functional language, and the behaviours of a JStar program
are deterministic. The use of immutable tuples does not allow side effects and makes JStar thread-safe. As tuples can
not be changed or modified after being created, there is no chance that a single tuple is updated by multiple threads.
With the properties of the functional paradigm, determinism, and thread safety, JStar programs can be aggressively
parallelized and optimized by the JStar compiler.
\par Tuples are inserted into the Delta Tree immediately after they are created and initialized by rules. Then these
tuples wait in order in the Delta tree for being processed by the JStar runtime environment. According to the execution
order of tuples which has been declared in the causality expression, the JStar runtime takes out a group of minimal
number of tuples from the Delta Tree. JStar processes the tuples in the same group with one of the three strategies,
which will be detailed in Section~\ref{DeltaTreeAndGammaDatabase}:
\begin{itemize}
\item Splitting the group into subgroups
\item Iterating sequentially through the tuples in the group
\item Creating a list of \texttt{Fork/Join} tasks and then processing them concurrently.
\end{itemize}
\section{How the JStar Compiler Works}\label{compiler}
The JStar compiler translates a JStar program to source code written in Java. By using the Java compiler and the Java
virtual machine(JVM), these generated Java files are converted into Java byte codes and executed on the different types
of operation systems. With appropriate compiler options, the JStar compiler generates parallel Java code. Thus, JStar
programs can be executed on single-core machine or multi-core machine without changing the source code.
\par The JStar compiler is implemented with \class{Xtext}\cite{XText:2.3}, which provides an open-source framework for
programming and domain-specific language development. The JStar compiler is developed with \class{Eclipse SDK} and uses
the \class{Java Runtime Environment (JRE)} for compilation and execution. The JStar compiler transforms each table
declaration in the program into two classes for the tuple and three classes for the table, and places all the 
Java source code into the \texttt{src-gen} folder.
\par Consider the compilation of the PvWatts table in the JStar PvWatts program. The PvWatts table has 5 fields,
ordered as year, month, day, time and watts. Besides, it also adds invariants to each field as described in the
following:
\begin{lstlisting}
table PvWatts(int year, int month, int day, String time, int watts)
	orderby (PvWatts)
	inv 1000<year && 1<=month && month<=12 && 1<=day && day<=31;
\end{lstlisting}
\par When the JStar compiler compiles this table declaration, it generates a \class{PvWatts} class inherited from
\class{Tuple} class and initializes its member variables with the \class{PvWattsBuilder} class. The member variables
of these two classes are inferred from the expression of field declaration. The \keyword{orderby} clause imposes an
natural ordering on the PvWatts class, and generates the \method{compareTo} method to compare all the fields.
For the invariant, the JStar compiler creates and overrides the \method{invariant} method of PvWatts class. This method
checks whether the member variables of each PvWatts tuple satisfy the conditions in the \keyword{inv} declaration, so
that each PvWatts tuple has valid date and time values.
\section{The Default Delta Tree and Gamma Database}\label{DeltaTreeAndGammaDatabase}
JStar uses a pool/queue pattern to process new tuples during the execution. When a new tuple arrives, the JStar runtime
does not process its task immediately but adds this tuple into a temporary data set. This shared database is called the
\texttt{Delta tree} and acts like a queue. All new tuples are lined up in order and waiting for processing. Thus, the
JStar runtime can create and process tuples at the same time without any waiting. JStar runtime take one or more tuples
from Delta tree and execute them concurrently. After being taken out from the Delta tree, each tuple is moved to one
table in the Gamma database and then JStar runtime starts to execute the associated rules whose input is this tuple
kind. These rules can query tuples from Gamma database and put more tuples to Delta tree. Since JStar runtime frequently
interacts with the Delta tree and the Gamma database, efficient implementations of these two databases are essential to
improve the JStar performance. The following subsections describe the default implementations of Delta tree and Gamma set.
\subsection{The Delta Tree}
\begin{singlespace}
\begin{lstlisting}[label=sourcecodeofdeltanode,caption=Source Code of the DeltaNode Class.]
package nz.ac.waikato.jstar.runtime.delta;
import ...

public abstract class DeltaNode extends RecursiveAction {	
	final JStarProgram prog;	
	public DeltaNode(JStarProgram prog) {
		this.prog = prog;
	}
	/**
	 * @return the program that this delta node is part of.
	 */
	public final JStarProgram getProgram() {
		return prog;
	}
	protected void compute() {
		process(prog);
	}	
	/**
	 * Insert the given tuple into this subtree, and remove duplicates.
	 * This subtree is the subtree for level 'depth' of the orderby list.
	 *
	 * @param toInsert the tuple to insert
	 * @param depth
	 */
	public abstract void insert(Tuple toInsert, int depth);
	/**
	 * Execute all the tuples within this subtree.
	 * They are processed in minimum-first order.
	 * Each tuple is removed after it is processed.
	 * @param prog TODO
	 * @return when the whole subtree is empty.
	 */
	public abstract void process(JStarProgram prog);
}

\end{lstlisting}
\end{singlespace}
The Delta tree is organized as a multi-level priority queue and made up of \class{DeltaNode} objects. The DeltaNode
class is shown in Listing~\ref{sourcecodeofdeltanode}. As being extended from the \class{RecursiveAction} class, the
DeltaNode object is an typical Fork/Join task which does not return any result. The DeltaNode class specifies the common
behaviours which are performed by the JStar runtime. For example, the \method{insertion} method inserts a tuple into the
Delta tree. For each kind of tuple, the JStar runtime creates one single DeltaNode subtree of the fixed tree-depth
predefined in the \keyword{order} declaration, and then puts the tuple of its kind to the leaf node. The branch-like data
structure can increase the speed to search for the set of minimal tuples. The reasons are described in the follows:
\begin{inparaenum}[\itshape a\upshape)]
  \item each leaf node in the Delta tree contains only one kind of tuples;
  \item the Delta tree are indexed hierarchically;
  \item duplicate tuples are removed from the Delta tree.
\end{inparaenum}
\textbf{Note that} many different kinds of tuples are inserted into the Delta tree, so it contains a heterogeneous set of tuples.
The ordering of subtree is determined by the \keyword{order} declarations of each kind of tuple with the Nth level.
\begin{singlespace}
\begin{lstlisting}[label=DeltaTreeTuples,caption=Table Declaration of the Delta Tree Example.][h]
table CmdLineArg(int index, String value)
	orderby (CmdLineArgs)
	inv 0<=index;
/**
 * A request to generate tuples: from (inclusive) .. to (exclusive)
 */
table GenTuples(int index, int from, int to)
     orderby (Int, seq index)
    inv 0 <= index;

table PvWatts(int year, int month, int day, String time, int watts)
	orderby (Int, seq year, Int, seq month, PvWatts)
	inv 1000<year && 1<=month && month<=12 && 1<=day && day<=31;

order CmdLineArg < GenTuples < PvWatts;
\end{lstlisting}
\end{singlespace}
\par The Delta set is implemented as a fixed-depth tree and composed of four kinds of DeltaNode objects:
\class{DeltaNodeNamed}, \class{DeltaNodeObject}, \class{DeltaNodeInt} and \class{DeltaNodeSet}.
Consider an example of three tuple kinds (\class{CmdLineArg}, \class{GenTuples} and \class{PvWatts}), and its table
declaration and ordering of tuples are listed in the Listing~\ref{DeltaTreeTuples}. The CmdLineArg tuple passes one
program argument to the JStar program; the GenTuples tuple requests the program to generate a fixed number of PvWatts
tuples; the PvWatts tuple represents a random hourly PvWatts record. The CmdLineArg is the first prioritized tuple as it
is ordered by the default \class{CmdLineArgs} table, which has been already implemented in JStar runtime. The GenTuples
tuple is the second, followed by the PvWatts tuple.
\begin{figure}[h]
\centering
\includegraphics[width=0.9\textwidth]{./introJStar/figure/DeltaTree.eps}
\caption[The Delta tree diagram.]{The Delta tree diagram with 3 tuple kinds of 5 tree-depths.}
\label{fig:DeltaTree}
\end{figure}
\par Figure~\ref{fig:DeltaTree} is the Delta tree of the above example. We will use this graph to describe four
DeltaNode objects:
\begin{description}
\item [DeltaNodeNamed] is used as the root node of the Delta tree and the tuple ordering indicator. According to the
\texttt{orderby} declaration, it inserts the same kind of tuples into one single subtree. As the root node of a Delta
tree, the DelteNodeNamed object contains a fixed-size array of DeltaNode nodes whose length is determined by the total
number of tuple kinds in the program. For example, the above JStar program uses 5 kinds of tuples, including three
user-defined tuple kinds and two default-implemented ones (\class{CmdLineArgs} and \class{Int}). Thus, the array size
inside the DeltaNodeNamed object is 5 and the array position indicates the \method{order} declaration, as listed in the
follows:
\begin{inparadesc}
\item [0)] CmdLineArgs; 
\item [1)] CmdLineArg; 
\item [2)] Int; 
\item [3)] GenTuples; 
\item [4)] PvWatts.
\end{inparadesc}
\par When a new tuple is inserted into the DeltaNodeNamed, its \method{orderby} list determines the position in the array.
For example, the CmdLineArg tuples are ordered by the \class{CmdLineArgs}, as shown in the \method{orderby} declaration
of CmdLineArg table. The JStar runtime puts each new CmdLineArg tuple on the first position of the array and forms the
left subtree.
\item [DeltaNodeInt] is used as the intermediate node of the Delta tree and sorts out the tuples whose the key field
are declared as the integer type. It stores the tuples with the \class{TreeMap<Integer, DeltaNode>} collection, indexing by
the tuple field. For example, the GenTuples tuple uses the \keyword{index} field as the key. When a new GenTuple tuple is
inserted into the sorted TreeMap, the insertion method of the DeltaNodeInt uses its index value as key and check whether this
key has been existed in the map. If not, then the method associates this key with a new DeltaNode object, which is
created with the tuple. As shown in Figure~\ref{fig:DeltaTree}, each GenTuples tuple is put into the DeltaNodeSet object
(depth=2) next to the DeltaNodeInt (depth=1).
\par In addition, this DeltaNodeInt node creates a DeltaNodeNamed node, so that the PvWatts tuples are sorted on
the next DeltaNodeInt node (depth=3). As the PvWatts tuple uses two integer keys, the JStar runtime creates two
layers of DeltaNode nodes, which one layer contains the DeltaNodeName node and the other has the DeltaNodeSet. With
this structure, all the PvWatts tuples are moved into the same leaf node of the right subtree.
\pagebreak
\item [DeltaNodeObject] is used as the intermediate node of the Delta tree and sort out the tuples whose the key field
are declared as the object type. Like the \class{DeltaNodeInt}, the \class{DeltaNodeObject} stores tuple with the
\class{TreeMap<Object, DeltaNode>} implementation. The key is the object itself. For example, if the PvWatts tuples are
ordered by $PvWatts$ object, then the position of a tuple is dynamically determined by all of its key fields: the
PvWatts tuples are sorted in a ascending order of year, month, day, time and watts values. When a new tuple is inserted
to this tree map, the order of tuples must be re-ordered again and each tuple's position needs to be changed as well.
Thus, both of the DeltaNodeObject and the DeltaNodeInt objects needs to dynamically change their storage size. The 
\class{TreeSet} is preferable to the \class{Array} because it provides a total ordering on tuples and quickly resizes
the capacity\cite{website:JavaTreeSet}.
\item [DeltaNodeSet] is used as the leaf node of a subtree. Because of the branch structure, the tuples of the same
kind have been sorted and ordered before they are moved into the DeltaNodeSet. Thus, the DeltaNodeSet node can directly
move these tuples to the storage.
\par The storage of the DeltaNodeSet must be implemented with an efficient data structure. Inserting a tuple requires
to check whether the tuple exists in this storage. As the number of tuples increases , this check takes more
time to compares the new incoming tuple with the old ones in the data storage. An efficient data structure is needed to ensure
the performance of insertion operation. The \class{HashSet} set is used to store the tuples in the DeltaNodeSet for
its stable insertion speed. It offers a contant-time performance over the basic operations (add, remove, contains
and size)\cite{website:JavaHashSet}.
\end{description}
\pagebreak
\subsection{The Gamma Database}
The Gamma database needs to be efficient at adding new tuples, searching for individual tuples and searching for a
subset of tuples with some common field values. The default implementation of each table in the sequential Gamma
database is \class{TreeSet}. When a new tuple is moved to Gamma database, JStar runtime uses the \method{compareTo}
method defined in the orderby declaration to check if this tuple has been present before. This comparison method only
compares the key fields and each of the operations depends on the data type of the compared key field. If the key field
is an integer, then the comparison uses the \method{greater than ($>$)} operator and the \method{less than
($<$)} operator to determine the equality of two tuples. As for the String values, the comparison uses the
\method{compareTo} method of Java \class{String} class to compare two strings. If the comparison results of all the key
fields are the same, then the method returns zero. Otherwise, it returns a non-zero value. The new or non-existing tuples
are moved to the Gamma database; the duplicate tuples, whose result is zero, are discarded.
\par Consider the PvWatts example. The following procedure is used to insert a new PvWatts tuple to the table in Gamma
database. First, the year value of this tuple is used to compare with one tuple in the Gamma database. If the year value is
greater than that of the other tuple, then the method returns the positive one (+1). If the value is less than the
other, then the negative one (-1) is returned. When the result is equal, the next key
field (the month value) is used to compare these two tuples. This comparison method continues until the result is
returned or it has used all the key fields for comparison. Then another tuple in Gamma is chosen to compare with this
tuple and repeat the above procedure until all of the tuples have been compared. If the final result is zero, then the Gamma
database adds this tuple. Otherwise, it ignores this tuple without doing any action.
\cleardoublepage