Partielle Auswertung einer imperativen Sprache


[Inhalt]Inhaltsverzeichnis [+]2 Programmspezialisierung

1 Einleitung und Grundbegriffe


1.1 Historie

Die Partielle Auswertung oder Programmspezialisierung als Methode der Programmtransformation ist schon ein vergleichsweise altes Forschungsgebiet der Informatik. Bereits 1964 wurde eine Arbeit [4] veröffentlicht, in der vermutlich zum ersten Mal der Begriff partielle Auswertung verwendet wurde. Seit 1971 ist bekannt, daß die Partielle Auswertung eng mit der Compilierung verbunden ist. Insbesondere kann ein Programmspezialisierer zum Compilieren verwendet werden, wenn eine interpretative Definition einer Programmiersprache als Eingabe vorliegt. Ein Programmspezialisierer kann, falls er auf sich selbst anwendbar ist, sogar einen Compiler oder auch einen Compiler-Generator erzeugen.

Die meisten veröffentlichten Arbeiten stammen aus dem Bereich der funktionalen Sprachen, mit Schwerpunkt Lisp. Erstmals wurden in den späten 70er und frühen 80er Jahren Ideen [5] entwickelt, die Methoden der partiellen Auswertung auch auf imperative Sprachen anzuwenden. Da fast alle gängigen Maschinenarchitekturen auf dem von-Neumann-Konzept, das zu imperativen Maschinensprachen führt, aufbauen, partielle Auswertung für funktionale Sprachen jedoch wiederum zu funktionalem Code führt, ist die partielle Auswertung für imperative Sprachen für praktische Anwendungen besonders interessant.

[Top]

1.2 Partielle Auswertung

Die theoretische Grundlage für die partielle Auswertung bildet das aus der Berechenbarkeitstheorie bekannte s-m-n-Theorem, welches besagt, daß zu jeder partiell rekursiven Funktion g(x,y) eine total rekursive Funktion s(x) existiert, so daß fs(x)(y) = g(x,y) für alle (x,y) gilt.

In der mathematischen Logik findet sich eine gleichwertige Aussage: Jede Funktion von n Variablen läßt sich in eine äquivalente einstellige Funktion umwandeln. Das Ergebnis dieser neuen Funktion ist eine Funktion von (n-1) Variablen. Diese Umwandlung wird nach H.B. Curry auch Curryfizierung genannt.

Bei der partiellen Auswertung eines in einer Quellsprache L geschriebenen Programms p bezüglich bekannter Eingabedaten d1, d2, ... dn und unbekannter Eingabedaten u1, ... um versucht man durch teilweise Abarbeitung von p ein neues Programm p' zu konstruieren, so daß

p'(u1, ... um) = p(d1, ... dn, u1, ... um)

gilt. Alle Befehle, die aufgrund der Abhängigkeit von unbekannten Eingabedaten noch nicht ausgeführt werden können, werden zurückgestellt und erst in einer späteren Phase abgearbeitet. Das entstandene Programm p' heißt residuales Programm zu p. Ein Programm, das aus einem gegebenen Programm p zu bekannten Eingabedaten ein residuales Programm p' erzeugt, heißt partieller Auswerter oder Spezialisierer.

[Top]

1.3 Zielsetzung

Ziel des Kapitels aus [1], das dieser Ausarbeitung zugrunde liegt, ist es, an einem konkreten Beispiel zu zeigen, daß es möglich ist, mit relativ einfachen Techniken einen nicht-trivialen Programmspezialisierer für eine einfache imperative Sprache zu konstruieren.

Von anderen Arbeiten auf dem Gebiet der Programmtransformation unterscheidet sich der hier vorgestellte Ansatz durch drei grundlegende Forderungen:

  1. Die Methoden sollen vollautomatisch sein, ohne jegliche Notwendigkeit eines Benutzereingriffs während der Programmtransformation.
  2. Die Methoden müssen ausreichend mächtig sein, um zu compilieren, indem ein Interpreter in Bezug auf ein festes Quellprogramm spezialisiert wird.
  3. Es soll möglich sein, automatisch eigenständige Compiler zu erzeugen. Um dahin zu gelangen, muß der Spezialisierer auf sich selbst angewendet werden können.

Zunächst werden die wesentlichen Prinzipien der partiellen Auswertung, die weitgehend unabhängig von der speziellen Programmiersprache sind, eingeführt. Aufbauende Konzepte und Techniken werden nur bei Bedarf verwendet. Im Anschluß daran wird der Zusammenhang von partieller Auswertung und Compilierung dargestellt, der im wesentlichen auf den Ideen von Futamura, den sogenannten Futamura-Projektionen, beruht.

[Top]

1.4 Schreibweisen

Um Programmspezialisierung genauer definieren zu können, müssen die Effekte einer Programmausführung formal beschrieben werden. Wenn mit p ein Programm in Sprache L und mit d die Eingabedaten des Programms bezeichnet werden, so wird das Ergebnis einer Programmausführung mit

||p||L d = result

bezeichnet (falls das Programm terminiert). || × ||L bezeichnet man auch als Semantik-Funktion.

Da Programmspezialisierer sowohl Programme als auch Daten als Eingabe akzeptieren, müssen sowohl das Programm p als auch die Eingabedaten d aus einer gemeinsamen Menge D von Datenwerten stammen. Eine Notation, die es erlaubt, Programme wie Daten zu behandeln, ist die Listen-Notation von Lisp mit Hilfe von sogenannten S-Ausdrücken.

Wenn A die Menge der Atome und S die Menge der S-Ausdrücke ist, kann die Menge S wie folgt rekursiv definiert werden:

  1. A Ì S
  2. a, b Î S Þ (a . b) Î S
  3. andere S-Ausdrücke gibt es nicht

Für spezielle S-Ausdrücke benutzt man die Listenschreibweise:

  4. ( ) º nil
  5. s1, ... sn Î S Þ (s1 s2 ... sn) º (s1 . (s2 . ( ... (sn-1 . (sn . nil)) ... )))

Ein Konstruktor C mit Parametern p1, ... pn wird dann beispielsweise als (C p1 ... pn) dargestellt.

[Top]

1.5 Die Flußdiagrammsprache

Um die grundlegenden Prinzipien der partiellen Auswertung einzuführen, wird eine einfache imperative Sprache verwendet:

áProgramñ

::=

read áVarñ, ... áVarñ; áBasicBlockñ+

áBasicBlockñ

::=

áLabelñ: áAssignmentñ* áJumpñ

áAssignmentñ

::=

áVarñ := áExprñ ;

áJumpñ

::=
|
|
goto áLabelñ ;
if áExprñ goto áLabelñ else áLabelñ ;
return áExprñ ;

áExprñ

::=
|
|
áConstantñ
áVarñ
áOpñ áExprñ ... áExprñ

áConstantñ

::=

quote áValñ
(Abkürzend kann der konstante Ausdruck (quote value) auch als 'value geschrieben werden.)

áOpñ

::=

hd | tl | cons | ...
(und weitere für Interpreter und Programmspezialisierer benötigte)

áLabelñ

::=

Identifizierer oder Zahl

Im Vergleich zu einer echten Programmiersprache ist diese Sprache lächerlich klein, aber aus folgenden Gründen ist es dennoch sinnvoll, die partielle Auswertung an einer solchen Sprache zu untersuchen:

Konstanten sind Lisp-S-Ausdrücke und Operationen werden auf S-Ausdrücke angewendet. Der Programmspeicher ist eine Abbildung der Programmvariablen in ihre aktuellen Werte. Die Eingabe eines Programms p ist eine Werteliste d = (v1, ... vn), die zu Beginn an die Variablen var1, ... varn gebunden ist. Alle nicht eingegebenen Variablen varn+1 haben als Anfangswert die leere Liste ( ), so daß der Anfangszustand des Speichers eine endliche Funktion ist:

[var1 ® v1, ... varn ® vn, varn+1 ® ( ), ... varn+k ® ( )]

Die Basisfunktionen werden als frei von Seiteneffekten auf die Werte der Variablen angenommen. Zuweisungen, Bedingungen und goto's werden in der üblichen Weise ausgeführt und ein return-Ausdruck beendet die Ausführung, mit dem Wert des Ausdrucks als Ergebnis der Programmausführung ||p||L d.

Wegen der besseren Lesbarkeit werden Programme frei unter Verwendung Pascal-ähnlicher Konstrukte wie begin...end, while...do und repeat...until geschrieben, da diese Konstrukte problemlos mit Hilfe von Basisblöcken, Labels und if-Anweisungen dargestellt werden können.

[Top]

1.6 Residuale Programme und Programmspezialisierung

Im weiteren bezeichnet L die Flußdiagrammsprache. Wenn p ein L-Programm, das als Eingabe eine zwei-elementige Liste erwartet, und d1 ein Element der Datenmenge D ist, dann wird ein L-Programm r ein residuales Programm für p bezüglich d1 genannt, wenn die Gleichung

||p||L [d1, d2] = ||r||L d2

für alle d2 aus D erfüllt ist.

Die Gleichung drückt aus, daß die Ausführung von r mit Eingabe d2 das gleiche Resultat liefert wie die Ausführung von p mit der Eingabe d1 und d2. Die Eingabe d1 ist also in das residuale Programm r integriert worden. Ein L-Programm mix, das bei gegebenem p und d1 ein residuales Programm r so erzeugt, daß obige Gleichung gilt, wird als Programmspezialisierer bezeichnet. Kurz ausgedrückt muß die Gleichung

||p||L [d1, d2] = ||(||mix||L [p, d1])||L d2

für alle d2 aus D erfüllt sein.

Das Programm p wird Subjektprogramm genannt. Die rechte Seite der Gleichung beinhaltet zwei Programmausführungen: Zuerst wird ein residuales Programm r = ||mix||L [p, d1] erzeugt; dann wird das residuale Programm r auf den Daten d2 ausgeführt.

Die Gleichungen können dahingehend verallgemeinert werden, daß p eine feste Anzahl n von Eingabedaten erwartet, von denen m durch den Programmspezialisierer mix in das residuale Programm r integriert werden. Es gilt stets 0 £ m £ n. In obigen Gleichungen gilt n=2 und m=1.

An einem Beispiel soll die Wirkung der Gleichungen verdeutlicht werden. Sei also folgendes Programmfragment, das etwa innerhalb eines Interpreters auftreten könnte, der den Speicher eines interpretierten Programms mit Hilfe einer Namensliste namelist und einer parallelen Werteliste valuelist darstellt, gegeben:

  while name ¹ hd(namelist) do
begin
  valuelist := tl(valuelist);
  namelist := tl(namelist)
end;
value := hd(valuelist);

Die Eingabedaten für das Programmfragment sind die drei Variablen name, namelist und valuelist, d.h., n=3. Angenommen, dem Programmspezialisierer werden die Anfangswerte der Variablen name und namelist gegeben, z.B. name = z und namelist = (x y z), aber die Werteliste valuelist ist unbekannt, d.h., m=2. Da die Programmkontrolle vollständig durch name und namelist festgelegt ist, kann es symbolisch ausgeführt werden mit folgendem residualem Programm als Ergebnis:

  valuelist := tl(valuelist);
valuelist := tl(valuelist);
value := hd(valuelist);

Die while-Schleife ist verschwunden und das residuale Programmfragment enthält nur noch die Befehle des Subjektprogramms, deren Effekte nicht während der Programmspezialisierung berechnet werden können. Weiterhin taucht der Befehl

 

valuelist := tl(valuelist);

zweimal im residualen Programm auf, einmal für jede Iteration der Schleife, obwohl er im Subjektprogramm nur ein Mal vorkommt. Die zwei Iterationen rühren daher, daß zweimal tl von namelist zu bestimmen war, bevor hd gleich name war.

Da die Variable valuelist nach dem Programmfragment nicht mehr benötigt wird, wäre denkbar, das resultierende Programm zu

 

value := hd(tl(tl(valuelist)));

zu optimieren. Für die Programmspezialisierung sind solche Optimierungen jedoch nicht entscheidend und werden daher im folgenden außer acht gelassen.

In diesem Beispiel wird angenommen, daß der Programmspezialisierer residuale Programme erzeugt, die in der gleichen Sprache wie die Subjektprogramme geschrieben sind. Das vereinfacht natürlich das Verständnis der Transformationen, die mix ausführt. In der praktischen Anwendung braucht das nicht der Fall zu sein. Um maximale Effizienz zu erreichen, würden die residualen Programme stattdessen vielleicht in einer Maschinensprache erzeugt.

[Top] [+]2 Programmspezialisierung


Copyright © 1998 Ulrich Telle - Letzte Änderung: 1. Februar 1998