% -*- Mode: LaTeX -*-

\section{Compilation and Run-time Model}
\label{framework}

\subsection{The Kernel Id Intermediate Language}

We base our description on a functional, intermediate language called
Kernel Id which is shown in \fig{kid}. This language supports a rich
set of types including typical scalar basetypes, general algebraic
(sum-of-products) datatypes, $n$-dimensional arrays, and curried
function types. Records and tuples are a special case of algebraic
datatypes with a single product disjunct. We also assume a rich set of
primitive functions for basetypes and array construction/selection, as
well as standard predefined algebraic datatypes such as \ibx{list} and
\ibx{bool}.  The operational semantics of this language has been given
elsewhere in terms of graph rewriting rules \cite{Ariola91}.

%Also note that the language permits accurate
%representation of data sharing using \ibx{blocks}. In this respect, it
%roughly corresponds to a textual representation of the program-graph
%intermediate form within the Id compiler \cite{Traub86}. 

\begin{figure}
\centering
\begin{tabular}{|c|}
\hline
\cbx{Expressions} \\
\hline\hline
$\begin{array}{lcl}
{F,x,y,z\ldots}   & \in & \bx{Identifier} \\
\ibx{SE}          & \in & \bx{Simple Expression} \\
\ibx{PF}^{n}      & \in & \bx{Primitive Fn. with $n$ arguments}\\
\ibx{Case}^{m}\_T & \in & \bx{$m$-way Case Dispatch for type $T$}\\
E                 & \in & \bx{Expression} \\[.1in]

\bx{Constant} & ::= & \ibx{Integer} \mid \ibx{Float} \\
\ibx{SE}      & ::= & \bx{Identifier} \mid \bx{Constant} \\
E             & ::= & \ibx{SE} \mid \ibx{PF}^{n}\;\ibx{SE}_{1}\cdots\ibx{SE}_{n} \\
              &     & \mid \ibx{Case}^{m}\_T \;\ibx{SE} \;(E_{1} \cdots E_{m}) \\
              &     & \mid \ibx{SE}_{0}\;\ibx{SE}_{1}\cdots\ibx{SE}_{n} \mid \bx{Block} \\
\bx{Block}    & ::= & \{[\bx{Statement};]^* \;\tbx{in} \;\ibx{SE} \}   \\
\bx{Statement} & ::= & \bx{Identifier} = E
\end{array}$ \\
\hline\hline
\cbx{Types} \\
\hline\hline
$\begin{array}{lcl}
T^{n}          & \in & \bx{Type-Identifier with $n$ type arguments} \\
{\alpha,\beta} & \in & \bx{Type-Variable} \\
\tau           & \in & \bx{Type} \\
\sigma         & \in & \bx{Type-Scheme} \\[.1in]

\tau    & ::= & \alpha \mid \ibx{int} \mid \ibx{float} \mid (\fbx{n}\ibx{d\_array}\;\tau) \\
        &     & \mid (T^{n} \;\tau_{1}\cdots\tau_{n}) \mid \tau_{1}\rightarrow\tau_{2} \\
\sigma  & ::= & \forall\alpha_{1}\cdots\alpha_{n}.\tau 
\end{array}$ \\
\hline\hline
\cbx{Program} \\
\hline\hline
$\begin{array}{lcl}
C^{k_{m}}_{m}    & \in & \bx{$m$-th Constructor Identifier}\\ 
                 &     & \bx{with $k_{m}$ arguments} \\[.1in]
\bx{Declaration} & ::= & \bx{Fn-Decl} \mid \bx{Type-Decl} \\
\bx{Fn-Decl}     & ::= & \tbx{def} \;F \;x_{1} \cdots x_{n} = E \\
\bx{Type-Decl}   & ::= & \tbx{type} \;T \;\alpha_{1} \cdots \alpha_{n} = \\
                 &     & \hmmm     C_{1} \;\tau_{11}\cdots\tau_{1k_{1}} \\
                 &     & \hmm \mid \cdots \\
                 &     & \hmm \mid C_{m} \;\tau_{m1}\cdots\tau_{mk_{m}} \\
\bx{Program}     & ::= & [\bx{Declaration};]^{*} \; E
\end{array}$ \\
\hline
\end{tabular}
\caption{The Kernel Id Intermediate Language.}
\label{fig:kid}
\end{figure}

The Id source language supports special syntactic constructs such as
list and array comprehensions, complex pattern matching, and nested
function and type declarations \cite{Id90.1}. The Id source program is
translated into a Kernel Id program using standard front-end analyses
and transformations such as comprehension-desugar\-ing,
scope-analysis, type-check\-ing, pattern-matching compilation, and
lambda-lifting \cite{Ariola91,Gupta90,Traub86}. The lambda-lifting
transformation is not essential for the purpose of this paper, but it
helps to simplify our description of the Kernel Id language.

%This results in a Kernel Id program
%where every sub-expression has a well-defined Hindley/Milner type, all
%identifiers have been assigned unique names so that all internal type
%declarations can be lifted to the top-level, and internal functions
%with free identifiers have been closed and also lifted to the
%top-level. 

\subsection{Object Representations and the Memory Model}
\label{reptn}

Kernel Id is an abstract intermediate form that does not take a
position on the underlying representation of objects. However, a
concrete implementation of a language must specify a representation of
objects, which to a large extent, determines its run-time performance
and the garbage collection strategy. In this section, we describe the
concrete representation of Id objects for our current implementation.
This representation is still independent of the target architecture
and only relies upon the assumption of a logically flat, shared, global
address space. Since our ultimate aim is to get the best performance
out of a compiler-directed object identification scheme, we avoid
making any assumptions about boxing and explicit tagging of objects as
much as possible.  The only assumption necessary to support
polymorphism is that all scalar objects and pointers to heap objects
fit a single 64-bit word.

\illfigure{reptn}{Run-time Object Representations for Id.}

Examples of various Id object representations appear in \fig{reptn}.
Scalar objects are by definition untagged and unboxed in Id.
$n$-dimensional arrays are linearized in row-major order into a flat
data-structure that also keeps the bounds in each dimension
$(l_{1},u_{1}),\ldots,(l_{n},u_{n})$ and a set of linearization
constants $c_{0},\ldots,c_{n-1}$ that are used to compute the linear
offset into the array given a $n$-dimensional index. For an algebraic
datatype, depending on the total number $m$ and the arity $k_{m}$ of
its various disjuncts, we may choose one of \ibx{product},
\ibx{enumerated}, \ibx{implicit}, or \ibx{explicit} representation.
In all cases except when there are more than one non-nullary disjuncts
present, we are able to choose an unboxed and untagged representation
for the datatype. In particular, when there is exactly one non-nullary
disjunct present, as in the case of the \ibx{list} datatype, we assume
that heap pointers can be distinguished from a small fixed range of
integers (say, 0-255), sufficient to represent all the nullary
disjuncts of the datatype and no explicit tag is necessary.  For some
applications, this may save a lot of space and time.

%If the algebraic
%datatype has only one disjunct (\ibx{product}), then no tag is
%necessary.  This is also how tuples and records are represented. If
%all disjuncts are nullary (\ibx{enumerated}), then we can encode the
%object by a small integer value. If there is exactly one non-nullary
%disjunct and some small number of nullary disjuncts (\ibx{implicit}),
%we can still avoid boxing every disjunct by encoding the nullary
%disjuncts with small integers and making sure that the global heap
%area starts beyond a small absolute address. With this convention, for
%example, list \ibx{cons}-cells can be represented without any tags
%which may constitute a major saving in space and time overhead for
%some applications. Finally, if there are more than one non-nullary
%disjuncts, we need an explicit tag to distinguish among them which is
%encoded as a small integer.

There are two more kinds of objects that are created and manipulated
indirectly at run-time by Id programs. These are {\it function
closures} and {\it activation frames}. In an implementation without
lambda-lifting and currying, function closures keep the values of the
free identifiers of a function obtained from its lexical environment.
In our implementation, all functions are already lambda-lifted, so the
closures carry just the curried arguments accumulated under partial
applications. We use the structure depicted in
\fig{reptn} which permits sharing of intermediate closures.

An activation frame is a temporary storage area used by an executing
function as a scratch pad keeping its input arguments and temporary
intermediate values. In Kernel Id, the bound variables of a function
constitute the intermediate values that need to be kept within its
activation frame for future use.\footnote{An intelligent compiler
back-end may be able to share some frame slots based on live-variable
analysis, but we are ignoring that issue here for simplicity.} The
frame also keeps the return continuation, consisting of the caller's
activation frame and the return instruction pointer.  In a sequential
system, activation frames are usually allocated on a stack. In our
parallel execution model, the linear stack of activation frames
generalizes to a tree and is managed explicitly by the run-time
system.

\subsection{Id Execution Model}

Id is a non-strict, parallel language with an eager evaluation
strategy. This implies that an Id program must be compiled and
executed in a multi-threaded fashion even on a sequential processor.
Parallel, multi-threaded architectures like Monsoon or *T directly
support this execution model in hardware, while software
multi-threading may be used in sequential workstations or in more
conventional parallel architectures like the CM-5.

\illfigure{model}{The Parallel Execution Model for Id.}

A program in Kernel Id consists of an expression query to be evaluated
within the scope of a set of top-level functions and type
declarations. The set of functions is compiled and loaded into the
program memory as code-blocks. The program starts by allocating a root
activation frame to evaluate the top-level program query. The parallel
execution model then unfolds the computation into a tree of function
activation frames distributed across the parallel machine (see
\fig{model}). The frame memory on each processor is separate from the
globally shared heap so it is easy to identify the dynamic tree of
activation frames at any given point. When the garbage collector is
invoked, we assume that all processor registers have been saved back
into the activation frame.  Therefore, the tree of activation frames
constitutes the root set of objects that need to be traversed for the
purpose of identifying all reachable heap objects.

