Partielle Auswertung einer imperativen Sprache


[Inhalt]Inhaltsverzeichnis [-]2 Programmspezialisierung [+]4 Offene Fragestellungen

3 Partielle Auswertung und Compilierung


3.1 Futamura-Projektionen

Futamura erkannte als erster Forscher, daß mit Hilfe der Selbstanwendung partieller Auswertung grundsätzlich Compiler generiert werden können. Daher werden die Gleichungen, die Compilierung, Compiler und Compilergenerierung beschreiben, Futamura-Projektionen genannt:

1. Futamura-Projektion (Compilierung):target=||mix||L [int, source program]
2. Futamura-Projektion (Compiler):compiler=||mix||L [mix, int]
3. Futamura-Projektion (Compilergenerator):cogen=||mix||L [mix, mix]

Obwohl die Gleichungen einfach zu überprüfen sind, ist ihre intuitive Bedeutung ungleich schwerer nachzuvollziehen. Daher soll anhand eines konkreten Beispiels gezeigt werden, daß, als Folge der 1. Futamura-Projektion, ein partieller Auswerter zum Compilieren verwendet werden kann, wenn ein Interpreter und ein Quellprogramm gegeben sind.

Zunächst wird der Begriff des Interpreters genauer definiert und ein konkreter Interpreter angegeben. Anschließend wird die 1. Futamura-Projektion verifiziert.

In [1] wird darüber hinaus die Generierung eines Compilers als Folge der Anwendung der 2. Futamura-Projektion dargestellt.

[Top]

3.2 Ein Interpreter für Turingmaschinenprogramme

Ein Interpreter für eine Quellsprache S, der selbst in der Sprache L implementiert ist, hat zwei Eingaben: ein auszuführendes Quellprogramm p aus der Menge der S-Programme und die Eingabedaten d aus der Datenmenge D. Die Ausführung des Interpreters mit den Eingaben p und d auf einer L-Maschine muß die gleichen Ergebnisse liefern wie die Ausführung des Programms p mit Eingabe d auf einer S-Maschine:

||p||S d = ||int||L [p,d]

Als konkreter Interpreter soll nun ein Interpreter für eine Turing-Maschine vorgestellt werden. Ein Turing-Programm Q ist eine Liste (I0, I1, ... In) von Instruktionen der Form

right, left, write a, goto i oder if a goto i

Ein Berechnungszustand besteht aus der aktuellen Instruktion I, die als nächstes auszuführen ist, und einem unendlichen Band mit Zellen ai: ... a-2 a-1 a0 a1 a2 ... Das Bandalphabet A ist gegeben durch A = { 0, 1, B }, wobei B für 'blank' (Leerzeichen) steht. Nur eine endliche Anzahl von Zellen enthalten Symbole ai ungleich B; a0 wird aktuelle Position genannt. Die Instruktionen haben nachfolgend beschriebene Wirkungen:

Ein Beispielprogramm Q in der Turing-Sprache lautet:

  0: if 0 goto 3
1: right
2: goto 0
3: write 1

Die Eingabe für dieses Programm ist a0a1...an Î { 0, 1 }*. In allen anderen Zellen enthält das Band zu Beginn ein B. Die Programmausgabe ist der Wert der Zellen a0a1... (bis zur letzten Zelle ungleich B) und wird erzeugt, wenn keine weitere Instruktion mehr auszuführen ist. Die Bandposition kann sich dabei von der am Anfang unterscheiden.

Das Beispielprogramm findet die erste 0 rechts von der Anfangsposition auf dem Eingangsband und wandelt sie in eine 1 um. Falls keine 0 gefunden wird, läuft es in einer Endlosschleife. Bei 110101 als Eingabe für Q, wird die Ausgabe 1101 erzeugt. Das ergibt sich daraus, daß die Position, an der die in eine 1 umgewandelte 0 gefunden wurde, nun die aktuelle Position a0 ist. Das Band enthält (a-2a-1a0a1a2a3) = (111101).

Der Quellcode des Turing-Interpreters in der Flußdiagrammsprache lautet:

 

    Read (Q, Right);
    init:     Qtail := Q;
              Left := ‘();
loop: if Qtail = ‘() goto stop else cont; cont: Instruction := first_instruction(Qtail);   Qtail := rest(Qtail);   Operator := hd(tl(Instruction));   if Operator = ‘right goto do-right else cont1; cont1: if Operator = ‘left goto do-left else cont2; cont2: if Operator = ‘write goto do-write else cont3; cont3: if Operator = ‘goto goto do-goto else cont4; cont4: if Operator = ‘if goto do-if else error;
do-right: Left := cons(firstsym(Right), Left);   Right := tl(Right);   goto loop; do-left: Right := cons(firstsym(Left), Right);   Left := tl(Left);   goto loop; do-write: Symbol := hd(tl(tl(Instruction)));   Right := cons(Symbol,tl(Right));   goto loop; do-goto: NextLabel := hd(tl(tl(Instruction)));   Qtail := new_tail(NextLabel, Q);   goto loop; do-if: Symbol := hd(tl(tl(Instruction)));   NextLabel := hd(tl(tl(tl(tl(Instruction)))));   if Symbol = firstsym(Right) goto jump else loop;
jump: Qtail := new_tail(NextLabel,Q);
error: return(‘syntax-error: Instruction);
stop: return Right;

Das gesamte zu interpretierende Programm wird in der Variablen Q gespeichert. Ein Programmkontrollpunkt wird durch ein Suffix Qtail von Q repräsentiert, entspricht also der Liste der noch auszuführenden Instruktionen. Das Band wird durch die Variablen Left und Right mit Werten aus A* repräsentiert, wobei Right a0a1a2... (bis zur ersten Zelle ungleich B) und Left a-1a-2a-3... entspricht. Zu beachten istt, daß für Left die Reihenfolge umgekehrt wurde.

Der Interpreter verwendet einige spezielle Basisfunktionen:

  new_tail bekommt als Argumente einen Label lab und das Programm Q und gibt den Teil (Suffix) des Programms zurück, der mit Label lab beginnt.
  first_instruction gibt die erste Instruktion aus einer Instruktionenfolge zurück.
  rest gibt alles bis auf die erste Instruktion aus einer Instruktionenfolge zurück.
  firstsym ist eine spezielle Version von hd, für die firstsym() = B gilt. Es wird tl() = ( ) angenommen.

Für das Beispielprogramm gilt Q = (0: if 0 goto 3 1: right 2: goto 0 3: write 1). Einige typische Werte für diese Hilfsfunktionen sind dann:

new_tail(2, Q)=(2: goto 0 3: write 1)
first_instruction(Q)=(0: if 0 goto 3)
rest(Q)=(1: right 2: goto 0 3: write 1)

Für jede ausgeführte Anweisung von Q muß der Turing-Interpreter zwischen 15 und 28 Operationen ausführen, wobei eine Operation für jede Zuweisung, jedes goto und jeden Aufruf einer Basisfunktion gezählt wird.

[Top]

3.3 Compilierung durch die erste Futamura-Projektion

Die Gültigkeit der ersten Futamura-Projektion, die besagt, daß die Spezialisierung eines Interpreters in Bezug auf ein Quellprogramm den Effekt der Compilierung hat, kann leicht formal bewiesen werden:

Sei int ein S-Interpreter geschrieben in L, sei s ein S-Programm und d seine Eingabedaten, dann gilt:

  ||s||S d = ||int||L [s, d]
  nach Definition des Interpreters
   = ||(||mix||L [int, s] )||L d   nach der mix Gleichung
   = ||target||L d   nach Benennung des residualen Programms als target

Die Gleichungen sagen nichts über die Qualität des Zielprogramms aus, aber in der Praxis kann sie recht hoch sein.

Die erste Aufgabe auf dem Weg zur Spezialisierung des Turing-Interpreters in Bezug auf das Beispielprogramm ist es, eine Einteilung der Variablen des Interpreters unter der Annahme zu ermitteln, daß das zu interpretierende Programm Q statisch und sein anfängliches Eingabeband (Right) dynamisch ist. Relativ leicht ist zu sehen, daß dann folgende Variablen statisch sind: Q, Qtail, Instruction, Operator, Symbol, NextLabel. Dagegen sind Right und Left dynamisch. Diese Information wird dem Programmspezialisierer zusammen mit dem Text des Interpreters und dem Quellprogramm eingegeben.

Als Endergebnis ergibt sich aus dem obigen Interpreter und dem Quellprogramm s =(0: if 0 goto 3 1: right 2: goto 0 3: write 1) folgendes Zielprogramm:

 

    read (Right);
    lab0: Left := '();
          if '0 = firstsym (Right) goto lab2 else lab1;   
    lab1: Left := cons (firstsym (Right), Left);
          Right := tl (Right);
          if '0 = firstsym (Right) goto lab2 else lab1;
    lab2: Right := cons ('1, tl (Right));
          return (Right);
  

Alle Zuweisungen X := exp und alle Tests if exp ..., bei denen X statisch ist, werden eliminiert, da sie zur Programmspezialisierungszeit ausgeführt werden. Die Label lab0, lab1 und lab2 sind Aliasnamen für spezialisierte Programmpunkte (pp, vs), wobei pp ein Interpreter-Label ist und vs die Werte der statischen Interpreter-Variablen enthält.

In der nachfolgenden Tabelle wird die Zuordnung der Label im Zielprogramm zu spezialisierten Programmpunkten aufgelistet. Da die Variable Q an jedem Programmpunkt das gesamte Turing-Programm als Wert enthält, wurde sie weggelassen. Die Variable Operator wurde aus Platzgründen weggelassen. Mit ( ) sind die Werte der nicht initialisierten Variablen bezeichnet.

Ziel-
Label
Interpreter-
Label
Statische Interpreter-Variablen (vs)
Instruction Qtail Symbol NextLabel
lab0 init ( ) ( ) ( ) ( )
lab1 cont right (2: goto 0 3: write 1) 0 3
lab2 jump if 0 goto 3 (1: right 2: goto 0 3: write 1) 0 3

Aus den Gleichungen der Futamura-Projektion folgt direkt, daß das Zielprogramm in derselben Sprache wie der Interpreter geschrieben ist. Die Struktur des Zielprogramms erinnert jedoch mehr an das Quellprogramm, von dem es abgeleitet wurde, als an die des Interpreters. Das Zielprogramm ist aus Teilen des Interpreters zusammengesetzt, z.B. Left := cons (firstsym(Right), Left), wobei einige Teile in Bezug auf Daten des Quellprogramms spezialisiert sind, z.B. if ‘0 = firstsym(Right) goto lab2 else lab1. Das ist typisch für Zielprogramme, die mit dem Programmspezialisierer mix erzeugt wurden.

Eine Laufzeitanalyse des Zielprogramms ergibt, daß die Hauptschleife im Zielprogramm 8 Operationen erfordert, während der Interpreter dafür 61 Operationen benötigt. Das Zielprogramm läuft also fast 8 mal schneller als der Interpreter.

[Top] [+]4 Offene Fragestellungen


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