\chapter{Implementierung}
\label{cha_implementierung}

In diesem Teil werden technische Details der Implementierung der in Kapitel
\ref{cha_strukturierung_tlmin} vorgestellten Elemente des {\tlmin} System
dargelegt.  Zum Verst"andnis werden vom Leser detaillierte Kenntnisse der
{\tlmin} Architektur und Systemimplementierung vorausgesetzt.

\section{Sichtbarkeitsbereiche}
Die Implementierung der Sichtbarkeitsbereiche, wie in Abschnitt
\ref{sec_sichtbarkeitsbereiche} beschrieben, umfa"st im einzelnen folgendes:

\begin{enumerate}

\item "Anderung der Grammatik, so da"s die neuen Konstrukte erkannt werden.
Dazu wurden gem"a"s der Produktion einer Sequenz weitere Produktionen
eingef"uhrt, die optional Namen ({\itshape with \ldots do}) "ubernehmen.  Es
ergeben sich somit vier neue Konstruktoren, die die Grammatik erweitern:

\begin{itemize}
\item \textit{mkValueScope}, um einen abgeschlossenen
  Sichtbarkeitsbereich ohne importierte Bezeichner zu generieren.

\item \textit{mkValueScopeWith}, um in den Sichtbarkeitsbereich
  Bezeichner aus dem "ubergeord\-neten Block zu importieren.

\item \textit{mkTypeScope} schlie"st den Sichtbarkeitsbereich einer
  Typdefinition ab.

\item \textit{mkTypeScopeWith} importiert die als Argument
  "ubergebenen Bezeichner in den leeren Sichtbarkeitsbereich der
  Typdefinition.
\end{itemize}

\noindent
Eine "Anderung des Parsers ist nicht notwendig.  Er wird mit der neuen
Grammatik parametrisiert und ruft die neuen Konstruktoren automatisch auf.

\item In die vom Parser erzeugte Darstellung, dem vorl"aufigen
  Syntaxbaum (PreAST), der als Eingabe zur Typ"uberpr"ufung
  herangezogen wird, wurden weitere Knotentypen eingef"ugt.  Diese
  wurden wieder analog einer Sequenz ({\itshape begin \ldots end})
  gestaltet, mit dem Unterschied, da"s die optional zu importierenden
  Namen enthalten sind.  An dieser Stelle werden die vier m"oglichen
  F"alle (s. obige Aufz"ahlung) zu zwei verbleibenden M"oglichkeiten
  normalisiert, indem die zun"achst optionale Liste von importierten
  Bezeichnern obligatorisch wird.  Im Falle, da"s keine Bezeichner
  importiert werden, ist die Importliste leer.

\item Der Typ"uberpr"ufer wurde modifiziert.  Er enth"alt Code zur
  Behandlung des neuen Knotens des vorl"aufigen Syntaxbaumes.  Dort
  wird daf"ur gesorgt, da"s die "Uberpr"ufung des in das
  Sichtbarkeitskonstrukt eingeschlossenen Bereichs gegen eine neue
  Umgebung erfolgt.  Dies wird erreicht, indem die Typ"uberpr"ufung
  des Sichtbarkeitsbereiches an einer ver"anderten Kopie der aktuellen
  Typumgebung stattfindet.  Diese Typumgebung enth"alt alle
  sichtbar gemachten (importierten) Bezeichner an deren bisherigen
  Positionen und an den "ubrigen Platzhalterwerten.  Diese
  Vorgehensweise f"uhrt dazu, da"s, obwohl nur wenige Bezeichner
  sichtbar sind, dennoch die neue Typumgebung gegen"uber der alten
  unver"andert viel Speicherplatz verbraucht.  Diese L"osung hat
  allerdings den Vorteil, keine weiteren "Anderungen im
  Typ"uberpr"ufer nach sich zu ziehen, wie z.B.\ eine Umrechnung von
  Indizes, die in die Typumgebung zeigen, und die invalidiert w"aren,
  wenn die Position der Bezeichner durch Schrumpfung der Typumgebung
  ver"andert wird.

  Weiterhin m"ussen die als Argumente des Sichtbarkeitskonstruktes
  angegebenen Namen auf ihr Vorhandensein in der umschlie"senden
  Umgebung gepr"uft und zur neuen Typumgebung hinzugef"ugt werden.
\end{enumerate}

F"ur das Sichtbarkeitskonstrukt ist keine Laufzeitunterst"utzung
notwendig.  Das ist begr"undet in der Tatsache, da"s es sich hierbei
um eine rein statische Abpr"ufung von Sichtbarkeit bzw. Vorhandensein
von Bezeichnern handelt, die zur "Ubersetzungszeit vollst"andig
behandelt werden kann.  Der f"ur die innerhalb des
Sichtbarkeitskonstruktes liegenden Anweisungen erzeugte Code kann
gegen die dort g"ultige Umgebung ausgef"uhrt werden.  Es mu"s keine
neue Laufzeitumgebung geschaffen werden, da sich die referenzierten
Bezeichner durch die besondere Behandlung der Typumgebung innerhalb
des Sichtbarkeitskonstruktes exakt an der erwarteten Position
befinden.  Auf nicht sichtbare Bezeichner, die sich zur
Ausf"uhrungszeit auch in der Laufzeitumgebung des betreffenden Codes
befinden, kann nicht zugegriffen werden.  Dies ist gerade durch die
Typ"uberpr"ufung statisch erzwungen worden.

\section{Umgebungen}
Das in {\tlmin} verwendete Modell der Umgebungen ist ausf"uhrlich in Abschnitt
\ref{sec_umgebung} beschrieben.  An dieser Stelle wird auf die konkreten
Aspekte der Implementierung eingegangen.

\subsection{Aufbau}
Umgebungen werden im "Ubersetzer von der Phase der Typ"uberpr"ufung
bis zur Ausf"uhrung des Codes der virtuellen Maschine in der Tycoon
Maschine benutzt.  Sie stellen erg"anzend zu den verschiedenen
Zwischen- und Coderepr"asentationen die Verbindung zwischen dem
Compiler als statische Komponente einerseits und den aktuellen
dynamischen Daten (Programme, Ausdr"ucke) andererseits her.

Eine Umgebung setzt sich aus drei Teilkomponenten zusammen.
Jede dieser Teilkomponente ist eine Massendatenstruktur, die Verweise auf die
eigentliche Information enth"alt:

\begin{description}

\item[Typumgebung:] Sie umfa"st die Signaturen aller sichtbaren Bezeichner wie
Funktionen, Variablen etc.  Unter Signaturen wird in diesem Zusammenhang die
Repr"asentation dieser Signaturen im Syntaxbaum verstanden.  Konkret sind in
der Typumgebung somit Verweise auf Teilsyntaxb"aume enthalten.

\item[Wertumgebung:] Die Codegenerierung "ubersetzt die Repr"asentation des
Syntaxbaums in die Darstellung als TML-Baum. Die Verweise auf die entstandenen
Knoten werden in der Wert\-umgebung abgelegt.

\item[Laufzeitumgebung:] Nach Erzeugung und Ausf"uhrung des TVM-Codes werden
die evaluierten Werte in die Laufzeitumgebung eingetragen und stehen damit
nachfolgenden Ausf"uh\-rungs\-schritten zur Verf"ugung.

\end{description}
Die Operationen zum Erzeugen von Umgebungen und zum Auffinden von Komponenten
lassen sich leicht implementieren, da sie gr"o"stenteils auf bereits
vorhandenem Code aufbauen k"onnen.  Sie werden hier nicht weiter behandelt.
Die Aufmerksamkeit soll stattdessen auf das Kopieren und Verschieben von
Komponenten zwischen Umgebungen gelenkt werden.

%\afterpage{\clearpage
\begin{figure}[H]
\centering\mbox{\epsfig{file=../Zeichnung/korrespondenz.eps}}
\caption{Beziehungen der drei Teilkomponenten einer Umgebung.}
\label{abb_korrespondenz}
\end{figure}
%}

Die bisherige Implementierung der drei Einzelkomponenten der Umgebungen sind
dergestalt realisiert, da"s sie von einer strengen Abfolge des
"Ubersetzungsvorganges ausgehen.  Konkret hei"st das z.B., da"s die Eintr"age
der Wertumgebung mit den Eintr"agen der Typumgebung korrespondieren, weil die
durch den Syntaxbaum implizit vorgegebene Reihenfolge durch den Algorithmus der
Codegenerierung erhalten bleibt (s. Abbildung \ref{abb_korrespondenz}).
"Uberlappende Aufrufe der Compilerfunktionen w"urden zu inkonsistenten
Umgebungen f"uhren.  Beim Anlegen neuer Eintr"age in einer
Umgebungskomponente mu"s also nicht nach einem freien Platz, sondern nach dem
korrespondierenden Eintrag gesucht werden.

Ein weiteres Problem bei der Implementierung von Umgebungen ergab sich aus der
Anforderung, Elemente zwischen Umgebungen frei kopieren und verschieben zu
k"onnen.  Die in der Umgebung abgelegten Strukturen beziehen sich teilweise auf
Eintr"age in derselben Umgebung.  Diese Verweise sind in der Implementierung
des {\tlmin} Systems im Gegensatz zur Implementierung in einem {\tl} System
nicht "uber de Bruijn Indizes gel"ost, sondern "uber direkte Verweise
\cite{bremer}.  Dies erleichtert es grunds"atzlich, ein Kopieren zwischen
Umgebungen zu realisieren, da die enthaltenen Strukturen sich nicht auf
die Umgebung beziehen, sondern direkt auf die in ihnen enthaltenen Strukturen.
Es gibt jedoch Ausnahmen in der Implementierung des {\tlmin} Systems, die
weiterhin "uber Indizes modelliert sind.  Diese betreffen ausschlie"slich den
Typ"uberpr"ufer bzw.\ die von ihm aufgebaute Struktur des Syntaxbaums.  Dies
sind im einzelnen:

\begin{itemize}
\item Bei der Definition eines Tupelfeldes bezeichnet ein Index
die Position des Feldes im entsprechenden Tupeltyp.  Da bei Rekordfeldern die
Feldidentifikation per Namen geschieht, tritt in diesem Fall kein Index auf.

Die Verwendung dieses Indexes bezieht sich nicht auf die Umgebung direkt,
sondern auf die Position innerhalb einer Struktur, die in der Umgebung abgelegt
ist.  F"ur das oben geschilderte Problem spielt dieser Index daher keine
Rolle.

\item Die Eintr"age der Typumgebung verweisen auf Signaturen, die wiederum auf
andere Komponenten wie Werte, Bindungen oder Typen verweisen k"onnen.  Jede
Signatur besitzt eine Komponente, die die Position in der Typumgebung angibt.
Da es sich hier um einen Index handelt, der sich auf eine Umgebung
bezieht, mu"s er f"ur oben genanntes Problem ber"ucksichtigt werden.  Zwar wird
in der Implementierung des {\tlmin} Systems dieser Index nur zu
Informationszwecken verwendet, diese Information sollte jedoch weiterhin zur
Verf"ugung stehen.  Dabei ist zu beachten, da"s diese Verweisinformation sich
nun auch auf andere Umgebungen beziehen kann.  Ein Index reicht zur
Identifikation deshalb nicht aus.

\item Auch bei der Repr"asentation von Werten im Syntaxbaum treten Indizes auf.
Neben der Benutzung bei Feldindizierungen und zum Auffinden einer Variante
eines varianten Tupeltyps ist vor allem die Verwendung von Bezeichnern
interessant, die sich auf zuvor definierte Variablen beziehen.  Hier werden
Indizes eingesetzt, um auf die Position der referenzierten Typrepr"asentation
in der Umgebung zu verweisen.

Die Verwendung dieses Indexes ist im Sinne des oben beschriebenen Problems
kritisch, da ein derartiger Index in einer anderen Umgebung keine G"ultigkeit
mehr besitzt. 

\end{itemize}

\subsubsection{L"osungsans"atze}

Grunds"atzlich besteht das Problem, da"s Verweise, in diesem Fall als Index in
einer Umgebung realisiert, nur lokale G"ultigkeit besitzen.  Der
G"ultigkeitsbereich dieser Verweise soll im Rahmen der Implementierung der
Umgebungen umgebungs"ubergreifend gestaltet werden.  Dazu bieten sich mehrere
Ans"atze an:

\begin{enumerate}

\item Der Index k"onnte um eine zus"atzliche Komponente erweitert werden, die
angibt, in welcher Umgebung die Verweisinformation g"ultig ist.  Bei dieser
L"osung kann das Problem der h"angenden Referenzen ({\itshape dangling
reference}) auftreten, wenn Eintr"age aus einer Umgebung gel"oscht werden und
nicht daf"ur gesorgt wird, da"s alle Verweise auf das zu l"oschende Element
eliminiert werden.  Hier tritt dann eventuell ein weiteres Problem auf, da
gel"oschte Komponenten nicht mit dem neuen Verweisschema referenziert werden
k"onnen, wenn sie sich in keiner Umgebung mehr befinden.  Es mu"s zur
L"osung eine weitere Umgebung gehalten werden, die bereits gel"oschte Eintr"age
aufnimmt.

\item Die Datenstruktur des Syntaxbaumes k"onnte in der Repr"asentation f"ur
Werte so ge"andert werden, da"s direkt auf die referenzierte Typinformation
verwiesen wird und nicht auf einen Eintrag in der Umgebung.  Bei diesem
L"osungsansatz ergibt sich die Schwierigkeit, da"s zum Zeitpunkt der
Erstellung des Indexes die referenzierte Information noch nicht vorliegt.  Es
mu"s mit einer variablen Bindung gearbeitet werden, die aktualisiert wird,
sobald die referenzierte Signatur vorliegt.

\item Da der Index in der Datenstruktur f"ur Werte bei der Codegenerierung
ausschlie"slich daf"ur verwendet wird, den entsprechenden Eintrag in der
Wertumgebung zu lokalisieren, bietet sich eine weitere L"osungsm"oglichkeit
an.  Das Auffinden kann auf Basis des Namens des entsprechenden Bezeichners
geschehen.  In diesem Fall dient die Namensinformation als Verweis.  Zu
beachten ist hierbei, da"s Bezeichner sowohl in unterschiedlichen Bl"ocken als
auch im gleichen Block mehrfach verwendet werden k"onnen.  Beim Auffinden ist
dies zu ber"ucksichtigen.

\item Die Analyse der auftretenden Indizes hat ergeben, da"s diese nur in der
Repr"asentation von Werten auftreten und nur auf die Signaturen der
entsprechenden Wertdefinition verweisen\footnote{Indizes treten wie
beschrieben auch an anderer Stelle auf, haben dort aber nur
Informationscharakter.  Aus diesem Grund werden sie hier nicht in die
Betrachtung einbezogen.  Es wird davon ausgegangen, da"s die mit Hilfe dieser
Indizes erstellten Fehlermeldungen auch auf andere Weise erzeugt werden
k"onnen}.  Es k"onnen nun in einer globalen Massendatenstruktur Verweise auf
alle angelegten Signaturen f"ur Werte gespeichert werden.  Der Verweis auf
diese Wertsignaturen erfolgt "uber einen entsprechenden Schl"usselwert des
Eintrages oder "uber einen Index bei der Realisierung mit Hilfe einer
indizierten Struktur.

\end{enumerate}

\subsection{Realisierung}
Wie in Punkt vier des letzten Abschnittes dargelegt, treten Verweise
auf Werte in der Wertkomponente einer Umgebung nur in Form von
Verweisen auf bestimmte Objekte auf.  Eine systemweite Verwaltung
aller Eintr"age in Wertkomponenten generiert bei jeder Erzeugung eines
neuen Objektes, auf das verwiesen werden kann, einen eindeutigen Index
f"ur dieses Objekt.  Dieser Index wird zus"atzlich im Syntaxbaum
gespeichert.

In der Zwischencode-Generierung, in der der Syntaxbaum abgewandert
wird, wird anhand des zuvor dort gespeicherten Indexes der Werteintrag
in der systemweiten Verwaltung der Werteintr"age abgelegt.  Auf diese
Weise haben alle anderen "Ubersetzungsvorg"ange Zugriff auf die
Werteintr"age anderer Umgebungen.

