%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                    %
% Universitaet Hamburg                                               %
% Fachbereich Informatik                                             %
% Arbeitsbereich DBIS                                                %
% File:    ti.tex                                                    %
% Titel:   The Tycoon Language TL: An Introduction                   %
% Author:  Florian Matthes, Sven Muessig                             %
% Needs:   tiIndex.tex, tiAppendix.tex
% Note:    tiIndex.tex is generated with a Tycoon program from ti.idx!
%      
%                                                                    %
% Date:    17-AUG-1994                                               %
%                                                                    %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentstyle[11pt,a4,xple_sl]{article}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\setcounter{tocdepth}{2}

\newcommand{\e}[1]{{\em #1\/}}
\newcommand{\p}[1]{{\sl{}#1}}
\newcommand{\k}[1]{{\bf{}#1}}
\newcommand{\dq}{{"}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\T}{{\it Tycoon}}
\newcommand{\Tl}{{\sc Tl}}
\newcommand{\Q}{Quest}
\newcommand{\PQ}{P-Quest}
\newcommand{\fsub}{F$_{\leq}$}

\newcommand{\r}{$\Rightarrow$}
\newcommand{\s}[1]{{\sl #1\/}}
\newcommand{\bold}[1]{{\bf #1}}
\newcommand{\engl}[1]{{\em #1\/}}

\newcommand{\bslop}{\begin{sloppypar}}
\newcommand{\eslop}{\end{sloppypar}}

%\newcommand{\synquot}[1]{\verb$"${\rm{#1}}\verb$"$}

\newcommand{\synopt}[1]{$[$ #1 $]$}
\newcommand{\synbrack}[1]{$($ #1 $)$}
\newcommand{\synrep}[1]{$\{$ #1 $\}$}
%\newcommand{\synquot}[1]{\verb$"${\rm{#1}}\verb$"$}
\newcommand{\synquot}[1]{{\tt \dq}{\rm{#1}}{\tt \dq}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{Persistent Polymorphic Programming in Tycoon:\\
  An Introduction\thanks{This research has been supported in part by the
  Esprit-III Basic Research Project FIDE-2 and by a grant from the
  German-Israel Foundation for Scientific Research and Development.}}

\author{Florian Matthes \and Sven M\"u{\ss}ig \and J.W.~Schmidt \\}

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


\makeindex

\begin{document}
\maketitle

\begin{abstract}

This text provides an introduction to Tycoon\footnote{Tycoon: Typed 
Communicating Objects in Open Environments.}, an open persistent 
polymorphic programming environment.  The Tycoon language TL is based on 
expressive and orthogonal naming, typing and binding concepts as they are 
required, for example, in advanced data-intensive applications.  The 
characteristic language mechanisms of TL are first-class functions and 
modules, parametric and subtype polymorphism extended to a fully 
higher-order type system.  Tycoon programs are statically typed but may 
include explicit dynamic type variables which can be inspected at run-time.
\thispagestyle{empty}
\end{abstract}

\vfill

\begin{center}
{\Large \sc Acknowledgements}
\end{center}

The Tycoon system described in this paper was developed by Andreas
Gawecki, Bernd Mathiske, Florian Matthes and Rainer M\"uller. Section 12
of this text was written by Bernd Mathiske who also developed Tycoon's
external language bindings. The authors would also like to thank Claudia
Nieder\'ee, Gerald Schr\"oder, Petra M\"unnix, Andreas Rudloff and Dominic
Juh\'asz for their careful reviewing of this paper and numerous hints
which helped to improve the presentation of the material.


\newpage

\pagenumbering{Roman}
\setcounter{page}{1}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\tableofcontents

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pagenumbering{arabic}
\setcounter{page}{1}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction and Motivation}
\label{Abs. Einfuehrung}

The Tycoon\footnote{Tycoon: Typed Communicating Objects in Open
Environments.} system is an open persistent polymorphic programming
environment based on higher-order language concepts.  It is designed as
a robust linguistic and architectural framework for the definition,
integration and interoperation of generic services represented as
polymorphically-typed libraries.

The Tycoon language \Tl\footnote{\Tl: Tycoon Language.} described in
this paper is used for the following two activities in database
application programming (see also \cite{MaSc93b}):

\begin{description}

\item[Strongly typed, high-level application programming:] \Tl\ is used
by application programmers to implement the full functionality of
data-intensive applications which require a tight and controlled
interaction between objects on the screen, objects in main memory,
objects on disk, and objects on the wire. For example, a value from a
screen form may be passed as a parameter to a transaction, be stored in
a database and finally be transmitted to a remote log server. \Tl\
supports such programming tasks by providing uniform and generalized
naming, typing and binding concepts that abstract from the specifics of
the underlying object servers like GUI toolkits, programming languages,
database systems and RPC services. In particular, Tycoon's type system
statically detects any attempt to apply an inappropriate operation from
one server to an object from another server. This should be seen in
contrast to the current practice in data-intensive applications where
there is virtually no inter-server consistency checking due to the lack
of an integrated typed system model. 

\item[Generic server integration:] Different from fourth-generation
languages, high-level application programming in the Tycoon system is
not restricted to {\em built-in} object types like tables, forms and
reports. By virtue of Tycoon's polymorphic (higher-order) type system it
is possible to also integrate pre-existing, independently developed {\em
generic} servers (like object-oriented databases, C++ GUI libraries or
RPC communication services) as strongly typed parametric libraries into
the Tycoon programming environment. Therefore, systems developed in \Tl\
fit smoothly into open system architectures. 

\end{description}
The idea of an open, library-based approach to system construction is
currently being pursued in several system frameworks that are based on
C++ or distributed object models of similar expressiveness.  Tycoon aims
at a higher system development productivity in a language framework with
the following characteristics: 

\begin{description}
\item[Improved language orthogonality:] All language entities in \Tl\
(like values, functions, modules and types) have first class status. For
example, it is possible to write a \Tl\ function that receives a type as
its argument and returns a module which aggregates a set of dynamically
constructed functions for a fresh abstract data type. Such {\em
higher-order} language concepts are particularly helpful to factor-out
repetitive programming tasks from individual applications into shared,
reusable library code. 

\item[Increased type system expressiveness:] \Tl\ combines subtype and
parametric polymorphism. Furthermore, both forms of polymorphism are
generalized to (higher-order) type operators supporting the type-safe
definition of highly polymorphic system libraries. 

\item[Orthogonal persistence abstraction:] \Tl\ programmers don't have to 
distinguish between local volatile data and shared global and persistent 
data. As a consequence, programmers can fully abstract from store 
properties (size of main memory, garbage collection, transfer between 
primary and secondary store, data format conversion between nodes in 
heterogeneous networks, etc.). 

\item[Reflective programming support:] Some system tasks in
data-intensive applications (e.g., query optimization, transaction
scheduling, GUI generation) are based on run-time reflective programming
techniques. Run-time linguistic reflection denotes the ability of a
system to inspect parts of the system (e.g. query expressions,
transaction instruction sequences, type structures) at run-time and to
dynamically extend or modify the system based on the outcome of this
inspection \cite{S*92}. For example, the \Tl\ programming environment
exports a (strongly-typed) function \p{reflect.optimize} that takes a
\Tl\ function value, re-invokes the \Tl\ compiler back-end on this
function, and returns an optimized version of the function. Contrary to
static code optimizations which are based on a limited static context (a
single function or a single module), such dynamic code optimizations can
exploit run-time information available for the dynamic context of a 
function (e.g. external function implementations or values of abstract 
data types).
\end{description} 

A more detailed discussion of the rationale behind Tycoon is given in
\cite{Matt93} and \cite{MaSc93b}.

This text is organized as follows: Section 2 gives a quick overview of
the Tycoon language in comparison with other modern (persistent)
programming languages. The subsequent sections (Section 3--8) provide a
step-by-step introduction to Tycoon's language concepts in a functional
setting (values, types, bindings, signatures, predefined type and value
constructors, user-defined types and type operators, subtype and
parametric polymorphism). Section 9 explains how these concepts interact
with the imperative concepts of Tycoon, namely mutable variables,
destructive assignment, sequential execution and exception handling.
Section 10 and 11 discuss alternative approaches to the structuring of
large Tycoon software systems into interfaces, modules and libraries.
Section 12 and 13 present some important system-oriented aspects of
Tycoon like its transparent persistence management and bindings from and
to external C libraries. 

Appendix A and B are intended mainly for reference purposes and
summarize the syntax and the predefined identifiers of the
language. Readers interested in the formal definition of the \Tl\
semantics are referred to \cite{MaSc92a}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Language Classification}
\label{Abs. Einfluesse anderer Programmiersprachen}

This section is intended primarily for readers who are familiar with the
state of the art in programming language research and who are interested
in a rough \Tl\ language classification.

The programming language \Tl\ evolved from the experimental languages
\Q\footnote{\Q{}: \engl{Quantifiers and Subtypes}.}\index{Quest}
\cite{Card89,Card90} and \PQ\footnote{P-Quest is a \Q{}\ System extended
by an orthogonal persistence concept}\index{P-Quest}
\cite{Matt91a,Mue91,NMM92}. All semantic concepts of these languages are
supported in \Tl (in a slightly variated syntactic from). \Tl\
eliminates some ad-hoc restrictions of Quest's language orthogonality.
Furthermore, it introduces new language concepts such as subtyping
between type operators, recursive type operators, extensible record
values, and libraries as scopes for modules and interfaces.

The syntactic structure\index{syntactic structure} and the module
concept of \Tl\ are similar to those of the languages of the Modula
family (\mbox{Modula-2} \cite{MODISO}, Oberon
\cite{Wirt87a}, \mbox{Modula-2+} \cite{RLW85}, \mbox{Modula-3}
\cite{Nels91}, and Ada \cite{I*83}). Regarding its semantics, \Tl\ is
more closely related to the polymorphic functional languages of the ML
language family \cite{Card89,Card90,Maun91,FiHa88,Hudak89}. The semantic
concepts\index{semantic concept} of \Tl\ are derived from the language
\fsub\ \cite{CMMS91},  a widely accepted formal basis for the study of 
modern type systems.

Like C \cite{KeRi77} \Tl\ is intended for application
programming\index{application programming} and for system programming
tasks\index{system programming}. By virtue of its polymorphic type
system\index{polymorphic type system} \Tl\ can also be utilized as a
data modeling\index{data modeling} language. In this respect, \Tl\
resembles Lisp development systems \cite{B*88} and commercial
object-oriented languages like Smalltalk \cite{GoRo83}.  From integrated
database programming languages like \mbox{PS-Algol} \cite{ACC81a},
Napier88 \cite{DCBM89}, Amber \cite{Card86}, and \mbox{P-Quest},
mentioned before, \T\ inherits the orthogonality of elementary kernel
concepts for persistence abstraction, type-complete data structuring,
and iteration abstraction \cite{AtBu86,ScMa90a}.

Motivated by an analysis of the conceptual and technological
foundations of existing database languages \cite{MaSc91b,MaSc91}, the
\T\ system pursues the idea of a strictly reduced kernel language
supporting naming, binding and typing of predefined semantic objects
(variables, functions, type variables, type operators). On the other
hand, it is possible to extend the language kernel with external
semantic objects (integers, floating-point numbers, strings, arrays,
relations, views, files, windows etc.) and generic functions associated
with these objects in a completely type-safe way (\engl{add-on}
vs. \engl{built-in}) \cite{MaSc91}.

\Tl\ enables the programmer to use different modeling styles.
\e{Functional} and \e{imperative} programming\index{functional
programming}\index{imperative programming} are supported directly. Due
to the considerable linguistic neutrality several variants of the
\e{object-oriented} programming style are supported by \Tl. \e{Relational} 
and
\e{logic-based} programming \cite{Mink88} are not supported directly,
since unification-based evaluation models and declarative approaches
deviate strongly from functional and imperative structures.

The \T\ system offers an interactive programming
environment\index{interactive programming environment}. Such
environments are known from functional systems (ML, Lisp). This
distinguishes the \T\ system from conventional translation systems like,
for example, C, \mbox{Modula-2}, or Ada compilers. Due to the
interactive environment, ad-hoc \Tl\ database queries are possible in
addition to the use of \Tl\ as a database programming language. The
persistence concept enables the user to perform incremental system
developments spanning several sessions. At the same time, the library
concept of \Tl\ supports the controlled use of shared data and programs
by several users.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Lexical and Syntactical Rules}
\label{Abs. Lexikalische und syntaktische Regeln}

This section introduces the most important lexical and syntactical
rules\index{lexical rule}\index{syntactical rule} of \Tl\ for the 
construction of symbols, reserved identifiers, and
productions. A precise definition of the syntax of \Tl\ is given in 
appendix \ref{Sec. The Tycoon Grammar}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Symbols}
\label{Abs. Symbole}

The character set\index{character set} predefined on a given system is 
partitioned into the
disjoint classes of letters, digits, delimiters, printable special
symbols, and non-printable formatting characters. On the basis of this
classification a sequence of characters is divided into atomic symbols
(e.g., numbers and identifiers).

\Tl\ distinguishes \e{alphanumeric identifiers}\index{alphanumeric 
identifier} and \e{infix symbols}\index{infix symbol}.
Alphanumeric identifiers consist of a character followed by a sequence
of characters and digits whereas infix symbols are composed solely of
special symbols. A space\index{space} is only required between two 
alphanumeric
identifiers or two infix symbols that appear in direct succession.

  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Reserved Keywords}

Appendix \ref{Sec. Reserved Keywords} lists all reserved 
keywords\index{reserved keyword} and infix symbols of \Tl. These 
identifiers\index{identifier} must not be used as user-defined identifiers 
or infix symbols.

The reserved keywords are written in \k{bold face} in the programming
examples. This facilitates the distinction from the rest of the
symbols in the examples which are presented in \s{italics}.

Keywords associated with types start with a capital letter whereas all
other keywords begin with lower case characters. It is advisable to
adopt this rule as a convention\index{convention} for all other 
identifiers to improve
the readability\index{readability} of programs. A proposal for the layout 
and for further naming
conventions in \Tl\ programs is described in section \ref{Sec. Layout and 
Naming Conventions}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Comments}
\label{Abs. Kommentare}

In \Tl, comments\index{comment} are enclosed in \s{(*} and \s{*)}. 
Arbitrary nesting
of comments is possible. Comments may include arbitrary (printable and
non-printable) characters and can span several lines.

\begin{xple}
    (* This is a comment. *)
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Factoring of Expressions}
\label{Abs. Zerlegung von Ausdruecken}

Operators represented by infix symbols\index{infix symbol} are 
left-associative and of
equal precedence\index{operator precedence}. The parsing of type and value 
expressions containing infix symbols can be controlled by the use of curly
brackets\index{bracket}. Consequently, the following expressions are 
equivalent.

\begin{xple}
    3 -- 7 * 4
    \{3 -- 7\} * 4
    \{*(--(3 7) 4)\}
    int.mul(int.sub(3 7) 4)
    \r --16 :Int
\end{xple}

Infix symbols starting with a colon (e.g., \s{:=} and \s{:+}) have a
weaker precedence than the other infix symbols. These
operators are also left-associative. The bracketed expressions in the
following examples show the factoring of the corresponding expressions
without brackets.

\begin{xple}
    x := a + b
    x := \{a + b\}

    x := y := z
    \{x := y\} := z
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Coercion and Overloading}
\label{Abs. Typanpassung und Ueberladen}


Automatic coercions\index{coercion}, e.g., of integers to real numbers, 
are not
performed in \Tl. For example,  a type error is caused by the following 
expression.

\begin{xple}
    3.0 + 4
    \r Argument type mismatch: '\_builtin.Int' expected, 'Real' found
       [while checking function argument '$<$anonymous$>$']
\end{xple}

Neither symbolic nor alphanumeric identifiers may be 
overloaded\index{overloading}. For
this reason it is, for example, necessary to have different operators
(infix symbols) for the addition of integers and real numbers,
respectively (see appendix \ref{Sec. Predefined Identifiers} for details).

\begin{xple}
    2 + 7
    \r 9 :Int
    2.4 ++ 3.8
    \r 6.2 :Real
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Predefined Values and Functions}
\label{Abs. Vordefinierte Werte und Funktionen}

This section presents the basic semantic rules of \Tl.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Naming, Binding, and Typing}
\label{Abs. Benennung, Bindung und Typisierung}

Contrary to many traditional programming languages neither the base
types, nor their constants, nor the functions defined on them are 
predefined\index{predefined, ~ type}\index{base type}\index{predefined, ~ 
function}\index{predefined, ~ constant} in \Tl. The identifiers of the 
base types (e.g., \s{bool.T}), the constants of the base types (e.g., 
\s{bool.true} and \s{bool.false}),
and the functions defined on the base types can be imported explicitly from
modules of the standard \T\ library\index{standard library}. They obey the 
same  syntax, typing, and evaluation rules as user-defined types, values, 
and
functions. The rationale behind this approach is to give predefined and 
user-defined data types equal status in the 
language\index{typing}\index{evaluation}.

In order to avoid the notational disadvantages resulting from this
approach, the base types and many functions defined on the base types are
bound to symbolic identifiers and infix symbols, respectively, in an 
initial context that is defined when the system is started (see appendix 
\ref{Sec. Predefined Identifiers}). Thereby, the identifiers
appear to be built into the \T\ system environment without including
them into the language \Tl. In the following sections we, therefore, use 
the phrases `predefined base types' and
`predefined functions'.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Literals}
\label{Abs. Notation von Literalen}

The following enumeration lists examples\index{literal} of literal values 
of the base types \s{Int}, \s{Real}, \s{Char}, \s{String}, and \s{Bool}, 
respectively, from left to right
(compare appendix \ref{Sec. Symbols}).



\begin{xple}
    3  $\sim$3  3.0  'c'  ''string''  true  
\end{xple}
Note that \Tl\ avoids overloading. For this purpose negative integer 
numbers are marked by an prefix "$\sim$". The symbol "-" is reserved for 
integer subtraction. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{User-defined Values and Functions}
\label{Abs. Benutzerdefinierte Werte und Funktionen}

The \e{binding}\index{binding} of a user-defined 
\e{identifier}\index{identifier, user-defined ~} to a semantic object
and the repeated use of this identifier\index{identifier, use of ~} in 
\e{expressions}\index{expression} denoting the
bound object\index{bound object} is a basic concept in \Tl. Furthermore, a 
\e{signature}\index{signature}
assigns static type information\index{static type information} in the form 
of a \e{type expression}\index{type, ~ expression}
to an identifier. A signature restricts the set of possible semantic
objects that can be bound to an identifier. This makes it possible to 
control
the correct use of identifiers in expressions \cite{Matt93}.

In this section, the discussion of naming\index{naming} and scoping 
concepts  is
restricted to value bindings\index{binding, value ~}. The orthogonal 
extension of these concepts to type bindings, presented in section
\ref{Abs. Vordefinierte Wert- und Typkonstruktoren}, gives rise to
much of the expressive power of \Tl.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Static Bindings}
\label{Abs. Statische Bindungen}

Static\index{binding, static ~}\index{static binding} value bindings in 
\Tl\ are defined as follows\index{{\bf let}}\index{=}. 

\begin{xple}
    \k{let} n = 10
\end{xple}

After evaluating the term, the variable \s{n} is statically bound to
the value \s{10}. Every subsequent use of the identifier \s{n} in an
expression evaluates to the bound value.

\begin{xple}
    \k{let} x = 1 + \{2 * n\}
    \r 21 :Int
\end{xple}

Sequences of bindings are interpreted as \e{sequential} 
bindings\index{binding, sequential ~} in \Tl.

\begin{xple}
    \k{let} n = 10
    \k{let} x = 1 + \{2 * n\}
\end{xple}

The identifier \s{n} used in the second binding, therefore, refers to
the binding \s{n=10} established in the first line of the example above. 
In order to achieve a \e{simultaneous} binding\index{binding, simultaneous 
~}, the single bindings have to be connected by the keyword \k{and}.

\begin{xple}
    \k{let} a = 4 
    \k{let} a = 123 / 3 \k{and} b = a + 2 \k{and} c = true 
    $\backslash{}/$ !xfalse
\end{xple}

The variable \s{b} is bound to the value \s{6} in this expression.
The associated binding for an expression is determined by static 
\e{scoping rules}\index{scoping, ~ rule} in \Tl.

\begin{xple}
    \k{let} a = 1.0
    \k{begin} \k{let} a = 'x'  \k{let} b = a \k{end}
    \k{let} c = a
\end{xple}

The scope of the local identifiers \s{a} and \s{b} is restricted to
the block\index{block} delimited by the keywords \k{begin}\index{{\bf 
begin}} and \k{end} (see section
\ref{Abs. Sequenz}).  For this reason, the identifier \s{c} is bound to
the value \s{1.0} denoted by the global identifier\index{identifier, 
global ~} \s{a}, whereas the
local identifier\index{identifier, local ~} \s{b} is bound to the value 
\s{'x'} denoted by the
local identifier \s{a}.

The  bindings described above are determined by two basic scoping rules:
local declarations\index{declaration, local ~} have precedence over global 
declarations\index{declaration, global ~} and an
identifier in an expression always refers to the last binding
established for this identifier. 

A block in \Tl\ evaluates to the value of its last
binding. This is illustrated by the following
example.

\begin{xple}
    \k{begin} \k{let} a = 3  \k{let} b = true \k{end}
    \k{begin} \k{let} a = 3  true \k{end}
    \k{begin} 3  true \k{end}
    \k{begin} \k{end}
\end{xple}

Evaluation of the first three blocks yields the value \s{true} whereas
the result of evaluating the last block is the canonical value 
\k{ok}\index{{\bf ok}}
of type \k{Ok}\index{{\bf Ok}}. The second and third example contain 
so-called
\e{anonymous} bindings\index{binding,  anonymous ~}, i.e, bindings without 
an identifier.

Signatures\index{signature} assign static type information to bindings; 
they are ordered sequences of pairs each consisting of an identifier and a
type. The signatures of the bindings established by the previous
example are considered as an illustrative examples.

\begin{xple}
    a :Int  b :Bool
    a :Int  :Bool
    :Int  :Bool
    (* empty signature *)
\end{xple}

It is possible to declare the type\index{typing} of the bound value in a
binding explicitly. This declaration is optional. If the type 
specification is
omitted, it is inferred by the compiler from the expression given in
the binding\index{type, ~ inference}.

\begin{xple}
    \k{let} a :Int = 3
    \k{let} b :Bool = true
\end{xple}

Recursive bindings\index{binding, recursive ~} are used for the 
construction of \e{recursive} and
\e{cyclic} data structures. In \Tl,  pointer types\index{pointer type} are 
not
necessary for this purpose.  Recursive bindings are introduced by the
keyword \k{rec}\index{{\bf rec}}. Examples of recursive value bindings are 
given in
section \ref{Abs. Rekursive Funktionen} and section
\ref{Abs. Rekursive Datentypen} since they have to be used in combination 
with 
functions and recursive data types.
    
The problem of uninitialized identifiers\index{uninitialized identifier} 
is avoided completely in
\Tl, since identifiers can only be introduced in bindings and,
furthermore, recursive bindings are subject to static constraints that 
avoid access to uninitialized variables (\cite{Matt93}).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Dynamic Bindings}
\label{Abs. Dynamische Bindungen}

Dynamic bindings\index{dynamic binding}\index{binding, dynamic 
~}\index{function} are established by passing parameters\index{parameter 
passing} to
functions. In addition to \e{simple} and \e{recursive} functions known
from other programming languages, \Tl\ supports \e{higher-order}
functions and \e{polymorphic} functions. Simple and recursive
functions as well as higher-order functions are presented in the
following sections. The description of the polymorphic functions is
postponed until section \ref{Abs. Polymorphe Funktionen} for
didactical reasons.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Simple Functions}
\label{Abs. Einfache Funktionen}

Functions\index{function, simple ~} are introduced by the keyword 
\k{fun}\index{{\bf fun}}. In \Tl, functions can
be defined without binding them to an identifier. Such a \e{function
abstraction}\index{function, ~ abstraction} consists of an ordered, 
possibly empty list of formal
parameters\index{formal parameter} (signatures\index{signature}) and an 
expression defining the body of the function\index{function, ~ body}.

\begin{xple}
    \k{fun}(x :Int) x + 1
\end{xple}

The body of the function (here \s{x + 1}) can refer to 
identifiers of different scopes. The formal parameters introduced by the 
signature of the
function, the global identifiers present in the static scope of the
function, and the identifiers defined locally inside the function are all
visible in the function body\index{visibility}.

\begin{xple}
    \k{let} global = 1
    \k{fun}(x :Int) \k{begin} \k{let} local = 3  x + global -- local \k{end}
\end{xple}

A function\index{function, ~ binding}\index{binding, function ~} defined 
by a function abstraction can be bound to an identifier.

\begin{xple}
    \k{let} succ = \k{fun}(x :Int) x + 1
    \k{let} add = \k{fun}(x :Real  y :Real) x ++ y
    \k{let} succ2 = succ
\end{xple}

The first function (\s{succ}) expects a parameter of type \s{Int} and
returns a value of type \s{Int} as its result\index{function, ~ result}. 
It computes the successor
of an integer value passed as a parameter. The second function (\s{add})
adds two real numbers. It takes two parameters of type \s{Real} and
returns a value of type \s{Real}. The third identifier (\s{succ2}) is
bound to the function denoted by \s{succ}. The syntax of \Tl\ also
supports the following abbreviated notation.

\begin{xple}
    \k{let} succ(x :Int) = x + 1
    \k{let} add(x, y :Real) = x ++ y
\end{xple}

The type of the result can be made explicit improving the readability
of the program; if omitted it is inferred by the compiler\index{type, ~ 
inference}.

\begin{xple}
    \k{let} succ(x :Int) :Int = x + 1
    \k{let} add(x, y :Real) :Real = x ++ y
\end{xple}

Infix symbols can be chosen as names for functions that can be used as
binary infix operators\index{infix operator}. In the following example, 
the function
concatenating two strings (\s{string.concat}) is bound to the infix
symbol \s{$<>$}.

\begin{xple}
    \k{let} $<>$ = string.concat
\end{xple}

A function bound to an infix symbol can be applied in two different ways, 
either using the standard prefix notation or the infix 
notation\index{infix notation}\index{function, ~ application}:

\begin{xple}
    $<>$(''concat'' ''enation'')
    ''concat'' $<>$ ''enation''
\end{xple}

As shown in the next example, the use
of the infix symbol in the prefix notation can lead to unexpected results 
because of the factoring rules\index{factoring rule} for expressions.

\begin{xple}
    \k{begin}
       \k{let} a = 3
       $<>$(''concat'' ''enation'')
    \k{end}
\end{xple}

The above expression causes a syntax error\index{syntax error} since the 
compiler
recognizes an expression of the form \s{3 $<>$ (''concat''
''enation'')}. As usual, such problems can be avoided by the use of 
brackets\index{bracket} to control the parsing of expressions.

\begin{xple}
    \k{begin}
       \k{let} a = 3
       \{$<>$\}(''concat'' ''enation'')
    \k{end}
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Recursive Functions}
\label{Abs. Rekursive Funktionen}

\Tl\ supports the definition of recursive functions\index{recursive, ~ 
function}\index{function, recursive ~}. 
Recursive bindings\index{recursive, ~ binding} introduced by the keyword 
\k{rec}\index{{\bf rec}} are used for this
purpose. In contrast to normal bindings where the types of the bound 
values can be
inferred by the compiler they have to be specified explicitly for
recursive bindings. The well-known computation of the factorial function 
is an
example of a recursive function binding.

\begin{xple}
    \k{let} \k{rec} fac(n :Int) :Int = \k{if} n == 0 \k{then} 1 \k{else} n * fac(n -- 1) \k{end}
\end{xple}

As mentioned above, \Tl\ does not support the overloading of
operators. The operator for an equality test\index{equality test}, 
therefore, is the doubled
equality sign\index{equality sign} (\s{==}\index{==}) and not the simple 
equality sign (\s{=}\index{=}) used in \k{let}-bindings. The
polymorphic operator \s{==} tests simple values like
numbers and booleans for equality whereas it checks\index{identity test} 
structured values like tuples and arrays for identity, i.e., the equality 
of the values of the
tuple and array components is not tested.

Mutually recursive functions\index{mutually recursive functions} have to 
be defined in \e{parallel}\index{parallel definition}. In \Tl\
the bindings are connected by the keyword \k{and}\index{{\bf and}} for 
this purpose. A
parity test is given as an illustrative example.

\begin{xple}
    \k{let} \k{rec} even(x :Int) :Bool =
       \k{if} x == 0 \k{then} true \k{else} odd(x -- 1) \k{end}
    \k{and} odd(x :Int) :Bool =
       \k{if} x == 0 \k{then} false \k{else} even(x -- 1) \k{end}
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Function Types}
\label{Abs. Funktionstypen}

Since function types\index{function type}\index{type, function ~} are a 
prerequisite for the definition of
higher-order functions, they are introduced here in anticipation of
the discussion in section \ref{Abs. Vordefinierte Wert- und
Typkonstruktoren}. A function type defines the signature\index{function, ~ 
signature} of function values, i.e.\ the names and types of their formal 
parameters and the function result type\index{function, ~ result type}. 
Function types are introduced by the keyword \k{Fun}\index{{\bf Fun}}. The
types of the previously defined functions \s{succ}, \s{add}, and
\s{succ2} are given as examples.

\begin{xple}
    succ :\k{Fun}(x :Int) :Int
    add :\k{Fun}(x :Real  y :Real) :Real
    succ2 :\k{Fun}(x :Int) :Int
\end{xple}

The following abbreviating notation is also supported in \Tl.

\begin{xple}
    succ(x :Int) :Int
    add(x :Real  y :Real) :Real
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Higher-Order Functions}
\label{Abs. Funktionen hoeherer Ordnung}

Higher-order functions\index{higher-order function}\index{function, 
higher-order ~} are functions accepting functions as 
parameters\index{function, ~ as parameter} or returning functions as a 
result\index{function, ~ as result}.

The functions \s{twice} and \s{newInc} are examples of higher-order 
functions.

\begin{xple}
    \k{let} twice = \k{fun}(f :\k{Fun}(:Int) :Int  a :Int) :Int  f(f(a))
    \k{let} newInc = \k{fun}(x :Int) :\k{Fun}(:Int) :Int  \k{fun}(y :Int) :Int  x + y
\end{xple}

Again, the functions can be written down more concisely.

\begin{xple}
    \k{let} twice(f(:Int) :Int  a :Int) = f(f(a))
    \k{let} newInc(x :Int)(y :Int) = x + y
\end{xple}

The function \s{twice} receives two parameters. The first parameter is
a function mapping an integer value to an integer value, and
the second parameter is an integer. In the function body
(\s{f(f(a))}) of \s{twice}, the function passed as a parameter is applied
twice to the second parameter\index{function, ~ application}.

\begin{xple}
    twice(succ 3)
    \r 5 :Int
    twice(\k{fun}(x :Int) x * x  3)
    \r 81 :Int
\end{xple}

The function \s{newInc} is an example of a function with a function 
result. 
An application of \s{newInc} returns an anonymous function\index{function, 
anonymous ~} whose
application finally computes the addition.

\begin{xple}
    \k{let} add2 = newInc(2) 
    add2(5) 
    \r 7 :Int 
    newInc(3)(5) 
    \r 8 :Int
\end{xple}

As illustrated by the example, the application of the function can be
performed in a single step  or in two steps (currying\index{currying}).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Predefined Value and Type Constructors}
\label{Abs. Vordefinierte Wert- und Typkonstruktoren}

The predefined type constructors\index{type, ~ constructor} of \Tl, tuple, 
tuple with variants,
and record are presented in this section. Function types have already
been introduced in section \ref{Abs. Funktionstypen}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Tuple Types}
\label{Abs. Tupeltypen}

The tuple types\index{tuple type}\index{type, tuple ~}\index{tuple} of 
\Tl\ resemble records in
Pascal and in \mbox{Modula-2} as well as structures in C. A
tuple type is a labeled Cartesian product type\index{labeled Cartesian 
product}. The fields of a tuple\index{tuple, ~ field}
are described by an ordered, possibly empty, sequence of
signatures. The signatures may contain anonymous 
identifiers\index{anonymous identifier}\index{{\bf Tuple}}\index{{\bf 
Let}}.

\begin{xple}
    \k{Let} Person = \k{Tuple} name :String  age :Int \k{end}
    \k{Let} IntPair = \k{Tuple} :Int  :Int \k{end}
\end{xple}

Tuple values\index{tuple, ~ value} are ordered lists of 
bindings\index{{\bf tuple}}.


\begin{xple}
    \k{let} peter = \k{tuple} \k{let} name = ''Peter''  \k{let} age = 3 \k{end}
    \k{let} paul = \k{tuple} ''Paul'' 5 \k{end}
    \k{let} pair = \k{tuple} 12 21 \k{end}
\end{xple}

The scope\index{scoping} of the field names\index{field name} \s{name} and 
\s{age} is restricted to the block limited by the keywords \k{tuple} and 
\k{end}. Components of tuples are referenced by the dot notation\index{dot 
notation}\index{tuple, ~ field selection}.

\begin{xple}
    peter.age
    \r 3 :Int
\end{xple}

The rules for type compatibility\index{type, ~ compatibility} of \Tl\ make 
an $\alpha$-conversion\index{$\alpha$-conversion} between anonymous and 
non-anonymous field names\index{field name, non-anonymous ~}\index{field 
name, anonymous ~} possible. This conversion takes  the order of the 
fields defined by the binding into account.

\begin{xple}
    \k{let} p :Person = paul
    p.name
    \r ''Paul'' :String

    \k{let} namedPair :\k{Tuple} x, y :Int \k{end} = pair
    namedPair.x
    \r 12 :Int
\end{xple}

In \Tl\ it is possible to include functions\index{function, ~ as tuple 
field} as fields into tuples. Combining  this concept with recursive 
bindings makes it possible to capture the concept of methods\index{method} 
known from object-oriented programming\index{object-oriented 
programming}\index{programming, object-oriented ~}. Illustrative examples 
are presented in the sections \ref{Abs. Abstrakte Datentypen} and 
\ref{Abs. Modifizierbare Variablen} and in \cite{Matt93}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Variant Types}
\label{Abs. Variantentypen}

Tuples with variants\index{tuple, ~ with variant}\index{variant 
type}\index{type, variant ~}\index{tuple type, ~ with variants} resemble 
variant records in Pascal and in \mbox{Modula-2}. Like tuples, tuples with 
variants represent ordered sequences of signatures\index{{\bf 
Tuple}}\index{{\bf case}}\index{{\bf with}}. 


\begin{xple}
    \k{Let} Address =
       \k{Tuple}
          \k{case} national \k{with} street, city :String  zip :Int
          \k{case} international \k{with} street, city, state :String  zip :String
       \k{end}
\end{xple}

The two variants\index{variant} \s{national} and \s{international} in the 
example have a common prefix. This prefix can be extracted from the 
variants and placed in front of them. 

\begin{xple}
    \k{Let} Address1 =
       \k{Tuple}
          street, city :String
          \k{case} national \k{with} zip :Int
          \k{case} international \k{with} state :String  zip :String
       \k{end}
\end{xple}

If all signatures of the variants are empty, the tuple type with variants 
degenerates to an enumeration type\index{enumeration type}. 

\begin{xple}
    \k{Let} Day = \k{Tuple} \k{case} mon, tue, wed, thu, fri, sat, sun \k{end}
\end{xple}

The definition of a value of a tuple type with variants consists of the 
choice of a variant and the definition of the corresponding 
bindings\index{{\bf tuple}}\index{{\bf of}}. 


\begin{xple}
    \k{let} address1 =
       \k{tuple} \k{case} national \k{of} Address1 \k{with}
          \k{let} street = ''Johnsallee 21''
          \k{let} city = ''Hamburg''
          \k{let} zip = 21234
       \k{end}
\end{xple}

The keyword \k{with} in the definition of \s{address1} is optional. It is 
also possible to use anonymous bindings\index{anonymous binding} in tuples 
with variants. 

\begin{xple}
    \k{let} address2 =
       \k{tuple} \k{case} national \k{of} Address1
          ''Johnsallee 21''  ''Hamburg''  21234
       \k{end}
\end{xple}

A value of type \s{Day} can be defined as follows.

\begin{xple}
    \k{let} today = \k{tuple} \k{case} mon \k{of} Day \k{end}
\end{xple}

The projection on fields\index{variant, ~ field projection} in the prefix 
and on fields of the variants requires two distinct notations. Fields of 
the prefix can be accessed using the dot notation\index{dot notation} as 
in the case of simple tuple fields. 

\begin{xple}
    address1.street
    \r ''Johnsallee 21'' :String
\end{xple}

For the fields of the variants\index{case analysis} a complete\index{case 
analysis, complete ~} (\k{case} \k{of}\index{{\bf case of}}\index{{\bf 
of}}) or an incomplete case analysis\index{case analysis, incomplete ~} 
(\k{case}\index{{\bf case}}\index{{\bf when}}) is necessary.

\begin{xple}
    \k{case} \k{of} address1
       \k{when} national \k{with} n \k{then} fmt.int(n.zip)
       \k{when} international \k{with} i \k{then} i.zip
    \k{end}
\end{xple}

The use of the complete case analysis avoids unexpected runtime errors by 
ensuring that later extensions of a tuple type with new variants are 
accompanied by corresponding extensions of the case analysis. The 
incomplete case analysis has the following form. 

\begin{xple}
    \k{case} address1
       \k{when} national \k{with} n \k{then} fmt.int(n.zip)
    \k{end}
\end{xple}

Since an incomplete case analysis can lead to runtime errors\index{runtime 
error}, an \k{else}-branch can (and should) be specified in this 
situation\index{{\bf else}}. 


\begin{xple}
    \k{case} address1
       \k{when} national \k{with} n \k{then} fmt.int(n.zip)
       \k{else} ''not national''
    \k{end}
\end{xple}

Finally, two abbreviating notations for the simple test of variants and 
for the projection of variants are presented\index{?}\index{!}. 

\begin{xple}
    address1?national
    address1!national
\end{xple}

These two examples are equivalent to the following expressions.

\begin{xple}
    \k{case} address1
       \k{when} national \k{then} true \k{else} false
    \k{end}

    \k{case} address1
       \k{when} national \k{with} n 
       \k{then} n 
       \k{else} \k{raise} tupleProjectError \k{with} line column ''national'' 1 \k{end}
    \k{end}
\end{xple}

The variant projection opens the scope of the selected 
variant\index{scoping}. 

\begin{xple}
    address1!national.zip
    \r 21234 :Int
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Record Types}
\label{Abs. Recordtypen}

In contrast to tuple types, record types\index{record type}\index{type, 
record ~} represent \e{unordered,} possibly empty sets of 
\e{non-anonymous} signatures\index{non-anonymous signature} in \Tl. The 
names of all fields have to be different\index{{\bf Record}}. 

\begin{xple}
    \k{Let} Person = \k{Record} name :String  age :Int \k{end}
\end{xple}

Record values\index{record value} are unordered sets of non-anonymous 
bindings\index{non-anonymous binding}\index{{\bf record}}. 
\begin{xple}
    \k{let} peter = \k{record} \k{let} age = 3  \k{let} name = ''Peter'' \k{end}
\end{xple}

Like in tuple values, the scope\index{scoping} of the field names \s{name} 
and \s{age} is restricted to the block enclosed by \k{record} and \k{end}. 
The fields of a record are accessed using the dot notation\index{dot 
notation}. 

\begin{xple}
    peter.age
    \r 3 :Int
\end{xple}

Different from tuple values, record values\index{record value, extension 
of ~} can be extended dynamically by non-anonymous bindings without losing 
their identity. The keyword \k{extend}\index{{\bf extend}}\index{{\bf 
with}} is provided for this purpose. In the process of extending a record, 
the uniqueness of the field names has to be ensured. 


\begin{xple}
    \k{let} peterAsStudent = \k{extend} peter \k{with} \k{let} semester = 1 \k{end}
\end{xple}

The infix operator \s{==}\index{==} checks the identity of two values. 

\begin{xple}
    peter == peterAsStudent
    \r true :Bool
\end{xple}

The record value \s{peterAsStudent} fulfills  the following type 
specifications (see also sec. \ref{Abs. Subtypbeziehungen zwischen 
Recordtypen})

\begin{xple}
    \k{Record} name :String  age :Int  semester :Int \k{end}
    \k{Record} age :Int  name :String  semester :Int \k{end}
    \k{Record} semester :Int  name :String  age :Int \k{end}
    \k{Record} name :String  age :Int \k{end}
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Recursive Data Types}
\label{Abs. Rekursive Datentypen}


Recursively defined data structures\index{recursive, ~ data structure} 
like lists, sets, and trees play a central role in computing science. \Tl\ 
provides means for the definition of recursive data types\index{recursive, 
~ data type} enabling a straightforward realization of recursively defined 
data structures. 

A recursive type definition is introduced by the keyword 
\k{Rec}\index{{\bf Rec}} in \Tl. A supertype\index{supertype} (e.g., 
\s{IntegerList $<$:\k{Ok}}) has to be specified when defining a recursive 
type. The definition of a list\index{list} for integer values is 
considered as an example. 


\begin{xple}
    \k{Let} \k{Rec} IntegerList $<$:\k{Ok} =
       \k{Tuple}
          \k{case} nil
          \k{case} cons \k{with} car :Int  cdr :IntegerList
       \k{end}
\end{xple}

The following expressions show the construction of  an empty list and the 
construction of a new list from an existing (possibly empty) list by 
appending a new element.  


\begin{xple}
    \k{let} emptyList =
       \k{tuple} \k{case} nil \k{of} IntegerList \k{end}

    \k{let} singleList =
       \k{tuple} \k{case} cons \k{of} IntegerList \k{with}
          \k{let} car = 7
          \k{let} cdr = emptyList
       \k{end}
\end{xple}

The next example shows the definition of a recursive 
value\index{recursive, ~ value}. As in the case of recursive functions, 
the type of the value has to be given explicitly. 

\begin{xple}
    \k{let} \k{rec} circularList :IntegerList =
       \k{tuple} \k{case} cons \k{of} IntegerList
          7  circularList
       \k{end}
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Dynamic Data Types}
\label{Abs. Dynamische Datentypen}

In\index{dynamic type}\index{type, dynamic ~} data-intensive 
applications\index{data-intensive application} there are programming 
situations where a context has to use a value generated by another context 
although the two context do not share common type information supporting 
static checking\index{static type checking}. In such situations it is 
desirable to defer the type checking\index{type, deferred ~ checking} to 
well-defined points during program evaluation. In \Tl, the keywords 
\k{Dyn}\index{{\bf Dyn}} and \k{typecase}\index{{\bf typecase}}\index{{\bf 
when}} are provided for this purpose. Their application is illustrated by 
the following example. 

\begin{xple}
    \k{Let} Auto = \k{Tuple} \k{Dyn} T $<$:\k{Ok}  x :T \k{end}
    \k{let} a1 = \k{tuple} \k{Let} \k{Dyn} T = Int  \k{let} x = 3 \k{end}
    \k{let} a2 = \k{tuple} \k{Let} \k{Dyn} T = String  \k{let} x = ''Hello'' \k{end}

    \k{let} asString(a :Auto) :String =
       \k{typecase} a.T
          \k{when} Int \k{then} fmt.int(a.x)
          \k{when} String \k{then} a.x
          \k{when} \k{Tuple} name :String \k{end} \k{then} a.x.name
          \k{when} \k{Tuple} \k{end} \k{then} ''Tuple''
          \k{else} ''???''
       \k{end}
\end{xple}

As discussed in \cite{Matt93} and in \cite{Nels91} structural 
equivalence\index{structural equivalence} is a prerequisite for dynamic 
type checking in persistent, distributed systems.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Subtype Relationships and Subtype Polymorphism}
\label{Abs. Subtypbeziehungen und Subtyppolymorphismus}

In \Tl, a signature\index{signature}\index{subtyping} of the form \s{x :A} 
is considered a partial specification\index{partial specification}. A 
value bound to the variable \s{x} has to fulfil at least the specification 
defined by the type \s{A}. The underlying partial order on types (\s{B} is 
more precise than \s{A}) is  described explicitly by an inductively 
defined subtype relationship\index{subtype, ~ relationship} (\s{B 
$<$:A}\index{$<$:}, \s{B} is subtype\index{subtype} of \s{A}).

The supertype\index{supertype} of all non-parameterized 
types\index{non-parametrized type}\index{type, non-parametrized ~} is 
\k{Ok}\index{{\bf Ok}} \cite{Matt93}. It represents the trivial 
specification\index{trivial specification} that is fulfilled by all 
values. The following example illustrates the use of the type \k{Ok}. The 
functions \s{fst} and \s{snd} both discard one of their parameters. The 
type of this parameter needs just a trivial specification.

\begin{xple}
    \k{let} fst(a :Int  b :\k{Ok}) :Int = a
    \k{let} snd(a :\k{Ok}  b :Int) :Int = b
    fst(3 4)  fst(3 true)  snd(3 4)  snd(true 4)
    \r 3 :Int  3 :Int  4 :Int  4 :Int
\end{xple}

The kind of polymorphism represented by the functions \s{fst} and \s{snd} 
is called \e{subtype polymorphism}\index{subtype, ~ 
polymorphism}\index{polymorphism, subtype ~}. According to the subsumption 
principle\index{subsumption principle} the dynamic binding of formal 
parameters of a static type \s{A} to values of an arbitrary subtype \s{B 
$<$:A} is possible.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Subtyping on Predefined Types}
\label{Abs. Subtypbeziehungen vordefinierter Typen}

All\index{subtyping, ~ on predefined types}\index{predefined, subtyping on 
~ types} predefined base types fulfil the trivial specification 
(\s{$<$:}\k{Ok}), e.g.:

\begin{xple}
    Int $<$:\k{Ok}
    Real $<$:\k{Ok}
    \k{Fun}(:Int) :Int $<$:\k{Ok}
    \k{Tuple} :Int \k{end} $<$:\k{Ok}
\end{xple}

Non-trivial subtype relationships, e.g., of the form \s{Int $<$:Real} do 
not exist between the base types of \T. It is, however, possible to define 
subtypes of these types in the \T\ libraries  as, for example, 
\s{directory.T $<$:String}. Values of the type \s{directory.T} represent 
syntactically correct path names of the operating systems and thereby also 
strings. The reverse is not true. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Subtyping on Tuple Types}
\label{Abs. Subtypbeziehungen zwischen Tupeltypen}

In \Tl, subtyping on tuple types\index{subtyping, ~ on tuple 
types}\index{tuple type, subtyping on ~s} is based on structural 
compatibility\index{structural compatibility}. Subtype relationships are 
not only defined between two tuple types without variants and two tuple 
types with variants, but also between a tuple type without and a tuple 
type with variants. 


A tuple type \s{B} without variants is a subtype of a tuple type \s{A} 
without variants if the signatures of \s{B} are a prefix of the signatures 
of \s{A}, e.g., for 

\begin{xple}
    \k{Let} Student = \k{Tuple} name :String  age :Int  semester :Int \k{end}
    \k{Let} Person = \k{Tuple} name :String  age :Int \k{end}
    \k{Let} Car = \k{Tuple} name :String  age :Int \k{end}
    \k{Let} Machine = \k{Tuple} name :String  fuel :String \k{end}
    \k{Let} NamedThing = \k{Tuple} name :String \k{end}
\end{xple}

the following subtype relationships hold

\begin{xple}
    Student $<$:Person  Person $<$:NamedThing
    Car $<$:NamedThing  Machine $<$:NamedThing
\end{xple}

but also 

\begin{xple}
    Car $<$:Person  Person $<$:Car
\end{xple}

On the other hand, it is described in \cite{Matt93} how the \T\ subtype 
relationship can be  restricted systematically to explicitly defined 
\e{subclasses}\index{subclass}  ensuring, for example, that \s{car.T $\not 
<:$person.T} holds.

A subtype of a tuple type can also be defined by specializing the types of 
tuple fields. For example, the definition 

\begin{xple}
    \k{Let} Student2 = \k{Tuple} name :\k{Ok}  age :Int  semester :Int \k{end}
\end{xple}

implies the following subtype relationship.

\begin{xple}
    Student $<$:Student2  
\end{xple}


In \Tl, a subtype\index{subtype, ~ definition} can be defined without 
repeating explicitly all the components\index{repeating component} of the 
supertype. The keyword \k{Repeat}\index{{\bf Repeat}} is used for this 
purpose. A definition of the type \s{Student} on the basis of the type 
\s{Person} may look as follows.

\begin{xple}
    \k{Let} Student = \k{Tuple} \k{Repeat} Person  semester :Int \k{end}
\end{xple}

This notation is applicable wherever signatures are expected, e.g., in 
function signatures. A corresponding construct exists on the value level. 
The keyword \k{open}\index{{\bf open}} supports the repetition of existing 
bindings\index{repetition of binding}\index{binding, repetition of ~}. The 
value \s{peter} defined in section \ref{Abs. Tupeltypen}, for example, can 
be extended by specifying its semester.

\begin{xple}
    \k{let} peterAsStudent :Student = \k{tuple} \k{open} peter  \k{let} semester = 6 \k{end}
\end{xple}

The major advantage of subtyping is the fact that functions working on a 
type also accept values of arbitrary subtypes of this type. Thereby, 
subtyping facilitates a later extension of programs\index{program 
extension}, in particular, the extension of data structures with new 
components. Functions written for the original type are also applicable to 
values of the new type. These values are recognized as instances of the 
old type. A function expecting two parameters of type \s{NamedThing} also 
works on values of the types \s{Student}, \s{Car}, or \s{Machine}.  

\begin{xple}
    \k{let} sameName(x, y :NamedThing) :Bool =
       string.equal(x.name y.name)

    \k{let} fiat :Machine = \k{tuple} \k{let} name = ''Uno''  \k{let} fuel = ''unleaded'' \k{end}

    sameName(peter fiat)
    \r false :Bool
\end{xple}

A tuple type \s{B} with variants is a subtype of a tuple type \s{A} with 
variants\index{subtyping, ~ on variant types}\index{variant type, 
subtyping on ~s}, if the ordered sequence of variant names of \s{B} is a 
prefix of the sequence of variant names of \s{A} and the signatures 
\s{S$_i$} of each variant of \s{B} are tuple subsignatures of the 
corresponding variant signatures \s{S$_i$}$'$ of \s{A}. For example,  the 
relationship \s{RGBColor $<$:Color} holds for

\begin{xple}
    \k{Let} RGBColor = \k{Tuple} \k{case} red, green, blue \k{end}
    \k{Let} Color = \k{Tuple} \k{case} red, green, blue, cyan, yellow  \k{end}
\end{xple}

and the relationship \s{Address $<$:Address2} holds for the type 
\s{Address} declared in section \ref{Abs. Variantentypen} if \s{Address2} 
is defined, for example, as follows:

\begin{xple}
    \k{Let} Address2 = 
       \k{Tuple}
          \k{case} national \k{with} street, city :String  zip :Int
          \k{case} international \k{with} street, city, state :String  zip :String
          \k{case} unknown
       \k{end}
\end{xple}

Finally, a tuple type without variants having signatures \s{S} is a 
subtype of a tuple type \s{A} with variants if the signatures \s{S} are 
tuple subsignatures of the signatures \s{S}$'$ of the first variant of 
\s{A}. The relationship  \s{AddressTuple $<:$Address2}, therefore, holds 
for 

\begin{xple}
    \k{Let} AddressTuple = \k{Tuple} street, city :String  zip :Int \k{end}
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Subtyping on Record Types}
\label{Abs. Subtypbeziehungen zwischen Recordtypen}

As in the case of tuple types, subtypes of record types\index{subtyping, ~ 
on record types}\index{record type, subtyping on ~s} can be constructed by 
specialization of types of existing components as well as by extension 
with new components. Additionally, the fact that the signatures of record 
types are not ordered is taken into account by the subtyping rules. A 
record type \s{B} with signatures \s{S} is a subtype of a record type 
\s{A} with signatures \s{S}$'$ if the signatures \s{S} contain a subset of 
signatures \s{S}$''$ which are subsignatures\index{subsignature} of 
\s{S}$'$.

\begin{xple}
    \k{Let} Person = \k{Record} name :String  age :Int \k{end}
    \k{Let} Student = \k{Record} name :String  semester :Int \k{end}
    \k{Let} Employee = \k{Record} ssno :String  salary :Real \k{end}
    \k{Let} Tutor = \k{Record} name, ssno :String age, semester :Int salary :Real \k{end}
\end{xple}

For these types the following subtype relationships hold in \Tl,

\begin{xple}
    Tutor $<$:Person  Tutor $<$:Student  Tutor $<$:Employee
\end{xple}

enabling the application of functions which are defined for arguments of 
the types \s{Person}, \s{Student}, or \s{Employee} to values of the type 
\s{Tutor}. Furthermore, it becomes possible to construct heterogeneous 
data structures\index{heterogeneous data structure} consisting, for 
example, of values of the types \s{Person}, and \s{Tutor}. Subtyping 
hierarchies\index{subtyping, ~ hierarchies} over record types are not 
restricted to tree structures as in the case of tuple types. Other 
directed acyclic graphs are also possible, thus making the representation 
of multiple inheritance\index{multiple inheritance} hierarchies possible.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Subtyping on Function Types}
\label{Abs. Subtypbeziehungen zwischen Funktionstypen}

The\index{subtyping, ~ on function types}\index{function type, subtyping 
on ~s} interpretation of types and signatures as partial specifications 
and of subtypes and subsignatures as specification refinements implies the 
well-known \e{contravariance rule}\index{contravariance rule} for the 
subtyping on function types. According to this rule  a function type with 
signatures  \s{S} for its formal parameters and result type \s{B} is a 
subtype of a function type with signatures \s{S}$'$ and result type \s{A} 
iff \s{B $<$:A} and \s{S}$'$ are subsignatures\index{subsignature} of 
\s{S}. In other words, a function \s{F$_1$} is a specialization of a 
function \s{F$_2$}, if under the assumption, that the 
preconditions\index{precondition} of \s{F$_2$} hold, the 
postconditions\index{postcondition} of \s{F$_1$} fulfil at least the 
postconditions of \s{F$_2$} and the preconditions of \s{F$_1$} are not 
more restrictive than the preconditions of \s{F$_2$} \cite{Matt93}.

For example, assuming the relationship  \s{Student $<$:Person} the 
relationship \s{GetRichestStudent $<$:GetRichestPerson} holds for the 
following function types because the result types of the function types 
are in covariance relationship\index{covariance relationship}. 

\begin{xple}
    \k{Let} GetRichestPerson = \k{Fun}() :Person
    \k{Let} GetRichestStudent = \k{Fun}() :Student
\end{xple}

However, for the function types  

\begin{xple}
    \k{Let} HirePerson = \k{Fun}(:Person) :\k{Ok}
    \k{Let} HireStudent = \k{Fun}(:Student) :\k{Ok}
\end{xple}
 
the relationship \s{HirePerson $<$:HireStudent} holds because the types of 
the function parameters are contravariant. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Parametric Polymorphism}
\label{Abs. Parametrischer Polymorphismus}

The type system of \Tl\ supports two kinds of 
polymorphism\index{polymorphism}: subtype polymorphism and parametric 
polymorphism\index{polymorphism, parametric ~}\index{parametric 
polymorphism}. Subtype polymorphism is presented in the previous section. 
Parametric polymorphism is the topic of this section. It makes the 
introduction of explicit type parameters\index{type, ~ parameter} into 
function and type definitions possible. 

Function definitions with parameters describe \e{polymorphic} functions, 
whereas the introduction of type parameters into type definitions results 
in \e{type operators}. Type operators\index{type operator} are 
functions\index{function, ~ on type level} mapping types to types. They 
introduce parametrization\index{parametrization} into type declarations. 

If a type is restricted explicitly to a subtype of a given type, this kind 
of polymorphism is called \e{bounded parametric polymorphism}. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Polymorphic Functions}
\label{Abs. Polymorphe Funktionen}

A function is made polymorphic (generic)\index{polymorphic 
function}\index{generic function}\index{function, polymorphic 
~}\index{function, generic ~} by extending its signature by one or more 
type parameters\index{type, ~ parameter}. The type parameters are 
instantiated with type expressions when the function is applied. 

The polymorphic identity function is a simple example of a polymorphic 
function. 
\begin{xple}
    \k{let} id(A $<$:\k{Ok}  a :A) :A = a
\end{xple}

Such a function is called with a type (e.g.,\s{:Int}) and a value (e.g., 
\s{7}) of this type as actual parameters\index{function, ~ application}. 

\begin{xple}
    id(:Int 7)
    \r 7 :Int
    id(:String ''Peter'')
    \r ''Peter'' :String
\end{xple}

The specification of the type argument\index{type, ~ argument} can be 
omitted in most cases because it can be inferred by the system from the 
value passed as parameter (type inference\index{type, ~ inference}). 

\begin{xple}
    id(7)
    \r 7 :Int
    id(''Peter'')
    \r ''Peter'' :String
\end{xple}

The instantiation of type parameters is not restricted to base types. 
Arbitrary user-defined types (e.g., the type \s{Person} with the value 
\s{peter}) can be chosen as parameter for a polymorphic function 

\begin{xple}
    id(peter)
    \r \k{tuple} name = ''Peter'' age = 3 \k{end} :Person
\end{xple}

Parametric polymorphism makes it possible to write functions working 
uniformly for arbitrary types. Polymorphic functions, therefore, can be 
used to describe type-independent behavior\index{type-independent 
behavior}. Separate functions for each considered parameter type would be 
necessary for this purpose in languages like C or \mbox{Modula-2}.

Much of the power of \Tl\ results from the possibility to combine the 
concepts of polymorphic and higher-order functions with each other. This 
is illustrated by a polymorphic sorting function. The pure sorting 
process, i.e.\ the permutation of the elements, is type-independent. 
Therefore, it can be described by a polymorphic function. On the other 
hand, the comparison of the elements during the sorting process is 
type-dependent. This task can be solved by passing a function whose 
application compares two elements as a parameter to the polymorphic 
sorting function. The signature of a polymorphic function sorting arrays 
of an arbitrary element type could look as follows. 


\begin{xple}
    \k{let} sort(A $<$:\k{Ok}  a :\k{Array}(A)  order(a, b :A) :Bool) :\k{Array}(A) = \dots
\end{xple}

In order to sort an array of a specific type, it is sufficient to write a 
function for the element comparison of this array. The sorting of persons 
by ascending age is considered as an example. 

\begin{xple}
    \k{let} older(a, b :Person) :Bool = a.age $>$= b.age
\end{xple}

The following call of the function  \s{sort} sorts an array of persons 
according to their age. 

\begin{xple}
    sort(:Person personArray older)
\end{xple}

Again, the type parameter can be omitted. 

\begin{xple}
    sort(personArray older)
\end{xple}

Further examples of polymorphic functions can be found in the sections 
\ref{Abs. Typoperatoren} and \ref{Abs. Abstrakte Datentypen}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Bounded Parametric Polymorphism}
\label{Abs. Eingeschraenkter parametrischer Polymorphismus}

Bounded parametric polymorphism\index{bounded parametric 
polymorphism}\index{polymorphism, bounded parametric ~}, a restricted form 
of parametric polymorphism, is introduced into polymorphic functions by 
specifying a type as a bound for the formal type parameter in the 
signature. Only subtypes of the given type can be passed as parameter to 
such functions. Employing subtype polymorphism\index{subtype, ~ 
polymorphism}, a function comparing the component \s{age} of two values of 
an arbitrary subtype of the type \s{Person} can be defined in the 
following way. 

\begin{xple}
    \k{let} chooseOlder(p1, p2 :Person) :Person =
       \k{if} p1.age $>$ p2.age \k{then} p1 \k{else} p2 \k{end}

    \k{let} peter :Student =
       \k{tuple} \k{let} name = ''Peter''  \k{let} age = 24  \k{let} semester = 3 \k{end}

    \k{let} paul :Student =
       \k{tuple} \k{let} name = ''Paul''  \k{let} age = 29  \k{let} semester = 6 \k{end}

    chooseOlder(peter paul)
    \r \k{tuple} \k{let} name = ''Paul'' \k{let} age = 29 \k{end} :Person
\end{xple}

Considering the function result displayed by the system, it can be seen 
that the attribute \s{semester} of \s{paul} is missing. This is a 
consequence of the fact that type information is lost\index{loss of type 
information} at compile time. In order to avoid the loss of attributes of 
subtypes, \s{chooseOlder} has to be defined as a polymorphic function.

\begin{xple}
    \k{let} chooseOlder(P $<$:Person  p1, p2 :P) :P =
       \k{if} p1.age $>$ p2.age \k{then} p1 \k{else} p2 \k{end}

    chooseOlder(peter paul)
    \r \k{tuple} name = ''Paul'' age = 29 semester = 7 \k{end} :Student
\end{xple}

As a result of integrating enough type information into the function 
definition, all attributes are taken into account. By introducing the 
specification \mbox{\s{P $<$:Person}}, the function \s{chooseOlder} is 
made polymorphic, but in contrast to the unrestricted parametric 
polymorphism, the polymorphism is restricted to subtypes of the type 
\s{Person}. The type variable \s{P} makes the intended relationship 
between the type of the formal parameters and the type of the result of 
the function explicit. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Type Operators}
\label{Abs. Typoperatoren}

Polymorphic functions support the description of type-independent 
behavior. Similarly, type-independent patterns on the type level lead to 
generic type expressions in the form of type operators\index{type 
operator}, which can be instantiated with concrete types. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Simple Type Operators}
\label{Abs. Einfache Typoperatoren}

A\index{type operator, simple ~} simple example of a type operator is an 
identity function on the type level corresponding to the polymorphic 
identity function presented above\index{{\bf Oper}}\index{{\bf Let}}. 

\begin{xple}
    \k{Let} Id = \k{Oper}(A $<$:\k{Ok}) A
\end{xple}

Similar to the function definition, the following abbreviated notation is 
also possible. 

\begin{xple}
    \k{Let} Id(A $<$:\k{Ok}) = A
\end{xple}
The operator \s{Id} maps the type passed as parameter to itself.

\begin{xple}
    :Id(Int)
    \r :Int
    :Id(Id(Bool))
    \r :Bool 
\end{xple}

A more practical application of the type operators is the description of 
optional values\index{optional value}.

\begin{xple}
    \k{Let} Opt(A $<$:\k{Ok}) =
       \k{Tuple}
          \k{case} nil
          \k{case} notNil \k{with} val :A
       \k{end}
\end{xple}

The syntax for the application\index{type operator, ~ application} of a 
type operator is equivalent to the syntax for the function application. 


\begin{xple}
    Opt(Person)
    Id(Opt(Id(Person)))
\end{xple}

Symbolic identifiers bound to type operators can be used in infix 
notation\index{infix notation}. These infix operators\index{infix 
operator} on the type level are all left-associative and of the same 
precedence. The classical binary type operators of functional programming 
languages can be introduced into TL in the following way.

\begin{xple}
    \k{Let} --$>$(X, Y $<$:\k{Ok}) = \k{Fun}(:X) :Y
    \k{Let} *(X, Y $<$:\k{Ok}) = \k{Tuple} fst :X  snd :Y \k{end}
    \k{Let} +(X, Y $<$:\k{Ok}) = \k{Tuple} \k{case} fst \k{with} x :X  \k{case} snd \k{with} y :Y \k{end}
\end{xple}

The preceding examples are restricted to first-order type 
operators\index{type operator, first-order ~}. \Tl\ also supports the 
definition of higher-order type operators\index{type operator, 
higher-order ~}. Higher-order type operators are, for example, type 
operators accepting a type operator as parameter and applying it to 
different types in the body. Other examples are type operators generating 
type operators as result based on non-parametrized types passed as 
parameters. The coding of case selections on the type level is considered 
as an illustrative example.

\begin{xple}
    \k{Let} Boolean(Then, Else $<$:\k{Ok}) = \k{Ok}
    \k{Let} True(Then, Else $<$:\k{Ok}) = Then
    \k{Let} False(Then, Else $<$:\k{Ok}) = Else
    \k{Let} Cond(If $<$:Boolean  Then, Else $<$:\k{Ok}) = If(Then Else)

    \k{let} i :Cond(True Int String) = 3
    \k{let} s :Cond(False Int String) = ''Peter''
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Recursive Type Operators}
\label{Abs. Rekursive Typoperatoren}

In addition to recursive types \Tl\ supports recursive type 
operators\index{type operator, recursive ~}\index{recursive, ~ type 
operator}. The type operator \s{List} maps a type \s{E} to the type of a 
list with elements of type \s{E}. For this purpose a type parameter is 
introduced into the definition of lists presented in section \ref{Abs. 
Rekursive Datentypen}.

\begin{xple}
    \k{Let} \k{Rec} List(A $<$:\k{Ok}) $<$:\k{Ok} =
       \k{Tuple}
          \k{case} nil
          \k{case} cons \k{with} car :A  cdr :List(A)
       \k{end}
\end{xple}

The corresponding list operations can be implemented by polymorphic 
functions.

\begin{xple}
    \k{let} new(A $<$:\k{Ok}) :List(A) =
       \k{tuple} \k{case} nil \k{of} List(A) \k{end}

    \k{let} cons(A $<$:\k{Ok}  head :A  tail :List(A)) :List(A) =
       \k{tuple} \k{case} cons \k{of} List(A) \k{with} head tail \k{end}
\end{xple}

The polymorphic functions \s{new} generates empty lists of arbitrary 
types. Elements can be added at the beginning of the list by the function 
\s{cons}.

In contrast to traditional programming languages, generic list, set, and 
tree types and polymorphic operations on these types can be defined in 
\Tl\ reducing the number of functions that have to be implemented. 

The concepts of polymorphic functions\index{polymorphic function} and type 
operators complement each other. Generic code\index{generic code} can be 
used for the description of structures as well as of behavior. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Abstract Data Types}
\label{Abs. Abstrakte Datentypen}

An abstract data type\index{abstract data type} (ADT\index{ADT}) consists 
of a data type and of a set of operations defined on this data type. Only 
the name of the type and the names and signatures of the operations are 
visible to programs that use the ADT. The implementation of the type and 
of the operations are hidden by the ADT. The operations provided by the 
ADT are the only possible and legal ones on the ADT. This protects the 
values of the ADT against undesired manipulations. 

Since the implementation is hidden, it can be changed locally without 
invalidating programs that use the ADT. If different implementations exist 
for an ADT, these implementations can be exchanged dynamically. 

A general functional stack\index{stack} is presented as an example. The 
stack is declared employing a polymorphic abstract data 
type\index{abstract data type, polymorphic ~}. 

\begin{xple}
    \k{Let} Stack =
       \k{Tuple}
          T(E $<$:\k{Ok}) $<$:\k{Ok}
          new(E $<$:\k{Ok}) :T(E)
          empty(E $<$:\k{Ok} stack :T(E)) :Bool
          push(E $<$:\k{Ok} element :E stack :T(E)) :T(E)
          pop(E $<$:\k{Ok} stack :T(E)) :T(E)
          top(E $<$:\k{Ok} stack :T(E)) :E
       \k{end}
\end{xple}

In the following an implementation of this interface based on the module 
\s{list}\footnote{\s{list} is a module of the standard library 
implementing polymorphic lists and the according operations.} is presented.


\begin{xple}
    \k{let} listStack :Stack =
       \k{tuple}
          \k{Let} T(E $<$:\k{Ok}) $<$:\k{Ok} = list.T(E)
          \k{let} new(E $<$:\k{Ok}) :T(E) = list.new(:E)
          \k{let} empty(E $<$:\k{Ok} stack :T(E)) :Bool = list.empty(stack)
          \k{let} push(E $<$:\k{Ok} element :E stack :T(E)) :T(E) =
             list.cons(element stack)
          \k{let} pop(E $<$:\k{Ok} stack :T(E)) :T(E) = list.tail(stack)
          \k{let} top(E $<$:\k{Ok} stack :T(E)) :E = list.head(stack)
       \k{end}
\end{xple}

In this example, \s{T} is defined as a type operator\index{type operator} 
and the operations  \s{new},
\s{empty}, \s{push}, \s{pop}, and \s{top} are implemented as polymorphic 
functions\index{polymorphic function}. Therefore, stacks for arbitrary 
data types can be generated.

ADTs are based on the concept of type signatures in tuple types. This 
leads to the concept of \e{semi-abstract} data types\index{abstract data 
type, semi-~}\index{semi-abstract data type} in \Tl. As an example, the 
signature of the type operator in the ADT \s{Stack} above can be modified 
in order to exhibit more information about the implementation of the ADT.  
 
\begin{xple}
    \k{Let} Stack2 =
       \k{Tuple}
          T $<$:list.T
          \dots
       \k{end}

    \k{let} listStack2 :Stack2 = 
       \k{tuple}
          \dots
       \k{end}
\end{xple}
Users of the ADT \s{Stack2} can apply operations  that expect values of 
the type \s{list.T} on the values of type \s{listStack2.T} in addition to 
the functions defined for the stack. On the other hand, a value of type 
\s{list.T} is incompatible with functions defined by \s{listStack}.


In \Tl, a subsignature relationship\index{subsignature, ~ relationship} 
between signatures of ADTs is defined: 

\begin{xple}
    Stack2 $<$:Stack
\end{xple}

Finally, a tuple signature\index{tuple, ~ signature} can make a local type 
binding visible globally\index{visibility}.
\begin{xple}
    \k{Let} Stack3 =
       \k{Tuple}
          \k{Let} T = list.T
          \dots
       \k{end}
\end{xple}

Such type definitions are particularly useful in interfaces of modules 
when programming libraries (compare section \ref{Abs. Module und 
Schnittstellen}).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Imperative Programming}
\label{Abs. Imperative Programmierung}

The\index{imperative programming} discussions in the previous sections are 
restricted to the functional concepts underlying the language \Tl. The 
imperative programming features are described in this section. 

Imperative programming is based on \e{mutable} variables in a global 
(possibly \e{persistent}) store. The   flow of control between operations 
as allocation, inspection, and destructive update of objects in the store 
is determined by constructs for sequences and loops.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Mutable Variables}
\label{Abs. Modifizierbare Variablen}

Binding a value to an identifier by the \k{let}-construct\index{{\bf let}} 
is equivalent to the definition of a \e{constant}\index{constant 
definition} because no update of the value bound to the identifier is 
possible. A further binding of an existing identifier to a new value 
employing the  \k{let}-construct establishes a new constant. 

In  \Tl, bindings of identifiers to mutable variables\index{mutable 
variable}\index{variable, ~ declaration}\index{variable}\index{variable, 
mutable ~} are marked by the keyword \k{var}\index{{\bf var}}. 
Subsequently, an existing mutable variable can be updated with new values 
employing the \e{destructive} assignment \s{:=}\index{:=}. 

\begin{xple}
    \k{let} \k{var} x = 3
    \k{let} \k{var} y = 4
    x y
    \r 3 :Int  4 :Int

    x := y
    \r \k{ok} :\k{Ok}
    x y
    \r 4 :Int  4 :Int

    y := 5
    \r \k{ok} :\k{Ok}
    x y
    \r 4 :Int  5 :Int
\end{xple}

For anonymous variables\index{anonymous variable}, e.g., inside of tuple 
values, the keyword \k{var} precedes the value used to initialize the 
variable. 


\begin{xple}
    \k{tuple} \k{var} ''text''  \k{var} 3 \k{end}
\end{xple}

The destructive assignment \index{assignment} is a globally defined 
function with the following signature.

\begin{xple}
    :=(A $<$:\k{Ok}  \k{var} lValue :A  rValue :A) :\k{Ok}
\end{xple}

The signature of the function defines that the assignment evaluates to the 
trivial value \k{ok} of type \k{Ok}\index{{\bf Ok}}\index{{\bf ok}} as it 
is the case for the empty block. Note that the infix symbol \s{:=} is not 
a keyword. Therefore, it can be bound locally to a user-defined 
polymorphic function. 

\Tl\ realizes two parameter passing mechanisms\index{parameter passing, ~ 
mechanism} for functions, namely the concept of value 
parameters\index{value, ~ parameter} (\e{call by value}\index{call by 
value}) presented in section \ref{Abs. Einfache Funktionen} and the 
concept of variable parameters\index{variable, ~ parameter} (\e{call by 
reference}\index{call by reference}). The latter concept is illustrated by 
the following example. 


\begin{xple}
    \k{let} swap(A $<$:\k{Ok}  \k{var} x, y :A) =
       \k{begin}  \k{let} tmp = x  x := y  y := tmp  \k{end}

    \k{let} \k{var} a = 3 \k{and} \k{var} b = 5
    swap(:Int a b)
    a b
    \r 5 :Int  3 :Int
\end{xple}

When applied, the function  \s{swap} references the L-values of the 
mutable variables \s{a} and \s{b} through the formal parameters in the 
signature. On return from the function, the values of the mutable 
variables are swapped.

The concept of higher-order functions presented in section \ref{Abs. 
Funktionen hoeherer Ordnung} supports the dynamic generation of 
encapsulated state variables, which can be shared by several functions 
(\e{shared variables}\index{shared variable}). In the following example, 
the variable \s{state} can be updated and inspected, respectively, by the 
three defined functions only.


\begin{xple}
    \k{let} newCounter() =
       \k{begin}
          \k{let} \k{var} state = 0
          \k{tuple}
             \k{let} reset() :\k{Ok} =  state := 0
             \k{let} inc() :\k{Ok} =  state := state + 1
             \k{let} value() :Int =  state
          \k{end}
       \k{end}

    \k{let} cntr1 = newCounter() \k{and} cntr2 = newCounter()
    cntr1.inc()  cntr1.value()  cntr2.value()
    \r \k{ok} :\k{Ok}  1 :Int  0 :Int
\end{xple}

Mutable function bindings enable the programmer to \e{override} 
functions\index{function, ~ overriding}. 


\begin{xple}
    \k{let} \k{var} f(x :Int) = x + 1
    f(3)
    \r 4 :Int
    f := \k{fun}(x :Int) x - 1
    f(3)
    \r 2 :Int
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Subtyping Rules for Mutable Bindings}
\label{Abs. Subtypisierungsregeln fuer modifizierbare Bindungen}

The \index{subtyping, ~ for mutable bindings}details of the interaction 
between the subtyping rules and the destructive assignment are very 
important for the type-safety of polymorphic programming languages. \Tl\ 
follows the example of the language Quest (and loosely related concepts 
in  C++) and disallows the application of the subsumption 
rule\index{subsumption rule} to mutable variables.  For this reason 

\begin{xple}
    \k{Fun}(x :Person  y :Person) :\k{Ok} $<$:\k{Fun}(x :Student  y :Student) :\k{Ok}
    \k{Tuple} x :Int \k{end} $<$:\k{Tuple} x :\k{Ok} \k{end}
\end{xple}

holds, but the following subtyping relationships do not hold in \Tl\  
\cite{Matt93}:

\begin{xple}
    \k{Fun}(\k{var} x :Person  y :Person) :\k{Ok} $<$:\k{Fun}(\k{var} x :Student  y :Student) :\k{Ok}
    \k{Tuple} \k{var} x :Int \k{end} $<$:\k{Tuple} \k{var} x :\k{Ok} \k{end}
\end{xple}

However, the concept of the bounded parametric polymorphism supported in 
\Tl makes the definition of a type-safe polymorphic function \s{update} 
working uniformly for arbitrary subtypes of type \s{Person} possible. 

\begin{xple}
    \k{let} update(P $<$:Person  \k{var} a, b :P) = a:= b
\end{xple}

Finally, it is possible in \Tl\ to type a mutable variable in an aggregate 
as a non-mutable value. As a consequence, the more liberal subtyping rules 
can be applied for the read-only access\index{read-only access} to value 
variables, e.g., 


\begin{xple}
    \k{Tuple} \k{var} x :Int \k{end} $<$:\k{Tuple} x :Int \k{end} $<$:\k{Tuple} x :\k{Ok} \k{end}
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Control Structures}
\label{Abs. Kontrollstrukturen}

In addition to \e{sequences}, \Tl\  offers control 
structures\index{control structure} for \e{conditional expressions}, three 
kinds of \e{loops} and a structured \e{exception handling} supporting a 
flexible imperative programming style. For the sake of completeness, 
concepts already introduced in previous sections are mentioned again.
  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Sequences}
\label{Abs. Sequenz}

A sequence\index{sequence} describes the sequential 
execution\index{sequential execution} of expressions. As mentioned in 
section \ref{Abs. Statische Bindungen}, expressions are enclosed by the 
keywords \k{begin} \index{{\bf begin}} and \k{end} in order to form a 
block\index{block}. The type of a sequence is determined by the type of 
the last expression or binding in the block. 

\begin{xple}
    \k{begin}
       \k{let} s = ''text''
       \k{let} x = 1
    \k{end}
    \r 1 :Int
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Conditional Expressions}
\label{Abs. Bedingte Ausfuehrung}

The simplest form of a conditional expression \index{conditional 
expression} is described by an \k{if}-expression\index{{\bf 
if}}\index{{\bf else}}\index{{\bf then}}\index{{\bf elsif}} in \Tl. The 
result types of all \k{then}-branches
and the \k{else}-branch have to be compatible.

\begin{xple}
    \k{if} x == 0 \k{then}
       0
    \k{elsif} x $<$ 0 \k{then}
       --1
    \k{else}
       1
    \k{end}
\end{xple}

Several conditions can be conjuncted by \k{andif}\index{{\bf orif}}
and \k{orif}\index{{\bf andif}} operators in \Tl.

\begin{xple}
    \k{if} x == 0 \k{andif} y == 0 \k{orif} x != 0 \k{andif} y != 0 \k{then}
       0
    \k{else}
       x
    \k{end}
\end{xple}

Since \k{andif} and \k{orif} have the same precedence and are 
evaluated from left to right as, above expression is equivalent 
to the following more complex expression:

\begin{xple}
    \k{if} x == 0 \k{then}
       \k{if} y == 0 \k{then} 
          0
       \k{else} 
          \k{if} x != 0 \k{then}
             \k{if} y != 0 \k{then}
                0
             \k{else}
                x
             \k{end}
          \k{else}
             x
          \k{end}
       \k{else}
          x
       \k{end}
    \k{else}
       x
    \k{end}
\end{xple}

Two further constructs for conditional expressions are provided in \Tl\ 
(compare section \ref{Abs. Variantentypen} und \ref{Abs. Dynamische 
Datentypen}).

\begin{xple}
    \k{let} weekDay(d :Day) :Bool =
       \k{case} d
          \k{when} mon, tue, wed, thu, fri \k{then} true
          \k{else} false
       \k{end}

    \k{let} asString(\k{Dyn} A $<$:\k{Ok}  a :A) :String =
       \k{typecase} A
          \k{when} Int \k{then} fmt.int(a)
          \k{when} String \k{then} a
          \k{else} ''???''
       \k{end}
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Loops}
\label{Abs. Schleife}

Loops\index{loop} enclose sequences of expressions for the purpose of 
iteration\index{iteration}. The most general kind of loop is introduced by 
the keyword \k{loop}\index{{\bf loop}}. The result type of loops of this 
kind is \k{Ok}\index{{\bf exit}}\index{{\bf Ok}}.

\begin{xple}
    \k{loop}
       x := x + 2
       \k{if} x $>$ 100 \k{then} \k{exit} \k{end}
       x := x - 1
    \k{end}
\end{xple}

Furthermore, there are two more special forms of loops, the prechecking 
\k{while}-loops\index{loop, prechecking ~}\index{{\bf while}}\index{{\bf 
do}} and the enumerating  \k{for}-loops\index{loop, enumerating 
~}\index{{\bf for}}\index{{\bf do}}. The function computing the 
greatest common divisor of two integers is considered as an example of a 
prechecking loop. 

\begin{xple}
    \k{let} gcd(n, m :Int) :Int =
       \k{begin}
          \k{let} \k{var} vn = n  \k{and} \k{var} vm = m
          \k{while} vn != vm \k{do}
             \k{if} vn $>$ vm \k{then} vn := vn \% vm \k{end}
             \k{if} vn $<$ vm \k{then} vm := vm \% vn \k{end}
          \k{end}
          vn
       \k{end}
\end{xple}

Two versions of enumerating loops are distinguished in \Tl, one counting 
upwards (\k{upto}\index{{\bf upto}}) and the other counting downwards 
(\k{downto}\index{{\bf downto}}).

\begin{xple}
    \k{let} \k{var} x = 0
    \k{for} i = 50 \k{downto} 1 \k{do}
       x := x + i
    \k{end}
    x
    \r 1275 :Int
\end{xple}

Note, that it is not necessary to declare the loop variable\index{loop, ~ 
variable} \s{i} which has local scope. In section \ref{Abs. Felder und 
Feldindizierung}, an example of a loop counting upwards is presented. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Exception Handling}
\label{Abs. Ausnahmebehandlung}

Exception handling\index{exception, ~ handling}\index{exception} is a 
further important structuring facility. In \Tl, it is  also integrated 
smoothly into the type system. Exceptional situations that have to be 
handled cannot only be caused by partially defined functions as, for 
example, \s{int.div} (division by zero), but also by an overflow of a 
partially represented domain. Furthermore, the projection on variants 
described in section \ref{Abs. Variantentypen} can raise 
exceptions\index{exception, ~ raising} in \Tl.

Each exception returns an exception package\index{exception, ~ package} 
containing a string which supports the identification of the exception on 
the top level. 

\begin{xple}
    3 / 0
    \r Exception: ''Int error''
\end{xple}

If an exception occurs inside a composite expression, the further 
evaluation is aborted and the exception package is propagated. 

\begin{xple}
    \k{let} safeDiv(x, y :Int) :Int =
       \k{try} x / y \k{else} int.maxValue \k{end}
\end{xple}

In this example, the further propagation of an exception is stopped by the 
\k{try}-construct\index{{\bf try}}. As in the case of the 
\k{if}-construct, the result types of both blocks have to match. 

In addition to the standard exceptions\index{exception, standard ~}, \Tl\ 
also supports user-defined exceptions\index{exception, user-defined ~}. 
The definition of an exception includes the identifier of the exception 
and, optionally, a signature for exception arguments\index{exception, ~ 
argument}. The definition is introduced by the keyword 
\k{exception}\index{{\bf exception}}\index{{\bf with}}.

\begin{xple}
    \k{let} noCredit = \k{exception} ''No Credit'' \k{with} overdrawn :Int \k{end}
\end{xple}

The type\index{exception, ~ type}\index{type, exception ~}\index{{\bf 
Exception}} of an exception defines only its signature\index{exception, ~ 
signature} not its identity. 

\begin{xple}
    noCredit :\k{Exception} \k{with} overdrawn :Int \k{end}
\end{xple}

A \k{raise}-expression\index{{\bf raise}} returns an exception package as 
its result, which encapsulates the identity of the exception. Depending on 
the exception signature it can contain further bindings.  

\begin{xple}
    \k{let} withdraw(\k{var} account :Int  amount :Int) =
       \k{if} amount $<=$ account \k{then}
          account := account -- amount
       \k{else}
          \k{raise} noCredit \k{with} \k{let} overdrawn = amount -- account \k{end}
       \k{end}
\end{xple}

Exception packages propagate\index{exception, ~ propagation} through 
nested expressions along the dynamic call hierarchy until an exception 
block enclosed by \k{try} and \k{end} or the main program is 
reached\index{{\bf when}}\index{{\bf with}}\index{{\bf then}}.

\begin{xple}
    \k{try}
       withdraw(petersAccount  300)
       print.string(''Transfer succeeded'')
    \k{when} noCredit \k{with} exc \k{then}
       print.string(''Overdrawn by '' $<>$ fmt.int(exc.overdrawn))
    \k{else}
       print.string(''Unexpected exception occurred'')
    \k{end}
\end{xple}

Similar to the \k{case}-expressions a local value variable (here \s{exc}) 
in a  \k{when}-branch of the \k{try}-construct can be used to access the 
bindings of the exception package in a type-safe way. 

A handled exception can be  propagated explicitly by 
reraising\index{exception, ~ reraising} it (\k{reraise}\index{{\bf 
reraise}}). The following example also shows that exceptions raised by 
functions exported from \T-libraries are bound to exported identifiers 
enabling the user to define handlers for these exceptions.  

\begin{xple}
    \k{try} x / y
    \k{when} int.overflow \k{then} int.maxValue
    \k{when} int.error \k{then} print.string(''Division by zero'')  \k{reraise}
    \k{end}
\end{xple}

Types in \Tl\ only specify the values of terminating computations. For 
this reason an \e{arbitrary} type can be assigned to terms containing 
\k{raise}, \k{reraise}, or \k{exit} (see section \ref{Abs. Schleife}), 
e.g.,
\begin{xple}
    \k{if} a \k{then} 3 \k{else} \k{raise} int.overflow \k{end}  :Int
    \k{if} a \k{then} ''String'' \k{else} \k{raise} int.overflow \k{end}  :String
\end{xple}

This\index{{\bf exit}} fact is reflected by the type rules \s{\k{raise} 
\dots \k{end} :\k{Nok}}, \s{\k{reraise} :\k{Nok}}, and \s{\k{exit} 
:\k{Nok}}, where \k{Nok}\index{{\bf Nok}} denotes the subtype of all 
non-parametrized types in \Tl, i.e.,  


\begin{xple}
    A $<$:\k{Ok}  $\Rightarrow$  \k{Nok} $<$:A
\end{xple}

This property of the type \k{Nok} is frequently used for the definition of 
polymorphic \e{null elements}\index{polymorphic null element}. 


\begin{xple}
    \k{Let Rec} AnyStream $<$:\k{Ok} =
       \k{Tuple} empty() :Bool  get() :\k{Nok}  rest() :AnyStream \k{end}
    \k{let} emptyExc = \k{exception} ``Empty Stream''

    \k{let} emptyStream :AnyStream =
       \k{tuple}
          \k{let} empty() :Bool = true
          \k{let} get() :\k{Nok} = \k{raise} emptyExc
          \k{let} rest() :AnyStream = \k{raise} emptyExc
       \k{end}
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Arrays and Array Indexing}
\label{Abs. Felder und Feldindizierung}

An array\index{array} is an ordered, possibly empty sequence of anonymous 
bindings to mutable variables of a common supertype indexed by 
non-negative integers (\s{i $>=$ 0}). The size of an array is fixed 
statically when it is generated. The size cannot be modified dynamically, 
whereas the elements of an array can be updated dynamically by destructive 
assignments. A check of the index bounds\index{array, ~ index bound} is 
performed at runtime only. 

In \Tl, array types are defined using the constructor \s{Array(A)} and 
array values are initialized enumerating their elements inside of an 
\k{array}-\k{end}-block\index{{\bf array}}. The elements of an array are 
accessed by indexing\index{array, ~ indexing}. The indices are expressions 
of type \s{Int} enclosed in square brackets.


\begin{xple}
    \k{let} a :Array(Int) = \k{array} 0 1 2 3 4 5 \k{end}
    a[0] := a[1] + 7
\end{xple}

Using the \k{for}-loop it is possible to define, for example, a summation 
function accepting arrays of an arbitrary size. 

\begin{xple}
    \k{let} sum(arr :Array(Int)) :Int =
       \k{begin}
          \k{let var} result = 0
          \k{for} i = 0 \k{upto} extent(arr) \k{do}
             result := result + arr[i]
          \k{end}
          result
       \k{end}
\end{xple}

Finally, examples for the application of the function \s{sum} are 
presented illustrating the \e{listfix} notation\index{listfix notation} 
that can be used for functions on arrays in \Tl. 


\begin{xple}
    sum(\k{array} 1 2 3 4 \k{end})
    sum \k{of} 1 2 3 4 \k{end}
\end{xple}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Multi-Paradigm Programming in Tycoon}
\label{Abs. Progammierstile}

It\index{programming, multi-paradigm ~} has been one of the design goals 
of the Tycoon system to support generic, model-independent 
naming\index{naming}, binding\index{binding}, and typing\index{typing} 
schemata providing an environment that is open for external services. \Tl\ 
can be used to support programming styles\index{programming, ~ style}, 
which differ substantially from each other (see \cite{Matt93}). This is 
illustrated here by the realization of two concepts: abstract data 
types\index{abstract data type} and object-oriented 
encapsulation\index{encapsulation, object-oriented 
~}\index{encapsulation}. 

The different programming styles and concepts are not supported by special 
language constructs but are realized using the \Tl\ primitives for naming, 
binding, and typing.

In order to implement the concept of abstract data types the primitives of 
\Tl\ can be combined in three different ways. It is possible to aggregate 
an opaque type\index{opaque type}\index{type, opaque ~} together with the 
functions working on this type\footnote{This is comparable to an 
implementation of abstract types in Modula-2 using the module concept of 
this language.}. This approach can be implemented purely functionally or 
state-based\index{state-based} resulting in the first two realization 
variants. The third variant aggregates methods that work on a hidden, 
internal state\index{state}. The different realization alternatives are 
called 
\begin{itemize}
\item {\it functional} encapsulation,
\item {\it imperative} encapsulation, and
\item {\it method-based} encapsulation.
\end{itemize}  

A generic stack\index{stack} implementation is used to compare the three 
different realization alternatives. Each of them provides a type operator 
that maps the element type of the stack to a tuple type. In the first two 
cases this tuple type aggregates the opaque stack type {\it T}, the common 
stack operations {\it empty, push, pop, top}, and a parameterless function 
{\it new} for the creation of new empty stacks. For the third alternative, 
the tuple type aggregates only the stack operations. It represents the 
type of a stack. The function {\it new} has to be defined outside this 
type signature. 

\paragraph{Functional Encapsulation}
In\index{encapsulation, functional ~} the functional realization the 
modified stack is returned by the the update operations. Therefore, the 
result type of these functions is the opaque type {\it T}:
 \begin{xple}
\k{Let} FunStack (E $<:$\k{Ok}) =
   \k{Tuple}
       T $<:$\k{Ok}
       new() :T
       empty(stack :T) :Bool
       push(element :E stack :T) :T
       pop(stack :T) :T
       top(stack :T) :E
   \k{end}
\end{xple}

The data type is implemented by a parametrized variable. It provides a 
tuple value consisting of a definition of the representation type and of 
the functions of this type. The generic service ({\it list}) providing the 
list type and the operations on this type is also based on a functional 
implementation.
\begin{xple}
\k{let} listStack (E $<:$\k{Ok}) : FunStack(E) =
   \k{tuple}
      \k{Let} T $<:$\k{Ok} = list.T(E)
      \k{let} new() :T = list.new(:E)
      \k{let} empty(stack :T) :Bool = list.empty(stack)
      \k{let} push(element :E stack :T) :T = list.cons(element stack)
      \k{let} pop(stack :T) :T = list.tail(stack)
      \k{let} top(stack :T) :E = list.head(stack)
   \k{end}
\end{xple}
Using this realization a new stack with elements of type {\it Int} 
containing the element  4 can be created by the following function call:
\begin{xple}
  \k{let} intStack = listStack(:Int)
  \k{let} myStack = intStack.push(4 intStack.new())
\end{xple} 

\paragraph{Imperative Encapsulation}

In\index{encapsulation, imperative ~} the imperative realization the 
update operations change the state of the stack passed as parameter via 
side-effects. In contrast to the functional solution, the modified stacks 
are not returned as function result. For this reason the result type of 
these operations is \k{Ok}.
\begin{xple}
\k{Let} ImpStack (E $<:$ \k{Ok}) =
   \k{Tuple}
      T $<:$ \k{Ok}
      new() : T
      empty(stack :T) :Bool
      push(element :E stack :T) :\k{Ok}
      pop(stack :T) :\k{Ok}
      top(stack :T) :E
   \k{end}
\end{xple}

The representation type of the implementation is defined as a tuple type 
with a mutable component. The update operations are implemented using 
assignments.
\begin{xple}
\k{let} listStack (E $<:$\k{Ok}) : ImpStack(E) =
   \k{tuple}
      \k{Let} T $<:$\k{Ok} = \k{Tuple} \k{var} l :list.T(E) \k{end}
      \k{let} new() :T = \k{tuple} \k{let} \k{var} l = list.new(:E) \k{end}
      \k{let} empty(stack :T) :Bool = list.empty(stack.l)
      \k{let} push(element :E stack :T) :\k{Ok}= stack.l := list.cons(element stack.l)
      \k{let} pop(stack :T) :T = stack.l := list.tail(stack.l)
      \k{let} top(stack :T) :E = list.head(stack.l)
\k{end}
\end{xple}

In this case a new stack containing the integer 4 can be created by the 
following function calls:
\begin{xple}
  \k{let} intStack = listStack(:Int)
  \k{let} myStack = intStack.new()
  intStack.push(4 myStack)
\end{xple} 

\paragraph{Method-Based Encapsulation}

The\index{encapsulation, method-based ~}\index{programming, 
object-oriented ~}\index{object-oriented programming} third encapsulation 
technique binds functions to an internal, shared, mutable 
variable\index{shared variable}. The function signatures are defined by a 
tuple type. This type represents the type of a stack object.
\begin{xple}
\k{Let} StackObject (E $<:$\k{Ok}) =
   \k{Tuple}
      empty() :Bool
      push(element :E) :\k{Ok}
      pop() :\k{Ok}
      top() :E
   \k{end}
\end{xple}

An implementation of the stack functions is provided by a {\it 
new}-function that can be used to create "objects" of\index{object} this 
type. The implementation of their methods\index{method} are value 
components of these objects. In this implementation framework method 
overwriting\index{method overwriting} for subtype objects can also be 
realized (see \cite{Matt93}). For this reason this encapsulation method is 
called object-oriented in \cite{Matt93}. It avoids an opaque type and 
input parameters of this type\footnote{Operations expecting more than one 
input parameter of the opaque type lead to recursive type definitions when 
this implementation style is used\cite{Matt93}.}\index{recursive, ~ data 
type}.
 
\begin{xple}
\k{let} newStackObject(E $<:$\k{Ok}) :StackObject(E) =
   \k{begin}
      \k{let} \k{var} state = list.new(:E)
      \k{tuple}
         \k{let} empty() :Bool = list.empty(state)
         \k{let} push(element :E) :\k{Ok} = state := list.cons(element state)
         \k{let} pop() :\k{Ok} = state := list.tail(state)
         \k{let} top() :E = list.head(state)
      \k{end}
\k{end}
\end{xple}

For this realization variant the creation of an integer stack with the 
element 4 looks as follows:
\begin{xple}
  let myStack = newStackObject(:Int)
  myStack.push(4) 
\end{xple}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Programming in the Large}
\label{Abs. Programmierung im Grossen}

Besides function abstraction, modularization \index{modularization} is
the most important structuring facility in modern programming
languages. Large programs can be split into \e{interfaces} and
\e{modules} in \Tl. Moreover, it is possible to group interfaces and
modules into \e{libraries}.

These structuring mechanisms do not introduce new concepts for naming,
binding, or typing. They just restrict deliberately existing concepts of
\Tl\ \cite{Matt93}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Modules and Interfaces}
\label{Abs. Module und Schnittstellen}

Interfaces \index{interface}\index{{\bf interface}} define the signatures 
of exported\index{export}\index{{\bf export}} values, functions, types, 
and type operators. Interfaces, therefore, can be viewed as named tuple 
types containing references to explicitly imported\index{{\bf 
import}}\index{import, ~ed module}\index{import, ~ed interface} modules 
(e.g., \s{bool}) and interfaces visible in the global scope.  
 

\begin{xple}
    \k{interface} List
    \k{import} bool
    \k{export}
       T(E $<$:\k{Ok}) $<$:\k{Ok}
       \k{Let} AnyT = T(\k{Nok})
       error :\k{Exception}
       nil :AnyT
       cons, ::(E $<$:\k{Ok}  hd :E  tl :T(E)) :T(E)
       empty(E $<:$\k{Ok}  l :T(E)) :bool.T
       car(E $<:$\k{Ok}  l :T(E)) :E
       cdr(E $<:$\k{Ok}  l :T(E)) :T(E)
    \k{end}
\end{xple}

Interfaces can include type bindings (\s{AnyT}). The definition of these 
types is visible to all users of the interface. If such types are imported 
by other modules, the name of the interface as well as the name of the 
module
can be employed as qualifying identifier\index{qualifying identifier}.

A module\index{module}\index{{\bf module}} defines a tuple value 
aggregating bindings according to its interface. In \Tl, an arbitrary 
number of modules can exist for a single interface. 
 
\begin{xple}
    \k{module} list
    \k{import} bool
    \k{export}
       \k{Let} \k{Rec} T(E $<$:\k{Ok}) $<$:\k{Ok} =
          \k{Tuple} \k{case} nil  \k{case} cons \k{with} hd :E  tl :T(E) \k{end}
       \k{Let} AnyT = T(\k{Nok})
       \k{let} error = \k{exception} ''Empty list''
       \k{let} nil = \k{tuple} \k{case} nil \k{of} AnyT \k{end}
       \k{let} cons(E $<$:\k{Ok}  hd :E  tl :T(E)) :T(E) =
          \k{tuple} \k{case} cons \k{of} T(E) hd tl \k{end}
       \k{let} :: = cons
       \k{let} empty(E $<:$\k{Ok}  l :T(E)) :bool.T = l?nil
       \k{let} car(E $<:$\k{Ok}  l :T(E)) :E =
          \k{try} l!cons.hd \k{else} \k{raise} error \k{end}
       \k{let} cdr(E $<:$\k{Ok}  l :T(E)) :T(E) =
          \k{try} l!cons.tl \k{else} \k{raise} error \k{end}
    \k{end}
\end{xple}


Type bindings established in the interface (here \s{AnyT}) have to be 
repeated in the module. Modules and interfaces are \e{first-class} 
objects\index{first class object} of the language. They can be bound to 
identifiers and passed as parameters to functions. Modules and interfaces 
can be imported by other modules and interfaces employing the 
\k{import}-clause\index{import}. In the library a unique interface is 
assigned to every module name. 

Interfaces and modules\index{module, ~ definition}\index{interface, ~ 
definition} are definable on the \e{top level}\index{top level} of the 
interactive programming environment. Their definition implicitly generates 
persistent data structures describing the types of interfaces and the 
values of modules, respectively. 

After importing a module its components are referenced by the dot 
notation\index{dot notation}. 

\begin{xple}
    \k{module} main
    \k{import} list  print
    \k{export}
       \k{let} l = list.cons(3  list.nil)
       \k{let} l2 :list.AnyT = list.nil
       \k{if} not(list.empty(l)) \k{then}
          print.int(list.car(l))
       \k{end}
    \k{end}
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Libraries}
\label{Abs. Bibliotheken}

The rapidly growing number of modules in real systems and the necessity 
for tools supporting consistent system restructuring in persistent systems 
makes it necessary to organize modules and interfaces into 
libraries\index{library} and suggests the introduction of a library 
concept into the language \Tl. 

A library defines the scope of the names of its local modules and 
interfaces and supports the definition of subsystems encapsulating hidden 
modules and interfaces. 

The definition of the standard library\index{standard library}(\s{StdLib}) 
is presented as a simple example\index{{\bf library}}\index{{\bf with}}. 


\begin{xple}
    \k{library} StdLib
    \k{with}
       \k{interface}
          Bool Int Char Real ArrayOp
       \k{module}
          bool :Bool  int :Int  char :Char  real :Real  arrayOp :ArrayOp
       \k{interface}
          List
       \k{module}
          list :List
    \k{end}
\end{xple}

The order in which the names of the modules and interfaces are listed 
matters. Only modules and interfaces preceding the importing modules and 
interfaces in the library can be imported. As a consequence, cyclic 
dependencies\index{cyclic dependency} are ruled out. 
The modules of the standard library introduced in the previous example can 
be imported into a further library (\s{BulkLib}). 


\begin{xple}
    \k{library} BulkLib
    \k{import} arrayOp :ArrayOp  list :List  iter :Iter
    \k{with}
       \k{interface}
          Set Bag Assoc Dictionary VarList
       \k{module}
          linkedSet :Set  bitSet :Set  hashedSet :Set
       \k{module}
          bag :Bag  assoc :Assoc  dictionary :Dictionary
       \k{hide}
          varList :VarList
    \k{end}
\end{xple}

For this purpose, the libraries \s{StdLib} and \s{BulkLib} have to be 
defined in the following order as parts of an enclosing 
library\index{library, enclosing ~}.  

\begin{xple}
    \k{library} Root
    \k{with}
       \k{library}
          StdLib BulkLib
       \k{interface}
          Test
       \k{module}
          test :Test
    \k{end}
\end{xple}

The example of the library \s{BulkLib} illustrates two further facilities 
of the library concept of \Tl. Modules and interfaces can be 
hidden\index{module,  hidden ~}\index{interface, hidden ~} in the library 
employing the \k{hide}-clause\index{{\bf hide}}. Furthermore, it is 
possible to specify different modules (\s{linkedSet}, \s{bitSet}, and 
\s{hashedSet}) for a single interface  (\s{Set}).

\Tl\ supports hierarchic library structures\index{library, hierarchic ~ 
structuring}, but the names of all modules, interfaces and libraries 
inside of a library have to be unique. This is also true for components 
defined as hidden. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Persistence and Garbage Collection}
\label{Abs. Persistenz und Freispeicherverwaltung}

In \T\, no linguistic difference between \e{persistent}\index{persistent
data} and \e{temporary} data is made. Every object can be made
persistent. Persistence is defined by
\e{reachability}\index{reachability} either from a linked library module
or from a local name space of a user (\e{top
level})\index{persistence}. This persistence concept works for values,
functions, and (dynamic) type bindings.

Consistent states of the object store\index{object store} are marked by
explicitly stabilizing\index{object store, ~ stabilizing} the object
store. The module \s{store} provides the function \s{stabilise} for this
purpose. A call of this function stabilizes the actual state of the
object store.

\begin{xple}
    \k{import} store;
    store.stabilise();
\end{xple}
    
The operation \s{store.stabilise} generates a 
\e{checkpoint}\index{checkpoint}.  If a user quits the session with the 
command \s{\k{do exit}} or if a system crash occurs, all changes of objects 
in the persistent store performed after the checkpoint are undone 
(\e{rollback}\index{rollback}).  At the beginning of the next session the 
object store is in the state of the last checkpoint.  Furthermore, it is 
possible to rollback explicitly to the state of the last checkpoint without 
leaving the system.  This is accomplished by the function \s{restart} which 
is also exported by the module \s{store}.  The effect of the functions 
\s{stabilise} and \s{restart} is illustrated by the following example.

\begin{xple}
    \k{import} store list;
    \k{let var} l = list.nil
    l := list.cons(1 l)
    l := list.cons(2 l)
    store.stabilise();
    (* object store with list l containing elements 1 and 2 is stabilized *)
 
    l := list.cons(3 l)
    store.restart();
    (* rollback to last checkpoint; insertion of 3 into l is undone *)

    list.car(l);
    \r 2
\end{xple}

Objects that are no longer reachable are automatically deleted from the 
object store by a \e{garbage collector}\index{garbage collector}. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{External C Libraries}
\label{Sec. External C Libraries}

\T\ provides a bidirectional\index{external library}
\index{library, external ~}\index{library, C ~} programming interface 
between \Tl\ and C\index{C}\index{C library} that
features a seamless integration of both languages' function paradigms.
External C functions can be integrated into \Tl\ as ordinary function
values. \Tl\ functions can be wrapped in a way that makes it possible 
to use them directly as C function pointers.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Function Calls from Tycoon to External C Libraries}
\label{Sec. Function Calls from Tycoon to External C Libraries}

\T\ provides a generic mechanism to use system functionality implemented 
in 
external languages\index{external language}. The binding of \Tl\ 
identifiers to external function\index{external function}\index{function, 
external ~} values is achieved by the predefined function \s{bind}. 
This function has the following signature:

\begin{xple}
    bind(Function $<$:\k{Ok}  library, label, format :String) :Function
\end{xple}

The parameters of the \s{bind} function have the following meaning:
\s{Function} describes the type of the resulting \Tl\ function. It has to
be of the form \s{\k{Fun}(\dots) :A}. The \s{library} parameter is a string
that identifies the library file that contains the required external 
C\index{C function} function. This can either be the full path 
name\footnote{If the same shared library is referenced several times the 
path should always be exactly the same. Otherwise the dynamic linker loads 
several instances of the shared object. This means not only consuming more 
process memory than necessary,
but leads to subtle bugs when global C variables are defined multiple times
in the same process.} of a dynamic library or the string result of one of
the functions exported by the module \s{runtimeCore} (see the following 
table) belonging to the \T\ library \s{stdenv}. 

\begin{center}
  \begin{tabular}{|l|l|}
    \hline
    \bold{Function} & \bold{Description} \\
    \hline
    \s{library}         & identifies the core of the \T\ runtime system \\
    \s{cLibrary}        & identifies the standard C library \\
    \s{dynamicLibrary}  & identifies dynamically bound libraries \\
    \s{staticLibrary}   & identifies statically bound libraries \\
    \hline
  \end{tabular}
\end{center}

The \s{label} parameter is a string that contains the original C source
text name of the C function. The \s{format} parameter is a string that
specifies the assumed parameter format\index{parameter format} of the 
C function. Every single character of this string corresponds to one 
parameter. 
It specifies the
conversions between tagged and untagged data representations to happen
before and after a call. The parameter order is \e{from left to right} like
in C, except for the function result type. It is given by the last
character which is mandatory. The following table contains the set of
characters that denote parameter formats.

\begin{center}
  \begin{tabular}{|l|l|l|l|}
    \hline
    \bold{Format} & \bold{TL type} & \bold{C type} & \bold{Description} \\
    \hline
    \s{i}  & \s{Int}        & \k{long}      & integer number \\
    \s{r}  & \s{Real}       & \k{double}    & floating point number \\
    \s{c}  & \s{Char}       & \k{char}      & ASCII character \\
    \s{b}  & \s{Bool}       & \k{long}      & boolean value (see text) \\
    \s{s}  & \s{String}     & \k{char} *    & zero-terminated string \\
    \s{v}  & \k{Ok}         & \k{void}      & return value only \\
    \s{=}  & \s{$<$:}\k{Ok} & \k{void} *    & \T\ value, no conversion \\
    \s{w}  & \s{word.T}     & \k{void} *    & 32-bit word \\
    \hline
  \end{tabular}
\end{center}

There is no predefined type for boolean values in C. Boolean \Tl\ values 
are
converted to C long values as follows.

\begin{xple}
    true   $\rightarrow$   1
    false   $\rightarrow$   0
\end{xple}

A C value x produces the following \Tl\ boolean values:

\begin{xple}
    x != 0   $\rightarrow$   true
    x == 0   $\rightarrow$   false
\end{xple}

When \s{s} is used as a format character for a string parameter,
every call is enclosed by automatic fix and unfix operations for the 
argument.
The result of the fix operation, a main memory pointer is passed to C.
The latter refers to a valid C string,
because all \T\ strings are represented with zero-termination.

Used in return value position the format character \s{s} causes
strings returned from C to be copied into newly created store objects 
(\e{copy-out})\index{copy-out}.

Suppose a library \s{/usr/lib/libexample.so} contains a function 
\s{example} that takes a string argument and returns a 32 bit integer
number. Thus, \s{example} is assumed to match the following 
declaration:

\begin{xple}
    \k{extern} \k{long} example(\k{char} *s);
\end{xple}

An appropriate binding for \s{example} in \Tl\ is:
 
\begin{xple}
    \k{let} cCallExample =
       bind(:\k{Fun}(:String) :Int  ''/usr/lib/libexample.so''  ''example''  ''si'')
\end{xple}

The value \s{cCallExample} has the type \s{\k{Fun}(:String) :Int}. 
Therefore, the C function can be called as follows.

\begin{xple}
    \k{let} result :Int = cCallExample(''My favorite String'')
\end{xple}

Note that external bindings are persistent and portable across host
architectures. For example, if the value \s{cCallExample} is transferred
with \s{dynamic.extern}/\s{intern}, the C binding would be reestablished
automatically.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Function Calls from External C Libraries to Tycoon}
\label{Sec. Function Calls from External C Libraries to Tycoon}

The programming interface between \Tl\ and C is bidirectional. It is not
only possible to call C functions from \Tl, but also to \e{call back} from
C to \Tl.

In order to minimize the programming effort for callbacks \index{callback} 
on the C side, it is desirable to make \Tl\ functions appear like ordinary 
C function pointers. Moreover, this is indispensable in situations where 
an 
external software component requires C callbacks but cannot be changed.

The module \s{cCallback} exports an abstract type \s{cCallback.T} which
represents C function pointers that refer to callbacks. The creation
function for values of type \s{cCallback.T} has the following signature:

\begin{xple}
    new(Function $<$:\k{Ok}  function :Function  format :String) :callback.T(Function)
\end{xple}

The first value argument (\s{function}) of \s{new} must always be a 
function, although this restriction is not checked. Nevertheless, the
function's signature has to be mirrored in the \s{format} string that
specifies how C arguments of the resulting callback are converted into \Tl\
values. Every single character of the string corresponds to one parameter.
The parameter order is \e{from left to right} like in C, except for the
function result type which is given by the last character. The latter is
mandatory. The format characters are shown in the table in section 
\ref{Sec. Function Calls from Tycoon to External C Libraries}.

If the format character \s{s} is used for a parameter, a C string argument
will be copied into a newly created store object 
(\e{copy-in}\index{copy-in}). 
In case of a return value, a C string is copied into a chunk of memory 
allocated by \s{malloc}. Hence the parameter passing semantics are 
\e{copy-out\index{copy-out}} instead of \e{by reference}\index{call by 
reference} 
which apply for strings within C only.

The format character \s{v} specifies a function result value of \k{ok}
irrespective of the actual C value returned by C.

For parameters with format code \s{w} a \Tl\ type that
is equivalent to \s{word.T} or to an instance of \s{word.Handle} must be 
used.
In particular callbacks conform to \s{word.Handle},
because \s{cCallback.T} $<:$ \s{word.Handle}.

A simple example follows:

\begin{xple}
    \k{import} cCallback fmt

    \k{let} myMessage(n :Int  r :Real) :String =
       fmt.int(n) $<>$ '' = '' $<>$ fmt.real(r)

    \k{let} myMessageCallback =
       cCallback.new(myMessage  ''irs'')

    \k{let} test =
       bind(:\k{Fun}(n :Int  messageCallback :cCallback.T) :\k{Ok}
         ''.../example.so.1.0''  ''test''  ''iwv'')
 
    test(2  myMessageCallback)
\end{xple}

The resulting console output would be

\begin{xple}
     ''pi * 2 = 6.28''
     \k{ok}
\end{xple}

assuming that the corresponding C program \s{\dots{}/example.c} looks like 
this:

\begin{xple}
    \#include $<$stdio.h$>$

    \k{void} test(\k{long} n, \k{char} *message(\k{long} n, \k{double} r))
    \{
      printf(''pi * \%s$\backslash$n'', message(n, n * 3.14));
    \}
\end{xple}

As callbacks can be transferred to address spaces which are not under
control of the \T\ system, there is in general no way to determine their
temporal extent automatically. Callbacks are never persistent.
Callbacks occupy some memory resources that can only be released
explicitly:

\begin{xple}
    cCallback.free(myMessageCallback)
\end{xple}

After freeing a callback it is invalid. Any subsequent usage is most likely
to cause strange system behavior (e.g. crashes). Attentive readers may
have noticed some more problems in the example: In what manner does the
result string of the function \s{message} get allocated on the C side 
before it is passed to \s{printf}, who is in charge of releasing its memory
and how can this be done?

The current solution is that the format character \s{s} in a return value
position causes the allocation of an appropriate memory block by calling
\s{malloc}. This block has to be released by the C programmer by a call to
\s{free}. Thus, the C program in the example should be written as follows:

\begin{xple}
    \#include $<$stdio.h$>$
    \#include $<$malloc.h$>$

    \k{void} test(\k{long} n, \k{char} *message(\k{long} n, \k{double} r))
    \{
      \k{char} *p;

      p = message(n, n * 3.14);
      printf(''pi * \%s$\backslash$n'', p);
      free(p);
    \}
\end{xple}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Layout and Naming Conventions}
\label{Sec. Layout and Naming Conventions}

Common formatting\index{formatting convention}\index{naming 
convention}\index{layout convention}\index{convention} conventions are 
worth a lot, especially when several
people work together on large projects. In addition to the communication
inefficiencies caused by differing conventions, newcomers to a programming
language often spend a significant amount of time incrementally developing
and retrofitting their own style, usually re-learning what turn out to be
simple lessons that others have already learned. While this is not always
wasteful, it is clearly worthwhile to have a good set of guidelines at
hand, if only for reference. Also adherence to common conventions makes
automatic formatting tools easier to provide and more useful \cite{RLW85}.

This section offers a complete set of conventions for formatting
\Tl\ modules and interfaces. Such conventions address indentation,
capitalization, punctuation, comments, etc. The following points of style
produce a visually pleasing program. Consistently applied, they also
provide syntactic cues to semantics that make a program easier to read.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Spelling}
\label{Sec. Spelling}

Identifiers\index{spelling} that name \e{values} (e.g.\ variables, 
functions, modules and
exceptions) start with a lower-case character and identifiers that name
\e{types} (e.g.\ type operators and interfaces) start with an upper-case
character. All following characters are entirely lower case, except for 
composed identifiers. Each first character of a subcomponent is 
capitalized\index{capitalization} (e.g.\ \s{longNameForAValue}).

Reserved keywords that are used in \e{value contexts} are entirely
lower-case and keywords that are used in \e{type contexts} start with an
upper-case character.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Punctuation}
\label{Sec. Punctuation}

A space\index{punctuation}\index{space} (\verb*| |) appears before and 
after a binary operator in infix 
notation and in a \k{let}-binding or destructive assignment.

\begin{xple}
    3\verb*| |+\verb*| |4  ''con''\verb*| |$<>$\verb*| |''cat''
    \k{let} a\verb*| |=\verb*| |3
    a\verb*| |:=\verb*| |5
\end{xple}

A space appears before but not after a colon or a subtype sign.

\begin{xple}
    \k{let} p\verb*| |:Person = \dots
    \k{let} n\verb*| |$<$:Ok = \dots
\end{xple}

A space appears after but not before a comma or a semicolon.

\begin{xple}
    add(x,\verb*| |y :Int) = \dots 
    \k{module} \dots \k{end};
\end{xple}

A space appears neither before nor after a point, a question-mark or
an exclamation-mark.

\begin{xple}
    person.name
    address?national
    address!national
\end{xple}

Except as required by adjacent tokens, no spaces appear before or after
left and right parenthesis, left and right square brackets and left and
right curly brackets.

\begin{xple}
    fac(3)  get(peter).name
    a[3]  p[3].name
    \{3 + 4\}
\end{xple}

Two spaces appears between two signatures, e.g.\ in function or tuple
signatures. Two spaces also appears between \k{let}-bindings function
applications or tuple fields.

\begin{xple}
    get(E $<$:\k{Ok}\verb*|  |coll :T(E)\verb*|  |index :Int) :E
    \k{Tuple} name :String\verb*|  |age :Int \k{end}
    f(\k{let} x = 2\verb*|  |\k{let} y = 7)
    \k{tuple} \k{let} a = 6\verb*|  |\k{let} b = ''hallo'' \k{end}
\end{xple}

A single space appears between actual parameters in function
applications and between tuple fields (anonymous bindings).

\begin{xple}
    get(:Person\verb*| |persons\verb*| |7)
    \k{tuple} ''Peter''\verb*| |29 \k{end}
    \k{array} 1\verb*| |2\verb*| |3 \k{end}
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Indentation}
\label{Sec. Indentation}

Indenting\index{indentation} is used to emphasize program structure. Each 
nesting level\index{nesting level} is
two spaces wide. A binding or signature sequence is indented under the
construct that introduces it. For example:
\begin{xple}
    \k{let} t = 
       \k{tuple}
          \k{let} name = ''Peter''
          \k{let} age = 3
       \k{end}
    \k{Let} Person = 
       \k{Tuple}
          name :String
          age :Int
       \k{end}
    \k{if} bool \k{then}
       ss
    \k{elsif} bool \k{then}
       ss
    \k{else}
       ss
    \k{end}
\end{xple}

Function signatures and function parameter lists that do not fit on a 
single
line are split element-wise across separate lines. Subsequent lines are
indented one nesting level, for example:
\begin{xple}
    \k{let} newSubWindowWithTitle(window :window.T
       title :String
       windowOptions :window.Options)
    newSubWindowWithTitle(longExpressionWithManyArguments
       longExpressionWithManyArguments
       longExpressionWithManyArguments)
\end{xple}

These forms only apply to constructs that do not fit on a single line.
For example, if the statement sequence following a \k{then} or \k{else}
fits on a single line, it can appear on the same line with the tokens
that introduce and terminate it. Similarly, if the statement sequence of
a loop body is short, it can be moved up to the line that introduces the
loop, along with the trailing \k{end}.

\begin{xple}
    \k{if} z $>$ 10 \k{then} x := z  y := z \k{end}
    \k{for} i = 1 \k{upto} 10 \k{do} a[i] := 0 \k{end}
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Comments}
\label{Sec. Comments}

The text of a multiline comment\index{comment}\index{multiline 
comment}\index{comment, multiline ~} begins on the same line as the opening
left-comment. Subsequent lines are indented the same as the first word
of the comment. The terminating right-comment appears on the last line of
the comment.

\begin{xple}
    (* A comment that fits entirely on one line by itself. *)

    (* A long comment that does not fit on one line. A long
        comment that does not fit on one line. A long comment
        that does not fit on one line. *)
\end{xple}

By convention, comments which refer to a group of items appear before the
group. Comments associated with a single definition or declaration appear
immediately after it. This comments starts at the same indentation level
as the definition or declaration begins.

\begin{xple}
    \dots
    (* Exceptions:
        This is a comment for a group of items. *)
 
    error, overflow :\k{Exception} \k{with} data :Int \k{end}
    (* Standard exceptions. *)
   
    test :\k{Exception}    (* Only for debugging. *)
    \dots
\end{xple}

Interfaces\index{comment, interface ~}\index{interface, ~ comment} and 
modules\index{comment, module ~}\index{module, ~ comment} have a multiline 
comment with predefined fields.
This comment is placed immediately after the interface respectively the
module name. It is used to give some initial information about the 
contents.
The terminating right-comment stands on a separate line.

\begin{xple}
    \k{interface} Editor
    (* System:  editenv
       File:       Editor.ti
       Author:   Florian Matthes, Sven Muessig
       Date:      02-dec-91
       Purpose:  Generic data editor and browser.
    *)
    \k{import}
       \dots
    \k{export}
       \dots
    \k{end}
\end{xple}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\appendix
\include{tiAppendix}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bibliographystyle{florian}
\addcontentsline{toc}{section}{Bibliography}

\bibliography{dbis-macros,florian}

\addcontentsline{toc}{section}{Index}
\input{tiIndex}

\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% End Of Text                                                        %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
