\chapter{Reflektive Dienste}
\label{reflection}

Das Tycoon-System zeichnet sich besonders durch die vorhandenen generischen
Dienste in seinen Bibliotheken aus, die ein hohes Ma"s an Wiederverwendung 
erlauben. Beispielhaft sei hier das Tycoon-{\em Compiler-Toolkit} 
\cite{SchMa92}
erw"ahnt, welches zur Implementierung des \TL-Compilers verwendet wurde. 
In diesem Kapitel wird behandelt, auf welche Weise Dienste des Compilers 
selbst (z.B. parsing, statische und dynamische Typ\-"uberpr"ufung, Codegenerierung)
in einer Bibliothek zur Verf"ugung gestellt werden m"ussen,
um streng typisierte reflektive Programmierung in \TL\ zu erm"oglichen. 

Nach einer allgemeinen Charakterisierung von Reflektion in Programmiersprachen
und der Behandlung typischer Beispiele und Anwendungen wird auf eine der
Grundvoraussetzungen zur reflektiven Programmierung in statisch typisierten
Sprachen eingegangen, n"amlich die {\em dynamische Typisierung}. 
Diese Spracheigenschaft ist Voraussetzung f"ur die im folgenden vorgestellte
typsichere Schnittstelle des aufrufbaren Compilers und wurde in Kooperation mit 
Hubertus Koehler\footnote{Arbeitstitel seiner Diplomarbeit: Generische Daten-
und Funktionsvisualisierung} als Erweiterung des bisherigen \TL-Compilers 
implementiert. 
Die Schnittstelle des aufrufbaren Compilers wiederum ist nicht nur 
Voraussetzung zur 
reflektiven Programmierung, sondern bildet dar"uberhinaus auch die Grundlage 
f"ur Programmierwerkzeuge der Tycoon-Entwicklungsumgebung (siehe Kapitel 
\ref{workbench}). Das Kapitel schlie"st mit einer Betrachtung von
Schnittstellen zu Compilern anderer Sprachen und einer Bewertung ihrer Eignung
zur reflektiven Programmierung.


\subsubsection{Charakterisierung von Reflektion}

Programme mit der F"ahigkeit, sich selbst zu inspizieren und zu ver"andern, 
werden als {\em reflektiv} bezeichnet \cite{Kir92}. 
Dies kann entweder durch Beeinflussung ihres
Interpretationsvorganges (verhaltensbasierte Reflektion) oder durch "Anderung
der eigenen Repr"asentation (linguistische Reflektion) erfolgen.
Die "Anderung der eigenen Repr"asentation beruht dabei auf der
F"ahigkeit von Programmen, Programmrepr"asentationen zu generieren (d.h.
Programme als Daten zu behandeln), sie in 
ausf"uhrbaren Code zu transformieren und diesen in den eigenen Programmablauf 
zu integrieren (d.h. Daten als Programme zu behandeln).

Reflektive F"ahigkeiten sind im Zusammenhang mit
Assemblersprachen oder untypisierten h"oheren Sprachen eher als gef"ahrlich 
einzustufen, da es keine wirksamen Mechanismen zur Einschr"ankung der
Verhaltens"anderung auf ein "`sinnvolles"' Ma"s gibt. Typisierte Sprachen 
erlauben es jedoch, alle Modifikationen, die ein Programm sich selbst
zuf"ugt, auf Typ\-korrektheit zu "uberpr"ufen. Man spricht in diesem Fall auch
von {\em typsicherer linguistischer Reflektion}. Diese kann sowohl zur
"Ubersetzungszeit als auch zur Laufzeit initiiert werden. Einen "Uberblick
"uber die Arten von Reflektion gibt Abbildung \ref{reflectionKinds}.

\begin{figure}
\leavevmode
\def\epsfsize#1#2{0.7\textwidth}
\centerline{\epsffile{reflectionKinds.epsf}}
\caption{\label{reflectionKinds} Ausformungen von Reflektion}
\end{figure}

Eine Programmiersprache um reflektive F"ahigkeiten zu erweitern bedeutet nicht,
ihre Ausdrucksm"achtigkeit zu erh"ohen, wenn diese Sprache ohnehin schon
algorithmisch vollst"andig ist. Sie erlaubt jedoch eine
generische und damit k"urzere und besser wiederverwendbare Darstellung einiger 
im Bereich datenintensiver Anwendungen h"aufig gebrauchter Algorithmen, auf die
im Verlauf dieses Kapitels noch n"aher eingegangen wird.
Ein Beispiel f"ur die Erh"ohung von Ausdrucksm"achtigkeit durch Reflektion ist
die in \cite{BGV92} beschriebene Erweiterung der Relationenalgebra um
einen Evaluationsoperator, mit dem in Relationen enthaltene
Programmrepr"asentationen ausgef"uhrt werden k"onnen.

In dieser Arbeit besteht ein zyklischer Zusammenhang zwischen Reflektion zur
"Ubersetzungszeit und Reflektion zur Laufzeit: zur "Ubersetzungszeit
ausgef"uhrte Funktionen werden zur Implementierung dynamischer Typen benutzt.
Diese erm"oglichen eine streng typisierte Schnittstelle eines
aufrufbaren Compilers. Diese Schnittstelle wiederum kann in der Implementation 
des Compilers (in einer weiteren Bootstrap-Iteration) verwendet werden, 
um zur "Ubersetzungszeit durch einen rekursiven Aufruf "`an sich selbst"' Werte 
zu berechnen. Dadurch wird eine
allgemeinere Form von Reflektion zur "Ubersetzungszeit m"oglich, als diejenige,
die zur Implementierung dynamischer Typen in "`hart verdrahteter"' Weise
eingesetzt wird.

                \section{Dynamische Typen zur reflektiven Programmierung}
                \label{dynamicTypes}

Ziel der Entwicklung h"oherer Programmiersprachen ist die Bereitstellung
immer m"achtigerer Abstraktionsmechanismen, um eine im hohen Ma"se
{\em generische} Programmierung zu erm"oglichen. Im einzelnen bedeutet dies,
da"s der Programmierer durch Wiederverwendung existierender Codefragmente und
durch Automatisierung gewisser Teile der Codierungsarbeit immer weniger Code 
selbst schreiben mu"s. Die verschiedenen Arten des {\em Polymorphismus} stellen 
dabei Schl"usselkonzepte bzw. S"aulen der generischen Programmierung dar
(siehe Abb. \ref{saeulen}).

\begin{figure}
\leavevmode
\def\epsfsize#1#2{0.6\textwidth}
\centerline{\epsffile{saeulen.epsf}}
\caption{\label{saeulen} S"aulen der generischen Programmierung}
\end{figure}

\begin{description}
\item {\bf Parametrischer Polymorphismus} dient zur Formulierung von 
Funktionen, die {\em typ\-unabh"angige} Berechnungen durchf"uhren. 
\item {\bf Subtyppolymorphismus} unterst"utzt den Aufbau von 
{\em Typ\-hierarchien}.
\item {\bf Reflektiver Polymorphismus} (Ad-hoc-Polymorphismus) erlaubt die
Formulierung von Funktionen, die {\em typgesteuerte} Berechnungen durchf"uhren.
\end{description}
Die Benutzung der ersten beiden S"aulen ist in \cite{MMS94} beschrieben, 
w"ahrend Benutzung und Implementierung der dritten S"aule Gegenstand dieses 
Kapitels sind.

Subtyppolymorphismus (Inklusionspolymorphismus) und parametrischer 
Polymorphismus werden in \cite{CaWe85} unter dem Begriff {\em universeller
Polymorphismus} zusammengefa"st. Durch ihn wird im Kontext 
statisch typisierter Sprachen eine "ahnliche Flexibilit"at erreicht, wie sie 
vorher nur in dynamisch typisierten Sprachen m"oglich war.   
Reflektiver Polymorphismus als Form des Ad-hoc-Polymorphismus jedoch erlaubt 
es dem Programmierer, Funktionen mit 
einem (noch) h"oheren Grad an Generik zu schreiben als demjenigen, der durch 
universellen Polymorphismus erreichbar ist. Dadurch 
werden dem Programmierer gr"o"sere M"oglichkeiten zur Wiederverwendung von Code 
erm"oglicht. Gerade im Bereich
datenintensiver Anwendungen, die durch einen hohen Anteil schematischer und
repetitiver Programmierung charakterisiert sind, ist diese h"ohere Generik 
f"ur eine Reihe h"aufig verwendeter Funktionen erw"unscht \cite{SFSS90}.
Aus Implementierungssicht ist der Hauptunterschied zwischen universellen und
ad hoc-polymorphen Funktionen derjenige, das erstere f"ur jeden Argumtenttyp
jeweils denselben Code, letztere hingegen unterschiedlichen Code ausf"uhren.


        \subsection{Anwendungen dynamischer Typisierung}
	\label{dynType-Anwendungen}

Manche Programmiersituationen machen dynamische Typisierung unumg"anglich. 
Diese sind dadurch charakterisiert, da"s der
Kontext, in dem ein Wert erzeugt wurde, und der Kontext, in dem er benutzt wird,
"uber keine gemeinsame statisch "uberpr"ufbare Spezifikation verf"ugen.
Das f"ur diese Arbeit wichtigste Beispiel zur Verdeutlichung dieses
Sachverhaltes ist die Funktion {\it eval}, die in ihrer einfachsten Form als 
Parameter eine Zeichenkette "ubernimmt, diesen als Ausdruck der Sprache 
auswertet und das Ergebnis zur"uckliefert.
\begin{xple}
  eval(sourceText :String) :???
\end{xple}
Wie durch die Fragezeichen angedeutet, l"a"st sich das Ergebnis dieser Funktion
innerhalb des Aufrufkontextes nicht statisch typisieren. Der Typ des
R"uckgabewertes kann erst zur Ausf"uhrungszeit festgestellt werden, da er vom 
dynamisch gebundenen Quelltext abh"angt. 

Weitere Anwendungen dynamischer Typen umfassen:
\begin{itemize}
\item Datenaustausch mittels (standardisierter) linearer Datenrepr"asentationen,
\item Datenaustausch mit strukturierten Datenspeichern ({\em repositories}),
\item Generierung, Konvertierung und Vermittlung ({\em trading)} von
  Schnittstellenbeschreibungen (siehe Kap. \ref{idl-comparing}),
\item Bindung an externen Code: RPC {\em Stubs} \cite{daSilva95}, Dynamic Link 
Libraries, \item Typ\-gesteuerte, generische Algorithmen: Da die Menge der 
Typ\-konstruktoren in jeder Programmiersprache begrenzt ist, im Gegensatz zur 
Menge der definierbaren Typen, lassen sich mit Hilfe von
Laufzeit-Typ\-information f"ur folgende Anwendungen generische rekursive 
Bibliotheksfunktionen zur Verf"ugung stellen, die ansonsten vom 
Anwendungsprogrammierer implementiert werden m"u"sten:
  \begin{itemize}
  \item Generische Datenvisualisierung \cite{Mues94}: Hierbei wird die in der
  objektorientierten Programmierung "ubliche Implementierung jeweils einer
  Visualisierungsmethode pro Klasse durch die Implementierung einer einzigen 
  generischen Funktion ersetzt, welche anhand der "ubergebenen 
  Laufzeit-Typ\-repr"asentation entscheidet, wie die Ausgabe gestaltet werden
  mu"s.
  \item Erzeugung von {\em Default}-Werten f"ur beliebige Typen: Da in \TL\ 
  keine uninitialisierten Wertbindungen m"oglich sind, ist in einigen
  Programmiersituationen ein generischer Konstruktor hilfreich. Dies trifft 
  vor allem bei Benutzung variabler Wertbindung im imperativen 
  Programmierstil zu, insbesondere, wenn komplexe Strukturen initialisiert 
  werden m"ussen.
  \item Test auf strukturelle Gleichheit beliebig strukturierter Werte: 
  Anders als die Identit"atsfunktion (\TL-Basisprimitive) kann der meist sehr
  aufwendige tiefe Vergleich von Baumstrukturen durch einen typgesteuerten
  Algorithmus als Bibliotheksdienst angeboten werden.
  \end{itemize}
\end{itemize}


        \subsection{Laufzeit-Typrepr"asentationen und automorphe Werte}

Typ\-repr"asentationen, die der Compiler lediglich als Hilfsstrukturen zur 
statischen Typ\-"uberpr"ufung benutzt, werden zur Laufzeit nicht mehr ben"otigt, 
da nach erfolgreicher Typ\-"uberpr"ufung das Programm als statisch korrekt 
angesehen werden kann \cite{Matt87}.
Zur Durchf"uhrung typgesteuerter Berechnungen ist es jedoch notwendig, 
Typen zur Laufzeit als {\em Wert} der Sprache zu repr"asentieren. 
Dieser Wert wird in der Literatur \cite{Matt87,ACPR92,LM91} meistens als 
{\em dynamischer Typ} 
bezeichnet, obwohl diese Bezeichnung eher irref"uhrend ist, da es sich
ja tats"achlich um einen {\em Wert} handelt, der einen statischen Typ 
repr"asentiert.

Sei $T$ ein Typ in einem statischen Kontext $S$, so soll mit 
$t_{S,T}$ dessen Repr"asentation zur Programmlaufzeit bezeichnet werden.

Aussagen "uber statische Typen sind, bedingt durch die statischen
Sichtbarkeitsregeln in \TL, immer kontextabh"angig. Charakteristisch f"ur
dynamische Typen ist hingegen, da"s sie ihren Kontext gewisserma"sen
"`in sich"' tragen, d.h. es gibt keinen allen dynamischen Typen gemeinsamen
Kontext au"ser dem initialen Kontext, in dem z.B. die Basistypen definiert
sind. 

Der in der Praxis h"aufigste Fall ist die Benutzung von
Laufzeit-Typ\-repr"asentationen im Zusammenhang mit einem Wert, der durch sie
beschrieben wird. Solch eine Aggregation, bestehen aus einem beliebigen Wert 
und dessen Typ\-repr"asentation, wird als {\em automorpher} 
(selbstbeschreibender) Wert \cite{Card89} oder auch als {\em dynamic} 
bezeichnet \cite{ACPP90,Card86,LM91}.

Ein {\em automorpher Wert} ist ein Paar $(x, t_{S,T})$, so da"s {\sl x} vom Typ
{\sl T} im statischen Kontext {\sl S} ist.

%Automorphe Werte lassen sich auch als Werte eines Varianten Tupels auffassen, 
%wobei die Zahl der m"oglichen Varianten unendlich, also nicht statisch 
%fixierbar ist (z.B. Typ {\bf Any} in Napier88 \cite{Mor*94}). 



        \subsection{Spracherweiterungen von TL}
        \label{spracherweiterung}

Das bisherige Konzept f"ur dynamische Typen wurde in Abschnitt
\ref{oldDynTypes} erl"autert. Abweichend davon
wird in dieser Arbeit ein zur "Ubersetzungszeit reflektiver Ansatz 
gew"ahlt, um Laufzeit-Typ\-repr"asentationen f"ur algorithmisch vollst"andige
Berechnungen zug"anglich zu machen und dabei dem Umstand Rechnung zu tragen,
da"s das Typ\-system von \TL\ h"oherer Ordnung ist.

Folgende Spracherweiterungen sind zur Implementierung dieses Ansatzes notwendig:
\begin{enumerate}
\item Neue Basistypen {\em typeRep\_T} und {\em dynamic\_T} f"ur 
Laufzeit-Typ\-repr"asentationen bzw. automorphe Werte.
\item Zu diesen Basistypen geh"orige Konstruktoren ({\em typeRep\_new} und
{\em dynamic\_new}).
\item Eine inverse Operation zu {\em dynamic\_new}, {\em dynamic\_be} 
genannt, die zur Laufzeit aus einem automorphen Wert die Wertkomponente 
extrahiert, falls dessen Typ\-komponente ein Subtyp des als Argument
"ubergebenen Typs ist.
\end{enumerate}

Diese Anweisungen lassen sich aus zwei Gr"unden nicht als 
Bibliotheksfunktionen im\-ple\-men\-tie\-ren\footnote{Die verwendete Notation
mit Unterstrich soll allerdings andeuten, da"s Operationen auf Werten
dieser Typen in entsprechend benannten Modulen zur Verf"ugung stehen.}:
Erstens ben"otigen sie den Zugriff auf interne Datenstrukturen des Compilers
und zweitens sollen sie auf {\em beliebige} Typen anwendbar sein.
Somit sind sie so generisch, da"s sich ihre Signaturen nicht im 
\TL-Typ\-system formulieren lassen. In einer Pseudo-Notation hingegen 
lie"sen sie sich folgenderma"sen ausdr"ucken:
\begin{xple}
  typeRep\_new(T ::\kw{ANYTYPE}) :typeRep\_T
  dynamic\_new(T $<:$\kw{Ok}  v :T) :dynamic\_T
  dynamic\_be(d :dynamic\_T  T $<:$\kw{Ok}) :T 
    (* l"ost Ausnahme aus, falls der dynamische Subtyptest fehlschl"agt *) 
\end{xple}
Hierbei stellt {\bf ANYTYPE} den allgemeinsten {\em Kind}\footnote{
{\em Kinds} strukturieren den Typ\-raum in "ahnlicher Weise, wie Typen
den Werteraum strukturieren \cite{Card89}.}
dar, also insbesondere
auch den {\em Kind} aller Typ\-operatoren. Die "Ubergabe von Typ\-parametern 
wird bei den Anweisungen {\sl typeRep\_new} und {\sl dynamic\_be}
durch die Syntax erzwungen. Bei der Anweisung {\em dynamic\_new} wird immer
der inferierte Typ zur Konstruktion des automorphen Wertes benutzt, es wird
also kein Typ\-parameter "ubergeben.

Diese Anweisungen sind keine Funktionen. Sie lassen sich vielmehr als Makros 
auffassen, die w"ahrend der Typ"uberpr"ufungsphase expandiert werden, wobei
neuer Code erzeugt wird, der an die Stelle der urspr"unglichen Anweisung
tritt. Dieser Vorgang wird in Abschnitt \ref{dyntype-implementation}
dargestellt.


\subsubsection{Behandlung von Polymorphismus und abstrakten Typen}
\label{polyAndAbsType}

Die Einf"uhrung dynamischer Typen darf keine M"oglichkeit er"offnen, das
Typ\-system zu unterlaufen. Dies ist insbesondere dann ein Problem, wenn es
Polymorphismus und abstrakte Typen enth"alt \cite{Matt87}. 
Beispielsweise darf es nicht erlaubt sein, mit Hilfe der polymorphen Funktion
\begin{xple}
  \kw{let} cast(A $<:$\kw{Ok}  d :dynamic\_T) :A = dynamic\_be(d :A)
\end{xple}
das Typ\-system zu unterlaufen, indem man z.B. aus einem Integer-Wert
einen automorphen Wert konstruiert, ihn dieser Funktion "ubergibt und das 
Resultat z.B. als String weiterverwendet. In \TL\ wird deswegen der Aufruf von 
{\em dynamic\_be} statisch verboten, wenn der "ubergebene Typ eine
polymorphe Typ\-variable ist. 

Die Erzeugung von Repr"asentationen abstrakter Typen kann nur zum Teil zur
"Ubersetzungszeit erfolgen. Dies liegt daran, da"s erst zur Laufzeit bekannt
ist, auf welchem Pfad (d.h. von welchem Tupel- oder Modul-Objekt aus) ein 
abstrakter Typ referenziert wird. Diese Information mu"s jedoch unbedingt in 
dessen Repr"asentation enthalten sein, damit nicht
f"alschlicherweise Typ\-repr"asentationen abstrakter Typen zueinander kompatibel
sind, deren Implementation unterschiedlich ist, wie folgendes Beispiel
verdeutlicht:
\begin{quote} 
Es gelte $\judge{S}{\tlhastype{d}{stack.T}}$. Durch die Bindung
\begin{xple}
        \kw{let} d = dynamic\_new(s)
\end{xple}
wird ein automorpher Wert aus diesem Kellerspeicher-Objekt erzeugt. 
In einem anderen Kontext wird es z.B. durch
\begin{xple}
        \kw{let} d :dynamic\_T = dynamic.intern(fileHandle)
        \kw{let} s = dynamic\_be(d :stack.T)
\end{xple}
als statisch typisierter Wert verf"ugbar gemacht. Der dynamische Typ\-test mu"s
jedoch fehlschlagen, falls das Tupel (im allgemeinen ein gebundenes Modul) 
{\em stack} nicht dieselbe Identit"at hat wie das, was im Kontext zur Zeit der 
Erzeugung des automorphen Wertes gebunden war. Pfade von abstrakten
Typ\-variablen sind also bei der Erzeugung von Typ\-repr"asentationen dynamisch zu
binden.
\end{quote}
Die Inspektion von Laufzeit-Typ\-repr"asentationen darf es 
dem Anwender nicht erlauben, die konkrete Struktur abstrakter Typen zu
erfahren und dieses Wissen als Grundlage weiterer Berechnungen zu verwenden,
denn dies st"unde im Widerspruch zum Grundgedanken abstrakter Datentypen.
Die Repr"asentation eines abstrakten Typs enth"alt darum lediglich dessen
Namen und Information "uber den Pfad, auf dem er referenziert wurde. 
Diese Pfadinformation sollte idealerweise system"ubergreifend eindeutig sein,
in der derzeitigen Implementation ist sie jedoch lediglich innerhalb eines
Objektspeichers eindeutig.

\subsubsection{Typregeln}

Die statische \TL-Semantik wird in \cite{Matt93} durch Typregeln formal
beschrieben. Diese Regeln werden in folgender Weise erweitert bzw. erg"anzt:

\vspace{1cm}
\define{Type Builtin}{
\dedtwoh{
  \judge{}{\tlissig{S}}
}
{ A \in \{ \tlOk,\tlNok,\tlBool,\tlInt,\tlString,\tltypeRepT,\tldynamicT \} }
{ \judge{S}{\tlistype{A}}
}}
Diese Regel dr"uckt aus, da"s die Menge der Basistypen um die Typen {\em 
typeRep\_T} und {\em dynamic\_T} erweitert wird.\\
\\
\vspace{1cm}
\define{Value TypeRep}{
\ded{
  \judge{S}{\tlistype{A}}
}
{ \judge{S}{\tlhastype{\mathbf {typeRep\_new}(A)}{\tltypeRepT}}
}}
Die Anwendung der Anweisung {\bf typeRep\_new} auf einen wohlgeformten Typen
resultiert in einem Wert vom Typ {\em typeRep\_T}.\\
\\
\vspace{1cm}
\define{Value Dynamic}{
\dedtwoh{
  \judge{S}{\tlhastype{x}{A}}
}
{ \judge{S}{\tlsubtype{A}{\tlOk}}
}
{ \judge{S}{\tlhastype{\mathbf {dynamic\_new}(x)}{\tldynamicT}}
}}
Die Anwendung der Anweisung {\bf dynamic\_new} auf einen Wert x 
vom Typ $A <:${\bf Ok} resultiert in einem Wert vom Typ {\em dynamic\_T}.\\
\\
\vspace{1cm}
\define{Value Be}{
\dedtwoh{
  \judge{S}{\tlhastype{x}{\tldynamicT}}
}
{ \judge{S}{\tlsubtype{A}{\tlOk}}
}
{ \judge{S}{\tlhastype{\mathbf {dynamic\_be}(x, A)}{A}}
}}
Die Anwendung der Anweisung {\bf dynamic\_be} auf einen automorphen Wert und 
einen wohlgeformten Typ $<:${\bf Ok} resultiert in einem Wert dieses Typs.

Zur Realisierung dieser Regeln ist,
im Sinne des Orthogonalit"atsprinzips von \TL, eine Erweiterung der
Syntax polymorpher Funktionen wie in folgendem Beispiel notwendig:
\begin{xple}
  \kw{let} f(\kw{Dyn} T $<:$\kw{Ok}  x :T) :... = 
    ... \kw{dynamic\_new}(x) ...
\end{xple}
Durch das Schl"usselwort {\bf Dyn} wird dem Compiler hierbei mitgeteilt, da"s
er Vorkehrungen treffen mu"s, um der Funktion~{\sl f} zur Laufzeit 
eine Typ\-repr"asentation des "ubergebenen (oder inferierten) Typs {\sl T} zur 
Verf"ugung zu stellen. Ohne diese Erweiterung mu"s {\sl f} folgenderma"sen
formuliert werden:
\begin{xple}
  \kw{let} f(x :dynamic\_T) :... = ... x ...
\end{xple}
Die Erzeugung eines automorphen Wertes erfolgt {\em vor} dem Aufruf,
da im Rumpf von {\sl f} statisch nur die Zusicherung {\sl T $<:$Ok} bekannt ist.
Es ist dann keine Vermischung von parametrischem und reflektivem
Polymorphismus m"oglich.


        \subsection[Programmierschnittstellen f"ur dynamische Typen]
	{Programmierschnittstellen f"ur dynamische Typen und automorphe Werte}

Zur Entwicklung datenstrukturgetriebener Algorithmen ben"otigt der
Programmierer neben den reflektiven Basiskonstrukten eine 
Programmierschnittstelle, die ihm Funktionen sowohl zur Inspektion als auch
zur Konstruktion von Typ\-repr"asentationen und automorphen Werten zur 
Verf"ugung stellt. Diese sind in den Modulen {\sl typeRep} und 
{\sl dynamic} implementiert, welche internes Wissen um die Darstellung von
Typ\-repr"asentationen durch den Compiler besitzen, ohne jedoch Teil des
Compilers zu sein, wie Abb. \ref{typeRep-compiler} verdeutlicht.

\begin{figure}[hbt]
\leavevmode
\def\epsfsize#1#2{0.7\textwidth}
\centerline{\epsffile{typeRep-compiler.epsf}}
\caption{\label{typeRep-compiler} Kopplung des API f"ur dynamische Typen an den Compiler}
\end{figure}

\subsubsection{Schnittstelle 'TypeRep'}
\label{typeRep-Modul}

Diese Schnittstelle stellt Funktionen zur strukturierten Analyse und 
Konstruktion von Typ\-repr"asentationen und Typ\-bindungen zur Verf"ugung 
(Schnittstelle siehe Anhang \ref{typeRep}). Wichtigste Operation auf 
Typ\-repr"asentationen ist die Funktion
{\em inspect}, die eine detailliertere Beschreibung der ihr "ubergebenen
Typ\-repr"asentation liefert. Ferner gibt es f"ur jeden strukturierten \TL-Typ
Konstruktorfunktionen, um aus Zwischenergebnissen von {\em inspect}, 
z.B. Listen von Signaturen, wiederum Typ\-repr"asentationen aufbauen
zu k"onnen. Die Anweisung {\sl typeRep\_new} reicht dazu nicht aus, da man
mit ihr nur Typ\-repr"asentationen von statisch bekannten Typen erzeugen kann.

Die Funktion {\sl isSubType} ist die "offentlich zug"angliche Version des
Subtyptests des \TL-Compilers. 
Hervorzuheben ist noch die Funktion {\sl fmt}, die eine Zeichenkette aus 
einer Typ\-repr"asentation erzeugt. Sie wird vor allem in Generatoren bei der 
laufzeit-reflektiven Programmierung verwendet, um Quelltext f"ur berechnete
Typen zu erzeugen.


\subsubsection{Schnittstelle 'Dynamic'}

Durch die Anweisung {\sl dynamic\_be} l"a"st sich die Wertkomponente eines
automorphen Wertes wieder auf die statisch typisierte Ebene zur"uckholen. 
Oftmals gibt es jedoch Programmiersituationen, bei denen man statisch keinerlei 
Information "uber die Typ\-komponente eines automorphen Wertes und deshalb 
keinen Anhaltspunkt zur Parametrisierung der {\sl dynamic\_be}-Anweisung hat. 
In diesem Fall ist eine
sukzessive Inspektion des automorphen Wertes n"otig, um an dessen elementare
Wertkomponenten zu gelangen, wie folgendes Beispiel zeigt:
\begin{quote} 
Sei d in einem anderen Kontext gebunden worden durch
\begin{xple}
      \kw{let} d = dynamic\_new(\kw{tuple let} name = ''Hans'' let age = 43 \kw{end}),
\end{xple}
so kann auf die Komponente {\sl name} folgenderma"sen zugegriffen werden:
\begin{xple}
      \kw{case} dynamic.inspect(d)
      \kw{when} tupleCase \kw{with} d \kw{then}
        \kw{let} nameDyn = list.head(d.bindings)!valueCase.value()
        dynamic.inspect(nameDyn)!stringCase.val 
          (* ! = Variantenprojektion *)
      \kw{else} ...
      \kw{end}.
\end{xple}
\end{quote}

Automorphe Werte von Arrays erfordern eine besondere Betrachtung.
Sinn der Inspektionsfunktion ist es ja, eine detailliertere Beschreibung des 
automorphen Wertes zu liefern\footnote{
siehe Typ {\sl Expansion} in Schnittstelle {\sl Dynamic} (Anhang \ref{dynamic})
}. Inspeziert man einen automorphen Wert eines
Arrays, so m"u"ste ein Array zur"uckgegeben werden, bei dem jedes einzelne
Element mit seiner Typ\-repr"asentation aggregiert ist. 
Dies w"urde insbesondere bei gro"sen Arrays zu erheblicher 
redundanter Typ\-information und damit Speicherverschwendung f"uhren.
F"ur diesen Fall stehen daher die Funktionen 
\begin{xple}
  getIndexed(:dynamic\_T) :dynamic\_T
\end{xple}
und
\begin{xple}
  setIndexed(a :dynamic\_T  value :dynamic\_T) :\kw{Ok} 
\end{xple}
zum indizierten Zugriff auf die Komponenten eines Arrays innerhalb eines 
automorphen Wertes zur Verf"ugung.

Als wichtige Operationen auf automorphen Werten seien noch die 
Funktionen {\em extern} und {\em intern} hervorgehoben (siehe dazu auch
\cite{Card89}), die eine lineare
Repr"asentation eines automorphen Wertes z.B. auf eine Datei schreiben bzw. von 
ihr lesen. Diese Operationen dienen z.B. zum typisierten Datenaustausch zwischen
unabh"angigen Objektspeichern oder verteilten autonomen Anwendungen. 
Diese Funktionen werden implementiert durch Aufrufe von Funktionen des 
{\em Tycoon Store Protocol}, welche die Linearisierung von Objektgraphen 
realisieren.


        \subsection{Implementierung durch Reflektion zur "Ubersetzungszeit}
       \label{dyntype-implementation}

Ein gro"ser Vorteil persistenter Umgebungen ist es, da"s Programme in
derselben Umgebung (d.h. konkret im selben Objektspeicher) ausgef"uhrt werden 
k"onnen, in der sie "ubersetzt wurden. Wenn dann auch noch der Compiler in 
derselben Sprache geschrieben ist wie seine Quellsprache, so ist es 
relativ einfach m"oglich, seine internen Datenstrukturen zur Laufzeit
verf"ugbar zu machen.
Diese Eigenschaft wird zur Implementierung der Anweisung {\em typeRep\_new(:T)}
ausgenutzt, indem sie zur "Ubersetzungszeit wie folgt ausgewertet wird.
\begin{enumerate}
\item {\sl T} wird innerhalb des statischen Kontexts {\sl S} auf 
Wohlgeformtheit gepr"uft.
\item Aus {\sl T} wird eine kontextunabh"angige Repr"asentation {\sl t}$_{S,T}$ 
generiert (siehe dazu Ab\-schnitt \ref{typeRep-Generierung}).
\item Um die Pfade abstrakter Typen (siehe Abschnitt~\ref{polyAndAbsType}) zur 
Laufzeit in die Typ\-repr"asentation integrieren zu k"onnen, wird ein
Funktionsaufruf generiert, der die Pfade (d.h. die Wertkomponenten)
aller benutzten abstrakten Typ\-variablen
zusammen mit {\sl t}$_{S,T}$ als Aktualparameter "ubergeben bekommt. Diese 
Funktion f"ugt die "ubergebenen Pfade dann zur Laufzeit an die entsprechenden 
Stellen in {\sl t}$_{S,T}$ ein.
\item Der generierte Funktionsaufruf wird in den urspr"unglichen Syntaxbaum 
implantiert.
\end{enumerate}

Zur Konstruktion von automorphen Werten wird Code generiert, der ein Tupel
bestehend aus dem "ubergebenen Wert und seiner Typ\-repr"asentation aufbaut.
Die Typ\-repr"asentation wird dabei aus dem inferierten statischen Typ wie oben 
angegeben generiert. Dieses Tupel wird wiederum in den urspr"unglichen
Syntaxbaum eingesetzt. Der beispielsweise f"ur den Aufruf {\em dynamic\_new(3)} 
generierte Code sieht dann aus, als h"atte der Programmierer folgendes 
geschrieben:
\begin{xple}
  \kw{tuple}
     \kw{let} value = 3
     \kw{let} type = typeRep\_new(:Int)
  \kw{end}
\end{xple}
Durch den Compiler wird allerdings sichergestellt, da"s die Typ\-repr"asentation
auch wirklich zum Wert pa"st, da dessen Typ inferiert und nicht, wie im
Beispiel, explizit angegeben wird.

Die Umsetzung der Anweisung {\sl dynamic\_be} in Code, der einen
Laufzeit-Subtyptest veranla"st, verl"auft "ahnlich wie bei der Generierung von 
Typ\-repr"asentationen, denn auch {\em Funktionen} des Compilers
k"onnen als Objektliteral in den Syntaxbaum eingef"ugt werden.
Es wird in diesem Fall eine Funktionsapplikation generiert, die als 
Wert eine Compiler-Funktion enth"alt, die die
gew"unschte Funktionalit"at (Subtyptest) realisiert.
Probleme treten bei diesem Ansatz (Bindung zur "Ubersetzungszeit) jedoch durch 
die hybride Natur der jetzigen Modulverwaltung auf, die lineare 
Repr"asentationen "ubersetzter Module sowohl im Objektspeicher h"alt (genauer 
gesagt in einem Modul-{\em Cache}) als auch im Dateisystem 
ablegt. Die lineare Repr"asentation eines "ubersetzten Moduls, die Code 
enth"alt, der einen Subtyptest basierend auf Struktur"aquivalenz ausf"uhrt, 
verbraucht jedoch unn"otig
viel Platz, denn zum Bindungszeitpunkt dieses Moduls existiert dieser Code 
ohnehin bereits im Objektspeicher. F"ur diesen Fall der Benutzung von {\sl
dynamic\_be} innerhalb eines Moduls sollte die Bindung dieses Codes 
zweckm"a"sigerweise zu einem sp"ateren Zeitpunkt erfolgen, am besten in
der separaten Modulbindungsphase. 


\subsubsection{Aufbau von Typrepr"asentationen}
\label{typeRep-Generierung}

Die Typ\-repr"asentationen, die in der Typ\-"uberpr"ufungskomponente des
\TL-Compilers eingesetzt werden, basieren auf der sogenannten {\em de Bruijn
Notation} \cite{deBr72,ACCL90} zur Formalisierung der Sichtbarkeitsregeln 
von Variablen. Dies bedingt die Abh"angigkeit {\em aller} dieser 
Typ\-repr"asentationen von {\em einem} gemeinsamen statischen Kontext, sofern
sie Indices auf Signaturen in diesem Kontext enthalten, was in der Regel der
Fall ist.

Da dynamische Typen vor allem dazu gebraucht werden, Werte zusammen mit ihrer
Typ\-information zwischen verschiedenen Kontexten zu transferieren, ist die
Abh"angigkeit der Typ\-information von einem gemeinsamen Kontext, der "uber
einen initialen Kontext hinausgeht, unerw"unscht.
Eine L"osung f"ur dieses Problem w"are, jeweils eine Typ\-repr"asentation 
zusammen mit ihrem Kontext zu aggregieren. Dieses Vorgehen hat jedoch zwei 
gravierende Nachteile:
\begin{enumerate}
\item Der Kontext enth"alt im allgemeinen Signaturen, die von der 
Typ\-repr"asentation nicht (per de Bruijn Index) referenziert werden.
Dieser u.U. sehr gro"se Anteil an "uberfl"ussiger Information w"urde sich 
insbesondere beim Transfer von Typ\-repr"asentationen zwischen autonomen 
Objektspeichern negativ auswirken. 
Ein Entfernen nicht referenzierter Signaturen w"urde eine aufwendige Anpassung 
s"amtlicher Indices im Kontext nach sich ziehen.
\item Beim dynamischen Subtyptest (initiiert durch die Anweisung {\sl
dynamic\_be}) m"u"ste der
Kontext, in der die Typ\-komponente des automorphen Wertes gilt, mit dem 
aktuellen Kontext
vereinigt werden, da Subtypbeziehungen in der derzeitigen Implementation
des \TL-Typ"uberpr"ufers nur in einem gemeinsamen Kontext
gelten k"onnen. Auch dies w"are eine teure Laufzeitoperation.
\end{enumerate}

Aus diesen Gr"unden wird eine zweite Darstellung von Typ\-repr"asentationen
eingef"uhrt, die Typ\-variablen nicht durch de Bruijn Indices, sondern durch 
direkte Referenzen auf ihr definierendes Auftreten repr"asentiert. Diese 
Darstellung entspricht folgendem rekursiven Typ~{\sl T}:
\begin{xple}
\begin{tabbing}
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx\= xxxxxx \= \kill
  \kw{Let Rec} T $<$:\kw{Ok} = \\
    \kw{Tuple}\\
      \kw{case} okCase,\\
           nokCase \kw{with}\\
      \kw{case} baseCase \kw{with} \> (* Basistyp *)\\
        name :String\\
      \kw{case} ideCase \kw{with} \> (* Typbezeichner *) \\
        definition :Signature     \> (* direkte Referenz zur Definition *)\\
      \kw{case} adtCase \kw{with} \> (* abstrakter Typbezeichner *) \\
        definition :Signature     \> (* direkte Referenz zur Definition *)\\
        path :\kw{Tuple}\\
                  \kw{var} oid :String\\ 
                  (* Pfad (als String), auf dem der ADT referenziert wurde. Wird\\
                     zur Laufzeit durch die OID\footnote{OID: Object Identificator}des betreffenden Moduls ersetzt. *)\\
              \kw{end}\\
      \kw{case} funCase \kw{with} \> (* Funktionstyp *)\\
        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}  \> (* Typoperator *)\\
        signatures :list.T(Signature)\\
        range :T  \\
      \kw{case} arrayCase \kw{with}\\
        elementType :T\\
      \kw{case} appCase \kw{with}   \> (* Typoperatorapplikation *)\\
        oper :T\\
        arguments :list.T(Signature) \> (* rekursiver Typ *)\\
      \kw{case} recCase \kw{with}\\
        bindingIndex :Int\\
        typeBindings :list.T(Signature) \> (* Typ einer ver"anderlichen Bindung *)\\
      \kw{case} varCase \kw{with}\\
        type :T\\
    \kw{end}\\
\\  
  \kw{and} Signature $<:$Ok = \kw{Tuple}\> (* Enth"alt auch Typbindungen *)\\
    ide :\kw{Tuple} name :String pos :SourcePosition \kw{end}\\
    \kw{var} type :T \> \\
    \kw{case} typeCase, typeEqualCase \kw{with} \> (* T $<:$A bzw. Let T = A *) \\
      typeID :time.T      \> (* Zeitstempel *)\\
    \kw{case} typeBoundCase \kw{with} \> (* Let [Rec] T $<:$B = A *)\\
      typeID :time.T     \> (* Zeitstempel *)\\
      \kw{var} bound :T 
    \kw{case} valueCase \\
    \kw{case} locationCase\\ 
  \kw{end}\\
\\
  \kw{and} Case $<:$Ok = \kw{Tuple}\\
    label :String               \\
    signatures :list.T(Signature) \> (* zus"atzliche Felder dieser Variante *)\\
  \kw{end}\\
\end{tabbing}
\end{xple}

Das nachfolgende Beispiel verdeutlicht zusammen mit Abbildung 
\ref{typeRep-objectref} den Unterschied zwischen beiden Typdarstellungen.
\begin{quote} 
Angenommen, der initiale Kontext enthalte die Deklaration des Typs {\sl Int}
an Position 50 und die Deklaration des Typs {\sl String} an Position 55. Es 
gelten folgende Typ\-bindungen:
\begin{samepage}
\begin{xple}
        \kw{Let} Age = Int@50
        \kw{Let} Address = \kw{Tuple} street :String@56 city :String@57  zip :Int@ \kw{end}
        \kw{Let} Person = \kw{Tuple} name :String@58  age :Age@3  address :Address@3 \kw{end}
        \kw{Let} Student = \kw{Tuple} 
                                 name :String@59  
                                 age :Age@4  
                                 address :Address@4 
                                 semester :Int@57 
                           \kw{end}
\end{xple}
\end{samepage}
\end{quote}

\begin{figure}[hbt]
\leavevmode
\def\epsfsize#1#2{0.6\textwidth}
\centerline{\epsffile{typeRep.epsf}}
\caption{\label{typeRep-objectref} Typ\-repr"asentationen mit Objektreferenzen}
\end{figure}

Die Darstellung mit direkten Referenzen
entspricht einem gerichteten Graph, der jedoch durch die M"oglichkeit
rekursiver Typ\-definitionen auch Zyklen enthalten kann.
Zu beachten ist dabei, da"s Typ\-repr"asentationen gemeinsame Komponenten
teilen (da sie Typ\-variablen enthalten k"onnen), aber trotzdem
kontextunabh"angig sind. Wird z.B. ein automorpher Wert in eine
Datei geschrieben, so werden alle von seiner Typ\-komponente aus transitiv 
erreichbaren Signaturen erfa"st. Man erh"alt dadurch automatisch den
gew"unschten minimalen Kontext\footnote{
d.h. der Kontext enth"alt keine nichtreferenzierten Typ\-bindungen}, 
da dieser durch die Darstellung als
Objektgraph in jeder Typ\-repr"asentation implizit vorhanden ist.

Generierte Typ\-repr"asentationen f"ur Typ\-bindungen werden in einer globalen 
Tabelle im Objektspeicher verwaltet. Durch die Verwendung der Objektidentit"at 
der Typ\-bezeichner von Signaturen als Schl"ussel dieser Tabelle wird 
gew"ahrleistet, da"s Typ\-repr"asentationen nur dann eine Typ\-bindung teilen, 
wenn sie dieselbe Quelltextdefinition dieser Typ\-bindung referenzieren.


                \section{Der aufrufbare Compiler}

Mit der Anwendungsschnittstelle des aufrufbaren \TL-Compilers werden zwei Ziele
verfolgt:
\begin{enumerate}
\item Unterst"utzung typsicherer laufzeitreflektiver Programmierung. 
\item Realisierung eines flexiblen Mechanismus zur {\em inkrementellen 
"Ubersetzung und Aus\-f"uh\-rung} von \TL-Ausdr"ucken als Bibliotheksdienst.
\end{enumerate}
Inkrementelle "Ubersetzung wird dem Benutzer bisher durch den
interaktiven {\em top Level} (textuelle Schnittstelle des
Tycoon-Systems) angeboten. Diesem mangelt es aber insofern an 
Flexibilit"at, als da"s er nur eine
flache, monolithische Sicht auf Bindungen im Objektspeicher bietet. 
Da er nur monoton wachsen kann, geht schnell die "Ubersicht "uber vorhandene
Bindungen verloren. Sein Einsatzbereich beschr"ankt sich im wesentlichen auf
die Auswertung kurzer Ausdr"ucke (Anfragen) und die Parametrisierung des
Compilers durch Auswertung spezieller Kommandos.
In gro"sen persistenten Systemen ist jedoch eine kontrollierte Evolution
von Daten und Funktionen im Objektspeicher nur dann m"oglich, wenn 
vorhandene Bindungen geeignet strukturiert werden k"onnen.
Nachfolgend werden daher {\em Environments} eingef"uhrt, welche den
bisherigen {\em top Level} ersetzen. Sie erm"oglichen es dem  
Anwendungsprogrammierer, den Objektspeicher als eine Art {\em repository} f"ur 
programmiersprachliche Objekte zu verwenden. Die Strukturierung des
Namensraumes aller Objekte im Objektspeicher durch Environments 
\cite{DCC92}, 
die M"oglichkeit der inkrementellen "Ubersetzung sowie nicht zuletzt die 
Persistenz (durch Erreichbarkeit definiert) bewirken durch ihr Zusammenspiel 
einen Synergie-Effekt, der sich besonders bei der GUI-gest"utzten Programmierung,
beispielsweise f"ur Ad-hoc-Anfragen, positiv auswirkt (siehe Abschnitt
\ref{scope-browsing}).


        \subsection{Environments}
        \label{environments}

In \cite{Mor*94,Dea89} sind Environments definiert als die unendliche 
Vereinigung aller benannten Kreuzprodukte. 
Konkret enthalten Environments eine nicht notwendigerweise geordneten 
Sequenz von Werten des nachfolgend definierten Typs {\em Binding}. 
Sie werden dem aufrufbaren Compiler als Parameter 
"ubergeben und erlauben es damit, Ausdr"ucke gegen bereits existierende Werte 
und Typ\-definitionen auszuwerten.
Anders als z.B. in {\sf Napier88} gibt es keine Sprachkonstrukte zur 
Manipulation von
Environments. Stattdessen wird ein {\em add-on} Ansatz bevorzugt und ein 
Bibliotheksmodul, basierend auf dynamischen Typen und automorphen Werten, 
implementiert. Diese Vorgehensweise harmonisiert mit der Auffassung, 
Massendatentypen besser nicht in die Sprache zu integrieren, sondern sie 
in Bibliotheken als generische Dienste anzubieten und damit den Sprachkern so 
einfach wie m"oglich zu halten \cite{MaSc91b}.
Im Tycoon-System ist es jedoch auch m"oglich, die Sprache durch 
{\em syntaktische Erweiterung} \cite{CMA94a}
mittels erweiterbarer Grammatiken mit einer benutzerfreundlicheren Syntax f"ur
die Manipulation von Environments (z.B. in der Art von {\sf Napier88}) 
auszustatten.

Das Bibliotheksmodul {\sl environment} (siehe Anhang \ref{environment})
enth"alt einen abstrakten Datentyp ({\sl environment.T}), auf dem folgende 
Grundfunktionen definiert sind (vergleiche \cite{Dea89}):
\begin{enumerate}
\item Erzeugen eines initialen Environment,
\item Erweiterung um Wert- oder Typbindungen,
\item Aufsuchen von Wert- oder Typbindungen anhand ihres Namens,
\item Entfernen von Bindungen.
\end{enumerate}

\subsubsection{Bindungen}

Nach \cite{MABD90} sind Bindungen charakterisiert durch ein 4-Tupel
bestehend aus Name, Wert, Typ und einen boolschen Wert, der angibt, ob die
Bindung ver"anderlich oder konstant ist. 
Mit Hilfe dynamischer Typen und automorpher Werte lassen sich Bindungen durch
folgenden Optionstyp darstellen:
\begin{xple}
  \kw{Let} Binding = \kw{Tuple}
    name :String
    \kw{case} value \kw{with}
      value :dynamic\_T
    \kw{case} location \kw{with}
      value() :dynamic\_T
      setValue(:dynamic\_T) :\kw{Ok}
    \kw{case} type \kw{with}
      type :typeRep\_T
  \kw{end}
\end{xple}
Anders als bei obigem 4-Tupel werden hier auch Typbindungen ber"ucksichtigt.

Ver"anderliche Bindungen m"ussen durch den Compiler erzeugt werden, da nur er
die Zelle kennt, in der der betreffende Wert gespeichert wird. Er kann dem 
Benutzer jedoch Zugriffsfunktionen auf diese Zelle zur Verf"ugung stellen. 
Eine ver"anderliche Bindung kann somit auf zwei Arten modifiziert werden:
Einerseits von der Benutzerebene direkt durch Aufruf der Funktion {\sl
setValue()}, andererseits durch die reflektive Auswertung eines Ausdrucks 
(Zuweisung) gegen ein Environment, das diese Bindung enth"alt.


\subsubsection{Verwendungsm"oglichkeiten}

Da Environments zu jeder Bindung sowohl Typinformation als auch den Wert
selbst enthalten, erm"oglichen sie sowohl die "Ubersetzung als auch die 
Ausf"uhrung von Ausdr"ucken. Sie subsumieren damit die Funktionalit"at des
bisherigen \TL\ {\em top level}. 

Durch Schachtelung,
ausgehend von einer persistenten Wurzel vom Typ {\sl environment.T}, bieten sie 
eine flexible M"oglichkeit zur Strukturierung und Typisierung des 
Objektspeichers (siehe Abbildung \ref{envs-in-store}). 

\begin{figure}
\leavevmode
\def\epsfsize#1#2{0.7\textwidth}
\centerline{\epsffile{envs-in-store.epsf}}
\caption{\label{envs-in-store} Objektspeicher als Baum von Environments}
\end{figure}

Weitere Eigenschaften sind
\begin{itemize}
\item Erweiterbarkeit: Environments k"onnen sowohl wachsen 
(durch Auswertung von Ausdr"ucken) als auch schrumpfen (durch L"oschen von 
Bindungen).
\item Migrationsm"oglichkeit von Bindungen: Durch die Darstellung der 
(dynamischen) Typ\-information durch direkte Referenzen sind Bindungen zwischen 
Environments leicht kopierbar, ohne die referentielle Integrit"at von
Typen zu verletzen. Dadurch ist eine Restrukturierung des 
Objektspeichers durch den Anwender m"oglich\footnote{
Eine Restrukturierung des Objektspeichers konnte bisher nur von der
Freispeicherverwaltung des Laufzeitsystems bei der {\em garbage collection}
vorgenommen werden.}.
\item Unterst"utzung von Reflektion: Der Compiler kann sich selbst, d.h. die 
Bindungen aus denen er besteht, typisiert im Objektspeicher in einem 
Environment darstellen und damit seinen Zustand, z.B. durch den Anwender oder 
durch Werkzeuge einer Programmierwerkbank zugreifbar machen.
\end{itemize}
Der Graph, der durch die Schachtelung von Environments entsteht,
entspricht dem hierarchischen Aufbau traditioneller Dateisysteme \cite{Dea89}.
Anders als in diesen lassen sich jedoch Daten beliebiger Struktur typisiert 
speichern, w"ahrend Dateisysteme nur wenige
unterschiedliche, flach strukturierter Dateiformate (z.B. ASCII-Format, 
Bin"arformat) zulassen.

Das Environment der obersten Ebene (Wurzel der Persistenz) l"a"st sich
als Einstiegspunkt eines {\em repository} f"ur typisierte Funktionen und Daten 
auffassen. Das Auffinden von Wert- und Typ\-bindungen in diesem {\em repository}
kann durch ein GUI-gesteuertes Navigationswerkzeug oder durch 
programmiersprachlich spezifizierte Anfragen unterst"utzt werden.


        \subsection{Architektur der Compiler-Schnittstelle}
        \label{Compiler-Schnittstelle}

Die bisherige Architektur des \TL-Compilers bietet dem Benutzer lediglich einen
schmalen Einstiegspunkt, n"amlich eine kommandoorientierte textuelle 
Schnittstelle nach dem Muster {\em read -- eval -- print} zur "Ubersetzung und 
Ausf"uhrung von \TL-Ausdr"ucken (siehe Kapitel \ref{tycoon}).
Ziel einer revidierten Architektur ist die "`Verbreiterung"' dieser
Schnittstelle, einerseits zur Benutzung aus laufzeitreflektiven 
Anwendungsprogrammen heraus, andererseits als Basis f"ur Werkzeuge einer 
integrierten Programmierwerkbank, wie in Abbildung \ref{compiler-architektur}
veranschaulicht. Sie erm"oglicht es, \TL\ als eingebettete Sprache in 
Anwendungsprogrammen zu verwenden, wobei dann auch die Programmierwerkbank als
Anwendungs- und nicht als Systemprogramm z"ahlt.

\begin{figure}
\leavevmode
\def\epsfsize#1#2{0.8\textwidth}
\centerline{\epsffile{compiler-architektur.epsf}}
\caption{\label{compiler-architektur} Schmaler Einstiegspunkt der bisherigen
Architektur gegen"uber einer reflektiven Architektur}
\end{figure}

Bisher existierten gebundene Anwendungsprogramme getrennt vom Compiler im
Objektspeicher. Obwohl die Laufzeitumgebung (d.h. der Objektspeicher) den 
Compiler enth"alt, sind seine Komponenten von Anwendungsprogrammen aus nicht 
zug"anglich, da keine Typ\-information zu diesen Komponenten in einer 
gemeinsamen Umgebung existiert.  

Dynamische Typ\-information macht es jedoch m"oglich, Laufzeitkomponenten des
Compilers in einem Environment zu binden und dieses z.B. innerhalb einer
Programmierwerkbank dem Benutzer als Auswertungsumgebung zur Verf"ugung zu
stellen. Weiterhin k"onnen ihm, abgesehen von Komponenten des 
Compilers selbst, auf diese Weise auch alle \TL-Standardmodule zur Verf"ugung 
gestellt werden. Dadurch erh"alt der Benutzer eine Bibliothek vordefinierter 
Bindungen im Objektspeicher schon zum Systemgenerierungszeitpunkt.

Da Komponenten des Compilers als vordefinierte Bindungen existieren, enf"allt
damit die Notwendigkeit einer Kommandosprache zur Steuerung des
"Ubersetzungsvorganges (setzen von Schaltern, Zustandsvariablen etc., Details
zur Kommandosprache siehe \cite{MMM93}), da hierf"ur \TL-Anweisungen eingesetzt 
werden k"onnen, z.B.
\begin{xple}
  compiler.traceSubtypeTest(true)  
\end{xple}
statt
\begin{xple}
  do set traceSubtypeTest true. 
\end{xple}
Eine auf dieser Compilerschnittstelle aufsetzende textuelle 
Benutzerschnittstelle "ahnelt in ihrem Verhalten sehr den aus verschiedenen
Betriebssystemen (z.B. UNIX-Derivate) bekannten {\em Shells}, mit dem 
Unterschied, da"s
statt einer Kommandosprache mit mehr oder weniger hoch entwickelten 
Kontrollstrukturen eine algorithmisch vollst"andige Programmiersprache zur 
Verf"ugung steht
\cite{Dea88}. Analog zu {\em Shell}-Kommandointerpretern, die Dateien in 
hierarchischen Verzeichnisstrukturen manipulieren, bearbeitet das 
Tycoon-Laufzeitsystem
persistente Wert- und Typ\-bindungen in hierarchischen Environments.

Zur Durchf"uhrung der "Ubersetzung baut der Compiler intern verschiedene
Datenstrukturen auf, die Zwischenergebnisse des "Ubersetzungsvorganges
repr"asentieren, wie z.B. Syntaxb"aume und Zwischencode. Durch die reflektive
Zugangsm"oglichkeit zu Komponenten des Compilers k"onnen dem Benutzer 
diese Strukturen f"ur eigene Auswertungen nach jedem "Ubersetzungsvorgang 
zur Verf"ugung gestellt werden.  


\subsubsection{Schnittstelle 'Compiler'}

Aufbauend auf existierenden Komponenten (Parser, Typ"uberpr"ufer, 
Codegenerierung) wird in dieser Arbeit eine von \TL-Programmen aus aufrufbare 
Schnittstelle zum \TL-Compiler entwickelt. Wesentliches Merkmal dieser 
Schnittstelle ist die Parametrisierung des "Ubersetzungsvorgangs durch ein 
Environment (siehe Abschnitt \ref{environments}). Dadurch k"onnen 
Programme gegen Werte der aktuellen Laufzeitumgebung "ubersetzt und ausgef"uhrt 
werden, z.B. durch eine Funktion folgender Signatur:
\begin{xple}
  compileString(code :String  env :environment.T) :\kw{Fun}() :Binding
\end{xple}
Diese Funktion "ubersetzt eine Zeichenkette gegen das "ubergebene 
Environment und gibt eine Funktion zur"uck, die bei ihrer Ausf"uhrung
den "ubersetzten Ausdruck auswertet. 
Die letzte durch Auswertung des Ausdrucks entstandene Bindung wird 
zur"uckgegeben und als Seiteneffekt das "ubergebene Environment um die neu 
etablierten Bindungen erweitert. Bei Fehlern w"ahrend der "Ubersetzung wird 
ein Ausnahmepaket mit entsprechenden Fehlermeldungen erzeugt.

Mit Hilfe von Funktionen h"oherer Ordnung kann der "Ubersetzungs- und
Auswertungsvorgang in seine einzelnen Phasen zerlegt und am jeweiligen
Phasenende quasi angehalten und wiederaufgenommen werden.
\begin{xple}
\begin{tabbing}
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx\= xxxxxx \= \kill
  parse(code :String)        \>(* Parsing *)\\  
    :\kw{Fun}(env :environment.T) \>(* Typ"uberpr"ufung *)\\
      :\kw{Fun}()                 \>(* Codegenerierung *)\\ 
        :\kw{Fun}() :Binding      \>(* Ausf"uhrung, Environment-Manipulation *)\\
\end{tabbing}
\end{xple}
Die Funktionen {\sl compileString} und {\sl eval} k"onnen dann durch die 
Bindungen
\begin{xple}
  \kw{let} compileString(env :environment.T code :String) :\kw{Fun}() :Binding = 
    parse(code)(env)()

  \kw{let} eval(code :String  env :environment.T) :Binding = 
    compileString(env code)()
\end{xple}
definiert werden.
Das der Funktion {\sl eval} "ubergebene Environment wird typischerweise
zuvor mit Werten und Typen aus dem "au"seren Kontext gef"ullt, wobei diese
zun"achst in automorphe Werte bzw. Typ\-repr"asentationen konvertiert werden
m"ussen.
Umgekehrt k"onnen automorphe Werte und Typ\-repr"asentationen aus dem durch die 
Auswertung von Ausdr"ucken erweiterten Environment herausgeholt und im 
"au"seren Kontext benutzt werden. Dies folgt direkt aus der oben beschriebenen
Kontextunabh"angigkeit von Laufzeit-Typ\-repr"asentationen.

Falls der Benutzer die Typen der durch den Compiler erzeugten Bindungen an
automorphe Werte statisch kennt, so kann er durch Anwendung der Anweisung 
{\sl dynamic\_be} (dynamischer Subtyptest) die entsprechenden automorphen Werte 
wieder als statisch typisierte Werte in den "au"seren Kontext einbinden.  
Hat er dieses Wissen nicht, so kann er immerhin noch durch Inspektion der 
automorphen Werte typgesteuerte Berechnungen im "au"seren Kontext durchf"uhren.

Im folgenden Beispiel soll eine Operation auf zwei automorphen Werten
durchgef"uhrt werden, deren Typ statisch nicht bekannt ist.
Unter der Annahme, da"s beide Werte eine Komponente mit
der Signatur {\sl salary :Int} enthalten, wird Code generiert, der die 
beiden Felder addiert und das Ergebnis zur"uckliefert. Falls diese Annahme
nicht zutrifft, wird eine Ausnahme ausgel"ost mit den Compiler-Fehlermeldungen
als Ausnahmepaket.
\begin{xple}
  \kw{let} sumOfSalaries(employee1, employee2 :dynamic\_T) :Int =  
    \kw{begin}  
      \kw{let} env = environment.initial() 
      environment.addValueBinding(env ''employee1'' employee1)
      environment.addValueBinding(env ''employee2'' employee2)
      \kw{let} code = ''employee1.salary + employee2.salary''
      \kw{let} resultBinding :Binding = compiler.eval(env code)
      \kw{let} result :dynamic\_T = resultBinding!valueCase.value 
      \kw{dynamic\_be}(result :Int)  
    \kw{end}
\end{xple}
Dieselbe Funktionalit"at k"onnte auch mit Hilfe dynamischer Typinspektion
implementiert werden. In Abschnitt \ref{reflect-vs-inspect} werden die beiden
typischen Implementierungsalternativen f"ur typgesteuerte Algorithmen,
Reflektion und Interpretation kurz diskutiert.

Die Bindung von freien Bezeichnern im Quelltext an aktuelle Werte erfolgt 
unmittelbar vor Ausf"uhrung der von {\sl compileString} zur"uckgegebenen 
Funktion. Im zu "ubersetzenden Code referenzierte 
(Wert)-Bindungen im "ubergebenen Environment k"onnen also bei Bedarf nach der 
"Ubersetzung noch typsicher modifiziert werden\footnote{
Dies wird erm"oglicht durch die Funktion {\sl environment.changeValue(env 
:environment.T name :String value :dynamic\_T)}.}, da der "ubersetzte Code
nur Positionsinformation "uber Werte im Environment enth"alt und nicht die 
Werte selbst. Wird jedoch vor der Ausf"uhrung keine "Anderung mehr am
Environment vorgenommen, so ist der resultierende Effekt derselbe, als h"atte
die Bindung direkt zur "Ubersetzungszeit stattgefunden. 


\subsubsection{Integration der reflektiven Compilerschnittstelle}
\label{typechecker-integration}

Die Hauptproblematik der Integration reflektiver F"ahigkeiten in Tycoon
liegt in den unterschiedlichen Repr"asentationsformen f"ur Typen zur Laufzeit
und zur "Ubersetzungszeit (siehe dazu Abschnitt \ref{typeRep-Generierung}).
Diese Tatsache macht h"aufige Konvertierungen von Typen in die jeweils andere
Darstellung erforderlich: Der Typ"uberpr"ufer verlangt Typen in der Darstellung
mit de-Bruijn-Indices, Laufzeitmanipulationen mit Typ\-repr"asentationen
erfordern die Darstellung mit direkten Referenzen. Diese
Konvertierungsoperationen verhindern eine zufriedenstellende Performanz.

Ziel weiterer Aktivit"aten im Tycoon-Projekt ist die Vereinheitlichung der
Darstellung von Typ\-repr"asentationen sowohl zur "Ubersetzungszeit als auch
zur Laufzeit, um auch den Anforderungen dynamischer Typisierung gerecht zu 
werden. Dies macht eine Re-Implementierung des Typ"uberpr"ufers erforderlich, 
welche im Rahmen einer parallel zu dieser Arbeit laufenden Diplomarbeit
stattfindet.


                \section{Anwendungen von Laufzeit-Reflektion}

Laufzeit-Reflektion ist immer dann sinnvoll anzuwenden, wenn zur
Generierung von Quellcode auf Information zugegriffen wird, die erst zur 
Laufzeit vorhanden ist. Diese Information kann entweder vom Benutzer
eingegeben werden oder aus dynamischer Typinformation bestehen.
Typsichere Laufzeit-Reflektion ist eng gekoppelt mit dynamischer
Typinformation:
Einerseits ist sie selbst eine Anwendung, die auf dynamischer Typisierung
beruht, andererseits verhilft sie einigen generischen, typgesteuerten 
Anwendungen zu einer potentiell effizienteren Implementierung, indem der Anteil 
interpretativer Berechnungen durch spezialisierte generierte Codefragmente 
ersetzt wird. Dies verdeutlichen die nachfolgenden Beispiele.


        \subsection{Dynamische Codegenerierung}

Der in Kapitel \ref{gdl} vorgestellte Gateway-Generator ist als typgesteuerte
Anwendung einzustufen, denn GDL-Schnittstellenbeschreibungen k"onnen als Typen 
aufgefa"st werden, da sie auf \TL-Schnittstellen (d.h. \TL-Tupeltypen) 
abbildbar sind.  Das Prinzip des Generators basiert somit auf der Generierung 
von Gateway-Implementationen durch Interpretation von Typ\-repr"asentationen.

Die Generierungsphase ist dabei v"ollig getrennt von der Benutzungsphase, da der
generierte Quelltext zun"achst im Dateisystem abgelegt und anschlie"send 
"ubersetzt und in den Objektspeicher importiert (gebunden) wird. 
Bei "Anderungen an Schnittstellenbeschreibungen kann eine Neugenerierung und
Einbindung des zugeh"origen {\em Stub}-Codes somit nicht im laufenden Betrieb 
einer Anwendung erfolgen. Insbesondere kann die Bibliotheksbeschreibung 
({\em library}) nur statisch ge"andert werden. 

In den meisten F"allen ist eine dynamische "Anderung
der Gateway-Implementation nicht erforderlich, da "Anderungen an
Schnittstellenbeschreibungen eher selten sind, und Anwendungen sich nicht
notwendigerweise {\em dynamisch} an diese "Anderungen anpassen m"ussen. 
Bei benutzerseitig konfigurierbaren Anwendungen ist jedoch eine dynamische 
Anpassung des laufenden Programmes an Benutzereingaben n"otig.   

Als Beispiel hierf"ur sei die in \cite{CK94} diskutierte dynamische
Anpassung der grafischen Benutzerschnittstelle einer
Anwendung angef"uhrt. Hierbei kann der Benutzer zwischen mehreren 
UI-Komponenten ausw"ahlen, wobei u.U. eine hohe Vernetzung zwischen diesen
Komponenten besteht. Ohne Reflektion ist der Zugriff der funktionalen
Komponenten einer Anwendung auf Komponenten der Benutzerschnittstelle nur {\em
indirekt} m"oglich: Zun"achst mu"s eine abstrakte UI-Komponente aufgerufen
werden, die anhand der zuvor eingegebenen Benutzerpr"aferenzen entscheidet,
welches konkrete UI-Element aufzurufen ist. Mit Reflektion l"a"st sich
in die laufende Anwendung Code integrieren, der den Aufruf der konkreten
UI-Komponente {\em direkt} ausf"uhrt, wodurch ein Effizienzgewinn erzielt wird.
Ist die Menge der UI-Komponenten durch den Benutzer erweiterbar (z.B. durch 
Konstruktion von Dialogen aus primitiveren UI-Komponenten), ist eine L"osung 
ohne Reflektion schon nicht mehr m"oglich, da zur
Konstruktionszeit der Anwendung nicht bekannt ist, welche UI-Komponenten es zur
Laufzeit geben wird.

In Abschnitt \ref{Compiler-Schnittstelle} wird beschrieben, wie 
interne Zust"ande der Programmierumgebung durch den Benutzer mit Hilfe von 
\TL-Ausdr"ucken manipuliert werden k"onnen. Allgemein kann jede \TL-Anwendung 
die reflektive Compiler-Schnittstelle 
dem Benutzer zur Verf"ugung stellen, indem es ein Environment mit
Werten aus dem eigenen Kontext f"ullt und vom Benutzer eingegebene
Zeichenketten als Ausdr"ucke gegen dieses Environment auswertet. 
Dadurch, da"s der Anwendungsprogrammierer selbst bestimmt, welche Werte der
Anwendung er dem Benutzer sichtbar und damit manipulierbar macht, ist eine 
kontrollierte Zustandsver"anderung gew"ahrleistet. Diese M"oglichkeit ist 
nat"urlich nicht geeignet f"ur Endbenutzer-Anwendungen, da Endbenutzer sich 
normalerweise nicht mit den Details der Implementierungssprache 
auseinandersetzen wollen und k"onnen. 


\subsubsection{Nat"urlicher Verbund beliebiger Relationen}
\label{join}

Ein weiteres Beispiel f"ur dynamische Codegenerierung zur Erreichung h"oherer
Generik ist der nat"urliche Verbund beliebig typisierter Relationen 
\cite{Kir92a}. Hierbei wird aus den Typ\-repr"asentationen der Eingaberelationen 
eine spezialisierte Repr"asentation einer Funktion generiert, die den 
Verbund durchf"uhrt. Dabei ist auch die Typ\-repr"asentation der Resultatrelation
zu ermitteln. Im Anhang \ref{natural-join} findet sich die vollst"andige
Definition des Generators in \TL. Dessen Benutzung im Zusammenhang mit dem 
aufrufbaren Compiler vollzieht sich etwa folgenderma"sen\footnote{
Relationen seien hier durch Mengen dargestellt.}: 
\begin{xple}
  \kw{import} environment joinGenerator set compiler

  \kw{Let} R1 = \kw{Record} a,b,c :String \kw{end}
  \kw{Let} R2 = \kw{Record} b,c,d :String \kw{end}
  \kw{Let} Result = \kw{Record} a,b,c,d :String \kw{end}

  \kw{let} code :String = generateJoin(\kw{typeRep\_new}(:R1) \kw{typeRep\_new}(:R2))
  \kw{let} env :environment.T = ... (* obtain environment from generator *)
  \kw{let} joinFunction :dynamic\_T = compiler.eval(s code)!valueCase.value
  \kw{let} joinFunction = 
    \kw{dynamic\_be}(joinFunction :\kw{Fun}(:set.T(R1) :set.T(R2)) :set.T(Result))
  ...  (* define rel1 :set.T(R1) and rel2 :set.T(R2) *) ...
  \kw{let} resultRel = join(rel1 rel2)
\end{xple}

Eine nichtreflektive L"osung erfordert mehr Berechnung zur Laufzeit,
da die Eingaberelationen mittels Ad-hoc-Typinformation\footnote{
z.B. eine Listendarstellung der Attributnamen der Elementtupel}
zun"achst auf Kompatibilit"at getestet werden m"ussen, und der Algorithmus zur 
Produktion der Resultattupel, der u.a. einen Test auf Gleichheit zweier
Attributbezeichner enth"alt, diese Typinformation interpretieren mu"s.

Problematisch an der reflektiven L"osung ist die Tatsache, da"s der Benutzer
der generierten Funktion deren Signatur statisch kennen mu"s, also insbesondere
auch den Resultattyp, obwohl der Generator ihm die Aufgabe der Berechnung des
Resultattyps eigentlich abgenommen hat. Die Angabe der vollst"andigen
Signatur der generierten Funktion kann umgangen werden, indem man davon
ausgeht, da"s grunds"atzlich eine Funktion mit dem R"uckgabetyp {\sl dynamic\_T}
generiert wird. Nach Durchf"uhrung der Verbundoperation steht die 
Resultatrelation dann als automorpher Wert zur Verf"ugung. Dieser kann zwar
durch ein generisches Datenvisualisierungswerkzeug dargestellt werden, doch
ohne weiteres statisches Wissen um den Aufbau seiner Typkomponente lassen sich 
keine Mengenoperationen auf die Wertkomponente anwenden, was seinen 
Anwendungsbereich unakzeptabel drastisch einschr"ankt.

%#        \subsection{Implementation von Datenmodellen}


        \subsection{Implementierung von "Ubersetzungszeit-Reflektion}

Nutzt man das Modul {\sl compiler} in einer zus"atzlichen 
{\em bootstrap}--Iteration zur Implementierung des Compilers selbst, 
ist man in der Lage,
\TL-Funktionen schon zur "Ubersetzungszeit auszuf"uhren. Dadurch wird
die "Ubersetzung selbst zu einem laufzeit-reflektiven Vorgang. 

Eine einfache Anwendung f"ur diese Methodik ist z.B. das Auswerten von
Ausdr"ucken zur "Ubersetzungszeit, sofern diese nicht auf Laufzeitwerte
zugreifen. Ein Beispiel (in einer testweise implementierten Syntax):
\begin{xple}
  \kw{let} zehnMega = \kw{reflect} 10 * 1024 * 1000 \kw{end} 
\end{xple}
Hierbei wird der in {\bf reflect ... end} geklammerte Ausdruck zur
"Ubersetzungszeit ausgewertet und das Ergebnis als Objektliteral in den 
Syntaxbaum implantiert. 
Die Umgebung, in der dieser Ausdruck ausgewertet wird, kann wiederum mit
Werten des Compilers vordefiniert werden.

Entscheidend f"ur einen sinnvollen Einsatz von Reflekion zur "Ubersetzungszeit
ist jedoch die M"oglichkeit, auf die aktuelle "Ubersetzungszeitumgebung
zugreifen zu k"onnen, also insbesondere auf die Typinformation des aktuellen
Kontexts. Dies ist in der reflektiven Programmiersprache {\sf TRPL} \cite{TRPL90}
verwirklicht. {\sf TRPL} erlaubt die Definition von Macros, die durch Argumente 
aus der abstrakten Syntax der Sprache parametrisiert werden. Im Rumpf des
Macros kann mit Hilfe vordefinierter Abstraktionen auf Typ- und
Coderepr"asentationen der aktuellen "Ubersetzungsumgebung zugegriffen werden.
Die durch den Macroaufruf generierte abstrakte Syntax wird in den aktuellen
Syntaxbaum eingegliedert und in der "Ubersetzung fortgefahren.

Reflektion zur Laufzeit ist m"achtiger als Reflektion zur
"Ubersetzungszeit, da Generatoren auf Laufzeitwerte (z.B. Benutzereingaben,
zur Laufzeit modifizierte Werte im Objektspeicher) zugreifen k"onnen.
Weiterhin ist in persistenten Systemen die Abgrenzung zwischen 
"Ubersetzungszeit und
Laufzeit weniger scharf als in nichtpersistenten Systemen, da durch die
M"oglichkeit der inkrementellen "Ubersetzung und Ausf"uhrung praktisch die
gesammte Lebensdauer des Objektspeichers als "`Laufzeit"' betrachtet werden
kann, in der persistente Seiteneffekte auftreten. Bei reflektiven Anwendungen
geh"oren zu diesen Seiteneffekten insbesondere die persistente Speicherung 
der Generatoren sowie des generierten Codes. Durch das Angebot beider Formen von
Reflektion wird die Ausdrucksm"achtigkeit des Systems somit nicht erh"oht.
%# Vielleicht noch unklar

        \subsection{Reflektion zur Laufzeit versus Typinspektion}
        \label{reflect-vs-inspect}

Zur Implementierung generischer typgesteuerter Algorithmen ist oft sowohl
eine reflektive als auch eine interpretative L"osung m"oglich.
Die reflektive L"osung besteht in der Generierung und Ausf"uhrung typspezifisch
spezialisierter Codefragmente, die in einer durch Typen indizierten persistenten
Tabelle gespeichert werden. Die interpretative L"osung beruht auf der 
Inspektion dynamischer Typinformation (s. Abschnitt \ref{typeRep-Modul}).

Der reflektive Aufruf eines Compilers zur Laufzeit ist eine vergleichsweise
teure Operation, deren Nutzung sich nur dann rechtfertigen l"a"st, wenn ein
Effizienzgewinn gegen"uber einer interpretativen L"osung zu erwarten ist.
Dies ist nur dann der Fall, wenn eine generierte Funktion so
h"aufig aufgerufen wird, da"s sich die relativ hohen "Ubersetzungkosten 
gegen"uber den Interpretationskosten amortisieren (Abbildung \ref{break-even}). 

\begin{figure}
\leavevmode
\def\epsfsize#1#2{0.8\textwidth}
\centerline{\epsffile{break-even.epsf}}
\caption{\label{break-even} Break-Even-Analyse als Entscheidungshilfe f"ur
reflektive oder interpretative Implementierung typgesteuerter Algorithmen}
\end{figure}

Persistente Systeme sind in dieser Beziehung im Vorteil, da sich die 
"Ubersetzungkosten "uber mehrere Programmausf"uhrungen hinweg amortisieren 
k"onnen. Es ist dadurch auch ein weiter vom Ursprung entfernter 
{\em break-even-point} tolerierbar. Der Effizienzgewinn h"angt dabei
ma"sgeblich von der Effizienz der Verwaltung der generierten Funktionen ab.
Wichtige Parameter sind dabei die Gr"o"se der Tabelle, die Trefferrate und
die Kosten f"ur das Auffinden einer Funktion in der persistenten Tabelle 
\cite{Kir92a}.  
In relationalen Datenbanksystemen, z.B. System R, hat sich die
"Ubersetzung mengenorientierter Anfragen als durchweg "uberlegen gegen"uber
ihrer Interpretation herausgestellt \cite{haerder:87}. Dies gilt auch f"ur 
Ad-hoc-Anfragen,
sogar dann, wenn der "ubersetzte Code nicht f"ur mehrmalige Benutzung
aufgehoben wird.

Die Generierung von Funktionen anhand dynamischer Typinformation und deren
Einbindung in den Programmablauf kann auch als eine eingeschr"ankte Form des 
{\em Lernens} aufgefa"st werden, wobei mit jeder generierten Funktion die 
Wissensbasis des reflektiven Programmes erweitert wird. Die maximale Gr"o"se 
dieser Wissensbasis ist dabei nur durch die maximale Gr"o"se des Objektspeichers
beschr"ankt. Wird diese "uberschritten, so k"onnen z.B. nach der LRU-Strategie
({\em least recently used}) Funktionen gegen neu generierte ausgetauscht
werden. Diese Form des {\em Vergessens} hat lediglich Auswirkungen auf die
Performanz zuk"unftiger Aufrufe, wenn diese eine Neugenerierung von Funktionen 
veranlassen.


                \section{Aufrufbare Compiler f"ur andere Programmiersprachen}

In diesem Abschnitt folgt eine Zusammenstellung weiterer Ans"atze, 
Schnittstellen zum Compiler in der eigenen Sprache als Dienst im Gesamtsystem 
zu begreifen. Auff"allig ist, da"s die genannten Beispiele alle aus dem 
Bereich der funktionalen Sprachen entstammen. Ein besonderer Zusammenhang 
zwischen funktionaler und reflektiver Programmierung l"a"st sich jedoch nicht 
belegen.

        \subsection{Lisp} 

In Lisp und seinen verschiedenen Dialekten wird der Interpreter/"Ubersetzer
durch die Basisprimitive {\sl eval} dem Benutzer zur Verf"ugung gestellt.
Dadurch k"onnen beliebige S-Ausdr"ucke zur Laufzeit konstruiert und
ausgewertet werden.
Diese S-Ausdr"ucke k"onnen dabei Bezeichner aus der implizit bekannten 
aktuellen Auswertungsumgebung referenzieren. Die in dieser Arbeit vorgestellte
Schnittstelle zum \TL-Compiler ist dagegen explizit mit einer
Auswertungsumgebung zu parametrisieren. 

Die {\sl eval}-Primitive ist ein sehr flexibles Mittel zur laufzeitreflektiven 
Programmierung, jedoch ist das Schreiben von Generatoren ohne Typ"uberpr"ufung
als noch schwieriger und fehlertr"achtiger anzusehen als in einem typsicheren
Kontext. Im Gegensatz dazu erm"oglichen die nachfolgend behandelten Sprachen 
typsichere linguistische Reflektion.


        \subsection{PS-algol und Napier88}
	\label{napier-compiler}

PS-algol und dessen Nachfolger Napier88 bieten den Compiler als Funktion 
im Objektspeicher an. Dadurch wird er f"ur reflektive Programme zur Laufzeit 
zugreifbar.

In PS-algol \cite{PPRG88} wird diese Funktion, abgesehen vom Quelltext, mit 
einer Struktur
parametrisiert, die zun"achst als Platzhalter fungiert und bei erfolgreicher
"Ubersetzung das Ergebnis aufnimmt. Als Ergebnisse sind nur Funktionen
zugelassen, deren Signaturen statisch bekannt 
sein m"ussen. Der Compiler "uberpr"uft zur Laufzeit, ob der aus dem 
"Ubersetzungsvorgang inferierte Typ mit dem Typ des vom Benutzer "ubergebenen 
Platzhalters "ubereinstimmt. Bei erfolgreicher "Ubersetzung wird ein Zeiger auf
den Platzhalter zur"uckgegeben, ansonsten ein Nullwert.
Zur reflektiven Programmierung eignet sich diese Schnittstelle nur bedingt, da
sie nicht mit Werten aus dem aufrufenden Kontext parametrisiert wird.
Allerdings kann das generierte Programm zur Laufzeit auf Werte im
Objektspeicher "uber vordefinierte Funktionen zugreifen.  

Der aufrufbare Napier88-Compiler stellt eine flexiblere Schnittstelle zur
Verf"ugung. Beliebige Napier88-Ausdr"ucke k"onnen gegen sogenannte {\em
declaration sets} \cite{Mor*94a} "ubersetzt werden. Diese stellen einen 
zus"atzlichen "au"seren Sichtbarkeitsbereich dar und entsprechen in etwa den 
oben vorgestellten Environments. Ausgewertete Ausdr"ucke liefern
einen Wert des in Napier88 vordefinierten Typs {\sl any}\footnote{
Der Typ {\sl any} stellt konzeptionell einen Verbund mit einer nicht statisch
fixierten Menge an Varianten dar. Er entspricht dem im vorigen beschriebenen
Typ des automorphen Wertes ({\sl dynamic\_T}).}. 
Durch Variantenprojektion, die einen dynamischen Typtest impliziert, l"a"st 
sich der in diesen Wert injizierte Wert statisch typisiert in den "au"seren 
Kontext integrieren. Diese Funktionalit"at entspricht in etwa der der oben
beschriebenen Funktion {\sl dynamic\_be}.
Falls keine Annahmen "uber den Typ des injizierten Wertes gemacht werden
k"onnen, gelten auch hier die am Schlu"s von Abschnitt \ref{join} aus Seite
\pageref{join}f gemachten Einschr"ankungen "uber die Verwendbarkeit automorpher
Werte.

Eine weitere wichtige Eigenschaft des Napier88-Compilers ist die Unterst"utzung
der in Kapitel \ref{gui} beschriebenen Bindungsstile, insbesondere Bindung zur
Programmkonstruktionszeit und zur "Ubersetzungszeit sowie von 
getrennter "Ubersetzung und Bindung \cite{Cut92}.

        \subsection{ML und CAML}

In Standard ML of New Jersey \cite{ML93} existieren Schnittstellen zum Compiler 
als ML-Module. "Ahnlich wie in der oben beschriebenen Schnittstelle zum
Tycoon-Compiler l"a"st sich der "Ubersetzungs- bzw. Interpretationsvorgang
durch ein Environment parametrisieren. Dieses gliedert sich in
einen statischen Anteil (Namens- und Typinformation) und einen dynamischen 
(aktuelle Werte). Fehlermeldungen werden durch Ausl"osen einer Ausnahme an die
aufrufende Umgebung propagiert. 

Die Compilerschnittstelle von Standard ML eignet sich nicht zur
typsicheren reflektiven Programmierung. Es ist nicht m"oglich, 
Environments mit
Werten der aktuellen Laufzeitumgebung zu f"ullen und Resultate eines
Auswertungsvorgangs in den den Compiler aufrufenden Kontext zu integrieren, was
direkt auf das Fehlen dynamischer Typ\-information zur"uckzuf"uhren ist.
Somit k"onnen Environments nur durch Auswertung von Ausdr"ucken erweitert
werden. Im Modul {\sl Environment} von Standard ML existieren jedoch Funktionen
zum Filtern von Bindungen und zum Konkatenieren von Environments. 

Ein Vorschlag zur Erweiterung von ML um automorphe Werte ist in \cite{LM91}
beschrieben und im System CAML implementiert \cite{CAML90}. 
Auch hier wird dynamische Typ\-information dazu verwendet, dem Benutzer
Systemfunktionalit"at typsicher zur Verf"ugung zu stellen, insbesondere auch
den Compiler selbst durch eine Funktion {\sl eval\_syntax :ML\footnote{
abstrakte ML Syntax} $\rightarrow$ dyn\footnote{Typ automorpher Werte}}.
Mit Hilfe dieser Funktion kann CAML leicht als eingebettete Sprache in
Programmen verwendet werden. Ein Beispiel hierf"ur ist ihre Benutzung im Rahmen 
einer Beweiser-Konstruktionsumgebung zur interaktiven Definition von
Beweistaktiken in CAML selbst. Au"serdem bildet sie die Grundlage f"ur
die Makro"ubersetzung von CAML. Gegen"uber der in dieser Arbeit entwickelten
Schnittstelle fehlt jedoch die M"oglichkeit der "Ubersetzung gegen eine
existierende Laufzeitumgebung. Allerdings k"onnen auch hier
Auswertungsresultate in den "au"seren Kontext durch das Vorhandensein
dynamischer Typ\-information integriert werden.

