\chapter {Erweiterungen und Verbesserungen}
\label{cha_erweiterung}

Die Schilderung der Realisierung der Modulverwaltung in
Kapitel~\ref{cha_implementierung} bildet nicht nur die Voraussetzung
f"ur die Entwicklung eines neuen Modulmanagers.  Sie ist auch
Grundlage f"ur Ver"anderungen an der existierenden Implementierung.
Zu diesen Ver"anderungen z"ahlt zum einen die Beseitigung von Fehlern
und zum anderen Verbesserungen im Laufzeitverahlten.

Im Rahmen der praktischen Arbeiten sind die im folgenden
dokumentierten "Ande\-rungen am Tycoon-Compiler vorgenommen worden.  Sie
haben Eingang in die allgemeine Entwicklung gefunden.

\section {Link-Vektor}
 
Der Link-Vektor wurde bisher im Modul {\itshape tyRuntime} als Array
verwaltet.  Jeweils drei aufeinanderfolgende Eintr"age geh"orten zu
einem Modul.  Es sind die schon mehrfach erw"ahnten Eintr"age f"ur
Code, Literale und evaluierten Wert eines Moduls.  

Da der Link-Vektor zur Modulverwaltung geh"ort, erscheint eine
Verlegung der kompletten Link-Vektor-Verwaltung vom Modul {\itshape
tyRuntime} in das Modul {\itshape tlObject} logisch. Somit werden alle
Aktivit"aten des Link-Mechanismus in {\itshape tlObject} behandelt.
Auch auf eine explizit persistente Speicherung des Link-Vektors, wie
bisher geschehen, kann verzichtet werden, da dies bei einem Aufruf von
{\itshape do saveSystem} auf dem Toplevel ohnehin geschieht.

\begin{sloppypar}
Folgenderma"sen wurde vorgegangen: Im Modul {\itshape tlObject} wurde
ein neuer Typ {\itshape LinkTableIndex} angelegt, der die Eintr"age
eines Link-Vektorelements aufnimmt.  Bei den Eintr"agen handelt es
sich um {\itshape tm.OID}s, die die entsprechenden Verweise auf den
Code, die Literale und den Wert eines Moduls enthalten.  Als Datentyp
f"ur den eigentlichen Vektor wurde ein dynamisches Array gew"ahlt,
einerseits um die Elemente des Vektors "uber Indizes ansprechen zu
k"onnen.  Andererseits ist es m"oglich, die Zunahme der Gr"o"se des
Link-Vektors zur Laufzeit zu ber"ucksichtigen, ohne wie bei einem
festen Array darauf angewiesen zu sein, einen ausreichend gro"sen
Anfangswert zu sch"atzen und dabei Gefahr zu laufen, da"s dieser
irgendwann nicht mehr ausreicht.  Auch scheint es bei der
Modellierungsm"achtigkeit der Sprache \tl nicht angemessen zu sein, die
Position des gew"unschten Wertes "uber Addition von Index und
konstantem Offset f"ur die entsprechende Gr"o"se zu berechnen.
\end{sloppypar}

Bedingt durch den neuen Datentyp und die damit verbundene "Anderung
der Verwaltung der Eintr"age im Link-Vektor mu"ste dieser Teil
entsprechend ge"andert werden.  Es wurden drei neue Funktionen
eingef"uhrt, die die jeweiligen Werte aus dem Link-Vektor extrahieren:
{\itshape getBytecode}, {\itshape getLiterals} und {\itshape getValue}

Die Verwaltung der freien Eintr"age im Link-Vektor mu"s nun nicht mehr
explizit vorgenommen werden, sondern kann vom Modul {\itshape
dynArray} "ubernommen werden, das diese Funktionalit"at schon
bereitstellt.  Auch die Funktion {\itshape setI}, in der zun"achst ein
eventuell schon vorhandener Eintrag im Link-Vektor gel"oscht wird,
bevor derselbe mit {\itshape allocateLinkTableIndex} wieder
angefordert wird, kann nahezu unver"andert bleiben.  Die Zusicherung,
da"s ein nach einem Aufruf von {\itshape freeLinkTableIndex}
angeforderter Index exakt der zuvor freigegebene Index ist, kann
aufgrund der Angaben in der Schnittstelle zu {\itshape dynArray}
gegeben werden.  Damit ist sichergestellt, da"s eine neue Version
einer schon im Objektspeicher befindlichen Komponente an die
Stelle der alten kommt.

\section {"Ubersetzen von Bibliotheken}

Beim Absetzen eines {\itshape do makeLibraries lib}-Kommandos
"uberpr"ufte der Compiler bisher, ob eine der Subbibliotheken von
{\itshape lib} "ubersetzt werden mu"s.  Wie bereits im Abschnitt
\ref{do_makeLibraries} ausgef"uhrt, beschr"ankt sich die "Uberpr"ufung
auf folgendes:

\begin {itemize}
\item 
Gibt es bereits eine "ubersetzte Bibliothek?

\item
Gibt es den Quelltext zur Bibliothek?

\item
Sind der Fingerprint des Quelltextes und des ausf"uhrbaren Codes gleich?

\end {itemize}

\noindent

\begin{figure}
\hrule
\vskip \baselineskip
\begin{alltt}
{\bfseries library} Root
{\bfseries with}
  {\bfseries library}
    stdenv 
    bulkenv 
    TestLib
{\bfseries end}

{\bfseries library} TestLib
{\bfseries import}
{\bfseries with}
  {\bfseries interface}
    Test
  {\bfseries module}
    test :Test
{\bfseries end}
\end{alltt}
\hrule
\caption{Beispiel ineinandergeschachtelter Bibliotheken}
\label{abb_libroot}
\end{figure}

Als Ausgangspunkt soll das Beispiel aus Abbildung~\ref{abb_libroot}
dienen.  Die Bibliothek {\itshape Root} selbst wird nur "ubersetzt,
wenn eine der geschachtelten Bibliotheken ge"andert wurde oder eine
der obigen Bedingungen falsch ist.  Wurde nun die Bibliothek {\itshape
TestLib}, die sich in der Bibliothek {\itshape Root} befindet,
zwischenzeitlich z.B. durch ein

\begin{quote}
{\ttfamily do ''TestLib/TestLib.tl'';}
\end{quote}

\noindent
ebenfalls "ubersetzt ohne sie jedoch zur Wurzelbibliothek zu machen,
so konnte dies bei einem erneuten

\begin{quote}
{\ttfamily do makeLibraries Root;}
\end{quote}

\noindent
nicht erkannt werden.  Wurden z.~B.\ in {\itshape TestLib} neue
Schnittstellen und Moduln einge\-f"uhrt, so k"onnen diese jetzt nicht
importiert werden.

Zur L"osung dieses Problems sollte eine zus"atzliche "Uberpr"ufung in
der Funktion {\itshape makeLibrary} im Modul {\itshape tyDepend}
erfolgen, ob {\itshape TestLib} zeitlich nach {\itshape Root}
"ubersetzt wurde, wenn alle oben genannten Bedingungen wahr sind.
Dies kann durch entsprechenden Abgleich der Object-IDs beider
Bibliotheken erfolgen, die einen Zeitstempel enthalten.  Die
Objekt-IDs sind in diesem Zusammenhang nicht mit den OIDs zu
verwechseln, die Referenzen innerhalb des Objektspeichers darstellen.
Ein "Ubersetzen von {\itshape TestLib} ist nicht erforderlich; es mu"s
lediglich eine Propagierung dieser Tatsache erfolgen.  Daf"ur bietet
sich {\itshape makeState.changes} an, welches nur inkrementiert werden
mu"s, um eine Neu"uber\-setzung der einschlie"senden Bibliothek zu
veranlassen.  Da die Objekt-ID der einschlie"senden Bibliothek in
{\itshape makeLibrary} nicht direkt verf"ugbar ist, mu"s sie explizit
der Funktion "ubergeben werden.  Dies erfordert eine entsprechende
Anpassung aller Aufrufe von {\itshape makeLibrary} und von {\itshape
compileLibrary}, da hier {\itshape makeLibrary} rekursiv aufgerufen
wird.

\section{"Ubersetzen von versteckten Komponenten}

In Abschnitt~\ref{sec_hidden} ist beschrieben, wie mit der {\itshape
hide}-Klausel einzelne Bezeichner einer Bib\-liothek nach au"sen
unerreichbar gemacht werden k"onnen.  Die Akzeptanz dieser
M"og\-lichkeit ist im Bereich der Anwender und Programmierer des
Tycoon-Systems "au"serst gering\footnote{In keiner Bibliothek, die zum
Tycoon-Compiler geh"ort oder die sonst im Verzeichnis {\itshape
bootlib} zu finden ist, wird die {\itshape hide}-Klausel benutzt.}.
Nur so ist es zu erkl"aren, da"s erst jetzt bemerkt wurde, da"s mit
versteckten Komponenten praktisch nicht gearbeitet werden kann.  Dies
kommt daher, da"s der Compiler den Versuch, ein verstecktes Modul oder
eine versteckte Schnittstelle mit {\itshape do makeComponent}\/ bzw.\
{\itshape do make}\/ zu "ubersetzen, mit einer Fehlermeldung abbricht.
Nur mit Hilfe eines Kniffs\footnote{Eine Komponente, die versteckt
werden soll, mu"s zun"achst als nicht versteckt "ubersetzt werden und
danach in der Bibliothek unter {\itshape hide}\/ aufgef"uhrt werden.
Dies ist aber zweifelsohne keine vertretbare Methode, versteckte
Bezeichner zu benutzen.} kann dies vermieden werden.  An dieser Stelle
soll nicht "uber Sinn und Zweck des {\itshape hide}-Konstruktes
diskutiert werden, vielmehr sollen die Ursache des Fehlers analysiert
und die zu seiner Beseitigung vorgenommenen Ma"snahmen beschrieben
werden.

In einer durch das Modul {\itshape tlLibrary} gepflegten Datenstruktur
wird der Aufbau der Bibliotheksstruktur repr"asentiert.  Dabei werden
die F"alle {\itshape moduleCase}, {\itshape interfaceCase}, {\itshape
libraryCase}\/ und {\itshape hiddenCase} unterschieden, also alle
Komponenten, die in einer Bibliothek vorkommen k"onnen.

Der oben beschriebene Fehler tritt auf, wenn f"ur eine versteckte
Komponente zum Zweck des "Ubersetzens die Namen der Quelltext-Datei
und der Objekt-Datei bestimmt werden sollen.  Dies erledigt die
Funktion {\itshape inspect}\/ im Modul {\itshape tyDepend}.
Dort wird der Fall einer versteckten Komponente jedoch nicht
ber"ucksichtigt.  Neben dieser weiteren Fallunterscheidung mu"s f"ur
den Fall {\itshape hiddenCase}\/ jedoch weiterhin gepr"uft werden, was
f"ur eine Komponente versteckt ist.  Die {\itshape hide}-Klausel kann
sowohl bei Moduln als auch bei Schnittstellen Anwendung finden.  Die
eigentliche Komponente ist im Falle der {\itshape hidden\-Case}-Variante
im Tupelfeld {\itshape component} abgelegt.  Diese mu"s dann zur
Ermittlung der Dateinamen herangezogen werden.

Um unn"otige Codeduplizierung zu vermeiden, wurde die eigentliche
Bestimmung der Dateinamen, jeweils getrennt nach Modul und
Schnittstelle, in die Funktionen {\itshape moduleFileNames}\/ und
{\itshape interfaceFileNames}\/ ausgelagert.

\section{Verzeichnis aller geladenen Komponenten}

Im Abschnitt~\ref{tlObject} wurde die Funktion der Datenstruktur
{\itshape Map} bereits erl"autert.  Der Eintrag {\itshape dictionary}
verzeichnet alle im Objektspeicher befindlichen Komponenten.  Er wird
benutzt, um das Vorhandensein einer Komponente zu testen oder um diese
zur\"uck\-zugewinnen.

Eine Beobachtung der Zugriffe auf {\itshape map.dictionary} ergab,
da"s bei zun"achst leerem Objektspeicher z.~B.\ ein 

\begin{quote}
{\ttfamily import print;}
\end{quote}

\noindent
zu ca.\ 550 Zugriffen f"uhrt. Dabei werden 26 Komponenten geladen und
sieben definiert.  Ein

\begin{quote}
{\ttfamily import tycoon;}
\end{quote}

\noindent
zieht sogar "uber 5000 Zugriffe nach sich.  Da bei gro"sen
Applikationen oder hochabstrakten Bibliotheken die Anzahl der Moduln,
die importiert werden, stetig steigt, wird die pro Zugriff ben"otigte
Zeit immer gr"o"ser.

Weil auf {\itshape map.dictionary} nur Zugriffe stattfinden, die ein
einziges Element zur"uckge\-winnen oder auf das Vorhandensein eines
Elementes "uberpr"ufen, scheint die Implementation als Dictionary
nicht ad"aquat.  Die Implementierung von dem Modul {\itshape
Dictionary} st"utzt sich auf die Datenstruktur einer Liste, d.~h.\ zum
Durchsuchen nach einem Element mu"s durchschnittlich die H"alfte aller
Elemente verglichen werden.  Im Laufe der Zeit steigt die Anzahl der
importierten Moduln stetig, und die Zeit, die pro Suche ben"otigt
wird, nimmt somit linear zu.  Ein Importieren eines Moduls ist deshalb
bei schon gef"ull\-tem Objektspeicher zugriffsintensiver als bei
leerem.

Als L"osung bietet sich an, das Dictionary durch eine Hashtabelle zu
ersetzen.  Dies hat den Vorteil, da"s im Idealfall, wenn das gesuchte
Element gerade an der berechneten Stelle ist, die pro Suche ben"otigte
Zeit konstant ist.  Leider ist dies nicht immer der Fall, da der
berechnete Eintrag bereits gef"ullt sein kann.  Bei einer Kollision
kann dann der n"achste freie Eintrag z.~B.\ durch sequentielle Suche
ermittelt werden ({\itshape linear probing}).  Auch wenn dieser Ansatz
Schw"achen gegen"uber {\itshape double hashing} hat, so ist er doch
einfach zu implementieren.  Beim {\itshape double hashing} wird bei
einer Kollision nicht ab der gefundenen Position ein freier Eintrag
gesucht, sondern durch eine weitere Hashfunktion ein Offset berechnet.
Dadurch kann das Problem des {\itshape clustering} effektiver
verhindert werden.

Nachteilig an einer Hashtabelle ist ganz allgemein der im Vergleich
zur Liste h"ohere Platzbedarf.  Dies liegt zum einen daran, da"s mit
einem Feld fester Gr"o"se gearbeitet wird, zum anderen nimmt die
Trefferquote bei einer mehr als 90\% gef"ullten Hashtabelle stark ab
bzw.\ schlie"st sich eine weitere sequentielle Suche "uber mehrere
Elemente an.  Um optimale Performanz zu erzielen, sollten also immer
gen"ugend freie Elemente vorgehalten werden \cite{algorithm}.

Bei der vorliegenden Implementierung der Hashtabelle wurde {\itshape
linear probing} verwendet.  Die Tabelle wird dabei solange gef"ullt,
bis sie vollst"andig gef"ullt ist.  Dies stellt zwar aus den genannten
Gr"unden nicht die optimale L"osung dar, bringt aber gegen"uber der
Implementierung als Liste deutlich sp"urbare Vorteile.

\begin{sloppypar}
Das Ersetzen der einzelnen Aufrufe geschieht bis auf eine Ausnahme
schematisch.  Beim Anlegen der Hashtabelle m"ussen zus"atzlich eine
Vergleichsfunktion f"ur die Schl"us\-sel, in diesem Fall vom Typ
{\itshape String}, und eine entsprechende Hashfunktion, die den
Schl"us\-sel\-wert auf einen Index abbildet, "ubergeben werden.  Hier
wurde auf Funktionen aus dem Modul {\itshape string} zur"uckgegriffen,
die speziell f"ur diesen Zweck bereitgestellt werden.
\end{sloppypar}

Die praktische Durchf"uhrung hat dann gezeigt, da"s ein {\ttfamily
dictionary.set} in ein

\begin{quote}
\begin{alltt}
\textbf{try}
  hashTable.insert (...)
\textbf{when} hashTable.error \textbf{then}
  hashTable.delete (...)
  hashTable.insert (...)
\textbf{end}
\end{alltt}
\end{quote}

\noindent
umgewandelt werden mu"s, um unerw"unschte Fehler beim Ersetzen eines
bereits vorhandenen Elementes zu verhindern.  Dies mu"s anders als bei
Benutzung des Moduls {\itshape dictionary} explizit abgefangen werden.

\section {Synchronisieren des Objektspeichers}
\label{sec_sync}

Bisher ist es nicht m"oglich, eine ausf"uhrbare Datei (*.x) , welche
aktueller ist als der im Objektspeicher befindliche Code bzw.\ bei
einer Schnittstelle die entsprechend "ubersetzte Typinformation, in
den Objektspeicher ohne erneutes {\itshape do make} oder {\itshape do
makeComponent} zu laden.  Dies kann aber n"otig sein, wenn nach einem
{\itshape do make} bzw. {\itshape do makeComponent} und vor {\itshape
do saveSystem} ein Systemabsturz auftritt.  Die Hauptursache daf"ur,
da"s dies bisher nicht funktioniert, liegt darin, da"s bei einem Aufruf
von {\itshape linkImports} (sowohl von {\itshape top\-LevelImport} als
auch von {\itshape link}) aus Performanzgr"unden im Modul {\itshape
tlObject} nur gepr"uft wird, ob sich die entsprechende Komponente im
Objektspeicher befindet, nicht jedoch, ob die Version auf dem
Sekund"arspeicher aktueller ist.  Damit wurde auch ein durchaus
vern"unftiger Einsatz verfolgt.  Zugriffe auf externen Speicher sind
im Vergleich zu Objektspeicherzugriffen, die meist innerhalb des
Hauptspeichers erfolgen k"onnen, erheblich teurer.

Ben"otigt wird also ein Kommando, welches explizit die entsprechende
Komponente auf dem Sekund"arspeicher pr"uft und bei Bedarf liest.
Diese Aufgabe soll das neu eingebaute {\itshape do syncComponent}
erf"ullen.

Es hat "ahnliche syntaktische Eigenschaften wie {\itshape do
makeComponent}.  Es kann mit mehreren Argumenten aufgerufen werden,
die der Reihe nach abgearbeitet werden.  Bei einem Modul oder einer
Schnittstelle werden alle transitiv erreichbaren Komponenten
synchronisiert.  Handelt es sich bei dem Argument um einen
Bibliotheksbezeichner, so werden in der Bibliothek enthaltene
Komponenten aktualisiert.

Zur Realisierung werden zwei neue Funktionen eingef"ugt.  Die erste
Funktion ({\itshape synchronize}) wird vom Modul {\itshape
tyDoCommand} aufgerufen und steuert den gesamten Ablauf des
Synchronisierens.  Es wird dann durch die zweite neue Funktion
({\itshape loadAll}) explizit jede von der betreffenden Komponente
abh"angige Komponente auf Konsistenz mit der im Objektspeicher
befindlichen Version "uberpr"uft und bei Bedarf geladen.  Ein
nachfolgender Aufruf von {\itshape linkImports}\/ f"uhrt dazu, da"s
alle entsprechend neuen Komponenten neu gebunden werden.  

Durch eine weitere "Anderung in {\itshape linkImport}, die verhindert,
da"s in {\itshape addImports} die falschen Schnittstellen gefunden
werden, werden sogar alle abh"angigen Schnittstellen gelinkt, bzw.\ in
{\itshape info.changes}\/ protokolliert und im anschlie"senden
{\itshape addImports}\/ neu definiert.  Dadurch entsteht der Nachteil,
da"s auch bei einem normalen Import Meldungen ausgegeben werden, die
schon gebundene Komponenten als neu gebunden ausweisen.  Das hat zwar
keinen Einflu"s auf die Funktionsf"ahigkeit, spiegelt den
tats"achlichen Vorgang aber nicht korrekt wider.  Abhilfe w"urde eine
"Anderung der Datenstruktur {\itshape tlObject.T}\/ schaffen, wo durch
ein weiteres Flag angezeigt werden k"onnte, ob eine Komponente neu
gebunden werden mu"s.  Da aber das Sekund"arspeicher-Layout einer
"ubersetzten Datei von dieser Datenstruktur abh"angt, m"u"ste eine
Konvertierung all dieser Dateien vorgenommen werden.  

Eine weitere M"oglichkeit, die "uberfl"ussigen Meldungen zu vermeiden
besteht darin, das Sekund"arspeicherlayout unabh"angig von der
Datenstruktur {\itshape tlObject.T}\/ zu gestalten.  Da das
einzuf"uhrende Flag erst nach dem Laden in den Objektspeicher eine
Bedeutung erlangt, m"u"ste es nicht explizit gespeichert werden.  Auch
andere Elemente der Datenstruktur {\itshape tlObject.T}\/ sollten in
diesem Zusammenhang darauf "uberpr"uft werden, ob sie auf
Sekund"arspeicher abgelegt werden m"ussen.  Die praktische
Durchf"uhrung m"u"ste in den Funktionen {\itshape loadFile}\/ und
{\itshape saveFile}\/ im Modul {\itshape tlObject} eine Projektion der
Datenstruktur {\itshape tlObject.T}\/ auf die Struktur des
Sekund"arspeicherlayouts bzw.\ umgekehrt durchf"uhren.


