\begin{appendix}

        \chapter{Sprachbeschreibung GDL}
        \label{grammar}

\section*{Syntaktische Konventionen}

Folgende EBNF-"ahnliche Notation wird zur Definition syntaktischer Elemente
verwendet, wobei {\sl A} und {\sl B} syntaktische Ausdr"ucke repr"asentieren
und Terminalsymbole durch Fettdruck dargestellt werden.

\begin{table}[h] 
\begin{center} 
\begin{tabular}{|l|l|} \hline 
\rule[-3mm]{0mm}{8mm}
{\bf Symbol} & {\bf Bedeutung}\\  \hline
{\sl Id} ::== {\sl A} & Nicht-Terminal {\sl Id} wird durch {\sl A} definiert\\
'x' & das Zeichen x\\
{\em identifier} & ein g"ultiger \TL-Bezeichner\\
{\em ''string''} & String-Literal \\
{\sl A B} & A gefolgt von B\\
{\sl A} $\mid$ {\sl B} & {\sl A} oder {\sl B}\\ 
$[${\sl A}$]$ & null- oder einmaliges Vorkommen von {\sl A}\\
\{{\sl A}\} & null- oder mehrmaliges Vorkommen von {\sl A}\\ \hline
\end{tabular}
\end{center} 
\end{table}

\section*{Reservierte Schl"usselw"orter}

Folgende Bezeichner sind reservierte Schl"usselworte und d"urfen nicht als 
Bezeichner in GDL-Quelltexten verwendet werden:
\begin{quote}
{\bf as class const constructor define end enum export from include import 
gateway static typedef use using virtual}
\end{quote}

\section*{Symbole}
Der Aufbau von Symbolen entspricht dem von \TL\ \cite{MaSc92}, wobei (in Anlehnung
an C) Kommentare auch alternativ durch /* */ geklammert sein k"onnen.
'\#' and ';' werden als Formatierungszeichen behandelt, also "uberlesen.

\section*{Produktionen}

\subsection*{"Ubersetzungseinheit}
\begin{tabbing}
xxxxxxxxxxxxxxxx\= xxxx\= xx\= xx \= \kill
{\em description} \>::= \> {\em header} \\
  \>\> [{\bf include} {\em ''string''\{''string''\}}] \\
  \>\> {\bf export} \{{\em typeDecl}\} \\
  \>\> {\bf end}  \\

{\em header} \>::= \> {\bf qateway} ''C++'' {\em module-name} : 
{\em interface-name}\\
  \>\> [{\bf import} {\em gateway-name \{gateway-name\}}] \\
\end{tabbing}

\subsection*{Typen und Konstanten}
\begin{tabbing}
xxxxxxxxxxxxxxxx\= xxxx\= xx\= xx \= \kill
{\em typeDecl} \>::= \> {\em typedef $\mid$ define 
                         $\mid$ use $\mid$ enum $\mid$ class } \\
\\
{\em typedef} \>::= \> {\bf typedef} {\em identifier [ref] declarator} \\
\\
{\em define} \>::= \> {\bf define} {\em identifier int} \\
\\
{\em use} \>::= \> {\bf use} {\em declarator}
  {\bf from} {\em identifier} {\bf as} {\em identifier} {\bf using} 
  {\em identifier}\\
\\
{\em enum} \>::= \> {\bf enum} {\em declarator} '\{' {\em enumList} '\}' \\
\\
{\em enumList} \>::= \> {\em enumerator \{ ',' enumerator\}}\\
\\
{\em enumerator} \>::= \> {\em declarator} [ '=' {\em integer}] \\ 
\\
{\em ref} \>::= \> * $\mid$ \& \\
\\
{\em declarator} \>::= \> {\em identifier} ['$$=>$$' {\em \TL-identifier}] \\
  \>\> [''documentation-string''] (* Umbenennung und Dokumentation *)
\end{tabbing}

\subsection*{Klassen}
\begin{tabbing}
xxxxxxxxxxxxxxxx\= xxxx\= xx\= xx \= \kill
{\em class} \>::= \> {\em classHead} ['\{' [{\em headerList}] '\}'] \\
\\
{\em classHead} \>::= \> {\bf class} {\em declarator} [{\em baseSpec}]  \\
\\
{\em baseSpec} \>::= \> ':' {\em baseList} \\
\\
{\em baseList} \>::= \> {\em identifier \{ ',' identifier\}}\\
\\
\end{tabbing}


\subsection*{Methoden}
\begin{tabbing}
xxxxxxxxxxxxxxxx\= xxxx\= xx\= xx \= \kill
{\em headerList} \>::= \> {\em methodHeader \{methodHeader\}} \\
\\
{\em methodHeader} \>::= \> {\em normalHeader} $\mid$ {\em constructorHeader}
  $\mid$ {\em virtualHeader} \\
\\
{\em normalHeader} \>::= \> [{\bf static}] {\em identifier} [{\em ref}] {\em nameAndSigs} \\ 
\\
{\em constrHeader} \>::= \> {\bf constructor} {\em nameAndSigs} \\ 
\\
{\em virtualHeader} \>::= \> {\bf virtual} {\em identifier} [{\em ref}]
  {\em nameAndSigs} \\ 
\\
{\em nameAndSigs} \>::= \> {\em declarator} '(' [{\em sigList}] ')' [{\bf const}]  \\
\\
{\em sigList} \>::= \> {\em signature \{ ',' signature\}}\\
\\
{\em signature} \>::= \> [{\bf const}] {\em identifier} [{\em ref}] {\em identifier}  \\
\end{tabbing}

        \chapter{Schnittstellen f"ur dynamische Typen}
	\label{dynTypeInterface}

\section{Schnittstelle 'TypeRep'}
\label{typeRep}

\begin{xple}
\kw{interface} TypeRep
\kw{import} list time :Iter :Source
\kw{export}
  \kw{Let} T = typeRep\_T
  (* T is a type representation for an arbitrary parameterized or closed type. *)
  \kw{Let} Ide = \kw{Tuple} name :String  pos :Source.Position \kw{end}
  \kw{Let} Signature = \kw{Tuple}
    ide :Ide
    type :T
    \kw{case} typeCase, typeEqualCase \kw{with} (* T$<:$A rsp. T = A *)
      typeID :time.T
    \kw{case} typeBoundCase \kw{with}
      typeID :time.T
      bound :T
    \kw{case} valueCase, locationCase 
  \kw{end}
  \kw{Let} Case = \kw{Tuple}
    label :String
    signatures :list.T(Signature) (* additional fields for this variant *)
  \kw{end}
  \kw{Let} Expansion = \kw{Tuple} 
    \kw{case} okCase, nokCase 
    \kw{case} baseCase \kw{with} ide :Ide
    \kw{case} ideCase \kw{with}
      ref :String
      definition :Signature
    \kw{case} adtCase \kw{with}
      ref :String
      definition :Signature
      path :\kw{Tuple} oid :String \kw{end}
    \kw{case} funCase \kw{with}
      signatures :list.T(Signature)
      range :T
    \kw{case} tupleCase \kw{with}
      signatures :list.T(Signature)
      cases :list.T(Case)
    \kw{case} recordCase \kw{with} signatures :list.T(Signature)
    \kw{case} exceptionCase \kw{with} signatures :list.T(Signature)      
    \kw{case} operCase \kw{with}
      signatures :list.T(Signature)
      range :T  
    \kw{case} arrayCase \kw{with}
      elementType :T
    \kw{case} appCase \kw{with} (* type operator application *)
       oper :T
       arguments :list.T(Signature)
    \kw{case} recCase \kw{with}
      bindingIndex :Int  (* No. of binding in typeBindings *)
      typeBindings :list.T(Signature)
  \kw{end}
  
  isSubType(small, big :T) :Bool
  (* Return true if the type representations are in the subtype relationship
     small$<:$big. *)
  inspect(type :T) :Expansion
  (* Return a more detailed description of the type 'type'. *)
  exposed(type :T) :T
  (* Strip definition(s) of 'type'. *)
  signatures(t :T) :Iter.T(Signature)
  (* If t is a tuple, record, exception, oper or function representation,
     return an iteration of signatures, else raise error *)
  fmt(type :T) :String
  (* Return a string containing a \TL\ type expression corresponding to type *)
  newArray(type :T) :T
  newFun(signatures :list.T(Signature)  range :T) :T
  newTuple(signatures :list.T(Signature)  cases :list.T(Case)) :T
  newRecord(signatures :list.T(Signature)) :T
  newException(signatures :list.T(Signature)) :T
  newOper(signatures :list.T(Signature)  range :T) :T
  (* Constructors for type representations *)
\kw{end}
\end{xple}

\newpage

\section{Schnittstelle 'Dynamic'}
\label{dynamic}

\begin{xple}
\kw{interface} Dynamic
\kw{import} list typeRep :TypeRep :Iter reader writer
\kw{export}
  error :\kw{Exception}
  \kw{Let} T = dynamic\_T
  (* A dynamic value :T is a  tuple val :T  type :Type end 
     where type is the type representation of val. *)
  \kw{Let} Binding = \kw{Tuple}  
    name :String
    \kw{case} typeCase \kw{with} type :typeRep.T
    \kw{case} valueCase \kw{with} value :T
    \kw{case} locationCase \kw{with}
      value() :T
      setValue(:T) :\kw{Ok} 
  \kw{end}
  \kw{Let} Expansion = \kw{Tuple}
    \kw{case} okCase 
    \kw{case} boolCase \kw{with} val :Bool
    \kw{case} charCase \kw{with} val :Char
    \kw{case} intCase \kw{with} val :Int
    \kw{case} realCase \kw{with} val :Real
    \kw{case} stringCase \kw{with} val :String
    \kw{case} adtCase 
    \kw{case} funCase \kw{with}
      signatures :list.T(TypeRep.Signature)
      range :typeRep.T
    \kw{case} tupleCase \kw{with}
      tag: String
      fields :list.T(Binding)
    \kw{case} recordCase \kw{with} fields :list.T(Binding)
    \kw{case} exceptionCase \kw{with}
      val :String
      signatures :list.T(TypeRep.Signature)
    \kw{case} arrayCase \kw{with}
      type :typeRep.T   (* type is the element type *)
      size :Int
    \kw{case} appCase \kw{with}
      oper :typeRep.T
      arguments :list.T(TypeRep.Signature) 
      value :T  
  \kw{end}
  typeOf(value :T) :typeRep.T
  (* Return the type attribute of value. *)
  valueOf(value :T) :\kw{Ok} 
  (* Return the value attribute of value with least possible static type information *)
  inspect(value :T) :Expansion
  (* Return a more detailed description of the value 'value'. *)
  signatures(value :T) :Iter.T(TypeRep.Signature)
  (* If value is a value of a function or exception, return an iteration of 
     signatures, else raise error *)
  bindings(value :T) :Iter.T(Binding)
  (* If value is a dynamic of a tuple or record, return an iteration of bindings, 
  else raise error *)
  functions(value :T) :Iter.T(T)
  (* Return an iteration of all functional components of a value. Especially 
     useful when value is a dynamic of a linked module. *)
  getIndexed(value :T  i :Int) :T
  (* Return the i'th element of value if it is a dynamic of an array else
     raise error *)
  setIndexed(value :T  i :Int newValue :T) :\kw{Ok}
  (* Set the i'th element of value to newValue if it is a dynamic of an array 
     else raise error *)
  intern(r :reader.T) :T
  (* Obtain a dynamic from a reader. *)
  extern(w :writer.T  value :T) :\kw{Ok}
  (* Write a dynamic to a writer. *)
  newDefault(type :typeRep.T) :T
  (* Create a default value with type 'type'. *)
  newArray(A $<:$\kw{Ok}  arr :Array(A)  type :typeRep.T) :T
  newTuple(fields :list.T(Binding)) :T
  newTupleCase(tag :String  type :typeRep.T fields :list.T(Binding)) :T
  (* Raise error if tag is not a tag of type or if fields do not match type. *)
  newRecord(fields :list.T(Binding)) :T
  newException(value :String  signatures :list.T(TypeRep.Signature)) :T
\kw{end}
\end{xple}


        \chapter{Schnittstellen des aufrufbaren Compilers}
	\label{compilerInterface}

\section{Schnittstelle 'Environment'}
\label{environment}

\begin{xple}
\kw{interface} Environment 
\kw{import} :Iter :Dynamic
\kw{export}
  lookupError :\kw{Exception with} name :String \kw{end} 
  T $<:$\kw{Ok} 
  (* A collection of Bindings *)
  new() :T
  (* Return an Environment containing the initial bindings *)
  clear(:T) :Ok 
  (* Clear all Bindings except the initial. *)
  size(:T) :Int
  (* Return the size of an Environment. *)
  getLast(:T) :Dynamic.Binding 
  (* Return last binding of an Environment *)
  concat(e1, e2 :T) :T
  (* Return concatenated environment. Bindings in e1 will possibly hide bindings in e2 *)
  lookup(:T name :String) :Dynamic.Binding
  (* Return last binding named 'name'. Raise lookupError if not found *)

  dropBinding(:T name :String) :\kw{Ok} 
  (* Removes binding for 'name' from environment. *)
  dropLastBinding(:T) :\kw{Ok} 
  (* Remove last binding of an environment. *)
  addBinding(:T binding :Dynamic.Binding) :\kw{Ok}
  (* Extend environment by adding bnd. *)
  addValueBinding(:T :String :dynamic\_T) :\kw{Ok}
  (* Short cut for addBinding(...). *)
  addTypeBinding(:T :String :typeRep\_T) :\kw{Ok}
  (* Short cut for addBinding(...). *)
  addLocationBinding(:T :String :dynamic\_T) :\kw{Ok}
  (* Short cut for addBinding(...). *)
  changeValue(:T :String :dynamic\_T) :\kw{Ok}
  (* Change value of a Binding *)
  ...
  symbols(:T) :Iter.T(String)
  (* Return iteration over symbols bound in environment *)
  create(from :Iter.T(Dynamic.Binding)) :T 
  (* Create an environment from an iteration of bindings *)
  elements(:T) :Iter.T(Dynamic.Binding)
  (* Return iteration over bindings in environment *)
\kw{end}
\end{xple}

\newpage

\section{Schnittstelle 'Compiler'}
\label{compiler}

\begin{xple}
\kw{interface} Compiler
\kw{import} environment source errorLog :Scanner :Symbol :TLValue :TML tm
\kw{export}
  error :\kw{Exception with} log :errorLog.T \kw{end}

  parse(:source.T) :TLValue.Bindings 
  (* Return abstract Syntax for source. *)
  check(:TLValue.Bindings :environment.T)()() :Dynamic.Binding 
  (* Checks bindings and returns a function which translates bindings
     and returns a function which executes them. 
     Updates environment on execution. *)
  compileSyntaxTree(:environment.T :TLValue.Bindings)() :Dynamic.Binding
  (* Compiles bindings and returns a function which executes them. 
     Updates environment on execution. *)
  compileSource(:environment.T :source.T)() :Dynamic.Binding
  (* Compiles src and returns a function which executes them. 
     Updates environment on execution. *)
  compileString(:environment.T :String)() :Dynamic.Binding
  (* Compiles src and returns a function which executes them. 
     Updates environment on execution. *)
  eval(:environment.T :String) :Dynamic.Binding 
  (* Executes a string, updates environment and returns the resulting Binding. *)

  (* Retrieval of intermediate results. *)
  getScan() :Scanner.T(Symbol.T)
  getParseTree() :TLValue.Bindings
  getAttributedParseTree() :TLValue.Bindings
  getTMLTree() :TML.T
  getTVMCode() :tm.OID

  (* compiler switches: *)
  optimize(:Bool) :\kw{Ok}
  ...
  getOptimize() :Bool
  ...

  (* switches for system debugging (output to stdout): *)
  printTVM(:Bool) :\kw{Ok}
  traceSubType(:Bool) :\kw{Ok}
  ...
  getPrintTVM() :Bool
  getTraceSubType() :Bool
  ...
\kw{end}
\end{xple}

  

        \chapter{Beispiel f"ur eine typgesteuerte Funktion: nat"urlicher
		 Verbund}

\label{natural-join}

Die Funktion {\sl generateJoin} erf"ullt folgende Teilaufgaben:
\begin{enumerate}
\item Generierung einer Typrepr"asentation der Ausgaberelation,
ausgehend von den Typrepr"asentationen der Eingaberelation,
\item Generierung einer Funktion ({\sl defineMatch}), die feststellt, ob 
zwei Join-Felder gleich sind. Der Test auf paarweiser Gleichheit der 
Join-Attribute wird dabei auf den Test auf (tiefe) Gleichheit zweier 
automorpher Werte zur"uckgef"uhrt. Dadurch arbeitet die generierte Funktion 
auch auf nicht flach strukturierten Tupeln. Die Funktion {\sl andCompose} 
erzeugt aus einer Menge von Strings einen String, dessen Worte durch ''andif''
verkn"upft sind.
\item Generierung einer Funktion ({\sl defineConcat}), die 
aus passenden Attributen der Eingabetupel ein Ausgabetupel konstruiert.
Die dazu benutzte Funktion h"oherer Ordnung {\sl reduce} hat folgende Signatur:
\begin{xple}
  \kw{Fun}(A, B, C $<:$Ok  
         i :Iter.T(A)
         apply(:A) :B
         accumulate(:B :C) :C
         base :C) :C 
\end{xple}
Sie wendet {\sl apply} auf jedes Element von {\sl i} an und akkumuliert das 
Resultat mittels {\sl accumulate}, beginnend mit {\sl base}.
\item Generierung einer rekursiven Funktion, die die Join-Operation ausf"uhrt.
\end{enumerate}

\begin{xple}
\kw{let} signatureEqual(s1, s2 :typeRep.Signature) :Bool = 
  string.equal(s1.ide.name s2.ide.name) 
  \kw{andif} typeRep.equal(s1.type s2.type)
  
\kw{let} getStructureFields(t :typeRep.T) :relation.T(typeRep.Signature) = 
  set.create(
    list.elements(
      \kw{case} typeRep.inspect(t)
      \kw{when} recordCase \kw{with} t1 \kw{then} t1.signatures
      \kw{else raise exception} ''Not a record type''
      \kw{end})
    signatureEqual)

\kw{let} generateJoin(type1, type2 :typeRep.T) :String =
  \kw{begin}
    \kw{let} type1Fields = getStructureFields(type1)
    \kw{let} type2Fields = getStructureFields(type2)
    \kw{let} resultFields = set.union(type1Fields type2Fields)
    \kw{let} resultType :typeRep.T = 
      typeRep.newRecord(list.create(set.elements(resultFields)))
    \kw{let} defineMatch() :String = 
      \kw{begin}
        \kw{let} overlap = set.intersection(type1Fields type2Fields)
        \kw{let} testSet = set.new(:String string.equal)
        iter.forEach( (* fill testSet with compare expressions *)
          set.elements(overlap)
          \kw{fun}(sig :typeRep.Signature) :\kw{Ok} 
            \kw{begin}
              \kw{let} expr = 
                 ''dynamic.equal(dynamic\_new(arg1.'' $<>\footnote{Operator zur Verkettung von Zeichenketten}$ sig.ide.name '')'' $<>$ 
                               ''dynamic\_new(arg2.'' $<>$ sig.ide.name $<>$ ''))''
              \kw{try} set.insert(testSet expr) \kw{else ok end}
            \kw{end})
        ''fun(arg1 :Rec1 arg2 :Rec2) :Bool '' $<>$ andCompose(testSet)
      \kw{end}

    \kw{let} defineConcat() :String =
      \kw{begin}
        \kw{let} fields  = 
          reduce(
            set.elements(resultFields)
            \kw{fun}(sig :typeRep.Signature) :String 
              \kw{begin}
                \kw{let} takeFrom = 
                  \kw{if} set.member(sig type1Fields) \kw{then} ''arg1''
                  \kw{else} ''arg2''
                  \kw{end}
                {''let '' $<>$ sig.ide.name $<>$ '' = '' $<>$ takeFrom $<>$ ''.'' $<>$ 
                 sig.ide.name $<>$ '' ''}
              \kw{end}
            \kw{fun}(binding :String fields :String) 
              string.cat(fields binding)
            '''')
        ''fun(arg1 :Rec1 arg2 :Rec2) :Result record '' $<>$ fields $<>$ ''end''
      \kw{end}
        
    \kw{let} defineOneJoin() :String =
      ''    let rec onejoin(element :Rec1 rel :Rel2 :ResultRel = $\backslash$n'' $<>$ 
      ''      if relation.empty(rel) then $\backslash$n'' $<>$
      ''        relation.new(:Result fun(x,y :Result) x == y) $\backslash$n'' $<>$
      ''      else $\backslash$n'' $<>$
      ''        let choose = relation.choose(rel) $\backslash$n'' $<>$
      ''        let rest = onejoin(element relation.rest(rel)) $\backslash$n'' $<>$
      ''        let match = '' $<>$ defineMatch() $<>$ ''$\backslash$n'' $<>$ 
      ''        let concat = '' $<>$ defineConcat() $<>$ ''$\backslash$n'' $<>$ 
      ''        if match(element choose) then $\backslash$n'' $<>$ 
      ''          let newRecord = concat(element choose) $\backslash$n'' $<>$
      ''          relation.insert(rest newRecord) $\backslash$n'' $<>$
      ''        end $\backslash$n'' $<>$
      ''        rest $\backslash$n'' $<>$
      ''      end $\backslash$n''

    ''Let Rec1 = '' $<>$  typeRep.fmt(type1) $<>$ ''$\backslash$n'' $<>$
    ''Let Rec2 = '' $<>$  typeRep.fmt(type2) $<>$ ''$\backslash$n'' $<>$
    ''Let Result = '' $<>$  typeRep.fmt(resultType) $<>$ ''$\backslash$n'' $<>$
    ''$\backslash$n'' $<>$
    ''Let Rel1 = relation.T(Rec1)$\backslash$n'' $<>$
    ''Let Rel2 = relation.T(Rec2)$\backslash$n'' $<>$
    ''Let ResultRel = relation.T(Result)$\backslash$n'' $<>$
    ''let rec join(rel1 :Rel1 rel2 :Rel2) :ResultRel = $\backslash$n'' $<>$ 
    ''  if relation.empty(rel1) then $\backslash$n'' $<>$
    ''    relation.new(:Result fun(x,y :Result) x == y) $\backslash$n'' $<>$
    ''  else $\backslash$n'' $<>$
    ''    '' $<>$ defineOneJoin() $<>$ ''$\backslash$n'' $<>$
    ''    let joinOne = onejoin(relation.choose(rel1) rel2) $\backslash$n'' $<>$
    ''    let joinOthers = join(relation.rest(rel1) rel2) $\backslash$n'' $<>$
    ''    relation.union(joinOne joinOthers) $\backslash$n'' $<>$
    ''  end $\backslash$n''
  \kw{end}
\end{xple}

%\section{Reflektive Behandlung von automorphen Werten, in denen abstrakte Typen
%injiziert sind}

\end{appendix}

