\section{Compiling {\sc Nesl} into Java}
\label{sec:implementation}

We considered three different ways to improve \nesl's portability using Java:
write a \vcode\ interpreter in Java, rewrite the \nesl\ compiler so that
it generates Java, or write a translator from \vcode\ into Java.  The
first approach would impose an additional layer of interpretive
overhead.  The second would provide the greatest opportunity for
optimizations (for example, by replacing \vcode's stack model with a
vector register model), but would also require considerable effort.
We took the third approach, choosing ease of implementation over
efficiency of the generated code.

The design of our system is shown in Figure~\ref{fig:overview-java}.
The \nesl\ compiler is unchanged.  Below it, a new \texttt{vcodetojava}
phase converts \vcode\ into Java source code plus calls to a \vcode\ 
emulation library written in Java.  A standard Java compiler compiles this into
bytecode, which can then be executed by any Java virtual machine.  Note
that we have effectively replaced the \vcode\ interpreter with a Java
virtual machine.

\begin{figure}[htb]
  \centerline{\psfig{figure=overview-java.eps}} 
  \onehalfspacing
  \caption{Components (boxes) and languages (solid lines) of the 
  \nesl-to-Java system.  Solid arrows represent translation, and dashed
  lines represent linkage to Java libraries.  New components are shown
  in bold.}
  \label{fig:overview-java}
\end{figure}

%%%%%%%%%%%%%%%%%%

\subsection{Implementing {\sc Vcode} Data Structures and Operations}

The only \vcode\ data structure is a vector of primitive type.  We
represent vectors as Java arrays, which are first-class objects with a
length attribute.  The \vcode\ types (integers, double-precision
floating-point numbers, booleans and characters) are mapped to their
obvious Java equivalents.  The \vcode\ interpreter allocates space for
vectors from a heap and uses reference counting for garbage collection.
In Java, we create arrays using \texttt{new()} and rely on the Java
garbage collector to reclaim them when they are no longer used.

\vcode\ operations receive all their arguments, and return all their
results, via the vector stack.  In a typical implementation, the stack
contains pointers to vectors rather than the vectors themselves.  This
approach permits fast stack operations (especially when popping,
copying, or moving more than one element) and enables multiple copies of
the same vector to be represented by identical pointers to the same
piece of data.  In Java, we achieve the same effect by storing
references to arrays in an instance of the standard Java stack class.

\vcode\ provides over 130 vector operations. These operations
typically have a direct mapping to functions provided by \cvl.  The
\vcode\ interpreter runs a function-dispatch loop to execute programs:
fetch the next \vcode\ operation, decode it, pop the appropriate number
of arguments from the vector stack, call the matching \cvl\ function,
and push the result(s) back onto the stack.
In Java, the \vcode\ vector operations are implemented as methods of a
\texttt{VcodeEmulation} class.  This class implements an abstract
vector-stack object with a stack of references to vectors (Java arrays).
Just like their \vcode\ equivalents, the Java vector methods pop
arguments from the stack and push results onto the stack.
Figure~\ref{fig:java-plus-int} shows a Java method to implement a
\vcode\ floating-point vector multiplication operation.

\begin{figure}[htb]
\singlespacing
\begin{verbatim}
      void MultF () {
        double[] a = (double []) pop ();        // pop the argument arrays
        double[] b = (double []) pop ();
        double[] dst = new double[a.length];    // create a result array
        for (int i = 0; i < a.length; i++) {    // loop over the elements...
          dst[i] = a[i] * b[i];                 // ...multiplying them together
        }     
        push (dst);                             // push the result onto the stack
      }
\end{verbatim}
\vspace*{-0.15in}
\onehalfspacing
\caption{Java implementation of the \vcode\ operation \texttt{* FLOAT},
  which performs an elementwise multiplication of two floating point vectors.}
\label{fig:java-plus-int}
\end{figure}

\vcode\ implements \nesl's nesting of data structures efficiently 
by using \emph{segmented vectors}~\cite{BlellochThesis}.  Segmented
vectors use two kinds of vectors to represent arbitrary sequence
nesting: a normal non-nested vector to hold the data, and a series of
specialized vectors (called \emph{segment descriptors}) to describe how
the data is subdivided.  Many \vcode\ operations are defined only for
segmented vectors, and require their arguments to have segment
descriptors.  We chose to represent a segment descriptor in Java as an
array of integers holding the individual segment lengths.  As a
consequence, the Java implementation of a segmented operation is only
slightly more complex than that of its unsegmented counterpart, with two
nested loops iterating over the segments and the elements within each
segment.  Figure~\ref{fig:java-plus-reduce} shows a Java method for the
\vcode\ operation \texttt{+\_REDUCE FLOAT}, a segmented add-reduce (sum)
that takes as arguments a segment descriptor and a floating-point data
vector.  The result is a vector of the sums of each of the segments.

\begin{figure}[htb]
\singlespacing
\begin{verbatim}
      final void AddReduceF () {
        int[] segd = (int []) pop ();               // pop the segment descriptor
        double[] src = (double []) pop ();          // and the source array
        double[] dst = new double[segd.length];     // create a result array
        int k = 0;
        for (int i = 0; i < segd.length; i++) {     // loop over the segments...
          double sum = 0.0;                         // ...initializing a sum of
          for (int j = 0; j < segd[i]; j++) {       // ...all values in a segment
            sum += src[k++];
          }
          dst[i] = sum;                             // ...and storing the sum
        }
        push (dst);                                 // push the result
      }
\end{verbatim}
\vspace*{-0.15in}
\onehalfspacing
\caption{Java implementation of the segmented \vcode\ operation
  \texttt{+\_REDUCE FLOAT}, which sums the individual segments within a
  floating-point vector.}
\label{fig:java-plus-reduce}
\end{figure}

%%%%%%%%%%%%%%%%%%

\subsection{Translating \vcode\ into Java}

The \texttt{vcodetojava} phase uses a Perl script to generate the Java
code.  An associative array maps most \vcode\ instructions to calls to
methods in \texttt{VcodeEmulation}, while conditionals and function
calls are translated directly to Java conditionals and methods.
Figure~\ref{fig:dotproduct} shows an example of the translation process
for a dot-product function in \vcode, which was generated from a single
line of \nesl\ code.  As can be seen, the translation into an equivalent
Java method is straightforward and can be applied on a line-by-line
basis.

The \vcode{} program is implemented by the \texttt{run} method of a
thread spawned by a Java applet.  \vcode\ graphics operations are mapped
to calls from this thread to Java's standard AWT library, while
asynchronous tasks such as refreshing and event handling are handled by
the parent applet thread.  This corresponds to the use by the standard
\nesl\ system of a subprocess, connected by Unix pipes to the \vcode\ 
interpreter, to interact with the X window system.

\begin{figure}[htb]
  \singlespacing
  \begin{tabbing}
    WWWW \= WWWWWWWWWWWWWWWW \= WWW \=  \kill
    \nesl: \> \verb"function dotproduct (X, Y) = sum ({x * y: x in X; y in Y})" \\
    \\
    \vcode: \> \verb"FUNC DOTPRODUCT_47" \> Java: \> \verb"void DOTPRODUCT_47 () {" \\
    \> \verb"POP 1 1" \> \> \verb"  s.Pop (1,1);" \\
    \> \verb"* FLOAT" \> \> \verb"  s.MultF ();" \\
    \> \verb"COPY 1 1" \> \> \verb"  s.Copy (1,1);" \\
    \> \verb"+_REDUCE" \> \> \verb"  s.AddReduceF ();" \\
    \> \verb"POP 1 1"  \> \> \verb"  s.Pop (1,1);" \\
    \> \verb"RET" \> \> \verb"}" 
  \end{tabbing}
  \vspace{-0.2in}
  \onehalfspacing
  \caption{\nesl, \vcode, and Java representations of a dot-product function.
    The extra Pop and Copy stack operations handle segment descriptors.
    \texttt{s} is an instance of the \texttt{VcodeEmulation}
    vector-stack class. } 
  \label{fig:dotproduct}
  \onehalfspacing
\end{figure}
