% File:     interop.tex
% Date:     19-FEB-1993
% Authors:  Florian Matthes, Joachim W.~Schmidt
% Purpose:  RIDE Interoperability paper [Vienna]
%           ## indicates changes to the original submission
%
\documentstyle[12pt,a4,xple_sl,epsf]{article}
%## 12pt,a4,xple_sl-->proc,ieeextra
%##\setlength{\textheight}{8.75in}
%##\setlength{\columnsep}{2.0pc}
%##\setlength{\textwidth}{6.8in}
%##\setlength{\footheight}{0.0in}
%##\setlength{\topmargin}{0.25in}
%##\setlength{\headheight}{0.0in}
%##\setlength{\headsep}{0.0in}
%##\setlength{\oddsidemargin}{-0.19in}
%##\setlength{\parindent}{1pc}
%##\newcommand{\figwidth}{\columnwidth}

%##new:
\newcommand{\figwidth}{0.6\textwidth}

% also defined in tycoon.sty:
\newcommand{\e}[1]{{\em #1\/}}
\newcommand{\k}[1]{{\bf #1}}
\newcommand{\comment}[1]{\par{[*** #1 ***]}\par}
\newcommand{\p}[1]{{\frenchspacing\sl{}#1}}
\def\longhrule{\par\hbox to \linewidth{\hss
               \hbox to \textwidth{\hrulefill}}\par}

% Tycoon general:
\newcommand{\TL}{{\sc Tl}}
\newcommand{\TML}{{\sc Tml}}
\newcommand{\TSP}{{\sc Tsp}}
\newcommand{\engl}[1]{{\em #1\/}}
\newcommand{\fsub}{{F$_{\leq}$}}

% Specific for this text:
\newcommand{\arr}{$\rightarrow$}
\newcommand{\var}[1]{\k{var}($\alpha_{#1}$)}
\newcommand{\id}[1]{$\alpha_{#1}$}

% ##
\title{\footnotesize\vspace*{-1cm} To appear in ``Proceedings International
IEEE/RIDE Workshop on Interoperability, Vienna, April 1993
\hspace*{0.5cm}\\ $ $\\
\Large\bf Lean Languages and Models:\\
Towards an Interoperable Kernel\\ 
for Persistent Object Systems \thanks{This research was supported by
ESPRIT Basic Research (FIDE).}}

\author{\normalsize\begin{tabular}[t]{c@{\extracolsep{8em}}c}
{\large Joachim~W.~Schmidt}& {\large Florian Matthes} \\[0.2cm]
Universit\"at Hamburg, DBIS      & Current Address: DEC SRC\\
Vogt-K\"olln Stra{\ss}e 30 & 130 Lytton Avenue\\
D-2000 Hamburg 54          & Palo Alto, CA 94301\\
\\
\multicolumn{2}{c}{{\small\{J\_Schmidt, matthes\}@dbis1.informatik.uni-hamburg.de}}
\date{}
\end{tabular}\\
}

\begin{document}
\maketitle
\subsection*{\centering Abstract}
Reliable interoperation between independently developed systems
frequently requires \e{type-safe} access to \e{persistent} data objects
and \e{generic} services while today's system architectures and
interoperation tools still focus primarily on store-level access to
volatile data and simple monomorphic or untyped services.
%##\thispagestyle{empty}
%##\pagestyle{empty}

In this paper, we summarize our experience gained in a long-term project
that provides persistence abstractions and generic database support in a
strongly typed database environment which includes optimizing gateways
to commercial relational database servers and module-based distributed
programming tools. To keep the presentation focussed, we make use of a
uniform language model based on higher-order polymorphic types to
capture the essential interoperation semantics including classical
cross-language calling mechanisms, remote procedure call models as well
as relational and object-based database gateways.

This uniform language model is also the conceptual core of the 
\p{Tycoon}\footnote{Typed Communicating Objects in Open Environments}
database environment being developed at Hamburg University. Tycoon lifts
Persistent Object System interoperability to a higher level of genericity
and precision while further reducing overall system complexity by a
\e{lean approach} to languages and models for data, execution and storage.

Since it is central to the concept of \e{lean production} to
substantially reduce the \e{manufacturing penetration} by importing and
reusing external services, interoperability is crucial to our approach.

% 1---------------------------------------------------------------------
\section{Introduction}

Persistent Object Systems (POS) are integrated software artifacts that
provide flexible and efficient access to and adequate operations on
large and long-lived (sets of) data objects.  Operations on simple data
objects include searching, sorting, arithmetic, textual input and
printing. More complex data objects (bit images, vector graphics, text
documents, sounds, \ldots) require special-purpose operations for data
retrieval, data presentation and data manipulation.

Persistent Object Systems have to address characteristic interoperation
needs such as:

\begin{description}
\item[Persistent Object Management] It is necessary to identify, store, retrieve
and manipulate objects that outlive a single program execution and that
may even exist independently of the application that created them.
Appropriate naming and scoping mechanisms are required to establish
temporary or persistent bindings between persistent objects created
independently, possibly using different tools on different machines.

\item[Data Integrity] Type systems represent a particularly successful
approach to enforce integrity constraints on data objects local to a
single program.  Similarly, language-in\-de\-pen\-dent mechanisms have to be
provided for shared, persistent objects.

\item[Generic Functions] Many functions required in a Persistent Object
System can be obtained by instantiating \e{generic} services.  Sorting,
searching, query processing, form management or report generation are
typical examples of tasks that are accomplished best by instantiating
generic algorithms with type-specific arguments.  Interoperation
protocols have to be capable of handling these generic functions without
diminishing data integrity or duplicating code.
\end{description}

In this paper we seek to contribute to the answers of three
interrelated questions: What are appropriate semantic models to
describe POS \e{interaction}? How can these semantics be captured in
a sound and concise linguistic framework? What is the impact of such lean languages and
models on their supporting system architectures and their import and export interfaces?

The paper is organized as follows. In the first part we present our
experience gained in using the database programming language DBPL for
the construction of Persistent Object Systems. In Section~\ref{Sec:2} we
argue that interoperability in mixed-language, cross-platform and
multi-site environments can be substantially improved by making the
linguistic framework for naming, scoping, typing, binding etc.\
uniformly applicable to all computational objects, be they small or
large, short-lived or persistent, local or remote.  DBPL achieves a high
degree of type-safe system interoperability by providing built-in
problem-specific language support for POS applications
\cite{MaSc92a,MRSS92,MaSc89}.  In Section~\ref{Sec:3} we report on our
experience with importing into DBPL application functionality provided
by servers external to DBPL.  We concentrate on a gateway between the
DBPL system and Ingres/SQL and discuss requirements for generic gateway
construction.

In the second part of the paper (Sec.~\ref{Sec:4}), we briefly sketch
ongoing research in the Tycoon project \cite{Matt93,MaSc92c,MaSc91}.
This research aims at lean and language system architectures where
Persistent Object Systems achieve essential parts of their functionality
by importing external services into a conceptually sound linguistic
framework.

Our running example is a miniature application involving simple data
objects, namely telephone numbers, fax messages and telephone
directories. Incremental program modifications illustrate how to add
persistence, distribution, bulk data handling and external services.

% 2 --------------------------------------------------------------------
\section{Improving Inter-Object Interaction at the Instance Level}
\label{Sec:2}

We present a canonical language-based model of Persistent Object Systems
and demonstrate how this model correctly captures modularization,
distribution, persistence and bulk data abstractions as provided by
the DBPL database programming environment. 

\subsection{Naming, Typing and Binding for Safe and Flexible Object 
Interaction}\label{Sec:Model}

In this section we introduce (informally) a model to describe the
naming, typing and binding concepts involved in Persistent Object System
interoperability. The model itself (subsequently referred to as the
\e{Tycoon POS model}) is based on concepts of higher-order type systems
\cite{Mart75,CoHu85,Card88c} and is sufficiently
expressive to serve as a language-independent framework for program
translation, generation and binding. The presentation of the actual DBPL
system and its gateways in the following sections makes use of a limited
subset of the Tycoon POS model. The potential of the full model will be
discussed in Section~\ref{Sec:4}.

The model is not biased towards specific features of object-oriented languages.
It is designed to capture equally well interoperability aspects that arise in
the interaction with classical imperative languages (Cobol, Fortran, C, Pascal)
and (relational, hierarchical, object-oriented) database systems.

It should be noted that the model as presented here is too expressive to
serve as a ``good'' programming language notation. For example, it
features dependent types in their full generality that complicate type
checking and compilation. However, by introducing level distinctions and
annotations to separate static and dynamic types, one can re-establish
the static typing property and obtain efficient language implementations
(see Section~\ref{Sec:4}).

The Tycoon POS model is based on the notion of \e{types},
\e{signatures}, \e{values} and \e{bindings}. Types are understood as (partial)
specifications of values. 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 exact mutual
dependencies are defined as follows.  

The syntax for \e{types} includes a set of base types $B_i$ (\k{Int},
\k{Real}, \k{String}, \ldots), a type constant \k{Any} (the trivial
type), user-defined type variables, function types, aggregated
signatures, parameterized type expressions (type operator definitions)
and type operator applications:
\begin{xple}
Type::= $B_i$ $|$ \k{Any} $|$ TypeName $|$ 
            \k{Fun}(Signatures) Type $|$ \k{Sig}(Signatures) $|$
            \k{Oper}(Signatures) Type $|$ Type(Bindings)
\end{xple}
Function types are used to describe the signatures of parameterized
objects like functions, procedures, methods, generators or relational
queries. Aggregated signatures are used to describe the signatures of
language entities like records, tuples, structures, modules, object
definitions, database definitions, or object files.

Type operators denote parameterized type expressions that map types or
type operators to types or type operators.  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{MaSc92c}).

%## remove linebreak
\begin{sloppypar}
Our notation for type operator definitions and type operator
applications (\p{Array(E$\equiv$\k{Int})},
\p{Stack(E$\equiv$Stack(E$\equiv$\k{Int}))},
\p{Dictionary(Key$\equiv$\k{String} Value$\equiv$ \k{String})})
emphasizes the analogy between the concept of (higher-order) functions,
mapping (function) values to (function) values, and the concept of
(higher-order) type operators.
\end{sloppypar}

\e{Signatures} are sequences of value, location or type signatures. A
value signature associates a value name with a type (\p{peter :Student}).
A location signature associates a location name with a type (\p{\k{var}
age :\k{Int}}). A type signature associates a type name with a supertype
specification (\p{Student $<$:Person}).
\begin{xple}
Signatures::= \{TypeSig $|$ ValueSig $|$ LocationSig\}
TypeSig::= TypeName $<$:Type
ValueSig::= ValueName :Type
LocationSig::= \k{var} LocationName :Type
\end{xple}
Aggregated signatures are used to describe named \e{declarations} as
they occur in function headings, module signatures, \k{external}
declarations in C programs or in database schema definitions.

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{age :Int}, the type-correctness of the
expression \p{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 module systems.

In a well-formed signature sequence, types only depend on type variables
introduced to their ``left'', avoiding non-well-founded cyclic supertype
specifications:
\begin{xple}
Person $<$:\k{Any}  Student $<$:Person  peter :Student
\end{xple}

The syntax for \e{values} includes base values $b_{ij} :B_i$, like 0, 3.4,
``xyz'', \k{true}, a canonical value of the type \k{Any}, function
values including built-in functions like \p{+, --, *} of type
\p{\k{Fun}(x :\k{Int}  y: \k{Int}) \k{Int}} and user-defined
functions and aggregated bindings:
\begin{xple}
Value::= $b_{ij}$ $|$ \k{any} $|$ \k{fun}(Signatures)Expr $|$ \k{bnd}(Bindings)
\end{xple}
The syntax \k{bnd}(Bindings) defines that aggregated value and type bindings
are first-class values, generalizing classical concepts like value, function
and type aggregation in records, structures, abstract data types or modules. 
The syntax of \e{expressions} in functions is deliberately not specified here in
order to be able to describe POS involving multiple languages. We assume that
every language provides read and write access to locations in the store that are
reachable through function arguments and declarations in the static scope of a
function. Moreover, every language should have primitives for function
definition, function application, binding formation and binding element
selection in addition to the standard operations on the base types and basic
control structures.  For simplicity, we treat statements as expressions
returning the value \k{any} :\k{Any}, possibly producing side-effects on the
store.

\e{Bindings} are sequences of type, value and location bindings. A type
binding \p{Age$\equiv$\k{Int}} defines a name for a type. A value binding
\p{pi=3.1415} defines a name for a value. A location binding
\p{petersAge=\var{i} 3} defines a name for an anonymous location
identified by (\p{\id{i}}) that in turn contains a value (3).
\begin{xple}
Bindings::= \{TypeBnd $|$ ValueBnd $|$ LocationBnd\}
TypeBnd::= TypeName$\equiv$Type
ValueBnd::= ValueName=Value
LocationBnd::= LocationName=\var{i} Value
\end{xple}
Bindings model type, constant, variable and function declarations in
programming languages and instances of database schemata in database
systems.

Several names may be bound to the same location (\e{aliasing, sharing}):
\begin{xple}
\k{bnd}(fred=\var{1}``Fred''
 peter=\var{2}\k{bnd}(name=``Peter'' son=\var{1}``Fred'')
 mary=\var{3}\k{bnd}(name=``Mary'' son=\var{1}``Fred''))
\end{xple}
To avoid redundancies, location bindings could be written simply as
\p{son = \var{1}}, \p{fred = \var{1}} and a separate \e{store} could
provide the location to value mapping \p{(\id{1}\arr``Fred''),
\id{2} \arr \k{bnd}(\ldots), \id{3} \arr \k{bnd}(\ldots)}, However, mixing
store and binding information simplifies the presentation of the
following examples substantially.

By convention, the name of a location in an expression designates the
contents (r-value) of the location.  Only in certain contexts (e.g., if
passed as a variable parameter in Algol-like languages) does  it designate
the location itself (l-value) \cite{MAD87}. All imperative
languages also provide an assignment operation to  update destructively
the contents of a location by a new value, possibly affecting multiple
location bindings at once (\e{side effects}).

The expression evaluation rules for a language $L$ could be specified by an
\e{evaluation function} that takes a function value, a set of matching
argument bindings and a store returning a result and a modified store.
\begin{xple}
Eval$_{L}$ :Value $\times$ Bindings $\times$ Store $\longrightarrow$ Value $\times$ Store
\end{xple}
As we will see later in more detail, there are two basic mechanisms for
interoperation between two languages $L_1$ and $L_2$ in Persistent
Object Systems.  Both mechanisms, dynamic cross-language function calls
and static sharing of type, value and location across address spaces,
are captured by the Tycoon POS model.  These two mechanisms are tightly
interrelated since functions take values as arguments and return values.
Moreover, functions are treated as first-class values and can therefore
be shared and passed on as function arguments and results.

As usual, types are intended to classify values, and signatures are to
classify bindings. Moreover it is possible to define
\e{generic} functions (functions that take type bindings as arguments),
value-dependent type operators, abstract data types (bindings that
contain partially-specified type components and operations on that
type). The formal type rules for this model (defining well-formed types,
the types of values, the subtype relationship between types and the
signatures of bindings)  become therefore quite subtle. 

In traditional systems, types and signatures are handled exclusively  at
compile-time, while values and bindings only appear at run-time. In
persistent systems, the distinction between compile-time and run-time
blurs, and it becomes possible, for example, to inspect value and type
bindings at compile-time, giving rise to powerful reflective algorithms
\cite{Kirb92,SSF92}. In the following, we present several examples
where a generalized treatment of values, types, signatures and bindings
can be exploited for improved POS interaction.

\subsection{Modularity: The Basis for Interoperability}\label{Sec:Modularity}

In this section we introduce the basic modularization concepts of DBPL
(inherited from Modula-2 \cite{Wirt85b}). 

DBPL programs are divided into modules with well-defined import
relationships. Definition modules define signatures for type, value and
location bindings defined in implementation modules. Program modules
export a single, parameterless function value, the main program.

An interface and a skeleton DBPL module exporting basic data
types and values to handle telephone numbers would look as follows:
\begin{xple}\label{Keyword:PhoneIface}
\k{definition module} Phone;
\k{type} Number = \k{array} [0..20] \k{of char};
\k{var} localPrefix, home :Number;
\k{procedure} operator(prefix :Number) :Number;
\k{end} Phone.
\end{xple}
\begin{xple}
\k{implementation module} Phone;
\k{procedure} operator(prefix :Number) :Number;
\k{begin} \ldots \k{return} \ldots \k{end} operator;
\k{begin} (* module initialization: *)
localPrefix:=``4940''; home:=concat(localPrefix,``85312'');
\k{end} Phone.
\end{xple}
During type checking of these compilation units, the DBPL compiler
extracts type and value signatures that are represented as follows in the
Tycoon POS model:
\begin{xple}\label{Keyword:CompileEnv}
CompileEnv $\equiv$ \k{Sig}(Phone $<$:\k{Sig}(Number $<$:\k{array}...
        \k{var} localPrefix :Number  \k{var} home :Number
        operator :\k{Fun}(prefix :Number) Number)
  linkPhone :\k{Fun}(imports :\k{Sig}()) Phone)
\end{xple}
The interface module is represented as a type signature which associates
the interface name \p{Phone} (understood as a type variable) with a
supertype that is an aggregate of all types and values signatures
exported by the interface. The implementation module is
represented as a single function, \p{linkPhone}, that takes an
aggregated binding of all imported module values (in this case an empty
binding) and returns a binding that conforms to the interface signature
\p{Phone}.\footnote{As we will see later, we would lose some modelling
precision if we were to treat the implementation module as a simple
binding of type \p{Phone}.}

The signatures of \p{Phone} and \p{linkPhone} are both elements of a
flat name space modelled by a signature bound to the type variable
\p{CompileEnv}. This name space is managed implicitly via search paths to
look up compiled interfaces, called ``symbol files'', in a typical DBPL
system implementation.

The code generated for the implementation module \p{Phone} is stored as
a named binding in a flat name space that collects all compiled modules.
This name space is represented in the Tycoon POS model as a named value
\p{linkEnv} whose type matches the signatures specified by
\p{CompileEnv}:
\begin{xple}
linkEnv = \k{bnd}(linkPhone=\k{fun}(imports :\k{Sig}()) \ldots)
\end{xple}
This name space is also utilized by the DBPL linker to compose all
module initialization functions that make up an executable application
program. The main module
\begin{xple}
\k{module} Main \k{import} Phone; \ldots  \k{end} Main.
\end{xple}
is represented by the following link function:
\begin{xple}
linkMain :\k{Fun}(imports :\k{Sig}(phone :Phone)) Main
\end{xple}
It leads to the following module initialization sequence:
\begin{xple}
initEnv=\k{bnd}()
phoneE=initEnv$\cup$\{phone=linkEnv.linkPhone(initEnv)\}
mainE=phoneEnv$\cup$\{main=linkEnv.linkMain(phoneE)\}
\end{xple}
The module value returned by \p{linkPhone} is an aggregate of two
bindings to two distinct, newly created locations and binding to a
function value.
\begin{xple}
\k{bnd}(localPrefix=\var{1}``4940" 
       home=\var{2}``4940 85312''
       operator=\k{fun}(prefix :Number) \ldots)
\end{xple}

\subsection{Cross-Platform Interoperability}\label{Sec:Cross-Platform}

The distributed version of DBPL \cite{JGLR88,JLRS88} exploits the basic
module concepts described in the previous sections to add an additional
layer of type-safety to standard remote procedure call mechanisms (RPC)
in federated client-server programming models.

To give access to a local fax service at a site called
``CentralOffice'', this site would compile the following \e{remote
definition module} and then \e{export} the compiled description
(typically together with its source text for documentation purposes)
only to those clients on the network who are to be authorized to use the  
service.
\begin{xple}\label{Keyword:FaxInterface}
\k{remote definition module} Fax \k{for} ``CentralOffice'';
\k{import} Phone;
\k{type} Status = (error, busy, done);
\k{procedure} dial(number :Phone.Number) :Status;
\k{procedure} send(text :\k{array of char}) :Status;
\k{procedure} receive(\k{var} text :\k{array of char}) :Status
\k{procedure} hangup();
\k{end} Fax.
\end{xple}
In this scenario, signatures of compiled definition modules accumulated
in the compilation environment serve as protocol specifications:
\begin{xple}
CompileEnv $\equiv$ \k{Sig}(
    Phone $<$:\k{Sig}(\ldots)  (see Sec.~\ref{Sec:Modularity})
    linkPhone :\k{Fun}(imports: \k{Sig}()) Phone
    Fax$<$:\k{Sig}(Status $<$:\k{Int}
        error :Status, busy :Status, done :Status
        dial :\k{Fun}(number :Phone.Number) Status
        send :\k{Fun}(text :\k{array}\ldots) Status
        receive :\k{Fun}(\k{var} text :\k{array}\ldots) Status
        hangup :\k{Fun}() \k{Any} )
        linkFax :\k{Fun}(imports :\k{Sig}(phone :Phone)) Fax )
\end{xple}
Note that an enumeration type declaration in DBPL introduces a new type
name (a subtype of the basic type \k{int}) and a number of values names
of that type. Furthermore, the signature of the \p{receive} function
illustrates that DBPL variable parameters correspond to location
signatures in the Tycoon POS model.

Clients also need to have access to the definition module
\p{Phone} that defines the argument type \p{Phone.Number} for the remote
function \e{dial}. In the distributed DBPL environment, unique identifiers are
assigned to compiled remote interface definitions. These identifiers are
used during connection establishment to verify that all parts of a
distributed program have been compiled using compatible versions of
the interface specifications. This mechanism directly generalizes classical
link-time consistency control mechanisms in non-distributed systems.

Frequently clients require distribution transparency. In this case it is of considerable
advantage if a  main program  
\begin{xple}\label{Keyword:SendFax}
\k{module} SendFax; \k{import} Phone, Fax;
\k{begin}  
Fax.dial(``853228'');Fax.send(``Sample fax.");Fax.hangup();
\k{end} SendFaxFromModula;
\end{xple}
stays textually unchanged whether it uses a local definition module
\p{Fax} or the above remote definition mofule \p{Fax} for ``Central
Office'' offered by a server somewhere in the network. This distribution
transparency is achieved as usual by a client stub and a server stub
that marshal and unmarshal the arguments and results supplied to
functions defined in the remote definition module \cite{Corb91}.

In terms of the Tycoon POS model, RPC-based communication mechanisms are
an implementation technology that enables the creation of function value
bindings between names in a client program and function values in a
server program. Using plain RPC mechanisms it is not possible to
directly define location bindings spanning machine boundaries. In
particular, we would have to revise the module interface \p{Phone} not
to directly export the locations \p{localPrefix} and \p{home}. In
section~\ref{Sec:Persistence} we show how these traditional RPC
restrictions are lifted by the provision of (distributed) persistent
variables in DBPL.

The crucial feature of DBPL is to retain (static) type safety across
machine boundaries by maintaining a distributed compilation environment
that allows local and remote modules to \e{share} signatures for
type checking purposes and to share module bindings for transparent connection
establishment. For example, in the system for the main program
\p{SendFax} the type variable \p{Fax} is shared between the
fax client stub, fax servers stub, the actual fax implementation and the
main program:
\begin{xple}
DistributedCompileEnv$\equiv$\k{Sig}(
  Phone $<$:\k{Sig}(\ldots) (see Sec.~\ref{Sec:Modularity})
  Fax $<$:\k{Sig}(\ldots) 
  linkSendFax :\k{Fun}(imports :\k{Sig}(fax :Fax)) Main
  linkFaxClientStub :\k{Fun}(serverId :ServerId) Fax
  linkFaxServer :\k{Fun}(imports :
              \k{Sig}(phone :Phone fax :Fax)) Main
  linkFax :\k{Fun}(imports :\k{Sig}(phone :Phone)) Fax
  linkPhone :\k{Fun}(imports :\k{Sig}()) Phone)
\end{xple}

The Tycoon POS model is also capable of giving precise signatures to the
the generic client and server stub generators (built-in components of the
distributed DBPL environment) working themselves on signatures and
bindings:
\begin{xple}
clientStubGenerator :\k{Fun}(Scope$<$:\k{Sig}() Iface$<$:\k{Sig}())
        \k{Fun}(serverId :ServerId) Iface
\end{xple}

The \p{clientStubGenerator} is a higher-order function that takes an
interface signature \p{Iface} (an arbitrary subtype of the empty
signature) and returns a link function. This link function has type
\p{\k{Fun}(serverId :ServerId) Iface}, i.e. based on a
connection information supplied dynamically at run-time, it will return
a module value of type \p{Iface}, an aggregation of bindings to stub
procedures. Each stub procedure generates a linear, portable
representation of its function arguments and transmits this
representation to the server (using a value of the not further specified type
\p{ServerId} supplied as a module argument). The \p{Scope}
argument contains the signatures of transitively imported interfaces to
access their type information (e.g., to transmit values of type
\p{Phone.Number}).

The task of the \p{serverGenerator} is similar. It takes the link
function for a user-supplied remote implementation (of type
\p{\k{Fun}(imports :Scope) Iface}) and returns a link function for a
main program with the same imports.  It creates a main program that
listens for client requests and dispatches them to parameterless wrapper
functions. For each function signature in \p{Iface} there is a wrapper
function that takes arguments from a client connection channel and
passes them as arguments to the corresponding function obtained from
\p{linkRemoteImpl}. The return value is again linearized and returned to
the client that issued the request.
\begin{xple}
serverGenerator :\k{Fun}(Scope$<$:\k{Sig}() Iface$<$:\k{Sig}()
     linkRemoteImpl :\k{Fun}(imports :Scope) Iface) 
          \k{Fun}(imports :Scope) Main
\end{xple}

The signatures of the generator functions illustrate a crucial feature
of the Tycoon POS model: it allows the user to capture type dependencies between
the arguments and the result of a generic function. For example, each
application of the client stub generator to an argument of type
\p{Iface} will return a function that returns values of type
\p{Iface} (\e{parametric polymorphism} \cite{Miln78}). Since the supertype
 specified in the generator signature (\p{Iface$<$:\k{Sig}()}) is
different from the type \k{Any}, this form of universal type
quantification is also called \e{bounded parametric polymorphism}
\cite{CaWe85}.  On the other hand, in contrast to classical models of 
polymorphism, we are assuming that the
(function) value returned by the generators \e{depends} on its type
argument.

Finally, it should be noted that existing proposals and standards for
languages to describe data exchange protocols and remote procedure entry points
\cite{ISOASN92} lack any support for polymorphic values and functions.
This lack of adequate type descriptions is reflected by the fact that
standards for remote database access (RDA \cite{ISORDA91}) use ad-hoc
solutions to transfer query results and query expressions (e.g., as
plain string values) and that the distributed DBPL system does not
adhere to these standardization proposals.

\subsection{The Potential of Persistent Objects}\label{Sec:Persistence}

Interoperability aims at providing flexible and safe mechanisms to share
data and programs across system boundaries. The previous two sections
tackled the problem of type-safe sharing across compilation units and
platform boundaries. This section demonstrates how the concept of
\e{orthogonal persistence} \cite{AtBu86} as found in DBPL extends the
potential for interoperability along two new dimensions: sharing over
time and sharing between multiple users.

The following two procedures (to be declared inside the implementation
module \p{Phone}) illustrate a classical approach in managing data objects
that outlive a single programming session via operating-system files:
\begin{xple}
\k{procedure} save(fileName :\k{array of char});
    \k{var} f :File.T;
\k{begin}  f:= File.create(fileName); 
    File.writeBytes(localPrefix); File.writeBytes(home); 
    File.close(f);
\k{end} save.

\k{procedure} load(fileName :\k{array of char});
    \k{var} f :File.T;
\k{begin}  f:= File.open(fileName); 
    File.readBytes(localPrefix); File.readBytes(home); 
    File.close(f);
\k{end} load.
\end{xple}
In the terminology of the Tycoon POS model, the \p{save} and \p{load}
procedures use operations on operating system files (exported by the
module \p{File}) to implement \e{persistent value bindings}. In fact,
one can view a file system as a large aggregated binding that 
binds file names (value identifiers) to locations (updatable files) of
type \p{\k{file of} Byte}. In this view, hierarchical file systems
provide nested bindings and (symbolic) links correspond to \e{aliases}
(see Sec.~\ref{Sec:Model}). 

Even in this small example, one can recognize the conceptual problems of this
approach that hamper its usefulness for real-life data-intensive
applications: 
\begin{itemize}

\item Naming: The use of external file names is a common source of
difficulties in system management since programs become sensitive to
changes in their computing environment. It is interesting to note that
early languages (notably Cobol) were rather careful to 
document explicitly dependencies on external resources in their program sources.
Automatic (possibly parameterized) name-lookup functions (program-,
language- or operating-system specific) tend to complicate the naming
issues for persistent objects even more.

\item Typing: Since the file system does not preserve the signatures of
its bindings, it is necessary for the \p{save} operation to store a
limited form of type information (e.g., a file type key) in each file
that is to be checked by the \p{load} operation against the
type information expected by the importer (see also
\cite{ACPP90})

\item Genericity: For each type of value held in main memory,
traversal routines have to be implemented that write linear value
representations to files and  read them back into main memory
preserving sharing and cycles. This is a highly repetitive and
error-prone task that can be automated by type-directed algorithms.

\item Concurrency, consistency, recovery: Since the name space offered by the
operating system is not only persistent but also \e{shared} between
several programs, it becomes necessary for the programmer to insert
special code to ensure that main memory and persistent data are properly
synchronized even in the presence of concurrent access by several users.
Furthermore, it is often necessary to ensure that destructive updates of
persistent data structures are performed \e{atomically} to handle 
system and program failures graciously.

\item Efficiency: In large-scale systems it is  difficult to decide
when to execute \p{save} and \p{load} operations and at which
granularity to transfer data between volatile and persistent store, in
particular, if the persistent data does not fit into main memory. It is
therefore desirable to separate these operational aspects from the
algorithmic task at hand.
\end{itemize}

DBPL introduces the notion of a \e{persistent module} (database
module) to define persistent location bindings in a
strongly-typed programming environment. For example, the following
local changes marked by underscores are sufficient to turn
\p{localPrefix} and \p{home} into persistent variables 
(compare Sec.~\ref{Keyword:PhoneIface}).
\begin{xple}
\underline{\k{database}} \k{definition module} Phone;
\k{type} Number = \k{array} [0..20] \k{of char};
\k{var} localPrefix, home :Number;
\k{procedure} operator(prefix :Number) :Number;
\k{end} Phone.
\end{xple}
\begin{xple}
\k{implementation module} Phone;
\k{procedure} operator(prefix :Number) :Number;
\k{begin} \ldots \k{return} \ldots \k{end} operator
\underline{\k{database definition}} \k{begin}
localPrefix:=``4940''; home:=concat(localPrefix,``85312'');
\k{end} Phone.
\end{xple}
The compilation of these modules defines a collection of signatures that
is identical to the non-persistent environment \p{CompileEnv} defined
in Sec.~\ref{Keyword:CompileEnv}. The import semantics of persistent
modules differ from volatile modules: the execution of the module
initialization code \p{linkPhone} of a persistent module at link-time
does not return a new set of bindings to newly created process-local
locations (copy semantics), but returns bindings to locations that are
\e{shared} between all programs importing the persistent module
(reference semantics).  Therefore, side effects created by one
application on persistent variables are visible to other applications
importing the same persistent module:
\begin{xple}
\k{module} Main1 \k{import} Phone;
\k{begin} Phone.localPrefix:= ``004940" \k{end} Main1.

\k{module} Main2; \k{import} Phone;
\k{begin} Phone.localPrefix:=concat(Phone.localPrefix,``-")
\k{end} Main2.
\end{xple}
The sequential execution of \p{Main1} and \p{Main2} would lead to the
following location bindings:
\begin{xple}
\k{bnd}(localPrefix=\var{1}``004940-'' 
      home= \var{2}``494085312''
      operator=\k{fun}(prefix :Number) \ldots)
\end{xple}
The statement sequence marked by the keywords \k{database definition
begin} is executed only once during the lifetime of the database module
\p{Phone}, namely before it is imported for the first time into a DBPL
application program.

The main advantages of persistent modules lies in overcoming the naming,
typing and genericity problems associated with file-based solutions
without introducing additional linguistic complexity in the programming
environment. Furthermore, DBPL supports user-defined (parameterized)
\e{transactions} to handle the concurrency-control, recovery and
integrity issues raised above based on standard database transaction
models.

Bindings to persistent locations are implemented by maintaining (at
compile- and at run-time) a mapping between module-level location names
and \e{external} locations and by having the compiler insert \p{save}
and \p{load} operations at appropriate code positions for values of
appropriate granularity. The task of caching values from external
locations in main-memory locations bears similarity to traditional
register allocation techniques \cite{Rich89,MRSS92}.  The \p{save} and
\p{load} operations and the transaction primitives (\p{begin, end, abort
transaction}) also trigger concurrency-control and recovery mechanisms
\cite{ScMa90b}.

The DBPL approach to transparent persistence management blends well with
the transparent RPC-based distribution mechanisms described in
Sec.~\ref{Sec:Cross-Platform}. For example, it is possible to import
remote values and remote locations or to perform dynamic location
bindings in remote function applications (i.e.~to pass variable
parameters or pointers to remote functions). Finally, it is possible to
delay the marshalling and unmarshalling of bindings (e.g., in argument
lists or records) until the value bound to a name is actually accessed
(\e{call by need})\footnote{The latter mechanism has not been
implemented in the DBPL system.}.


\subsection{Bulk Types in DBPL}\label{Sec:Bulk}

In the process of building a POS, it is often necessary to handle large,
dynamic homogeneous collections of objects (e.g., class extents).
Furthermore, it is necessary to represent relationships between object
collections and to perform efficient, set-oriented update and retrieval
operations.

Database systems have been designed to provide specific system and
modelling support for these tasks. Expanding on our running example, let
us assume that there is a need to store information on telephone numbers
assigned to persons as well as fees per unit assigned to area codes.
This kind of information is adequately described by the following
relational database definition:
\begin{xple}\label{Keyword:IngresDB}
\k{createdb} SQLPhoneDB \ldots
\k{create table} register (name \k{char}(50), num \k{char}(21))
\k{create table} fees (prefix \k{char}(50), cost \k{int4})
\end{xple}
The language SQL provides simple, efficient, declarative read and write
access to the information held in the database (\k{insert into table},
\k{delete from table}, \k{select} \ldots \k{from} \ldots \k{where}
\ldots). However, it turns out to be surprisingly difficult to access SQL
databases from application programs, e.g., to use the \p{Fax} service to
send a message to every person named ``Smith''. We do not want to go
into the details of SQL host language embedding, but the problems
encountered can be classified as follows:
\begin{description}

\item[Naming Problems] The only way to name SQL objects (databases,
tables, attributes) from a programming language is via strings. These
strings adhere to quite non-standard scoping rules. There is no
mechanism to directly identify table elements. Programmers therefore
have to explicitly create \e{cursors} to navigate over tables.
Essentially, the programmer is forced to explicitly introduce
programming language variables (cursors, database handles,
\ldots) for every DB object being accessed.

\item[Typing Problems] While it is easy to find an ad-hoc translation
between values of the SQL base types (\k{int4}, \k{float8}, \ldots),
there are no mechanisms to share type information (e.g., record or table
types) between databases and application programs. Every application
program therefore has to repeat the type declarations made in the
database schema.  Null-values in databases have to be handled via
special ``indicator variables'' in application programs. Most
importantly, there is no static type checking between type assumptions
made in the application and those found in the database.  Mismatches are
only detected at run-time or result in ``arbitrary'' values being stored
in communication buffers.

\item[Binding Problems] There is no mechanism to statically bind
applications to databases. Binding and scoping is performed typically
via side-effects, e.g., by issuing a \p{connect(``SQLPhoneDB'')}
command, that affects the interpretation of all table names used in
subsequent statements. Finally, query expressions are subject to
``textual'' substitutions that are incompatible with classical
programming language semantics. For example, the correctness of the
query \p{\k{select} x.num \k{from} :RangeExp \k{where} x.name =``\%Smith\%''} depends on the value
of the string host variable \p{RangeExp} (``quoted'' with a ``:''). A
legal substitution would be \p{RangeExp:= ``register, x''}, while
\p{RangeExp:= ``fees, x''} yields a scoping error and \p{RangeExp:=
``x$>$400''} yields a syntax error at run-time.
\end{description}

It should be noted that these problems are not specific to relational
database languages; the very same difficulties arise in newly designed
persistent object management systems that also provide special-purpose
data definition and query languages \cite{Catt91,KiLo89}.

DBPL overcomes these difficulties by using the persistence and
modularization concepts described in Sec.~\ref{Sec:Modularity} and
extending the language by a generic bulk types operator \k{relation} and
predefined polymorphic operations on values of type relation. Due to the
orthogonality of the DBPL type system, it is possible to define a richer
set of data structures than it is possible in the classical relational
model, but this flexibility is not required here
\cite{ScMa91a}. The SQL database schema is represented by the
following persistent DBPL module:
\begin{xple} 
\k{database definition module} PhoneDB; \k{import} Phone;
\k{type} String = \k{array} [0..49] \k{of} \k{char};
\k{type} Entry = 
          \k{record} name :String num :Phone.Number \k{end};
\k{type} Fee = \k{record} prefix :String  cost :\k{integer} \k{end};
\k{type} Register = \k{relation} name \k{of} Entry;
\k{type} Fees = \k{relation} prefix \k{of} Fee;
\k{var} register :Register; \k{var} fees :Fees;
\k{end} PhoneDB.
\end{xple}
Names have been assigned to all types to be re-used in application
programs importing the database variables \p{register} and \p{fees}. DBPL
provides a rich set of set-oriented update operators and an extended
relational calculus including recursion based on fixed-point semantics to
express bulk operations: \cite{ERMS91}
\begin{xple}
\k{if} \k{card}(register) = 0 \k{then} \ldots \k{end};
johnsEntry:= Entry\{``John", ``237"\};  
register:= Register\{johnsEntry\};
register:+ Register\{\{``Peter", ``249"\}\}; 
register:--Register\{\k{each} n \k{in} register:n.num$>$``240''\};
\end{xple}
Relations can be viewed as collections of \e{location} bindings (indexed by
the key values defined in the relation type declaration). Consequently,
it makes sense to provide element-oriented update operators and destructive
iteration capabilities:
\begin{xple}
register[``Peter''].num:= ``250'';
\k{transaction} addPrefix;
\k{begin} \k{for each} n \k{in} register :\k{true} \k{do} 
        n.num:= concat(Phone.localPrefix, n.num) \k{end}
\k{end} addPrefix;
\end{xple}
DBPL has special (generic) type rules for the built-in
relation operators, e.g., to capture the fact that the set-oriented
insertion operator ``:+'' can be applied to relations of arbitrary
element type \p{E}, as long as the right-hand side expression is also a
relation of the same element type \p{E}:
\begin{xple}
\p{fees:+ Fees\{\{``853'', 14\}\}}
\end{xple}

Relation types provide a good example for the use of type operators and
type-par\-ameter\-ized functions in the Tycoon POS model introduced in
Sec.~\ref{Sec:Model}. As a first step to define the signature of the
interface \p{PhoneDB}, the built-in DBPL type environment could be
represented as follows:
\begin{xple}
DBPLBuiltinEnv $\equiv$ \k{Sig}(
      Relation $<$:\k{Oper}(ElementType$<$:\k{Any}) \k{Any}
      \{\} :\k{Fun}(E $<$:\k{Any}) Relation(\k{Any})
      CARD :\k{Fun}(E $<$:\k{Any}  rel :Relation(E)) \k{Int}
      :+ :\k{Fun}(E $<$:\k{Any}  \k{var} lhs :Relation(E) 
                  rhs :Relation(E)) \k{Any}
      \ldots )
\end{xple}
This environment declares a type operator \p{Relation} that maps
arbitary types (subtypes of type \k{Any}) to a hidden representation
type (a subtype of type \k{Any}). The subsequent function signatures
make use of this type operator to express the type constraints on the
built-in DBPL functions. For example, the standard function \k{CARD}
takes an arbitrary type argument \p{E}, a relation \p{rel} of type
\p{Relation(E)} and returns the cardinality of the relation, a value of
type \k{Int}.

Using the abstract type operator \p{Relation} exported from
\p{DBPLBuiltinEnv}, the signature of \p{PhoneDB} looks as follows:
\begin{xple}
CompileEnv $\equiv$ DBPLBuiltinEnv  $\cup$ 
    Phone $<$:\k{Sig}(\ldots) 
    PhoneDB $<$:\k{Sig}(
       String $<$:\k{array} \ldots
       Entry$<$:\k{Sig}(name:\k{String} num:Phone.Number)
       Fee $<$:\k{Sig}(prefix :\k{String} cost :\k{Int})
       Register $<$:Relation(Entry)  
       Fees $<$:Relation(Fee)
       \k{var} register :Register  \k{var} fees :Fees)
\end{xple}

% 3 -------------------------------------------------------------------
\section{Interoperability and Genericity}\label{Sec:3}

In the previous section we discussed dimensions of object interaction on
the instance level. In the framework of the DBPL language and system we
presented support for safe inter-object interactions based on naming,
typing and binding mechanisms that apply uniformly to computational
objects whether they are local or remote, short-lived or persistent,
small or large.

The notion of interoperability applies, of course, to a more general
setting in which independently developed, \e{generic} systems have to
cooperate, i.e.\ to provide for inter-object interactions that
handle \e{all} potential objects the systems may create
and maintain. In this section we report on our experience with such
generic cross-language interoperability via the DBPL/C and the DBPL/SQL
gateway and outline general requirements for generic gateway
implementation.  We will continue focussing on the underlying naming,
typing and binding concepts presented in terms of the Tycoon POS model
introduced above.

\subsection{Cross-Language Interoperability}\label{Sec:Cross-Language}

The most primitive (but also most common) form of cross-language
interoperability is achieved by having a standardized,
language-independent link format (e.g., COFF of Unix System V) that
allows static bindings in a language $L_{imp}$ to bind to values or
locations defined in another language $L_{exp}$. In this setting,
$L_{imp}$ is able to import from $L_{exp}$. The next step is to define
standardized, language-independent parameters passing conventions that
allow argument values or argument locations defined in $L_{imp}$ to be
bound dynamically to function parameters defined in $L_{exp}$. If the
roles of $L_{imp}$ and $L_{exp}$ can be interchanged, full
cross-language interoperability (including ``call-back'' mechanisms) is
supported.

Since this interoperability takes place at the value, location and
binding level only, all naming and typing consistency control enforced
by the use of type names, types and signatures in compilers is
effectively lost in this scenario\footnote{There are, however, attempts
to define ``architecture-neutral distribution formats'' that preserve
(low-level) type information until link-time \cite{TDF91a}.}.

The DBPL compilers for VAX, Sparc and Motorola architectures attack this
problem by providing the DBPL programmer with a mechanism to recover
type and signature information for external bindings via so-called
\e{foreign definition modules}. For example, the interface of the
\p{Fax} module defined in Section~\ref{Keyword:FaxInterface} could be
revised as follows to define a FAX service implemented in the
programming language C:
\begin{xple}
\k{definition} \underline{\k{for} C} \k{module} Fax;
\k{import} Phone;
\k{type} Status = (error, busy, done);
\ldots  
\k{end} Fax.
\end{xple}
The compiler will enforce the consistent use of the bindings exported by
the external \p{Fax} package in all importing DBPL programs. For
example, it would catch the following type error in the application of
the function \p{Fax.dial} that attempts to pass an integer value as a
string argument:
\begin{xple}
\k{module} SendFax; \k{import} Phone, Fax;
\k{begin}  
Fax.dial(853228);Fax.send(``Sample fax.");Fax.hangup();
\k{end} SendFax;
\end{xple}
The skeleton of a C-program to provide value bindings matching the
signatures \p{Fax} looks as follows.
\begin{xple}
\k{typedef} \k{char}* Phone\_Number
\k{typedef} \k{int} Status
\#\k{define} error ((Status) 0)
\#\k{define} busy ((Status) 1)
\#\k{define} done ((Status) 2)
Status Fax\_dial(\k{char}* number)\{ \ldots \}
Status Fax\_send(\k{char}* text) \{ \ldots \k{return} done; \ldots \}
Status Fax\_receive(\k{char}** text) \{ \ldots \k{return} done; \ldots \}
\k{void} Fax\_hangup() \{ \ldots \}
\end{xple}
The location binding in the signature of the function \p{Fax\_receive}
is achieved by declaring the argument type for the parameter \p{text}
with an extra level of (pointer) indirection. The compiled C object file
(File ``fax.o'') can be viewed as a collection of function value bindings.
\begin{xple}
faxCObjectFile = \k{bnd}(error=0 busy=1 done=2
                       Fax\_dial=\k{fun}(number :\k{char}*) \ldots
                       Fax\_send=\k{fun}(text :\k{char}*) \ldots
                       Fax\_receive=\k{fun}(\k{var} text :\k{char}*) \ldots
                       Fax\_hangup=\k{fun}() \ldots )
\end{xple}
In reality, the object file does not contain the constants defined by
preprocessor macros and the type information associated with the
function\footnote{See \cite{ElSt90} for an
approach to partially encode the signatures of values in their names to
support a limited form of cross-module type checking in C++.}. The binding
\p{faxCObjectFile} therefore has the following signature:
\begin{xple}
faxCObjectFile :\k{Sig}(Fax\_dial :\k{Any}  Fax\_send :\k{Any}  
                   Fax\_receive :\k{Any}  Fax\_hangup :\k{Any})
\end{xple}
The DBPL language environment provides a \e{generic} (type-dependent)
function (a generator) that is capable of extracting relevant external
bindings specified by a DBPL interface signature \p{Iface} from a given
external binding. In the Tycoon POS model this generator has the
following signature:
\begin{xple}
linkC: \k{Fun}(Iface $<$:\k{Sig}()  prefix :\k{string}  
               externalObject :\k{Sig}()) Iface
\end{xple}
The type signature \p{Iface $<$:\k{Sig}()} matches any actual type
parameter that is an aggregated signature without further constraints on
the signature elements. For example, the interface heading
\p{\k{definition for} C \k{module} Fax} causes the DBPL compiler to
automatically generate the  following module initialization code
\p{linkFax} that calls \p{linkC} with module-specific type and value arguments:
\begin{xple}
linkFax = \k{fun}(imports :\k{Sig}(phone :Phone)) 
              linkC(Iface$\equiv$Fax  prefix=``Fax"  
                    externalObject=faxCObjectFile)
\end{xple}
The prefix ``Fax'' is used to locate the value bindings \p{dial, send,
receive, hangup} in \p{faxCObjectFile} based on the (C) naming convention
that the names of components in an aggregated binding are prefixed by
the name of their enclosing scope. If the generic \e{linkC} function
encounters value and location specifications  in a DBPL signature for
which no matching bindings can be found, a ``link error'' is reported.

An additional level of consistency could be achieved by implementing a
tool that generates C type, constant and function prototype declarations
based on the signature information extracted from a DBPL foreign
definition module (and all its transitively imported
interfaces)\footnote{Similar tools play a central role in window systems
involving the PostScript language \cite{NeWS90} and proposals for
distributed object management\cite{CORBA91}.}. Since modern C compilers
are capable of verifying function declarations against given prototypes,
this tool would guarantee full type consistency for cross-language
bindings (static and dynamic) from DBPL to C. However, in  view of
the fact that the vast majority of external library code is not shipped
as source text but as untyped object code, such a tool is of limited use
in current programming environments.

Since relation types and relation operations are fully integrated into
the DBPL language, they can be freely combined with the cross-language
binding mechanisms:
\begin{xple}
\k{for each} b \k{in} register :contains(n.name, ``Smith'') \k{do} 
         Fax.dial(n.num); Fax.send(\ldots); \k{end}
\end{xple}
It is also possible to call DBPL transactions on bulk objects
from C, e.g., \p{dbpl\_addPrefix()}. 

\subsection{The DBPL/SQL Gateway}

Cross-language linking as described in Sec.~\ref{Sec:Cross-Language} is
an instance-base interoperability mechanism limited to individual
function and data values. DBPL generalizes these concepts to provide
transparent translation of families of data structures and expressions
that are defined in terms of generic types and polymorphic functions.

Analagous to external function bindings, DBPL supports bindings to
external persistent objects in addition to internal persistent DBPL
objects \cite{MRSS92b}.  For example, the following modification of the
header of module \p{PhoneDB} binds the location variables \p{register}
and \p{fees} to \e{external} SQL relations \p{register} and \p{fees}
defined in an Ingres database named \p{SQLPhoneDB}:
\begin{xple}
\k{database definition} \underline{\k{for} Ingres} \k{module} PhoneDB; 
\k{import} Phone;
\ldots 
\k{var} register :Register; fees :Fees;
\k{end} PhoneDB.
\end{xple}
All DBPL statements and expressions referring to these variables are
translated fully transparently into SQL update and selection expressions
submitted to the Ingres SQL database management system.  These SQL
expressions typically take DBPL program variables (value and location
bindings) as arguments and return (set) values that are converted
appropriately for further processing within DBPL. For example, the
query
\begin{xple}
\k{if} \k{all} n \k{in} register n.phone $>$ x \k{then} \ldots \k{end}
\end{xple}
is translated into a \k{select from where} SQL expression that
uses the actual value stored in the DBPL location \p{x} of type
\k{String}. Depending on the cardinality of the set-valued result, a boolean
value is then returned to the compiled DBPL code.

It should be noted that DBPL can handle arbitrarily nested (possibly
recursive) query expressions that mix volatile relations, persistent
DBPL relations residing in local or remote databases and SQL database
relations. Therefore, much care has been devoted to develop evaluation
heuristics that minimize data transfer and make best use of index
information available for individual relations. Evaluation strategies
are not determined at compile-time but depend on cardinality and
index information available at run-time.

Again, a conceptually simple generalization of an existing programming
language concept suffices to overcome the interoperability deficiencies
of todays database programming interfaces that have developed in
a system-driven, bottom-up fashion.


\subsection{Architectural Requirements of Generic Gateway Implementations}
\label{Sec:Requirements}

Although the system details of the DBPL/SQL gateway are quite delicate
and often require ad-hoc case analysis to achieve good system
performance, this specific gateway implementation follows a more general
pattern that directly reflects the model of typed programming languages
in terms of types, signatures, values and bindings presented in
Sec.~\ref{Sec:Model}. In order to  extend a language
$L_{int}$ by a generic gateway to an external language $L_{ext}$ successfully (i.e.,
to embed $L_{ext}$ as a sublanguage of $L_{int}$), the following
conditions have to be met.

The \e{type} syntax of $L_{int}$ must be sufficiently expressive to
capture the structure of values in $L_{ext}$. This may require extensions
to the set of base types (e.g., to handle SQL date, time and table key
values) as well as extensions to the set of type constructors (e.g., to
handle SQL relations, views or indices).  In DBPL, the base type
extensions are covered by user-defined abstract data types, while the
type constructors are mapped to built-in DBPL type constructors. 

There have to be tools to aid in the mapping between 
\e{signatures} in $L_{int}$ and $L_{ext}$. Instead of writing a generator that
maps from Ingres DB schema information to DBPL database definitions or
vice versa, we developed an interactive binding tool that
automatically extracts signature information from DBPL module
descriptions and the Ingres data dictionary and verifies the
compatibility of these separately developed descriptions.

Tool support is also required at run-time to establish value and location
\e{bindings} from names in $L_{int}$ to entities in $L_{ext}$ and vice
versa. In the DBPL/SQL scenario this is achieved by using
\e{DynamicSQL}, a set of library routines shipped with the Ingres DBMS
to create cursors and communication buffers to convert Ingres values
(element-by-element, attribute-by-attribute according to their type
structure) to DBPL values and to pass arguments (of scalar types) to SQL
query strings.

If \e{expressions} of $L_{ext}$ are to be generated from (a subset of)
expressions in $L_{int}$ (e.g., SQL queries based on DBPL queries), the
expression syntax of $L_{int}$ has to be sufficiently general to emulate
high-level external abstractions present in $L_{ext}$. For example,
DBPL's query expressions directly correspond to SQL \k{select from
where} expressions, whereas a mapping from arbitrary imperative loop
statements to SQL expressions does not seem to be feasible.

Finally, there have to be means to ensure that typing assumptions in the
static compilation context of $L_{int}$ (expressed, for example, as
signatures of database variables) are met by the corresponding bindings
provided in $L_{ext}$ at run-time.  In the DBPL/SQL context, this
limited form of dynamic type checking is achieved by having the compiler
generate run-time type representations for external database variables
that are checked during program startup (accessing the SQL data dictionary).

In addition to these linguistic and technical prerequisites, a smooth
integration of internal and external services also requires adequate
architectural support, like access to the scoping and typing phase of
the compiler, support for separate compilation and persistent storage of
type and signature information, or abstract program representations that
support static (and possibly dynamic) program analysis and translation.

\begin{figure}
\begin{center}\leavevmode
\epsfxsize=\figwidth
\epsfbox{dbpl-components.ps}
\end{center}
\caption{Integration of the SQL gateway into the DBPL system architecture}
\label{Fig:dbpl-components}
\end{figure}

The majority of the additional interoperation services (cross-language
binding, cross-platform binding, transparent language translation)
described in this paper are handled by localized extensions of the
layered DBPL architecture displayed in Fig.~\ref{Fig:dbpl-components}.
For example, the layer \p{SQLGate} inserted between the
(predicate-based) transaction management system \p{CTMS} and the
predicate evaluation system \p{CPMS} (the non-recursive query evaluator)
localizes virtually all extensions to the DBPL system required to handle
external databases (6K lines Modula-2 code of a total of 52K lines 
DBPL run-time system code). \p{SQLGate} transparently dispatches
subqueries accessing local database objects to \p{CPMS} amd subqueries
accessing external database objects to Ingres/Oracle.

% 4 -------------------------------------------------------------------
\section{Towards Open Communicating Environments}\label{Sec:4}

After seven years of development, the DBPL system has now reached a
level of maturity and interoperability that makes its linguistic
abstractions readily available for implementors of non-trivial
Persistent Object Systems on several hardware-platforms.\footnote{The DBPL
system is distributed by Hamburg University.}

From a research point of view, an interesting side-effect of this DBPL
implementation effort is an insight into repeating patterns of language
and system extension requirements, some of which are outlined in
Sec.~\ref{Sec:Requirements}. Consequently, our current work in the
Tycoon project investigates languages and architectures that facilitate such
incremental, problem-specific extensions in a type-safe environment.

In contrast to DBPL, Tycoon takes a rather radical approach by not
maintaining upward compatibility with existing programming languages
(Modula-2) and data models (complex-object models). Also its internal
protocols for store access, program representation and linkage do not
adhere to pre-existing standards. The rationale behind the design of
Tycoon is to provide a lean language and system environment that
provides just the kernel services and abstractions needed to define
higher-level, problem-oriented ``languages'' and ``data models''.

The following two sections sketch how Tycoon overcomes limitations of
classical languages and architectures and contributes to the development of
future open communicating environments.

\subsection{Beyond Classical Database System Architectures}

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, bulk data indexing, iteration abstraction, meta-data
management, access control, data distribution 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 services by
strictly separating data modelling, data manipulation and data storage
issues. Horizontal bars in Fig.~\ref{Fig:Tycoon-Layers-Engl.ps} indicate
the three central Tycoon system abstractions:
\begin{itemize}

\item TL is a strongly-typed higher-order polymorphic programming
language based on the notions of types, signatures, values and bindings
as introduced in Sec.~\ref{Sec:Model}.  \TL\ serves as a uniform
application and system programming language and therefore has to support
both, programming using high-level problem-specific data models as well
as the implementation of these data models in terms of low-level
implementation-oriented data structures. Further aspects of \TL\ are
discussed in the Sec.~\ref{Sec:TL}
 
\item TML is a minimal intermediate language (22 instructions)
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.

\item TSP 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).
\end{itemize}

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

This layered protocol-oriented architecture aims at system
\e{scalability} and \e{portability} by de-emphasizing operational
aspects of the protocol implementations. For example,  two implementations 
of \TML\ currently exist, a compact, portable interpreter, immediately executable on a
wide range of hardware-platforms and an optimizing code generator. Both can be combined
freely with several object store implementations ranging from garbage collected, paged
main memory implementations suitable for personal computers to sophisticated
persistent store implementations exploiting virtual memory hardware
available on file servers.

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 interoperability. This functionality had to be emulated in the
DBPL project either by resorting to interpretation techniques (e.g., to
execute access plans generated by the query optimizer) or ad-hoc binding
mechanisms in the distributed DBPL system.

It will be interesting to compare the efficiency of the layered Tycoon
architecture that does not provide set-abstractions at the store level
with the efficiency of traditional, tailored DBMS query interfaces.

\subsection{Beyond First-Order Type Systems}
\label{Sec:TL}

Given the architecture in Fig.~\ref{Fig:Tycoon-Layers-Engl.ps}, several
tasks handled by hard-wired algorithms inside the DBPL runtime system
(Fig.~\ref{Fig:dbpl-components}) or inside an SQL database server can be
defined in the \TL\ language. For example, it is possible to define new
collection types (bulk data structures) and iteration abstractions
(query formalisms) as well as higher-level language concepts for
integrity maintenance and transaction management. In this section, we
 demonstrate merely how these tasks can be delegated to external servers
while giving the user the illusion of a fully integrated persistent
system.

In order to factor out repeating generic programming tasks from
individual applications into reusable library code, \TL\ requires type
abstraction capabilities that are beyond classical first-order type
systems. The type-theoretic starting point for \TL\ is \fsub, a
second-order lambda calculus with subtyping \cite{CMMS91}. This is
extended by a rather small set of standard programming concepts (base
types, tuples, arrays, control structures and exceptions) as found in
other functional or imperative programming languages. Furthermore, the
type concepts of
\fsub\ are generalized to higher-order (in the spirit of
Quest \cite{Card89}), providing the formal basis for \e{generic}
interoperability as sketched in the Sec.~\ref{Sec:3}.

In the following, we express an idea how the type-safe integration of
external generic servers is accomplished in the Tycoon system. Due to
space limitations we cannot go into the details of the language \TL
but based on the informal Tycoon model presented in
Sec.~\ref{Sec:Model} the reader should be able to follow the examples.
A formal definition of \TL\ can be found in \cite{MaSc92c}.  Here is a
(simplified) interface taken from the current Tycoon libraries that
describes the signatures of the polymorphic functions exported by an
SQL server:
\begin{xple}
\k{interface} SQL \k{export}
  error :\k{Exception with} sqlError :String \k{end}
  Table(E$<$:\k{Tuple} \k{end})$<$:\k{Ok}
  openTable(\k{Dyn} E$<$:\k{Ok} name:String):Table(E)
  insert(E$<$:\k{Ok} \k{var} table:Table(E) tuple:E):\k{Ok}  
  :+, :-(E$<$:\k{Ok} \k{var} table:Table(E) tuples:Table(E)):\k{Ok}
  delete(E$<$:\k{Ok} \k{var} table:Table(E) where(: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} which corresponds to type
\k{Any} in Sec.~\ref{Sec:Model}). 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 \e{generic} functions. There may be several modules
implementing this interface, i.e.\ defining type, value and location
bindings that match the specified signatures:
\begin{xple}
\k{module} ingres \k{import} DynamicSQL \k{export}
  \k{let} error=\k{exception} ``Ingres Error'' 
                \k{with} sqlError :String \k{end}
  \k{Let} Table(E$<$:\k{Ok}) = 
      \k{Tuple} hostId, tableId :String \ldots \k{end}
  \k{let} openTable(\k{Dyn} E$<$:\k{Ok} name:String) =
      \k{begin} ... \k{end}
  \ldots
\k{end}
\end{xple}
The scope for modules and interface names is represented explicitly via
libraries: 
\begin{xple}
\k{library} SQLLib \k{with}
  \k{interface} DynamicSQL \ldots SQL
  \k{module} \ldots ingres :SQL  oracle :SQL
  \k{hide} DynamicSQL \ldots
\k{end}
\end{xple}
The library \p{SQLLib} exports an interface \p{SQL} and two modules
implementing this interface, and it hides several local modules required for
gateway implementation. Libraries typically appear as components of
larger libraries:
\begin{xple}
\k{library} PhoneApplication \k{with}
  \k{library} SQLLib 
  \k{interface} PhoneDB  
  \k{module} phoneDB :PhoneDB  test :Main
\k{end}
\end{xple}
The \p{PhoneApplication} subsumes an interface to an external
Ingres \p{PhoneDB} (see DB definition in Sec.~\ref{Keyword:IngresDB}):
\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 relation variables is established
in the module implementation:
\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} test \k{import} ingres phoneDB \k{export}
  \k{open} phoneDB
  ingres.insert(register \k{tuple} ``Peter'' ``249'' \k{end})
  ingres.delete(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 systems. 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 compilers. (Further
examples of \TL\ signatures for object-oriented and deductive data models are
given in \cite{Matt93}).

As a specific example, the SQL statement \p{delete \ldots from
\ldots where \ldots } removes all elements of a table that fulfil 
a given predicate which has to be compatible with the table structure.
These semantic restrictions are  captured correctly by the signature of
the function \p{delete} in the interface \p{SQL}. It specifies that the
function works uniformly over all types \p{E} given a location binding
to a \p{table} with elements of type \p{E} and a binding to a function
\p{where} mapping elements of type \p{E} to a boolean value (i.e.\ a
predicate on domain \p{E}).

Given the flexibility of higher-order type systems, it is not
necessary to limit the language to a fixed set of base types. In fact,
Tycoon does not provide any built-in operations on base types (except the
conditional for booleans). The usual arithmetic and string operations
are all implemented in external libraries that are (dynamically) bound
to the Tycoon system. This makes it particularly easy to modify the
internal representation of the base types or to add new base types with
their associated operations as abstract data types (e.g.~sound or pixel
data types).

% 5 --------------------------------------------------------------------
\section{Conclusion}

Within a uniform framework based on the notions of types, signatures,
values and bindings, this paper presents two approaches to reduce the
complexity of Persistent Object Systems and to  increase significantly
programmer productivity.

The relational database language DBPL provides built-in system and
language support for a uniform handling of computational objects whether
they are local or remote, short-lived or persistent, small or large.
Generic gateways provide transparent and optimizing access from DBPL to
external programming languages and commercial database systems.

The Tycoon environment minimizes the amount of built-in system and
language support by exploiting higher-order type concepts and by
strictly separating the issues of data storage, data manipulation and
data modelling into three distinct formalisms and system layers.

We expect such lean languages and systems, where most of the
functionality of a Persistent Object System is achieved by importing
external services into a conceptually sound linguistic framework, to
possess a higher potential for scalability, portability and interoperability
than classical ``all-in-one'' database systems.

% ----------------------------------------------------------------------
{%\small
\bibliographystyle{plain}
\bibliography{florian}
}

\end{document}
