partielle Auswertung durch Fold/Unfold

11. Partielle Auswertung durch Fold/Unfold

Partielle Auswertung, kann auf funktionalen Sprachen z.B. durch eine Automatisierung der Fold/Unfold-Methode realisiert werden. Hier sollen Programme spezialisiert werden. Dies wird durch eine anfängliche Zielregel verwirklicht, in der einige Variablen zu Konstanten gemacht werden, z.B. f₅x y -> f 5 x y.
Um das spezialisierte Programm zu erzeugen, wird die Programmberechnung simuliert. Für unbekannte Werte werden Variablen benutzt. Reichen Variablen nicht aus, um die Berechnung fortzuführen, werden sie instantiiert. Es wird, wenn möglich, entfaltet, um möglichst viele Programmberechnungen auszuführen, die dann nicht mehr während der Laufzeit durchgeführt werden müssen. Reicht die Information nicht aus, um zu entfalten, wird eine neue Regel erzeugt.
Der vorgestellte Algorithmus verwendet zwei Mengen Pending und Out. Pending enthält dabei noch nicht verarbeitete Regeln (zu Anfang enthält Pending die Zielregel) und Out enthält die Regeln des Zielprogramms.
Es folgt ein Algorithmus zur partiellen Auswertung auf funktionalen Sprachen.

Hauptprogramm :

Definition von T
T [|x|] = x
T [|c t₁...t_n |] = c [|t₁|]...T[|t_n|]
T[| f t₁...t_n |] =

let u₁= T [|t₁|],..., u_n = T[|t_n|] in

let

else

result is

Definition von Make_new
Make_new(f t₁...t_n ) =

where

s_i = if t_i is ground then t_i else x_i

g is a new function name, depending only on f and the ground s_i's

{i₁,...i_m} = { i | t_i is non ground }

T wertet einen Funktionsaufruf so weit wie möglich aus. Reicht die Information nicht aus, um vollständig auszuwerten, wird eine neue Funktion erzeugt. Die Funktion Make_new erzeugt eine neue Funktion ohne konstante Argumente.

Beispiel : Spezialisierung der Ackermannfunktion :

Spezialisiere ack m n auf einen festen Wert von 2 für m
Startregel : ack₂ n -> ack 2 n
Originalprogramm :

      ack 0   n	  -> n+1
      ack m+1 0   -> ack m 1
      ack m+1 n+1 -> ack m (ack m+1 n)

Anwendung des obigen Algorithmus ergibt :

Pending	= { a₂x -> ack 2 x}	(Anfang)
Out	= {a₂0 -> 3}	(mache x zu , werte komplett aus)
Pending	= {a₁ y -> ack 1 y ,...}	(mache x zu n+1, füge Fkt. a₁ hinzu)
Out	= {a₂n+1 -> a1 (a₂ n),...}	( rufe neue Funktion auf)
Out	= {a₁0 ->; 2 ,...}	(mache x zu 0, werte komplett aus)
Out	= {a₁n+1 -> (a₁ n) +1,...}	(durch a₁n+1 -> ack 0(ack 1 n ) )

Man kann so sehen, daß man partielle Auswertung durch die Fold/Unfold Methode realisieren kann. Bei dem vorgestellten Algorithmus treten keine Terminierungsverluste auf. Jedoch kann die Terminierung zunehmen, da entfaltet wird, wenn dies bei der 'Call by Value' - Semantik nicht der Fall sein würde. Weiterhin können in diesem Algorithmus Teilberechnungen wiederholt werden.

Weiteres Beispiel :
Spezialisierung des folgenden Programms auf n=5 :

       power 0 x   -> 1
       power n+1 x -> x*power n x

Durch den Algorithmus werden keine weiteren Regeln (außer natürlich der Startregel) zu Pending hinzugefügt. Das neue Programm besteht nur aus einer Regel, die durch Berechnung von power₅x -> T[| x * power 4 x |] entstanden ist.
Das neue Programm lautet :
power₅x -> x * x * x * x * x * 1

Und noch ein Beispiel :
In den folgenden Ausführungen wurden einige Konstruktoren weggelassen. Dadurch sind die beschriebenen Programme zwar nicht ganz korrekt, jedoch besser zu lesen.
Originalprogramm :
append NIL Y -> Y
append zX Y -> z append(X Y)

Eine mögliche Spezialisierung ist :
append_abcY -> append abc Y

Das entstehende Programm lautet :
append_abc Y -> abcY ,
da der Term T[|append abc Y|] vollständig berechnet werden kann.
In diesem Beispiel ist sehr gut zu sehen, daß eine Spezialisierung von Y in diesem Programm nichts bringt, da der Programmablauf nur von X beeinflußt wird.
Versucht man trotzdem Y einzufrieren, sieht das Ergebnis wie folgt aus :
Spezialisierungsregel : append_abcX -> append X abc
Durch entsprechende Instantiierungen von X werden beide Programmregeln verarbeitet. Der Algorithmus erzeugt das folgende Programm :
append_abcNIL -> abc
append_abczX -> z append_abc X

Das Programm hat die gleiche Laufzeit wie das Original. Eine Änderung des Originalprogramms in

 
   append X NIL -> X
   append X Yz -> append(X Y) z

würde bei einer Spezialisierung von X nur konstante Laufzeit haben.

Es ist auch möglich, daß die Spezialisierungsregel auf der rechten Seite eine Verkettung von Funktionen des Originalprogramms enthält. Wichtig ist hierbei nur, daß mindestens eine Variable zu einer Konstanten wird. Betrachte z.B. die Startregel :
app2_abc X -> append( abc (append X fgh))

Durch die Parameterauswertung der äußeren Funktion wird der Term (append X abc) ausgewertet. Dabei wird ein Programmteil erzeugt, der der Spezialisierung auf Y im vorigen Beispiel gleicht. Bei der Auswertung der äußeren Funktion kann wieder vollständig ausgewertet werden, wobei wieder das abc vorangestellt wird.