% File:    Euro-Arch-Tycoon.tex
% Author:  Florian Matthes
% Date:    25-Oct-1993
%          [FM] Corrected several typos & added 'appeared in' footnote
% Purpose: Systems Muenchen, Oktober 1993, Vortrag: FM
%
\documentstyle[12pt,a4,xple_sl,epsf]{article}

\setlength{\textheight}{24.5cm}
\setlength{\textwidth}{16cm}
\pagestyle{empty}

\newcommand{\yes}{$\bullet$}
\newcommand{\no}{\ }

% Frames around figures:
\newcommand{\figsep}{\noindent\rule{\textwidth}{0.5pt}}

% -- Macros:
\newcommand{\e}[1]{{\em #1\/}}
\newcommand{\p}[1]{{\sl{}#1}}
\newcommand{\k}[1]{{\bf{}#1}}
\newcommand{\comment}[1]{ [[ #1 ]] }

\title{\parbox{13.5cm}{{\footnotesize Appeared in: P.P.Spies, editor, \e{Proceedings of Euro-Arch'93 Congress}, pages 301-317, Springer Verlag, October 1993}}\\
$ $\\
\Large\bf System Construction in the Tycoon$^1$ Environment:\\
       Architectures, Interfaces and Gateways}

\author{Florian Matthes \and Joachim W.~Schmidt}

\date{\small Universit\"at Hamburg\\Vogt-K\"olln Stra{\ss}e 30\\D-22527 Hamburg, Germany\\
      {\small \{matthes,J\_Schmidt\}@dbis1.informatik.uni-hamburg.de}}
      
\begin{document}
\maketitle

\begin{abstract}\noindent This paper outlines the basic concepts and the 
system architecture of the Tycoon\footnotemark[1] environment. Tycoon is
designed for the construction of persistent object systems intended to
be available on multiple software and hardware platforms.

Tycoon's contribution to system portability and scalability is achieved
by strictly separating concerns of data modeling, data manipulation,
and data storage into three distinct system layers each of which is
based on state-of-the-art system technology (polymorphic programming
languages, portable code representations, persistent object stores).
Much emphasis is being placed on supporting interoperability between
Tycoon applications and off-the-shelf tools and systems, such as
database systems, user interface managers, and optimizing code
generators.

We illustrate how higher-order functions, polymorphic typing and
transparent persistence management reduce the amount of repetitive and
type-unsafe programming in typical persistent object systems.\
\end{abstract} 

\footnotetext[1]{Tycoon: Typed Communicating Objects in Open
Environments.\\This research is supported by ESPRIT Basic Research,
Project FIDE, \#6309.\\
This paper appeared in: P.P. Spies (Ed.): \e{Proceedings Euro-ARCH'93},
Informatik aktuell, pages 301--317, Springer-Verlag, 1993.} 
\thispagestyle{empty}

\section{Introduction and Overview}

In this paper we present the concept of \e{application frameworks in
persistent higher-order languages} as a systematic approach to carry
forward the conceptual and technological achievements of
fourth-generation languages (4GLs) into open, heterogeneous
environments.

In a fist step (section~\ref{Sec:Approaches}), we summarize the relative 
merits of third-generation languages and fourth-generation languages for 
the development of information systems. Based on this analysis we explain 
how persistent higher-order languages equipped with well-designed 
polymorphic libraries make it possible to blend the advantages of 3GLs and 
4GLs in a conceptually simple and linguistically integrated system 
environment. 

In the following sections we present Tycoon, a particular example of a
persistent higher-order language that has been developed at the
University of Hamburg \cite{MaSc92a,Matt93}. The Tycoon project draws
heavily from practical experience gained in implementing successive
generations of relational database programming languages
\cite{Schm77a,Reim83,ScMa92a,SMV93} and from recent research results of
the Esprit Basic Research Project FIDE (Fully Integrated Data
Environments).

Section~\ref{Sec:Tycoon-Language} sketches Tycoon's characteristic
language concepts that are required for the definition of type-safe,
high-level application frameworks. Tycoon drastically reduces the amount
of repetitive and type-unsafe programming in typical information systems
by factoring-out much of the application's functionality into generic,
extensible server libraries. 

Section \ref{Sec:Tycoon-System} outlines the overall Tycoon system 
architecture that achieves a high degree of portability and scalability by 
strictly separating concerns of data modeling, data manipulation, and data 
storage into three distinct system layers each of which is based on 
state-of-the-art system technology (polymorphic programming languages, 
portable code representations, persistent object stores). 

Finally, section~\ref{Sec:Tycoon-Framework} gives an idea of the
organization and functionality of the Tycoon libraries for bulk data
management. We distinguish between internal library implementations
(written entirely in Tycoon) and external library implementations
(imported from external servers like SQL databases, graphical user
interfaces, or operating system libraries). Due to the richness of
Tycoon's type system it is possible to provide application programmers
with a uniform view on both kinds of libraries. 

\section{Approaches to Persistent Object System Construction}
\label{Sec:Approaches}

We use the term \e{persistent object systems} (POS) to denote a class of
software systems that give their users a flexible, problem-oriented and
safe access to large sets of long-lived objects of various types
\cite{ScMa93,Matt93}.

Due to technological and commercial developments there is an
ever-increasing demand for persistent object systems that handle new
object types like texts (electronic mail, text retrieval,
``intelligent'' text manipulation), two- and three-dimensional graphics
(CAD and geographic information systems), digitized raster images
(picture and font finder, fax manager, character recognition software),
voice data, or even short, compressed image sequences (presentation
software, scene analysis).  Furthermore, persistent object systems have
to be implemented in substantially different (PC-based, interactive,
networked, distributed, semi-autonomous) system environments
\cite{Blas90,Catt91,BaMy91}.

In addition to the classical problems of large-scale application
development, developers of a POS are faced with the following
characteristic tasks (see, e.g.,~\cite{ZdMa89,ABW*90,Manifesto90}):

\begin{description} 

\item[Persistent Storage:] The primary task in a persistent object system 
is the manipulation of the state of long-lived data objects shared by 
multiple, possibly concurrently executing applications. In many persistent 
object systems it is advantageous to be able to store, share and modify 
also program objects (``methods'', ``scripts'') as first-class data 
objects. 

\item[Generic Programming:] Persistent object systems are characterized by 
highly repetitive algorithmic and structural patterns (set-oriented 
queries, integrity constraints, generic data structures, etc.). Therefore, many 
commercial tools utilize generator techniques to derive automatically stereotyped program 
fragments (form definitions, format conversions, sorting routines, 
iterators, etc.) from parameterized, high-level descriptions. 

\item[External Server Integration:] The buzzword ``open architectures'' is 
of particular relevance for persistent object systems since it is often
necessary to interact with external devices (screens, printers,
keyboards, pointing devices, scanners, CD-ROMS, modems, fax machines,
etc.) and external servers (window libraries, RPC libraries, directory
services, etc.) for data acquisition, data presentation and data
transfer.

\end{description}

In the following, we first sketch how these requirements are met partially 
by third- and fourth-generation languages, respectively, and we then 
develop the idea of application frameworks in persistent higher-order 
languages which can be understood as a synthesis of the 3GL and 4GL 
approach. 

\subsection{Low-Level Server Access from 3GLs}

\begin{figure}
\begin{center}\leavevmode
\epsfxsize=0.6\textwidth
\epsfbox{3GL-Interfaces.ps}
\end{center}
\caption{Narrow server interfaces in 3GLs}   
\label{Fig:3GL-Interfaces}
\end{figure}

The majority of today's information systems is implemented in 
third-generation languages (COBOL, FORTRAN, C, Pascal). A severe limitation 
of these languages is their inability to capture correctly the generity 
inherent even in simple persistent object models. For example, the 
relational data model supports the definition of unary, binary, ternary, 
\ldots\ relations over various domains and it includes generic operations 
over relation variables. These operations cannot be captured adequately
by any of the commercial programming languages mentioned above \cite{BHR82}.

As a consequence of this conceptual limitation, developers of database 
programming interfaces like Embedded SQL \cite{ESQL90} restrict themselves 
to the least common denominator of all 3GLs and handle any information 
interchange via strings, addresses and untyped byte arrays that are 
transferred at the smallest possible granularity (attribute-wise) between 
application programs and the database systems. A similar situation can be 
observed at the interface between programming languages and (graphical) 
user interfaces. 

The resulting POS scenario using 3GLs is depicted in 
Fig.~\ref{Fig:3GL-Interfaces}: The overall functionality of a particular 
POS is provided by a coordinated manipulation of numerous heterogeneous 
objects on different media (D: database objects, P: program objects, S: 
screen objects, etc.). Objects on different servers are subject to 
server-specific naming, typing, lifetime, and binding rules (indicated by 
different line styles in Fig.~\ref{Fig:3GL-Interfaces}) while 
inter-server communication takes place at a low level of abstraction using 
simple, machine-oriented protocols.

A crucial advantage of such a loose server coupling is the \e{openness}
of the application development environment. If required, new servers can
be integrated freely as libraries into existing persistent object
systems.  Furthermore, call interfaces provide a minimal common ground
for data exchange between independently developed services and they
also constitute a starting point for data abstraction and component
exchangeability.

\subsection{Server Integration in 4GLs}

\begin{figure}
\begin{center}\leavevmode
\epsfxsize=0.6\textwidth
\epsfbox{4GL-Integration.ps}
\end{center}
\caption{Server integration in proprietary 4GLs}   
\label{Fig:4GL-Integration}
\end{figure}

\noindent Fourth-generation languages recognize the need for a uniform,
safe and application-oriented development environment across a variety
of servers and above the minimal interoperation level of strings and
cursors.  As depicted in Fig.~\ref{Fig:4GL-Integration}, a well-designed
4GL provides high-level naming, typing and binding mechanisms for
objects on different media (on disk, in memory, and on screen) and
thereby eliminates a substantial amount of the low-level, repetitive data
conversion and data transfer code found in 3GL applications.  4GLs are
tailored to the specific requirements of traditional, commercial
database applications:
\begin{description} 

\item[Functional requirements:] record- and set-oriented data 
modeling, data manipulation, data storage and data display; generic 
operations (search, iterate, insert, delete, update, format, display, 
validate, \ldots) applicable uniformly to record and set objects of 
different component structure. 

\item[Operational requirements:] persistent storage of data, application 
code, integrity constraints and user interface definitions; efficient 
manipulation of data on secondary storage; integration into transactional 
multi-user systems. 

\item[Modal requirements:] interactive user-interfaces, access to
precompiled queries and update transactions; support for incremental system 
evolution (e.g.\ schema changes); provision for \e{ad-hoc} queries. 

\end{description}
Examples of relational 4GLs include Ingres-4GL \cite{Ingb90}, PL-SQL
\cite{Orac90}, and Informix-4GL \cite{Infor86}. Furthermore, several
object-oriented database systems are shipped with 4GL languages to
simplify application development (e.g., $O_2$SQL and $CO_2$ for $O_2$
\cite{BDK92}). Practical experience shows that 4GL constitute a
significant advance towards achieving faster software development,
improved long-term software maintainability, better software
portability, and even enhanced execution efficiency for specialized
applications (e.g., queries) when compared with hand-coded
third-generation language solutions like C or COBOL \cite{MaJa89}.

There are, however, some severe limitations to current 4GL languages that 
hamper their success in today's open, continually evolving system environments:

\begin{itemize}
\item 4GLs are deeply integrated into proprietary DBMSs and it is 
therefore impossible to move 4GL applications from one DBMS to another.
This situation is in sharp contrast to 3GL applications using
standardized programming and database languages (e.g., C and OpenSQL).

\item It is typically very difficult to interface 4GLs with external 
servers (window systems, statistical packages, text-retrieval tools) that 
do not come bundled with the DBMS.

\item Applications developed in 4GLs do not scale well due to a lack of
appropriate typing and modularization support as found, for example, in 
Ada, C++, Modula-2 or Eiffel.

\item On the system level, 4GL often incur an unnecessary system overhead 
since it is impossible to ``downscale'' the extensive 4GL runtime support 
(form management, event management, query support, report generation, 
transaction management, \ldots) to just the functionality needed by a 
particular application. 

\item The linguistic quality of 4GLs does not compare well with modern
(object-oriented, modular, or functional) programming languages.
\end{itemize}


\subsection{Scalable Application Frameworks in Persistent Higher-Order Languages}
\label{Sec:App-Frameworks}

Most of the above 4GL limitations reflect the deficiencies of the
implementation technology that is being used to construct 4GL
interfaces. This technology simply does not support the abstractions
required for a more flexible, systematic 4GL service integration.  To
overcome these limitations and to achieve 4GL openness and extensibility,
we propose an architecture based on interacting POSs using
well-organized safe libraries and an implementation which exploits
higher-order language technology.  According to our understanding, an
ideal POS development environment involves the following components:

\begin{enumerate}

\item A persistent higher-order programming language that
provides just the core functional, operational and modal primitives
required by persistent object systems (see Sec.~\ref{Sec:Tycoon-Language});
	
\item  A lean system architecture that unbundles and repackages the
services found in traditional programming languages, database systems,
and operating systems to allow scalable system implementations ranging
from simple, PC-based, single-user systems to networked, multi-user,
client-server architectures (see Sec.~\ref{Sec:Tycoon-System}).

\item  A systematically designed application framework that consists of
a rich and extensible set of libraries. The framework supplies
application builders with predefined, composable, high-level services
like bulk data structures (relations, sets, lists, graphs, etc.),
iteration abstractions (queries, views, traversal patterns for recursive
data structures, etc.),	and declarative integrity checking mechanisms
(see Sec.~\ref{Sec:Tycoon-Framework});
	
\end{enumerate}

The success of such a development environment crucially depends (1) on
the expressiveness and orthogonality of the base language, (2) on the
degree of interoperability with pre-existing services and tools that can
be achieved by the system architecture, and (3) on the quality of the
initial set of libraries provided by the application framework.

Fig.~\ref{Fig:Application-Framework} sketches the architecture of a POS
implemented in an application framework provided by a persistent
higher-order language. Similar to a 4GL, the relevant application
objects (persistent database objects, volatile program objects, virtual
screen objects, etc.)  are subject to uniform naming, typing and binding
rules, indicated by uniform line styles connecting the corresponding
symbols in Fig.~\ref{Fig:Application-Framework}. In contrast to a 4GL,
most of these object types are not built into the base language but are
provided by an open set of libraries that are an integral part of the
programming environment. Some of the libraries are simply interfaces to
external services (database systems, language compilers, GUI toolkits),
others libraries provide functionality that is implemented in the
persistent higher-order language itself. Furthermore,
Fig.~\ref{Fig:Application-Framework} indicates that access to some of
the libraries may be supported by syntax extensions to the persistent
core language. The technology for such flexible, problem-oriented syntax
extensions using extensible grammars is described in \cite{CMA93}.

In the rest of this paper we present the contributions of the Tycoon 
system, a particular example of a persistent higher-order application 
framework, to the three areas outlined above. 

\begin{figure}
\begin{center}\leavevmode
\epsfxsize=0.6\textwidth
\epsfbox{Application-Framework.ps}
\end{center}
\caption{Scalable application frameworks in persistent higher-order 
languages}   
\label{Fig:Application-Framework}
\end{figure}

\section{Language Concepts for High-Quality Information Systems}
\label{Sec:Tycoon-Language}

In this section we highlight some of Tycoon's higher-order language 
concepts. By treating functions and types as first-class language objects, 
it becomes possible to write generic libraries and generators without 
leaving Tycoon's language framework. This fact is exploited extensively 
in the Tycoon libraries and tools  (see Sec.~\ref{Sec:Tycoon-Framework}) to 
provide 4GL functionality without resorting to inflexible, monolithic 
built-in solutions.

\subsection{Values, Types, Bindings and Signatures}

The semantic model of Tycoon is based on higher-order type theories 
\cite{Mart75,CoHu85,Card88c}. The core semantic entities of Tycoon are 
values, types, bindings and signatures \cite{BuLa84,Card89}. 
Values and types can be named in bindings for identification purposes and 
to introduce shared or recursive structures at the value and the type 
level. Signatures act as (partial) specifications of static and dynamic 
bindings. Bindings are embedded into the syntax of values, i.e. they can be 
named, passed as parameters, etc. Accordingly, signatures appear in the 
syntax of types to describe these aggregated bindings. The mutual 
dependencies are illustrated best by the following excerpt from Tycoon's 
recursive language syntax. Further examples and explanations are given 
below. 

\begin{xple}
Type::= Ide $|$ \k{Ok} $|$ \k{Nok} $|$ \k{Fun}(Signatures):Type $|$ \k{Tuple} Signatures \k{end}
             $|$ Type(Bindings) $|$ \k{Oper}(Signatures)Type 
Signatures::= \{TypeSignature $|$ ValueSignature $|$ LocationSignature\}
TypeSignature::= Ide $<$:Type
ValueSignature::= Ide :Type
LocationSignature::= \k{var} Name :Type
Value::= Literal $|$ Ide $|$ \k{ok} $|$ \k{fun}(Signatures)Value $|$ \k{tuple} Bindings \k{end} $|$ Value(Bindings)
Bindings::= \{TypeBinding $|$ ValueBinding $|$ LocationBinding\}
TypeBinding::= \k{Let} Ide=Type $|$ :Type
ValueBinding::= \k{let} Ide=Value $|$ Value
LocationBinding::= \k{let var} Ide=Value $|$ \k{var} Value
\end{xple}

Types are partial specifications of values. Here are some examples of
types (compare with the type syntax above):
\begin{center}
\begin{tabular}{ll}
\p{Int, Real, String}         & library-defined type names \\
\p{Age, IntPair}              & user-defined type names \\
\k{Ok}, \k{Nok}               & top type and bottom type \\
\p{\k{Fun}(x :Int) :Int}      & function type \\
\p{\k{Tuple} fst :Int  snd :Int \k{end}} & aggregate type \\
\end{tabular}
\end{center}

There is no syntactic distinction between library-defined base type
names and user-defined type names. The predefined type \k{Ok} represents
the weakest type specification. The predefined type \k{Nok} represents
the strongest (non-satisfiable) type specification. In Tycoon there is a
partial order on types based on their degree of precision: \p{A $<$:B}
(``A is subtype of B'') iff type \p{A} is more precise than type \p{B}.
The order \p{$<$:} is defined inductively and Tycoon's type system
contains the subsumption rule: if a value \p{a} has type \p{A} and
\p{A$<$:B} then \p{a} has also the weaker supertype \p{B}. For any type 
\p{A}, \p{\k{Nok} $<$:A $<$:\k{Ok}} holds.

Function types are used to describe the signatures of parameterized objects 
like functions, procedures, methods, generators or relational queries. 
Aggregate types are used to describe the signatures of language entities 
like records, tuples, structures, modules, object definitions, or database 
definitions,. 

For each type constructor there exist corresponding value constructors, 
for example:
\begin{center}
\begin{tabular}{ll}
\p{3, 3.4, "XY"}              & literal values \\
\k{ok}, \k{raise} \p{abort}   & top value and exception generator \\
\p{true}, \p{false}, \p{pi}   & library-defined value identifiers \\
\p{+, --, *, sin, abs}        & library-defined function identifiers \\
\p{\k{fun}(x :Int) x+1}       & user-defined function value \\
\p{\k{tuple} \k{let} fst=3 \k{let} snd=4 \k{end}} & aggregate value \\
\end{tabular}
\end{center}
The builtin value \k{ok} has type \k{Ok}. This value is returned by
expressions that are not intended to produce a useful value and that
only perform side-effects like assignments. There is no value that has
type \k{Nok}. Type \k{Nok} is assigned by the compiler to expressions
whose evaluation does not terminate, like statement sequences that raise an exception.

Bindings are ordered sequences of value, type and location bindings, for 
example:
\begin{center}
\begin{tabular}{ll}
\p{\k{let} pi = 3.1415}                & value binding  \\
\p{\k{let} succ = \k{fun}(x:Int) x+1}  & function value binding  \\
\p{\k{Let} IntPair=\k{Tuple} fst:Int snd:Int \k{end}} & type binding \\
\p{\k{let var} age = 20}               & location binding \\
\end{tabular}
\end{center}
A type binding defines a name for a type. A value binding defines a name 
for a (constant) value. A location binding defines a name for an anonymous 
location that in turn contains a value. Value, type and location bindings 
in Tycoon are immutable, i.e., it is not possible to destructively update 
bindings once they are established. Assignments can be performed only on 
the contents of locations (\p{age:=age+1}). 

It is sometimes desirable to omit identifiers from bindings and to write 
\e{anonymous} bindings, like \p{succ(3)} or \p{\k{tuple} 3 4 \k{end}} 
instead of \p{succ(\k{let} x=3)} and \p{\k{tuple} \k{let} fst=3 \k{let} 
snd=4 \k{end}}, respectively. There are type rules that govern the 
compatibility between anonymous bindings and named signatures in Tycoon. 

Signatures classify bindings like types classify values. Signatures are 
ordered sequences of value, location or type signatures, for example: 
\begin{center}
\begin{tabular}{ll}
\p{pi :Real}                                        & value signature  \\
\p{succ :\k{Fun}(x:Int) :Int}                       & function value signature  \\
\p{IntPair $<$:\k{Tuple} fst:Int  snd :Int \k{end}} & type signature \\
\p{\k{var} age :Int}                                & location signature \\
\end{tabular}
\end{center}
Signatures specify invariants on bindings and allow the verification of the
correctness of (value or type) expressions depending on names without
having access to the actual binding in which the name is defined. 
For example, based on the signature \p{\k{var} age :Int}, the 
type correctness of the expression \p{age:=age+1} can be verified without 
having access to the actual value bound to \p{age}. Signatures therefore 
play a central role in type-safe application frameworks that require
separate compilation.

\subsection{Higher-Order Functions}

In Tycoon, functions are first-class typed values. The following examples 
illustrate three powerful proramming patterns that are based on the use of 
first-class functions. It should be noted that today's 3GLs and 4GLs impose 
restrictions on the use of functions that essentially rule out these 
programming patterns for all ``interesting'' cases, e.g., if functions 
contain references to non-local variables, if functions are to be stored 
persistently, or if functions are to be passed between programs running on 
different hardware architectures. 

\e{Function aggregation} allows programmers to build complex data 
structures (``objects'') that contain function values. A particular form
of function aggregation underlies the modular and object-oriented
programming style where aggregated functions are used to perform
operations on encapsulated state variables:
\begin{xple}
\k{let} object = \k{tuple let} print = \k{fun}() \k{begin}\ldots\k{end}  \k{let} copy = \k{fun}() \k{begin}\ldots\k{end} \k{end}
\end{xple}
The selection of function components in aggregates is achieved via the
usual dot notation (\p{object.print(), object.copy()}).

\e{Function parameterization} allows programmers to pass functions 
dynamically as arguments to other functions. For example, the higher-order 
function \p{twice} takes a function argument and an integer argument and 
applies its fist argument twice to its second argument: 
\begin{xple}
\k{let} twice = \k{fun}(f :\k{Fun}(x:Int):Int  a:Int)  f(f(a))
twice(succ 3) $\Rightarrow$ 5
\end{xple}
The capability to pass functions as arguments to other 
functions is exploited heavily in the Tycoon framework to factor-out 
application-dependent functionality from otherwise re-usable library code. 

Finally, \e{function generation} allows programmers to return functions  
as the result of other functions. For example, the function \p{makeInc} 
returns a function that adds a fixed value to its argument. The increment 
step is determined by an argument to the function \p{makeInc}:
\begin{xple}
\k{let} makeInc = \k{fun}(step :Int)  \k{fun}(x :Int) x + step
\k{let} inc1 = makeInc(1)  \k{let} inc10 = makeInc(10)
inc1(3) $\Rightarrow$ 4     inc10(3) $\Rightarrow$ 13
\end{xple}
Technically speaking, each invocation of \p{makeInc} returns a fixed piece of code 
(\p{x+step}) with a different static environment that assigns values, 
types and locations to the global variables (\p{step} in this example).

\subsection{Higher-Order Type Operators}

Type operators denote parameterized type expressions that map types or
type operators to types or type operators. For example, the type operator 
\p{Pair} takes any type \p{X} that is a subtype of the trivial type 
\k{Ok} and returns a tuple type with two fields of type \p{X}:
\begin{center}
\begin{tabular}{ll}
\p{\k{Let} Pair=\k{Oper}(X $<:$\k{Ok}) \k{Tuple} fst:X  snd:X \k{end}}
                              & type operator binding \\
\p{Pair(Int), Pair(String), Pair(Pair(Int))} & type operator applications \\
\end{tabular}
\end{center}
Many programming languages have built-in type operators that map types to 
types (\p{Array}, \p{List}, \p{File}, \p{Pointer}, \ldots); some languages 
have support for user-defined type operators that map types to types (e.g., 
type definitions in ML \cite{MTH90} and Haskell \cite{HuWa92}); very few 
languages support higher-order type operators (Quest \cite{Card89}, Tycoon 
\cite{MaSc92a}).

The ability to introduce new type operators is required to supply generic 
data structures like relations, indices, stacks in the application 
framework. These generic types can later be instantiated with type 
parameters to construct application-specific types like ``supplier 
relations'', ``student indices'' or ``integer stacks''. 

The syntax for type operator definitions and type operator applications in 
Tycoon emphasizes the analogy between the concept of (higher-order) 
functions, mapping (function) values to (function) values, and the concept 
of (higher-order) type operators. In particular, it is possible to perform 
type operator aggregation, type operator parameterization, and type operator 
generation in analogy to the functional concepts outlined in the previous 
section. 

An example of a higher-order type operator is \p{Twice} 
which takes a type operator \p{F} and returns the result of applying \p{F} 
twice to a given type \p{A}:
\begin{xple}
\k{Let} Twice=\k{Oper}(F $<$:\k{Oper}(X$<$:\k{Ok})$<$:\k{Ok} A$<$:\k{Ok})  F(F(A))
Twice(Pair Int)
\end{xple}
For example, \p{Twice(Pair Int)} is equivalent to \p{Pair(Pair(Int))}.
More useful examples of higher-order type operators require substantially 
more complex type expressions as they appear in interface specifications 
of large libraries.

\subsection{Type Quantification in Signatures}

The parameterization concepts on the value and type level outlined in
the previous two secions are complemented in Tycoon by the concept of
type quantification in signatures. Type identifiers introduced in a type
signature can appear in subsequent type, value and location signatures.
This makes it possible to express two kinds of dependencies on type
variables\footnote{To a limited extent it is also possible to define
type dependencies on value identifiers (\e{dependent types}
\cite{MacQ86}).}:

\e{Existential Quantification:} Type components embedded in the 
signature of an aggregate type allow to model type abstraction as found in 
modular programming languages:
\begin{xple}
\k{Let} ADT = \k{Tuple} T $<$:\k{Ok}  zero :T  succ(:T):T  \k{end}
\k{let} nat =\k{tuple} \k{Let} T=Int  \k{let} zero=0  \k{let} succ=\k{fun}(x :Int) x+1 \k{end} 
\k{let} one = nat.succ(nat.zero)
\end{xple}
Intuitively, the existential quantification inside of an aggregate type gives 
extra flexibility to the service provider, in this case the implementor 
of the value \p{nat} of type \p{ADT}, since he can choose the 
representation type for \p{T} freely, as long as the constraints of the 
other signatures are met:
\begin{xple}
\k{let} nat =\k{tuple} \k{Let} T=String  \k{let} zero=``'' \k{let} succ=\k{fun}(x :String) concat(x ``1'') \k{end} 
\end{xple}

\e{Universal Quantification:} Type components embedded in the 
signature of a function type lead to the well-known concept of (bounded) parametric 
polymorphism \cite{CaWe85}:
\begin{xple}
\k{Let} Sort = \k{Fun}(X $<$:\k{Ok}  x :Array(X)  \{$<$\}:\k{Fun}(a:X b:X):\k{Ok}):\k{Ok}
\k{let} quickSort = \k{fun}(X $<$:\k{Ok}  x :Array(X)  \{$<$\}:\k{Fun}(a:X b:X):\k{Ok}) \k{begin}\ldots\k{end}
quickSort(:Int  IntArray  \{$<$\})
quickSort(:Person  PersonArray  \k{fun}(a,b:Person) string.$<$(a.name b.name))
\end{xple}
\p{Sort} describes the type of generic sort functions that work uniformly 
for all types \p{X} and that take an array \p{x} with elements of type 
\p{X} and a function \p{$<$} to compare two elements of type \p{X}.

Intuitively, the universal quantification inherent in generic function 
types gives extra flexibility to the service consumer, in this case the 
caller of the function \p{quickSort}, since he can apply the function to 
a wider range of arguments.

Another example of a universally quantified type expression is the type 
of the assignment function \p{``:=''}:
\begin{xple}
\k{Let} Assign = \k{Fun}(X $<$:\k{Ok}  \k{var} lhs :X  rhs :X):\k{Ok}
\end{xple}

This signature expresses the fact that the assignment operation works 
uniformly over all subtypes \p{X} of \k{Ok} and takes a location of type 
\p{X} and a value of type \p{X} as its left-hand-side and right-hand-side 
argument. Since the type of \p{``:=''} is fully representable in the Tycoon 
type system, it is also possible to export alternative implementations of 
the assignment function in the Tycoon libraries, e.g. to perform 
concurency control, integrity checking or recovery operations in
addition to the plain assignment operation.

\section{The Scalable Tycoon System Architecture}
\label{Sec:Tycoon-System}

It should be clear from the language overview in the previous section
that Tycoon does not attempt to achieve expressiveness by an extensive
list of featuers but by generalization and orthogonal combination of
relatively few basic concepts. This minimalistic approach also
simplifies the implementation of the supporting Tycoon system
architecture that is sketched in this section.

The complexity of relational database systems (and recent OODBMS)
results essentially from the fact that they are monolithic servers that
bundle a large number of tightly coupled services like memory
management, concurrency control, recovery, data structuring, access
control, etc. Moreover, access to these services is only granted via a
narrow database language interface that severely restricts access
to individual services.

The Tycoon system attempts to unbundle the above DBMS and 4GL services
by strictly separating data modeling, data manipulation and data
storage issues. Horizontal bars in Fig.~\ref{Fig:Tycoon-Layers}
indicate the three central Tycoon system abstractions: TL, TML and TSP.

\e{TL} (Tycoon Language) is the strongly-typed higher-order polymorphic 
programming language presented in Sec.~\ref{Sec:Tycoon-Language}
\cite{MaSc92a}. TL serves as a uniform application and system
programming language and therefore has to support both, programming
using high-level problem-specific data models (like entities and
relationships) as well as the implementation of these data models in
terms of system-oriented data structures (like hash tables, B-trees, or
linear lists).

Large TL programs are typically divided into modules, interfaces and 
hierachically nested libraries. The Tycoon language processors support 
separate compilation and dynamic linking. Furthermore, it is possible to 
evaluate TL expressions interactively, e.g., to perform \e{ad-hoc} 
queries. Scanning, parsing, type checking, code generation, linking and 
execution is then performed immediately, giving the user the illusion of 
interpretative execution. Since expressions entered interactively may refer 
to precompiled TL modules, this interactive interface constitutes also a 
convenient programming development environment. 

\e{TML} (Tycoon Machine Language) is a minimal intermediate language
based on an untyped lambda calculus extended with imperative constructs
that serves as a low-level, portable TL program representation in
distributed heterogeneous environments. TML was designed to support
efficient host-specific target code generation as well as dynamic
optimizations analogous to query and transaction rewriting in database
systems.

The ability to inspect abstract program representations at run-time, to
generate new executable code from program representations, and to link
newly created code to ``live'' systems is a key technology for generic
system construction. This functionality has to be emulated in third- and
fourth-generation languages either by resorting to interpretation
techniques or to non-portable, ad-hoc binding mechanisms.

Currently, there exist two different TML evaluators: a compact, portable
interpreter, immediately executable on a wide range of
hardware-platforms and an optimizing code generator. The latter uses
proprietary C compilers as portable target machine code generators.  The
current version of the Tycoon system runs on Sun Sparc, DEC Mips, and
IBM Power architectures. We intend to make Tycoon also available on IBM
PC and Apple Macintosh systems.

\begin{figure}
\begin{center}\leavevmode
\epsfxsize=0.7\textwidth
\epsfbox{Tycoon-Layers.ps}
\end{center}
\caption{The Tycoon system architecture}
\label{Fig:Tycoon-Layers}
\end{figure}

\e{TSP} (Tycoon Store Protocol) is a data-model-independent object
store protocol based on the notion of a \e{persistent heap} that shields
TML evaluators (and TL programmers) from operational aspects of the
underlying persistent store like access optimization, storage
reclamation, concurrency or recovery.  By forcing all higher levels of
the system to use the TSP (software) protocol, it provides an ideal
starting point to add system functionality at the store-level (e.g.
distribution transparency or access-control).

A key contribution of the TSP to the overall Tycoon system functionality
is support for \e{orthogonal persistence} \cite{AtBu86}: data of any type
(including functions) can exist as long or as short as required by the
application. Programmers do not need to write explicit code to move data
between persistent and volatile store. 

Currently, there exist three different TSP implementations that can be 
combined freely with the existing TML evaluators: a compact, paged main 
memory store implementation with a simple file-based persistence mechanism 
\cite{MMS92}; an interface to the Napier persistent object store
\cite{B*91} that  provides an efficient single-user stable store with
recovery mechanisms based on shadow copying exploiting low-level memory
managemement hardware support; and a gateway to the object-oriented
database system ObjectStore \cite{LLOW92} supporting recoverable
multi-user access to shared databases in client-server architectures.
All store implementations feature automatic garbage collection and
portable data import and export to files.

To summarize, this layered protocol-oriented architecture aims at system
\e{scalability} and \e{portability} by de-emphasizing operational
aspects of the protocol implementations and focussing on the core
requirements of persistent object systems.


\section{An Application Framework for Bulk Data Management}
\label{Sec:Tycoon-Framework}

As explained in Sec.~\ref{Sec:App-Frameworks}, application programmers
do not use the bare Tycoon language TL but implement substantial parts
of the overall application functionality by instantiating generic
library code supplied by an application framework. In this section we
give a brief overview of an application framework that is being
developed at the University of Hamburg to meet the specific demands of
data-intensive applications. One should note that there may be multiple
application frameworks supported by the same core language and system
architecture. For example, \cite{SchMa92} describes a Tycoon application
framework for the construction of language processors, exporting
scanner, parser and unparser generators as well as utility modules for
source code, error log and cross-reference management.

\begin{figure}
\begin{center}\leavevmode
\epsfxsize=0.8\textwidth
\epsfbox{Bulk-Type-Library.ps}
\end{center}
\caption{Components of the Tycoon Collection Type Library}
\label{Fig:Bulk-Type-Library}
\end{figure}

Fig.~\ref{Fig:Bulk-Type-Library} gives an idea of the organization of
the main components of the Tycoon application framework for bulk data
management which provides services at several levels of abstraction.
For simple applications that only need to print, display and possibly
edit (persistent) bulk data, the modules \p{Browser, Fmt, Sink} and
\p{Writer} provide pre-packaged program patterns that bundle the necessary data
retrieval and data formatting code.

Other modules (\p{Iter, IC, Reader}) export query constructs (like
select, project, join, aggregate, sort, or group by), loop statements
and predicative integrity control mechanisms. These modules utilize
higher-order functions, polymorphic functions and user-defined type
operators to make their functionality applicable uniformly to a wide
range of bulk data structures. These query constructs are fully
integrated into the Tycoon language TL, i.e., they can be nested, named,
parameterized, or stored persistently.

The declarative and set-oriented services of the modules \p{Iter, IC}
and \p{rReader} are based on abstract collection type definitions
(\p{Relation, Table, Sequence}). An abstract collection is represented
as an object with a hidden state and a set of functions (size, member,
insert, delete, get, set, \ldots) that modify or inspect the hidden
state.

For each abstract collection type (e.g., \p{Relation}) there exist
alternative collection type implementations. Some of these
implementations are written in TL (e.g., \p{LinkedList, BTree, Array,
HashTable}), others are imported from external servers (e.g. \p{SQL}
Tables). All of these implementations are polymorphic, that is, they can
be instantiated with different element types. For example, the following
(simplified) interface \p{SQL} taken from the current Tycoon libraries describes
the signatures of the polymorphic functions exported by the a SQL server:
\begin{xple}
\k{interface} SQL \k{export}
  Table $<$:\k{Oper}(E$<$:\k{Tuple} \k{end})$<$:\k{Ok}
  openTable:\k{Fun}(\k{Dyn} E$<$:\k{Ok} name:String):Table(E)
  insert:\k{Fun}(E$<$:\k{Ok} table:Table(E) tuple:E):\k{Ok}  
  insertAll:\k{Fun}(E$<$:\k{Ok} table:Table(E) tuples:Table(E)):\k{Ok}
  delete:\k{Fun}(E$<$:\k{Ok} table:Table(E) where:\k{Fun}(e:E):Bool):\k{Ok}
  \ldots
\k{end}
\end{xple}
This interface exports an abstract type operator \p{Table} that maps a
tuple type \p{E} (any subtype of the empty tuple type) to a hidden type (an
arbitrary subtype of the type \k{Ok}). This parameterized hidden type 
describes the type of SQL tables with elements of type \p{E}.  The type
operator \p{Table} is used in subsequent function signatures of this
interface, capturing the fact that the only way to manipulate SQL tables
is via these generic functions. There may be several modules
implementing this interface, i.e.\ defining type, value and location
bindings that match the specified signatures. Currently, there exist a
Tycoon/Ingres and a Tycoon/Oracle gateway that both have the interface
\p{SQL}.

The following interface imports the type operator \p{Table} from the
module \p{ingres} with interface \p{SQL} to define a
application-specific database schema that declares two relation variables
(\p{register, fees}).
\begin{xple}
\k{interface} PhoneDB \k{import} ingres \k{export}
  \k{Let} Entry=\k{Tuple} name:String num:String \k{end}
  \k{Let} Fee = \k{Tuple} prefix :String cost :Int \k{end}
  \k{var} register :ingres.Table(Entry)
  \k{var} fees :ingres.Table(Fee)
  \k{end}
\end{xple}
The binding to the external Ingres relation variables is established
in the corresponding implementation module:
\begin{xple}
\k{module} phoneDB \k{import} ingres \k{export}
  \k{let} \k{var} register=ingres.openTable(``register'')
  \k{let} \k{var} fees=ingres.openTable(``fees'')
\k{end}
\end{xple}
A main program may use the bindings provided by the phone database as
arguments to the SQL interface functions:
\begin{xple}
\k{module} main \k{import} ingres phoneDB \k{export}
  ingres.insert(phoneDB.register \k{tuple} ``Peter'' ``249'' \k{end})
  ingres.delete(phoneDB.fees \k{fun}(f:Fee) f.prefix$>=$``800'')
\k{end}
\end{xple}
This example illustrates how higher-order type systems contribute to
lean languages and open system architectures. All the code necessary to
implement the SQL gateway is encapsulated in a library that has to be
imported only by those applications that actually need this service.
Furthermore, the ``type rules'' which ensure that clients make proper
use of this service are also encapsulated by the library interface
signatures and do not need to be hard-wired into the language or its
runtime system.

\section{Concluding Remarks}

Application frameworks in persistent higher-order languages provide the
functionality of 4GLs for a much broader class of object types than the
classical set- and record-oriented data structures.  By a strict
separation of data modeling, data manipulation and data storage issues
into three distinct system layers, this generalization on the language
level can be achieved in a relatively small, scalable and portable
system environment with substantially improved interoperability.

Our current work in the Tycoon project aims at integrating further
relevant generic servers (e.g., authentication, directory and RPC
servers) into the Tycoon POS environment and to lift their services
using state-of-the-art language technology.

{\small
\bibliographystyle{florian}
\bibliography{../bib/florian}
}
 
\end{document}
