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 :

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
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.