% File:    pquest.tex
% Author:  Claudia Niederee, Sven Muessig
% Date:    05-MAR-1992
% Subject: P-Quest Benutzerhandbuch (Text)
%
\section{Einf"uhrung}

\Q\footnote{\Q\ steht f"ur {\em Quantifiers and Subtypes}.} ist eine
strikt typisierte, polymorphe, funktionale Programmiersprache, in der
jedoch auch imperative Eigenschaften zu finden sind.
Die Typ"uberpr"ufung findet statisch zur "Ubersetzungszeit statt.

Die Sprache \Q\ wurde von Luca Cardelli bei DEC SRC in Palo Alto, USA \cite{Card89} entwickelt. Im Rahmen einer Diplomarbeit an der Universit"at Hamburg \cite{Mue91} wurde die Sprache durch Hinzuf"ugen eines Persistenzkonzeptes zu \PQ\ erweitert. 
In diesem Report wird in die relevanten Konzepte der Sprache \PQ\ eingef"uhrt und danach das Persistenzkonzept des \PQ\/-Systems erl"autert. 
Eine vollst"andige Einf"uhrung in die Sprache \Q\ findet sich in \cite{Card90}.

\bslop
Das \PQ\/-System besteht aus mehreren Komponenten. Die Komponenten sind
eine interaktive Programmierumgebung, eine Reihe von Bibliotheken (z.Zt. Standard-,
Bulk Data Type- und Grafik-Bibliothek), sowie eine in \mbox{Modula-3} \cite{Card88} realisierte
Abstrakte Maschine. Die Abstrakte Maschine interpretiert den vom
\PQ\/-Compiler erzeugten Bytecode.
\eslop

Mit \PQ\ werden viele neuere Programmierkonzepte realisiert, die in
den nachfolgenden Abschnitten anhand von Beispielen vorgestellt werden
sollen.

Die Konzepte sind im einzelnen:

\begin{itemize}
  \item Erweitertes Typkonzept (Werte, Typen, Kinds)
  \item Funktionen h"oherer Ordnung
  \item Subtypisierung
  \item Parametrischer und Subtyppolymorphismus
  \item Abstrakte Datentypen
  \item Module und Schnittstellen
  \item Funktionen und Module als Objekte {\em erster Klasse}
  \item Ausnahmebehandlung
\end{itemize}

\section{\PQ\/-Typkonzepte}

Traditionelle Progammiersprachen unterscheiden nur zwischen {\em Werten}
und {\em Typen}. Werte stellen die Ebene 0 und Typen die Ebene 1 dar.
Wie in der nachfolgenden Abbildung zu sehen ist, gibt es in
\PQ\ noch eine weitere Ebene (Ebene 2), die Ebene der {\em Kinds}. Kinds klassifizieren Typen in der gleichen Weise, wie Typen Werte. Die Ebene der Kinds wird ben"otigt, um die in \PQ\ ungew"ohnlich reiche Typebene zu strukturieren. Die drei Ebenen werden in den nachfolgenden Abschnitten anhand von Beispielen beschrieben.

\input{typkonze}

Die obige Abbildung zeigt nicht nur die im Typkonzept von 
\PQ\ vorhandenen drei Ebenen, sondern sie verdeutlicht auch die in
Abschnitt \ref{kinds} aufgef"uhrte Typisierung von Operatoren in der Kindebene und  die in Abschnitt \ref{subtypisierung} beschriebene Subtypisierung.

Bevor auf die drei Ebenen eingegangen wird, sei hier die verwendete Konvention f"ur die Schreibweise von Schl"usselworten und die Schreibweise von Bezeichnern in den Beispielen erl"autert. Schl"ussselworte im Zusammenhang mit Werten werden klein geschrieben, Schl"usselworte im Zusammenhang mit Typen beginnen mit einem Gro"sbuchstaben und Schl"usselworte im Zusammenhang mit Kinds werden ganz in Versalien geschrieben. In dieser Arbeit wird zur besseren Unterscheidung zwischen den Ebenen die Konvention von Cardelli "ubernommen, diese Regel auch auf die Schreibweise von Bezeichnern f"ur Objekte in der jeweiligen Ebene anzuwenden.  


\subsection{Die Ebene der Werte}

Zur Ebene der Werte geh"oren Auspr"agungen der in \PQ\ angebotenen Basistypen, strukturierte Werte, wie Tupel und Optionen, aber auch Funktionen und
polymorphe Funktionen.
\begin{figure}
\begin{xple}
     \k{let} x = 3
     \k{let} sven = \k{tuple let} name = ''sven'' \k{let} age = 25 \k{end}
     \k{let} name = \k{fun}(p :Person) :\k{String} p.name
     \k{let} identity = \k{fun}(A ::\k{TYPE} a :A) :A a
\end{xple}
\end{figure}

Ein Wert wird mit dem Schl"usselwort {\sl let} an eine Variable 
gebunden. Im ersten Beispiel wird eine Auspr"agung des Basistyps Integer an die Variable {\sl x} gebunden. Im zweiten Beispiel wird ein strukturierter Wert, und zwar ein 
{\sl tuple}, an die Variable {\sl sven} gebunden. In den folgenden Beispielen
werden eine Funktion und eine polymorphe Funktion definiert. Wie am vierten Beispiel zu sehen ist, k"onnen bereits auf dieser Ebene Typen auftreten, und zwar z.B. als Komponenten von Tupeln und als Parameter von polymorphen Funktionen.
  
\subsection{Die Ebene der Typen}

Die Typebene enth"alt Typen und Typoperatoren. Zu den Typen geh"oren
neben den Basistypen wie z.B. {\sl Int}, {\sl Real} und 
{\sl Ok}\footnote{{\sl Ok} ist ein Typ, der nur die Konstante {\sl ok} beinhaltet. 
Entspricht {\sl void} in C.}, strukturierte Typen, wie z.B. 
Tupeltypen und Funktionstypen. Typoperatoren (Typfunktionen) sind
Funktionen, die es erm"oglichen, Typen auf Typen abzubilden.
Objekte der Typebene k"onnen durch das Vorstellen des Schl"usselworts 
{\sl Let} an Namen gebunden werden. Es folgen einige Beispiele f"ur die Definition und Benennung von Typen.  
\begin{xple}
     \k{Let} Number = \k{Int}
     \k{Let} Person = \k{Tuple} name :\k{String} age :\k{Int} \k{end}
     \k{Let} Name = \k{All}(:Person) \k{String}
     \k{Let} Identity = \k{Fun}(A ::\k{TYPE}) ::\k{TYPE} A
\end{xple}
Die Beispiele korrespondieren mit den Beispielen auf der Ebene der
Werte. Das erste Beispiel f"uhrt einen neuen Namen f"ur den Typ der ganzen Zahlen ein. {\sl Person} ist der Typ der Variablen {\sl sven} und {\sl Name} der Typ der Funktion {\sl name}. Das vierte Beispiel definiert einen Typoperator. Es handelt sich dabei um eine Identit"atsfunktion auf der Typebene.

\subsection{Die Ebene der Kinds} \label{kinds}

Kinds sind die Typen von Typen. Sie dienen zur Strukturierung der 
Menge der Typen. Der allgemeinste Kind ist {\sl TYPE}; das ist der
Kind, der alle Typen enth"alt.  Weitere Kinds k"onnen vom Benutzer 
definiert werden. Die Definition von Kinds geschieht durch 
Voranstellen des Schl"usselwortes {\sl DEF}.                 

\begin{xple}
     \k{DEF} TYPOP = \k{ALL}(A ::\k{TYPE}) \k{TYPE}
     \k{DEF} PERSON = \k{POWER}(\k{Tuple} name :\k{String} \k{end})
\end{xple}

Im ersten Beispiel wird der Kind der einstelligen Typoperatoren 
definiert und an den Namen {\sl TYPOP} gebunden. Das Schl"usselwort 
{\sl ALL} dient zur Definition von Typen von Typoperatoren.
Der im zweiten Beispiel definierte Kind {\sl PERSON} repr"asentiert 
alle Tupeltypen,  deren erste Komponente den Attributnamen {\sl name} hat und vom Typ
{\sl String} ist, die aber eventuell weitere Komponenten besitzen. Wenn {\sl T} ein Typ ist, dann ist {\sl POWER(T)} ein Kind, und zwar die Menge aller Subtypen von {\sl T}. 

\section{Funktionen in \PQ}

\label{Funktionen}
Neben den aus anderen Programmiersprachen bekannten {\em einfachen} und
{\em rekursiven} Funktionen gibt es in \PQ\ zus"atzlich Funktionen
{\em h"oherer Ordnung} und {\em polymorphe} Funktionen. Auf diese Arten von Funktionen und ihre Definition in \PQ\ wird im folgenden geanauer eingegangen.

\subsection{Einfache Funktionen}

Da das Konzept der einfachen Funktionen aus anderen Programmiersprachen hinreichend bekannt ist, soll es hier gen"ugen, ihre Syntax in \PQ\ einzuf"uhren. Diese unterscheidet sich allerdings ein wenig von der in traditionellen Programmiersprachen "ublichen. Funktionen werden durch das Schl"usselwort {\sl fun} eingeleitet, und die einzelnen Parameter werden nicht durch Kommata, sondern durch Leerzeichen voneinander getrennt, wie an den beiden folgenden Beispielen zu sehen ist: 
\begin{xple}
     \k{let} succ = \k{fun}(a :\k{Int}) :\k{Int} a + 1
     \k{let} add = \k{fun} (a :\k{Real} b :\k{Real}) :\k{Real} a ++ b 
\end{xple}

Die erste Funktion {\sl succ} erwartet einen Parameter vom Typ {\sl Int} und liefert als Ergebnis auch einen Wert vom Typ {\sl Int} zur"uck. Sie berechnet f"ur einen ganzzahligen Eingabewert den direkten Nachfolger. Die zweite Funktion {\sl add} addiert zwei reelle Zahlen. Sie erwartet zwei Parameter vom Typ {\sl Real} und liefert einen Wert vom Typ {\sl Real} zur"uck. Die Syntax von \PQ\ l"a"st auch folgende verk"urzte Schreibweisen zu:
\begin{xple}
     \k{let} succ(a :\k{Int}) :\k{Int} = a + 1
     \k{let} add(a, b :\k{Real}) :\k{Real} = a ++ b
\end{xple}

In \PQ\ gibt es keine Operator"uberladungen. Deshalb gibt es je nach Parametertytp  unterschiedliche Additionsoperatoren.
W"ahrend zwei ganze Zahlen mit einem Pluszeichen ({\sl +}) addiert werden, benutzt man f"ur die Addition zweier reeller Zahlen ein doppeltes Pluszeichen
({\sl ++}).


\subsection{Rekursive Funktionen}

Rekursive Funktionen werden durch das Schl"usselwort {\sl rec} gekennzeichnet. Ein  Beispiel f"ur rekursive Funktionen ist die bekannte Fakult"atsberechnung:
\begin{xple}
     \k{let rec} fac(n :\k{Int}) :\k{Int} =
        \k{if} n \k{is} 0
           \k{then} 1
           \k{else} n * fac(n - 1)
        \k{end}
\end{xple}
Bei diesem Beispiel ist au"serdem zu beachten, da"s der Test auf Gleichheit zweier Werte nicht durch das Gleichheitszeichen, sondern durch den Operator {\sl is} geschieht. Das dient der Vermeidung von Operator"uberladungen\footnote{Das Gleichheitszeichen dient der Bindung an eine Variable.}. Der Operator {\sl is} testet einfache Werte, wie z.B. Zahlen auf Gleichheit, strukturierte Werte hingegen, wie z.B. Tupel, auf Identit"at. 

Um wechselseitig rekursive Funktionen zu schreiben, m"ussen Funktionen 
{\em parallel} definiert werden. In \PQ\ verbindet man hierbei die Definitionen
mit dem Schl"usselwort {\sl and}. Als Beispiel ist hier ein Parit"atstest
aufgef"uhrt.
%\begin{figure}
\begin{xple}
     \k{let rec} even(n :\k{Int}) :\k{Bool} =
        \k{if} n \k{is} 0 \k{then} 
           true
        \k{elsif} n $<$ 0 \k{then}
           even(int.abs(n))
        \k{else}
           odd(n - 1)
        \k{end}
     \k{and} odd(n :\k{Int}) :\k{Bool} =
        \k{not}(even(n))
\end{xple}
%\end{figure}

\subsection{Funktionen h"oherer Ordnung}

Funktionen h"oherer Ordnung sind Funktionen, denen Funktionen als Parameter
"ubergeben werden bzw. die Funktionen als Ergebnis zur"uckliefern
k"onnen.

Ein Beispiel f"ur Funktionen h"oherer Ordnung ist die Funktion {\sl double}. 
\begin{xple}
     \k{let} double(f(a :\k{Int}) :\k{Int} a :\k{Int}) :\k{Int} = f(f(a))
\end{xple}

Sie erh"alt als ersten Parameter eine Funktion, die ganzzahlige Werte auf ganzahlige Werte abbildet, und als zweiten Parameter einen ganzzahligen Wert "ubergeben. {\sl double} wendet die "ubergebene Funktion zweimal hintereinander auf den "ubergebenen Wert an. 

Ein Aufruf der Funktion {\sl double} mit der Funktion {\sl succ} und der Zahl 4 als Parameter ({\sl double(succ 4)}) zum Beispiel, berechnet den Nachfolger vom Nachfolger von vier, also die Zahl Sechs.     

\subsection{Polymorphe Funktionen}

Eine Funktion wird zu einer polymorphen oder generischen Funktion, indem man ihre Signatur durch einen oder mehrere Typparameter erweitert ({\em parametrischer 
Polymorphismus}).  Die Typparameter werden beim Aufruf durch Typen instanziiert.

Ein einfaches Beispiel f"ur ein polymorphe Funktion ist eine polymorphe Identit"atsfunktion. Sie soll hier in zwei Versionen betrachtet werden: 
\begin{xple}
     \k{let} identity1(A ::\k{TYPE})(a :A) :A = a
     \k{let} identity2(A ::\k{TYPE} a :A) :A = a
\end{xple}
Die Versionen unterscheiden sich dadurch, da"s die erste in zwei Stufen parametrisiert werden kann, w"ahrend die zweite in einer Stufe parametrisiert werden mu"s. 

Die erste Version kann in der ersten Stufe nur mit einem Typ {\sl T} parametrisiert werden. Man erh"alt dann eine Identit"atsfunktion auf dem Typ {\sl T}, was hier am Beispiel des Typs {\sl Integer} gezeigt wird:
\begin{xple}
     \k{let} intId = identity1(:\k{Int})
\end{xple}

Die zweite Version mu"s sofort mit einem Typ {\sl T} und mit einem Wert {\sl t} dieses Typs parametrisiert werden und liefert als Ergebnis {\sl t} zur"uck. In der Regel kann  dabei jedoch die Angabe des Typs weggelassen werden, da dieser vom \PQ\/-System durch Typinferenz aus dem "ubergebenen Wert hergeleitet werden kann.

Folgende Aufrufe der definierten Funktionen liefern alle das gleiche Ergebnis und zeigen noch einmal die verschiedenen Parametrisierungen der beiden Versionen der polymorphen Identit"atsfunktion:
\begin{xple}
     intId(4) 
     identity1(:\k{Int})(4)
     identity2(:\k{Int} 4)
     identity2(4)
\end{xple}

F"ur die Instanziierung von Typparametern sind nicht nur die Basistypen, sondern auch beliebige benutzerdefinierte Typen zul"assig.
\begin{xple}
     \k{Let} Person = \k{Tuple} name :\k{String} age :\k{Int} \k{end}
     \k{let} selfId = identity1(:Person) 
\end{xple}
Der gro"se Vorteil von polymorphen Funktionen ist, da"s man eine Funktion schreiben kann, die auf allen Typen arbeitet, anstatt f"ur jeden Typ eine eigene Version dieser Funktion zu schreiben. Sie eignen sich also besonders zur Beschreibung von Verhalten, das typunabh"angig ist. 

Eine besondere St"arke von \PQ\ liegt in der M"oglichkeit, das Konzept der polymorphen und der h"oheren Funktionen miteinander zu kombinieren. Dies soll am Beispiel einer 
polymorphen Sortierfunktion veranschaulicht werden. Das eigentliche Sortieren, d.h. das Umordnen der Elemente ist typunabh"angig, kann also im Rahmen einer polymorphen Funktion beschrieben werden. Das Vergleichen der Elemente jedoch, das beim Sortieren durchgef"uhrt werden mu"s, ist typabh"angig. Diese Aufgabe kann gel"ost werden, indem man der polymorphen Sortierfunktion eine Funktion als Parameter "ubergibt, deren Aufruf den Vergleich von zwei Elementen durchf"uhrt. 
 
Die Signatur einer polymorphen Sortierfunktion, die Felder von Elementen sortiert, k"onnte dann wie folgt aussehen:  
\begin{xple}
     \k{let} sort(A ::\k{TYPE} order(a,b :A) :\k{Bool} a :\k{Array}(A)) :\k{Array}(A) = \dots
\end{xple}
Um ein konkretes Feld zu sortieren, mu"s man noch eine Vergleichsfunktion auf dem Elementtyp schreiben. Mit dieser Funktion legt man das Sortierkriterium und die Sortierreihenfolge fest. Als Beispiel sei hier die Sortierung von Personen nach ihrem Alter gew"ahlt:
\begin{xple}
     \k{let} older(a, b :Person) :\k{Bool} = a.age $>$ b.age
\end{xple}

Der folgende Aufruf der Funktion {\sl sort} sortiert dann ein Feld von Personen, und zwar nach ihrem Alter. 
\begin{xple}
     sort(:Person older personArray)
\end{xple}
In den Abschnitten \ref{operatoren} und \ref{adt} sind Beispiele f"ur die 
Implementation polymorpher Funktionen zu finden.



\section{Datentypen und Typoperatoren}

Die Sprache \PQ\ enth"alt neben den Basistypen {\sl Ok}, {\sl Bool}, {\sl Char} {\sl String}, {\sl Int} und {\sl Real} die Typkonstruktoren {\sl Tuple}, {\sl Option}, {\sl Array} und {\sl Exception}\footnote{Auf die Typkonstruktoren {\sl Array} und {\sl Exception} wird in sp"ateren Abschnitten genauer eingegangen.}. Dabei entspricht der Typ {\sl Tuple} dem Record traditioneller Programmiersprachen und der Typ {\sl Option} dem varianten Record.
Definitionen von Tupel- bzw. Optionstypen und zugeh"origer Wert sehen wie folgt aus:
\begin{xple}
     \k{Let} Point = \k{Tuple} x :\k{Int} y :\k{Int} \k{end}
     \k{let} point = \k{tuple let} x = 5 \k{let} y = 7 \k{end}
    
     \k{Let} Figure =
        \k{Option}
           circle \k{with} center :Point radius :\k{Int} \k{end}
           triangle \k{with} point1, point2, point3 :Point  \k{end}
           rectangle \k{with} point1, point2, point3 :Point \k{end}
        \k{end}
     \k{let} circle =
        \k{option} circle \k{of} Figure \k{with let} center = point \k{let} radius = 1 \k{end}
\end{xple}

Der Zugriff auf Komponenten eines Tupels geschieht mit Hilfe der Punktnotation. Optionen werden im allgemeinen mit einer {\sl case}-Anweisung inspiziert.

Soviel zu den grundlegenden Typen in \PQ. Im folgenden wird auf die spezielleren Typen und auf die Typoperatoren eingegangen. 
   
\subsection{Funktionstypen}

In \PQ\ ist jeder Funktion (auch den polymorphen und denen h"oherer Ordnung) ein Typ zugeordnet. Funktionstypen werden mit dem Schl"usselwort {\sl All} eingeleitet. Zur Veranschaulichung sind anschlie"send die Typen einiger der im Abschnitt \ref{Funktionen} definierten Funktionen aufgef"uhrt:
\begin{xple}
     succ, fac :\k{All}(:\k{Int}) \k{Int}
     add :\k{All}(:\k{Real} :\k{Real}) \k{Real}
     double :\k{All}(:\k{All}(:\k{Int}) \k{Int} :\k{Int}) \k{Int}
     identity1 :\k{All}(A ::\k{TYPE}) \k{All}(:A) A
     identity2 :\k{All}(A ::\k{TYPE} :A) A
     sort :\k{All}(A ::\k{TYPE} :\k{All}(:A :A) \k{Bool} :\k{Array}(A)) \k{Array}(A)
\end{xple}

\subsection{Rekursive Datentypen}

Rekursive Datenstrukturen, wie Listen, Mengen und B"aume spielen eine wichtige Rolle in der Informatik. \PQ\ bietet deshalb auch eine M"oglichkeit zur Definition von rekursiven Datentypen, mit denen rekursive Datenstrukturen auf einfache Weise realisiert werden k"onnen. Als Beispiel sei hier die Definition einer Liste f"ur ganze Zahlen gezeigt:
\begin{xple}
     \k{Let Rec} IntegerList ::\k{TYPE} =
        \k{Option}
           nil
           cons \k{with} head :\k{Int} tail :IntegerList \k{end}
        \k{end}
\end{xple}

Die Definition von rekursiven Typen wird durch {\sl Rec} eingeleitet.

An diesem Beispiel l"a"st sich die Einf"uhrung von Typoperatoren motivieren, die im n"achsten Abschnitt beschrieben werden. "Ahnlich wie beim "Ubergang zu polymorphen Funktionen ist es auch hier w"unschenswert, gemeinsame, typunabh"angige Muster herauszukristallisieren und f"ur diese Muster generischen Code zu schreiben, der f"ur die einzelnen Typen instanziiert werden kann. Im konkreten Fall w"are das so etwas wie eine polymorphe Liste, die mit einem Typ {\sl E} instanziert eine Liste "uber Elementen vom Typ {\sl E} ergibt.

\subsection{Typoperatoren} \label{operatoren}

Typoperatoren sind Funktionen, die Typen auf Typen abbilden. Sie 
erm"oglichen es, Typdeklarationen zu parametrisieren. 

Ein einfaches Beispiel f"ur einen Typoperator ist eine der weiter oben eingef"uhrten Identit"atsfunktion entsprechende Funktion auf der Typebene:
\begin{xple}
     \k{Let} Identity = \k{Fun}(E ::\k{TYPE}) ::\k{TYPE} E
\end{xple}
oder k"urzer ("ahnlich wie bei den Funktionen):
\begin{xple}
     \k{Let} Identity(E ::\k{TYPE}) ::\k{TYPE} = E
\end{xple}
Der Operator {\sl Identity} bildet den als Parameter "ubergebenen Typ auf sich selbst ab.

Wie im vorigen Abschnitt bereits erw"ahnt, soll jetzt ein Typoperator {\sl List} betrachtet werden, der einen Typ {\sl E} auf den Typ einer Liste mit Elementen des Typs {\sl E} abbildet. Dazu wird in die Listendefinition des vorigen Abschnittes ein Typparameter eingef"uhrt.
\begin{xple}
     \k{Let} List(E ::\k{TYPE}) ::\k{TYPE} =
        \k{Rec}(L)
           \k{Option}
              nil
              cons \k{with} head :E tail :L \k{end}
           \k{end}
\end{xple}

Der Typoperator {\sl List} bildet den Typ {\sl E} auf einen rekursiven Optionstyp {\sl L} ab, wobei die erste Komponente vom Typ {\sl E} und die zweite vom Typ {\sl L} ist\footnote{Hierbei ist zu beachten, da"s der Operator {\sl List} einen Typ {\sl E} auf einen rekursiven Typ abbildet. Der eigentliche Typoperator ist jedoch nicht rekursiv. Rekursive Typoperatoren sind in \PQ\ nicht zul"assig, da sie zu Entscheidbarkeitsproblemen f"uhren.}. Die notwendigen Listenoperationen k"onnen dann durch polymorphe Funktionen implementiert 
werden.
\begin{xple}
     \k{let} new(E ::\k{TYPE}) :List(E) =
        \k{option} nil \k{of} List(E) \k{end}
   
     \k{let} cons(E ::\k{TYPE} head :E tail :List(E)) :List(E) =
        \k{option} cons \k{of} List(E) \k{with} head tail \k{end}
\end{xple}
Mit der polymorphen Funktion {\sl new} k"onnen leere Listen beliebigen 
Typs erzeugt werden, und "uber die Funktion {\sl cons} k"onnen Elemente an
den Listenanfang angef"ugt werden. 

Der daraus resultierende Vorteil ist, da"s im Gegensatz zu traditionellen 
Programmiersprachen generische Listen-, Mengen- oder Baumtypen sowie
polymorphe Operationen auf diesen definiert werden k"onnen, was die Anzahl
der zu implementierenden Funktionen stark reduziert. Desweiteren k"onnen
die Implementationen dieser Strukturen in einfacher Weise modifiziert und
ausgetauscht werden, ohne Programme dadurch zu invalidieren.

Die Konzepte der polymorphen Funktionen und der Typoperatoren erg"anzen sich also ideal und erm"oglichen die Verwendung von generischem Code sowohl bei der Beschreibung von Strukturen als auch bei der Beschreibung von Verhalten. 


\subsection{Abstrakte Datentypen} \label{adt}

Ein Abstrakter Datentyp (ADT) besteht aus einem Datentyp und einem Satz von Operationen auf diesem Datentyp. Dabei wird dem Benutzer nur der Name des Typs und die Signaturen und Namen der Operationen zur Verf"ugung gestellt. Ein ADT verbirgt  die Implementation des Typs und der Operationen nach au\3en. Die zur Verf"ugung gestellten Operationen sind die einzig m"oglichen und zul"assigen auf dem abstrakten Datentyp. Dadurch werden die Elemente des ADTs vor unzul"assiger Benutzung gesch"utzt. 

Da die Implementation verborgen bleibt, kann sie nachtr"aglich ge"andert werden, ohne dadurch Programme zu invalidieren, die den ADT benutzen. Auch kann, falls mehrere Implementationen eines ADT zur Verf"ugung stehen, zwischen diesen dynamisch gew"ahlt werden. 
 

Als Beispiel sei hier ein allgemeiner, funktionaler Kellerspeicher mit Operationen auf demselben vorgestellt. Der Kellerspeicher wird in Form eines polymorphen, abstrakten Datentyps deklariert. 
\begin{xple}
     \k{Let} FunStack =
        \k{Tuple}
           T ::\k{ALL}(E ::\k{TYPE}) \k{TYPE}
           new(E ::\k{TYPE}) :T(E)
           empty(E ::\k{TYPE} stack :T(E)) :\k{Bool}
           push(E ::\k{TYPE} element :E stack :T(E)) :T(E)
           pop(E ::\k{TYPE} stack :T(E)) :T(E)
           top(E ::\k{TYPE} stack :T(E)) :E
        \k{end}
\end{xple}

Zu dieser Schnittstelle wird im folgenden eine auf dem Modul {\sl list}\footnote
{{\sl list} ist ein Modul der Standardbibliothek, das eine polymorphe
Liste mit dazugeh"origen Operationen anbietet.} basierende
Implementation vorgestellt.
\begin{xple}
     \k{let} listStack :FunStack =
        \k{tuple}
           \k{Let} T(E ::\k{TYPE}) ::\k{TYPE} = list.T(E)
           \k{let} new(E ::\k{TYPE}) :T(E) = list.new(:E)
           \k{let} empty(E ::\k{TYPE} stack :T(E)) :\k{Bool} = list.empty(stack)
           \k{let} push(E ::\k{TYPE} element :E stack :T(E)) :T(E) =
              list.cons(element stack)
           \k{let} pop(E ::\k{TYPE} stack :T(E)) :T(E) = list.tail(stack)
           \k{let} top(E ::\k{TYPE} stack :T(E)) :E = list.head(stack)
        \k{end}
\end{xple} 

Man sieht, da"s in diesem Beispiel die Operationen {\sl new}, {\sl empty},
{\sl push}, {\sl pop} und {\sl top} als polymorphe Funktionen implementiert
wurden, so da"s Kellerspeicher f"ur beliebige Datentypen erzeugt werden 
k"onnen.


\section{Subtypisierung und Subtyppolymorphismus}
\label{subtypisierung}

In \PQ\ gibt es eine Subtypbeziehung ($<$:) zwischen Typen. Sie ist wie folgt definiert:
Wenn {\sl x} vom Typ {\sl A} ist und es gilt
\mbox{\sl A $<$:B} (A ist Subtyp von B), dann ist {\sl x} auch vom Typ {\sl B}. 
Die Intuition hinter dieser Subtypisierung ist Mengeninklusion. 

\bslop
Die Menge aller Subtypen eines Typs {\sl T} wird mit {\sl POWER(T)}
bezeichnet. \mbox{\sl A ::POWER(B)} und \mbox{\sl A $<$:B}
haben damit die gleiche Bedeutung und die zweite wird als Abk"urzung f"ur die erste Schreibweise betrachtet. 
\eslop
 
Zwischen den Basistypen gibt es keine Subtypbeziehungen au"ser den trivialen. F"ur strukturierte Typen sind die Subtypbeziehungen induktiv definiert. Dazu gibt es f"ur alle Typoperatoren Subtypisierungsregeln. Aus Platzgr"unden wird an dieser Stelle jedoch nur die Subtypisierung bei Tupel- und Optionstypen betrachtet:
\begin{description} 
\item [Tupel:] Ein Tupeltyp {\sl A} ist Subtyp eines Tupeltyps {\sl B}, wenn {\sl A} mindestens alle Komponenten von {\sl B} enth"alt oder genauer, wenn f"ur alle Komponenten von {\sl B} gilt: Die Namen der i-ten Komponente in A und B stimmen "uberein und der Typ der i-ten Komponente in {\sl A} mu"s ein Subtyp der i-ten Komponente in {\sl B} sein. Da die Komponenten von Tupeln geordnet sind, kommt es dabei auf die Reihenfolge der Komponenten an.

So ist in folgendem Beispiel {\sl Employee} ein Subtyp von {\sl Person}, nicht aber {\sl Student}:
\begin{xple}
     \k{Let} Person = \k{Tuple} name :\k{String} age :\k{Int} \k{end}
     \k{Let} Employee = \k{Tuple} name :\k{String} age :\k{Int} company :\k{String} \k{end}
     \k{Let} Student = \k{Tuple} name :\k{String} matrNr :\k{Int} age :\k{Int} \k{end}
\end{xple}


\item [Optionen:] Ein Optionstyp {\sl A} ist Subtyp eines Optionstyps {\sl B}, wenn {\sl B} mindestens alle Komponenten von {\sl A} enth"alt oder genauer, wenn f"ur alle Komponenten von {\sl A} gilt: Die Namen der i-ten Komponente in {\sl A} und {\sl B} stimmen "uberein und er Typ der i-ten Komponente in {\sl A} mu"s ein Subtyp der i-ten Komponente in {\sl B} sein (im Sinne der Subtypisierung bei Tupeln). Auch die Komponenten von Optionen sind geordnet. Es kommt also auch hier auf die Reihenfolge der Komponenten an.

Der Typ {\sl WeekDay} in folgendem Beispiel ist offensichtlich ein Subtyp vom Typ {\sl Day}. Es gilt die Beziehung {\sl WeekDay} \k{$<$:} {\sl Day}.

\begin{xple}
     \k{Let} Day =
        \k{Option} mon tue wed thu fri sat sun \k{end}
        
     \k{Let} WeekDay =
        \k{Option} mon tue wed thu fri \k{end}
\end{xple}
\end{description}

Die Subtypisierungsregeln f"ur die anderen Konstruktoren sehen "ahnlich, aus werden aber, wie oben bereits erw"ahnt, hier nicht behandelt.

Ein gro"ser Vorteil der Subtypisierung ist die Tatsache, da"s Funktionen, die auf einem Typ arbeiten, auch Werte jedes beliebigen Subtyps dieses Typs akzeptieren. Subtypisierung erleichtert somit die nachtr"agliche Erweiterung von Programmen, insbesondere die Erweiterung von Datenstrukturen um neue Komponenten. Funktionen, die f"ur den urspr"unglichen Typ geschrieben worden sind, arbeiten dann auch auf Werten des neuen Typs, weil sie als Instanzen des alten Typs erkannt werden. 

Folgendes Beispiel zeigt die Anwendung, aber auch die Begrenzungen dieses Konzeptes. Seien folgende Tupel definiert:

\begin{xple}
\begin{tabbing}
     123456789012345678901234567890 \= \kill
     \k{let} florian :Person =         \>      \k{let} gabi :Employee = \\
        \k{tuple}                      \>         \k{tuple} \\
           \k{let} name =  ''Florian'' \>            \k{let} name =  ''Gabi'' \\
           \k{let} age = 27            \>            \k{let} age = 29 \\
        \k{end}                        \>            \k{let} company =  ''ibm'' \\
                                       \>         \k{end}
\end{tabbing}
\end{xple}


Es wird jetzt eine Funktion {\sl show} betrachtet, die den Inhalt eines Personentupels anzeigen kann. 
\begin{xple}
     \k{let} show(p :Person) :Person = p
     show(florian)
     \k{tuple} name =  ''Florian'' age = 27 \k{end} :Person

\end{xple}
Da der Typ {\sl Employee} ein Subtyp des Typs {\sl Person} ist, kann man dieser Funktion auch ein Angestelltentupel als Parameter "ubergeben.
\begin{xple}
     show(gabi)
     \k{tuple} name =  ''Gabi'' age = 29 \k{end} :Person
\end{xple}

Allerdings ist der R"uckgabewert der Funktion vom Typ {\sl Person}. Es geht also Typinformation verloren, was zur Folge hat, da"s die Firma von
Gabi nicht ausgegeben wird. Damit auch dieses Attribut bei der Ausgabe
ber"ucksichtigt wird, ist es notwendig, die Funktion {\sl show} als 
polymorphe Funktion zu implementieren.
\begin{xple}
     \k{let} show2(A $<$:Person a :A) :A = a

     show2(gabi)
     \k{tuple} name =  ''Gabi'' age = 29 company =  ''ibm'' \k{end} :Employee
\end{xple}

Da gen"ugend Typinformation in die Funktionsdefinition integriert wurde,
werden nun alle Attribute ausgegeben. Durch die Angabe 
von {\sl A} \k{$<$:} {\sl Person} wird die Funktion {\sl show} zu
einer polymorphen Funktion, wobei jedoch der Polymorphismus im Gegensatz
zum parametrischen Polymorphismus auf Subtypen des Typs {\sl Person} 
beschr"ankt wird. Diesen auf Subtypen eines Typs eingeschr"ankten Polymorphismus bezeichnet man als {\em Subtyppolymorphismus}\footnote{Aufgrund eines Fehlers im Compiler funktioniert
in der derzeitigen Version des \PQ\/-Systems die explizite Angabe von Subtypbeziehungen
nicht.}.

\section{Imperative Programmierung}

Die imperative Programmierung basiert auf ver"anderbaren Werten in einem
globalem Speicher. Der Kontrollflu"s wird durch Konstrukte f"ur Sequenzen
und Schleifen gesteuert.

\subsection{Ver"anderbare Variablen}

Die Bindung eines Namens an einen Wert durch das {\sl let}-Konstrukt entspricht der Definition einer Konstanten, da der dem Namen zugewiesene Wert nicht durch eine Zuweisung modifiziert werden kann.  Wird an einen bereits existierenden Namen mit {\sl let} ein neuer Wert gebunden, so bewirkt dies die Erzeugung einer neuen Variablen (eigentlich Konstanten). 

Soll eine Variable modifizierbar sein, so mu"s sie bei der Bindung explizit
als modifizierbar gekennzeichnet werden. Dies geschieht durch Angabe des
Schl"usselworts {\sl var} bei der Definition.
\begin{xple}
     \k{let} a = 7
     \k{let var} b = 9
     b := b + 4
\end{xple}
Nur f"ur die Variable {\sl b} ist eine Zuweisung m"oglich. Eine Zuweisung an die Variable {\sl a} f"uhrt bei der "Ubersetzung zu einem Typfehler, da  modifizierbare Werte nicht vom Typ T, sondern von dem speziellen Typ {\sl Var(T)} sind.

Es ist zu beachten, da"s in der gegenw"artigen Implementation von \PQ\ f"ur beliebige Typen {\sl T} weder globale Variablen vom Typ {\sl Var(T)} innerhalb von Funktionen ver"andert werden k"onnen, noch Werte vom Typ {\sl Var(T)} als Parameter von Funktionen zugelassen sind. Diese Einschr"ankungen k"onnen umgangen werden, indem Variablen dieses Typs zuvor in eine Struktur, z.B. in ein Tupel eingebettet werden\footnote{Ein Beispiel hierf"ur findet sich bei der Definition des modifizierbaren Kellerspeichers in Abschnitt \ref{interfaces}.}. 

\subsection{Sequenzen und Schleifen}

Eine Sequenz ist eine Zusammenfassung von Ausdr"ucken. Der Typ einer Sequenz
ist der Typ des letzten Ausdrucks in der Sequenz. Sequenzen werden durch die Schl"usselworte {\sl begin} und {\sl end} zu Bl"ocken zusammengefa"st.

Schleifen fassen Folgen von Ausdr"ucken zum Zweck der Iteration zusammen.  Der Typ einer solchen Schleife ist {\sl Ok}. Die allgemeinste Form ist die {\sl loop}-Schleife. Zus"atzlich gibt es noch zwei speziellere Formen von Schleifen, die {\sl while}-Schleifen und die {\sl for}-Schleifen. Als Beispiel f"ur Sequenzen und Schleifen sei hier eine Funktion angegeben, die den gr"o"sten gemeinsamen Teiler von zwei ganzen Zahlen bestimmt.

\begin{xple}
     \k{let} gcd(n,m :\k{Int}) :\k{Int} =
        \k{begin}
           \k{let var} vn = n
           \k{and var} vm = m
           \k{while} vn \k{isnot} vm \k{do}
              \k{if} vn $>$ vm \k{then} vn := vn - vm \k{end}
              \k{if} vn $<$ vm \k{then} vm := vm - vn \k{end}
           \k{end}
           vn
        \k{end}
\end{xple}

Typ und Wert der Sequenz ergeben sich aus ihrem letzen Ausdruck, in diesem
Fall {\sl vn}.

\subsection{Der Datentyp {\sl Array}}

Ein Feld ({\sl Array}) ist eine durch nicht negative ganze Zahlen indizierte Sequenz von Elementen gleichen Typs. Die Gr"o"se des Felds wird bei der Erzeugung festgelegt und kann danach nicht mehr ge"andert werden. Die Elemente des Felds hingegen stellen modifizierbare Werte dar.
\begin{xple}
     \k{let} a:\k{Array}(\k{Int}) = \k{array of} 0 1 2 3 4 5 \k{end}
     \k{let} b:\k{Array}(\k{Bool}) = \k{array of} (5 false)
     b[0] := \{a[0] \k{is} 0\}
\end{xple}
Es gibt zwei M"oglichkeiten, ein Feld zu initialisieren: Beim
sechselementigen Feld {\sl a} sind die Elemente einzeln aufgef"uhrt und
in {\sl array of} und {\sl end} eingeschlossen. Die zweite M"oglichkeit ist
die Angabe der Anzahl der Elemente und des Initialisierungswertes, so
geschehen beim Feld {\sl b}. Die einzelnen Elemente k"onnen, wie aus anderen Programmiersprachen bekannt, durch einem Wert in eckigen Klammern
indiziert werden.

Mit Hilfe der {\sl for}-Schleife kann eine Summenfunktion f"ur beliebig
gro"se Felder ganzer Zahlen definiert werden.
\begin{xple}
     \k{let} sum(a :\k{Array}(\k{Int})) :\k{Int} =
        \k{begin}
           \k{let var} total = 0
           \k{for} i = 0 \k{upto} extent(a) - 1 \k{do}
              total := total + a[i]
           \k{end}
           total
        \k{end}
\end{xple}
Mit dem Operator {\sl extent} kann die Gr"o"se von Feldern ermittelt werden.
Die Schleifenvariable {\sl i} mu"s nicht deklariert werden. 

Sind Felder Parameter von Funktionen, so kann eine abk"urzende Schreibweise benutzt werden.
\begin{xple}
\begin{tabbing}
     1234567890123456789012345 \= \kill
     sum \k{of} 1 2 3 4 \k{end}   \> {\rm statt\sl} sum(\k{array of} 1 2 3 4 \k{end}) \\
     sum \k{of} (5 2)             \> {\rm statt\sl} sum(\k{array of} (5 2))
\end{tabbing}
\end{xple}



\section{Module und Schnittstellen}
\label{interfaces}
Die Modularisierung ist nach den Funktionen die wichtigste 
Struk\-tu\-rie\-rungs\-m"og\-lich\-keit moderner Programmiersprachen. \PQ\ bietet
"ahnlich wie Modula-2 \cite{Wirt83} die M"oglichkeit, gro"se Programme in 
Schnittstellenmodule ({\em interfaces}) und die eigentlichen Implementationsmodule
({\em modules}) zu unterteilen. In den Schnittstellenmodulen werden die Bezeichner und Typen der Variablen, die Bezeichner und Kinds der abstrakten Datentypen und die Bezeichner und Signaturen der Funktionen und Typoperatoren, die von den Modulen implementiert und exportiert werden, deklariert.

Zus"atzlich kann ein Schnittstellenmodul Typdefinitionen enthalten. Diese werden nicht wie normale Typdefinitionen mit {\sl Let}, sondern mit dem Schl"usselwort {\sl Def} eingeleitet. Die Definition dieser Typen ist, anders als die abstrakten Datentypen, f"ur alle Benutzer der Schnittstelle sichtbar. Werden solche Typen von anderen Modulen benutzt, so
ist als Name $<$Schnittstellenname$>$\_$<$Typname$>$ anstatt 
$<$Modulname$>$.$<$Typname$>$ zu verwenden.

In \PQ\ k"onnen zu einem Schnittstellenmodul im Gegensatz zu Modula-2 beliebig viele 
Implementationsmodule existieren. Module sind, wie Funktionen, 
Objekte {\em erster Klasse}, was bedeutet, da"s sie an Bezeichner gebunden
und als Parameter an Funktionen "ubergeben werden k"onnen. 

\bslop
Schnittstellen- und Implementationsmodule m"ussen auf dem {\em Top-Level} der 
interaktiven Programmierumgebung definiert werden, wobei dadurch implizit 
externe Dateien, die den Schnitt\-stel\-len- beziehungsweise Modulcode
enthalten, erzeugt werden.
\eslop

Beide Modularten k"onnen ihrerseits von anderen Modulen importieren. Dies
geschieht mittels des Schl"usselwortes {\sl import}. Als Beispiel wird noch einmal ein Kellerspeicher betrachtet. Im Gegensatz zu dem in Abschnitt \ref{adt} vorgestellten wurde hier aber ein modifizierbarer Kellerspeicher gew"ahlt. 

\begin{xple}
     \k{interface} Stack
     \k{export}
        T(E ::\k{TYPE}) ::\k{TYPE}
        new(E ::\k{TYPE}) :T(E)
        empty(E ::\k{TYPE} stack :T(E)) :\k{Bool}
        push(E ::\k{TYPE} element :E stack :T(E)) :\k{Ok}
        pop(E ::\k{TYPE} stack :T(E)) :\k{Ok}
        top(E ::\k{TYPE} stack :T(E)) :E
     \k{end}
\end{xple}


Ein zugeh"origes Implementationsmodul, das wie die in Abschnitt \ref{adt} vorgestellte Implementation eine Realisierung des Kellerspeichers basierend auf Listen verwendet, k"onnte dann wie folgt aussehen:
\begin{xple}
     \k{module} stack :Stack
     \k{import} list:List
     \k{export}
        \k{Let} T(E ::\k{TYPE}) ::\k{TYPE} = \k{Tuple var} l :list.T(E) \k{end}
        \k{let} new(E ::\k{TYPE}) :T(E) = 
           \k{tuple let var} l = list.new(:E) \k{end}
        \k{let} empty(E ::\k{TYPE} stack :T(E)) :\k{Bool} = list.empty(stack.l)
        \k{let} push(E ::\k{TYPE} element :E stack :T(E)) :\k{Ok} =
           stack.l := list.cons(element stack.l)
        \k{let} pop(E ::\k{TYPE} stack :T(E)) :\k{Ok} =
           stack.l := list.tail(stack.l)
        \k{let} top(E ::\k{TYPE} stack :T(E)):E = list.head(stack.l)
     \k{end}
\end{xple} 


Das Modul kann nun seinerseits von anderen Modulen importiert werden.
Nach einem Import in ein Programm oder Modul kann mit der Punktnotation auf die Modulkomponenten zugegriffen werden.
\begin{xple}
     \k{module} main
     \k{import} stack :Stack print :Print
        \k{let} s = stack.new(:\k{Int})
        stack.push(7 s)
        \k{if} not stack.empty(s) \k{then}
           print.Int(stack.top(s))
        \k{end}
     \k{end};
\end{xple}

\section{Ausnahmebehandlung}

Wie die Modularisierung, dient auch die Ausnahmebehandlung
({\em Exception handling}) der Strukturierung gro"ser Programme. Sie ist ein Kontrollflu"smechanismus, der sich in \PQ\ aber problemlos in das 
Typkonzept einf"ugt. 

Die Ausnahmebehandlung ist ein wichtiges Konzept in einer Programmiersprache, weil bereits einfache Funktionen, wie z.B das Teilen durch Null, Fehlersituationen erzeugen, die abgefangen werden m"ussen. Neben diesen Standardausnahmen unterst"utzt \PQ\ auch benutzerdefinierte Ausnahmen.

Daf"ur gibt es einen speziellen Typoperator {\sl Exception}, mit dem man verschiedene Typen f"ur Ausnahmen definieren kann. Eine Ausnahme vom Typ {\sl Exception(T)} kann, wenn sie ausgel"ost wird, einen Wert vom Typ T als Parameter erhalten. 

"Ahnlich wie beim Typ {\sl Tuple} werden Werte vom Typ {\sl Exception(T)} zwischen zwei Schl"usselworten eingeschlossen, und zwar {\sl exception} und {\sl end}:
\begin{xple}
     \k{let} exc1 :\k{Exception}(\k{Int}) =
        \k{exception} integerException :\k{Int} \k{end}
     \k{let} exc2 :\k{Exception}(\k{String}) =
        \k{exception} stringException :\k{String} \k{end}
\end{xple}
 
Eine Ausnahme wird mit dem {\sl raise}-Befehl ausgel"ost. Dabei kann, wie oben bereits erw"ahnt, ein Wert vom entsprechenden Typ als Parameter "ubergeben werden. 
\begin{xple}
     \k{raise} exc1 \k{with} 3 \k{end}
\end{xple}

Weiterhin bietet \PQ\  die M"oglichkeit Ausnahmen abzufangen. Dazu wird das {\sl try}-Konstrukt verwendet:
\begin{xple}
     \k{try}
        \dots
        \k{raise} exc1 \k{with} 55 \k{end}
        \dots
        \k{when} exc1 \k{with} x \k{then} x + 5
        \k{when} exc2 \k{then} 1
        \k{else} 0
     \k{end}
\end{xple}

Die einzelnen Zweige des {\sl try}-Konstrukts dienen dazu, spezielle Ausnahmen, hier {\sl exc1} und {\sl exc2}, zu behandeln. F"ur die jeweilige Ausnahme wird die genannte Operation ausgef"uhrt. Der mit der Ausnahme erzeugte Wert kann hierbei verwendet werden. Ausnahmen, die in keinem Zweig auftreten, werden vom {\sl else}-Zweig behandelt. 

Falls kein solcher existiert, wird die Ausnahme weiter propagiert, bis sie auf ein passendes {\sl try}-Konstrukt trifft oder der Top-Level erreicht ist. In diesem Fall wird die Ausnahme nach au"sen hin sichtbar.


\section{Persistenz}

Es gibt in der Sprache \PQ\ zwei Ans"atze, um Daten persistent zu machen.
\begin{description} 
\item [Dynamische Datentypen] Das Modul {\em Dynamic} bietet Funktionen an, mit denen Daten samt ihrer Typ\-in\-for\-ma\-tion auf Dateien geschrieben werden k"onnen.
\item [Objektspeicher] Beim "Ubergang von \Q\ zu \PQ\ wurde das System um das Konzept eines Objektspeicher erweitert, der es erm"oglicht, Daten vollst"andig transparent persistent zu speichern.
\end{description}
 
\subsection{Dynamische Datentypen}

Die \PQ\ Standardbibliothek enth"alt ein Modul names {\em Dynamic}, das 
den abstrakten Datentyp {\sl dynamic.T} sowie eine Menge von Funktionen auf
diesem Datentyp zur Verf"ugung stellt. Der Typ {\sl dynamic.T} und die dazugeh"origen
Operationen k"onnen dazu verwendet werden, Daten ohne Verlust von 
Typinformation persistent zu speichern.

Der Typ {\sl dynamic.T} kann als ein Tupel interpretiert werden, bei dem in
der ersten Komponente der Typ eines Datums und in der zweiten der Wert
gespeichert wird. Nachfolgendes Beispiel demonstriert, wie Daten in eine
externe Datei exportiert werden k"onnen. (Die Funktionen der Module
{\sl writer} und {\sl reader} werden dabei zum Erzeugen bzw. "Offnen einer Datei ben"otigt.)
\begin{xple}
     \k{let} wr = writer.file(''Test.qst'') 
     \k{let} dyn = dynamic.new(:\k{Int} 3) 
     dynamic.extern(wr dyn dynamic.portable) 
     writer.close(wr)
\end{xple}
Der Parameter {\sl dynamic.portable} legt die Formatierung der exportierten Daten fest.

In einer nachfolgenden Sitzung kann dieses Datum wie folgt in die 
interaktive Umgebung importiert und dort verwendet werden.
\begin{xple}
     \k{let} addone(x :\k{Int}) = x + 1 
     \k{let} rd = reader.file(''Test.qst'') 
     \k{let} dyn = dynamic.intern(rd dynamic.portable) 
     reader.close(rd) 
     addone(dynamic.be(:\k{Int} dyn))
\end{xple}
"Uber die Funktion {\sl dynamic.be} wird eine Typ"uberpr"ufung initiiert.
Stimmt der Typ, der der Funktion {\sl dynamic.be} als erster Parameter "ubergeben wird,
nicht mit dem in dem Bezeichner {\sl rd} gespeicherten Typ "uberein, kommt
es zu einem Laufzeitfehler. Im anderen Fall wird der Wert des Bezeichners 
{\sl dyn} an den Aufrufer "ubergeben\footnote{Diese Typ"uberpr"ufung findet in
\PQ\ (Version 14) nicht statt.}.

Dar"uberhinaus k"onnen diese Funktionen auch dazu benutzt werden,
"ubersetzte Funktionen oder \PQ\/-Programme persistent zu speichern, was 
im nachfolgenden Beispiel demonstriert wird.
\begin{xple}
     \k{let} wr = writer.file(''sqr.qst'') 
     \k{let} hello() :\k{Ok} = print(''Hello world'') 
     dynamic.extern(wr dynamic.new(:\k{All}() :\k{Ok} hello) dynamic.portable) 
     writer.close(wr)
\end{xple}

\subsection{Der Objektspeicher von \PQ}

In \PQ\ gibt es keine Unterscheidung zwischen persistenten und tempor"aren Daten. Jedes Objekt kann persistent gemacht werde. Das Kriterium f"ur die Persistenz ist die Erreichbarkeit vom Hauptprogramm aus. Bei diesem Hauptprogramm handelt es sich  meistens um die interaktive Compilerumgebung (Es sind jedoch auch Applikationsprogramme m"oglich.). Wenn das Hauptprogramm die Compilerumgebung ist, k"onnen alle benannten Top-Level-Objekte und alle von diesen aus (auch transitiv) erreichbaren Objekte persistent gemacht werden. M"ogliche Top-Level-Objekte sind Werte, Typen, Kinds, aber auch ganze Schnittstellen und Module. 

Um diese Objekte persistent zu machen, mu"s eine explizite Stabilisierung des Objektspeichers durchgef"uhrt werden. Die Vorgehensweise beim Anlegen und Stabilisieren eines persistenten Speichers wird im folgenden beschrieben. 

\subsubsection{Das Anlegen eines persistenten Speichers}

Jeder Benutzer legt zun"achst seinen privaten persistenten Speicher an. Dies geschieht "uber den Befehl {\sl PQFormat}, dem die gew"unschte Gr"o"se des Speichers als Parameter "ubergeben wird. Auf weitere Parameter und die genaue Funktionsweise des Befehls wird hier nicht eingegangen. 

Nach dem Anlegen eines privaten, persistenten Speichers mu"s dieser durch den Befehl
\begin{xple}
     PQInit
\end{xple}
initialisiert werden. Dieser Befehl l"adt eine Reihe von vordefinierten \PQ\/-Objekten (wie z.B. die eingebauten Ausnahmen) in den persistenten Speicher.

Durch den Befehl
\begin{xple}
     PQuest.NewQuest.qm
\end{xple}
wird das interaktive \PQ\/-System in den persistenten Speicher geladen. Au"serdem werden alle in der Datei {\sl Library.qst} aufgef"uhrten Schnittstellen und Module importiert.

Man befindet sich nach Ausf"uhrung der obigen Befehle in der interaktiven \PQ\/-Umgebung. Der Zustand des persistenten Speichers kann jetzt durch die folgenden Befehle\footnote{Die Befehle werden weiter unten genauer erl"autert.}
persistent gemacht werden.
\begin{xple}
     \k{import} store
     store.stabilise()
\end{xple}

Diese Schritte m"ussen nur beim Anlegen, also nur einmal f"ur jeden persistenten Speicher durchgef"uhrt werden. 

\subsubsection{Persistente Speicher f"ur Applikationen}

Wie oben bereits erw"ahnt, kann man nicht nur f"ur die interaktive Compiler-Um\-ge\-bung, sondern auch f"ur andere Programme einen persistenten Speicher anlegen. Dazu mu"s das gew"un\-schte Programm (in Form einer parameterlosen Funktion mit R"uckgabewert vom Typ {\sl Ok}) zun"achst explizit in eine Datei geschrieben werden. Das Modul {\sl Dynamic} bietet daf"ur einen speziellen Befehl {\sl bootFile} an. 

Die Ausf"uhrung der Befehle
\begin{xple} 
     dynamic.bootFile(prog ''prog.qm'' dynamic.portable)
\end{xple}
schreibt ein Programm {\sl prog} in eine Datei {\sl prog.qm}\footnote{Die "ubergebene Funktion wird dabei so modifiziert, da"s sie mit einer Ausnahme endet. Dies ist aus internen Gr"unden erforderlich.}.

Das Programm kann dann durch den Befehl 
\begin{xple}
     PQuest . prog.qm
\end{xple}
in seinem persistenten Speicher ausgef"uhrt werden.


 \subsubsection{Stabilisieren des Speichers und Setzen von Sicherungspunkten}

Die Persistenz beruht wie oben bereits erl"autert, auf der Erreichbarkeit von Objekten vom Hauptprogramm aus. Um solche Werte, Typen, Kinds usw. persistent zu machen, mu"s der Speicher explizit {\sl stabilisiert} werden.
Dazu stehen zwei Befehle des Standardmoduls {\sl store} zur Verf"ugung.
\begin{xple}
     store.stabilise()
\end{xple}
stabilisiert den Speicherinhalt und
\begin{xple}
     store.halt()
\end{xple}
stabilisiert den Speicherinhalt und beendet sofort die Programmausf"uhrung.

Die Befehle k"onnen auch dazu benutzt werden, um in Programmen Sicherungspunkte (checkpoints) anzulegen.  Sie bewirken, da"s die vom Programm aus zum Zeitpunkt des Aufrufs erreichbaren Objekte persistent gemacht werden. Wenn das \PQ\/-System durch Control-D verlassen wird oder es zu einem Absturz des Systems kommt, werden alle "Anderungen, die seit dem letzten Stabilisieren an Objekten des persistenten Speicher durchgef"uhrt worden sind, r"uckg"angig gemacht. 

Der Aufruf des System durch den Befehl {\sl PQuestRecover} bewirkt dann eine Wiederaufnahme der Ausf"uhrung des Programms beim n"achstem Befehl hinter dem letztem {\sl store.stabilise} bzw. {\sl store.halt}.
Bei einen Aufruf von {\sl PQuest} wird das Hauptprogramm neu gestartet.

\subsubsection{Ein Beispiel}

Das folgende Beispiel soll zur Veranschaulichung der vorgestellten Konzepte dienen.
\begin{xple}
     \k{import}
        list :List
        print :Print
        fmt :Fmt
        store :Store
        dynamic :Dynamic
   
     \k{let} db = \k{tuple} \k{let} \k{var} l = list.new(:\k{Int}) \k{end}

     \k{let} printList(l :list.T(\k{Int})) :\k{Ok} =
        print.iter(list.elements(l) fmt.int)
  
     \k{let} listProg() :\k{Ok} =
        \k{begin}
           db.l := list.cons(1 db.l)
           db.l := list.cons(2 db.l)
           db.l := list.cons(3 db.l)
           printList(db.l)
           store.halt() 
           db.l := list.cons(4 db.l)
           printList(db.l)
        \k{end}
\end{xple}

Die Variable {\sl db} wird an eine modifizierbare Liste gebunden. Die Funktion {\sl listProg} f"ugt drei Elemente in diese Liste ein, f"uhrt ein {\sl store.halt} aus und f"ugt danach noch ein Element in die Liste ein. Vor dem Aufruf von {\sl store.halt} und am Ende der Funktion wird der aktuelle Inhalt der Liste durch einen Aufruf der Funktion {\sl printList} ausgegeben. 

Der folgende Aufruf schreibt das Programm {\sl prog}, wie oben bereits erl"autert, in die Datei {\sl prog.qm}.
\begin{xple}
     dynamic.bootFile(listProg ''prog.qm'' dynamic.portable)
\end{xple}

Ein Start des Programms {\sl prog} durch den Befehl {\sl PQuest .\ prog.qm} f"uhrt zur Ausgabe der Listenelemente: 
\begin{xple}
     [3, 2, 1]Exception:
\end{xple}
Der Aufruf von {\sl store.halt} im Programm macht den aktuellen Inhalt der Liste zum Zeitpunkt des Aufrufs persistent und f"uhrt zur Beendigung des Programms (deshalb die Ausnahme).

Eine Wiederaufnahme des Programms durch den Befehl {\sl PQuestRecover} liefert das Ergebnis:
\begin{xple}
     [4, 3, 2, 1]..ok : Ok
\end{xple}

Das {\sl ok :Ok} zeigt, da"s das Progamm bis zum Ende durchgelaufen ist. Das Element 4 ist neu in die Liste eingef"ugt worden, w"ahrend die Elemente 1, 2 und 3 noch vom vorherigen Programmlauf in der Struktur enthalten sind. Der Aufruf  von {\sl store.halt} hat sie, wie bereits erw"ahnt, persistent gemacht.

Wenn man das Programm stattdessen durch den Befehl {\sl PQuest} wieder startet, erh"alt man das Ergebnis:
\begin{xple}
     [3, 2, 1, 3, 2, 1]Exception:
\end{xple} 

Da das Programm wieder von vorne gestartet wird, werden noch einmal die gleichen Elemente in die Liste eingef"ugt. Wie im vorigen Fall sieht man auch hier, da"s die Elemente des ersten Programmlaufs noch vorhanden sind. 

\subsubsection{L"oschen durch {\sl Garbage Collection}} 

Es existiert keine Operation f"ur das explizite L"oschen von Objekten aus dem persistenten Speicher. Stattdessen gibt es eine Funktion, die alle Objekte ermittelt, die nicht mehr erreichbar sind, und den von ihnen belegten Speicherplatz wieder freigibt ({\sl Garbage Collection})
 
Dieser Vorgang kann zum einen zu jedem Zeitpunkt vom Benutzer durch einen expliziten Aufruf folgender Funktion initialisiert werden.   
\begin{xple}
     store.garbageCollect()
\end{xple}
Au"serdem wird der Vorgang automatisch gestartet, wenn es zu einem "Uberlauf des persistenten Speichers kommt. 
