2. Aufgaben der partiellen Auswertung
Alle Berechnungen, die nur von in1 abhängen, werden ausgeführt. Für Berechnungen, die von in2 abhängen, wird entsprechender Code erzeugt. Es wird also eine Mischung von Programmausführung und Codeerzeugung durchgeführt. Daher stammt auch der Name mix.
Die angewendeten Haupttechniken sind :
- symbolische Berechnung
- Entfalten von Funktionsaufrufen
- Programmpunktspezialisierung.
Programmpunktspezialisierung:
Wird eine Funktion von einem Programm mehrmals aufgerufen, ist es manchmal sinnvoll, für jeden (oder zumindest einige) Aufrufe eine spezialisierte Version der Funktion zu erzeugen, die schneller ist als das Original.
Zur weiteren Betrachtung wird eine Semantikfunktion [|.|] definiert :
output:=[|p|]L[in1,...,inn]
output ist dann die Ausgabe, wenn man p auf den Eingaben in1,...,inn ausführt.
Bei der 'normalen' Programmausführung gilt :
out = [|p|] [in1,in2]
Dieses wird auch als 'Berechnung erster Stufe' bezeichnet.
Berechnungen zweiter Stufe benutzen den partiellen Auswerter mix. Sie funktionieren, wie der Name schon sagt, in zwei Stufen
- erste Stufe :
pin1 = [|mix|] [p,in1]
- zweite Stufe :
out = [| pin1 |] in2
Die erste Stufe entspricht der Erzeugung der spezialisierten Programmversion. Die zweite Stufe stellt die Ausführung dieser spezialisierten Version auf der restlichen Eingabe dar. Da die beiden Ausgaben gleich sind, erhält man :
[|p|] [in1,in2] = [| [|mix|] [p,in1] |] in2 .
Es ist auch möglich, daß Eingabe-, Ausgabe- und Implementationssprache verschieden sind. Dann würde in den obigen Gleichungen die Semantikfunktion jeweils mit der entsprechenden Sprache gekennzeichnet werden.
Ein weiteres Beispiel :
Spezialisierung einer Funktion zur Berechnung des Binomialkoeffizienten
Original - Modula-2 - Programmfunktion :
PROCEDURE Binom( n,k : LONGINT ) : TBruch;
VAR Zaehler,Nenner,i : LONGINT;
BEGIN
IF n < k THEN
RETURN Bruch.Create(0L,1L);
ELSE
IF k=0L THEN
RETURN Bruch.Create(1L,1L);
ELSE
Zaehler:=n;
Nenner:=k;
FOR i:=1L TO k-1L DO
Zaehler:=Zaehler*(n-i);
Nenner := Nenner*i;
END;
END;
RETURN Bruch.Create(Zaehler,Nenner);
END;
END Binom;
Durch eine Spezialisierung dieser Prozedur auf k=5, erhält man eine neue Prozedur Bin5, die nur noch von n abhängt. Da die Programmausführung durch k gesteuert wird (i.e. die FOR-Schleife), ist hier eine gute Geschwindigkeitsverbesserung zu erwarten. Durch Auswertung der Berechnungen, die von k abhängen erhält man so die folgende, spezialisierte Version:
PROCEDURE Bin5( n : LONGINT) : TBruch;
VAR Zaehler,Nenner : LONGINT;
BEGIN
IF n < 5 THEN
RETURN Bruch.Create(0L,1L);
ELSE
Zaehler := n*(n-1L)*(n-2L)*(n-3L)*(n-4L);
Nenner := 60L; (* 5*1*2*3*4 *)
RETURN Bruch.Create(Zaehler,Nenner);
END;
END Bin5;
Hier sieht man, daß aus einem Programm, das vorher eine lineare Laufzeit hatte, ein Programm entstanden ist, welches eine konstante Laufzeit aufweist. Überdies ist diese Version kürzer, da einige Programmabzweigungen im Original auch nur von k abhingen.