% File:    kiev90-3.tex
% Author:  F. Matthes
% Date:    7.2.1991
%
\section{Towards a Language for Database Application Systems}
\label{Quest}

In this section we give arguments to support our claim that essential
parts of the language technology necessary to fulfill the requirements
outlined in the previous section already exist in the programming
language research community.

Since our goal is to expoit the same linguistic platform for application
programming and for database environment extension, the choice of a
uniform underlying programming paradigm becomes crucial. Following the
distinction in \cite{BrMy86} between computational and semantic models,
our language will certainly be based on a computational model.
Furthermore, since virtually all practical algorithms for DBMS
implementation heavily rely on the concept of state and state
transition, a \e{pure} functional or relational language, like Haskell
\cite{Hudak89}, Machiavelli \cite{OBBT89} or Life
\cite{AKN89} does not seem to be a suitable starting point.

On the other hand, languages like Modula-3 \cite{Card88} or Eiffel
\cite{Meyer88} are too biased towards an ``object-oriented'' execution
model to allow the definition of suitable layers of abstraction, e.g. to
emulate the built-in functionality of set- and predicate-oriented
languages like DBPL \cite{ScMa90b}.

We expect the general flavor of a language for Database Application
System programming to be interactive, compiled, strongly-typed,
applicative-order, incorporating higher-order functions and
imperative features and a primitive set of built-in mechanisms to
achieve persistence, atomicity and concurrency in shared environments.

In order to access pre-existing functionality (e.g. operating system
services, window-management services, application libraries) from within
the language and to make best use of the hardware resources available,
the language implementation should be based on well-developed,
optimizing compilation technology.

As an example of a particularly well-developed and consistent language
we present Quest \cite{Card89}, a functional language with imperative
features, explicit type quantification and subtyping rules inductively
defined over all type constructions. Although Quest lacks important
operational features required in database programming, e.g.\ persistence
management with incremental loading strategies, primitives for
concurrency control and recovery, languages like Quest seem to be the
right platform to start with since they support the abstraction
mechanisms discussed in the previous section without restricting their
application to specific contexts.


\subsection{Generalized Data Abstraction}

It should be clear that Database Application Systems will be composed of
a large number and variety of denotable language objects like values,
variables, functions, types, function types, modules, module interfaces,
database schemas, databases, views and transactions. Our primary concern
is therefore not the set of built-in language primitives, but set of
abstraction mechanisms available to cope with the variety and complexity
of the language objects te be expected in Database Application Systems.

\subsubsection{Classification by Types and Kinds}
\label{Classification}

A specific form of \e{classification} underlies schema definitions
in database systems and type declarations in programming languages:
They both classify run-time values according to their statically-known
structure expressed by means of type constructors.

For several tasks in database modelling and system programming, 
traditional, mono\-mor\-phic classification schemes which only allow to
assign a single type to a given variable proved to be too limited.
Polymorphic languages, like ML or object-oriented languages, usually
have rich structures at the type level, e.g. to describe functions
that operate uniformly over values of a {\em set of types} or to
denote {\em orderings} among types expressed by means of inheritance
hierachies. The richness of the type level now calls again for a
\e{classification} of type expressions. As discussed in detail in
\cite{Card88b}, this can be accomplished by introducing a three-level
structure of language entities:
\begin{description}
\item[Values] and functions inhabit level 0, they are classified by
means of
\item[Types] and type operators at level 1 which in turn are
classified by means of
\item[Kinds] at level 2. Kinds can be utilized, for example, to distinguish
between ``plain'' type variables and parameterized type operators.
\end{description}
As will be demonstrated later in section \ref{Classification}, types and type
operators as first-class denotable language objects allow to achieve a
high degree of uniformity between built-in and user-defined
functionality. For example, the typing rules underlying relational
algebra or relational calculus can be adequately defined using
parameterized type operators.

The idea to resolve the mismatch between the expressiveness of untyped
languages (like Smalltalk or Lisp) and the security and descriptive
power of strongly typed languages (like Modula-2, Modula-3 or
Standard-ML) by including types as denotable and manipulable language
objects is not new. However, early languages pursueing this idea
\cite{Harl84,BuLa84} had to give up static type checking.  Quest also
has exceptionally rich structures at the type level, including type
variables, subtyping and recursive type operators.  In contrast to the
above mentioned languages, \e{static} type checking is preserved by
introducing a stratified three level structure and by controlling the
interaction between entities of the three levels. In general,
higher-level entities act as specifications for lower-level entities and
must therefore not depend on the outcome of operations on lower-level
entities.

In this text we adopt the conventions of \cite{Card89} and use
lower-case identifiers for level 0 entities, capitalized
identifiers for level 1 entities and all caps for level 2 entities.

The following three examples declare and bind four value
variables, three type variables, and one kind variable:
\begin{xple}
\k{let} macSerialNum = 4711
\k{let} keyboard = \k{tuple} \k{let} sn = 3132  \k{let} name = "Keyboard" \k{end}
\k{let} monitor = \k{tuple} \k{let} sn = 1344 \k{let} name = "Monitor" \k{end}
\k{let} nameOf = \k{fun} (p:Part):String = p.name

\k{Let} SerialNum = Int
\k{Let} Part = \k{Tuple} sn:SerialNum name:String \k{end}
\k{Let} PartFunction = \k{Fun} (p:Part):String

\k{DEF} COLLECTION = \k{OPER} (E::TYPE)::TYPE 
\end{xple}
The function \kw{nameOf} of type \kw{PartFunction} exemplifies
an important property of the uniform classification schemes we are
interested in: Functions introduced by means of the function value
constructor \kw{\k{fun}} are \e{first-class} citizens of level 0.
In particular, they are classified according to their signature and
result type by means of function types (level 1 entities), 
denoted by the function type constructor \kw{\k{Fun}}. 

Examples in subsequent sections will demonstrate that the 
embedding of functions as true level 0 entities leads to a
substantial \e{reduction} of language complexity. Important
language concepts like higher-order functions, polymorphic
functions, procedural attachment and abstract data types can all be
reduced to more primitive concepts, simply by classifying functions
as values. 

\subsubsection{Aggregation by Signatures and Bindings}

\label{Signatures}
In programming languages and database models the concept of
\e{aggregation} is captured traditionally by means of labeled
records or tuples composed of value components \cite{SmSm77,Kent79}.
Relational and deductive databases typically constrain these components
to be values of basic (unstructured) types. By loosening this constraint
one arrives at more expressive (non-standard) data models based on
nesting \cite{AFS89}.  Object-oriented models go one step further by
allowing functions as attributes of ``objects''. This procedural
attachment is intended to capture the ``behavior'' of objects.

Quest exemplifies how to liberate the concept of aggregation from the 
narrow interpretation as simple record definition, namely by
introducing the notion of generalized \e{signatures} and
\e{bindings}. Extending ideas of Landin and Burstall and Lampson 
\cite{BuLa84}, Quest introduces a correspondence betweeen declarations, 
formal parameters and interfaces, all based on common syntax, and also
between definitions, actual parameters, and modules.

A \e{signature} is a (possibly empty) \e{ordered} association of
types to value variables and of kinds to type variables,  where
all the variables have distinct names. 
\begin{xple}
sn:SerialNum  name:String  madeFrom:Set(Part)
\end{xple}
The above signature declares value variables \kw{sn},
\kw{name} and \kw{madeFrom} of type \kw{SerialNum}, \kw{String},
and \kw{Set(Part)}, respectively. The following
signature introduces a type variable \kw{T}, a type operator
variable \kw{C} and a value variable \kw{c} of type \kw{C(T)}.
Note that signatures introduce variables from left to right and
that such variables can be used after their introduction.
\begin{xple} 
T::TYPE  C::COLLECTION  c:C(T)
\end{xple}

\e{Bindings} are (possibly empty) ordered associations of values
to value variables and types to type variables, where all the
variables have distinct names, for example:
\begin{xple}
\k{let} sn = macSerialNum 
\k{let} name = "Mac II"
\k{let} madeFrom = set.create \k{of} keyboard monitor \k{end}
\end{xple}
The binding
\begin{xple}
\k{Let} T = Part \k{Let} C = Set  \k{let} c = set.create \k{of} keyboard \k{end}
\end{xple}
binds the the type variable \kw{T} to the type \kw{Part}
declared in the previous section, the type operator variable \kw{C}
to the type constructor \kw{Set} and, finally, the value
variable \kw{c} to a singleton set of type \kw{Set(Part)}.

By decoupling aggregation from the tuple construction, we can
aggregate also in formal parameter positions and in module
interfaces and apply aggregation uniformly to values,
functions, types and type operators: 
\begin{xple}
\k{Let} Display = \k{Fun} (T::TYPE C::COLLECTION c:C(T)) Ok
\k{Let} Collection = \k{Tuple} T::TYPE C::COLLECTION c:C(T) \k{end}  
\k{Interface} CollectionInterface \k{import} \ldots\
\k{export}
   T::TYPE   C::COLLECTION   c:C(T)
\k{end}
\end{xple}

There are subtle issues in defining the instance-of relationhip between
bindings and signatures, for example, whether the variable names or the
order of signature components should matter. The interested reader is
referred to \cite{Card89} for a discussion of these topics and the
alternatives supported in Quest.

To give an idea of the power and flexibility gained by
the generalized notion of signatures, we show examples of how
to develop a refined description of composite parts:
\begin{xple}
\k{let} myMac = \k{tuple} 
     \k{let} sn = macSerialNum  
     \k{let} name = "Mac II" 
     \k{let} madeFrom = set.create \k{of} keyboard monitor \k{end}
\k{end}
\k{Let} CompPart = \k{Tuple} sn:SerialNum name:String madeFrom:Set(Part) \k{end}
\end{xple}
The value \kw{myMac} is a simple aggregation of \e{independent} 
value variables. Accordingly, the signature of the tuple type
\kw{CompPart} is also a simple aggregation of independent type
variables.
A first example for the need to be able to express 
\e{dependencies} between the components of a binding is the
aggregation of function values referring to ``local'' value
variables:
\begin{xple}
\k{let} myMac1 = \k{tuple} 
     \k{let} sn = macSerialNum  
     \k{let} name = "Mac II" 
     \k{let} madeFrom = set.create \k{of} keyboard monitor \k{end}
     \k{let} printMyself = \k{fun}():String %
"composite part " \& name \& " " \& conv.int(sn)
\k{end}
\k{Let} CompPart = \k{Tuple} 
     sn:SerialNum  name:String  madeFrom:Set(Part)  printMyself:\k{Fun}():String
\k{end}
\end{xple}
A somewhat more elaborated example may illustrate the need
for dependencies between components of a signature:
\begin{xple}
\k{Let} SerialNum = \k{Tuple} 
  T::TYPE  first():T  next(sn:T):T  equal(sn1,sn2:T):Bool  asString(sn:T):String 
\k{end}
\end{xple}
Values of type \kw{SerialNum} are tuples of five components,
namely a type \kw{T} and four operations on values of type
\kw{T}. The tuple type \kw{SerialNum} can therefore be 
understood as the signature of an algebra for values of type \kw{T}
capturing the essential properties of serial numbers: Serial numbers can
be created (\kw{first}, \kw{next}), there is an equality defined over
them, and they are printable entities.  A crucial constraint expressed
via dependencies in this signature is the requirement that, for example,
the result of the application of
\kw{first} has to be a legal argument for the application of \kw{next}
or
\kw{asString}. Note that \kw{SerialNum} is a level 1 entity that
classifies a set of level 0 entities, in particular the 
following implementation of serial numbers by means of integer
numbers:
\begin{xple}
\k{let} intSerialNum = \k{tuple}
  \k{Let} T = Int
  \k{let} first():T = 0
  \k{let} next(sn:T):T = sn + 1
  \k{let} equal(sn1,sn2:T):Bool = sn1 \k{is} sn2
  \k{let} asString(sn:T):String = conv.int(sn) 
\k{end}
\end{xple}

\subsubsection{Generalization by Subsignatures and Subtyping}

Object-oriented models emphasize the need to capture generalization
relationships between object classes and to view objects not only as
members of their most specialized class, but also as members of more
general classes. Typically, this is accomplished by defining static
\e{is-a} relationships between classes and by indicating the most
specialized type of an object at object-creation time.

Again, Quest takes a somewhat less biased approach to capture the
concept of \e{generalization}. Instead of bundling classification,
generalization and dynamic extent management in the concept of a class,
specialization relationships are defined in Quest inductively by means
of \e{subtyping} rules between all types in level 1.  The subtyping
relation, written $<:$, is defined such that if \kw{x} has type \kw{A}
and \kw{A$<:$B} then \kw{x} has also type \kw{B}.  The syntax for kind
terms of level 2 allows to denote the collection of all subtypes of a
given type \kw{B} by a kind of the form
\kw{POWER(B)}. Then \kw{A::POWER(B)} and \kw{A$<:$B} have the same
meaning. There is also a \e{subkind} relationship, written $<::$, in
level 2, derived from the subtype relationship by 
\kw{POWER(A)$<::$POWER(B)} if \kw{A$<:$B} and 
\kw{POWER(A)$<::$TYPE} for all \kw{A::TYPE}.

\label{Subsignature} In this paper we only discuss those subtype
(subkind) relationships which are induced by the notion of
\e{subsignatures}. A signature \kw{S} is a subsignature of a
signature \kw{S'} if it has the same number of components as
\kw{S'}, with the same names and in the same order, and if the
component types (or kinds) of \kw{S} are subtypes (or subkinds)
of the corresponding components in \kw{S'}. For example, 
the declarations of the previous sections
\begin{xple}
\k{Let} Part = \k{Tuple} sn:SerialNum name:String \k{end}
\k{Let} CompPart = \k{Tuple} sn:SerialNum name:String madeFrom:Set(Part) \k{end} 
\end{xple}
imply \kw{CompPart$<:$Part}. It should be noted that in particular the
existence of recursive and parameterized type definitions requires
non-trivial typing rules for the verification of subtyping relationships
\cite{AmCa90}.

The main conceptual advantage of deriving subtyping
relationships based on the generalized notion of signatures is
to uniformly capture the concept ``partiality'' as it occurs in
the specification of data, functions and modules. Other
important aspects of this approach (e.g. the interaction with
type abstraction in order to constrain inferred subtype
relationships) are beyound the scope of this paper. As an example for the use of subtyping information, take the
function returning the name of a part:
\begin{xple}
\k{let} nameOf = \k{fun}(p:Part):String  p.name
\end{xple}
Since \kw{CompPart$<:$Part}, the following function applications
are both correct:
\begin{xple}
nameOf( keyboard ) 
nameOf( myMac )
\end{xple}
This particular form of genericity achieved by means of implicit
subtyping rules is crucial for the quality of Database Application
Systems. It allows to build systems that are capable of operating
uniformly over a wide range of specialized data structures, even 
if the specialization was the result of an \e{unexpected} extension
long after the subsystem exporting the generic function was
implemented and delivered.

A formal treatment of Quest-like subtype relationships and a semantics
for values, types and kinds in Quest can be found in
\cite{CaLo90,AmCa90}


\subsection{Localization by Parameterization} 
\label{Parameterization}

Until recently, programming languages and database systems focussed on
different localization tasks: Programming languages employed lambda
abstraction and parameterization mainly to define algorithms and to
instantiate them with suitable parameters in different contexts.
Database systems on the other hand recognized the need to share
(database) variables between multiple applications and to localize the
operational support (transaction management, set evaluation) for these
database variables within a central DBMS.  A logical and physical
database schema can then be understood as a very detailed
parameterization to be used during the instantiation of the generic data
structures offered by a given database (model).

Quest incorporates an important building block to regularize
these up to now separated approaches by generalizing the concept of
\e{parameterization} and binding. One can define parameterized
function values, parameterized type operators and
(indirectly) parameterized kind expressions.

The previous subsection already demonstrated the definition of a
parameterized function, \kw{nameOf}, exhibiting subtype polymorphism.
A more explicit treatment of polymorphic functions can be achieved by
the definition of (kinded) type parameters:
\begin{xple}
\k{let} pair(A::TYPE x:A): \k{Tuple} first:A second:A \k{end} = 
            \k{tuple} \k{let} first = x \k{let} second = x \k{end} 
\end{xple}
The polymorphic function \kw{pair} takes a parameter \kw{x} of type
\kw{A} and returns a tuple that contains \kw{x} twice. The fact
that \kw{x} can be of any type \kw{A} is expressed by defining \kw{A} as
an additional type parameter of \kw{pair}. Again, note that the type
variable \kw{A} is also used in the definition of the result type of
\kw{pair}. The last of the following three applications of
\kw{pair} illustrates that actual type parameters can also be
\e{inferred} in Quest -- relieving application programmers from
supplying (essentially redundant) type parameters:
\begin{xple} 
pair(:Int  3)
pair(:String "ABC")
pair("ABC")
\end{xple}
Since both types (\kw{Int} and \kw{String}) are of kind \kw{TYPE},
the above actual parameter substitutions are successfully
kind-checked at compile-time.

Set types (tacitly assumed to be pre-defined in the previous
sections) can be fully defined within Quest by means of a type
expression aggregating a parameterized type operator \kw{Set(E)}
and the signatures of the admissible set operations operating on
values of this type:

\label{SetInterface}
\begin{xple}
\k{Let} SetInterface = \k{Tuple}
  Set(E::TYPE)::TYPE
  create(E::TYPE from:Array(E)):Set(E)
  empty(E::TYPE x:Set(E)):Bool
  size(E::TYPE x:Set(E)):Int
  member(E::TYPE e:E x:Set(E)):Bool
  get(E::TYPE x:Set(E)):E
  rest(E::TYPE x:Set(E)):Set(E)
  add(E::TYPE e:E x:Set(E)):Set(E)
  union,difference,intersect(E::TYPE x,y:Set(E)):Set(E)
  equal(E::TYPE x,y:Set(E)):Bool
\k{end}
\end{xple}
Section \ref{Streams} will provide further details on defining set 
abstractions that can be instantiated with arbitrary element types
\kw{E} of kind \kw{TYPE}. The above definition of \kw{Set} in 
particular expresses the constraint that the arguments of set functions
like \kw{intersection} have to be sets of the same element type and that
they return homogeneous sets. Instantiations of the type operator look
as follows:
\begin{xple}
Set(Part)
Set(Set(CompPart))
\end{xple}
These are two examples of set operations:
\begin{xple}
\k{let} allParts = union(parts baseParts)
\k{if} equal(parts allParts) \k{then} \ldots\ \k{end}
\end{xple}


Other interesting type aspects inherent in traditional database systems
can also be expressed by means of higher-order type operators. For
example, the traditional quantifiers {\tt EXIST} and {\tt ALL} present
in SQL as well as a non-standard {\tt MAJORITY} quantifier proposed for
Starburst \cite{HFLP89}, all share the same signature pattern denoted by
the following parameterized type constructor:
\begin{xple}
\k{Let} Quantifier(E::TYPE Coll::\k{POWER}(Set(E)) = 
      \k{Fun}(collection:Coll predicate(:E):Bool):Bool
\end{xple}
A quantifier can be instantiated with arbitrary element types
\kw{E}, but only with collection types \kw{Coll} of kind
\kw{POWER(Set(E))}, i.e.\ subtypes of sets of \kw{E}.
A very specific instance of such a quantifier can be defined and
applied as follows:
\begin{xple}
\k{let} \k{rec} somePart:Quantifier(Part Set(Part)) = 
    \k{fun}(collection:Set(Part) predicate(:Part):Bool) 
        \k{if} empty(collection) \k{then} false
        \k{elsif} predicate(get(collection)) \k{then} true
        \k{else} somePart(rest(collection) predicate)
        \k{end}
\k{let} b:Bool = somePart(parts \k{fun}(p:Part):Bool p.sn $>$ 4711)
\end{xple}
To summarize, this examples illustrates how parameterized types allow to
``factor out'' common protocols from individual application programs
into the database environment, and how they can be utilized to enforce
global ``standards'', e.g. for the definition of iteration facilities.
As will be discussed in section \ref{Streams}, this standardization of
protocols is important to provide enhanced operational support by a
database environment that may choose optimized implementations for a
given protocol based on case analysis of the actual protocol parameters
(e.g. indexed access based on \kw{p.sn}).

Parameterization is the main tool to achieve localization of
functionality in complex systems, more specialized mechanisms, like
\e{exceptions}, are beyond the scope of this paper \cite{Card89,Borg88}.


\subsection{Implementation Abstraction by Scoping}

The term \e{implementation abstraction} as introduced in the previous
section subsumes the more specific (but also overloaded) term
\e{encapsulation} as used in object-oriented systems. In general, we are
interested in defining interfaces to data structures, functions, types
etc. that hide particular implementation details (e.g. local
declarations, import-export relationships, subtyping relationships) that
are only accidental and should be left open for future change without
affecting the correctness of clients utilizing the interface. Statically
nested procedure scopes, modules, encapsulated class declarations and
abstract data types in programming languages, as well as views and the
concept of data independence in database environments can all be
mapped, more or less directly, to an elementary scoping mechanism.

In Quest, the scope of a value, type and kind identifier is 
limited  to the binding or signature introducing the name. It can be
entered via dot notation (field selection). Already in 
section \ref{Subsignature}, the notion of a \e{subsignature} has been
introduced. It is also the key to a generalized understanding of
implementation abstraction:
\begin{xple}
\k{let} View = \k{Tuple} a:Int b:String \k{end} 
\k{let} x:View = \k{tuple} \k{let} a = 3  \k{let} b = "ABC" \k{let} c = true \k{end} 
\end{xple}
By declaring \kw{x} as being of type \kw{View}, with signature
\kw{a:Int b:String}, only tuple selections \kw{x.a} and \kw{x.b} are
valid on \kw{x}, although the actual binding contains a third
value variable binding \kw{\k{let} c=true}. This example shows a
general matching rule between bindings and signatures: A signature
\kw{S} is also satisfied by a binding that has an extended
subsignature of \kw{S}.  

Due to the generalized interpretation of signatures and bindings in
Quest (see section~\ref{Signatures}), this matching rule again does not
only apply to record types but also to module interfaces and function
declarations.

