% File:     dataMod.tex
% Date:     26-jul-1995
% Author:   Florian Matthes, Joachim W. Schmidt, Jens Wahlen
% Purpose:  F2 Book contribution

\documentstyle[xple_sl,epsf]{clmult01}

\pagestyle{myheadings}

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

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

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

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

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

\title{Chapter 3.2.3\\Using Extensible Grammars for Data Modelling}

\author{Florian Matthes \and Joachim W. Schmidt \and Jens Wahlen}

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

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

\begin{document}

\authorrunning{Florian Matthes \and Joachim W. Schmidt \and Jens Wahlen}
\titlerunning{Using Extensible Grammars for Data Modelling}

\maketitle

\abstract{We present a systematic approach to the rapid implementation of
high-level data models and query languages in the polymorphic
higher-order programming language TL. The static semantics of data model
constructs are captured by a mapping to polymorphic types and associated
data constructor and selector functions. The dynamic semantics of query
languages are realised by a mapping to bulk data types and iteration
abstractions. Contrary to conventional approaches, these two mappings
are specified by user-defined grammar extensions of the target language
TL based on user-defined library code and not by separate tools in the
programming environment. We give examples of this syntax-directed
approach to data modelling and discuss its advantages and limitations.}

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

\section{Introduction and Motivation}

To address the modelling requirements of advanced data-intensive
applications, a large number of high-level data models and query
languages have been proposed in the literature to overcome the
limitations of existing relational, deductive or object-oriented models.

Unfortunately, the implementation of a new data model or query language
for evaluation purposes turns out to be a rather complex task since it
requires non-trivial language processing, software engineering and
database system construction know-how. Therefore, such data model
proposals lead either to ambitious long-term database system development
projects (see, e.g., \cite{Ston90} and \cite{ScMa94}, synopsis in Chapter 2.1.2) with a very long
design-implementation-evaluation cycle, or, more frequently, to closed
toy implementations that lack the operational support required for
experiments in a realistic setting (persistence, interfaces to
production systems, user interface support).

Due to their orthogonality and their full integration of persistent
data, code and meta-data management, persistent higher-order languages
constitute a promising platform for the rapid implementation of
high-level data models and their query languages. The static semantics
of data model constructs can be captured by a mapping to polymorphic
types and associated data constructor and selector functions. The
dynamic semantics of query languages can be realised by a mapping to
bulk data types and iteration abstractions in the persistent programming
language.

The mapping itself can be achieved either by standard source-code to
source-code translators (B-Tool \cite{BMSW89} for DBPL, Sidereus
\cite{ACCP89} for Galileo) or by \e{reflective} code generation
techniques \cite{SSW92} (see also Chapter 3.2.2) that exploit the fact that the target
language (run-time environment) and the code generator (compile-time
environment) are tightly integrated in many persistent systems and that
typed persistent program representations can be utilized instead of
linear source-code.

In this paper, we report on our experience using a third mapping
option that exploits \e{extensible grammars} as developed in
\cite{CMA94,CMA94a} and implemented in the Tycoon system
(see Chapter 2.1.4) to translate systematically from declarations and statements of a high-level data model
down to type and value expressions of the polymorphic Tycoon language TL
(see Chapter 1.1.1). 

This paper is organized as follows: We first introduce the concept and
notation of extensible grammars by a simple programming language
example. In section~\ref{general} we give an overview of our
syntax-driven approach to data model and query language
implementation. We then illustrate in section~\ref{Sec:Iter} this
approach through a small example (SQL-style queries over multiple bulk
types). Section~\ref{Sec:Fibo} summarizes our experience gained in the
Tycoon/Fibonacci add-on experiment, a larger exercise in data model
implementation. The paper concludes with a comparison of our approach with
generator-based techniques to data-model implementation.

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

\section{Extensible Grammars}
\label{extGra}

In this section we introduce the concept and notation of extensible
grammars using a simple programming language example. We also explain how
extensible grammars fit into the Tycoon system architecture
(see Chapter 2.1.4).

\subsection{Dynamic Syntax Extensions}

The Tycoon language TL aims at minimality and orthogonality of semantic
concepts which is also reflected by its syntax that provides only a
small number of keywords and syntactic forms.

However, such a syntactic austerity may lead to stereotypical
programming patterns in application code. As a simple example, consider
a programming language that provides only a single \k{loop \ldots exit
\ldots end} iteration construct. Other common loop structures
(\k{while}, \k{repeat}, \k{for}) have to be expressed by systematic
combinations of \k{loop} and \k{if} statements.

The idea behind extensible grammars is to provide programmers (or, more
realistically speaking, application library designers) with a generic
mechanism to introduce tailored syntax for the application domain at
hand.  The use of tailored syntactic forms often leads to more readable
and understandable application code and helps to avoid accidental
programming errors in repeating code patterns.

For example, the following dynamic TL syntax extension introduces a
block-structured \k{for \ldots to \ldots do \ldots end} statement by a
syntax-directed rewriting into a standard TL \k{loop} statement.
\begin{xple}
  \k{grammar}
     value :Value \k{$\mid$==}
          ''for'' x=ide ''='' l=value ''to'' h=value ''do'' b=bindings ''end'' 
          hv=\k{unique}
          \k{=$>$} value\k{$<<\mid$ begin}
                                 \k{let} hv = h
                                 \k{let} \k{var} x = l 
                                 \k{loop if} x $>$ hv \k{then exit else} b  x:=x+1 \k{end}
                              \k{end $\mid>>$}
  \k{end}
\end{xple}
Grammar definitions can be embedded freely into TL source code and therefore
have to be enclosed in a \k{grammar end} block. In the example above,
the syntax for TL \p{value}s is extended (indicated by the operator
\p{$\mid$==}) by a new production that consists of a syntax definition
preceding the arrow \p{=$>$} and a pattern enclosed in $<<\mid$ $\mid>>$
that defines a \p{value} which is to be generated whenever the new syntax
appears in the input program. The pattern utilizes pattern variables
(\p{x, l, h, b, hv}) which are instantiated on expansion of a pattern
with concrete identifiers (\p{x, hv}) or with complete subexpressions
(\p{l, h, b}) as defined by the pattern variable bindings to the left of
the arrow \p{=$>$}. For example, the loop
\begin{xple}
  \k{let} g = 40
  \k{for} i = 1 \k{to} g+7 \k{do} a[i]:=g \k{end}
\end{xple}
is rewritten into the TL program
\begin{xple}
  \k{let} g = 40
  \k{begin}
     \k{let} hv = g+7
     \k{let} \k{var} i = 1 
     \k{loop if} i $>$ hv \k{then exit else} a[i]:=g  i:=i+1 \k{end}
  \k{end}
\end{xple}
TL grammar definitions are statically sort-checked. For example, the
production \p{value} is checked to generate expressions of sort
\p{Value} only. Similarly, the productions \p{ide} and \p{bindings} are
guaranteed to return individual identifiers and sequences of bindings,
respectively.

A syntax extension gives also a precise definition of the scoping,
typing and evaluation rules for each newly defined language construct in
terms of the scoping, typing and evaluation rules of the underlying base
language.  In the example above, the following rules apply:\footnote{An
alternative loop semantics can be realised easily by local changes to
the syntax definition.}

\begin{itemize}

\item The scope of the loop variable \p{x} is delimited by the loop body
\p{b}. Inside \p{b}, a loop variable \p{x} hides a variable \p{x} in an
outer scope.  All other global variables are visible in the
subexpressions \p{l, h} and \p{b}.  The binding \p{hv=\k{unique}}
ensures that on expansion, the identifier \p{hv} used as an auxiliary
variable is chosen to be different from all other variables in the
program and therefore remains invisible in all subexpressions.

\item The loop variable \p{x} has to be of type \p{Int} since it
appears as an argument to the integer infix function \p{"$>$"}. This
implies that the start and end expressions (\p{l} and \p{h}) also have
to be of type \p{Int}. Assignments to the loop variable in \p{b} are
allowed.

\item The start and end expressions \p{l} and \p{h} are evaluated
only once, \p{h} is evaluated before \p{l}. 

\end{itemize}
%
Grammar extensions can be layered without restrictions, for example, a
vector sum could be defined by a mapping onto a \k{for} loop.

In addition to the production extension operator \k{$\mid$==} used in
the example above, TL provides two other operators to destructively
override production definitions and to introduce new productions
avoiding name clashes with existing productions.

As described in \cite{CMA94,CMA94a}, TL's extensible grammars are
superior to other syntax definition formalisms since they respect
static, block-structured scoping and avoid unwanted name clashes, unlike macro definitions and preprocessor-based systems.


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

\subsection{Initial Syntax Definition}

The previous subsection explained how new syntactic forms can be defined
based on an existing syntax. To fully decouple the concrete syntax from
the TL abstract syntax, the initial TL syntax is not hard-wired into the
compiler but provided as a grammar source file. In the current version
of our system, this file is compiled once for each persistent store. For
example, the syntax of the \k{loop} and \k{exit} statements is defined
initially as follows using the production definition operator \p{"==="}: 
\begin{xple}
  \k{grammar}
     value:Value \k{===}  \ldots
       \k{$\mid$} ''loop'' b=bindings ''end'' \k{=$>$} mkValueLoop(b)
       \k{$\mid$} "exit" \k{=$>$} mkValueExit()
       \k{$\mid$} \ldots
  \k{end}
\end{xple}
The notation to specify the concrete syntax and pattern-variable
bindings on the left-hand side of the productions is identical to the
one used for dynamic syntax extensions. The right-hand side consists of
constructor applications (\p{mkValueLoop, mkValueExit}). At compiler
definition time, the names and signatures (argument and result sorts) of
all TL constructors are made available to the extensible grammar front
end. These constructors correspond directly to functions in the TL
compiler that create typed program representations (abstract syntax
trees).

Despite its rich language model, TL provides language objects of only
four different semantic domains which simplifies the orthogonal
combination of these objects in the mapping process for a higher-level
data model. These semantic domains correspond to the following built-in
sorts used in TL grammars:
\begin{itemize}

\item The sort \p{Type} subsumes closed and parameterized type
expressions like base types, structured types and higher-order type
operators. The canonical type \k{Ok} is the supertype of all closed
types and contains the canonical value \k{ok}.

\item The sort \p{Value} subsumes expressions and side-effecting
statements. A statement returns the canonical value \k{ok}. The result
of an expression used in a statement context is discarded.

\item \p{Bindings} are ordered sequences of identifier/type or
identifier/value pairs. If identifiers are omitted, so-called anonymous
bindings are defined. This makes it possible, for example, to represent
tuple attributes, array elements and statement sequences uniformly as
bindings.

\item \p{Signatures} are ordered sequences of identifier/type or
identifier/supertype pairs. Again, identifiers can be omitted.
Signatures appear, for example, in functions, tuple types and module
interfaces. 

\end{itemize}

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

\subsection{On the Implementation of Extensible Grammars} 

\begin{figure}[t]
\epsfpic{EGram.epsf}%{}
{\epsfxsize \hsize}
\caption{\label{Egram} Interfaces of the extensible grammar package}
\end{figure}

\noindent Extensible grammars are realised by a fully self-contained
polymorphic Tycoon library implementing an extensible parser and grammar
checker which are bound statically as a front-end to the TL type checker
and code generator (see figure~\ref{Egram}). Without recompilation, the
very same extensible grammar package can be used for other programming
languages, as demonstrated by the TooL language \cite{GaMa95a}.

The grammar checker and parser generator as well as the constructors for
TL abstract syntax trees are defined in TL. Input phrases accepted by
the extensible parser can be either new syntax definitions which are
passed on to the grammar checker and parser generator to be available
for future input parsing or they can be TL abstract syntax trees that
are processed further by the TL type checker and code generator.

The extensible parser is initialized with the syntax of the target
language $L_0$ at hand (TL or TooL). Given an extensible parser for
programs in a language $L_n$, a new extensible parser for a language
$L_{n+1}$ can be defined by specifying the context-free grammar and the
rewrite rules (productions) that map $L_{n+1}$ terms into $L_n$ terms.
This method is incremental since $L_n$ is translated into $L_{n-1}$
until the base target language is reached and the final (TL or TooL)
abstract syntax tree is generated.

Static checks at grammar-definition time guarantee the sort-correctness
of grammars (only legal syntax trees are generated during parsing), the
termination of parsing for arbitrary input programs, and the absence of
syntactic ambiguities. Formal proofs for these properties are given in
\cite{CMA94a}. This high degree of static correctness should be
contrasted with other program transformation or reflective compilation
techniques.

Extensible grammars can be implemented efficiently. In our persistent
system environment, the first extensible TL parser is half as fast as
the old, hand-coded standard LL(1) top-down parser. We expect the next
re-implementaion of the extensible parser to outperform a handcoded
parser using a simple optimization of the attribute evaluation strategy.
Furthermore, the space required for the code and data of both parsers is
of similar size.

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

\section{Supporting Data Modelling with Extensible Grammars} \label{general}

\begin{figure}[t]
\epsfpic{TycoonLayers.epsf}%{}
{\epsfxsize 210pt}
\caption{\label{TycLay} A layered architecture for data model
implementation in Tycoon}
\end{figure}

\noindent Figure~\ref{TycLay} sketches the generic architecture of a
data model implementation in TL: Users interact with the system through
data-model-specific tools like schema and data browsers. Data and schema
declarations, and interactive and embedded queries are written in a
data-model-specific syntax. This syntax is specified once per data model
by a set of TL syntax modules (bulk syntax, query syntax, etc.). Each
syntactic construct is mapped to functions and types exported from
Tycoon interfaces. This mapping captures the static and dynamic
semantics of the data model.  The data-model-specific TL interfaces
in turn are based either on the existing set of TL libraries or directly
on the built-in TL constructs.

The top-down methodology to implement a given data model \p{M} in TL can
be summarized as follows:

\begin{enumerate}
\item Identify the semantic concepts of \p{M}  (e.g., table, row,
attribute, domain, query, view).

\item Map each concept to a newly defined or pre-existing abstract TL
type or type constructor. At this stage, the implementation of the
abstract types is irrelevant.  \label{step2}

\item Identify the abstract operations available on each of the
semantic objects (e.g., create a table, insert a row, execute a query,
define a view, union two tables, join two tables, ...).

\item Map these abstract operations to typed TL function signatures that
refer to the types identified in step~\ref{step2}. In order to correctly
capture the static semantic constraints on the abstract operations of
\p{M} by TL type constraints, elaborate TL type concepts (parametric
polymorphism, subtype polymorphism, ad-hoc reflective polymorphism based
on dynamic type inspection) can be used. The abstract types and their
operations are preferably clustered into TL interfaces named after
their semantic concept. \label{step4}

\item In parallel, develop a TL grammar definition 
(incrementally) that maps each syntactic construct of \p{M}
(e.g. attribute type definition, table type definition, query, subquery,
projection list, \ldots) into nested TL expressions that utilize the
types, type operators and functions defined in the previous step. An
important task of the grammar is to correctly capture \p{M}'s scoping
rules.

The name of a grammar production should be chosen based on the data
model concept it represents. As a positive side-effect of this naming
convention, later syntax error messages generated for non-well-formed
data models will utilize this name and convey additional information to
the data modeller (e.g., \p{error in tableDefinition}).

The initial grammar should de-emphasize syntactic details of \p{M} (like
precedence rules or alternative notations). Such detail can be added
easily at a later stage. The sorts for the grammar productions
(\p{Value}, \p{Type}, ...) follow immediately from the TL mapping chosen.

\item Verify the consistency of the model developed so far by compiling
the grammar and by translating some examples using empty stub
implementations for the TL functions defined in step~\ref{step4}. That
is, the static semantics of \p{M} (scoping and typing rules) can be
checked in isolation.

\item Choose appropriate implementations for the abstract data types and
polymorphic functions introduced in steps~\ref{step2} and \ref{step4} to
implement the dynamic semantics of \p{M} by TL program code. The
implementation typically makes heavy use of polymorphic data structures
(lists, sets, bags, dictionaries, \ldots) and iteration abstractions
(select, map, join, \ldots) provided by the TL libraries.

\item Provide tools for schema browsing,  data visualization, code
management, data import and export, etc. Again, these tools can
frequently be derived schematically from the existing, strongly-typed TL
tools.
\end{enumerate}
%
This top-down approach can also be complemented by a bottom-up
composition of existing modules and grammar extensions to increase code
reuse and to speed up the data model mapping process.

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

\section{Uniform Iteration Abstraction over Bulk Types}
\label{Sec:Iter}

The Tycoon libraries implement multiple bulk data types (sets, lists,
relations, etc.). Each bulk data type is represented by a module that
exports an abstract type operator and a set of polymorphic functions
that work on bulk values of that type.  Additional bulk types can be
added to the Tycoon library as needed (add-on vs.\ built-in approach
\cite{MaSc91b}; synopsis in Chapter 1.4.2). Some of these bulk types (like SQL tables) are
implemented by gateways to external servers. Each bulk type has to
satisfy a \e{bulk type algebra} (similar to \cite{BeTa94}) to create and
inspect bulk type instances in a uniform manner.

Uniform declarative access to multiple bulk data types (selection,
projection, mapping, join, aggregate functions, \ldots) is provided by
the concept of abstract iterators implemented by a separate Tycoon
library module \p{iter}. An iterator over a homogeneous collection of
values of type \p{E} has type \p{iter.T(E)}. It can be inspected and
manipulated by a large number of iteration abstractions such as
\p{iter.select}, \p{iter.flatten} and \p{iter.map} exported from the module \p{iter}.

Set-oriented query access to bulk data values is achieved in TL as
follows. First, the bulk data is (conceptually) transformed into the
common iterator type \p{iter.T}. Then, iterator functions are applied to
this iterator which can also combine an iterator with other iterators
derived from other bulk data collections. The result can then be
converted explicitly into a specific bulk data structure (set, list,
bag, \ldots).

For example, the following iterator expression joins an iteration over
\p{Person} values (tuples with a \p{name} and \p{cityZip}
attribute) with an iteration over \p{City} values (tuples with a \p{zip}
and \p{name} attribute) based on their \p{cityZip} attributes returning
an iteration \p{residences} over person name and city name pairs:
\begin{xple}
  \k{let} residences = iter.flatten(iter.map(persons
     \k{fun}(p :Person) iter.get(
           \k{fun}(c :City) \k{tuple} p.name c.name \k{end}
           cities
           \k{fun}(c :City) p.cityZip == c.zip)))
\end{xple}
The function \p{iter.flatten} produces a single iteration by
concatenating an iteration of iterations. The function \p{iter.map}
applies its function argument to each element of the iteration supplied
as its first argument and returns the results as a new iteration. The
function \p{iter.get} provides combined selection and projection on an
iteration. The first parameter is a projection function applied to each element
(\p{select}) of the iteration supplied as the second parameter
(\p{from}) restricted by the predicate of the third parameter
(\p{where}). The infix function ''=='' is a polymorphic test on object
identity.

Clearly, it is desirable to support a more readable syntax for these
declarative iterator queries. In the following, we describe how to
define a SQL-style \k{select from where} syntax for the generalized
Tycoon iteration abstractions. Other syntactic forms like \e{bulk
comprehensions} \cite{Trind91} can be defined in a similar fashion. The
above query can then be written more succinctly as:
\begin{xple}
  \k{let} residences= \k{select} p.name c.name
                     \k{from} persons p:Person, cities c:City
                     \k{where} p.cityZip == c.zip
\end{xple}
Based on the functions provided by the Tycoon
\p{iter} module sketched above, the following small grammar extension
suffices to add this SQL syntax to iterator expressions:
\begin{xple}
  \k{grammar}
     value:Value \k{$\mid==$}
          ''select'' b=bindings ''from''  \k{$=>$} range(b)
     range(b:Bnds):Value ===
          v=value i=ide '':'' t=type  \k{$=>$} rangeOrPredicate(b v i t)
     rangeOrPredicate(b:Bnds v:Value i:Binder t:Type):Value ===
          '','' r=range(b)   \k{$=>$}
                   value\k{$<<\mid$} iter.flatten(iter.map(v \k{fun}(i :t) r)) \k{$\mid>>$}
     \k{$\mid$}     ''where'' p=value  \k{$=>$}
                   value\k{$<<\mid$} iter.get(\k{fun}(i :t) \k{tuple} b \k{end}  v  \k{fun}(i :t) p) \k{$\mid>>$}
  \k{end}
\end{xple}
The expanded \p{value} production parses the target list (a list of
bindings following the \k{select} keyword) and passes these bindings as 
parameters to the recursively defined productions
\p{range} and \p{rangeOrPredicate}. A \p{range} specification defines an
iterator \p{v}, a range variable \p{i} with local scope, and a type
\p{t}. This information is again passed as a parameter to the production
\p{rangeOrPredicate}. If there is just a single range iteration, the
second alternative of the production \p{rangeOrPredicate} (starting with
the keyword \k{where}) matches and a call to \p{iter.get} is
generated. The first argument of this function is generated based on the
structure of the target list \p{b}, the name of the range variable \p{i},
and the iteration element type \p{t}. The second argument is the range
\p{v} and the third argument is the selection predicate \p{p}, again in
the scope of the user-defined range variable \p{i}.

For each additional range iteration, the first alternative of the
production \p{rangeOrPredicate} matches, and an enclosing
\p{iter.flatten} call is generated which accumulates the results of
nested iterations defined by a recursive invocation of \p{range}.

The reader is encouraged to verify that this syntax definition does in fact capture the scoping and typing constraints of the usual \k{select from
where} syntax.

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

\section{Tycoon/Fibonacci Add-On Experiment}\label{Sec:Fibo}

The goal of the Tycoon/Fibonacci add-on experiment is the evaluation of
the Tycoon system as an implementation platform for
advanced data models. The experiment aims at a comparison of
the effort required for the implementation of (a significant subset of)
the Fibonacci language \cite{ABGO93,AGO94} (see Chapter 1.1.2) using extensible TL grammars
and Tycoon's persistent system infrastructure with the effort required
to implement Fibonacci from scratch using Modula-3 at Pisa University
\cite{ABDGOR94}.

The Fibonacci TL implementation re-used Tycoon's persistent stores, code
generator, interactive top level, module manager, incremental linker,
and its gateways to commercial systems without change by a rather
straightforward mapping of Fibonacci data and code objects onto
corresponding TL persistent language objects. This fact nicely
demonstrates that one of Tycoon's system design goals, the
full separation of data storage, data manipulation and data presentation
aspects from data modelling features has been achieved.

Another goal of the experiment is to fully capture Fibonacci's strong
static type system (including objects with multiple roles
\cite{ABGO93b}) by a \e{statically typed} mapping of data and code
objects. This way, the full functionality of the Fibonacci type checker
is emulated by the existing Tycoon TL type checker. In the remainder of
this section we give some insight into this translation scheme at the
value and type level. The development of this scheme revealed
limitations of the existing TL language constructs available for the
manipulation of signature lists and binding lists. The current TL
primitives \k{Repeat} and \k{open} \cite{MaSc92a} (see Chapter 1.1.1) are not
flexible enough to emulate the specific multiple inheritance conflict
resolution strategy of Fibonacci. This deficiency could be solved by
introducing a rather small (but ad-hoc) TL type checker extension
matching the specific Fibonacci inheritance semantics. This
extension would require approximately one week's work for a
programmer who is familiar with the non-trivial TL type checker
implementation. The Tycoon/Fibonacci experiment required a total of six
person months by a scientist visiting our group who had no
previous programming experience in persistent languages.

\subsection{Module Structure and Overview}

\begin{figure}[t]
\epsfpic{FibonacciLayers.epsf}{\epsfxsize 210pt}
\caption{\label{FibLay} Implementing the Fibonacci data model in Tycoon}
\end{figure}

\noindent Figure~\ref{FibLay} gives an overview of the implementation of the
Fibonacci data model which was developed following the approach sketched
in section~\ref{general} and involves five Tycoon interface modules and
four associated grammar modules. The interfaces are implemented by
modules written in statically-typed Tycoon code. A small set of record
operations is implemented in type-unsafe C and is only available within
type-safe programming patterns specified by the syntax-directed
Fibonacci to TL mapping. C code could be avoided completely by using
dynamically-typed TL code. However, this would lead to ``unnecessary''
additional run-time type tests (which never fail).

\begin{center}
\begin{tabular}{|l|l|}
\hline
\k{Fibonacci Source Code}        & \k{TL Equivalent}
\\ \hline \hline
\k{Let} Address =                & \k{Let} Address = fiboCore.T(\\ 
\ \ [name:\k{String}             & \ \  \k{Tuple} name:fiboCore.StringT \\
\ \ \ country:\k{String}]        & \ \ \ country:fiboCore.StringT \k{end})\\
\hline
\k{let} address :Address =       & \k{let} address :Address = fiboCore.new(\\
\ \  [''Bill'' unknown]          & \ \ \k{tuple} fiboCore.new(''Bill'')\\ 
\                                & \ \ \ fiboCore.noneT.unknown \k{end})\\
\hline
\k{Let} Object =                 & \k{let} Object = \k{tuple} \\
\ \ \k{NewObject}                & \ \k{Let} T = \k{Record} \_object:fibo.Object \k{end}\\
                                 & \ \ \k{let} to(...):\k{Ok} = \ldots\\
                                 & \ \ \k{let} copy(..):T = \ldots\\
                                 & \ \ \k{let} lateImplementationSetting(...):\k{Ok} = \ldots\\
                                 & \ \ \k{let} roleExistenceTest(...):\k{Ok} = \ldots\\
                                 & \k{end} \\
\hline
\k{Let} Person =                 & \k{let} Person = \k{tuple} \\
\ \ \k{IsA} Object \k{With}      & \ \ \k{Let} T = \k{Record}\\
\ \  name :\k{String}            & \ \ \ \ \k{Repeat} Object.T\\
\k{End}                          & \ \ \ \ name:fibo.Dispatcher(fiboCore.StringT)\\
                                 & \ \ \k{end} \\
                                 & \ \ \k{let} propagateToSub(...):\k{Ok} = ...\\
                                 & \ \ \ldots\\
                                 & \k{end}\\
\hline
\k{let} john = \k{role} Person  & \k{let} john = \k{begin} \\
\ \ \k{methods}                 & \ \ \k{let} \k{rec} \_object:fibo.Object = \k{record} \\
\ \ \ \ name = ''John Major''   & \ \ \ \ \k{let} \_oid = fibo.newOid() \k{let} Person = me \\
\k{end}                         & \ \ \k{end} \\
                                & \ \ \k{and} me :Person = \k{record} \\
                                & \ \ \ \ \k{let} \_object = \_object \\
                                & \ \ \ \ \k{let} name = fibo.newDispatcher(''name'' \\
                                & \ \ \ \ \ me \k{fun}()fiboCore.new(''John Major''))\\
                                & \ \ \k{end} \\
                                & \k{end} \\
\hline
john.name                       & john.name.late()\\
\hline
john!name                       & john.name.strict()\\
\hline
\end{tabular}
\end{center}

\begin{center}
{\bf Table 5.1. Translation scheme from Fibonacci to TL}
\end{center}

\noindent Table~5.1 gives some examples of the systematic
translation from Fibonacci to TL.  Some details of the translation are
described below. The implementation of Fibonacci class extents, sequences
and relationships (modules \p{FiboClass} and \p{FiboSeq}) is based on
the Tycoon bulk libraries and utilises syntax definitions
(\p{Class.syntax} and \p{Sequence.syntax}) similar to the ones described
in section~\ref{Sec:Iter} to map Fibonacci's query language to Tycoon
iterator expressions. Value-based integrity constraints on class extents
were not studied in the experiment but could be realised by a mapping to
an existing Tycoon add-on library (\p{dbenv} \cite{Nied92}) that
provides the required base services.

\subsection{Mapping of Concrete Types}

The interface \p{FiboCore} exports the Fibonacci base types and some
predefined values like booleans and functions on the base types
(comparisons, arithmetics, etc.). This interface relies on the services
of the interface \p{OptionalFibo} to ensure that the value space of each
Fibonacci base type and structured type also contains the special value
\k{unknown} (a generic null value). This value is handled explicitly by
the predefined functions, for example, by raising a run-time exception
\p{fiboCore.error} that can be caught by the programmer. The type
operator \p{fiboCore.T(A)} defines a representation for a Fibonacci type
\p{A} by a mapping onto a TL union type with a variant
\p{unknown} and a variant \p{known} with a value \p{val} of type \p{A}.
The polymorphic functions \p{new} and \p{value} construct or inspect
values of type \p{fiboCore.T(A)}, respectively.
\begin{xple}
  \k{interface} FiboCore \k{export}
    \k{Let} T(A $<$:\k{Ok}) = \k{Tuple case} unknown \k{case} known \k{with} val:A \k{end}
    error :\k{Exception}
    new(A $<$:\k{Ok} a:A) :T(A)
    value(A $<$:\k{Ok} optional:T(A)) :A  (* may raise "error" *)
    \k{Let} NoneT = \k{Tuple case} unknown \k{end}
    \k{Let} AnyT = T(\k{Ok})
    \k{Let} StringT = T(String)
    \ldots
  \k{end}
\end{xple}
By using the Tycoon type \p{NoneT} to represent the Fibonacci type
\k{None} that only contains the value \k{unknown} and by mapping the
type \k{Any} (the supertype of all Fibonacci types) to type \p{AnyT},
the subtype hierarchy of Fibonacci is fully mapped onto the TL subtype
hierarchy. In particular, this mapping preserves the subsumption
principle, i.e., a value of type \p{A} can be substituted freely in any
context where a value of a supertype of \p{A} is expected.

Using the interface \p{FiboCore}, the syntactic mapping of Fibonacci
base types and type expressions (functions, aggregates, unions) to Tycoon
type expressions as defined in the module \p{BaseTypes.syntax} is rather
straightforward: 
\begin{xple}
  \k{grammar}
    fiboType:Type ===
      x=simpleId =$>$ type$<<\mid$x$\mid>>$
    $\mid$ "Null" =$>$ type$<<\mid$fiboCore.NullT$\mid>>$
    $\mid$ "Any" =$>$ type$<<\mid$fiboCore.AnyT$\mid>>$
    $\mid$ "String" =$>$ type$<<\mid$fiboCore.StringT$\mid>>$
    $\mid$ \ldots
    $\mid$ "Fun" "(" s=fiboSigs ")" ":" t=fiboType =$>$ type$<<\mid$fiboCore.T(\k{Fun}(s):t)$\mid>>$
    $\mid$ "[" s=fiboSigs "]" =$>$ type$<<\mid$fiboCore.T(\k{Tuple} s \k{end})$\mid>>$
    $\mid$ "Choice" c=fiboCases "End" =$>$ type$<<\mid$fiboCore.T(\k{Tuple} c \k{end})$\mid>>$
  \k{end}
\end{xple}
The first two rows of table~5.1 give an example of the
translation of a Fibonacci type and a matching value expression into TL
code.

\subsection{Mapping of Object and Role Types}

A key feature of Fibonacci is the support for statically-typed objects
with multiple roles \cite{ABGO93,ABGO93b}. Any interaction with a
Fibonacci object takes place by sending messages to a specific \e{role}
of an object. The set of roles possessed by an object can change over
time so that its behavior changes over time too. Here we do not want
to go into the intricate details of the Fibonacci object model but only
give a rough idea of its mapping to typed TL object representations.

A Fibonacci object is represented by a dynamically-constructed directed
acyclic graph of roles that share a common object representation. Each
role is a static Tycoon record that aggregates a set of named
\e{dispatchers}, one for each message understood by a role. A Fibonacci
role type is described by a Tycoon record type (a set of message
signatures) and enables the static type checking of message send
operations. A message dispatcher for a Fibonacci message (or attribute)
of type \p{A} is a Tycoon tuple of type \p{fibo.Dispatcher(A)}:
\begin{xple}
  \k{Let} Dispatcher(A$<:$\k{Ok}) = \k{Tuple}
     methodName :String
     self : \k{Record end} 
     strict():A
     \k{var} late():A
  \k{end}
\end{xple}
The two functional components \p{strict} and \p{late} of a dispatcher
realize the two forms of message dispatching supported by Fibonacci. A
late binding as in \p{john.name} leads to the execution of the most
specialized implementation of the method \p{name} (which depends on the
run-time history of role acquisitions for the object \p{john}).  A
strict binding as in \p{john!name} executes the method specified
statically for the current role. A dispatcher is created by a call to
\p{fibo.newDispatcher} which provides an initial method implementation
for \p{strict} and \p{late}. The function \p{late} is tagged as mutable
with the \k{var} keyword since it is overridden dynamically whenever a
matching dispatcher is created in a subrole.  The dispatcher attributes
\p{methodName} and \p{self} are utilised by the Tycoon library code that
has to work uniformly on dispatchers of arbitrary roles.

The last two lines in table~5.1 show how the two forms of
Fibonacci message send operations are translated into TL
function calls. Once a systematic encoding of objects, roles and
methods by a graph of linked TL records and function closures has been
found, the translation of role type and role value expressions can be
carried out in a type-safe way as indicated by examples in table~5.1.

An interesting detail is the fact that a Fibonacci role \e{type}
\p{Person} is mapped to a Tycoon \e{value} \p{Person} that aggregates a
type specification \p{Person.T} and a set of functions to work on
instances of that type (\p{Person.copy, Person.roleExistenceTest,
\ldots}).  The aggregation of types and values into a
first-class language object is a good example of the power available to
data model implementors through Tycoon's higher-order type system.

The following fragments of the grammar definitions in the  module
\p{Object.syntax} (see figure~\ref{FibLay}) show that the mechanism of
extensible grammars is sufficiently expressive to carry out the mappings
indicated in table~5.1 and that these mappings can be
written in a rather readable way. 
\begin{xple}
  \k{grammar}
     fiboValue:Value \k{===}
          v=fiboSimpleValue  \k{=$>$} optFiboValueApp(v)
     optFiboValueApp(v:Value):Value \k{===}
          "!" method=ide  \k{=$>$} value\k{$<<\mid$}v.method.strict()\k{$\mid>>$}
     \k{$\mid$}    "." method=ide  \k{=$>$} value\k{$<<\mid$}v.method.late()\k{$\mid>>$}
     \k{$\mid$}    (* no suffix *) \k{=$>$} v
  \k{end}
\end{xple}
\pagebreak
\begin{xple}
  \k{grammar}
     fiboObjectValue:Value \k{===}
          ''role'' roleName=ide ''methods'' mbnds=fiboObjectMethodBnds ''end'' 
          \k{=$>$} value\k{$<<\mid$} \k{begin}
                       \k{let rec} \_object :fibo.Object = \k{record}
                           \k{let} \_oid = fibo.newOid()
                           \k{let} roleName = me
                         \k{end}
                       \k{and} me :roleName.T = \k{record}
                           \k{let} \_object = \_object
                           mbnds
                       \k{end}
                       me
                     \k{end} \k{$\mid>>$}
     \k{$\mid$} ...
  \k{end}
\end{xple}
Note that this rewriting captures the Fibonacci scoping rules, for
example, the identifier \p{me} is bound to the ``current'' object in the
scope of the method bindings \p{mbnds} by virtue of a recursive object
binding in Tycoon. Similarly, the names of record attributes that
should not be visible to Fibonacci programmers are made inaccessible
by prefixing them with an underscore that is disallowed in the source
syntax. 

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

\section{Related Work and Concluding Remarks}

The work described in this paper can be seen as a contribution towards
the ``type alchemist's dream'' \cite{AtBu86}, to express multiple data
models uniformly in a sufficiently expressive type system.

The rapid implementation of a data model in the typed and persistent
Tycoon framework has the following advantages compared with a
system prototype implemented from scratch:
\begin{itemize}
\item The constructed system inherits most of Tycoon's system
functionality  (persistence management, garbage collection, code
generation, modular compilation etc.);
\item No compiler implementation know-how is needed to implement type checkers for
polymorphic (higher-order) data models;
\item The methodology described in section~\ref{general} supports early
experimentation with newly developed data models.
\end{itemize}
%
Compared with source-to-source code generators and preprocessor-based
systems, extensible grammars have the following advantages:
\begin{itemize}
\item Extensible grammars are fully integrated in the Tycoon compiler
(intermediate source files are avoided, error messages refer to the
original source code position, code management is simplified);
\item Extensible grammars are easy to read and modify;
\item Extensible grammars provide mechanisms to avoid name clashes and
to invent fresh identifiers as needed.
\end{itemize}
%
Extensible grammars are best suited for \e{context-independent} local
rewriting techniques. Some data model implementation techniques, e.g. the
one described in \cite{BMSW89}, make heavy use of global schema
information held in a central repository to drive the generation of
integrity-preserving transaction code. This is not possible with the
mechanism of extensible grammars since the rewrite process can only
depend on the input syntax and not on schema information available at
compile-time. However, as exemplified by the Tycoon/Fibonacci add-on
implementation, the handling of context dependencies can often be
delayed until run-time where it is possible to work on persistent
meta-data generated at compile-time. 

\begin{acknowledgement}
This research was supported by ESPRIT Basic Research, Project FIDE,
\#6309 and by a grant from the German Israeli Foundation for Research
and Development (\e{bulk data classification}, I-183 060).  Davide
Berveglieri (Politecnico di Milano) contributed significantly to the
Tycoon/Fibonacci experiment described in section~\ref{Sec:Fibo}. He was
supported by the ESPRIT Basic Research Network of Excellence IDOMENEUS
(No. \#6606) and the ESPRIT Basic Research Project FIDE \#6309.
\end{acknowledgement}

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

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

\end{document}
