\section{The Tycoon Machine Language TML}
\label{Section:The Tycoon Machine Language TML}

%\section{Advantages of CPS}

Building on the experience gained with the first TML version that was
designed to be executed directly \cite{Matt93,Math92}, we have developed
a new intermediate representation that emphasizes easy program
compilation, transformation and analysis.  These goals are achieved by
representing programs in {\it Continuation Passing Style} (CPS) which
has been used successfully in several optimizing compilers for
functional languages \cite{App92,KKRHPA86,Kels89,Tedo91} as well as for
object-oriented languages \cite{Gawe92}.

CPS is a powerful yet simple program representation technique. The
advantage of CPS lies in the great reduction of the number of program
constructs that have to be handled by the Tycoon compile-time and
runtime (reflective) optimizer.

CPS is particularly well-suited for data flow analysis by making the
flow of control explicit through the uniform use of one language
construct: the procedure call. Since CPS does not have implicit
procedure returns, this language construct can be viewed as a
generalized \k{goto} with parameter passing \cite{Stee78}.

CPS has a simple and clean semantics based on the $\lambda$-calculus. TML
is effectively a call-by-value $\lambda$-calculus with store semantics. A
number of predefined {\em primitive procedures} (section
\ref{Section:Primitive Procedures}) operate on an implicit, hidden
store.

By representing programs in CPS, many well-known optimization techniques
become special cases of a few simple and general $\lambda$-calculus
transformations. Due to certain syntactical restrictions on the CPS
tree, these transformations can be applied freely even in the presence
of side-effecting calls to primitive procedures.
%## because applications might not be arguments contain any applications

Six different node types are sufficient to represent the data
structures for a TML tree (cf. appendix \ref{Section:TML Data
Structures}). This simplicity makes it possible to build compact
language processors like compiler front ends, back ends and
optimizers.

\begin{figure}[btp]

\include{tmlast}

\caption{Abstract Syntax for TML}
\label{Fig:TML AST}
\end{figure} 

%\pagebreak

\subsection{TML Abstract Syntax}
\label{Section:TML Abstract Syntax}

The abstract syntax of TML is given in figure \ref{Fig:TML AST}. The set
of literal constants (\p{Lit}) includes simple values such as integers,
characters and boolean values, as well as references {(\em object
identifiers, OIDs)} to complex objects in the store. These {\em values}
can be bound to {\em variables} (identifiers) by means of an {\em
application}. In the following example, an integer literal, a character
constant and an object identifier are bound to variables \p{i}, \p{ch}
and \p{oid}, respectively. These variables might be used as
values within the body \p{app} of the $\lambda$-abstraction (which in
turn must be an application):

\nopagebreak
\begin{xple}
    ($\lambda$(i ch oid) $app$
      13
      'a'
      $<\!oid 0x005b4780\!>$)
\end{xple}


{\em Abstractions} are also values in TML. This means that they may be
bound to variables and that these variables may be used in the
functional position ($val_0$ on the right hand side of the production
for $app$ in figure \ref{Fig:TML AST}) of an application. In the
following example, an abstraction with a single formal parameter \p{t}
is bound to the variable \p{fn}, and \p{fn} is used immediately within
an application of the abstraction, whereby \p{t} is bound to an integer
value:

\nopagebreak
\begin{xple}
    ($\lambda$(fn) (fn 13)
      $\lambda$(t) $app$)
\end{xple}


Although the semantics of TML is based on the general
$\lambda$-calculus, well-formed TML programs must satisfy a number of
additional constraints\footnote{It is important to note that these
contraints are never violated by any of the TML rewrite rules introduced
in chapter
\ref{Section:Optimization}.}:

\begin{enumerate}
\item A value used in the functional position of an application must, at
runtime, evaluate to an abstraction. Furthermore, this abstraction must
expect the same number of value and continuation arguments as the given
application, and it must expect them in the same order\footnote{We
currently investigate techniques for compiling and type-checking
variable-length argument lists. These techniques would merely weaken the
given well-formedness rule.}. This property is statically enforced by
the compiler front end that performs the necessary type checking on the
input to the TML code generator, rejecting any program that contains an
application which might violate this rule.

\item Similarly, an application of a primitive procedure must obey the
calling conventions of the primitive. Again, the compiler front end
(that generates calls to primitive procedures) has to enforce this
constraint on any input program.

\item Continuations may not {\em escape} (by binding them to value
identifiers), therefore, continuations are no first class values in TML.
It is not possible to store continuations in data structures where they
might subsequently be retrieved and applied.  This restriction allows
TML procedure calls to be compiled into efficient (stack based)
procedure calls and returns on stock hardware, so the main motivation
lies in the target code generator techniques we use. If we built a
somewhat more complex code generator that is able to deal with
first-class continuations, we could simply drop this restriction. The
rest of the compiler (e.g. the optimizer) would not be affected.

Several CPS-based compilers support continuations as first class values
\cite{App92,KKRHPA86,Kels89,Tedo91}. However, these compilers have to
translate source language constructs that capture the current
continuation, for example, the \p{call/cc} of SCHEME \cite{Stee86}, or
the built-in polymorphic function \p{callcc} of ML \cite{Repp90}).


\item Identifiers (value and continuation variables) may not be bound
more than once (unique binding rule), i.e. an identifier may occur only
once in at most one formal parameter list. For example, the following
two TML code fragments are not allowed:

  \begin{quote}
    \p{$\lambda$(x x)$app$}
    
    \p{$\lambda$(x)($\lambda$(x)$app$ $val$)}
  \end{quote}

This means that the TML code generator has to use fresh identifiers for
the parameter list of every new $\lambda$-abstraction. The TML optimizer
(section \ref{Section:Optimization}) and the target code generator
(section \ref{Section:Generating ANSI C Code}) rely heavily on this
property.

\item Abstractions that are used as values (that is, not as
continuations and not in functional position of applications) may
take an arbitrary number of value parameters, but they must take exactly
two continuation parameters: one for the {\em normal} continuation
(that receives the computed value) and one for the {\em exception}
continuation (that is invoked iff a runtime exception occurs, cf.
section \ref{Section:Exception Conversion}).

\end{enumerate}

Abstractions that are used as values correspond to first-class, user
level procedures. In order to make the printed TML representation used
in this document more readable, these procedures (\k{proc} abstractions)
are differentiated from continuations (\k{cont} abstractions) even
though both have the same internal representation (cf. appendix
\ref{Section:TML Data Structures}) and the same semantics
($\lambda$-abstractions). The differentiation is based on a purely
syntactic property of abstractions: a continuation does not take any
other continuation as a parameter. Thus, the parameter lists of
continuation abstractions do not contain any continuation variables. The
following two syntactic equivalences reflect these considerations $(n
\ge 0)$:

\begin{eqnarray*}
\fun{t_1..t_n}app 	 	& \equiv & \cont{t_1..t_n}app  \\
\fun{t_1..t_n\,c_e\,c_c}app	& \equiv & \proc{t_1..t_n\,c_e\,c_c}app
\end{eqnarray*}

\vspace{3ex}

%This separation of {\em values} from {\em continuations} allows
%certain constraints on their usage in TML programs to be expressed
%directy in the abstract syntax of TML.

\subsection{Primitive Procedures}
\label{Section:Primitive Procedures}

In TML, most of the `real work` needed to implement source language
semantics (e.g. integer arithmetik) is factored out into primitive
procedures which are not considered part of the intermediate language
itself.

\begin{figure}

\include{tmlprim}

\label{Fig:TML Primitives}
\caption{TML Primitives supporting TL source program compilation}
\end{figure} 

The set of primitive procedures handled by the current back end is
listed in figure 3.
%\ref{Fig:TML Primitives}.
Some examples of their
usage will be given in sections \ref{Section:Translating TL into TML}
and
\ref{Section:Target Machine Code Generation}.
By definition, each primitive calls exactly one of its continuation
arguments tail-recursively, passing the result of its computation, if
any. For example, some arithmetic primitives take two continuations: the
{\it normal} continuation which receives the calculated result, and an
{\it exception} continuation which is invoked if the primitive failes
due to overflow.

Although this set of predefined primitive procedures is rather small,
the set is not minimal due to efficiency tradeoffs. Moreover, it is
possible to define new primitive procedures in order to meet the
specific needs of more specialized source languages, for example
languages with a rich built-in object-oriented data model like Fibonacci
\cite{ABGO93}. These languages are often built on top of 
abstract machines with complex instruction sets.
%\cite{PHOLAMS}
The easiest way to support such complex instructions in TML is to define
new primitives that are mapped directly to the corresponding abstract
machine instructions during target code generation.

New primitive procedures can be defined at back end compile-time by
providing the following information to the generic TML rewriting tools:

\begin{enumerate}
\item A function to generate target machine code for a given call. This
  function is used by the code generator to map TML primitive
  procedure calls into sequences of target machine instructions.
\item A meta-evaluation function to perform optimizations on TML 
  nodes representing calls to this primitive procedure.
  This function is used by the optimizer to perform constant folding.
  To give an example, the primitive procedure '\p{+}' has an associated
  function that is able to reduce the TML application node
      \begin{quote}
      \p{(+ 1 2 c$_e$ c$_c$)}
      \end{quote}
  into an application of the continuation which represents {\em normal}
  (i.e. non-exceptional) execution with the result:
      \begin{quote}
      \p{(c$_c$ 3)}
      \end{quote}
      
\item A function to estimate the runtime cost of
  a given call (represented by a TML node) to the primitive procedure,
  measured in the number of instructions necessary to implement the
  primitive on an idealized abstract machine.  This function is used by
  the optimizer to estimate the possible savings resulting from the
  inlining of a TML procedure containing calls to the primitive.
  
\item A collection of attributes useful for the optimizer,
  for example commutativity, side effect classes
  \cite{GiLu86}, and flags to enable or disable certain
  optimization rules. There is a default value for any of these
  attributes, representing the worst possible case (i.e no further
  information available) for the optimizer.
\end{enumerate}

%This is an example how higher order language features
%lead to a very modular and extensible compiler.


%Calls to the following primitive procedure are
%generated during closure conversion (see section \ref{Section:Closure Conversion}):

%\nopagebreak

%\begin{tabular}{ll}
%(closure $p\:l\:g_1..g_nc$)   & Create a closure object with code p, \\
%                              & literal vector l and
%                                global variable values $g_1..g_n$ ($n \ge 0$)  
%\end{tabular}

\subsection{Exceptions}
\label{Section:Exceptions}

The following two approaches to handle exceptions in CPS have been
described by \cite{App92}:

\begin{enumerate}
\item A distinguished location that holds the current
exception handler is kept in the store. This handler is simply a
continuation taking one argument, the exception object.  Two primitive
procedures manipulate that location:

  \begin{description}
  \item[sethandler] installs a new handler (a continuation function), and
  \item[gethandler] retrieves it and passes it to its continuation argument,
  where it can subsequently be invoked.
  \end{description}

\item Every function accepts an additional argument, the exception
      continuation, which is normally passed through to other functions
      called.  To install a new handler, however, a new continuation
      function is passed which handles exceptions in the callee's body.
      The 'old' handler is remembered automatically within the lexical
      environment.

\end{enumerate}

Obviously, the second scheme is more in the spirit of continuation passing
style since it makes control flow explicit even in the presence of
exceptions. This approach has the advantage that exception {handling}
can be optimized immediately with ordinary optimization rules. This becomes
important when the optimizer is inlining functions that do extensive
exception {handling}.

In \cite{App92} it is claimed that the second scheme has an important
drawback which forced him to use the first variant in his compiler for
ML: the runtime system might not be able to locate the current exception
handler to raise a built-in exception like arithmetic overflow.

However, we think this drawback can easily be avoided by treating the
exception argument in a special way during target code generation.  In
our compiler, this is done anyway with the continuation argument, which
is passed as a return address on the stack at runtime with ordinary
procedure calls and returns. Thus, the implementation has the same
freedom as in the first scheme. Moreover, built-in exceptions like
arithmetic overflow are handled in TML simply by using primitive
procedures that accept an additional exception continuation.

Another drawback of the second scheme is that it does not handle
asynchronous exceptions like interupts, but we think that this kind
of exceptions should be handled somewhat different anyway, since a
thread's stack can be unwound only when the evaluator is in a consistent
state \cite{Repp90}. The same problem arises (and must be solved) by a
special asynchronous exception: memory overflow, signaled by the
underlying object store. When the garbage collector is invoked, every
thread must be in a well-defined state.
%(\cite{sml2c}).

We will transform the second scheme into a variant of first prior to
target code generation (see section \ref{Section:Exception Conversion}
about exception conversion).

\subsection{Compilation Phases}
\label{Section:Compilation Phases}

The Tycoon compiler front end performs syntactic analysis, TL abstract
syntax tree generation and semantic analysis (scoping and type
checking). The remaining compilation tasks are performed by the comiler
back end and are organized into the following phases:

\begin{enumerate}

\item \label{tmlcodegen}
     TML code generation: translation of typed TL abstract syntax
     trees into untyped TML trees, including cell conversion for
     mutable variable bindings (see section \ref{Section:L-Value Bindings}).
\item \label{alpha}
     $\alpha$-conversion: renaming of variables to avoid name clashes
     in later passes, in particular for the extensive tree rewriting
     performed by the optimizer in the next phase.
\item \label{optimize}
     TML code optimization (optional): this includes various
     optimizations like constant folding, dead code elimination and
     procedure inlining.
%\item \label{cellconvert}
%     Cell conversion: eliminating assignments to non-local variables
%     by explicit manipulation of the store.
\item \label{exception}
     Exception conversion: removing exception continuation arguments from
     procedures and procedure calls.
\item \label{analyze}
     Environment analysis: gathering information
     on the use of each variable, i.e. whether it is  referenced
     by closures.
\item \label{close}
     Closure conversion: eliminating non-local variable references.
\item \label{ccode}
     Target machine code generation.
\end{enumerate}

Note that these are only {\it conceptually} different phases.  For
efficiency reasons, several of them may be combined into a single pass
of the compiler. Phases \ref{tmlcodegen} to \ref{alpha} as well as Phases
\ref{analyze} to \ref{close} are currently merged into a single pass,
respectively.

The translation of TL into TML (step \ref{tmlcodegen}) is the topic of
the next section. During this pass, the $\alpha$-conversion (step
\ref{alpha}) of variable names is done as a side-effect of the TML tree
construction. Since a new TML variable node is created for each bound
variable, variables with the same name are distinguished by their
different object identities (object identifiers) of the corresponding
TML tree nodes.

After the TML tree is built, the (optional) optimization pass (step
\ref{optimize}) performs various source language and target machine
independent optimizations by extensive TML tree rewriting. We describe
the generic re-write rules for TML in section \ref{Section:Optimization}.

The phases \ref{exception} through \ref{close} rewrite the TML tree into
a somewhat simpler form that is easier to handle by the code generator
(step \ref{ccode}). The exception conversion pass (step
\ref{exception}) is described in section \ref{Section:Exception
Conversion}, whereas environment analysis (step \ref{analyze}) and
closure conversion (step \ref{close}) are summarized in section
\ref{Section:Environment Analysis and Closure Conversion}.  Finally, the
generation of executable target machine instructions (step
\ref{ccode}) is discussed in section \ref{Section:Generating ANSI C Code}.

