\section{Translating TL Source Programs into TML}
\label{Section:Translating TL into TML}

In this section, we discuss some TL source code examples and their
corresponding TML equivalents in order to give an idea of the overall
translation process.  For an introduction to TL see \cite{MMS94}.  When
a given TL expression is translated, there is always a {\em current
continuation} that denotes the continuation after evaluation of the
expression. This {\em normal} continuation will eventually receive the
computed value of the expression. Similarly, there is always a {\em
current exception continuation} that denotes the continuation if a
runtime exception is raised. Both continuations are initially given by
the top level loop of the Tycoon system that interactively reads a TL
expression, executes it and prints the result.

We will introduce the normal (current) continuation and the exception
continuation as formal parameters \p{cc} and \p{ce}, respectively, to
the translation function from TL to TML. We denote the translation
function with

\xbegin
\p{\lll{}E,ce,cc\ggg{}}
\xmiddle{}
\mv{T}\xend

in the following examples. It takes a TL expression $E$ in addition to
the two continuations $ce$ and $cc$, and produces a TML tree $T$. This
tree might in turn contain embedded recursive calls of the translation
function itself.

\subsection{Constants}
\label{Section:Constants}

Simple constants like numbers and string literals evaluate to
themselves. This is expressed in CPS by an application of the current
continuation, passing the constant as a parameter:

\xbegin
\lll{}1,ce,cc\ggg
\xmiddle{}
(cc 1)
\xend

\leaveout{\xbegin

{\bf{}TL}

\lll 1,ce,cc\ggg
\xmiddle{}

{\bf{}TML}

cc(1)
\xend}

\subsection{Bindings}
\label{Section:Bindings}

Sequential and parallel bindings are translated into nested
abstractions. Each value obtained by a recursive application of the
translation function (passing a new continuation) is bound to a TML
value identifier with the same name as the original TL identifier. We
indicate the sequential evaluation of the two subexpressions \p{A} and
\p{B} by printing them at the same indentation level, even though they
are properly nested within the TML data structure:

\xbegin
\lll\k{let} a = \mv{A} \k{let} b = \mv{B},ce,cc\ggg
\xmiddle{}
\lll\mv{A},ce, \k{cont}(a)        ; a is bound to the value of \mv{A}
\lll\mv{B},ce, \k{cont}(b)        ; b is bound to the value of \mv{B}
(cc b)\ggg\ggg               ; return the value of b \xend


\leaveout{
\xxbegin
\lll\k{let} a = \mv{A} \k{let} b = \mv{B},ce,cc\ggg
\xxmiddle{}
\contni{\xlat{\mv{A}}{ce}{\cont{a}{
\xlat{\mv{B}}{ce}{\cont{b}{
\applyi{cc}{b}}}}}}
\xxend}

%comment
%; a is bound to the value of \mv{A}
%; b is bound to the value of \mv{B}
%; return the value of b \xxcommentend

The translation of reecursive bindings is somewhat more comlicated and will be
discussed in section \ref{Section:Recursive Bindings}. Mutable bindings will
be discussed in section \ref{Section:L-Value Bindings}.

\subsection{Expressions}
\label{Section:Expressions}

Expressions that may contain embedded function calls are translated into
CPS by {\em flattening out} nested subexpressions. Recall that, in CPS,
arguments to procedure calls are restricted to be literal constants,
temporary variables, procedures or continuations (cf. figure
\ref{Fig:TML AST} on page
\pageref{Fig:TML AST}).  No nested procedure
calls (function applications) are allowed:

\xbegin
\lll\mv{F}(\mv{A,B}),ce,cc\ggg
\xmiddle{}
\lll\mv{F},ce, \k{cont}(f)
\lll\mv{A},ce, \k{cont}(a)
\lll\mv{B},ce, \k{cont}(b)
(f a b cc)\ggg\ggg\ggg
\xend

In the following example, the result of the whole
expression is bound to the temporary variable \p{t3}:

\xbegin
\lll{}1 + \{2 * 3\} -- 4,ce,cc\ggg
\xmiddle{}
(* 2 3 \k{cont}(t1)
(+ 1 t1 \k{cont}(t2)
(-- t2 4 \k{cont}(t3)
(cc t3))))
\xend

\subsection{Functions}
\label{Section:Functions}

Each TL function is translated into a TML \k{proc} abstraction by
adding two additional formal arguments to hold the two possible
continuations of a function call: the continuation that does exception
handling, and the continuation that accepts the return value of the
function. For example:

\xbegin
\lll{}\k{fun}(x,y :Int) \mv{S},ce,cc\ggg\xmiddle
(cc
  \k{proc}(x y e c)
    \lll\mv{S},e,c\ggg)\xend
    
Mutually recursive function bindings are translated into calls to the
primitive procedure \p{Y}. This is the (multiple-value-return) CPS
version of the $\lambda$-calculus fixed point operator. 
The abstraction given to the \p{Y}-primitive (cf. figure \ref{Fig:TML
Primitives} on page \pageref{Fig:TML Primitives}) takes $n$ abstraction
arguments $v_1..v_n$ and a continuation abstraction $c$, and returns
$n\!+\!1$ abstractions. As usual in CPS, this multiple-value-return is
expressed by calling the continuation $c$ with the desired return
values:

\begin{xple}
(Y $\lambda$(v$_1$..v$_n$ c)
     (c
       $abs_1$
       ..
       $abs_n$
       \k{cont}()$app$))
\end{xple}

The \p{Y}-primitive computes the least fixed point of its abstraction
argument. This fixed point is a vector of mutually recursive procedures
and/or continuations.  In other words, the neat effect of the
\p{Y}-primitive is that the $n\!+\!1$ abstractions $abs_1..abs_n$ and
{\k{cont}()$app$} are bound to the variables $v_1..v_n$ and $c$,
respectively, and that these bindings are {\em visible within the
abstractions themselves}. Moreover, the continuation {\k{cont}()$app$}
that is bound to $c$ is invoked tail-recursively after all the recursive
bindings have been established. 

A similar primitive is used in the ORBIT compiler \cite{KKRHPA86}. The
introduction of the \p{Y}-primitive obviates the need to extend the
intermediate language with a special recursive binding operator similar
to the \p{letrec} special form of SCHEME
\cite{Stee86}.
%: $Y$ For this
%function, $Y(f) = f(Y(f))$ holds for every function $f$.}:

In the following example, two mutually recursive functions are bound to
the identifiers \p{f} and \p{g}, and \p{g} is finally invoked:

\nopagebreak

\xbegin
\lll \k{let} \k{rec} f(a :Int):Int = \mv{F}
\k{and} g(b :Int) :Int = \mv{G}
g(13),
ce,
cc\ggg\xmiddle{}
(Y $\lambda$(f g c)
     (c
       \k{proc}(a e c) \lll{}\mv{F},e,c\ggg       ; function f
       \k{proc}(b e c) \lll{}\mv{G},e,c\ggg       ; function g
       \k{cont}() (g 13 ce cc)))         ; invoke g \xend
      
\subsection{Aggregates}
\label{Section:Aggregates}

Aggregate value constructors are translated into appropriate calls to
primitive procedures. The following code fragment creates a mutable array with
two slots and binds the result to the temporary variable \p{t}:

\xbegin
\lll\k{array} \mv{A} \mv{B} \k{end}, ce, cc\ggg\xmiddle{}
\lll{}\mv{A},ce,\k{cont}(a)
\lll{}\mv{B},ce,\k{cont}(b)
(array a b \k{cont}(t)
(cc t))\ggg\ggg\xend

%...tuple variants...simple tuples...subtyping...

\subsection{Recursive Bindings}
\label{Section:Recursive Bindings}

The translation of parallel recursive bindings is done
in four consecutive steps:

\begin{enumerate}
\item Allocation of aggregates.
\item Initialization of variables for simple bindings.
\item Binding of variables for functions using the primitive procedure
\p{Y}.
\item Initialization of aggregates.
\end{enumerate}

Here is an example of a mutually recursive value binding:
%##(note that this is impossible in ML \cite{}):

\xbegin
\lll\k{let} \k{rec} t = \k{tuple} f \k{end}
\k{and} f() = g(x f)
\k{and} x = h(99)
\k{and} g(a :Int b :Fun():Int) = t,
ce,
cc\ggg\xmiddle{}
(new 2 nil \k{cont}(t)   ; 1. Allocate aggregates
(h 99 \k{cont}(x)         ; 2. Inititalize simple bindings
(Y $\lambda$(f g c)            ; 3. Bind function variables
     (c
       \k{proc}(e c) (g x f e c)  ; function \p{f}
       \k{proc}(a b e c) (c t)    ; function \p{g}
       \k{cont}()                   ; 4. Initialize aggregates:
         (\arrayset{} t 0 1 \k{cont}()  ; tuple variant
         (\arrayset{} t 1 f \k{cont}()   ; tuple field
         (cc g)))))))           ; return the value of \p{g}\xend
               
\subsection{Conditionals}
\label{Section:Conditionals}

Conditionals are translated into calls to the primitive procedure
\p{'=='}, which does simple case analysis based on object identity
similar to the C language \k{switch} statement (cf. figure \ref{Fig:TML
Primitives} on page \pageref{Fig:TML Primitives}). Note how the current
continuation is bound to the variable \p{join} in order to avoid
duplicating code:

\xbegin
\lll\k{if} \mv{A} \k{then}
  \mv{B}
\k{else}
  \mv{C}
\k{end},
ce,
cc\ggg\xmiddle{}
\lll{}\mv{A},ce,\k{cont}(a)
($\lambda$(join)
    (== a true
      \k{cont}() \lll{}\mv{B},ce,join\ggg
      \k{cont}() \lll{}\mv{C},ce,join\ggg)
 cc)\ggg\xend

\subsection{Loops}
\label{Section:Loops}

Loops are translated into tail recursive procedure calls.  This is
another application of the \p{Y} primitive. Note that, in TL, any form
of loop statement (\k{loop}, \k{while}, \k{for}) yields the value
\k{ok} which is similar to \k{nil} in other languages:

\xbegin
\lll{}\k{loop}
  \mv{A}
  if \mv{B} then
    exit
  end
  \mv{C}
\k{end},
ce,
cc\ggg\xmiddle{}
($\lambda$(exit)
    (Y $\lambda$(loop c)
           (c
             \k{cont}()               ; loop head (bound to \p{loop})
                \lll{}A,ce,\k{cont}(ignore)
                \lll{}B,ce,\k{cont}(b)
                (== b true exit       ; exit test
                  \k{cont}() \lll{}C,ce,\k{cont}(ignore)
                  (loop))\ggg)\ggg\ggg     ; continue loop
             \k{cont}() (loop))           ; loop entry (bound to \p{c})
   \k{cont}()                               ; loop exit label (bound to \p{exit})
    (cc \k{ok})) ; yield \k{ok} \xend
                

Note that \p{loop} always denotes the same, statically determinable
continuation, and that \p{loop} is used in functional position only
(i.e. it does not escape \cite{App92}).  This property is also an
invariant of the optimization rules.  So this translation of loops into
recursive continuations does not imply the introduction of first-class
continuations in TML with associated runtime cost. There is no need to
actually allocate a variable cell holding a reference to a
``continuation object'' for \p{loop}, and, since there are no \k{proc}
abstractions between the loop head and the exit instructions (enforced
by source level restrictions and optimization invariants), the loop exit
and loop continuation instructions will be translated into simple jumps
(C language gotos) without special tricks, even if the optimization
phase is skipped.


\subsection{Case Statements}
\label{Section:Case Statements}

Case statements are translated into calls to the primitive procedure
'\p{==}' applied to the tuple variant code (an integer value). Note
again that the current continuation as well as the case branches are
encapsulated using continuations to avoid duplicating code:

\xbegin
\lll\k{Let} T = \k{Tuple}
  \k{case} mon,tue,wed,thu,fri,sa,so
\k{end}
\k{let} t :T = \mv{X}
\k{case} t
  \k{when} mon,tue \k{then} \mv{A}
  \k{when} wed, thu, fri \k{then} \mv{B}
  \k{else} \mv{C}
\k{end},
ce,
cc\ggg\xmiddle{}
($\lambda$(join)
    \lll{}\mv{X},ce,\k{cont}(t)    ; evaluate tuple value
    (\arrayget{} t 0 \k{cont}(v)     ; extract tuple variant
    ($\lambda$(c1 c2 c3)
          (== v 1 2 3 4 5 c1 c1 c2 c2 c2 c3)
       \k{cont}() \lll{}\mv{A},ce,join\ggg
       \k{cont}() \lll{}\mv{B},ce,join\ggg
       \k{cont}() \lll{}\mv{C},ce,join\ggg))\ggg
 cc)\xend

\subsection{Exception Handling}
\label{Section:Exception Handling}

Exception handlers are translated into appropriate continuation
passings: a function `installs' a new handler by binding it to a
continuation variable (denoted by \p{e} in the following example) and
passing it to subsequent function calls:

\xbegin
\lll\k{try}
  \mv{S}
  \k{when} \mv{E1} \k{then} \mv{V1}
  \k{when} \mv{E2} \k{then} \mv{V2}
  \k{else} \k{reraise}
  \k{end},
ce,
cc\ggg
\xmiddle{}
($\lambda$(join)
    ($\lambda$(ce2) \lll{}\mv{S},ce2,join\ggg
      \k{cont}(exc)                    ; handler, bound to ce2
        \lll\mv{E1},ce,\k{cont}(e1)
        \lll\mv{E2},ce,\k{cont}(e2)
        (\arrayget{} exc 0 \k{cont}(excId)   ; extract the exception id
        (== excId e1 e2
          \k{cont}() \lll{}\mv{V1},ce,join\ggg        ; excId == e1
          \k{cont}() \lll{}\mv{V2},ce,join\ggg        ; excId == e2
          \k{cont}() (ce exc))))\ggg\ggg       ; else reraise
  cc)  ; current continuation, bound to join \xend

A \k{raise} statement is translated into an application of the current
exception continuation, passing an exception object as the argument:

\xbegin
\lll\k{raise} \mv{E} \k{with} \mv{V} \k{end},
ce,
cc\ggg\xmiddle{}
\lll{}\mv{E},ce,\k{cont}(e) 
\lll{}\mv{V},ce,\k{cont}(v) 
(vector e v \k{cont}(exc)  ; create exception object
(ce exc))\ggg\ggg            ; raise \xend

\subsection{C Language Function Calls}
\label{Section:C Language Function Calls}


It is often necessary to be able to use existing external services
written in other programming languages. The \p{ccall} primitive provides
a way to call C language functions from within TL
programs\footnote{These functions are typically bundled within a
dynamic link library, even though it is possible to call C language
functions that are statically linked to the Tycoon runtime system.}. The
inverse direction, i.e. calling TL functions from within C code, is
implemented in C within the Tycoon runtime system, accessible for the
Tycoon programmer via the ordinary \p{ccall} mechanism.

The \p{ccall} primitive takes a format string describing the parameter
and result types (used for data representation conversion), an array
object describing the desired C language function (essentially two
strings describing the library and entry point where the compiled
function code can be found), and a continuation which receives the
return value.

The predefined polymorphic TL function \p{bind} can be used to establish
a binding to a C language function. The following code
fragment defines a TL function that calls the standard C function
\p{strlen}. The function \p{raiseCCallError} is called to raise an exception
if the \p{ccall} primitive fails. This may be the case when the given library
does not exist, or it does not contain a function with the given name:

\xbegin
\lll\k{let} strlen =
  bind(:Fun(s :String):Int
    "/usr/local/lib/libc.so"
    "strlen"
    "si"),
ce,
cc\ggg\xmiddle{}
(array "/usr/local/lib/libc.so" "strlen" \k{cont}(cfn)
($\lambda$(strlen) (cc strlen)  
  \k{proc}(s e c)
    ($\lambda$ (fail) (ccall "si" cfn s fail c)
      \k{cont}()
        (raiseCCallError
          "/usr/local/lib/libc.so"
          "strlen" "si" e c))))\xend

\subsection{Builtin Functionality}
\label{Section:Builtin Functionality}

Some TML primitives can be utilized explicitely from within TL source
programs by means of the predefined polymorphic function
\p{builtin}. This is useful for some frequently-used low-level
operations like integer arithmetic for which an equivalent
implementation using C calls would be too inefficient. The function
\p{builtin} is a mapping of strings and TL functions of a given type to
a function of the same type:

\begin{xple}\sf builtin :\k{Fun}(\k{Dyn} FctType $<:$\k{Ok} name :String  ifFail :FctType) :FctType \end{xple}

This mapping is implemented within the Tycoon compiler. The name string
tells the compiler about the desired semantics of the result, whereas
the function parameter \p{ifFail} provides a convenient hook in the case the
TML primitive fails. This leaves the relatively complex task of
exception handling to the higher language level, rather than beeing
hard-wired into the compiler.

To give an example, a TL function performing integer division can be
defined using the \p{"int~/"} builtin:

\xbegin
\lll\k{let} / =
  builtin(:\k{Fun}(:Int :Int) :Int
    "Int /"
    \k{fun}(x,y :Int) \k{raise} intError),
ce,
cc\ggg\xmiddle{}
($\lambda$(/) (cc /)
  \k{proc}(x y e c)
    ($\lambda$(fail) (/ x y fail c)
      \k{cont}()
        (vector intError \k{cont}(exc)
        (e exc)))) \xend

In this code fragment, the (globally defined) exception \p{intError}
will be raised in case of a division-by-zero error.

\subsection{L-Value Bindings}
\label{Section:L-Value Bindings}

TML does not allow lambda variables to be modified once they are
bound. This means that mutable variable bindings must be translated into
explicit manipulation of the store by means of TML primitives. A
store object (heap memory cell) is allocated for each mutable TL
variable that holds the variables value at runtime, introducing a level
of indirection for variable access ({\em Cell Conversion} \cite{KKRHPA86}):

\xbegin
\lll\k{let} var a = \mv{A},ce,cc\ggg
\xmiddle{}
\lll\mv{A},ce,\k{cont}(t)      ; t is bound to the value of \mv{A}
(array t \k{cont}(a)     ; allocate memory cell for a
(\arrayget{} a 0 cc))\ggg        ; return the value of a \xend

In TL, it is also possible to pass a reference to a mutable variable
binding (i.e. an {\em L-value}) to a user-defined function. Such a {\em
call-by-reference} parameter is translated into two {\em call-by-value}
parameters in the TML representation, passing base address and offset of
the memory cell (or, in Tycoon Store Protocol terminology
\cite{Matt93}, the object identifier (OID) and the slot index):

\xbegin
\lll\k{let} inc(\k{var} x :Int) = x := x+1
inc(a), ce, cc\ggg\xmiddle{} ($\lambda$(inc) (inc a 0) \k{proc}(xBase
xOffset e c) (\arrayget{} xBase xOffset \k{cont}(t1) ; retrieve value of
x (+ t1 1 \k{cont}(t2) (\arrayset{} xBase xOffset t2 c)))) ; change
value of x \xend

The offset of the mutable memory cell might become non-zero when mutable tuple
components or array slots are passed as L-values:

\xbegin
\lll\k{let} k = \k{array} 1 2 3 \k{end}
inc(k[2]),
ce,
cc\ggg\xmiddle{}
(array 1 2 3 \k{cont}(k)
(inc k 2 ce cc)) \xend

The TL assignment operator is defined as a polymorphic function within the
programming environment. A call-by-reference parameter and the predefined
function \p{builtin} is used in the definition. Note that the exception
handling code will be removed by the optimizer as dead code:

\xbegin
\lll\k{let} := = builtin(
    :\k{Fun}(A $<:$ \k{Ok} \k{var} lhs: A rhs :A ):\k{Ok}
    ":="
    \k{fun}(A $<:$ Ok var lhs: A rhs :A ):\k{Ok}
      \k{raise} \k{exception} "none"),
ce,
cc\ggg\xmiddle{}      
($\lambda$(:=) (cc :=)
  \k{proc}(lhsBase lhsOffset rhs e c)
    ($\lambda$(fail)
        (\arrayset{} lhsBase lhsOffset rhs \k{cont}()
        (c \k{ok}))
      \k{cont}()
        (\k{vector} "none" \k{cont}(exc)
        (e exc)))) \xend

