% File:   tycoonArchitecture.tex
% Date:   20-JUL-1995
% Author: Gerald Schr"oder, Florian Matthes
% Purpose: F2 Book
%
\documentstyle[xple_sl,epsf]{clmult01}

\pagestyle{myheadings}

% program text embedded within main document text
\newcommand{\p}[1]{{\frenchspacing\sl{}#1}}

% program keyword
\newcommand{\k}[1]{\mbox{\bf #1}}

% emphasize
\newcommand{\e}[1]{{\em{}#1\/}}

% Bug fix for clmult01: Description labels in bold face:
\def\descriptionlabel#1{\hspace\labelsep \bf #1\hfil}

%\newcommand{\comment}[1]{\begin{small} *** #1 *** \end{small}}
%\newcommand{\comment}[1]{}

\newcommand{\epsfpic}[2]{
  \begin{center}
    \leavevmode
    #2
   \epsffile{#1}
  \end{center}}


\title{Chapter 2.1.4\\Tycoon: A Scalable and Interoperable Persistent System Environment}

\author{Florian Matthes \and Gerald Schr\"oder \and Joachim W. Schmidt}

\institute{Technical University Hamburg-Harburg\\
Harburger Schlo{\ss}stra{\ss}e 20\\
D-21071 Hamburg, Germany}

\begin{document}

\authorrunning{Florian Matthes, Gerald Schr\"oder, and Joachim W. Schmidt}
\titlerunning{Tycoon: A Scalable and Interoperable Persistent System Environment}

\maketitle

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

\abstract{We describe the Tycoon persistent system architecture that
achieves a high degree of scalability and interoperability through a full
integration of persistent data, programs and threads while maintaining
a strict separation of storage, manipulation, modelling and
representation tasks into well-defined system layers.  For several of
these layers alternative implementations with distinct operational
support are provided that can be configured dynamically to match best
the requirements of a given application.  Moreover, we present Tycoon's
architectural contributions to enable interoperability with existing
generic services like databases, user-interface toolkits and C++
program libraries.}

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

\section{Introduction and Motivation}

Modern information systems provide their users with a flexible and 
problem-oriented access to large repositories of complex persistent 
objects.  The efficient and cost-effective implementation of such 
information systems has to be based on \e{generic services} provided by 
commercially available systems like relational or object-oriented 
databases, graphical user-interface toolkits, program libraries or 
standardized communication services.

The goal of the Tycoon\footnote{Tycoon: Typed communicating objects in
open environments.} project carried out by our group since
1992 in the context of the ESPRIT Basic Research Project FIDE is to
improve substantially the programmer productivity and modelling
flexibility in such an \e{open} heterogeneous system environment through
contributions at two levels.  First, Tycoon provides a persistent
polymorphic programming language with an elaborate higher-order type
system to uniformly describe existing generic services and to enable the
consistent integration of these services via high-level application
code.  This language aspect of the Tycoon project is described in more
detail in Chapter 1.1.1, \cite{MaSc91b,ScMa93} (synopses in Chapters 1.4.2 and 3.3.3) and \cite{SMV93,MaSc93b}.

In this paper we focus on the second contribution of the Tycoon project,
the development of a \e{persistent system architecture} to support the
Tycoon language and a seamless generic server integration.  Several
innovative components of the Tycoon system have been described already
in \cite{MaSc94,MMS96a,GaMa96a} (synopses in Chapters 1.5.2, 2.2.4 and 2.3.5) and \cite{MMS95a,MMS95b}.  Here we
present and explain Tycoon's overall system architecture which
excels through its scalability and interoperability.

Tycoon's system \e{scalability} makes it possible to cover in a single
linguistic and architectural framework system implementations that range
from a stand-alone main memory Tycoon implementation on a personal
computer to a large, networked, multi-user, optimizing persistent Tycoon
implementation.  Contrary to monolithic information system architectures
such as SAP/R3 or Oracle, Tycoon applications that require only a limited
system functionality can work with an efficient and lean system version
that nevertheless can be scaled easily to cope with increasing
operational demands over the lifetime of the application.

\begin{figure}
\epsfpic{TycoonEnvironment.epsf}{\epsfxsize=0.9\textwidth}
\caption{Interoperability in the Tycoon environment}
\label{Fig:TycoonEnvironment}
\end{figure}

\noindent
Figure~\ref{Fig:TycoonEnvironment} describes Tycoon's 
contributions to \e{interoperability}:
\begin{itemize} 

\item Existing and evolving generic services are integrated in a \e{uniform 
manner} as polymorphic Tycoon libraries that provide type-safe access to 
external data and code.  Using this approach, several generic services such 
as window systems (OpenWindows/NeWS), user-interface management systems 
(StarView), database systems (Ingres, Oracle), remote procedure call 
libraries (SunRPC), authentication services (Kerberos) and information 
retrieval engines (Inquery) have been integrated successfully in an add-on 
fashion into the Tycoon system.

Within the Tycoon language, uniform naming, typing, binding and lifetime
rules apply to screen, program and data objects (S, P, D in
figure~\ref{Fig:TycoonEnvironment}).  In contrast to closed systems like
fourth generation languages, Tycoon enables programmers to integrate
also new generic services into their applications, that is,
interoperability is not limited to a fixed set of object types like
tables or forms.  This extensibility is indicated by ellipses in the
server icon list of figure~\ref{Fig:TycoonEnvironment}.

\item Integrated services are indistinguishable from services implemented 
in Tycoon itself.  In particular, \e{type safety} and \e{persistence 
abstraction} can be obtained systematically also for external services in 
the context of the Tycoon system.  As a result, many programming errors can 
be found by static type checking at compile-time.  This should be seen in 
contrast, for example, to untyped or string-oriented bindings as found in 
user-interface toolkits or SQL databases.  Furthermore, Tycoon programmers 
are relieved from storage management issues like garbage collection, data 
transfer from and to disk, and recovery of persistent data.

\item It is not only possible to integrate existing services into the 
Tycoon programming environment, but Tycoon is designed to be itself easily 
\e{integrated as a subsystem} into larger systems.  For example, parts 
of the Tycoon compile-time and run-time environment can be reused as
servers for persistent data storage, for portable code representation
and evaluation, or for dynamic type checking.  Similarly, Tycoon
application code can be called from main programs written in C, C++,
FORTRAN, COBOL etc.  This interoperability aspect is indicated by the
arrows at the top of figure~\ref{Fig:TycoonEnvironment}.

\end{itemize}

\begin{figure}
\epsfpic{TycoonLayers.epsf}{\epsfxsize=0.7\textwidth}
\caption{Overview of the Tycoon persistent system layers}
\label{Fig:TycoonLayers}
\end{figure}

\noindent
Figure~\ref{Fig:TycoonLayers} provides an overview of Tycoon's persistent
system architecture that strictly separates storage, manipulation,
modelling and representation tasks into well-defined system layers.  For
several of these layers, alternative implementations with distinct
operational support are provided that can be configured dynamically to
match best the requirements of a given application.

In this paper we discuss these layers of the Tycoon system environment in a 
bottom-up fashion: As described in section~\ref{Sec:TSP}, full persistence 
abstraction for data and code is achieved already at the lowest layer of 
the Tycoon system defined by the Tycoon Store Protocol (TSP).  The Tycoon 
Virtual Machine (TVM) presented in section~\ref{Sec:TVM} provides a 
platform-independent higher-order execution model that also supports calls, 
callbacks and exception handling involving external code written in 
other languages.  In addition to executable TVM code, our persistent system 
architecture relies heavily on a persistent intermediate code 
representation (Tycoon Machine Language, TML) presented in 
section~\ref{Sec:TML} which is used for static and reflective run-time code 
analysis and optimization.  Since TML is an untyped language it is possible 
to implement multiple (polymorphically-typed) languages using a common TML 
intermediate representation.  In Section~\ref{Sec:Languages} we highlight 
how modern language features like dynamic typing and reflection are 
supported by Tycoon's persistent system architecture.  The wide range of 
services to be integrated into the Tycoon languages calls for a syntactic 
flexibility supported by the concept of extensible grammars as described in 
section~\ref{Sec:EGrammar}.  In section~\ref{Sec:PPE} we sketch how the 
Tycoon system components are integrated into a self-contained persistent 
programming environment including mechanisms for separate compilation and 
global optimization.  The paper ends 
with a short summary of our experience using the Tycoon environment.

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

\section{The Tycoon Store Protocol (TSP)}
\label{Sec:TSP}

The Tycoon Store Protocol defines a \e{uniform} data-model-independent 
call-level interface to multiple (commercially distributed) persistent 
object stores.  TSP is defined as an ANSI C header file which fully 
abstracts from implementation details of the underlying persistent stores.  
TSP is discussed in detail in \cite{MMS96a} (see Chapter 2.2.4).

A TSP client can switch freely from one store implementation to another and 
work with more than one persistent store at once, but references between stores are not supported.  Furthermore, TSP defines 
a portable linear data representation (TXR) to achieve store-level 
interoperability between all TSP server implementations.  TSP concentrates 
on that subset of store functions that is provided by existing, widely used 
commercial and public-domain persistent object stores.  TSP has a slight 
bias towards the needs of clients that have to implement persistent and 
possibly distributed programming languages.

A typical TSP server is implemented by writing a store adaptor that maps 
TSP data structures and functions to data structures and operations of an 
existing object store.  As of today, this has been carried out for the 
commercial multi-user store ObjectStore (ObjectDesign) and the research 
prototype FLASK (Chapter 2.3.1).  Moreover, our group has 
implemented two additional stand-alone TSP servers particularly well-suited 
for personal computers.

TSP contributes significantly to Tycoon's system scalability since TSP 
clients can choose between

\begin{itemize}
\item different garbage collection strategies;
\item different object faulting mechanisms;
\item optional error recovery, logging and persistent savepoint mechanisms;
\item single-user or multi-user access;
\item alternative commit protocols (for distributed systems);
\item optional security and authentication support.
\end{itemize}
%
At present we are investigating the orthogonal combination of these features 
through a layering of (partial) TSP implementations.

As an experiment in store-level interoperability, an NFS (Network File
System) server was written that exports selected TSP store objects
as files and directories.  In this way, all file-level commands are
available on TSP stores, for example, \p{cd} and \p{ls} for browsing
through an object graph.

A primary design goal behind TSP has been to provide efficient data storage 
as independently as possible from the data and language model supported by 
TSP store clients.  In particular, TSP should be capable of supporting 
polymorphically typed models where the components of store objects 
contain values of multiple types that cannot be fixed in a separate schema 
definition phase.  TSP therefore uses an \e{untyped} low-level store model, 
i.e., there is no separate dictionary of type or schema information 
maintained by the store.  Instead of this, store values are made 
self-descriptive by imposing a regular object layout and a uniform 
tagging scheme.  As a result, TSP achieves data model independence without 
sacrificing the advantages of self-descriptive statically-typed databases.

\begin{figure}
\epsfpic{TSPScenario.epsf}{\epsfxsize=0.9\textwidth} 
\caption{Accessing a persistent store via the Tycoon Store Protocol (TSP)}
\label{Fig:TSPScenario}
\end{figure}

\noindent
The access to persistent store objects via the TSP is depicted in 
figure~\ref{Fig:TSPScenario}.  Store objects are identified by unique 
persistent object identifiers (OIDs) that are also used to establish 
bindings between persistent objects.  Each store has a single root of 
persistence (a location that holds the OID of a distinguished root object). 
 Every object reachable from the root of persistence is stored 
persistently.  Store objects can be created through TSP operations but are 
never explicitly destroyed by clients.  The space of store objects that are 
not reachable from the persistent root object or from a (transient) OID 
held outside the persistent store during a session is reclaimed by a 
garbage collector.  In general, all object access is performed using TSP 
function calls.  TSP also supports the mapping of store objects into main 
memory to reduce the overhead incurred by repeated TSP calls.

Concurrency control and recovery on TSP stores is based on a flat 
transaction model.  The TSP operations issued between two consecutive calls 
of the TSP \p{commit} operation are regarded as a single atomic 
transaction.  Transactions of concurrently executing TSP clients are 
serialized. Furthermore, a TSP client can trigger an explicit TSP 
\p{rollback} operation to undo all side-effects on a TSP store since the 
last \p{commit} operation.

TSP provides customization facilities to support a tight integration of
TSP servers into client systems.  A TSP client can install callback
functions that are called whenever certain state transitions occur in
the backend.

\begin{itemize} \item If a failure occurs, a failure handler is called with 
an error code.  Depending on this code, the client can try to recover from 
the failure.  This is especially useful in handling deadlocks or commit 
failures.

\item If garbage collection is to be performed, a garbage collection 
handler is called.  The client can decide to perform some additional 
operations (e.g.  in an interactive user mode) before the internal garbage 
collection is triggered.

\item The garbage collector of a TSP backend calls a client-provided 
enumerator function that has to enumerate all store object identifiers
(OIDs) which are held outside the object store.  Objects transitively
reachable through these OIDs are not garbage collected.  Since some
persistent stores change OIDs during garbage collection,  the
client-provided enumerator function is also used to propagate OID
changes to TSP client data structures.

\item To transfer arbitrarily complex object store subgraphs between multiple 
TSP servers via sequential streams, a handler is needed that encapsulates 
the byte stream access.  In this way, the TSP implementation remains 
independent of file systems, network protocols or other input/output 
facilities.

\item TSP provides hooks to enable a portable transfer of client-specific 
data types like unique symbols, floating point numbers, matrices, etc.\
not supported by the predefined TSP data formats.  This is accomplished
by so-called \p{extern}/\p{intern} handlers that are called on data
export and on data import via sequential byte streams.
\end{itemize}


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

\section{The Tycoon Virtual Machine (TVM)}
\label{Sec:TVM}

The Tycoon Store Protocol defines a passive data repository that is 
independent of a particular evaluation model.  Executable code is stored as 
persistent data by the store manager.  The store manager is thus 
independent of code representations that can be tailored to specific 
application purposes.

The Tycoon Virtual Machine (TVM) is an abstract call interface above the 
TSP layer that defines a bytecoded instruction set based on a higher-order, 
functional execution model.  TVM bytecode is either interpreted by a 
virtual machine or is compiled on the fly into target machine code.  
The TVM interpreter and its associated run-time system are written in ANSI-C 
and have been ported to SunOS 4.1.x, Solaris 2.x, Linux, Windows-NT and 
MacOS. 

The platform-independence of the TVM model makes it possible to
dynamically transfer portable bytecode between heterogeneous nodes in a
distributed programming environment without recompilation.  Utilizing
TSP's linear external data representation (TXR), it is also possible to
migrate a persistent thread (code in the process of being executed)
across system boundaries \cite{MMS95a,MMS95b,MaSc94}. A thread is
represented as an object graph describing bindings between code and data
objects.

In addition to the interpreter vs.\ compiler alternative, scalability at
the TVM level is achieved by switching between single-threaded and
multi-threaded TVM implementations or between TVM implementations that
support first-class persistent threads or transient evaluation contexts
only.  The set of TVM instructions can also be extended with new
instructions to meet the needs of specific application domains like
floating-point-intensive simulation software.

Individual TVM instructions are guaranteed execution atomically w.r.t.
their effects on TSP stores.  This property can be implemented rather 
efficiently at the TVM level and simplifies the implementation of higher 
system layers in a multi-threaded and multi-user persistent system 
scenario.

To enable interoperability with existing and future libraries written in
other programming languages, TVM includes a portable and efficient
mechanism to access functions stored in statically or dynamically bound
object libraries.  This mechanism is also exploited heavily in the
Tycoon architecture to support an open set of ``base'' types like fixed
point and floating point numbers of different precisions, date and time
values, etc.

In the TVM bytecode there is no distinction between calls to static and
dynamic libraries so the TVM code remains independent of the binding 
mechanism employed by a particular TVM implementation.  The name of the 
external library and the symbol name (the name of the function to be 
called) are specified as run-time values along with a description of the 
function argument values and types.  The interpreter maintains a list of 
statically bound libraries and symbols that is searched first.  If no 
matching static library is found, a dynamic binding via the dynamic linker 
of the underlying operating system is attempted.  On platforms that do not 
support dynamic linking, all required external servers (like window 
libraries or databases) have to be bound statically to the TVM.  This 
requires only the insertion of the library name and the exported symbol 
names into a table in the source code of a distinguished TVM module.  Then 
the TVM has to be rebuilt, compiling this module and relinking the 
executable.  Again, these binding mechanisms are motivated by the desire to 
support a scalable system architecture.

Much care has been devoted in addition to support callbacks from external code to 
TVM byte code through a binding mechanism that exports an arbitrary TVM 
function object (closure) as an external function pointer.  This is 
achieved by a generic wrapper function that takes a TVM argument type 
descriptor list and a function closure and dynamically generates a wrapper 
function that maps external function arguments to TVM function arguments.

The parameters that can be transferred between the TVM and external 
languages are limited to unstructured values, i.e.  numbers, strings, words 
(including pointers and OIDs).  Structured values have to be handled by 
wrapper functions written in C or in TVM code that construct and 
decompose these values.  

To ensure a seamless interoperability at higher system layers, the external 
call and callback interface has to ensure that TVM exceptions are 
propagated correctly across language boundaries even in multi-threaded TVM 
applications.

A non-trivial problem arises if persistent TVM programs and threads work
with pointers to data structures outside TSP stores.  The lifetime of
such data structures is limited to the lifetime of a single operating
system process.  Therefore, TVM offers mechanisms to log the
construction and destructtion of these \e{volatile} values so that these
values can be reconstructed automatically if a persistent thread is
resumed.  The log is essentially a list of TVM constructor and
destructor functions stored persistently.  As a result, it is possible,
for example, to open and close windows in a windowing system, commit a
state of the store, and to have the the windows that existed in the
committed state automatically recreated on startup of the store.  Note
that this feature does not assume that the window system or other
external libraries have been prepared specifically for usage in a
persistent system architecture but that this persistence support is
added independently by the TVM layer. This is discussed in more detail in \cite{Korn95}.

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

\section{The Tycoon Machine Language (TML)}
\label{Sec:TML}

While TVM code is designed for efficient executability on multiple
platforms, our persistent system architecture relies heavily on an
additional persistent \e{intermediate} code representation (Tycoon
Machine Language, TML) to unify static compile-time and reflective
run-time code analysis and optimization.  TML is an untyped language
that is used for the implementation of multiple (polymorphically-typed)
languages using a common TML intermediate representation.  A detailed
description of the syntax and semantics of TML and of the TML
optimization algorithms can be found in
\cite{GaMa96a} (a synopsis appears in Chapter 2.3.5).

A TVM bytecode sequence is generated for a given TML term by a compiler
backend written in TL, the Tycoon Language.  TML is a Continuation
Passing Style (CPS) program representation that is well-suited for
standard code optimizations and for algebraic query optimizations.

TML is a powerful yet simple program representation technique.  The
advantage of TML lies in the dramatic reduction of the number of
program constructs that have to be handled by an optimizer, namely
variable access, function abstraction, function application and
primitive function application only.  TML is particularly well-suited
for control and data flow analysis by making the flow of control
explicit through the uniform use of one language construct: the function
application.  Since TML does not have implicit function returns this
language construct can be viewed as a generalized \p{goto} with
parameter passing.

TML has a simple and clean semantics based on the $\lambda$-calculus.
It is effectively a call-by-value $\lambda$-calculus with store
semantics.  By representing programs in TML, many well-known
optimization techniques become special cases of a few simple and general
$\lambda$-calculus transformations.  Due to certain syntactical
restrictions on TML trees, these transformations can be applied freely
even in the presence of side-effecting calls to primitive functions.

Primitive functions (such as: conditional operations, integer arithmetic, object
store access) encapsulate most of the semantics of a specific
application programming language and operate on an implicit, hidden
store.  This separation between generic CPS functionality and specific
application language functionality is also reflected by the
implementation of the TML optimizers where all information about
primitive procedures (meta evaluation function, cost attributes, target
code generation function, etc.) is factored-out from the generic TML
analysis and rewrite algorithms.

The TML optimizers and the TML to TVM translator do not perform checks
on TML trees to test their well-formedness, e.g.  whether a function
receives more or different parameters than expected.  This is the
responsibility of the clients of these tools, i.e.  of a frontend for a
specific application programming language.

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

\section{The Tycoon High-Level Languages}
\label{Sec:Languages}

As depicted in figure~\ref{Fig:TycoonLayers}, the task of the Tycoon 
high-level languages (like TL and TooL) is to support flexible high-level 
modelling of data, programs and threads independent of execution and storage 
details.

Again, scalability is achieved by supporting multiple high-level
languages within the Tycoon architecture.  The implementation of a
particular high-level language is encapsulated by a tailored compiler
function that takes typed data structures (an abstract syntax tree of
the program to be compiled and a compile-time environment) as its input
and returns typed data structures (a TML tree and a possibly extended
compile-time environment) as its result.  Target code generation and
code optimization are performed in a second phase based on the returned
TML tree.  The TML tree may contain bindings to arbitrary store values
like string literals or function closures that are preserved by all
rewriting and code generation steps of the backend.  The possibility of
passing typed persistent bindings from the source code through to the
executable code is exploited, for example, in persistent hyper-programming systems like the one described in \cite{KCC*92}.

Based on the backend functionality provided by TML, TVM and TSP, and by
utilizing the generic frontend functionality provided by extensible
grammars (see section~\ref{Sec:EGrammar}), a special-purpose database
language \p{L} can be implemented rather rapidly in the Tycoon
persistent system architecture. A tailored compilation function for
\p{L} can check the static semantics of \p{L} (scoping and typing rules)
by a recursive traversal of the abstract syntax tree and can realize the
dynamic semantics of \p{L} by a structure-directed mapping of language
terms into TML terms.  If necessary, language-specific TML primitives
(e.g., \p{method-lookup}) and run-time support libraries (e.g.,
implementing operations on bulk data structures like relations) can be
utilized to extend the higher-order TML core execution model by semantic
primitives required by \p{L}.

Our group in Hamburg has implemented two high-level languages based on
expressive \e{polymorphic} type systems.  As discussed, for example, in
\cite{AtBu86} and \cite{MaSc91b,ScMa93} (synopses in Chapters 1.4.2 and 3.3.3) such languages can serve as meta
models to describe and integrate existing relational, functional and
object-oriented database models.

\begin{itemize} 

\item The Tycoon Language (TL, \cite{MaSc92a,Matt93}) excels by its
very expressive type system based on existential and universal type
quantification, recursive types and structural subtyping similar to the
type system of the experimental polymorphic programming language Quest
\cite{Card89}.  Contrary to Quest which is based on the notion of
values, types and kinds (types of types), TL has a full
\e{higher-order} type system where type quantification and subtyping
applies uniformly to types, type operators and higher-order type
operators, eliminating the need for a separate kind level.

In addition to very few built-in types like \p{Int}, \p{String} or
\p{Bool}, TL defines a small set of data type constructors: Tuples
aggregate a fixed number of value and type bindings, arrays aggregate a
flexible number of value bindings with homogeneous signatures, variant
records define types that consist of a finite union of tuple types
distinguished by a discriminator. The orthogonal combination of these
type constructors along with recursive type definitions and (recursive)
type operators covers virtually all data structures that appear in
persistent programming.

The TL execution model is mainly imperative and includes updatable
locations. Since functions and types are first-class language objects,
powerful generic higher-order functions can be written.  To cope with
run-time errors, exceptions and exception handlers are supported.
Furthermore, TL includes mechanisms for reflective programming, dynamic
typing and external language bindings as described in the remainder of
this section.

\item The Tycoon object-oriented language (TooL) is 
organized around (parameterized) classes and message passing.  The type
system of TooL captures much of the flavor of Smalltalk within a safe
static typing discipline.  Following the spirit of Smalltalk that
provides a highly flexible and extensible programming environment based
on a small set of expressive language primitives, TooL provides only a few
built-in type concepts with rich semantics that achieve power through
systematic use and orthogonality.  TooL integrates type concepts that
are well understood in isolation like object types, subtyping, type
matching and type quantification into a practical database programming
language.

\end{itemize}
%
In the following subsections we point out some innovative language 
implementation techniques that are utilized in our Tycoon language 
processors and that are also relevant for other high-level persistent 
language implementations.

\subsection{Dynamic Types}
\label{SubSec:DynamicTypes}

In long-lived and distributed applications there are situations where type 
checking cannot be performed completely at compile-time.  For example, if 
values are transmitted (via files or communication channels) between 
independently developed applications, there is no common scope in which a 
static type check could be performed to guarantee compatibility between 
data and programs.

For such situations, the Tycoon languages provide dynamically-typed
values.  A dynamic value is a pair of value \p{v} and run-time
type representation \p{t} that describes the type of \p{v}.  A type
representation is created automatically by the compiler whenever a
dynamic value is created.  If a value component \p{v} is extracted at
run-time from a dynamic value, its associated type representation \p{t}
can be inspected.  Most languages that support dynamic types limit this
inspection to a simple boolean subtype test: is \p{t} subtype of a given
supertype \p{T} defined at compile-time? Tycoon provides a much richer
set of strongly-typed functions for the algorithmic inspection of
dynamic values, for example, to iterate over the attribute values and
attribute types of a tuple or to construct a tuple from a list of typed
bindings.

Another application area for dynamic types is the implementation of
generic functions with type-dependent behavior.  These functions take a
type representation, usually along with a value of this type, analyze
the type and exhibit different behavior depending on the type.  An
example is a generic persistent store browser that is capable of
displaying and manipulating values of any type.
 
In the Tycoon scenario where the compile-time and run-time environment
reside in the same persistent store, it is advantageous to use the same
type representation at compile-time and at run-time.  A dynamic type
representation is  a compile-time value (a run-time value of
the compiler) that is stored persistently until the run-time of the
application.  More generally, the Tycoon compilers provide a binding
mechanism for making arbitrary compile-time values accessible to the
generated code.  Furthermore, the functions to inspect, check and create
type representations are shared (as persistent store objects) between
the compile-time type checker and the run-time environment.

The higher-order Tycoon language TL provides a limited form of 
\e{dependent} types, i.e.  TL type expressions may depend on value 
identifiers.  For example, an abstract data type depends on a specific
implementation represented as a tuple value with functional components.
Dynamic type representations for such dependent types involve bindings
to run-time values.  Therefore, the concept of compile-time name
equivalence has to be mapped to the concept of run-time value
equivalence (e.g., based on OIDs) and type representations may need to
be constructed dynamically, depending on the result of value
computations.


\subsection{Compile-Time and Run-Time Reflection}
\label{SubSec:Reflection}

The Tycoon languages TL and TooL are implemented using a compiler 
bootstrapped in the Tycoon language TL.  In many Tycoon applications the 
compiler is used as a \e{black box} to develop a self-contained stand-alone 
application program.  Advanced Tycoon applications like object-oriented 
database systems, programmable simulators or compilers for high-level 
languages can also access the functionality offered by the Tycoon compiler 
in a structured way.  This is called compile-time or run-time reflection 
depending on the point in time the compiler functionality is used 
\cite{SMA91} (see Chapter 1.2.1).

Compile-time reflection is achieved by executing user-definable code during 
the compilation process if so-called \e{reflective} expressions appear in 
the source code of a program being compiled.  This makes it possible to 
write code that depends on information that is known statically at 
compile-time, maybe inferred by the compiler.  For example, generic code to 
traverse recursively defined data structures that depend on statically 
inferred type information can be written using compile-time reflection.

Run-time reflection is achieved by making typed bindings to compiler 
subcomponents (parser, type checker, code generator, evaluator, module 
manager, \ldots) available to applications at run-time.  In this case, 
code is evaluated or even generated depending on run-time (computed) values 
that are not known statically at compile-time.  Note that this kind of 
reflection, although very flexible, may lead to unexpected run-time type 
checking errors during reflective compiler calls.

Full type safety even in the presence of run-time and compile-time
reflection is guaranteed by the consistent use of dynamic types in the
Tycoon compile-time and run-time environment.


\subsection{Typing of External Bindings}
\label{SubSec:ExternalBindings}

The flexible but untyped TVM mechanisms described in section~\ref{Sec:TVM} 
to establish bindings from TVM code to external, dynamically-bound library 
functions is the basis for high-level data and code interoperability of the 
Tycoon languages with an open set of external servers.

External functions are inherently type unsafe since neither object files
nor linked libraries contain type information.  This type information is
available in the sources of the generating languages but is lost after
compilation.  This means that Tycoon cannot automatically check the
parameters of function calls to external libraries.  However, the
correctness of calls to these functions can be enforced by the Tycoon
programmer who binds the external libraries into the Tycoon system by
assigning appropriate Tycoon signatures to these external functions.

The following example shows the binding of a function \p{int\_add} that 
takes two integers and returns an integer stored in an external library 
\p{math} to the Tycoon identifier \p{intAdd} with the function
type \k{Fun}\p{(:Int :Int):Int}.

\begin{xple}
\k{let} intAdd = bind(:\k{Fun}(:Int :Int):Int  "math"  "int\_add"  "iii")
\k{let} sum = intAdd(12 23)
\end{xple}
%
The string value \p{"iii"} specifies the low-level parameter-passing
conventions to be used at the TVM level (here: call-by-value with two
integers and return by value of an integer).  All subsequent
applications of \p{intAdd}, like \p{intAdd(12 23)}, can be checked for
type correctness assuming that the binding has been typed correctly.  Note
that an external function like \p{intAdd} has true first-class status in
Tycoon, for example, it can be passed as a parameter or can be stored
persistently without restrictions.

As a more elaborate example of strongly-typed access to external functions, 
the following excerpt of the TL interface \p{SQL} exports polymorphic 
functions to perform dynamic SQL database access from Tycoon applications:

\begin{xple}
\k{interface} SQL \k{import} \ldots\ \k{export}
  error :\k{Exception with} sqlError:String \k{end}
  Table(E $<$:\k{Tuple end})  $<$:\k{Ok}
  \ldots
  openTable(\k{Dyn} E $<$:\k{Ok}  tableName :String) :Table(E)
  \ldots
  insertTuple(E $<$:\k{Ok} table :Table(E)  tup:E) :\k{Ok}
  \ldots
\k{end}
\end{xple}
%
In the Tycoon libraries there exist two distinct modules \p{ingresSQL}
and \p{oracleSQL} that implement this interface with bindings to the
dynamic SQL call interfaces of these relational database systems.  The
unary type operator \p{Table(E)} exported from the interface describes
the type of SQL tables with element type \p{E}.  For example, a value of
type \p{oracleSQL.Table(Person)} is an Oracle table with rows that have
attributes as defined by the Tycoon tuple type \p{Person}.

The polymorphic function \p{openTable} opens an existing named table for
further processing and takes a dynamic type variable \p{E} as its first
argument to ensure that the database table structure matches the Tycoon
type information. If a schema mismatch is detected, the Tycoon exception
\p{error} is raised at run-time. All other operations of the SQL
interface (queries, table updates) can be checked statically by the
Tycoon compiler based on the polymorphic signatures assigned to the SQL
functions. For example, the signature of the function \p{insertTuple}
expresses the type constraint that into a table of type \p{Table(E)}
only tuples of a matching type \p{E} can be inserted.

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

\section{Extensible Grammars}
\label{Sec:EGrammar}

The high-level Tycoon languages described in the previous section aim
at minimality and orthogonality of concepts.  The definition and
implementation of these languages is based on a restricted \e{abstract
syntax} represented by typed data structures in a Tycoon store.  The
mapping of a concrete syntax (a linear source text or a two-dimensional
graphical notation) to an abstract syntax is not part of the language
definition proper.

Most programming languages provide a fixed mapping from concrete syntax to 
abstract syntax.  For convenience, several syntactic variants are often 
provided for the same construct of the abstract syntax.  For example, the 
TL abstract syntax provides only one iteration construct (\k{loop} \dots 
\k{exit} \dots \k{end}).  Other common loop constructs (\k{while}, 
\k{repeat}, \k{for}) can be expressed using \k{loop} in combination with 
\k{if}.

For languages like TL and TooL that have to support a wide spectrum of data 
and execution models, it is desirable to keep the concrete syntax adaptable 
to the needs of a particular application domain (see also Chapter 3.2.3).  
For example, declarative bulk data access can be supported by a tailored 
query language syntax (relational calculus, SQL, comprehensions notation) 
and parallel programming can be supported by tailored control structures 
(\k{par}, \k{alt}, ...).

The Tycoon technology of \e{extensible grammars} \cite{CMA94,CMA94a} makes 
it possible to provide syntactic support for such add-on data and control 
abstractions.

Extensible grammars are implemented as a library of compiler tools
written in TL.  They were used to define the core syntax of TL and
TooL thereby supporting the syntactic extension of both languages in a
uniform way.  Extensible grammars are parameterized by the abstract
syntax tree constructors of the respective high-level Tycoon language.

The extensible grammar library also defines an abstract syntax for the 
dynamic definition and extension of grammars.  Grammars describe the 
concrete syntax (EBNF notation) and the translation into abstract syntax 
trees using typed term constructors.  Checks at grammar-definition time 
ensure that only well-formed abstract syntax trees are generated and that 
no syntactic ambiguities arise during grammar extension.

In a first step, the TL extensible grammar library is applied
reflectively to define an initial concrete syntax for the definition of
grammars using term constructors of the grammar library itself. In
a second step, this grammar is used for the definition of a core
programming language (e.g., TL or TooL abstract syntax).  Although this
initial syntax would be sufficient to express any well-typed program, it
is not user-friendly.  Thus, the initial version of the programming
language syntax is used in further redefinitions, for example, to
provide \k{while}, \k{repeat} and \k{for} loops and higher-level
abstractions like \k{select from where} queries implemented on top of a
bulk type library.

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

\section{Integrated Persistent Programming Environment}
\label{Sec:PPE}

In this section we sketch how the building blocks of the Tycoon persistent 
system architecture described in the previous sections are fully 
integrated into a persistent programming workbench to support the 
development of large data-intensive applications by teams of cooperating 
programmers.  Since computer-aided software engineering itself is a 
data-intensive task, it is natural to implement a Tycoon workbench in one 
of the Tycoon languages exploiting orthogonal persistence, reflection, and 
dynamic typing (see also figure~\ref{Fig:TycoonLayers}).

The interactive top level of the current TL workbench gives access to 
all tools in the environment via a command-line interpreter.  A graphical 
workbench based on the concept of direct manipulation of persistent data 
and code is under construction.  Separate compilation and incremental 
linking is currently built into the workbench, but we are implementing a 
generic separate compilation manager that exploits dynamic types, 
first-class environments, generic dependency checking and version 
management.

The development of large applications requires separate compilation.  This 
facilitates teamwork by dividing the problem into manageable parts and 
eases the re-use of software components.  Furthermore, type correctness 
of software components can be verified based on explicit assumptions 
about the interfaces of other software components.

TL supports separate compilation through three language constructs, namely,  
interface, module and library.  A library defines a scope for nested 
module, interface and library declarations.  An interface is syntactic 
sugar for a type- and value-parameterized tuple type definition.  A module 
is syntactic sugar for a type- and value-parameterized link function that 
computes a tuple value as defined by the type of the module interface.  The 
TL module manager tracks the dependencies between modules, interfaces and 
libraries and controls automatic recompilation and incremental linking 
based on these dependencies.

The TL programming environment has to inter-operate with commercial tools
for project management and source-code version management.  For example,
our group is using SunSoft's Team\-Ware to coordinate the parallel
Tycoon development by five full-time employees and approximately 35
students.  Therefore, the TL workbench has to maintain the source code
of library definitions, modules and interfaces as well as compiled
modules and interfaces in the file system.  The object store holds
linked modules and persistent data only.  This makes it necessary to
assign version keys, check-sums and time stamps to source code and to
compiled modules and interfaces to inform the module manager of changes
performed by external tools on individual source or object files.

\begin{figure}
\epsfpic{CompilerFlow.epsf}{\epsfxsize=0.9\textwidth}
\caption{Data flow between the language processors of the Tycoon workbench}
\label{Fig:CompilerFlow}
\end{figure}

\noindent
The data flow between the components of the various Tycoon system
layers described in this paper is shown in
figure~\ref{Fig:CompilerFlow}.  Source files or interactive user input
is parsed by the extensible parser (based on the TL or TooL syntax
definition).  Input phrases that contain grammar definitions are
checked for consistency by the grammar checker and then transformed
into parse rules for the extensible parser.  Type expressions
represented as abstract syntax trees are checked by the type checker
for well-formedness according to static semantic rules of the
respective Tycoon high-level language.  Values are translated into
(untyped) TML terms.  TML terms may be optimized locally before they
are submitted to the target code generator for the TVM.  The TVM
handles transparently the switching between the interpretation of
portable bytecode and the direct execution of native machine code
(external library code or compiled TVM code).

An interesting detail in figure~\ref{Fig:CompilerFlow} is the run-time 
reflective code optimizer.  On request, the Tycoon target code generator 
augments the executable TVM code of each function by a (persistent) binding 
to its abstract intermediate code representation (a TML tree).  This makes 
it possible to inspect function implementations at run-time.  This is 
exploited in Tycoon to perform link-time and run-time optimizations across 
abstraction barriers.

To explain this form of optimization, consider the compilation of the
expression \p{stack.empty(s)} in a module \p{m}.  At compile-time, the
only information available about the identifier \p{stack.empty} is the
signature of the function.  As soon as module \p{m} is linked, a binding
to the module \p{stack} and its function \p{empty} is established.
Tycoon's reflective optimizer exploits the binding information available
after linking or more generally during program execution to compose the
TML trees of separate functions into aggregated TML trees (dynamic
inlining) that can then again be submitted to a (global) optimizer and
code generator.  The expansion and optimization of TVM functions in the
persistent store are controlled by a tagging scheme and a cost model that
avoid repeated optimizations of shared subfunctions and limit the
increase in code size resulting from inlining.

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


\section{Concluding Remarks}
\label{Sec:Conclusion}

We have described the layers of the Tycoon persistent system
architecture that emphasizes system scalability and interoperability with
external servers. Currently, the following set of server gateways is
available as TL source code:
\begin{itemize}
\item NeWS window system based on display PostScript: 48 modules; 6300
lines of code;
\item StarView cross-platform user-interface toolkit: 131 modules; 6700
lines of code generated automatically from C++ header files;
\item Oracle RDBMS: 3 modules; 1300 lines of code;
\item Ingres RDBMS: 3 modules; 1300 lines of code;
\item Kerberos authorization and authentication server \cite{RMS95}: 6 
modules; 1055 lines of code;  
\item Inquery text retrieval engine: 3 modules; 1000 lines of code;
\item RPC and socket communication: 13 modules; 1700 line of code.
\end{itemize}
%
An additional set of approximately 80 Tycoon modules with 29000 lines of
TL code exports reusable library code like standard data types (date, time,
string), bulk data types with uniform iteration abstractions,
strongly-typed graphical data browsers and generic compiler toolkits
(scanner, parser).

Through the bootstrap of the Tycoon language processors (TML, TL and
TooL) and the implementation of an integrated object-oriented data
modelling workbench (STYLE, see Chapter 3.2.2) we already have some experience
with the development of complex Tycoon applications by cooperating teams
of programmers.

\begin{center}
\begin{tabular}{|lcr|}
\hline
system component & number of modules & total lines of code\\
\hline
TML  & 13 & 7600\\
TL   & 36 & 18200\\
TooL & 22 & 9200\\
STYLE & 250 & 41000\\
\hline
\end{tabular}
\end{center}

\noindent
Since 1994, a WWW-driven information system implemented in TL has been
operational at Hamburg University. This server was developed in the
context of the ESPRIT Network of Excellence IDOMENEUS and utilizes
Tycoon as a persistent store for data that is supplied by WWW forms and
displayed on dynamically-generated WWW pages. Persistent TL threads are
used to read, check and transform the data and to emulate persistent
sessions between WWW clients and the WWW server. In particular, it is
not necessary to install the Tycoon system as a demon, but Tycoon is
started dynamically on request since persistent threads lead to
very fast system startup sequences.

\begin{acknowledgement}
This research was supported by ESPRIT Basic Research, Project FIDE$_2$,
\#6309.
\end{acknowledgement}

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

\small
\bibliographystyle{plain}
\bibliography{../dbis-macros,../florian}


\end{document}


