% -*- Mode: LaTeX -*-

\section{Compilation of Kernel pH}
\label{sec:compile}

The compilation process involves separating program control from the
data it manipulates at run-time.  Essentially, this involves a
systematic elimination of all \fbx{eval} instructions from the
program, replacing them with compiled sequences of low-level
instructions that compute the values of the original expressions. We
also need to define the layout of environments and the mapping from
identifier names to environment slots at compile-time.

In this section we will define a compiler for kernel pH programs based
on the same machinery as described in \sec{eager}. Instead of
dynamically generating and interpreting code sequences as in
\sec{eager}, we will now generate a fixed set of code sequences called
\ibx{threads} at compile-time.  The compiler is defined in three
phases: first, we describe the extensions to the abstract machine and
its instruction set; next, we describe the compilation scheme for the
source program transforming them into a collection of threads; and
finally, we describe how these code sequences are executed on the
abstract machine by giving additional execution rules for the new
instructions.

\subsection{Compilation Machinery}

The semantic categories and translation functions used during
compilation are shown in \fig{static} and are discussed below.

\begin{myfig}{fig:static}{Compile-time Objects.}
\centering
$\begin{array}{lclcl}
\tmap   & \in & \bx{Threadmap} & = & \bx{Identifier} \rightarrow \bx{Code} \\
\imap   & \in & \bx{Identmap} & = & \bx{Identifier} \rightarrow (\bx{Integer}\times\bx{Integer})\\
\env    & \in & \bx{Environment} & = &
(\bx{Integer}\times\bx{Integer}) \rightarrow \bx{Location}\\ \\
\texp{\;} & ::  & \multicolumn{3}{l}{\bx{Expression} \rightarrow
\bx{Identmap} \rightarrow (\bx{Code}\times\bx{Threadmap})}
\end{array}$ \\[0.2in]
$\begin{array}{lrcl}
\bx{Compilation:} & (\insts_{0},\tmap) & = & \texp{\bx{Program}}\;\{\;\}
\end{array}$ 
\end{myfig} 

Every program expression bound to an identifier is compiled into a
single primary thread that computes the value of that identifier.
Other identifiers bound within that computation give rise to their own
threads that are collected into a compile-time mapping from
identifiers to threads ($\tmap$).  The precise compilation rule for
each source language construct appear in \sec{comp-rules}. 

The run-time environment mapping from identifier names to locations is
split into two mappings: one compile-time mapping ($\imap$) from
identifier names to a pair of index offsets $\ang{i,j}$ into the
current environment stack, and another run-time mapping ($\env$) from
index-offset pairs to locations. The first index $i$ in a pair
$\ang{i,j}$ refers to the position of the environment frame from the
top of the current environment stack (zero based).  The second index
$j$ gives the offset within that frame (zero based) that carries the
store location for that identifier.

During compilation, we may sometimes need to refer to some of the
components of the current machine state. We use $\Diamond$ for the
accumulator and \stack for the environment stack.

Finally, the additional machine instructions are shown in \fig{inst2}.
The detailed explanations appear along with the execution rules given
in \sec{comp-inst}.

\begin{myfig}{fig:inst2}{Additional Compiler Instructions.}
\centering
\begin{tabular}{l@{\hm::\hm}p{4.0in}}
\ldc{c} & Load a constant into the accumulator \\  
\makeclsr{\insts}{\env} & Make a closure for the thread $\insts$ with
the environment \env \\ 
\comapp{\ang{i_{f},j_{f}}}{\ang{i_{z},j_{z}}} & Apply the closure $f$
to the argument $z$ \\ 
\pushwork{\insts}{\envs} & Make and push work with the thread \insts,
and the environment stack $\envs$ \\ 
\copyenv{\ang{i_{0},j_{0}}\ldots\ang{i_{n-1},j_{n-1}}} & Allocate an
environment using existing identifier locations \\
\allocenv{\ul{n}} & Allocate an environment with $n$ new identifier
locations
\end{tabular}
\end{myfig}

\subsection{Compilation Rules}
\label{sec:comp-rules}

In this section we describe the compilation process of kernel language
expressions into a collection of threads. 

\subsubsection*{Constants}

An immediate constant is simply loaded into the accumulator.
\[\texp{c}\;\imap = [\ldc{c}], \hm \phi \]

\subsubsection*{Identifiers}

An identifier reference compiles into a sequence of \fbx{touch} and
\fbx{load} instructions that touch the preassigned environment slot and
load its value into the accumulator.
\[\texp{x}\;\imap = [\touch{\imap(x)},\lda{\imap(x)}], \hm \phi\]

\subsubsection*{Primitive Functions}

For strict primitives, we first touch their arguments and then apply
the primitive function.  The identifier translation gives the precise
coordinates of each argument being applied to the primitive function.
\[\texp{\ibx{PF}^{n}(x_{1}\ldots{}x_{n})} \;\imap =
[\touch{\imap(x_{1})},\ldots,\touch{\imap(x_{n})},
\primapp{\fbx{PF}^{n}}{\imap(x_{1}),\ldots,\imap(x_{n})}], \hm \phi\]

Data selector functions such as \tbx{hd},\tbx{tl} and
\tbx{select\_$k$} are implemented using the indirect load instruction
\fbx{loadi\_$k$}. 
\[\texp{\tbx{select\_$k$}(x)} \;\imap =
[\touch{\imap(x)},\ldi{k}{\imap(x)}], \hm \phi \]

The \tbx{Cons} operator is no longer considered as a primitive for
compilation purposes. It is desugared into a block of statements that
allocate an I-structure and fill it as shown below.
\[\tbx{Cons}(x_{1},x_{2}) \Longrightarrow \{\;\begin{array}[t]{l}
t_{1} = \tbx{iAlloc}(2); \\
t_{2} = \tbx{iStore}(t_{1}, x_{1}); \\
t_{3} = t_{1}+1; \\
t_{4} = \tbx{iStore}(t_{3}, x_{2}); \\
\tbx{in} \;t_{1}\;\}
\end{array}\]
\tbx{make\_$n$\_tuple} is desugared similarly. 

\subsubsection*{$\lambda$-abstraction}

The compilation of a function must ensure that both the free
identifiers of the function and the dynamically bound identifiers at
an application can be accessed properly from within the function body.
Since there is no return stack in our machine, we must also explicitly
provide a place to save the caller continuation at the time of
function application which is reactivated by storing the result of the
callee. 
\[\texp{\lambda{}x.\;E} \;\imap =
\{\; \begin{array}[t]{l}
  \insts_{b}, \tmap_{b} = \texp{E}\;\imap_{b}; \\
  \insts_{d} = \insts_{b} \append [\sta{\ang{0,0}}:\popenv:\sched]; \\
  \tbx{in}\; [\copyenv{\imap(y_{1}),\ldots,\imap(y_{m})}:
              \makeclsr{\insts_{d}}{\Diamond}], \hm \tmap_{b} \;\}
  \end{array}\]
\hm where 
\[\begin{array}{l}
y_{1}\ldots{}y_{m} = \fn{FV}{\lambda x.E}\\
\imap_{b} = \{\;x\mapsto\ang{0,1},y_{1}\mapsto\ang{0,2},\ldots,y_{m}\mapsto\ang{0,\ul{m+1}}\;\}
\end{array}\]

We compile the function body under the assumption that its argument
and all its free identifiers are accessible through the top-level
environment frame as reflected in the identifier map $\imap_{b}$. The
first slot in the top-level frame points to the location where the
return continuation of the caller function is stored. This environment
structure and the location to store the return continuation will be
setup during function application. Note that the return continuation
is reactivated at the end of the function body by updating this slot
with the final result.

The $\lambda$-abstraction itself compiles to produce a closure which
carries an environment frame pointing to its free identifiers. 

\subsubsection*{Function Application}

A function application first evaluates the function and then applies
it to the given argument. The application rule is described later in
\sec{comp-inst}. 
\[\texp{\tbx{ap}(f,z)} \;\imap = 
[\touch{\imap(f)}:\comapp{\imap(f),\imap(z)}], \hm \phi \]

\subsubsection*{Case Expression}

For \tbx{case} expressions, we simply compile threads for each branch
and generate a \fbx{switch} instruction to select the appropriate one.
\begin{eqnarray*}
\lefteqn{\texp{\tbx{case}(x,E_{1},\ldots,E_{n})} \;\imap =}\\
& & \{\; \begin{array}[t]{l}
  \insts_{1}, \tmap_{1} = \texp{E_{1}}\;\imap; \\
  \cdots \\
  \insts_{n}, \tmap_{n} = \texp{E_{n}}\;\imap; \\
  \tbx{in} \; [\touch{\imap(x)}:\switch{\imap(x)}{\insts_{1},\ldots,\insts_{n}}],
              \hm\tmap_{1}+\cdots+\tmap_{n} \;\}
  \end{array}
\end{eqnarray*}

\subsubsection*{Block Expression}

For a block, first we need to allocate an environment to hold all the
bound identifiers. Each of the right-hand sides are compiled into
threads that update the appropriate environment slots with their
respective values. These threads are pushed into the work queue for
evaluation. The ``letrec'' semantics of the block are maintained by
allowing the new threads being compiled to refer to themselves \via an
extended thread map.  The identifier map is also adjusted to reflect
the new environment frame being pushed onto the environment stack.

\begin{eqnarray*}
\lefteqn{\texp{\{\;x_{1}=E_{1};\cdots;x_{n}=E_{n}\;\tbx{in}\;x\;\}} \;\imap =} \\
& &  \{\; \begin{array}[t]{l}
  \insts_{1}, \tmap_{1} = \texp{E_{1}}\;\imap'; \\
  \insts'_{1} = \insts_{1} \append [\sta{\ang{0,0}}:\sched]; \\
  \cdots \\
  \insts_{n}, \tmap_{n} = \texp{E_{n}}\;\imap'; \\
  \insts'_{n} = \insts_{n} \append [\sta{\ang{0,\ul{n-1}}]}:\sched]; \\
  \tbx{in}\; [\allocenv{\ul{n}}:\pushenv{\Diamond}:\pushwork{\insts'_{1}}{\stack}:\ldots: \\
  \hmm        \pushwork{\insts'_{n}}{\stack}:\enter{\imap'(x)}:\popenv], 
               \hm \tmap_{b}+\tmap_{1}+\cdots+\tmap_{n} \;\}
  \end{array}
\end{eqnarray*}
\hm where
\[\begin{array}{l}
  \tmap_{b} = \{x_{1}\mapsto\insts'_{1},\ldots,x_{n}\mapsto\insts'_{n}\;\} \\
  \imap'(x) = \bbx{if}\;x=x_{k}\;(1\leq{}k\leq{}n)\;\bbx{then}\;\ang{0,k}\;
              \bbx{else}\;\ang{\fn{fst}{\imap(x)+1},\fn{snd}{\imap(x)}}
  \end{array}\]

\subsection{Execution Rules for Additional Instructions}
\label{sec:comp-inst}

In this section we provide the execution rules for the additional
instructions given in \fig{inst2}. Note that identifier names have
been translated into index-offset pairs $\ang{i,j}$ pointing into the
environment stack that must be dereferenced at run-time to access the
store location.

\subsubsection*{Loading Accumulator}

The \fbx{loadc} instruction is used to load an immediate constant into
the accumulator.

\begin{evalrule}{\fbx{loadc}:}
\inference{\state{\_}{\ldc{c}:\insts}{\envs}{\works}{\store}{}}%
          {\state{c}{\insts}{\envs}{\works}{\store}{}}
\end{evalrule}

\subsubsection*{Closure Creation}

The \fbx{makeclsr} instruction simply creates a new closure from the
given thread and the environment stack.

\begin{evalrule}{\fbx{makeclsr}:}
\inference{\state{\_}{\makeclsr{\insts}{\env}:\insts}{\envs}{\works}{\store}{}}%
          {\state{\cval{(1).\;\insts,\env}}{\insts}{\envs}{\works}{\store}{}}
\end{evalrule}

\subsubsection*{Function Application}

Function application first allocates a flat argument environment for
the function call, copying the closure environment into it. It also
copies the current argument mapping and allocates a new location to
save the return continuation of the caller. The return continuation
would enable the callee to resume the caller after the function call
has completed.  Finally, the entry point present within the closure is
scheduled.

\begin{evalrule}{\fbx{apply}:}
\inference{\state{\_}{\comapp{\ang{i_{f},j_{f}}}{\ang{i_{z},j_{z}}}:\insts}{\envs}{\works}%
                 {\store[\envs[i_{f},j_{f}]\mapsto\ftag{\cval{(1).\;\insts',\env'}}]}{}}%
          {\state{\_}{\insts'}{[\env_{b}]}{\works}{\store'}{}}\\
\multicolumn{1}{l}{where $\begin{array}[t]{l}
\env_{b} = \loc:\envs[i_{z},j_{z}]:\env' \\
\store' = \store+\{\;\loc\mapsto\dtag{[(\insts,\envs)]}\;\}
\end{array}$}
\end{evalrule}

\subsubsection*{Resource Management}

The \fbx{pushwork} instruction creates a thread with the given
instruction thread and the environment chain. 

\begin{evalrule}{\fbx{pushwork}:}
\inference{\state{\_}{\pushwork{\insts'}{\envs'}:\insts}{\envs}{\works}{\store}{}}%
          {\state{\_}{\insts}{\envs}{\works\append[(\insts',\envs')]}{\store}{}}
\end{evalrule}

The \fbx{copyenv} and \fbx{allocenv} instructions construct
environments. \fbx{copyenv} is used to create a new environment
mapping from existing identifier locations such as those for the free
identifiers of a function. \fbx{allocenv} is used for new identifiers
bindings in a block. It allocates new locations in the store and
initializes them to be empty.

\begin{evalrule}{\fbx{copyenv}:}
\inference{\state{\_}{\copyenv{\ang{i_{0},j_{0}}\ldots\ang{i_{n-1},j_{n-1}}}:\insts}%
                 {\envs}{\works}{\store}{}}%
          {\state{\env}{\insts}{\envs}{\works}{\store}{}}\\
\multicolumn{1}{l}{where $\env = [\envs[i_{0},j_{0}],\ldots,\envs[i_{n-1},j_{n-1}]]$}
\end{evalrule}

\begin{evalrule}{\fbx{allocenv}:}
\inference{\state{\_}{\allocenv{\ul{n}}:\insts}{\envs}{\works}{\store}{}}%
          {\state{\env}{\insts}{\envs}{\works}{\store'}{}}\\
\multicolumn{1}{l}{where $\begin{array}[t]{l}
\env = [\loc_{0},\ldots,\loc_{n-1}]\\
\store' = \store+\{\;\loc_{0}\mapsto\dtag{[\;]},\ldots,\loc_{n-1}\mapsto\dtag{[\;]}\;\}
\end{array}$}
\end{evalrule}

