% File:     tml.tex
% Date:     21-JUN-1995
% Author:   Andreas Gawecki, Florian Matthes
%
\documentstyle[epsf,tml,snamed]{llncs}

\begin{document}

\title{\parbox{12.5cm}{{\footnotesize\vspace*{-1cm}Appeared in: \e{Proceedings of the 5th Conference on Extending Database Technology, EDBT'96}, Avignon, France, March 1996. Springer Verlag.}}\\
$ $\\
Exploiting Persistent Intermediate Code Representations\\
in Open Database Environments\thanks{
This research is supported by ESPRIT Basic Research, Project FIDE,
\#6309 and by a grant from the German Israeli Foundation for Research
and Development (\e{bulk data classification}, I-183 060).
}}

\author{Andreas Gawecki \quad Florian Matthes}

\institute{
Universit\"at Hamburg, Vogt-K\"olln-Stra{\ss}e 30 \\
D-22527 Hamburg, Germany \\
%Phone: +49 40 54715 332\\
%Fax: +49 40 54715 328\\
\{gawecki,matthes\}@informatik.uni-hamburg.de}

\maketitle
\thispagestyle{empty}

\begin{abstract} \noindent Modern database environments have to execute, 
store, analyze, optimize and generate code at various levels of
abstraction (queries, views, triggers, query execution plans, methods,
4GL programs, etc.).  We present TML, an abstract persistent intermediate
code representation developed in the Tycoon\footnote{Tycoon: Typed
Communicating Objects in Open Environments.} project to fully integrate
static and dynamic code analysis and rewriting.  TML is a continuation
passing style (CPS) language which excels in its explicit, high-level
representation of control and data dependencies.  We formally define TML
and its core rewrite rules which unify many well-known optimizing
transformations.  We also present Tycoon's innovative reflective system
architecture which supports modular compile-time as well as global
runtime optimizations.  Moreover, we describe how this architecture
enables optimizations across abstraction barriers in large modular
persistent applications including embedded declarative queries.
\end{abstract}

\leaveout{
\noindent \k{Keywords:} Code Representation, Code Optimization, Query 
Optimization, Continuation Passing Style, Persistent Systems, Term 
Rewriting, Reflection, Lambda Calculus.
}

\section{Introduction and Motivation}

The traditional focus of database language research has been on
high-level languages for data access and manipulation (query languages,
trigger definition languages, 4th generation languages, script languages)
or on implementation-oriented languages which capture the characteristic
operations of a specific target system at hand (relational algebra,
object algebra, structural recursion, \ldots).

A closer look at tools working on such code representations like query
and program optimizers reveals a large number of common tasks which at
present are addressed with often incompatible technologies:

\begin{itemize} 
\item Binding analysis: Which entity (table, index, view, 
function, method, variable, etc.) is denoted by an identifier? Are there
multiple references to the same entity?
\item Identifier substitution by a bound value or expression: View 
expansion, procedure or method inlining, constant folding, substitution of 
host programming language parameters, etc.
\item Free variable analysis: Does a variable appear in a query predicate? 
Does a procedure depend on global variables? Does a query contain 
programming language variables? Are there independent subexpressions? Which 
base relations appear inside an integrity constraint?
\end{itemize} 
After a decade of experience with building integrated database programming
environments \cite{Schm77a,MRS84,ScMa94} and successive versions of optimizers
for their query languages \cite{JaSc82b,JKMS82,JaKo84,BJS86,ERMS91}, we made
the radical decision to replace special-purpose representations for queries,
programs and scripts with a single, expressive \e{intermediate} language.  We
thereby avoid incompatibilities and redundancies arising from the repeated
implementation of the above functionality.

In this paper, we present the Tycoon Machine Language (TML), the common
abstract persistent intermediate code representation used for local
compile-time as well as global runtime optimizations in the Tycoon system
developed at the University of Hamburg.  The development of TML was influenced
heavily by continuation passing style (CPS) representations found in modern
optimizing compilers for functional, imperative and
object-oriented languages \cite{Appe92,KKRHPA86,Kels89,Teod91,Gawe92a}.

TML inherits the advantages of CPS representations which support a wide
range of algorithmically-complete languages, multiple front-ends and
back-ends and cross-language optimization. To address the specific needs
of database environments, TML also supports optimizations based on
runtime bindings to arbitrary complex values in the persistent store
and mechanisms to work with persistent TML terms attached to executable
code.

The paper is organized as follows: In section~\ref{Section:The Tycoon
Machine Language TML} we present the abstract syntax and semantics of
the CPS-based intermediate representation TML. The core rewrite rules on
TML terms are described in section~\ref{Section:TML Rewrite Rules}.
Examples are then given of innovative code optimization architectures
which exploit the availability of persistent TML terms at runtime
(section~\ref{Section:Reflective Opt}.  A full description of TML and
its rewrite rules can be found in
\cite{GaMa94,Kira94}.  The paper ends with a perspective on future research 
work and on other innovative application domains for uniform persistent 
code and query representations in the spirit of TML.

%-----------------------------------------------------------------------------

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

This section presents the CPS-based intermediate representation TML
(Tycoon Machine Language) which is used for integrated program and query
compilation, transformation and analysis, both at compile time and at
runtime.

\subsection{Advantages of CPS Intermediate Representations}

Continuation Passing Style (CPS) is a powerful yet simple program
representation technique.  Using continuations, various control
structures commonly found in programming languages such as conditionals,
(non-block-structured) loops and exception handling can be expressed
quite naturally.  While this is also true for many other intermediate
representations such as triples or quadrupels, the main advantage of CPS
lies in the great reduction of the number of program constructs which
have to be handled by the compile-time and runtime optimizer while
preserving much of the structural information of the source language
input.

CPS representations are well-suited for machine analysis by making the
flow of control and of data 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 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.

CPS supports higher-order languages, i.e.  languages where functions may 
take other functions as arguments.  For example, the selection operation 
$\sigma_p(R)$ in relational algebra takes two arguments, a range relation 
$R$ and a selection predicate $p$ where $p$ can be understood as a boolean 
function on the element type of $R$. 

Like terms in the $\lambda$-calculus, CPS terms provide an integrated 
representation of code fragments and their associated data bindings.  To 
meet the specific requirements of persistent languages and database 
languages, TML terms may contain simple literal values and object 
identifiers which denote arbitarily complex objects (tables, indices, ADT 
values) in the persistent Tycoon object store.

By representing programs in CPS, many well-known program and algebraic
query optimization techniques become special cases of a few simple and
general $\lambda$-calculus transformations.  These transformations can
be applied freely even in the presence of nonterminating computations
and/or side-effecting calls to primitive procedures. This is due to the
syntactical restrictions on CPS terms (see Sec.~\ref{Section:TML
Abstract Syntax}) which require actual parameters to function calls to be
constants, variables or abstractions. 

Six different node types are sufficient to represent the data structures
for a TML tree.  This simplicity facilitates the construction of compact
language processors like compiler front ends, back ends and optimizers.

\begin{figure}[btp]
\fbox{\vbox{
\begin{tabular}{ll}                               
$lit \in Lit$	    & \p{Literal constants (including object identifiers)}\\
\p{t $\in$ Temp}    & \p{Temporary variables} \\
\p{c $\in$ Cont}    & \p{Continuation variables} \\
\p{prim $\in$ Prim} & \p{Primitive procedures (procedure constants)}\\
\end{tabular}

\begin{tabular}{lcll}                             
$v$   & $::=$ & $t$ $|$ $c$              & \p{Variables} \\
$val$ & $::=$ &	$lit$ $|$ $v$ $|$ $abs$  & \p{Values} \\
$abs$ & $::=$ & $\lambda(v_1..v_n)\,app$ & \p{Abstractions, n $\ge$ 0} \\
$app$ & $::=$ & $(val_0\,val_1..val_n)$  & \p{Applications, n $\ge$ 0} \\
      & $|$   & $(prim\,val_1..val_n)$   &    
\end{tabular}
}}

\caption{Abstract Syntax for the Tycoon Machine Language TML}
\label{Fig:TML AST}
\end{figure} 


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

The complete abstract syntax of TML is defined 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 persistent
object store.  These {\em values} can be bound to language {\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, i.e.  TML is a higher-order 
language.  This means that abstractions may be bound to variables and that 
these variables may be used in the functional position of an application 
($val_0$ on the right hand side of the production for $app$ in figure 
\ref{Fig:TML AST}). In TML, the body of an abstraction must be an
application, and applications are surrounded by parentheses. Therefore,
the scope of the abstraction is unambiguous.  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
constraints are never violated by any of the TML rewrite rules introduced
in section \ref{Section:TML Rewrite Rules}.}:

\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 which performs the necessary type checking on the
input to the TML code generator, rejecting any program which 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
(which 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 not first-class values in TML.  
It is not possible to store continuations in data structures where they 
might be retrieved and applied subsequently.  This restriction allows TML 
procedure calls to be compiled into efficient (stack based) procedure calls 
and returns on stock hardware, i.e.  the main motivation behind this 
restriction lies in the target code generation techniques we use.

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

\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:TML Rewrite Rules}) and the target code generator rely
heavily on this property.

\item Abstractions which 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 (which
receives the computed value) and one for the {\em exception}
continuation (which is invoked if a runtime exception occurs).

\end{enumerate}

Abstractions which are used as values correspond to first-class, user
level procedures. In order to make the printed TML representation used
in this paper more readable, these procedures (\k{proc} abstractions)
are differentiated from continuations (\k{cont} abstractions) even
though both have the same internal representation 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*}


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

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

A typical set of primitive procedures used for the compilation of a
fully-fledged imperative, algorithmically-complete polymorphic
programming language (TL \cite{MaSc92a})) is listed in
figure~\ref{Fig:TML Primitives}. 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 {\em normal} continuation which
receives the calculated result, and an {\em exception} continuation
which is invoked if the primitive fails due to overflow or division by
zero.

Although the set of predefined primitive procedures is typically chosen
to be rather small, the set does not need to be minimal due to
efficiency tradeoffs.  Moreover, it is possible to add new primitive
procedures in order to meet the specific needs of more specialized
source languages (e.g., supporting multiple bulk data types or
scientific or statistical databases).  The easiest way to support such
complex instructions in TML is to define new primitives which are mapped
directly to 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
or calls to the underlying runtime system.

\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 and dead code elimination.  To 
give an example, the primitive procedure '\p{+}' has an associated function 
which 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}

\noindent Note that exception handling is expressed in TML by passing
continuations: Every function accepts an additional argument, the exception
continuation, which is normally passed through to other functions called.  To
install a new exception handler, however, a new continuation function which
handles exceptions in the callee's body is passed.  The 'old' handler is stored
automatically within the lexical environment.

\begin{figure}\small

\fbox{\vbox{
\begin{tabular}{ll}                              
($p\:val_1\:val_2\:c_e\:c_c$)         & integer arithmetic, $p \in \{+, -, *, /, \%\}$ \\
($p\:val_1\:val_2\:c_1\:c_2$)         & integer comparison,
				    $p \in \{<, >, <=,>=\}$ \\
($p\:val_1\:val_2\:c$)          & bit operations on integers,
			     $p \in \{<<, >>, \&, |, \hat{~}, \tilde{~}\}$ \\

(char2int $val\:c$)  & convert a byte to an integer value \\
(int2char $val\:c$)  & convert an integer to a byte value \\

(array \pvec{val} $c$)  & create a mutable array holding $n$ object references \\
(vector \pvec{val} $c$) & create an immutable array \\

(new $val_1\:val_2$ $c$)       & create a mutable array holding $val_1$ object \\
                               & references, initialized with $val_2$ \\
(\$new $val_1\:val_2$ $c$)
  & create a mutable byte array holding $val_1$ simple \\
  & byte values, initialized with $val_2$ \\
  
(\arrayget{} $val_1\:val_2\:c$)          & array access: indirect indexed load    \\
(\arrayset{} $val_1\:val_2\:val_3\:c$)   & array update: indirect indexed store \\
(\$\arrayget{} $val_1\:val_2\:val_3\:c$) & byte array access   \\
(\$\arrayset{} $val_1\:val_2\:val_3\:c$) & byte array update \\

(== $val$            & case analysis based on object identity with\dots  \\
 \hspace{5mm}\pvec{val}      & values  and\dots              \\
 \hspace{5mm}\pvec{c} [$c_{n+1}$]) & branches (optional else branch)  \\
 
(Y \fun{c_0\,\pvec{val}\,c}{app})	   & the Y combinator\\

(size $val\:c$)                  & array or byte array size (in slots) \\
(move $val_1\dots val_5\:c$)
  & move array contents \\
(\$move $val_1\dots val_5\:c$)
  & move bytearray contents \\
(ccall $val_{fmt}\:val_{cfn}\:c_1\:c_2$)
  & C language function call \\
%(move {\it n src srcOffs dst dstOffs c})     & move array contents \\
%(\$move  {\it n src srcOffs dst dstOffs c})  & move bytearray contents \\
%(ccall {\it fmt cfn $c_1\:c_2$})                 & C language function call \\

(pushHandler $c_1\:c_2$)   & Install continuation \p{c$_1$} as a new \\
                           & exception handler, continue with \p{c$_2$} \\
(popHandler $c$)       & Remove the topmost exception handler, \\
		       & continue with  \p{c} \\
(raise $val$)            & Raise exception
\end{tabular}
}}

\caption{TML primitives for the compilation of an imperative programming 
language}
\label{Fig:TML Primitives}
\end{figure} 

This approach makes control flow explicit even in the presence of 
exceptions, with the advantage that exception {handling} can be optimized 
immediately without special optimization rules.  This becomes important when 
the optimizer is inlining functions which perform extensive exception 
{handling}, which is quite common in high-level value-oriented languages.

The primitive procedure Y is a multiple-value-return CPS version of the
lambda-calculus fixed point operator. The abstraction given to the
Y-primitive takes $n$ abstraction arguments $v_1..v_n$ and a continuation
abstraction $c_0$, 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.

The 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 effect of the
Y-primitive is that the $n+1$ abstractions
\p{\k{cont}()app} and $abs_1..abs_n$ are bound to the variables $c_0$
and $v_1..v_n$, respectively, and that these bindings are visible within
the abstractions themselves. Moreover, the continuation
\p{\k{cont}()app} which is bound to $c_0$ is invoked tail-recursively (by
Y) after all the recursive bindings have been established.

To give a simple example, a loop which iterates from 1 up to 10, written
in the Tycoon Language as \p{\k{for} i = 1 \k{upto} 10 \k{do} f(i)
\k{end}} is expressed in TML as follows:

\begin{xple}
(Y \k{proc}(c$_0$ for c)
      (c
        \k{cont}()                     ; continuation, bound to c$_0$
          (for 1)                   ; loop entry
        \k{cont}(i)                    ; loop head, bound to 'for'
          ($>$ i 10 cc \k{cont}()     ; loop exit
          (f i ce \k{cont}(t1)        ; loop body
          (+ i 1 ce \k{cont}(t2)    
          (for t2))))))            ; recursion
\end{xple}

As usual, \p{cc} and \p{ce} represent the current normal and the current
exception continuation, respectively. 
The introduction of the Y-primitive obviates the need to extend the
intermediate language with a special recursive binding operator similar
to the letrec special form of SCHEME. A similar primitive is used in the
ORBIT compiler \cite{KKRHPA86}.

The set of TML primitives is described in more detail with additional
examples in \cite{GaMa94,Kira94}.

%-----------------------------------------------------------------------------

\section{Analysis and Rewriting of TML Intermediate Representations}
\label{Section:TML Rewrite Rules}

We have organized the TML optimizer into two separate passes, namely a
\e{reduction} pass and the \e{expansion} pass.
During the reduction pass, a number of generic rewrite rules are applied
to the TML tree until no more rules are applicable.  Termination is
guaranteed because each of the rewrite rules reduces the size of the TML
tree if it is applied.

The subsequent expansion pass tries to substitute bound 
$\lambda$-abstractions (procedures or continuations) at the positions where 
they are applied.  Effectively, this CPS transformation performs {\em 
procedure inlining} in terms of traditional compiler optimization or view 
expansion in database terminology.  The decision whether a given use of a 
bound abstraction is to be substituted is based on a heuristic cost model 
similar to the one described by \cite{Appe92}.

When one or more abstractions are substituted during the expansion pass, 
there usually is the opportunity to perform more reductions on the TML tree 
(this is indeed the main reason why inlining is performed in programming 
languages at all), so each expansion pass is followed by a reduction pass.  
Likewise, the reduction pass may reveal new opportunities to perform 
expansions, so the two passes are applied repeatedly until no more changes 
are made to the TML tree.  To guarantee the termination of this process 
even in obscure cases, a penalty is accumulated at each round of the 
reduction/expansion phases.  The optimization process stops when this 
penalty reaches a certain limit.

In the following, we give a formal definition of the core TML rewrite
rules. We present these rules using the notation

\tmlrewritep{rule name}{(precondition)}{A}{B}

indicating that the TML expression $A$ may be rewritten to the TML 
expression $B$ if $precondition$ evaluates to true.  By convention, an 
empty precondition evaluates to true.

A key feature of CPS-based representations is the fact that control and 
data dependencies are captured uniformly by the concept of bound variables 
(variable occurrences inside the scope of a binder).  In the precondition, 
we denote the number of occurrences of a variable $v$ in an TML expression 
$E$ with $\tmlrefcount{E}{v}$.  This function is defined inductively on the 
abstract syntax of TML as follows:

\begin{center}
\begin{tabular}{rcl}
$ \tmlrefcount{v}{v} $ & = & $ 1 $ \\
$ \tmlrefcount{lit}{v} $ & = & $ 0 $ \\
$ \tmlrefcount{prim}{v} $ & = & $ 0 $ \\
$ \tmlrefcount{v_1}{v_2} $ & = & $ 0 \quad (v_1 \neq v_2) $ \\
$ \tmlrefcount{\lambda{}(v_1..v_n)\:app}{v} $ & = &
  $ \tmlrefcount{app}{v} $ \\ %\hspace{-4pt}
$ \tmlrefcount{(val_0\:val_1..val_n)}{v} $ & = & $ 
   \sum_{i=0}^n \tmlrefcount{val_i}{v} $ \\
\end{tabular}
\end{center}

Similarly, on the right side of a TML rewrite rule, we use the notation 
$\tmlsubst{E}{val}{v}$ which denotes the expression $E$ where every 
occurrence of the variable $v$ is replaced by the value $val$.  Name clashes 
cannot occur during substitution because each variable is bound only once 
in a TML tree (unique binding rule).  This property is achieved by the {\em 
$\alpha$-conversion} performed during TML code generation, and is never 
violated by any of the TML rewrite rules, except in one case: if, in an 
application of the substitution rule, the value substituted is an 
abstraction, the formal parameters of this abstraction occur temporarily at 
two different places within the TML tree.  However, this does not do any 
harm because the first occurrence of the abstraction will be removed 
immediately (by an application of the rewrite rule {\em remove}) since the 
substituted variable is not referenced any more.

Variable substitution is defined inductively on the abstract syntax
of TML as follows:

\begin{center}
\begin{tabular}{rcl}
$ \tmlsubst{v}{val}{v} $ & = & $ val $ \\
$ \tmlsubst{v'}{val}{v} $ & = & $ v' \quad (v \neq v') $ \\
$ \tmlsubst{lit}{val}{v} $ & = & $ lit $ \\
$ \tmlsubst{prim}{val}{v} $ & = & $ prim $ \\
$ \tmlsubst{\{\lambda{}(v_1..v_n)\:app\}}{val}{v} $ & = & $ %\hspace{-4pt}
   \lambda{}(v_1..v_n)\:\{\tmlsubst{app}{val}{v}\} $ \\
$ \tmlsubst{(val_0\:val_1..val_n)}{val}{v} $ & = & $
   (\tmlsubst{val_0}{val}{v}\:\tmlsubst{val_1}{val}{v}..\tmlsubst{val_n}{val}{v}) $ \\
\end{tabular}
\end{center}

Values bound to $\lambda$-variables may be substituted freely within the
TML tree since, due to CPS, they are not allowed to contain nested
primitive or function calls which may cause side effects in the store.

The complete set of the TML rewrite rules which is currently implemented as a
part of the reduction pass is given below.  The expansion pass uses a 
variant of the $subst$ rewrite rule in order to perform procedure inlining. 
 Although each individual rule is fairly simple, the combination of these 
rules is surprisingly powerful.  Many of the well-known standard program 
optimizations like constant and copy propagation, dead code elimination, 
procedure inlining or loop unrolling are just special cases of these 
general $\lambda$-calculus transformations.

The \p{subst} rewrite rule replaces each occurrence of a bound variable
$v_i$ with the corresponding value $val_i$. Note that the precondition
of this rule states that, if the value $val_i$ is an abstraction, the
variable $v_i$ must be referenced exactly once. This precondition
prevents the TML code from growing arbitrary large:

\tmlrewritep{subst} % $v_i$}
    {(val_i \not\in Abs \vee \tmlrefcount{app}{v_i} = 1)}
    {\applybbi{\fun{v_1..v_i..v_n}
                   {app}}
              {val_1..val_i..val_n}}
    {\applybbi{\fun{v_1..v_i..v_n}
                   {\tmlsubst{app}{val_i}{v_i}}}                
              {val_1..val_i..val_n}}

The \p{remove} rewrite rule strikes out a bound variable $v_i$ which is
not referenced any more.  The corresponding value $val_i$ is also
removed.  Note that this is possible because, due to syntactical
restrictions (cf.  figure \ref{Fig:TML AST}), $val_i$ cannot be an
application, and, therefore, cannot contain any calls to side-effecting
primitive procedures:

\tmlrewritep{remove} % $v_i$}
    {(\tmlrefcount{app}{v_i} = 0)}
    {\applybbi{\fun{v_1..v_i..v_n}
                   {app}}
              {val_1..val_i..val_n}}
    {\applybbi{\fun{v_1..v_{i-1}\:v_{i+1}..v_n}
                   {app}}
              {val_1..val_{i-1}\:val_{i+1}..val_n}}

The \p{reduce} rewrite rule simply removes applications of 
$\lambda$-abstractions which do not bind any variables:

\tmlrewrite{reduce}
    {\applyi{\fun{}{app\!}}{}}
    {app}
             
The \p{$\eta$-reduce} rewrite rule removes unnecessary abstractions:

\tmlrewritep{$\eta$-reduce}
    {(\forall_{i = 1\ldots n}\:\tmlrefcount{val}{v_i} = 0)}
    {\fun{v_1..v_n}
        {\applyi{val}
                {v_1..v_n}}}
    {val}
       
The \p{fold} rewrite rule uses an evaluation function {\it eval} which
knows details of the semantics of primitive procedures:

\tmlrewrite{fold} % p}
    {\applyi{prim}
            {val_1..val_n}}
    {eval(prim,val_1,..,val_n)}

Given an application of a certain primitive, it may be able to {\em
meta-evaluate} the call, yielding a somewhat simpler TML tree than the
original call. For example, if the evaluation function detects that a
given call to a primitive will always compute the same value and invoke
always the same continuation, it reduces the primitive call to an
application of the continuation to the result. Typically, this is
possible if some of the arguments are literal constants:

\tmlrewrite{fold +}
    {\applyiv{+}{1}{2}{c_1}{c_2}}
    {\applyi{c_2}{3}}
             
To give another example, a call to the object identity primitive will
fold if the value to be compared is identical to one of the case tags:

\tmlrewrite{fold ==}
    {\applyvii{==}{2}{1}{2}{3}{c_1}{c_2}{c_3}}
    {\apply{c_2}}

If the {\em eval} function cannot perform any useful meta-evaluation, it
simply returns the original call to the primitive.

The \p{case-subst} rewrite rule substitutes variables in case statements
with the tag value of the corresponding branch:

\tmlrewrite{case-subst} % v}
    {\applybiii{==}{v}{val_1..val_n}{val_1^c..val_n^c}}
    {\applybiii{==}{v}{val_1..val_n}
       {\tmlsubst{val^c_1}{val_1}{v}..\tmlsubst{val^c_n}{val_n}{v}}}
           
\tmlrewrite{case-subst} % v}
    {\applybiii{==}{v}{val_1..val_n}{val_1^c..val_n^c\:val_{n+1}^c}}
    {\applybiii{==}{v}{val_1..val_n}
       {\tmlsubst{val^c_1}{val_1}{v}..\tmlsubst{val^c_n}{val_n}{v}\:val_{n+1}^c}}

Finally, there are two rewrite rules which operate on calls to the
primitive procedure $Y$.
The \p{Y-remove} rewrite rule strikes out any
recursive procedure which is not referenced from within the \hbox{bodies} of the
other (mutually) recursive procedures, whereas the \p{Y-reduce} rewrite
rule removes empty $Y$ applications:

\tmlrewritep{Y-remove}
    {(\tmlrefcount{app}{v_i} = 0 \wedge
      \forall_{i \neq j}\:\tmlrefcount{val_j}{v_i} = 0)}
    {\applyi{Y}
           {\funb{c_0\:v_1..v_i..v_n\:c}
                 {\applybvi{c}
                           {\cont{}{app}}
			   {abs_1}
                           {..}
                           {abs_i}
                           {..}
                           {abs_n}
                           }}}
    {\applyi{Y}
            {\funb{c_0\:v_1..v_{i-1}\:{v_{i+1}}..v_n\:c}
                  {\applybvii{c}
                             {\cont{}{app}}
			     {abs_1}
                             {..}
                             {abs_{i-1}}
                             {abs_{i+1}}
                             {..}
                             {abs_n}
                             }}}
    
\tmlrewritep{Y-reduce}
    {(\tmlrefcount{app}{c_0} = 0)}
    {\applyi{Y}
            {\fun{c_0\:c}
                 {\applyi{c}
                         {\cont{}{app}}}}}
    {app}


%-----------------------------------------------------------------------------

\section{Exploiting Persistent TML Representations}

The TML intermediate representation and the TML rewrite rules described so
far can be utilized fairly straightforward to build a static optimizer
for a given source language and target architecture. Additionally, TML
supports innovative code optimization scenarios which we describe in the
following subsections.


\subsection{Optimization across Abstraction Barriers}
\label{Section:Reflective Opt}

Today's applications are constructed incrementally, with heavy re-use of
modular software components defined in shared program libraries or
application frameworks.  At the same time, many binding decisions are
delayed until runtime.  Abstraction barriers (module interfaces, class
interfaces, schema layers) severely restrict the binding information
available to local static program optimizers which become less effective
with increasing modularization.

Effective optimization of highly modular languages and of database
languages therefore requires the analysis and rewriting of CPS terms which
have been declared and compiled in separate scopes (logical schema,
physical schema, query modules, embedded query, application program), at
different times and most often by different users.

In the following, we explain by an example how the Tycoon system
achieves optimizations across abstraction barriers.  Given a uniform
representation of programs and queries, the ``trick'' to eliminate these
abstraction barriers is (1) to wait until link or execution time, when
all the bindings between the contributing parts of a persistent
application are established (database schemata, application modules,
program libraries, program parameters, etc.), and (2) to keep
sufficiently abstract code and binding information until that point in
time.  Based on this approach it is rather straightforward to collect
(via transitive reachability) all declarations which contribute to a
given TML term (for example an embedded query) into a single scope
(represented again as a TML term) and to invoke the TML optimizer to
generate a globally optimized TML term.

Since the compiler (and, therefore, the optimizer) is an integral part of 
the Tycoon persistent programming environment, it is not difficult to 
call the Tycoon compiler at runtime.

For each exported source code function \p{f} in a compilation unit, the 
compiler back end augments the generated code for \p{f} with a reference to 
a compact persistent representation of the TML tree (Persistent TML, 
PTML) for \p{f}.  At runtime, it is possible to map PTML back into TML, 
re-invoke the optimizer and code-generator, link the newly-generated code 
into the running program, and execute it (Fig.~\ref{Fig:ReflectiveOpt}).

\begin{figure}[btp]
\epsfbild{ReflectiveOpt.epsf}{\epsfxsize=\columnwidth}
\caption{Interaction between compilation, optimization and evaluation 
in the Tycoon system}
\label{Fig:ReflectiveOpt}
\end{figure}

The mapping from PTML back to TML also returns the set of R-value bindings 
([identifier, OID] pairs) established at runtime.  These bindings 
correspond to free variables (module names, database names, table names, 
function names, constant names, etc.) in the source text and they 
naturally give rise to context-dependent, inter-procedure and inter-module 
optimizations ({\em optimization across abstraction barriers}).
     
To speed up repeated optimizations of (shared) functions, the optimizer
attaches several derived attributes (costs, savings, ...) to the 
generated code which also become part of the persistent system state.

For example, the following Tycoon module \p{complex} exports a (hidden) 
abstract data type \p{complex.T} and encapsulated accessor functions 
\p{complex.x()}, \p{complex.y()}, \ldots\  on values of that type:
\begin{xple}
  \k{module} complex \k{export} 
    \k{Let} T = \k{Tuple} x,y :Real \k{end}
    \k{let} new(x,y :Real):T = \k{tuple} x y \k{end}
    \k{let} x(complex :T) :Real = complex.x
    \k{let} y(complex :T) :Real = complex.y
    ...
  \k{end}
\end{xple}
Here is a function \p{abs} which uses the functions exported from the 
module:
\begin{xple}
\k{let} abs(c :complex.T) :Real =
  sqrt(complex.x(c) * complex.x(c) + complex.y(c) * complex.y(c))
\end{xple}
In the static context of this function, the implementation of the
module (the binding to the module value) is not available. Only after
module linkage (Tycoon has first class modules), the dynamic context
of \p{abs} contains bindings to the exported function. 

The programmer can obtain a (dynamically created) function
\p{optimizedAbs} which is equivalent to the original function \p{abs}
but which executes faster than the original by explicitly
invoking the optimizer on \p{abs}:
\begin{xple}
  \k{let} optimizedAbs = reflect.optimize(abs)
\end{xple}
In our current implementation, the reflective dynamic optimizer inlines
the bodies of
\p{{complex.x}} and \p{{complex.y}}, i.e., \p{optimizedAbs} is equivalent to:
\begin{xple}\k{let} optimizedAbs(c :complex.T) :Real = sqrt(c.x*c.x + c.y*c.y)
\end{xple}
Finally, the optimized function which takes advantage of the particular 
encapsulated implementation of complex numbers can be applied:
\begin{xple}
  optimizedAbs(complex.new(3 4))
\end{xple}

The main extension which is necessary to be able to carry out this kind of
dynamic optimization is to re-establish, in TML, the R-value bindings of
global variables as they are stored in the {\em closure record} of the
runtime representation of a given procedure.  For the example above, this
means that the values of the variables \p{complex}, '+', '*' and \p{sqrt}
which are global to the function \p{abs} are fetched from the closure
record of \p{abs} and are bound to the corresponding identifiers {\em
before} the (original) body of \p{abs} is processed by the
optimizer\footnote{This is a TML listing similar to the output of our TML
pretty-printer. Note that, during $\alpha$-conversion, each identifier
name is appended with a unique number in order to distinguish it from any
other identifier.}:

\begin{xple}
  \k{proc}(c\_10 c\_11)
    ($\lambda$(complex\_6 *\_7 +\_8 sqrt\_9)
        ([] complex\_6 2 cont(t\_12)            ; begin of the original body of \p{abs}
        (t\_12 c\_10 cont(t\_13)
        ([] complex\_6 2 cont(t\_14)
        (t\_14 c\_10 cont(t\_15)
        (*\_7 t\_13 t\_15 cont(t\_16)
        ([] complex\_6 3 cont(t\_17)
        (t\_17 c\_10 cont(t\_18)
        (+\_8 t\_16 t\_18 cont(t\_19)
        ([] complex\_6 3 cont(t\_20)
        (t\_20 c\_10 cont(t\_21)
        (*\_7 t\_19 t\_21 cont(t\_22)
        (sqrt\_9 t\_22 cont(t\_23)
        (c\_11 t\_23)))))))))))))              ; end of the original body of \p{abs}
      $<\!oid 0x005b4780\!>$           ; value of module \p{complex}
      $<\!oid 0x001b4044\!>$           ; value of function \p{'*'}
      $<\!oid 0x001b4024\!>$           ; value of function \p{'+'}
      $<\!oid 0x00993d28\!>$)         ; value of function \p{sqrt}
\end{xple}

Given these value bindings, the optimizer is able to perform
substitution, constant folding and procedure inlining in the usual way,
yielding a result which is equivalent to the above Tycoon code for
\p{optimizedAbs}.


\subsection{Towards Integrated Program and Query Optimization}
\label{Section:Integrated}

There is a strong interest in improving the interface between query
languages and programming languages.  For example, the ODMG standard
document explicitly states that ``object database management systems
provide an architecture which is significantly different than other DBMSs
-- they are a revolutionary rather than an evolutionary development.
Rather than providing only a high-level language such as SQL for data
manipulation, an ODBMS transparently integrates database capability with
the application programming language''
\cite{Cate94}.

Following this rationale, the syntax of many modern query languages
allows programming language variables, function and method calls to
appear in the \k{select} and \k{where} clauses of SQL statements.
Furthermore, the body of element-at-a-time iterators (\k{for} \k{each}
statements) and of database triggers may refer to programming language
statements.  User-defined data types lead to further interaction between
query expressions and programming language expressions.

Since traditional query optimizers do not have access to an abstract
representation of these program fragments, they have to work under
worst-case assumptions (dependencies between subexpressions,
side-effects) or they have to rely on programmer-supplied information
(commutativity, idempotence, side-effects) which is difficult to keep
consistent in large, long-lived systems.  In particular, current query
representations do not cover any form of control flow (conditionals, case
analysis, loops, exceptions) which is ``inherited'' through embedded
programming language expressions.

Given an integrated database language where user-defined code and query
expressions are fully integrated \cite{MaSc91b}, query and program
optimization have to interact closely (see Fig.~\ref{Fig:EmbeddedQueryOpt}):
Whenever the program optimizer encounters an embedded query construct
like a set-at-a-time (bulk) query or update, an element-at-a-time
iterator, or a view definition, it invokes the query optimizer on the
respective TML subtree with a TML environment which describes the global
bindings (free variables) for that expression.  Similarly, the query
optimizer invokes the program optimizer to analyze and optimize nested
programming language expressions which appear in query constructs (target
list, selection predicate, iterator body).  Again, binding information
for free variables (e.g., range variables in queries or loop control
variables in \k{for each} iterators) is passed along with the respective
TML subtree.  Recursive declarations of functions, values, or queries are
represented uniformly through applications of the fixpoint combinator $Y$
and do \e{not} lead to repeated traversals of TML terms.

\begin{figure}[btp]
\epsfbild{EmbeddedQueryOpt.epsf}{\epsfxsize=\columnwidth}
\caption{Embedded Query Optimization}
\label{Fig:EmbeddedQueryOpt}
\end{figure}

In general, since the optimization of query expressions depends on
runtime bindings (for example, knowledge about index structures), we
have to delay query optimizations until runtime as described in the
previous section. The translation of a declarative query construct
embedded in the source language into a TML term is rather
straightforward and resembles the usual approach of mapping a relational
query 1:1 into a tree of algebraic operators \cite{Ullm89}.

For example, the SQL statement
\begin{xple}
\k{select} Target(x) \k{from} Rel x \k{where} Pred(x)
\end{xple}
can be represented by the following TML term which uses the primitive 
procedures \p{project} and \p{select} as defined by the relational algebra:
%\pagebreak
\begin{xple}
(select $\lambda$(x ce cc) (Pred x ce cc) 
   Rel
   ce
   \k{cont}(tempRel) 
      (project $\lambda$(x ce cc) (Target x ce cc) 
         tempRel
         ce
         cc))
\end{xple}
The scope of the SQL correlation variable \p{x} is captured in TML by
having two $\lambda$-abstractions with the bound variable \p{x} in
addition to the two continuation variables \p{ce} and \p{cc}. The data
dependency between the selection and projection is made explicit by
introducing a named variable \p{tempRel} in the continuation for the
selection which is then used as an argument to the projection. Since the
variable \p{ce} which describes the current exception handler is simply
passed through, exceptions which are raised during selection or projection
are propagated to the enclosing block.

As can be seen in the simple example above, CPS focuses on data and
control dependencies, but leaves much freedom in the choice of the
particular primitive procedures to be used for the representation of
declarative queries.  Instead of relational algebra operators, more
general operators can be utilized, for example the higher-order-functions
proposed for the optimization of generalized queries over multiple bulk
types in \cite{Trind91,BTBN91,Fega94}.

For a given set of primitive procedures, algebraic and
implementation-oriented query optimization rules can be expressed quite
naturally in CPS, for example, the simple equivalence
$\sigma_p(\sigma_q(R)) \equiv \sigma_{p \wedge q}(R)$ can be written as:

\tmlrewrite{merge-select}
    {\applybbiiii{select}
        {\funb{r_1\:ce_1\:cc_1}{\applyiii{q}{r_1}{ce_1}{cc_1}}}
        {R}
        {ce}
        {\contb{tempRel}
            {\applybbiiii{select}
               {\funb{r_2\:ce_2\:cc_2}
                  {\applyiii{p}{r_2}{ce_2}{cc_2}}}
               {tempRel} 
               {ce}
               {cc}}}}
    {\applybbiiii{select}
        {\funb{r_1\:ce_1\:cc_1}
	  {\applybii{p}{r_1\:ce_1}
	    {\contb{t_1}
	      {\applybii{q}{r_1\:ce_1}
	        {\contb{t_2}{\applyiv{and}{t_1}{t_2}{ce_1}{cc_1}}}}}}}
        {R}
        {ce}
	{cc}}
	
In particular, scoping restrictions which limit the applicability of
certain rewrite rules are also directly expressible using the notation
introduced in section \ref{Section:TML Rewrite Rules}.  For example, if the
variable $x$ does not appear in the predicate $p$ of the quantified
expression $\exists x\in R :p$, this predicate is equivalent
to $p\wedge (R\neq\oslash)$.  This rule is written as follows, using CPS
notation and the predefined procedures \p{and}, \p{exists} and \p{empty}:

\tmlrewritep{trivial-exists}
   {(\tmlrefcount{p}{x} = 0)}
   {\applybbiiii{exists}{\fun{x\:ce'\:cc'}{p}}
     {R}
     {ce}
     {cc}}
   {\applybbii{empty\:R}
     {ce}
     {\contb{t_1}
       {\applybbii{\fun{ce'\:cc'}{p}}
	  {ce}
	  {\contb{t_2}
	    {\applyiv{and}{t_1}{t_2}{ce}{cc}}}}}}

Note that the resulting TML tree will be further reduced and optimized
using any other applicable rewrite rule.

%-----------------------------------------------------------------------------

\section{Related Work}

The issue of uniform intermediate code representations in database
environments arose in the integration of program and query optimization.

Freytag \cite{FrGo89} investigated the problem of translating relational 
queries into iterative programs which are quite effectively simplified using 
a set of transformation rules.  Queries are rewritten into nested 
applications of stream operators which are similar to our polymorphic 
higher-order iterator functions.  The transformation process is based on 
purely algebra-based relational query specifications which may neither contain 
embedded (user-defined) function calls nor side effects.

Lieuwen and DeWitt \cite{LiDeW91} have applied loop transformations on queries
written in the database programming language O++ \cite{AgGh89b} which provides
constructs to iterate through a set in an unspecified order.  Similar
constructs can be found, for example, in Pascal/R \cite{Schm77a} and DBPL
\cite{ScMa94}.  Lieuwen and DeWitt focus on the reordering of joins which are
expressed via nested set iterations.  Iterations may contain embedded function
calls and output statements which constrain reorderings.  However, they do not
interact with the program optimizer.  They have developed their own query tree
representation which is quite different from the AST used by the compiler.

Breazu-Tannen et al.\  \cite{BTBN91} propose a programming paradigm based on 
structural recursion on sets which comes close to both the semantic 
simplicity of the relational algebra and the expressive power of 
algorithmically complete programming languages. The authors suggest that 
this conceptual unification of queries and functional programs 
will contribute to the optimization problem.

The work which is most closely related to ours is described in 
\cite{PoSm94}.  This work investigates algebraic query optimization 
techniques for database programming languages in the context of a purely 
declarative functional language which supports sets as first-class objects.  
Within the language, it is possible to use user-defined functions as query 
predicates and as target expressions.  Since the language is 
computationally complete, the possibility of non-termination and the 
construction of infinite data structures must be taken into account, while 
problems concerning side-effects are avoided.  As in our framework, all 
optimizations can be fully exploited for all subexpressions of a query 
since no distinct languages are used to represent query trees and 
programming language expressions.  In contrast to our work, the query 
language is not integrated into a general-purpose persistent programming 
environment.

%% Chaudhuri, Shim: Query Optimization in the presence of foreign 
% functions. VLDB 1993
% Cluet, Delobel: A general framework for the optim. of oo queries. SIGMOD-92

%-----------------------------------------------------------------------------

\section{Concluding Remarks}

We have presented the syntax and generic rewrite rules for TML, a
persistent intermediate code representation. We also reported on our
experience building reusable TML analysis and rewrite tools to carry out
the core tasks in symbolic code manipulation like binding analysis,
identifier substitution, and free variable analysis. Due to its
parameterization by user-defined primitive procedures, TML is virtually
independent of the Tycoon language TL and Tycoon's bulk data library and
can be tailored with little effort to other program or query languages.
By utilizing TML, innovative optimizers like reflective code optimizers
and integrated query and program optimizers can be constructed
systematically.

The current version of the Tycoon system fully implements dynamic
reflective optimization across abstraction barriers based on CPS
representations as described in this paper.  In particular the static
and dynamic optimizers share the same code for TML analysis and
rewriting.  As described in more detail in \cite{Kira94}, performing
local program optimizations on standard benchmarks for imperative
programs (the Stanford Suite) do not yield a significant speedup in the
Tycoon database programming language.  The reason for this is the fact
that even operations on integers and arrays are factored out into
dynamically bound libraries and therefore not amenable to local
optimization.  However, a move to dynamic (link-time or runtime)
optimization more than doubles the execution speed of the standard
benchmarks as well as of most larger Tycoon programs we have
experimented with (including the compiler itself, consisting of 98
modules containing more than 29,000 lines of high-level Tycoon code).
On the down side, due to the space requirements for the additional
persistent encoding of the TML tree for each function, the code size
doubles at the same time (1.2MB vs.  600kB for the complete Tycoon
system).  We are currently investigating techniques to reconstruct a
TML representation by examining the persistent executable code
representation of a procedure, effectively inverting the target machine
code generation process.  In general, the TML tree reconstructed this
way will not be isomorphic to the original TML tree which we currently
encode in PTML.  The interesting question is whether this has an impact
on the possible optimizations, in particular in the presence of nested
recursive function bindings.

More work is required to evaluate the effectiveness of query optimization
exploiting the availability of a uniform program and query representation
at runtime.  We are also very interested in exploiting TML for other
tasks in data-intensive applications, like code shipping in distributed
systems \cite{MMS95b}, synchronization of persistent threads
\cite{MaSc94}, access control and security issues \cite{RMS95}.

\small

\bibliographystyle{enamed}
\bibliography{../bib/agdef,../bib/ag}

\end{document}




