\chapter{Dynamische Typisierung}
\label{Dynamics}

%{\sf TL} ist eine strikt typisierte Programmiersprache, deren Typ"uberpr"ufung
%statisch zur "Ubersetzungszeit erfolgt. Die strikte Typisierung stellt sicher,
%da"s alle Programmentit"aten vor der Programmausf"uhrung auf Konsistenz mit dem
%Typsystem gepr"uft werden, so da"s die Programmausf"uhrung nicht aufgrund von
%Typfehlern ein falsches Ergebnis liefert oder sogar durch einen Laufzeitfehler
%abbricht. Dieses ist zur Konsistenzerhaltung der Daten in verteilten
%datenintensiven Anwendungen \cite{ScMa93,SMV93}, f"ur die Skalierbarkeit eines
%Systems und f"ur die Unterst"utzung durch externe Dienste unverzichtbar
%\cite{MaSc93}. Aufgrund der effizienteren Programmausf"uhrung, da die
%Typkorrektheit vorher in der "Ubersetzungsphase "uberpr"uft wird, ist die
%statische Typ"uberpr"ufung der dynamischen vorzuziehen. Allerdings gibt es
%Situationen in datenintensiven Anwendungen, in denen statisch nicht
%feststellbar ist, welchen Typ ein Wert zur Laufzeit hat, auch wenn das
%Typsystem polymorph ist. Dies ist bei der generischen Daten-- und
%Funktionsvisualisierung der Fall, da bei der Entwicklung der
%Visualisierungsfunktionen nicht bekannt ist, welche Typen die zu
%visualisierenden Daten haben werden. Zu diesem Zweck werden statisch typisierte
%Sprachen um das Konzept der dynamischen Typisierung erweitert, das in den
%Situationen, in denen eine statische Typ"uberpr"ufung nicht m"oglich ist, eine
%Typ"uberpr"ufung zu wohldefinierten Zeitpunkten w"ahrend der Programmlaufzeit
%erlaubt \cite{Matt87}.

Die typsichere generische Datenvisualisierung erfordert die Inspektion von
Typinformationen zur Laufzeit, um beliebige Daten entsprechend ihrer Struktur
korrekt visualisieren zu k"onnen. Deshalb m"ussen strikt typisierte
Programmiersprachen wie {\sf TL} um ein Konzept zur dynamischen Typisierung
erweitern werden (s. Abschnitt \ref{Typdiskussion}). Auch der urspr"ungliche
Sprachreport von {\sf TL} \cite{MaSc92} enth"alt Sprachkonstrukte, die die
dynamische Typisierung erm"oglichen. Allerdings wurde dieses Konzept nie
vollst"andig realisiert, da es bei der Implementierung des Kodes zur
Laufzeitunterst"utzung verschiedene Unzul"anglichkeiten offenbarte
(s. Abschnitt \ref{erster Ansatz}).

Aus diesem Grund erfolgt im Rahmen dieser Arbeit in Kooperation mit
\cite{Geis95} die Realisierung eines verbesserten, neuen Ansatzes. Nach einer 
Begriffseinf"uhrung zur dynamischen Typisierung werden im zweiten Abschnitt 
verschiedene, "uber die generische Datenvisualierung hinaus f"ur {\sf Tycoon}
relevante Anwendungsgebiete dynamischer Typisierung vorgestellt. Anschlie"send
erfolgt eine Analyse bekannter Ans"atze zur Realisierung dynamischer
Typisierung innerhalb statischer Programmiersprachen, unter besonderer
Ber"ucksichtigung der Probleme, die sich in Verbindung mit abstrakten
Datentypen und Polymorphismus ergeben. Ausgehend von diesen Untersuchungen wird
schlie"slich der Ansatz erl"autert, der in der aktuellen Version des {\sf
Tycoon} Systems implementiert worden ist.


\section{Laufzeittyprepr"asentationen und automorphe Werte}
Im Gegensatz zu den Programmteilen, die bereits statisch typgepr"uft worden 
sind, m"ussen Typinformationen von Werten, deren Typkorrektheit erst zur 
Laufzeit festgestellt werden kann, als Laufzeitwerte repr"asentiert werden. 
Solche Werte werden in der Literatur in der Regel als {\em dynamische Typen} 
bezeichnet \cite{Matt87,ACPR92,LeMa91}. Diese Bezeichnung ist jedoch
irref"uhrend, da es sich um Werte handelt, die statische Typen repr"asentieren,
so da"s hier ein anderer Begriff verwendet wird. 

In {\sf TL} ist die G"ultigkeit eines Typs T immer auf einen statischen 
Kontext S beschr"ankt. Mit $t_{S,T}$ sei die kontextunabh"angige
Typrepr"asentation des Typs T in dem statischen Kontext S zur Laufzeit
bezeichnet. Die h"aufigste Verwendung von Laufzeittyprepr"asentationen erfolgt
in Verbinding mit solchen Werten, deren Typ durch die
Laufzeittyprepr"asentation beschrieben wird. Solch ein Aggregat aus Wert und
zugeh"origer Laufzeittyprepr"asentation wird in der Literatur als {\em
automorpher} (selbstbeschreibender) Wert \cite{Card89} oder als {\em dynamic}
\cite{ACPR92} bezeichnet. Ein {\em automorpher} Wert ist also ein Paar ({\sl
x\/}, $t_{S,T}$), so da"s $t_{S,T}$ eine Laufzeitrepr"asentation des Typs des
Wertes {\sl x\/} darstellt.


\section{Anwendungen dynamischer Typisierung}
\label{Anwendungen}
Es gibt eine Reihe von Anwendungen, in denen die Typinformation erst zur
Laufzeit bekannt ist, so da"s sie mit Hilfe statischer Typsysteme nicht zu
realisieren sind. Diese werden innerhalb dieses Abschnittes charakterisiert und
anhand von Beispielen, die f"ur das {\sf Tycoon} System relevant sind,
untersucht. Diese Charakterisierung stellt ein wichtiges Kriterium f"ur die
Entwicklung eines Konzeptes zur Integration dynamischer Typisierung in {\sf TL}
dar.

Als ein typischer Vertreter von Anwendungen, die auf dynamische Typisierung
angewiesen sind, galten urspr"unglich generische Funktionen, d.h. Funktionen
die auf Werte verschiedener Typen angewendet werden k"onnen, aber ein Ergebnis
liefern, das unabh"angig von deren Typstruktur berechnet wird \cite{LeMa91}.
Ein Beispiel daf"ur ist die Funktion, die die Anzahl der Elemente einer Liste
eines beliebigen Typs ermittelt. Die Integration verschiedenener Arten von
Polymorphismus in das statische Typsystem erm"oglichte jedoch schlie"slich die
statische Typ"uberpr"ufung solch generischer Anwendungen. 

Die Frage, ob dynamische Typisierung in statischen Typsystemen generell
"uberfl"ussig ist, l"a"st sich mittels der in \cite{CaWe85} erfolgten
Charakterisierung der unterschiedlichen Arten des Polymorphismus beantworten.
Generell wird zwischen zwei Arten von Polymorphismus unterschieden:

\begin{description}
\item[Universeller Polymorphismus] wird bei Funktionen verwendet, die auf 
einer unendlichen Menge verschiedener Typen arbeiten, die alle "uber eine 
gemeinsame Struktur verf"ugen. 
\item[Ad--hoc--Polymorphismus] erlaubt die Formulierung typgesteuerter 
Funktionen, die auf einer endlichen Menge verschiedener Typen arbeiten, die
keine gemeinsame Struktur besitzen. Die Ausf"uhrung solch einer Funktion h"angt
vom Typ des der Funktion "ubergebenen Parameters ab.
\end{description}

\noindent Beim {\em universellen} Polymorphismus unterscheidet man wiederum
\begin{description}
\item[Parametrischen Polymorphismus,] der die oben vorgestellten 
generischen Funktionen realisiert, die einen impliziten oder expliziten 
Typparameter erhalten, der den Typ jeder Anwendung der Funktion spezifiziert,
und
\item[Inklusionspolymorphismus,] der es erm"oglicht, ein Objekt als 
Mitglied verschiedener, nicht unbedingt disjunkter Klassen zu betrachten. Eine
Instanz des {\em Inklusions}poly\-mor\-phis\-mus ist der 
{\em Subtyp}polymorphismus \cite{Card84}, in dem ein Typ Subtyp eines 
anderen Typs ist (z.B. {\sl Student} $<$:{\sl Person}). In diesem Fall kann
"uberall dort, wo ein Wert vom Typ {\sl Person\/} erwartet wird, auch ein Wert
des Typs {\sl Student\/} verwendet werden.
\end{description}

\noindent Sowohl der parametrische als auch der {\rm Subtyp}
Polymorphismus sind in {\sf TL} in das statische Typsystem integriert. Da der
Kontext einer {\em ad--hoc}--polymorphen Funktion, in dem ein Wert erzeugt
wird, und der Kontext, in dem der Wert benutzt wird, keine gemeinsame statisch
"uberpr"ufbare Spezifikation besitzen, ben"otigen solche Anwendungen dynamische
Typisierung. Abbildung \ref{Saulen}\footnote{leicht modifiziert aus
\cite{Geis95} "ubernommen} illustriert die Arten des Polymorphismus, die in
{\sf TL} die S"aulen der generischen Programmierung darstellen.

\begin{figure}[tp]
\begin{center} \leavevmode
\epsfbox{polymorphismus.epsf}
%\epsfbox{polymorp.eps}
\end{center}
\caption{S"aulen der generischen Programmierung in {\sf TL}}
\label{Saulen}
\end{figure}

In den folgenden Abschnitten werden einige Beispiele f"ur generische, 
datenstrukturabh"angige Funktionen vorgestellt, die sich grob in folgende 
Anwendungsklassen unterteilen lassen:

\begin{itemize}
\item Meta--Level Operationen, die reflektives Wissen des Compilers 
ben"otigen
\item strukturierte Ein-- und Ausgabefunktionen
\item Generatoren, die unterschiedlichen Kode f"ur unterschiedliche 
Eingabetypen generieren
\item Bindungen an entfernte Prozeduraufrufe
\end{itemize}

\subsection{Meta--Level Operationen}
Als {\em Meta--Level Operationen} werden hier solche Operationen bezeichnet, 
die reflektives Wissen des Compilers ben"otigen. Ein typischer Vertreter 
solcher Operationen ist die Funk\-tion

\begin{xple}
\id{eval(sourceText :String)} :???
\end{xple}

\noindent die ein St"uck Programmkode erh"alt und unter Ausnutzung von 
Laufzeitreflektion (s. Abschnitt \ref{Reflektion}) "ubersetzt und ausf"uhrt. 
In untypisierten Sprachen wie {\sf Lisp} oder {\sf SNOBOL4} 
\cite{GPP71} l"a"st sich die {\em eval} Funktion ohne dynamische Typisierung 
realisieren. In typsicheren Sprachen wie {\sf TL} dagegen mu"s die Bindung 
eines {\em eval} Aufrufs an einen Bezeichner typgepr"uft werden. Wie durch die
Fragezeichen angedeutet ist, kann der Ergebnistyp dieses {\em eval} Aufrufes
jedoch nicht statisch ermittelt werden, da er vom "ubergebenen Programmkode
abh"angt. Deshalb mu"s als Ergebnis dieser Funktion ein automorpher Wert
erzeugt werden, der eine Typ"uberpr"ufung zur Laufzeit erm"oglicht.


\subsection{Strukturierte Ein-- und Ausgabe}
\label{strukturierte Ein-- und Ausgabe}
Im {\sf Tycoon}--System wird nicht nur der Quelltext, sondern auch der 
zugeh"orige, ausf"uhrbare Kode von Modulen und ihren Schnittstellen als 
separate Dateien abgespeichert. Dies erfordert zwei Funktionen:

\begin{xple} \id{extern(object :???  writeHdl :FileHandle)} :\kw{Ok} \end{xple}

\noindent schreibt ein im persistenten Speicher erzeugtes Objekt beliebigen
Typs linearisiert in eine Datei und

\begin{xple} \id{intern(readHandle :FileHandle) :???} \end{xple}

\noindent liest ein Objekt beliebigen Typs aus einer Datei in den
persistenten Speicher.

Das in eine Datei geschriebene Objekt mu"s die Eigenschaft besitzen, da"s es
selbstbeschreibend ist und somit keine Referenzen auf andere Objekte au"serhalb
der Datei enth"alt \cite{Card89}. Da automorphe Werte diese Eigenschaft
erf"ullen, sind beide Funktionen typische Anwendungen dynamischer Typisierung.
Um ein Objekt mittels der {\sl extern\/} Funktion in eine Datei schreiben zu 
k"onnen, mu"s ein Konstruktor existieren, der aus einem beliebigen Wert einen 
automorphen Wert erzeugt. Um andererseits auf einem Objekt, das aus einer 
Datei in den persistenten Speicher gelesen worden ist, Operationen ausf"uhren
zu k"onnen, mu"s eine weitere Operation existieren, die einen automorphen Wert
({\sl x}, $t_{S,T}$) auf einen Wert {\sl x\/} mit einem statischen Typ
$T^\prime$ in einem Kontext $S^\prime$ projiziert, wobei $T^\prime <:T$ in
$S^\prime$ gilt. Diese Operation f"uhrt also zur Laufzeit einen Typtest durch
und propagiert ein Ausnahmepaket, falls dieser Typtest fehlschl"agt.

Eine andere Form der strukturierten Ausgabe, die Gegenstand dieser Arbeit 
ist, ist die generische Visualisierung solcher Daten und Funktionen auf dem 
Bildschirm, die sich innerhalb des persistenten Speichers befinden. 
Um f"ur ein zu visualisierendes Objekt die entsprechende Darstellungsform 
generieren zu k"onnen, ist eine Typanalyse des Objektes notwendig. Da es 
jedoch potentiell unendlich viele verschiedene Typen innerhalb einer solch 
komplexen Sprache wie {\sf TL} gibt, l"a"st sich statisch nicht feststellen, 
welche Typen die zu visualisierenden Objekte eventuell haben k"onnen. Deshalb 
mu"s die generische Datenvisualisierung mittels automorpher Werte 
erfolgen, die eine Typanalyse zur Laufzeit erm"oglichen. Das gleiche Problem 
tritt bei der strukturierten Eingabe mittels generischer Editoren auf 
\cite{Mues94}. In beiden F"allen mu"s es einen Mechanismus geben, mittels 
dessen man die Struktur von Objekten inspizieren kann, um anhand ihrer 
Typinformationen entscheiden zu k"onnen, welche Operationen durchzuf"uhren 
sind.

\subsection{Generatoren}
Generatoren bilden ein weiteres Anwendungsgebiet f"ur dynamische Typsierung.
Ein Operator in relationalen Datenbanken ist der sogenannte Verbindungsoperator
{\em join}, der zwei Relationen kombiniert und dann denjenigen Teil der
Ergebnisrelation ausw"ahlt, der mindestens je ein Attribut gleichen Werts aus
jeder Relation enth"alt. Eine Verallgemeinerung davon ist der nat"urliche
Verbindungsoperator {\em natural join}, bei dem die Ergebnisrelation nur eines
der "uberlappenden Attribute enth"alt \cite{Schm87}. Ein Generator, der f"ur
zwei beliebige Relationen den Programmkode generiert, der die nat"urliche
Verbindungsoperation auf diesen beiden Relationen durchf"uhrt, l"a"st sich aus
folgenden Gr"unden nicht als generische Funktion realisieren \cite{SFSS90}:

\begin{itemize}
\item Die Konkatenierungsfunktion, die die Ergebnisrelation erzeugt, mu"s den 
Typ der Ergebnisrelation in Abh"angigkeit von den Typen der zu verbindenden
Relationen ermitteln.
\item Die Funktion, die zwei Tupelkomponenten auf Gleichheit "uberpr"uft mu"s
sowohl den Namen der jeweiligen Komponenten als auch deren Typ auf Gleichheit
testen. Die Namen und Typinformationen der Attribute sind jedoch erst zur
Laufzeit bekannt, so da"s der Test dynamisch erfolgen mu"s.
\item Die Funktion, die Tupel beider Relationen aggregiert und dabei nur 
ein Attribut der "uberlappenden Komponenten erzeugt, mu"s ebenfalls in der 
Lage sein, die Namen der Attribute und deren Typ auf Gleichheit zu testen.
\end{itemize}

\noindent Damit sind die Typen der Elemente beider Relationen statisch nicht 
festgelegt:

\begin{xple}
\id{joinGenerator(typ1, typ2 :???) :String}
\end{xple}

\noindent Dieses Beispiel macht deutlich, da"s ein Konzept zur dynamischen
Typisierung neben automorphen Werten auch Laufzeittyprepr"asentationen umfassen
mu"s.


\subsection{Bindungen an entfernte Prozeduraufrufe}
Eines der Ziele im {\sf Tycoon} Projekt ist es, das System so skalieren zu
k"onnen, da"s die Sprache {\sf TL} als Beschreibungssprache f"ur verteilte
Anwendungen genutzt werden kann \cite{MMS95a}. Dabei bilden synchrone entfernte
Prozeduraufrufe ({\em RPC}) die bevorzugte Technik f"ur die Entwicklung von
{\em Client--Server} Anwendungen \cite{Corb91}, da sie eine hohe Ebene der
Kommunikation zur Verf"ugung stellen, auf der Klientenprogramme Prozeduren aus
anderen, entfernten Anbieterprogrammen aufrufen k"onnen \cite{BiNe84}. Die
Auswahl des Anbieters sowie die Bindung an eine entfernte Prozedur erfolgen
dynamisch zur Laufzeit, da die Programme auf dem Anbieter und dem Klienten
unabh"angig voneinander entwickelt, "ubersetzt und gebunden werden. Das kann
dazu f"uhren, da"s die Signatur des Prozeduraufrufs durch den Klienten nicht
mit der Signatur der Prozedur des Anbieters "ubereinstimmt, so da"s die
Typkorrektheit des entfernten Prozeduraufrufs zur Laufzeit "uberpr"uft werden
mu"s, um die Typsicherheit gew"ahrleisten zu k"onnen. Damit bilden auch {\em
RPCs} eine typische Anwendung dynamischer Typisierung.



\subsection{Aufgaben dynamischer Typisierung}
\label{Aufgaben}
Aus den in den vorhergehenden Abschnitten vorgestellten Beispielen
lassen sich zwei wesentliche Arten von Anwendungen definieren, die
nur mittels dynamischen Typisierung realisierbar sind:

\begin{enumerate}
\item Die {\em Manipulation von Werten mit dynamischer Typinformation}, die
nicht statisch zur "Ubersetzungszeit bestimmt werden kann, ist
immer dann notwendig, wenn Werte, die au"serhalb der statischen
Umgebung des Typ"uberpr"ufers generiert werden, manipuliert werden
m"ussen. Zu dieser Art von Anwendungen geh"oren die {\em eval--,
intern--} und {\em extern}--Funktionen sowie Bindungen an enfernte
Prozeduraufrufe.
\item Das {\em Inspizieren von Typinformationen} zur Laufzeit ist
notwendig, um hochgenerische, datenstrukturabh"angige Algorithmen
zu entwickeln \cite{SFSS90,SSF92,Kirb92b}. Beispiele daf"ur sind
die generische Datenvisualisierung, die generische
Datenmanipulation und die Generatoren zum Erzeugen von
Programmkode.
\end{enumerate}

\noindent Um diesen Aufgaben gerecht zu werden, mu"s ein Konzept zur
Realisierung dynamischer Typisierung folgende Komponenten umfassen:

\begin{itemize}
\item {\em Datentypen} f"ur Laufzeittyprepr"asentationen und automorphe
Werte, sowie Konstruktoren zum Erzeugen von Werten dieser Datentypen,
\item einen {\em Projektionsoperator}, der einen automorphen Wert auf
seine Wertkomponente projiziert und dabei zur Laufzeit "uberpr"uft, ob der Typ,
den der Wert erhalten soll, ein Supertyp der Typkomponente des automorphen
Wertes ist,
\item Operationen zum {\em Inspizieren} von Laufzeittyprepr"asentationen
und automorphen Werten,
\item eine Operation, die einen {\em Subtyptest} auf
Laufzeittyprepr"asentationen durchf"uhrt, und
\item {\em Konstruktoren}, die aus Laufzeittyprepr"asentationen und
automorphen Werte strukturierte Laufzeittyprepr"asentationen und
automorphe Werte erzeugen
\end{itemize}


\section{Konzepte zur Realisierung dynamischer Typisierung}
In einer Reihe statisch typisierter Programmiersprachen sind bereits Konzepte 
f"ur die Integration dynamischer Typisierung realisiert worden. Dar"uber hinaus
gibt es theoretische Ans"atze, in denen die Interaktion zwischen statisch und
dynamisch "uberpr"uften Teilen einer Programmiersprache untersucht
werden. Diese Konzepte und Ans"atze werden in diesem Abschnitt vorgestellt und
anhand bestimmter Kriterien analysiert. Dazu werden im folgenden Abschnitt
zun"achst Ans"atze in monomorphen Sprachen vorgestellt. Besondere Probleme
ergeben sich bei der Behandlung abstrakter Datentypen und des Polymorphismus in
Verbindung mit dynamischer Typisierung, so da"s diese Aspekte jeweils in einem
eigenen Abschnitt behandelt werden.

\subsection{Dynamische Typisierung in anderen Sprachen}
\label{existierende Konzepte}
Die Analyse der betrachteten Sprachen orientiert sich im wesentlichen an den 
folgenden, f"ur die Entwicklung eines Konzepts zur dynamischen Typisierung 
in {\sf Tycoon} wichtigen Fragestellungen: 
\begin{itemize}
\item Welche Typen bietet die Sprache f"ur die dynamische Typisierung 
an?
\item Welche Sprachkonstrukte werden f"ur Operationen auf diesen Typen 
angeboten und welche Funktionalit"at wird durch diese bereitgestellt?
\item Welche zus"atzlichen Operationen existieren auf diesen Typen?
\end{itemize}
Ziel bei der Auswahl der Sprachen ist es, m"oglichst verschiedene
Konzepte und L"osungsans"atze vorzustellen. Andere Sprachen, die
ebenfalls "uber Konzepte zur dynamischen Typisisierung verf"ugen, die
hier aber nicht vorgestellt werden, sind {\sf CLU} \cite{LABM*81} und {\sf
Cedar/Mesa} \cite{Lamp83}, deren Hauptziel die Unterst"utzung von
Programmidionomen aus Lisp ist, sowie {\sf Modula-2$+$} \cite{Rovn86} zur
Integration persistenter Daten, und {\sf Modula-3} \cite{CDGJ*88,CDJK+89}, in
denen die Ans"atze aus {\sf Cedar/Mesa} direkt "ubernommen worden sind.

\subsubsection{Amber}
{\sf Amber} ist eine funktionale, polymorphe und modulare Sprache, bei deren 
Entwicklung eines der Hauptziele die Integration dynamischer Typisierung in 
eine statisch typisierte Sprache war. Sie kann auch als 
Systemprogrammiersprache verwendet werden \cite{Card86}.

{\em Dynamic} ist der Typ automorpher Werte in {\sf Amber}. Auf 
Werten dieses Typs existieren zwei Sprachkonstrukte:

\begin{xple}
\kw{dynamic} \id{e}
\kw{coerce} \id{e} \kw{to} \id{t}
\end{xple}

\noindent Mit {\sl dynamic\/} wird aus einem Wert {\sl e}, der einen beliebigen
Typ haben kann, ein automorpher Wert erzeugt. Falls ein automorpher Wert {\sl
e\/} den Typ {\sl t\/} hat, so kann man diesen Wert mittels {\sl coerce\/} auf 
einen Wert des Typs {\sl t\/} projizieren. Dazu erfolgt zur Laufzeit eine
Typ"uberpr"ufung zwischen der Typkomponente des automorphen Wertes {\sl e\/}
und dem Typ {\sl t\/}, die im Fehlerfall einen Laufzeitfehler erzeugt.

Die Hauptanwendung automorpher Werte in {\sf Amber} ist die 
Handhabung persistenter Daten, die mittels {\sl extern\/} als automorpher Wert 
im Dateisystem gespeichert und mittels {\sl intern\/} geladen werden
\cite{ACPP89}.

Die Verwendung von {\em coerce} ist nur dann sinnvoll, wenn der Typ des 
automorphen Wertes bereits bekannt ist. Ist dies jedoch nicht der Fall, so 
bietet {\sf Amber} noch eine Reihe von Primitiven zum Inspizieren und 
Manipulieren automorpher Werte mit unbekanntem Typ. Das Primitiv 
{\sl typeOf\/} liefert eine Kodierung des Typs eines dynamisch typisierten 
Wertes {\sl val\/}, indem der Typ von {\sl val\/} um einen Schritt expandiert 
wird. Handelt es sich dabei nicht um einen Basistyp, so kann man die Struktur 
des Typs noch weiter analysieren. Weitere Primitive erlauben das schrittweise 
Expandieren eines automorphen Wertes, dessen Typ kein Basistyp ist.
Beispielsweise gibt das Primitiv {\sl exposeRecord\/}, falls es sich bei dem
"ubergebenen automorphen Wert um einen {\sl Record\/} handelt, eine Liste
zur"uck, deren Elemente jeweils aus dem Namen und dem automorphen Wert einer
Komponente des {\sl Records\/} bestehen. Analog existieren Primitive f"ur
Varianten, Felder, Werte mit rekursivem Typ und Funktionen mit einem
"Ubergabeparameter.

\subsubsection{CAML}
{\sf CAML} \cite{Weis90}, eine Implementierung von {\sf ML} \cite{MTH90}, ist 
eine funktionale, polymorphe Programmiersprache, die gegen"uber {\sf ML} um 
ein Konzept zur dynamischen Typisierung erweitert worden ist \cite{LeMa91}.
{\sf ML} ist eine implizit typisierte Programmiersprache. Das bedeutet, da"s 
bei der Typ"uberpr"ufung jeweils der generellste Typ f"ur einen Wert 
inferiert wird. Dar"uber hinaus existiert das Konzept der Muster"uberpr"ufung,
das den Vergleich des Formats eines Wertes mit dem Format einer Schablone
erlaubt.

In {\sf CAML} gibt es einen vordefinierten Datentyp {\em dyn}, der diejenigen 
Werte repr"asentiert, die bez"uglich ihres Typs selbstbeschreibend sind. Er 
entspricht damit dem Typ {\em Dynamic} in {\sf Amber}. Auf Werten des Typs 
{\em dyn} gibt es das Konstrukt {\em dynamic e}, das den Ausdruck {\sl e\/} 
evaluiert und aus dem Evaluationsergebnis einen automorphen Wert 
erzeugt. 

Da das Binden von Werten an Bezeichner und die Fehlerbehandlung bereits durch 
die Muster"uberpr"ufung abgedeckt sind, wird in {\sf CAML} kein dem {\em
coerce} in {\sf Amber} entsprechendes Konstrukt ben"otigt. Stattdessen
existiert eine zus"atzliche Art von Mustern, n"amlich die dynamischen Muster:

\begin{xple}
\kw{dynamic}(\id{p :$\tau$})
\end{xple}

\noindent Solch ein Muster selektiert alle automorphen Werte, deren 
Wertkomponente dem Muster {\em p} entspricht und deren Typkomponente 
genereller als der Typausdruck {\em $\tau$} ist. 

Mit Hilfe dieses Konzeptes zur dynamischen Typisierung sind in {\sf CAML} 
unter anderem die Funktionen {\sl extern\/}, {\sl intern\/} und {\sl print\/} 
zum Ausdrucken eines automorphen Wertes auf dem Bildschirm in 
{\sf ML} Syntax realisiert.


\subsubsection{Napier88}
{\sf Napier88} \cite{MBC*94} ist wie {\sf Tycoon} ein persistentes, 
polymorphes Programmiersystem. Es existiert ein vordefinierter Datentyp 
{\em any}, der der Typ der Vereinigung aller Werte ist. Auf Werten dieses 
Datentyps gibt es zwei Operationen:

\begin{xple}
\kw{any}(Ausdruck)
\kw{project} Ausdruck \kw{as} \id{Bezeichner} \kw{onto} Projektionsliste 
					    \kw{default} :Ausdruck
\end{xple}

\noindent Mittels der Operation {\bf any\/} k"onnen Ausdr"ucke explizit in den
Typ {\em any} eingef"ugt werden. Die Operation {\bf project} erlaubt eine
Projektion eines Wertes des Typs {\em any} auf einen Wert, der an den nach dem
Schl"usselwort {\em as} angegebenen Bezeichner {\sl Id\/} gebunden wird. In der
Projektionsliste, jeweils bestehend aus einem Typbezeichner und einem Ausdruck,
k"onnen mehrere Alternativen angegeben werden. Der G"ultigkeitsbereich des
Bezeichners {\sl Id\/} ist auf den Ausdruck der jeweiligen Alternative
beschr"ankt. Dieser Mechanismus verhindert Seiteneffekte auf dem projizierten
Wert w"ahrend der Evaluation dieses Ausdrucks und erm"oglicht eine statische
Typ"uberpr"ufung innerhalb dieses Ausdrucks. Zur Laufzeit erfolgt eine
Typ"uberpr"ufung des Typs des zu projizierenden Ausdrucks mit den
Typbezeichnern der verschiedenen Alternativen. Bei dem ersten erfolgreichen
Typtest wird der zugeh"orige Ausdruck ausgef"uhrt. Ist f"ur keine Alternative
der Projektionsliste der Typtest erfolgreich, so wird der Ausdruck nach dem
Schl"usselwort {\em default} ausgef"uhrt. Die {\em project} Operation
entspricht damit den dynamischen Mustern in {\sf CAML}. Dar"uber hinaus
existiert noch eine weitere Funktion: 

\begin{xple}
\id{getTypeRep} : \kw{proc}(\id{any} $\rightarrow$ \id{TypeRep})
\end{xple}

\noindent Sie erh"alt als Parameter einen Wert des Typs {\em any} und liefert
eine Typrepr"asentation des Wertes zur"uck, durch deren Manipulation es
m"oglich ist, die  Typbeschreibungsinformation eines {\em any} zu untersuchen
\cite{SMKC93}. Mittels weiterer Hilfsfunktionen, die auf der Kenntnis der
Objektformate von Werten beruhen (s. Abschnitt \ref{Objektformate}), kann man
anhand dieser Strukturinformationen die Wertkomponente eines automorphen Wertes
inspizieren \cite{KiDe90}. Allerdings sind diese Hilfsfunktionen in der {\sf
Napier88} Standardbibliothek nicht enthalten \cite{KBC*94}. Somit stehen dem
Anwendungsprogrammierer keine Operationen zum Inspizieren von Werten des Typs
{\sl any\/} zur Verf"ugung. {\sf Napier88} stellt statt dessen als Alternative
die Nutzung linguistischer Laufzeitreflektion zur Verf"ugung, mit deren Hilfe
sich u. a. generische, typgesteuerte Anwendungen realisieren lassen
(s. Abschnitt \ref{Reflektion}).

\subsubsection{Ansatz von Abadi, Cardelli, Pierce und Plotkin}
In diesem Ansatz \cite{ACPP89} werden ein neuer Basistyp {\em Dynamic}
f"ur automorphe Werte sowie die beiden Operationen

\begin{xple}
\kw{dynamic}(\id{a :T})
\kw{typecase} \id{a} \kw{of} \id{Projektionsliste} \kw{else} \id{c}
\end{xple}

\noindent in die statisch typisierte Sprache eingef"uhrt. Die Operation  {\bf
dynamic} konstruiert einen automorphen Wert aus einem Wert {\sl a\/} mit Typ
{\sl T\/}. Die Operation {\bf typecase} dient wie die {\em project} Operation
in {\sf Napier88} zum Inspizieren von dynamisch typisierten Werten. Der
Unterschied zu der {\em project} Operation liegt aber in der M"oglichkeit, vor
einem Projektionszweig Mustervariablen erster Ordnung $V_i$ definieren zu
k"onnen, die zu jedem Subausdruck innerhalb des Typausdrucks des zugeh"origen
Zweiges passen. Ihr G"ultigkeitsbereich erstreckt sich auf den gesamten
Zweig. Dadurch wird die Ausdrucksm"achtigkeit von {\em typecase} erh"oht. So
l"a"st sich im Gegensatz zu {\em project} in einer Funktion, die aus Werten
beliebigen Typs eine Zeichenkettenrepr"asentation erzeugt, innerhalb eines
einzigen Zweiges von {\em typecase} eine Vorschrift f"ur Tupel mit zwei
Komponenten definieren, deren beide Komponenten einen beliebigen Typ haben
k"onnen:\footnote{In diesem Beispiel wird eine {\sf TL} Syntax verwendet, die
um die eben vorgestellten Typen und Konstrukte erweitert ist.} 

\begin{xple}
\kw{let rec} \id{toString(val :Dynamic) :String} =
   \kw{typecase} \id{val} \kw{of}
       ...
       \id{(X,Y) (v} :\kw{Tuple} \id{x :X  y :Y} \kw{end})
         ``$<$'' $<>$ \id{toString(}\kw{dynamic} \id{(v.x :X))}
         $<>$ \id{toString(}\kw{dynamic} \id{(v.y :Y))} $<>$ ``$>$''
       ...
   \kw{end}
\end{xple}

\noindent Um die Funktion {\sl toString\/} rekursiv innerhalb des
Evaluationsausdrucks des Projektionszweiges aufrufen zu k"onnen, m"ussen
aus den Komponenten des Tupels wieder automorphe Werte erzeugt
werden. Dies ist m"oglich, da die Mustervariablen {\sl X\/} und {\sl Y\/}
erst zur Laufzeit an die entsprechenden Typen gebunden werden. Weitere
Konstrukte zum Inspizieren von automorphen Werten werden in
diesem Ansatz nicht vorgestellt, da das theoretische Interesse dieses
Ansatzes in der Interaktion zwischen den durch {\em typecase} erlaubten
statisch und dynamisch typ"uberpr"uften Teilen der Sprache liegt.

\subsubsection{Zusammenfassung}
Allen hier vorgestellten Ans"atzen ist gemein, da"s sie ein Konzept zur
Manipulation automorpher Werte anbieten. Die Entwicklung generischer, 
datenstrukturabh"angiger Algorithmen ist jedoch nur mit dem Ansatz von 
{\sf Amber} sowie mittels sprachlicher Laufzeitreflektion in {\sf Napier88}
m"oglich. Weitere Unterschiede ergeben sich durch die Ausdrucksm"achtigkeit 
des jeweiligen Projektionsoperators. So ist es in dem Ansatz von 
\cite{ACPP89} durch die Einf"uhrung von Mustervariablen erster Klasse in 
eleganter Weise m"oglich, viele "ahnliche Zweige von {\bf typecase} in einem 
einzigen Zweig zusammenzufassen. Dies erlaubt es einerseits, die Anzahl der 
Zweige in {\bf typecase} zu reduzieren, andererseits wird dessen 
Wiederverwendbarkeit erh"oht. 


\subsection{Dynamische Typisierung und Polymorphismus}
\label{Polymorphismus}
In Programmiersprachen, in denen das Konzept des parametrischen 
Polymorphismus realisiert ist, und in denen Funktionen Werte erste Klasse 
darstellen, ist es ohne Einschr"ankungen m"oglich, automorphe Werte von 
polymorphen Funktionen zu erzeugen. Problematisch ist dagegen jedoch die 
Frage, ob in automorphen Werten die Typvariablen mit Ausnahme von 
Mustervariablen geschlossen sein m"ussen, oder ob es erlaubt ist, automorphe
Werte von solchen Werten zu erzeugen, bei deren Typ es sich um eine 
universell oder existentiell quantifizierte Typvariable aus dem umgebenden 
Kontext handelt \cite{ACPR92}:

\begin{xple}
\kw{let} \id{f(A $<$:}\kw{Ok} \id{a :A)} = \kw{dynamic}(\id{a})
\end{xple}

\noindent Die in diesem Beispiel definierte polymorphe Funktion {\sl f\/} soll
aus dem Parameter {\sl a\/}, deren Typ die universell quantifizierte
Typvariable {\sl A\/} ist, einen automorphen Wert erzeugen und diesen
zur"uckgeben. Da die polymorphe Typvariable {\sl A\/} aber erst bei der
Applikation von {\sl f\/} instantiiert wird, ist statisch nur bekannt, da"s
{\sl a\/} den Typ {\bf Ok} besitzt. Diese Funktion w"urde also
f"alschlicherweise als Ergebnis immer einen automorphen Wert liefern, deren
Typkomponente aus einer Repr"asentation des Typs {\bf Ok} besteht. Deshalb
k"onnten in automorphen Werten nur geschlossene Typvariablen erlaubt werden.
Dies w"urde jedoch zu einer erheblichen Einschr"ankung der M"achtigkeit
automorpher Werte in polymorphen Programmiersprachen f"uhren. Eine andere
L"osungsm"oglichkeit besteht darin, die polymorphe Funktion um einen
zus"atzlichen Parameter zu erweitern, der eine Laufzeitrepr"asentation der
jeweils "ubergebenen Typvariablen darstellt, die dann in die Typkomponente der
automorphen Werte eingesetzt wird. So w"urde bei der Applikation von {\sl f\/}
auf den Wert 3 zur Laufzeit eine Typrepr"asentation des Typs von 3, also von
{\sl Int\/}, erzeugt werden, die als Typkomponente in den automorphen Wert
eingesetzt wird.

Ein weiteres Problem, das sich in Programmiersprachen mit explizitem 
Polymorphismus im Zusammenhang mit automorphen Werten ergibt, entsteht durch 
deren zus"atzliche sprachliche Ausdrucksm"achtigkeit. Gegen"uber monomorphen
erh"oht sich in polymorphen Programmiersprachen die Anzahl der definierbaren 
Typen um ein Vielfaches. Das bedeutet, da"s sich auch die Anzahl der Typen 
erh"oht, auf die ein automorpher Wert projiziert werden kann. Die bisher 
vorgestellten Konzepte reichen jedoch nicht aus, um innerhalb von 
Projektionslisten in geeigneter Weise gegen polymorphe Typvariablen zu testen. 
In \cite{ACPR92} wird ein Konzept vorgestellt, um diesem Problem zu begegnen. 
Es erweitert die in \cite{ACPP89} vorgestellten Mustervariablen erster Ordnung 
zum Vergleichen von Typen um Mustervariablen h"oherer Ordnung. Diese decken 
den Kontext von Mustern ab, d.h. es handelt sich dabei um Muster, die "uber 
eine bestimmte Menge von Typvariablen abstrahieren. 

\begin{xple}
\kw{let} \id{dynApply(f} :\kw{Dynamic}  \id{x} :\kw{Dynamic}) =
   \kw{typecase} f \kw{of}
   \id(F,G) \id{g} :\kw{Fun}(\id{A} $<$:\kw{Ok}  \id{a} :\id{F(A)}) :\id{G(A)}
      \kw{typecase} x \kw{of}
      \id{(W)} \id{a} :\id{F(W)}  \kw{dynamic}(\id{g}(:\id{W a}) :\id{G(W)})
      \kw{else} \kw{raise exception} ``falsche Parameter'' \kw{end}
   \kw{else} \kw{raise exception} ``falsche Parameter'' \kw{end}
   
\id{dynApply}(\kw{dynamic}(\kw{fun}(\id{A} $<$:\kw{Ok}  \id{x :A}) \id{x}) \kw{dynamic}(3)))
\id{dynApply}(\kw{dynamic}(\kw{fun}(\id{A} $<$:\kw{Ok}  \id{x :} \kw{Tuple} \id{y :A  z :A} \kw{end}) \kw{tuple} \id{x.z x.y} \kw{end})
	      \kw{dynamic}(\kw{tuple} 1 2 \kw{end}))
\end{xple}

\noindent Im obigen, in {\em TL} "ahnlicher Syntax beschriebenen Beispiel,
stellen {\sl F\/} und {\sl G\/} Mustervariablen h"oherer Ordnung und  {\sl W\/}
eine Mustervariable erster Ordnung dar. Sie erm"oglichen die beiden Anwendungen
von {\sl dynApply}. 


\subsection{Dynamische Typisierung abstrakter Datentypen}
\label{ADT}
Abstrakte Datentypen dienen dazu, Informationen zu verstecken und modulare 
Programmierung zu erm"oglichen. Formal kann man abstrakte Datentypen  
als existentielle Typen betrachten \cite{MiPl88}, wodurch sie als Objekte
erster Klasse behandelt werden k"onnen, die dem Programmierer in einer
persistenten Programmierumgebung orthogonale Persistenz sichern \cite{OTCP90}.
Um diese Betachtungsweise zu formalisieren, sind zwei Typregeln {\sl Pack\/}
und {\sl Open\/} notwendig \cite{ACPR92}. Mittels der Typregel {\sl Pack} wird
die tats"achliche Struktur eines abstrakten Datentyps in einem Paket versteckt.
Nur innerhalb des speziellen Ausdrucks {\bf open} ist diese sichtbar und kann
mittels einer festen, explizit spezifizierten Menge von
Schnittstellenfunktionen auf sie zugegriffen werden. Da die Typ"uberpr"ufung
abstrakter Datentypen nicht strukturell erfolgt, gilt in folgendem Beispiel

\begin{xple}
\kw{Let} \id{ADT} = \kw{Tuple} \id{T} $<$:Ok ....  \kw{end}
\kw{let} \id{adt :ADT} = \kw{Tuple Let} \id{T} = \kw{Tuple end} ...  \kw{end}
\kw{let} \id{adt1} = \id{adt}
\end{xple}

\noindent {\sl adt.T} $\not<$: {\sl adt1.T}. Im Zusammenhang mit automorphen
Werten ergibt sich jedoch die Fragestellung, ob bei abstrakten Datentypen die 
Typ"uberpr"ufung abstrakt oder strukturell erfolgen soll \cite{ACPR92}. F"ur 
beide Entscheidungen gibt es gute Gr"unde:

\begin{enumerate}
\item Die abstrakte Typ"uberpr"ufung versteckt weiterhin die 
Typrepr"asentation des abstrakten Datentyps und verhindert so eine zuf"allige
Typgleichheit in den F"allen, in denen verschiedene abstrakte Datentypen die 
gleiche Repr"asentation besitzen.
\item Die strukturelle Typ"uberpr"ufung erlaubt es, automorphe Werte eines 
abstrakten Datentyps als Werte verschiedener Versionen des gleichen 
abstrakten Datentyps zu behandeln. Dies ist z.B. in {\sl Client--Server}
Umgebungen unverzichtbar, auf denen automorphe Werte des gleichen abstrakten
Datentyps auf verschiedenen Rechnern erzeugt und ausgetauscht werden.
\end{enumerate}

\noindent In \cite{ACPR92} wird eine L"osung dieses Problems vorgestellt, die
beide Arten der Typ"uberpr"ufung unterst"utzt, indem eine erweiterte Typregel
{\em Open} zum Entpacken eines existentiellen Typs eingef"uhrt wird. Sie
erlaubt es innerhalb von {\bf typecase}, alternativ die Struktur des abstrakten
Datentyps zu inspizieren oder die Typabstraktion weiterhin zu gew"ahrleisten.


\section{Realisierung dynamischer Typisierung in TL}
In diesem Abschnitt wird der in {\sf TL} realisierte Ansatz beschrieben, der
die in Abschnitt \ref{Aufgaben} definierten Aufgaben dynamischer Typisierung
unter Ber"ucksichtigung der in Abschnitt \ref{existierende Konzepte}
vorgestellten Ans"atze und Probleme umsetzt. Dazu werden zun"achst der
urspr"unglich in {\sf TL\/} entwickelte Ansatz \cite{MaSc92} sowie dessen
bei der Implementierung festgestellten Nachteile diskutiert. Die bei der
Realisierung dieses Ansatzes gesammelten Erfahrungen trugen zu der in dieser
Arbeit realisierten L"osung bei.


\subsection{Urspr\protect"unglicher Ansatz}
\label{erster Ansatz}
In diesem Ansatz werden zwei Sprachkonstrukte definiert, um die Aufgaben
dynamischer Typisierung (s. Abschnitt \ref{Aufgaben}) zu unterst"utzen:

\begin{itemize}
\item Die Signatur einer Typvariablen {\sl T\/} kann mit dem
Schl"usselwort {\bf Dyn} versehen werden. Solch eine Typvariable
kann wie eine Wertvariable zur Laufzeit inspiziert werden, um Informationen
"uber die Struktur des tats"achlich an {\sl T\/} gebundenen Typs zu erhalten.
\item Typvariablen k"onnen mittels des Konstrukts {\bf typecase} inspiziert 
werden. Innerhalb der Zweige des Konstrukts {\bf typecase} wird die 
Typvariable auf einen statisch bekannten Typ eingeschr"ankt, so da"s dort die
Typ"uberpr"ufung statisch erfolgen kann.
\end{itemize}

\noindent Automorphe Werte lassen sich erzeugen, indem Wertbindungen mit
ihren zugeh"origen Typinformationen aggregiert werden
\cite{Matt93}:

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

\id{asString(a :Auto) :String =}
   \kw{typecase} \id{a.T}
   \kw{when} \id{Int} \kw{then} \id{fmt.int(a.x)}
   \kw{when} \id{String} \kw{then} \id{a.x}
   \kw{else} ``???''
   \kw{end}

\id{asString(a1)   asString(a2)}
\end{xple}

\noindent Im Unterschied zu den in Abschnitt \ref{existierende Konzepte} 
vorgestellten Ans"atzen mu"s ein individueller Wert nicht explizit in einen 
infiniten Vereinigungstyp injiziert und aus diesem wieder auf seine 
Wertkomponente projiziert werden, um eine Typanalyse durchzuf"uhren. 
Insbesondere ist es damit auch m"oglich, eine reflektive Typanalyse 
durchzuf"uhren, wenn kein automorpher Wert, sondern nur eine 
Laufzeittyprepr"asentation, vorliegt.

Dieser Ansatz bringt jedoch drei entscheidende Einschr"ankungen mit sich, die
dazu f"uhrten, da"s er nicht weiterverfolgt wurde:

\begin{enumerate}
\item Die Eigenschaften des Konstrukts {\bf typecase} sind wie in
den meisten anderen vorgestellten Ans"atzen nicht ausreichend, um algorithmisch
vollst"andigen Kode f"ur generische, datenstrukturabh"angige Anwendungen zu
schreiben. Das Konstrukt {\bf typecase} ist beschr"ankt auf
Programmsituationen, in denen der Subtyptest einer
Laufzeittyp\-re\-pr"a\-sen\-ta\-tion auf einer endlichen Menge statischer Typen
durchgef"uhrt wird.
\item Da es in {\sf TL} eine Vielzahl von Typhierarchien gibt
(s. Abschnitt \ref{Typhierarchien}), "uber die aber nicht mit Hilfe einer 
{\em Kind} Spezifikation quantifiziert werden kann, m"u"ste man f"ur jede
Typhierarchie eine eigene Funktion zum Inspizieren von Typen bereitstellen:

\begin{xple}
\kw{let} \id{inspectType}(\kw{Dyn} \id{T} $<$:\kw{Ok}) = ...
\kw{let} \id{inspectTypeOper1}(\kw{Dyn} \id{T} $<$:\kw{Oper}(\id{X} $<$:\kw{Nok}) \kw{Ok}) = ...
\kw{let} \id{inspectTypeOper2}(\kw{Dyn} \id{T} $<$:\kw{Oper}(\id{X} $<$:\kw{Nok}  \id{Y} $<$:\kw{Nok}) \kw{Ok}) = ...
\end{xple}

Stattdessen m"ochte man eine generische Funktion mit einer passenden Signatur
schreiben, z.B.

\begin{xple}
\kw{let} \id{inspectAnyType}(\kw{Dyn} \id{T} $<$:???) = ...
\end{xple}

\item Die Kodegenerierung f"ur dynamische Typvariablen f"uhrt
einige versteckte Komplexit"at in den {\sf TL} Sprachprozessor
ein.
\end{enumerate}

\noindent Aufgrund dieser Nachteile wurde im Rahmen dieser Arbeit ein neuer
Ansatz entwickelt, der dem minimalistischen Ansatz von {\sf TL} folgt, Namen,
Konstanten und Funktionen vordefinierter Datentypen aus Modulen der {\sf
Tycoon} Standardbibliothek zu importieren, indem die Verwaltung von 
Laufzeittyprepr"asentationen explizit gemacht und in {\sf TL} Bibliotheken
herausfaktorisiert wird.


\subsection{Spracherweiterungen in TL}
\label{Spracherweiterungen}
Der hier vorgestellte, zur "Ubersetzungszeit reflektive Ansatz (siehe Abschnitt
\ref{Reflektion}) macht Laufzeittyp\-re\-pr"a\-sen\-ta\-tion\-en f"ur
algorithmisch vollst"andige Berechnungen unter Ber"ucksichtigung der Tatsache
zug"anglich, da"s {\sf TL} eine Programmiersprache h"oherer Ordnung ist. Dazu
wird {\sf TL} um folgende Typen und Anweisungen erweitert:

\begin{enumerate}
\item Neue Basistypen {\sl typeRep\_T\/} und {\sl dynamic\_T\/}
f"ur Laufzeittyprepr"asentationen bzw. automorphe Werte.
\item Konstruktoren {\sl typeRep\_new\/} und {\sl dynamic\_new\/}
zum Erzeugen von Werten dieser Typen.
\item Eine zu {\sl dynamic\_new\/} inverse Operation
{\sl dynamic\_be}, die zur Laufzeit aus einem automorphen Wert die
Wertkomponente extrahiert.
\item Polymorphe Typvariablen k"onnen innerhalb einer Funktionssignatur mit dem
Schl"usselwort {\bf Dyn} versehen
werden.
\end{enumerate}

\noindent Laufzeittyprepr"asentationen sind Werte erster Klasse, die einen
statischen Typ repr"asentieren. Die verwendete Notation bei den Typen und
Anweisungen soll andeuten, da"s es in entsprechenden Modulen weitere
Operationen auf diesen Typen gibt. Sie lassen sich jedoch nicht innerhalb von
Bibliotheksmodulen realisieren, da {\sf TL} nicht "uber eine {\em Kind}
Spezifikation verf"ugt (s. Abschnitt \ref{erster Ansatz}), und da die
Anweisungen auf interne Datenstrukturen des Compilers zugreifen. Die
Anweisungen lassen sich aber in folgender Pseudonotation spezifizieren:
 
\begin{xple}
\id{typeRep\_new(T} ::\kw{ANYTYPE}) :\id{typeRep\_T}
\id{dynamic\_new(T} $<$:\kw{Ok}  \id{v :T) :dynamic\_T}
\id{dynamic\_be(d :dynamic\_T  T} $<$:\kw{Ok}) :\id{T}
\end{xple}

\noindent Hierbei soll durch {\bf ANYTYPE} \label{ANYTYPE} ausgedr"uckt werden, da"s es sich
bei {\sl T\/} um einen beliebigen Typ des Typsystems handeln kann.
Durch die Syntax wird bei {\sl typeRep\_new\/} und {\sl dynamic\_be\/} die
Angabe des Typparameters erzwungen. Bei {\sl dynamic\_new\/} dagegen wird die
Typkomponente des automorphen Wertes aus dem "ubergebenen Wert inferiert und
braucht deshalb nicht mit "ubergeben zu werden.

Die Funktion {\sl dynamic\_be} erh"alt den automorphen Wert {\sl d\/} und 
die Typvariable {\sl T\/}, die ein geschlossener Typ sein mu"s, d.h. nicht
quantifiziert sein darf. Die Ausnahme {\sl dynamic.error} wird zur Laufzeit
ausgel"ost, wenn der Typ der Wertkomponente von {\sl v\/} kein Subtyp von {\sl
T\/} ist. Diese Anweisung hat nicht die Ausdrucksm"achtigkeit wie {\bf
typecase} in dem Ansatz von \cite{ACPR92}, da die Einf"uhrung von
Mustervariablen erster und h"oherer Ordnung die Komplexit"at des {\sf
TL}--Sprachprozessors erheblich erh"oht h"atte und da diese L"osung f"ur die in
Abschnitt \ref{Anwendungen} vorgestellten Anwendungen dynamischer Typisierung
ausreichend ist.

Polymorphe Typvariablen, die mit dem Schl"usselwort {\bf Dyn}
gekennzeichnet sind, d"urfen innerhalb von Laufzeittyprepr"asentationen
verwendet werden: 

\begin{xple}
\kw{let} \id{makeDyn}(\kw{Dyn} \id{T} $<$:\kw{Ok}  \id{x :T}) = \id{dynamic\_new(x)}
\id{makeDyn}(3)  \id{makeDyn(list.singleton(3))}
\end{xple}

\noindent Das Erzeugen von Laufzeittyprepr"asentationen aus polymorphen
Typvariablen, die nicht durch das Schl"usselwort {\bf Dyn} gekennzeichnet sind,
ist jedoch verboten und f"uhrt zur "Ubersetzungszeit zu einem Typfehler.

Eine weitere Einschr"ankung bei der Erzeugung von automorphen Werten bilden
Uni\-fi\-ka\-tions\-var\-i\-a\-blen. Diese werden innerhalb des {\sf TL} Typ"uberpr"ufers
zum Instantiieren von Typbindungen in Typoperatorapplikationen eingef"uhrt.

\begin{xple}
\kw{let} \id{x = list.new()}         (* x :list.T(E') *)
\kw{let} \id{y = list.cons(13 x)}   (* x :list.T(Int) *)
\kw{let} \id{z = list.cons(`A' x)}  (* Typfehler!! *)
\end{xple} 

\noindent Damit ist es wie in der Bindung von {\sl x\/} m"oglich, Werte zu
erzeugen, deren Typ eine Typoperatorapplikation mit einer nichtinstantiierten
Unifikationsvariable ist. Sp"ater kann dann die Unifikationsvariable mit
einer Typbindung instantiiert werden, wie dies in der Bindung von {\sl y\/}
implizit mit dem Typ {\sl Int\/} erfolgt. Danach ist es nicht mehr erlaubt, die
Unifikationsvariable mit einer anderen Typbindung zu instantiieren, so da"s
die Bindung von {\sl z\/} zu einem Typfehler f"uhrt. Unifikationsvariablen
innerhalb von Laufzeittyprepr"asentationen f"uhren zu Abh"angigkeiten zwischen
statischen Typen und Laufzeittyprepr"asentationen, wie das folgende Beispiel
illustriert:

\begin{xple}
\kw{let} \id{x = list.new()}
\kw{let} \id{d = dynamic\_new(x)}                 (* d :list.T(E') *)
\kw{let} \id{s = dynamic\_be(d :list.T(Int))}    (* d :list.T(Int) *)
\kw{let} \id{y = list.cons(`A' x)}                   (* Typfehler !! *)
\end{xple}

\noindent Da Laufzeittyprepr"asentationen jedoch unabh"angig von einem
statischen Kontext sein sollen, sind Unifikationsvariablen innerhalb von
Laufzeittyprepr"asentationen verboten.


\subsection{Programmierschnittstellen}
Um generische, datenstrukturabh"angige Programme entwickeln zu k"onnen, werden
aufbauend auf diesen Spracherweiterungen die beiden Module {\sl typeRep\/} und
{\sl dynamic\/} in der {\sf Tycoon} Standardbibliothek {\sl tl\_reflective\/}
zur Verf"ugung gestellt. Diese implementieren Funktionalit"at zum Inspizieren
und Konstruieren von Laufzeittyprepr"asentationen und automorphen Werten
sowie einige Hilfsfunktionen. Dazu bedienen sie sich internen Wissens "uber die
Darstellung von Laufzeittyprepr"asentationen durch den Compiler. Sie selbst
sind aber nicht Bestandteil des Compilers (s. Abb. \ref{Kopplung}).

\begin{figure}[htp]
\begin{center} \leavevmode
\epsfbox{kopplung.epsf}
%\epsfbox{kopplung.eps}
\end{center}
\caption{Kopplung des API f"ur dynamische Typen an den Compiler}
\label{Kopplung}
\end{figure}


\subsubsection{Schnittstelle `TypeRep'}
Diese Schnittstelle (vgl. Anhang \ref{TypeRep}) bietet Operationen auf
Laufzeittyp\-re\-pr"a\-sen\-ta\-tion\-en an. Sie unterst"utzt die Inspektion
von Typinformationen zur Laufzeit, eine der beiden Anforderungen an dynamische
Typen. Dazu werden die folgenden Typen und Funktionen exportiert:

\begin{itemize}
\item Der Typ {\sl T\/} ist der Typ einer Laufzeittyprepr"asentation f"ur
einen beliebigen Typ der verschiedenen {\sf TL} Typhierarchien (vgl. {\bf
ANYTYPE} auf Seite \ref{ANYTYPE}). Er entspricht dem Basistyp {\sl typeRep\_T}
und sollte an dessen Stelle innerhalb von {\sf TL} Programmen verwendet werden.
\item Der Typ {\sl Expansion\/} ist eine detaillierte Beschreibung einer
Laufzeittyprepr"asentation.
\item Die Funktion {\sl inspect\/} erm"oglicht eine strukturierte Analyse 
einer Laufzeittyprepr"asentation, indem diese um einen Schritt expandiert 
wird.
\item Zu jedem {\sf TL} Basistyp existiert eine Laufzeittyprepr"asentation.
\item Die {\sl isSubType\/} Funktion macht die Subtyptestfunktion des
Compilers f"ur Lauf\-zeit\-typ\-re\-pr"a\-sen\-ta\-tion\-en f"ur
Anwendungsprogrammierer zug"anglich.
\item Mit Hilfe einer Reihe von Konstruktoren ist es m"oglich, f"ur jeden
strukturierten {\sf TL} Typ eine Laufzeittyprepr"asentation aus
Komponenten existierender Laufzeittyprepr"asentationen zu erzeugen. Der
Unterschied zu {\sl typeRep\_new} liegt darin, da"s diese Konstruktoren keinen
statischen Typ erwarten. Damit ist es m"oglich, Laufzeittyprepr"asentationen
von Typen zu erzeugen, von denen kein statischer Typ existiert.
\item Einige zus"atzliche Hilfsfunktionen erleichtern dem Programmierer die
Arbeit mit Lauf\-zeittyprepr"asentationen. So expandiert z.B. die Funktion
{\sl exposed} eine Lauf\-zeittyp\-re\-pr"a\-sen\-ta\-tion so lange, bis es
sich nicht mehr um einen Typbezeichner handelt.
\end{itemize}

\subsubsection{Schnittstelle `Dynamic'}
Die L"osung der anderen Anforderung an dynamische Typen --- die Manipulation
automorpher Werte --- wird von der Schnittstelle {\sl Dynamic\/}
(s. Anhang \ref{Dynamic}) unterst"utzt. Sie exportiert folgende Typen und 
Funktionen:

\begin{itemize}
\item Der Typ {\sl T\/} ist der Typ automorpher Werte in {\sf TL}. Er
entspricht dem {\sf TL} Basistyp {\sl dynamic\_T\/} und sollte an dessen
Stelle in {\sf TL} Programmen benutzt werden. Durch diese Schnittstelle wird
sichergestellt, da"s jeder Zugriff auf die Wertkomponente des automorphen
Wertes zu dem Typ pa"st, der durch seine Typkomponente repr"asentiert wird.
\item Der Typ {\sl Expansion\/} liefert eine detaillierte Beschreibung eines
automorphen Wertes.
\item Die Funktion {\sl inspect\/} f"uhrt eine Ein--Schritt--Expansion auf 
einem automorphen Wert durch. Dabei ist zu beachten, da"s die Objektidentit"at
der Wertkomponente eines automorphen Wertes erhalten bleibt. Im Gegensatz zu
der Anweisung {\sl dynamic\_be\/} wird diese Funktion in Programmsituationen
verwendet, in denen der Programmierer keine Kenntnis des statischen Typs eines
automorphen Wertes besitzt. Eine sukzessive Inspektion eines automorphen
Wertes liefert dessen elementare Wertkomponenten. Diese Funktion stellt die
Kernfunktionalit"at f"ur datenstrukturabh"angige Programme wie die generische
Daten-- und Funktionsvisualisierung bereit.
\item Einen Sonderfall bei der Ein--Schritt--Expansion bilden Felder.
Normalerweise m"u"ste deren Inspektion ein Feld von automorphen Werten 
liefern. Da jedoch alle Feldelemente  gleichen Typs sind, w"urde dies zu
redundanter Speicherung von Typ\-in\-for\-ma\-tion\-en f"uhren. Aus diesem
Grund werden die beiden Funktionen {\sl getIndexed\/} und {\sl setIndexed\/}
f"ur den indizierten Zugriff auf Felder exportiert.
\item Die Funktion {\sl typeOf\/} liefert die Typkomponente eines automorphen 
Wertes.
\item Eine Reihe von Konstruktoren erm"oglicht die Konstruktion von
strukturierten automorphen Werten aus Komponenten anderer automorpher Werte,
die man mittels {\sl inspect\/} erh"alt. Das hat den Vorteil, da"s ein
automorpher Wert nicht zuerst auf seine Wertkomponente projiziert werden mu"s,
die der Konstruktion eines neuen Wertes dient, aus dem dann schlie"slich
mittels {\sl dynamic\_new\/} der gew"unschte automorphe Wert erzeugt wird.
\item Die Funktionen {\sl intern\/} und {\sl extern} lesen eine linearisierte
Repr"asentation eines automorphen Wertes aus einer Datei in den Objektspeicher
bzw. schreiben diese aus dem Objektspeicher in eine Datei
(s. Abschnitt \ref{strukturierte Ein-- und Ausgabe}).
\item Einige zus"atzliche Hilfsfunktionen bieten weitere Funktionalit"at auf
automorphen Werten an. Die Funktion {\sl newDefault\/} z.B. erzeugt einen
vordefinierten automorphen Wert zu dem als Paramter "ubergebenen Typ.
\end{itemize}


\subsection{Erweiterungen des TL Compilers}
Die Implementierung der in Abschnitt \ref{Spracherweiterungen} beschriebenen 
{\sf TL} Spracherweiterungen erfordert Erweiterungen des {\sf TL}
Compilers. Dabei vereinfachen zwei Eigenschaften der {\sf Tycoon}
Programmierumgebung den Zugriff auf Funktionen des Compilers und somit die
Implementierung mittels Reflektion zur "Ubersetzungszeit: Da {\sf Tycoon} eine
persistente Programmierumgebung ist, k"onnen Programme im gleichen
Objektspeicher "ubersetzt und ausgef"uhrt werden. Au"serdem ist der {\sf 
TL} Compiler wie alle Anwendungsprogramme auch in {\sf TL} geschrieben.

Der abstrakte Wertsyntaxbaum des {\sf TL} Compilers wird um je eine Variante
f"ur die Anweisungen {\sl typeRep\_new\/}, {\sl dynamic\_new\/} und 
{\sl dynamic\_be\/} erweitert. Allen drei Anweisungen ist gemein, da"s zur
"Ubersetzungszeit w"ahrend der Typ"uberpr"ufungsphase des Compilers der
jeweilige Ausdruck analysiert und durch generierten Kode ersetzt wird, der zur
Laufzeit ausgef"uhrt wird. Die Kodegenerierung erfolgt dabei mittels der
zum Compiler geh"orenden Schnittstellen {\sl TLDynamicImpl\/}, {\sl
TLDynamic\/} und {\sl TLDynEnv\/} (s. Anhang \ref{Compilerschnittstellen}).


\subsubsection{Generierung von Laufzeittyprepr"asentationen}
Um Laufzeitrepr"asentationen von Typen zu generieren, mu"s zun"achst eine
Darstellungsform gefunden werden, die in der Lage ist, Typen ad"aquat zu
repr"asentieren. Es bietet sich an, die Repr"asentation zu w"ahlen, die schon
w"ahrend der "Ubersetzungszeit innerhalb des {\sf TL} Compilers verwendet wird,
aber bei der Kodegenerierung verloren geht. In der aktuellen Version des {\sf 
TL} Compilers ist dies jedoch nicht angebracht. Dort basieren die
Typrepr"asentationen auf der sogenannten {\em de Bruijn Notation}
\cite{deBr72,ACCL90} zur Implementierung der Sichtbarkeitsregeln von
Variablen. Dabei verweisen Variablen mittels Indices auf Signaturen innerhalb
eines statischen Kontextes. Dies f"uhrt zu einer Abh"angigkeit {\em aller}
Typ\-re\-pr"a\-sen\-ta\-tion\-en von {\em einem} gemeinsamen Kontext.
Laufzeittyprepr"asentationen sollen jedoch unabh"angig von einem bestimmten
Kontext sein, damit sie in jedem Kontext, der "uber einen initialen Kontext
hinausgeht, g"ultig sind. Aus diesem Grund w"are es notwendig, eine
Typrepr"asentation jeweils mit ihrem Kontext zu aggregieren. Diese L"osung hat
jedoch zwei entscheidende Nachteile:

\begin{enumerate}
\item In einem gemeinsamen Kontext f"ur alle Typrepr"asentationen werden in der
Regel nur ein geringer Teil der Signaturen dieses Kontextes von einer
Typrepr"asentation durch einen {\em deBruijn} Index referenziert. Es w"are
aber zu aufwendig, bei der "Ubertragung einer Typ\-re\-pr"a\-sen\-ta\-tion in
einen anderen Kontext den gesamten Kontext mitzuf"uhren. Deshalb sollte der
jeweils mitgef"uhrte Kontext minimal sein, das hei"st nur die Signaturen
enthalten, die von einer Typkomponente aus referenziert werden. Aber auch die
Eliminierung aller nicht von einer Typrepr"asentation referenzierten Signaturen
zur Laufzeit ist ein teurer Vorgang, da alle {\em deBruijn} Indices innerhalb
der verbleibendenden Signaturen entsprechend angepa"st werden m"ussen.
\item Der Subtyptest zwischen zwei Typrepr"asentationen, der beispielsweise bei
der Anweisung {\sl dynamic\_be\/} durchgef"uhrt wird, mu"s innerhalb
eines gemeinsamen Kontextes erfolgen. Deshalb m"ussen die beiden Kontexte, in
denen die Typrepr"asentationen jeweils g"ultig sind, zun"achst miteinander
vereinigt werden. Dies ist ebenfalls mit hohen Laufzeitkosten verbunden.
\end{enumerate}

\noindent Das f"uhrt zu der Wahl einer alternativen Laufzeitrepr"asentation
von Typen in {\sf TL}, in der Typvariablen eine direkte Referenz auf ihr
definierendes Auftreten enthalten. Diese Art der Darstellung entspricht einem
zyklischen, gerichteten Graphen. Die Zyklen entstehen dann, wenn in einer
Typrepr"asentation rekursive Typbindungen definiert sind. Enthalten
verschiedene Typrepr"asentationen gemeinsame Typvariablen, so referenzieren
beide Repr"asentationen die gleiche Typvariable. Im Unterschied zur {\em
deBruijn Notation} sind die Typ\-re\-pr"a\-sen\-ta\-tio\-nen aber
kontextunabh"angig, da eine Typrepr"asentation nur alle von einer Typkomponente
aus transitiv erreichbaren Signaturen enth"alt, wenn sie aus einem Kontext in
einen anderen "ubertragen wird. Damit ist die Forderung, da"s eine
Typrepr"asentation nur die referenzierten Typbindungen enthalten soll,
erf"ullt.

Der Unterschied zwischen den beiden Darstellungsformen soll anhand eines
Beispiels in Verbindung mit Abb. \ref{Referenzen} illustriert werden:

\begin{quote}
Angenommen, im initialen Kontext sei der Typ {\sl Int\/} an der Position 54 und
der Typ {\sl String\/} an Position 52 definiert. Es werden folgende
Typbindungen definiert:

\begin{xple}
\kw{Let} \id{Name} = \id{String@52}
\kw{Let} \id{Address} = \kw{Tuple} \id{street} :\id{String}@53 \id{city} :\id{String}@54 \id{zip} :\id{Int}@57 \kw{end}
\kw{Let} \id{Person} = \kw{Tuple} \id{name} :\id{Name}@2 \id{address} :\id{Address}@2 \kw{end}
\kw{Let} \id{Student} = \kw{Tuple} \id{name} :\id{Name}@3 \id{address} :\id{Address}@3 \id{semester} :\id{Int}@58 \kw{end}
\end{xple}
\end{quote}

\begin{figure}[tp]
\begin{center} \leavevmode
\epsfbox{referenzen.epsf}
\end{center}
\caption{Typrepr"asentation mit Referenzen}
\label{Referenzen}
\end{figure}

\noindent Bei der Repr"asentation durch direkte Referenzen auf das definierende
Auftreten eines Typs tauchen bei benutzerdefinierten Typen wie z.B. {\sl
Person\/} Typbezeichner zweimal auf --- einmal als Bezeichner, an den 
der Typ gebunden wird, und einmal als Identifikator bei der Definition der
Typkomponente.

Die Verwendung unterschiedlicher Darstellungsformen f"ur Typen innerhalb des
{\sf TL} Com\-pi\-lers und f"ur Laufzeittyprepr"asentationen hat jedoch den
Nachteil, da"s eine hochgradig rekursive Transformation zwischen den beiden
Repr"asentationen erforderlich ist, sowohl bei der Erzeugung von
Laufzeittyprepr"asentationen, als auch bei einem Subtyptest auf
Laufzeittyprepr"asentationen, da dazu der im {\sf TL} Compiler
implementierte Subtyptest verwendet wird, der auf Typen in der {\em
deBruijn Notation} arbeitet. Das f"uhrt zu erheblichen Kosten zur Laufzeit. Um
den Aufwand bei der Generierung von Laufzeittyprepr"asentationen zu
verringern, werden alle generierten Laufzeittyprepr"asentationen f"ur
Typbindungen in einer globalen Tabelle gespeichert, die durch die Schnittstelle
{\sl TLDynEnv\/} verwaltet wird. Da in {\sf Tycoon} jedes erzeugte Objekt eine
eigene Identit"at erh"alt, kann anhand der Objektidentit"at des Typbezeichners
einer Signatur festgestellt werden, ob f"ur eine Typbindung bereits eine
Laufzeittyprepr"asentation erzeugt worden ist. Somit wird eine
Lauf\-zeit\-typ\-re\-pr"a\-sen\-ta\-tion f"ur jede Typbindung nur einmal
erzeugt. Andererseits gew"ahrleistet dieses Verfahren auch, da"s
Laufzeittyprepr"asentationen nur dann eine Typbindung teilen, wenn sie dieselbe
Definition dieser Typbindung referenzieren.

Die Transformation von Laufzeittyprepr"asentationen in statische
Typrepr"asentationen des Compilers erfolgt in zwei Schritten. Im ersten mu"s
f"ur jede in einer Laufzeittyprepr"asentation referenzierte Typvariable
"uberpr"uft werden, ob sie schon in dem Kontext definiert ist, in dem sie
g"ultig sein soll. Ist dies nicht der Fall, so mu"s sie zun"achst in den
Kontext eingef"ugt werden. Um zuf"allige Namens"aquivalenzen zwischen
strukturell unterschiedlichen Typen zu vermeiden, werden die Namen von
Typidentifikatoren um die Position, an der sie im Quelltext definiert worden
sind, sowie um einen Zeitstempel, der bei der Generierung der
Laufzeittyprepr"asentation erzeugt worden ist, erweitert. Im zweiten Schritt
erfolgt die eigentliche Transformation, bei der die {\em deBruijn} Indices f"ur
Typvariablen gesetzt werden m"ussen. 

Trotz der Transformationskosten ist im Rahmen dieser Arbeit die zweite
Darstellungsform gew"ahlt worden, zumal in der zuk"unftigen Version des {\sf
TL} Compilers Typen ebenfalls durch direkte Referenzen auf ihr definierendes
Auftreten repr"asentiert werden \footnote{Eine Implementierung des
Typ"uberpr"ufers mit direkten Objektreferenzen wird zur Zeit im Rahmen einer
anderen Diplomarbeit realisiert und in \cite{Brem96} beschrieben werden},
so da"s die Transformationskosten entfallen. Der rekursive Typ {\sl T\/} der
Schnittstelle {\sl TLDynamicImpl\/}, die die Transformation von
Laufzeittyprepr"asentionen in statische Typrepr"asentationen realisiert,
exportiert die Repr"asentation von Laufzeittypen innerhalb des {\sf
TL} Compilers.

Ein Problem, das bei der Generierung von Laufzeittyprepr"asentationen zu
beachten ist, ist die Behandlung abstrakter Datentypen (s. Abschnitt 
\ref{ADT}). Da in {\sf TL} f"ur abstrakte Typ\-vari\-ab\-len 
Namens"aquivalenzregeln gelten (s. Abschnitt \ref{Namensregel}), m"ussen 
diese f"ur Lauf\-zeit\-typ\-re\-pr"a\-sen\-ta\-tion\-en weiterhin erf"ullt
sein. Zus"atzlich  sollen aber abstrakte Typvariablen {\sl x.T\/} und {\sl
x1.T\/} "aquivalent sein, wenn {\sl x\/} und {\sl x1\/} innerhalb eines
Objektspeichers das gleiche Objekt referenzieren, oder wenn sie in zwei
verschiedenen Objektspeichern durch die gleiche Injektionsfunktion erzeugt
worden sind. Damit ist die Generierung von Laufzeittyprepr"asentationen also
auch abh"angig von den Werten {\sl x\/} und {\sl x1\/}.

Eine L"osung dieses Problems, die es vermeidet, die tats"achliche Struktur der
abstrakten Typvariablen offenlegen zu m"ussen, ist die Ersetzung der Pfade,
d.h. der Wertkomponente, abstrakter Typvariablen durch (weltweit eindeutige)
universelle Bezeichner ({\sl UID\/}). Solch eine {\sl UID\/} besteht aus einer
Plattformidentifikation, einer Maschinenidentifikation sowie einem Zeitstempel
und wird durch eine Funktion zur Generierung von Symbolen der {\sf Tycoon}
Bibliothek erzeugt. Wird diese Funktion mit einem Objekt aufgerufen, von dem 
noch keine {\sl UID\/} erzeugt worden ist, so wird ein neues Symbol generiert. 
Ansonsten wird die bereits erzeugte {\sl UID\/} zur"uckgegeben. Urspr"unglich 
ist dieser Mechanismus entwickelt worden, um beim Austausch von Daten 
innerhalb eines Netzwerkes die zu "ubertragende Datenmenge zu reduzieren. 
Werden zwei Objekte in verschiedenen Objektspeichern als ubiquit"ar
\cite{MMS95a} registriert, so k"onnen {\sl UID\/} Werte anstelle der Objekte
ohne Typinformationen innerhalb des Netzwerkes verschickt werden. "Uber die 
{\sl UID} kann "uberpr"uft werden, ob zwei solche Werte in verschiedenen 
Objektspeichern ``semantisch "aquivalent'' sind. 

Ausgehend von diesen "Uberlegungen, erfolgt die Generierung einer
Laufzeittyprepr"asentation des Typs {\sl T\/} in vier Schritten:
\begin{enumerate}
\item {\sl T\/} wird innerhalb des statischen Kontextes {\sl S\/} auf
Wohlgeformtheit "uberpr"uft.
\item Aus {\sl T\/} wird eine kontextunabh"angige Repr"asentation t$_{S,T}$
generiert.
\item Es wird ein Funktionsaufruf generiert, der die Pfade aller abstrakten
Typvariablen zusammen mit t$_{S,T}$ als Parameter erh"alt. Diese Funktion
f"ugt zur Laufzeit die {\sl UID} Werte f"ur die Pfade in die entsprechenden
Stellen in t$_{S,T}$ ein.
\item Der generierte Funktionsaufruf wird in den Syntaxbaum eingef"ugt.
\end{enumerate}


\subsubsection{Generierung automorpher Werte}
Bei der Generierung automorpher Werte wird zun"achst der Typ aus dem Wert
inferiert. Aus diesem wird wie im vorherigen Abschnitt beschrieben eine
Laufzeittyprepr"asentation generiert, die mit dem Wert zu einem Tupel
aggregiert und in den Syntaxbaum eingesetzt wird. Beispielsweise h"atte der
Programmierer statt des Aufrufs {\sl dynamic\_new(2)\/} auch schreiben k"onnen

\begin{xple}
\kw{tuple}
  \kw{let} \id{value} = 2
  \kw{let} \id{type = typeRep\_new(:Int)}
\kw{end}
\end{xple}

\noindent mit dem Unterschied, da"s der Compiler zusichert, da"s {\sl
type\/} auch den Typ von {\sl value\/} repr"asentiert, da dieser aus dem Wert
inferiert und nicht explizit vom Programmierer angegeben wird.


\subsubsection{Generierung der Projektion}
Da auch Funktionen des Compilers als Literale in den Syntaxbaum geh"angt
werden k"onnen, wird der Subtyptest, der zur Laufzeit von {\sl dynamic\_be\/} 
ausgef"uhrt wird, realisiert, indem ein Aufruf der Funktion generiert wird, 
die den Subtyptest im {\sf TL} Compiler durchf"uhrt. Ein Nachteil dieser 
L"osung entsteht daraus, da"s im {\sf Tycoon} System "ubersetzte Module sowohl 
linearisiert im Dateisystem gespeichert sind als auch nach dem Binden im 
Objektspeicher. Obwohl die Funktion, die den Subtyptest durchf"uhrt, 
Bestandteil des Compilers ist und somit bereits im Objektspeicher vorhanden 
ist, wird sie mitsamt des gr"o"sten Teils des Compilers und allen im aktuellen 
Kontext definierten Bindungen in das Dateisystem hinausgeschrieben, falls der 
Aufruf von {\sl dynamic\_be\/} innerhalb eines Moduls erfolgt. Dies f"uhrt zu 
zus"atzlichem Zeitaufwand bei den Funktionen {\sl intern\/} und {\sl extern\/} 
sowie zu erheblich gr"o"seren Dateien. Eine L"osung diese Problems best"unde 
darin, da"s man "ahnlich wie beim Verschicken von Objekten zwischen zwei 
Objektspeichern solche Funktionen, die wie die des Compilers in jedem 
Objektspeicher vorhanden sind, registriert. Bei {\sl extern\/} wird das Objekt 
durch seine UID ersetzt und umgekehrt bei {\sl intern\/} die UID durch den
Objektidentifikator im Objektspeicher. 

Da beim Transformieren einer Laufzeittyprepr"asentation in eine 
Typrepr"asentation des Compilers die Namen von Typidentifikatoren ver"andert
werden, mu"s auch vom  Typparameter der Anweisung {\sl dynamic\_be\/}
zun"achst eine Laufzeittyprepr"asentation erzeugt werden, die dann wieder
zur"uckverwandelt wird in eine Typrepr"asentation des Compilers. Als initialer
Kontext, in dem die beiden Typrepr"asentationen g"ultig sein sollen, wird dabei
der Kontext gew"ahlt, der auch bei der Initialisierung des {\sf
Tycoon} Systems erzeugt wird. Er enth"alt eine im {\sf TL} Compiler minimal
ben"otigte Anzahl von Bindungen wie beispielsweise die Definitionen der
Basistypen.

Die Umsetzung von {\sl dynamic\_be\/} umfa"st im Typ"uberpr"ufer folgende 
Schritte:

\begin{enumerate}
\item Der Typparameter {\sl T\/} wird innerhalb des statischen Kontextes {\sl
S\/} auf Wohlgeformtheit "uberpr"uft. 
\item Aus {\sl T\/} wird eine Laufzeittyprepr"asentation $t_{S,T}$ erzeugt.
\item Falls es sich bei dem Typparameter um eine universell quantifizierte
Typvariable handelt, die nicht durch das Schl"usselwort {\bf Dyn}
gekennzeichnet ist, oder um eine uninstantiierte Unifikationsvariable, wird
eine Typfehlermeldung erzeugt. 
\item Es wird ein Funktionsaufruf generiert, der bei einem erfolgreichen
Subtyptest zwischen $t_{S,T}$ und der Typkomponente des automorphen Wertes
in dem gemeinsamen statischen Kontext S' dessen Wertkomponente zur"uckliefert.
\item Der generierte Funktionsaufruf wird in den Syntaxbaum eingef"ugt.
\end{enumerate}


\subsubsection{Polymorphe Typvariablen}
Um mit dem Schl"usselwort {\bf Dyn} gekennzeichnete polymorphe Typvariablen
innerhalb von Laufzeittyprepr"asentationen verwenden zu k"onnen, mu"s bei
jedem Aufruf einer polymorphen Funktion f"ur den aktuellen Typparameter
eine Laufzeittyprepr"asentation erzeugt und als Parameter mit "ubergeben
werden (s. Abschnitt \ref{Polymorphismus}). Dazu wird w"ahrend der 
"Ubersetzungsphase f"ur den Anwendungsprogrammierer nicht sichtbar die 
Funktionssignatur f"ur jede mit {\bf Dyn} gekennzeichnete polymorphe 
Typvariable um einen zus"atzlichen Parameter f"ur die 
Laufzeittyprepr"asentation des aktuellen Typparameters erweitert.

\begin{xple}
\kw{let} \id{f}(\kw{Dyn} \id{A} $<$:\kw{Ok}) = \id{typeRep\_new(A)}
     $\Longrightarrow$
\kw{let} \id{f}(\kw{Dyn} \id{A} $<$:\kw{Ok}  \id{a\_Rep :typeRep\_T)} = \id{typeRep\_new(A)}

\id{f(:Int)}   $\Longrightarrow$   \id{f(:Int typeRep\_new(:Int))}
\end{xple}

\noindent Wird wie in obigem Beispiel aus der polymorphen Typvariable {\sl A\/}
im Rumpf von {\sl f\/} eine Laufzeittyprepr"asentation erzeugt, so wird diese
nicht aus {\sl A\/} generiert, sondern es wird die bei der Funktionsapplikation
erzeugte Laufzeittyprepr"asentation {\sl a\_Rep\/} eingesetzt. Jeder andere
Zugriff auf die Typvariable {\sl A} erfolgt so, als w"are sie nicht mit {\bf
Dyn} gekennzeichnet. Die Funktion {\sl f\/} wird jedoch weiterhin mit der
urspr"unglich definierten Anzahl von Parametern aufgerufen. Der Compiler
generiert dann aus allen mit {\bf Dyn} gekennzeichneten polymorphen
Typvariablen Laufzeittyprepr"asentationen.


Eine f"ur den Programmierer transparentere L"osung w"are die Einf"uhrung
eines weiteren Typs und Konstruktors gewesen:

\begin{itemize}
\item {\sl typeRep\_Closed(X $<$:\/}{\bf Ok}{\sl) $<$:typeRep\_T\/} ist der
Typ von Laufzeittyprepr"asentationen, die einen geschlossenen Typ darstellen.
\item {\sl typeRep\_newClosed(X $<$:\/}{\bf Ok}{\sl) :typeRep\_Closed(X)\/}
erzeugt aus einem geschlossenen Typ eine Laufzeittyprepr"asentation.
\end{itemize}

\noindent Soll eine Laufzeittyprepr"asentation von einer polymorphen
Typvariablen erzeugt werden, so ist dieser Funktion als weiterer Parameter
explizit eine Laufzeittyprep"asentation des aktuellen Typparameters, die den
Typ {\sl typeRep\_Closed\/} hat, zu "ubergeben. Da {\sl typeRep\_Closed\/} ein
Typoperator ist, ist sichergestellt, da"s die Laufzeittyprepr"asentation die
polymorphe Typ\-vari\-able repr"asentiert. Dieser Ansatz hat den Vorteil, da"s
er keine versteckten komplexen Erweiterungen des {\sf TL} Sprachprozessors
erfordert.

Allerdings gibt es auch zwei entscheidende Nachteile, die zu der in {\sf TL}
realisierten L"osung gef"uhrt haben: Zum einen ist die Erzeugung von
Laufzeittyprepr"asentationen, in denen eine polymorphe Typvariable innerhalb
eines strukturierten Typs verwendet wird, komplizierter, wie folgender
Vergleich illustriert:

\vspace{0,8cm}

\begin{minipage}[t]{9cm}
\begin{xple}
\kw{let} \id{f(A} $<$:\kw{Ok}  \id{a\_Rep :typeRep\_Closed(A))} =
  \kw{begin}
    \kw{Let} \id{T} = \kw{Tuple} \id{a :A  b :Int} \kw{end}
    \kw{let} \id{aSig} =
      \kw{tuple\_case} \id{valueCase} \kw{of} \id{typeRep.Signature} \kw{with}
        \kw{let} \id{ide} = \kw{tuple}
          \kw{let} \id{name} = ``a''
          \kw{let} \id{pos = source.noWhere}
        \kw{end}
        \kw{let} \id{type = a\_Rep}
      \kw{end}
    \kw{let} \id{bTuple =} \id{typeRep\_new}(:\kw{Tuple} \id{b :Int} \kw{end})
    \kw{let} \id{sigs =} \id{list.cons(aSig typeRep.signatures(bTuple))}
    \kw{let} \id{tRep =} \id{typeRep.newTuple(sigs}
                       \id{typeRep.newEmptyCases())}
    ...
  \kw{end}
\end{xple}
\end{minipage} \hfill
\begin{minipage}[t]{5cm}
\begin{xple}
\kw{let} \id{f}(\kw{Dyn} \id{A} $<$:\kw{Ok}) =
  \kw{begin}
    \kw{Let} \id{T} = \kw{Tuple}
      \id{a :A}
      \id{b :Int}
    \kw{end}
    \kw{let} \id{tRep = typeRep\_new(:T)}
    ...
  \kw{end}
\end{xple}
\end{minipage}

\vspace{0,8cm}

\noindent Zum anderen erlaubt diese L"osung keine uniforme Verwendung
polymorpher Funktionen. Anders als beim Schl"usselwort {\bf Dyn} ist die Anzahl
der beim Funktionsaufruf zu "ubergebenden Parameter abh"angig davon, ob von
einer polymorphen Typvariablen im Funktionsrumpf eine
Laufzeittyprepr"asentation erzeugt werden soll oder nicht. Um die in Abschnitt
\ref{Funktionskode} beschriebene L"osung zur Generierung von
Laufzeittypinformationen der Typen globaler Bindungen zu verwenden, m"u"sten
also nicht nur die Funktionssignaturen um die Parameter f"ur die
Laufzeittyprepr"asentationen polymorpher Typvariablen erweitert werden, sondern
auch alle Funktionsaufrufe polymorpher Funktionen. Da der in
\ref{Funktionskode} realisierte Ansatz "ubersetzungszeitreflektiv ist,  m"uste
der Compiler bei jedem Funktionsaufruf testen, ob die Funktion polymorphe
Typvariablen erwartet und ob dazu die Laufzeittyprepr"asentation mit generiert
und als Parameter "ubergeben werden mu"s. Damit f"uhrt dieser Ansatz, anders
als bei der Verwendung des Schl"usselwortes {\bf Dyn} zu
Geschwindigkeitsverlusten beim "Ubersetzen und zu einer h"oheren Komplexit"at
des Sprachprozessors.
