% File:    edbt98.tex
% Author:  AW, FM
% Purpose: Submission to EDBT'98
% Date:    14.Sept.1997
%          needs florian.bib
%
\documentclass[a4paper]{article}
\usepackage{a4}        % use full A4 paper size
\usepackage{epsfig}    % support EPS figures
\usepackage{sts}       % defines \p, \e, \xple ...
\usepackage{sts-named-e} % support long citations as used by 'sts-named.bst'

\newcommand{\tag}[1]{{\tt $<$#1$>$}}

\begin{document}

\title{Visualizing Persistent Objects using\\ Higher-Order Functions in SGML}

\author{Florian Matthes \and Axel Wienberg}

\date{\small AB 4-022 Software Systems\\
Technical University Hamburg-Harburg\\
D-21071 Hamburg, Germany\\
\{f.matthes,ax.wienberg\}@tu-harburg.de}

\maketitle

\begin{abstract} \noindent
  We describe a novel approach for the visualization of persistent objects
  based on an orthogonal extension of SGML by variables, conditionals, function
  abstraction and function application. This enables a seamless integration
  with persistent languages and makes this approach particularly well-suited
  for the presentation of bulk data structures on various media.
  
  After a definition of the syntax, evaluation semantics and type rules of
  this model, we present the implementation and use of the Structured Tycoon
  Markup Language (STML), a specific example of the model applied to the
  polymorphic, strongly-typed persistent object-oriented programming language
  Tycoon-2.
\end{abstract}

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

\section{Motivation and Overview}
\label{Sec:Intro}

An information system comprises database, application, and presentation services which tend to be realized using distinct technologies (database systems, programming languages, GUI toolkits) and which can be distributed over the network based on a client/server architecture as shown in the example of Figure~\ref{Fig:ThreeTier}.

Significant progress has been made in the last decade to overcome the impedance mismatch \cite{CoMa84} between the database and the application services through the development of object-oriented databases \cite{Catt94}, database programming languages \cite{ScMa94} and persistent programming systems \cite{AtMo95}. 

Moreover, virtually all database products today are equipped with graphical GUI design tools, report generators and mail merge tools to bridge the other gap, namely between presentation and application services. These tools help to visualize and pretty-print database objects on diverse windowing systems and output media like text files, postscript printers, e-mail messages or Word documents.

\begin{figure}[htb]
\centerline{\epsfxsize=\textwidth \epsfbox{threetier.ps}}
\caption{SGML-based visualization of persistent objects over the Internet}
\label{Fig:ThreeTier}
\end{figure}

In this paper, we report on an alternative approach to simplify the presentation of complex persistent objects which is based on SGML as an open, platform-independent and highly popular standard to describe the content and the layout of text documents. The rationale of our work is to make use of the rich toolbox of SGML-based browsers, parsers, editors, etc.\ by a (fully orthogonal and compatible) extension of SGML with a minimum set of dynamic concepts necessary to generate SGML documents based on the content of persistent objects in relational databases, text-retrieval engines, directory services, file systems, etc. (compare Figure~\ref{Fig:ThreeTier}).

Given a particular application language $A$ (e.g., Persistent C++), and a particular structured presentation language $P$ (e.g., HTML), defined through its SGML document type definition, our approach can be summarized as follows:

\begin{enumerate}
\item A document type definition $P_A$ is created by extending $P$ by SGML elements for variables, conditionals, function abstraction and function application based on expressions of $A$. The document type definition $P_A$ is used by standard SGML tools to assist application programmers in building and maintaining $P_A$ documents which define presentation services with embedded (bi-directional) bindings to typed application and/or database objects.

\item A $P_A$ processor is implemented that checks $P_A$ documents for type-correctness and translates them into executable code of $A$. In particular, this processor ensures that the generated code will at run-time produce documents which conform to $P$.

\item At run-time, a small library implements the type-safe binding from the generated code written in $A$ to application and to database objects. 
\end{enumerate}

After a brief introduction to SGML in Section~\ref{Sec:SGML}, we describe how to extend SGML by first-class functions (Section~\ref{Sec:STML}). Section~\ref{Sec:Integration} gives some insight into the expressiveness of the model by presenting a particular implementation of this model for the persistent, object-oriented programming language Tycoon-2 ($A$) and for HTML ($P$). As of September 1997, there are several commercial Web sites of newspapers in Germany which utilize the resulting language $P_A$ (called STML, the Structured Tycoon Markup Language) on a daily basis to provide customer-oriented information services on the Internet via HTML front-ends \cite{HOX97}. The paper ends with a comparison of our approach with related academic and commercial models for the generation of structured documents based on database contents (Section~\ref{Sec:RelatedWork}).

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

\section{Understanding SGML}
\label{Sec:SGML}

This section explains the basic SGML concepts necessary to understand how structured persistent objects and higher-order functions fit into SGML's document model. 

The Structured General Markup Language (SGML) \cite{ISO8879,Gold91,Herw94} is an international standard for content- as well as layout-based structuring and annotation of text documents.  It has found widespread acceptance in areas such as electronic publishing and digital libraries, with its most popular application being the HTML language(s) used in the World Wide Web.

\begin{xple}
$<$!DOCTYPE HTML PUBLIC "-//W3C/DTD HTML 3.2 Final//EN"$>$
$<$HTML$>$ $<$HEAD$>$ $<$TITLE$>$Sample SGML document$<$/TITLE$>$
$<$BODY$>$ \ldots $<$IMG SRC="sgml.gif"$>$ \ldots $<$/HTML$>$
\end{xple}
This sample document illustrates that every SGML document consists of a reference to its underlying document type definition (DTD, in this case HTML release 3.2), and a document instance (in this case a title and a body with a nested reference to an embedded image). 

A document instance relates to its DTD like a database instance relates to a database schema, filling the structure (nested types) defined in the DTD with actual values.  The document text is annotated with start tags and end tags, denoting the range of an element.  Tags are enclosed in angle brackets, with an initial slash indicating an end tag.  Start tags can contain additional attributes applying to the occurrence of the element, specified as a sequence of \p{name=value} pairs (e.g., \p{SRC="sgml.gif"}).  The document instance can contain entity references that are substituted with previously defined, potentially long strings by the SGML parser. References to so-called external entities allow the inclusion of other documents.

A specific DTD defines the elements and their attributes that can be used to structure the document instances, as shown in the following excerpt from the HTML DTD:
\begin{xple}
$<$!ELEMENT HTML O O (HEAD, BODY)$>$
$<$!ELEMENT HEAD O O (TITLE \& ISINDEX? \& BASE?)  +(META$|$LINK)$>$
$<$!ELEMENT TITLE -- -- (\#PCDATA)*$>$
\ldots
$<$!ELEMENT IMG -- O EMPTY$>$

$<$!ATTLIST IMG
        SRC CDATA \#REQUIRED

        ALT CDATA \#IMPLIED
        \ldots$>$
\ldots
\end{xple}
Every element has a name (\p{HTML, HEAD, TITLE, IMG, \ldots}) and a content model, declaring the set and order of elements that may appear inside.  This defines a context-free grammar for the logical structure of the document instances. For example, the element \p{HTML} consists of a \p{HEAD} followed by a \p{BODY}.

Since SGML is intended to be written by hand, it contains a number of
abbreviation (minimization) features which are also specified as part of the DTD. Opening and closing tags may be declared optional by using the letter \p{O} instead of the dash (--) in an element definition. The first and second letter refer to the opening and closing tag, respectively. Omitted tags are inferred by the SGML parser based on the content model.  When an attribute takes only an enumerated set of values, the attribute name is inferred from the value, and may be omitted.  These two features and the context-sensitive whitespace handling preclude a correct parsing of a document instance without knowledge of
its underlying DTD.\footnote{For this reason, the XML standard currently being developed by the W3 consortium does not support minimization.  XML is a restricted variant of SGML that may become the ``next HTML''.  As a basis for our model, it would be just as suitable as SGML.}

The interpretation and presentation of an SGML document lies outside the scope
of the SGML standard.  Documents may be typeset as books or manuals, published as hypertext, or the markup may be used for content-based text retrieval. 

Several authors (see, e.g.,  \cite{Abit97} for further references) have already explored a bi-directional mapping between (semi-) structured persistent objects and linear SGML text documents based on the following (rough) correspondence table:
\begin{center}
\begin{tabular}{|l|l|}
\hline
{\bf SGML Concept}       & {\bf Data Modeling / Typing Concept}  \\
\hline
document type definition & database schema / type definition \\
document instance        & complex object / typed value \\
sequence of (attributed) elements & record type definition \\
repetition of elements   & list type definition \\
choice between elements  & union type definition \\
optional element / attribute & type with null value \\
predefined element       & domain / base type \\
nesting of elements      & nested type definition \\
recusion in DTD          & recursive type definition \\
external element         & reference type definition \\
\hline
\end{tabular}
\end{center}
Our contribution complements their work by providing programmers with a structured, type-safe model to define both, the (rather static) overall layout and repeating elements of the documents to be generated and also the (possibly deeply nested) bindings to queries and expressions which extract persistent data from the database and embed them into the result document.

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

\section{Extending SGML with First-Class Functions}
\label{Sec:STML}

In our model, an SGML fragment is viewed as an expression that returns a value. All static document elements (described using tags of the non-extended DTD) are treated as literals, that is, they return themselves. Dynamic document elements may contain variables, conditionals, function abstractions and function applications which interact smoothly with the corresponding concepts of the application language. As a consequence, all visual elements of an application can be defined in SGML documents, cleanly separating presentation and application concerns.

In order to simplify the presentation, our examples make use of STML (Structured Tycoon Markup Language), the extension of SGML with expressions of the application language Tycoon-2. However, as described in Section~\ref{Sec:Integration}, any  higher-order or object-oriented language (Lisp, Standard ML, Java, C++, OQL) could be used instead of Tycoon-2. 

We first illustrate the use of STML by examples before we define its syntax, evaluation semantics and type rules. 

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

\subsection{Examples of STML Code}

In STML, a function abstraction allows a programmer to turn an arbitrary STML fragment into a function by enclosing it with the \p{$<$fun$>$} tag. The (optional) \p{param} attribute of that tag describes the list of typed formal parameters of the function:\footnote{In this example, all arguments are declared to be (long) strings of type \p{Sgml}. A more realistic example would utilize a single parameter of the type \p{Employee} declared as a class in Tycoon-2.}
\begin{xple}
$<$define name=formatEmployee$>$
  $<$fun param='lastName :Sgml, sex :Sgml, age :Sgml'$>$
     \texttt{$<$P$>$}$<$if true='sex="m"'$>$\texttt{Mr.}$<$else$>$\texttt{Mrs.}$<$/if$>$
     $<$ref name=lastName$>$ \texttt{$<$I$>$(}$<$ref name=age$>$\texttt{)$<$/I$>$}
  $<$/fun$>$
$<$/define$>$
\end{xple}
A \p{$<$define$>$} tag introduces a named variable which is bound to the value enclosed by the tag. This value can be an SGML fragment or a (higher-order) STML function. The scope of the variable declaration is the text following the tag within the enclosing sequence (see~Section~\ref{Sec:Semantics}). A \p{$<$ref$>$} tag gives access to the actual value of a variable in the current lexical scope. 

In the example above, the identifier \p{formatEmployee} is bound to a function for formatting the information about an employee.  The gaps in this template are explicitly named and declared; the remaining SGML is checked for well-formedness independent of the actual arguments (for example, the correct balancing of the \tag{I} tag is verified by the parser).  

By applying the function, the template can be instantiated repeatedly.  This can be done within an STML document using the \p{$<$apply$>$} tag, with the potential benefit of centralizing layout decisions.
\begin{xple}
\texttt{$<$P$>$Our employees:}
$<$apply name=formatEmployee$><$arg$>$\texttt{Maier}$<$arg$>$\texttt{f}$<$arg$>$\texttt{39}$<$/apply$>$
$<$apply name=formatEmployee$><$arg$>$\texttt{Smith}$<$arg$>$\texttt{m}$<$arg$>$\texttt{36}$<$/apply$>$
\end{xple}
This example produces the following output:
\begin{xple}
\texttt{$<$P$>$Our employees:}
\texttt{$<$P$>$Mrs. Maier $<$I$>$(39)$<$/I$>$}
\texttt{$<$P$>$Mr. Smith $<$I$>$(36)$<$/I$>$}
\end{xple}
More interestingly, the STML function can be applied to persistent data by passing the function as an argument to a method (\p{forEachEmployee}) of an application object (\p{project}):
\begin{xple}
\texttt{$<$P$>$Our employees:}
$<$send receiver=project selector=forEachEmployee$>$
  $<$arg$><$ref name=formatEmployee$>$
$<$/send$>$
\end{xple}
Please note the separation between application logic (how iterations are implemented) and presentation details (how persons should be visualized).
 
Since STML functions and SGML values are treated uniformly, statically nested and anonymous functions can be defined as illustrated in the following example which traverses a nested collection. The variable \p{p} of the outer function is bound iteratively to each element of the collection object \p{projects}. The variable \p{p} is then used as the receiver for a nested iterator method to enumerate all employees of that project.
\begin{xple}
$<$send receiver='application.projects' selector=forEach$>$
  $<$arg$><$fun param='p :Project'$>$
   \texttt{$<$H1$><$A NAME='`}p.name\texttt{`'$>$}\texttt{Project} $<$eval$>$out.writeString(p.name)$<$/eval$>$\texttt{$<$/A$><$/H1$>$}
    \texttt{$<$UL$>$}
      $<$send receiver=p selector=forEachEmployee$>$
         $<$arg$><$fun param='e :Employee'$>$
           \texttt{$<$LI$>$} \ldots
         $<$/fun$>$
      $<$/send$>$
    \texttt{$<$/UL$>$}$<$/fun$>$
$<$/send$>$
\end{xple}
The \p{p} argument passed to the STML function is in fact an object of the application programming language.  Though the STML text cannot manipulate it directly, the object can be passed in a type-safe way to application objects. The \p{$<$eval$>$} tag encloses source code of the application language which has access to all (typed) variables in its lexical scope.

As indicated by these examples, operations on bulk structures are expressed by iterators of the target language using higher-order functions. These iterators work uniformly over multiple bulk structures (sets, lists, bags) and exceed the expressive power of relational query languages (compare \cite{MaSc91b,Fega94,BTBN91,GaMa96b}).

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

\subsection{Syntax of STML}
\label{Sec:Syntax}

Syntactically, STML is defined by augmenting a given ``client'' DTD (e.g., HTML 3.2) with the element definitions shown in Figure~\ref{Fig:STML-DTD}. The definition of the element \p{STML} in the last line of Figure~\ref{Fig:STML-DTD} \e{includes} the additional elements \p{define}, \p{ref}, \ldots, and \p{eval} into the original content model with the root element named \p{\%client.base}. Inclusion is an idiosyncratic SGML feature which allows the included elements to appear floating anywhere inside the element for which the inclusion was defined.  In this case, the scope of the extension is the entire document instance.

The syntax of the additional STML elements is expressed entirely in SGML. For example, the \p{apply} element is defined to consists of a list of \p{arg} elements.

As a consequence, STML documents conform to a clearly defined DTD and can be created, edited and maintained with standard SGML tools. 

The DTD contains references to the entities \p{\%stml.ident}, \p{\%stml.param}, \p{\%stml.type}, and \p{\%stml.expression}, denoting identifiers, signatures, types and expressions of the application programming language, respectively.  In SGML, they are viewed as uninterpreted strings. If these strings consist of alphanumeric characters only, enclosing quotation marks can be omitted. Syntax and type errors in these strings are detected by the compiler of the target language as soon as an STML document is compiled.

\newsavebox{\stmlDtd}
\begin{lrbox}{\stmlDtd}
\begin{minipage}{\linewidth}
\begin{xple}
\begin{tabbing}
wwwwwwwww\=wwwwwwwwwwwwwww\=wwwwwwwwww\=  \kill
$<$!ENTITY \% stml.ident "CDATA"$>$
\\$<$!ENTITY \% stml.param "CDATA"$>$
\\$<$!ENTITY \% stml.type "CDATA"$>$
\\$<$!ENTITY \% stml.expression "CDATA"$>$
\\
\\$<$!ELEMENT define - - \%client.any$>$
\\$<$!ATTLIST define                     \>\>\>-- variable declaration --
\\        name \>\%stml.ident \>\#REQUIRED   \>-- name of this variable --
\\        type \>\%stml.type  'Sgml' \>\#IMPLIED \>-- type of this variable --$>$
\\$<$!ELEMENT ref - O EMPTY$>$
\\$<$!ATTLIST ref
\\        name \>\%stml.ident   \>\#REQUIRED \>-- name of referenced variable --$>$
\\$<$!ELEMENT assign - O \%client.any$>$
\\$<$!ATTLIST assign
\\        name \>\%stml.ident   \>\#REQUIRED \>-- name of assigned variable --$>$
\\$<$!ELEMENT fun - O \%client.any$>$
\\$<$!ATTLIST fun
\\        param \>\%stml.param  \>\#IMPLIED \>-- parameter list --
\\        type  \>\%stml.type   \>\#IMPLIED \>-- result type --$>$
\\$<$!ELEMENT apply - - (arg*)$>$
\\$<$!ATTLIST apply
\\        name  \>\%stml.ident   \>\#REQUIRED \>-- name of function --$>$
\\$<$!ELEMENT arg - O (\%client.any)$>$
\\$<$!ELEMENT if - - (\%client.any, elseif*, else?)$>$
\\$<$!ATTLIST if
\\        true \>\%stml.expression \>\#REQUIRED \>-- predicate --$>$
\\$<$!ELEMENT elseif - O \%client.any$>$
\\$<$!ATTLIST elseif
\\        true \>\%stml.expression \>\#REQUIRED \>-- predicate --$>$
\\$<$!ELEMENT else - O \%client.any$>$
\\$<$!ELEMENT send - - (arg*)$>$
\\$<$!ATTLIST send
\\        selector \>\%stml.ident \>\#REQUIRED \>-- method selector --
\\        receiver \>\%stml.expression  'self' \>\>-- receiver expression --$>$
\\$<$!ELEMENT eval - - \%stml.expression$>$
\\$<$!ATTLIST eval
\\        type \>\%stml.type   'Sgml' \>\#IMPLIED \>-- result type --$>$
\\
\\$<$!ELEMENT STML O O  (\%client.base) 
\\        +(define $|$ ref $|$ assign $|$ fun $|$ apply $|$ if $|$ send $|$ eval)$>$
\end{tabbing}
\end{xple}
\end{minipage}
\end{lrbox}

\begin{figure}[htbp]
  \fbox{\usebox{\stmlDtd}}
  \caption{STML element definitions}
  \label{Fig:STML-DTD}
\end{figure}

%-----------------------------------------------------------------------------
\subsection{Evaluation Semantics of STML}
\label{Sec:Semantics}

There are three kinds of values that can be returned by an STML expression:
\begin{itemize}
\item a well-formed SGML text,
\item a function mapping STML values to an STML value, with possible
side effects on the store, and
\item an arbitrary value of the application programming language.
\end{itemize}

Text that contains no markup evaluates to itself.  Client DTD elements
evaluate to the concatenation of their opening tag, the evaluation result of
all subexpressions, and their closing tag.  As a result, SGML text that
contains no STML elements is self-evaluating.

STML expressions in a \p{\%client.any} sequence and in an argument list are
evaluated in a strict left-to-right order.  Evaluation takes place in a dynamic
environment mapping variable names to store locations.  If at least one
expression in a sequence may return non-white SGML text, all results are
concatenated, and the sequence too returns SGML text.  Otherwise, any
whitespace in the sequence is discarded, and the result of the last subexpression is the result of the sequence.  These kinds of sequence are called \e{concatenation} and \e{value} sequences, respectively.

An STML variable can be defined and initialized using the \tag{define} tag,
extending the current environment, and can be referenced using the \tag{ref}
tag.  The variable can be updated using \tag{assign}.  Variables are typed
and scoped statically.  Because of higher-order functions, variables have
potentially unlimited lifetime.

The \tag{fun} element is the abstraction operator, also known as lambda.
Evaluation returns a function value capturing the function's body and the
current environment.  Functions are truly first-class: They can be assigned to
a variable, passed to another function or be returned form the current
function.  Functions are applied with the \tag{apply} element.  Actual
arguments have to match the formal parameters' types.

There is no way to decompose an SGML text value or to test complex
conditions using STML constructs only.  These applications fall into the
domain of the application programming language, and will be explained in
Section~\ref{Sec:Integration}.

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

\subsection{Typing Rules for STML}
\label{Sec:Types}

The type algebra of STML is based on the type \p{Sgml}, the type identifiers inherited from the application language and on function types mapping a list of argument types to a result type.  The following EBNF grammar gives the syntax of type expressions and parameter lists denoted by the \p{\%stml.type} and \p{\%stml.param} entities in Figure~\ref{Fig:STML-DTD}.

\begin{xple}
  Type ::= BaseType $|$ 'Fun' '(' Parameters ')' ':' Type ;
  BaseType ::= 'Sgml' $|$ ApplicationLanguageType ;
  ApplicationLanguageType ::= name ;
  Parameters ::= [ Parameter \{ ',' Parameter \} ] ;
  Parameter ::= name ':' Type ;
\end{xple}

The type \k{Sgml} denotes well-formed SGML text.  By well-formed we
mean syntactically valid markup, a proper balancing of opening and
closing tags, and tag and attribute names corresponding to those
defined in the client DTD.  We have not attempted to enforce
conformance to the client DTD's element structure in computed SGML
text, although with a more elaborate type system, this would be
possible, too.

Arbitrary nesting of function types is possible.  There is no mechanism to give
names to STML types, so type checking is purely based on structure.
Application language types are treated as abstract types: An application
language type only matches another application language type of the same name.

In addition to the types used for variables, STML expressions can have the
types \e{Bottom}, for the null value returned by \tag{assign} and \tag{define} elements, and \e{Whitespace}.  These types are used internally by the
typechecker for determining sequence types. The following example should
illustrate the problem of whitespace handling in SGML and the distinction between value and concatenation sequences:

\begin{xple}
$<$define name=v1$>$   $<$ref name=v$>$   $<$/define$>$
\end{xple}

The variable \p{v1} is bound to a value based on that of the variable
\p{v}.  To the parser, the sequence contained in the \tag{define} element
consists of character data (the initial whitespace), followed by a \tag{ref}
element, followed by further character data (further whitespace).  How should this be interpreted by the compiler?  If \p{v} is a variable containing
SGML text, the programmer wants to concatenate whitespace on both sides, and so
the sequence is a concatenation sequence.  However, if \p{v} is an STML
function or an application language value, the sequence is a value sequence, and the whitespace should be discarded.  In order to statically determine the correct behavior, the STML compiler has to track \p{v}'s type. 

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

\section{Integration with an Application Programming Language}
\label{Sec:Integration}

This section describes how the services of an application programming language
can be utilized seamlessly in STML documents.  This is achieved by mapping STML types, variables and values to the corresponding concepts of the application
programming language, thus enabling bi-directional data flow, and by allowing
application code to be embedded into STML documents.

This tight integration is realized by a compilation from STML into application language code.  However, as should be clear from the previous section, we have taken care to define the syntax, type rules and evaluation semantics of STML independent of the specific application language model.

In the following examples we will use the language Tycoon-2 as a concrete example for an application language.  As the name implies, Tycoon-2 is the successor of the Tycoon system \cite{Matt95} developed at the University of Hamburg. An earlier version of Tycoon-2, called TooL, is described in \cite{GaMa96b}. Tycoon-2 is a polymorphic, strongly-typed
object-oriented programming language that integrates external services and data sources, and provides the glue between user-oriented interface and communication services on the one hand side, and computation and storage-oriented services such as full-text and relational databases on the other hand. 

\subsection{Using Application Language Expressions in STML Tags}

As can be seen from the DTD in Figure~\ref{Fig:STML-DTD}, the \tag{if}, \tag{elseif}, \tag{send}, and \tag{eval} tags all contain application code (\p{\%stml.expression}). Evaluating these tags involves evaluating the application language expression. In the case of the \tag{if} and \tag{elseif} tags, the expression evaluates to a boolean, determining which branch of the conditional is to be taken.

\begin{xple}
$<$if true='project.employees.size = 0'$>$
  No employees.$<$P$>$
$<$else$>$
  $<$!-- list employees... --$>$
$<$/if$>$
\end{xple}

The \tag{eval} tag allows execution of arbitrary application code.  This code
may produce SGML output as a side-effect.  Free identifiers in the application
code, like \p{project} in the condition of the \tag{if} tag above, can
refer to variables defined in STML, for example, defined as a function
parameter:

\begin{xple}
$<$define name='projectHeader'$><$fun param='project :Project'$>$
  \texttt{$<$H1$>$Project }$<$eval$>$ out.writeString(project.name) $<$/eval$>$\texttt{$<$/H1$>$}
$<$/define$>$
\end{xple}

The \tag{send} tag serves to pass arbitrary STML values to a method of the
application language.\footnote{Our implementation is based on an
  object-oriented application language.  In a procedural or
  functional language, the \tag{send} tag could be renamed \tag{call}. } The receiver is denoted by an application language
expression, but all arguments are STML expressions, possibly STML functions.

\begin{xple}
$<$send receiver='project' selector='discriminate'$>$
$<$arg$><$fun param='project :InternalProject'$>$
  ...$<$!-- project is an internal project --$>$
$<$arg$><$fun param='project :ExternalProject'$>$
  ...$<$!-- project is an external project --$>$
$<$/send$>$
\end{xple}

\subsection{Accessing STML Values from Application Code}
\label{Sec:STMLToApp}

In the previous examples, the variables referenced from application code
always contained application values.  But functions and SGML text defined in
STML can be referenced as well.

\begin{xple}
$<$define name='separator'$><$P$><$HR$><$/define$>$
$<$eval$>$ 
  application.projects.forEach(\k{fun}(p :Project) \{
    projectHeader[p]
    p.printDescription(out)
    out.writeString(separator)
  \})
$<$/eval$>$
\end{xple}
This example, using Tycoon-2, iterates over all projects defined in the
application.  For each project, it calls the STML \p{projectHeader} function
defined in an earlier example, calls a Tycoon-2 method for the
actual project description, and prints the contents of the \p{separator}
variable after each project.

Note how the types and values of the \p{projectHeader} and \p{separator}
variables are mapped: The \k{Sgml} type of \p{separator} becomes \p{String} on the Tycoon-2 side, allowing it to be passed to \p{writeString}.
The variable \p{projectHeader} has type \p{\k{Fun}(project :Project):\k{Sgml}}, a function from the application type \p{Project} to \k{Sgml}.
On the Tycoon-2 side, this becomes a function type, too, and the argument type
is naturally mapped to the Tycoon-2 type \p{Project}.  However, the result
type \k{Sgml} turns into \p{Void\/}: For efficiency reasons, STML functions
returning SGML text are implemented in a side-effecting way, printing on the
current output rather than returning a string value.  As a consequence, the Tycoon-2 code does not have to explicitly concatenate the output it produces, but can use the implicit (and more efficient) concatenation of the output stream. The type mapping rules are summarized in Figure~\ref{Fig:TypeMapping}.

\begin{figure}[htbp]
\begin{center}
\leavevmode
\begin{tabular}{|l|l|}
\hline
STML Type $T$           & Generated Tycoon-2 Type $\rho(T)$ \\
\hline
\k{Sgml}                & \p{String}(containing well-formed SGML) \\
\p{ApplicationType}     & \p{ApplicationType} \\
\k{Fun}($i_1:T_1$,...,$i_n:T_n$):\k{Sgml}
                        & \k{Fun}($\rho(T_1)$,...,$\rho(T_n)$)\p{Void}\\
                        &(output via side-effect)\\
\k{Fun}($i_1:T_1$,...,$i_n:T_n$):$T$
   ($T \neq$ \k{Sgml})  & \k{Fun}($\rho(T_1)$,...,$\rho(T_n)$)$\rho(T)$ \\
                        & (no output)\\
\hline
\end{tabular}
\caption{Mapping from STML Types to Tycoon-2 Types}
\label{Fig:TypeMapping}
\end{center}
\end{figure}


\subsection{Passing Application Values to STML}
\label{Sec:AppToStml}

There are three ways of introducing application values into STML: As parameters
of STML functions called back from the application, through the \tag{eval}
tag, or through an implementation-dependant initial environment defined for a
document.

The initial environment contains at least the current output (\p{out}) and
the application object (\p{application}), which serves as the global entry
point for persistent, application-wide data.  The environment can also contain
information about the particular request that initiated evaluation of this
document, which in turn may include information about the person initiating
the request.  The concrete implementation is described in Section~\ref{Sec:Web}.

The statements inside an \tag{eval} tag can include binding statements,
introducing new application variables.  These are not only visible inside the
\tag{eval} tag, but also in the following STML code up to the end of the
current sequence.  The example uses the Tycoon-2 binding operator \p{::=}.

\begin{xple}
$<$eval$>$  application.sortProjects  project ::= application.projects[0] $<$/eval$>$
$<$if true='project.isNotNil'$>$
  $<$apply name='projectHeader'$><$arg$><$ref name=project$><$/apply$>$
$<$/if$>$
\end{xple}
Since in this example the type of the \p{project} variable is deliberately left open by the programmer (to be inferred later by the application language's type checker) the STML type checker can only assume that the variable has \p{some} type.  Technically speaking, the  variable is assigned a type unification variable, which will at least detect inconsistent use.  Exact type checking is deferred to the application language's type checker.

Another way of passing data out of the \tag{eval} tag is through assignment.
STML variables are mutable, and this property is reflected in application
code.  

\begin{xple}
$<$define name='str'$>$\texttt{some string}$<$/define$>$
$<$define name='f'$><$fun param='x :Sgml'$><$ref name=x$><$/define$>$
$<$eval$>$
  str := "another string"
  f := \k{fun}(s :String):Void \{ out.writeString(s) \}
$<$/eval$>$
\end{xple}
This example assigns a Tycoon-2 string value to an STML variable of type
\k{Sgml}, and a Tycoon-2 first-class function value to an STML variable of the
corresponding type.  Types are mapped in the way described in
Section~\ref{Sec:STMLToApp}.

Note that the new function assigned to \p{f} is semantically equivalent to
the one defined in STML.  Note also that the Tycoon-2 String type is less
strict than the \k{Sgml} type, allowing strings that are not well-formed SGML.

Call-back parameters are the most common way for accessing application data in
STML.  An STML function is passed to the application, and is applied there
like an ordinary function defined in the application language.  Transparent to
the application program, the function arguments enter the STML document, with
their types being mapped as described above, for example:
\begin{xple}
formatEmployees(f :\k{Fun}(String, String, String)Void)
\{ employees.forEach(\k{fun}(e:Employee) \{
     f[e.firstName, e.sex.asString, e.age.asString]
  \})
\}
\end{xple}
Assuming the above definition of the method \p{formatEmployees} in class \p{Project}, application data can be formatted in STML like this:
\begin{xple}
$<$send receiver='project' selector='formatEmployees'$>$
  $<$arg$><$ref name=formatEmployee$><$/send$>$
\end{xple}
By virtue of the rich bulk type libraries of Tycoon-2 (inherited from its predecessor TooL \cite{GaMa96a,GaMa96b}), the iterator \p{employees.forEach} could be an iteration over a persistent program data structure, a selection query, or an iteration over the results of an SQL query submitted to a SQL server as exemplified by the following Tycoon-2 code fragments: 
\begin{xple}
employees :Array(Employee)    (* persistent data structure *)

employees: Reader(Employee)   (* computed iteration *) \{
  application.allEmployees.select(\k{fun}(e:Employee):Bool \{
    e.project = self
  \})
\}

employees: Reader(Employee)   (* SQL query *) \{
  cursor ::= sqlConnection.directQuery(
    "select * from Employees where projectId="+self.id),
  FunReader.new(\k{fun}() \{   ;; call this function for successive elements:
    cursor.next.if(   ;; more employees?
      true: \{ rowToEmployee(cursor) \}   ;; yes $\Rightarrow$ create object for this row
      false: \{ nil \})\})   ;; no $\Rightarrow$ end of iteration
\}
\end{xple}

%-----------------------------------------------------------------------------
\section{Using STML on the WWW}
\label{Sec:Web}

One of the communication services supported by Tycoon-2 is the Hypertext Transfer Protocol (HTTP) of the World Wide Web.  Tycoon-2 offers an
extensible Web Server Framework based on polymorphic resource objects, similar
to the W3 consortium's Jigsaw server.  By connecting HTTP resource
objects to external resources, it implements a \e{three-tier
architecture} as shown in Figure~\ref{Fig:ThreeTier}.  The web
browser on the \e{client} tier connects to the integrated Tycoon-2
web and \e{application} server representing the second tier, which
operates on \e{data} from the third tier.

The Web Server Framework can be extended by subclassing resource
classes using the full power of the Tycoon-2 system to answer a HTTP request, without the overhead traditionally associated with the Common Gateway Interface (CGI). All external system resources are accessed and all computations are performed in statically typed, compiled Tycoon-2 code.

In this context, STML is used for dynamically generating HTML pages based on persistent application objects (e.g., an inventory database), possibly depending on session-specific information (e.g., contents of a virtual shopping basket) and on information associated with an individual client request, (e.g., address of a customer).

The resource class \p{StmlResource} is defined and is registered with the web server under the file extension \p{.stml}.  Whenever the web server encounters a request for a file name with this extension, it creates an \p{StmlResource} object.  HTTP requests for the resource are then delegated to the resource object.  The \p{.stml} document itself is assumed to contain STML source text (i.e. SGML enriched with higher-order functions), and the HTML page returned by the server is the result of evaluating the STML code (c.f. Figure~\ref{Fig:ThreeTier}).  

This dynamic and personalized document generation involves the following steps:

\begin{enumerate}
\item The \p{.stml} file's timestamp is checked.  If the file has not
  been modified since the last access by the web server, execution proceeds
  directly with step 6. This implies that the compilation result obtained in
  steps 2 through 5 is cached persistently.

\item The STML source is parsed and verified by a standard SGML parser.  Errors
  such as invalid markup, mismatched tags, and missing or unknown attribute
  names or values are reported.

\item The abstract STML tree produced by the SGML parser is type checked
  as described in Section~\ref{Sec:Types}.

\item If type checking succeeds, the STML code is compiled into a Tycoon-2
  function.  Adjacent
  output is concatenated into block write messages whenever possible, giving
  performance equal to or exceeding that of static HTML (file) resources.
  This phase produces an object structure representing a Tycoon-2 abstract
  syntax tree.  We do not produce source text in order to avoid unnecessary
  dependency on the surface syntax and to avoid costly unparsing and
  re-parsing by the Tycoon-2 compiler.  There is an analogy to STML here: In
  both cases, we prefer dealing with structure rather than flat text.

\item The Tycoon-2 abstract syntax tree produced in the previous step is
  compiled to an executable Tycoon-2 function using the reflective facilities
  offered by the Tycoon-2 system.  This includes an additional type-checking
  phase on the Tycoon-2 side.  The function is stored in the resource object.

\item Every time the resource is accessed, an \p{StmlProcessor} object is
  allocated which handles the current request.  Its slots and methods provide
  the initial environment for the STML document (see
  subsection~\ref{Sec:AppToStml}), containing at least a reference to the HTTP
  request object, a reference to the application object, and the current
  HTML output object.  The request object includes information about the
  client issueing the HTTP request, in the form of the HTTP basic authentication
  scheme (identification by name and password) and id numbers attached as query
  arguments or cookies.
  
\item The function created in step 5 is called to produce the actual output.
  If a compilation error occurred, the error messages are returned instead of
  the STML page's results.  This can only happen during development, since a
  page that has been successfully compiled once will not have to be compiled
  again.
\end{enumerate}

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

\section{Related Work}
\label{Sec:RelatedWork}

Support for textual presentation with specialized report languages dates back to the 1970s. Over the years, the presentation media evolved, from printers, terminals to graphical workstations and to Hypertext documents published via the World Wide Web.

Dynamically generated HTML has been with the World Wide Web from the
beginning.  The simplest solutions for generating dynamic output consists of
CGI scripts fully responsible for composing a page, usually consisting of a
sequence of print statements.  The document is embedded in the program, so the
author of a dynamic page has to be a programmer.  There is no mechanical aid
such as an editor that would simplify the creation of these pages, and there
is no guarantee that their output is actually HTML. Moreover these scripts
tend to be unreliable and slow because they are written in dynamically typed,
purely interpreted languages with virtually no support for efficient database access.

As a reaction to these shortcomings, specialized markup languages allow the
inclusion of dynamic elements inside documents.  This way, the document
layout can be designed and modified later without affecting the dynamic parts,
and without a need to understand them.  Examples are WWW servers that
recognize certain special character sequences in HTML documents, and replace
them with the current time, the modification date, the contents of some other
file, or the output of some shell command.  The NCSA server \cite{NCSA97} expects these server-side includes in HTML comments, thus allowing page construction with a standard HTML editor.  This serves some basic needs, but offers no way to produce conditional or repeating document parts. 

A number of database/web integration tools offer specialized
markup for the presentation of relational tables, including a restricted form
of iteration.  These tools are similar in functionality to traditional report
languages, binding text fragments to certain events in the
output like page breaks or group changes.  However, the document structure
assumed by these constructs is too rigid to cope with varying media types, or
to represent complex data structures.

Most dynamic HTML extensions do not conform to any document
standard, precluding the use of a standard editor.  For example, the Roxen
server \cite{Roxen97} uses a huge number of ad hoc tags, one tag for every function offered by the server.  There is no DTD available, so the page creator has to resort to manual construction.  Other HTML preprocessing tools (e.g. w3msql by Hughes Technologies \cite{MSQL97}) use fantasy tags like {\tt $<<$...$>>$}, {\tt [...]} or {\tt $<!$...$>$} that have no meaning or a different meaning in SGML. Moreover, the dynamically generated parts are usually produced using print statements.

Some major systems like ColdFusion by Allaire \cite{ColdFusion97}, HAHTSite by HAHT \cite{HAHTSite97}, NetDynamics \cite{NetDynamics97}, or WebObjects by NeXT, Inc. \cite{WebObjects97} work around this problem by supplying their own WYSIWYG editor. However, this requires updating the development system when the user wants to use new HTML extensions.

Another framework for dynamic HTML is the LiveWire product by
Netscape Communications Corporation, offering server-side JavaScript \cite{LiveWire97}.  This offers the flexibility of a full (though dynamically typed) programming language, with access to server-side persistent data. LiveWire introduces just one new tag, the \tag{SERVER} tag for including LiveWire statements.  This minor extension poses no problems for computer supported editing.  Still, dynamically created HTML fragments have to be issued via print statements.

\section{Summary and Future Work}
\label{sec:conclusion}

STML is defined as an orthogonal DTD extension, which can be added easily to the latest HTML DTD. Any SGML editor can be used for page creation and maintenance.  STML tags obey and preserve the document structure.  Dynamic parts are created from templates passed to the application in the form of first-class, lexically-scoped STML functions.  STML separates the language level (naming and binding) from the application level (the actual operation to be performed), allowing greater flexibility when adding new functionality.  Last but not least, STML offers a seamless, type-safe integration with persistent data and external services.

Structured document description languages in the spirit of SGML can also be used to describe interactive elements (buttons, input fields, scrollbars, drop targets) embedded in hierarchical documents. We expect that the extension of SGML with higher-order functions will also simplify the binding from these elements to event handlers in the application code.

\subsection*{Acknowledgments}


This paper is a summary of work carried out at Higher-Order Information and
Communication Systems GmbH, Hamburg.  Andreas Gawecki turned this idea into a
project, and supplied the framework for implementing STML on the Web.  STML was improved by the comments and remarks of its first users, Hubertus Koehler and Ingo Richtsmeier.  

{\small
\bibliography{florian-macros,florian}
}
\end{document}

