Partielle Auswertung einer imperativen Sprache

Inhaltsverzeichnis

3 Partielle Auswertung und Compilierung

5 Zusammenfassung und Ausblick

4 Offene Fragestellungen

• 4.1 Terminierung
• 4.2 Endlichkeit der Menge der spezialisierten Programmpunkte
• 4.3 Online/Offline-Strategien

Probleme bei der partiellen Auswertung im Hinblick auf die Terminierungseigenschaften sind bei den bisherigen Ausführungen zumeist nur am Rande erwähnt und ansonsten ignoriert worden, da das Ziel die Vermittlung von Programmierkonzepten war. Eine formalere Darstellung hätte das Verständnis der Basisalgorithmen erschwert. Es wurde nur sichergestellt, daß die behandelten Programme häufig genug terminieren. In Kapitel 14 von [1] werden die Probleme und Lösungen bezüglich der Terminierung ausführlich diskutiert.

Wie in Abschnitt 2.7 an einem Beispiel gezeigt, ist es keine triviale Aufgabe, die Endlichkeit von poly zu garantieren. Bei genauerer Untersuchung zeigt sich, daß das Problem, eine genügende Anzahl von Variablen als dynamisch zu klassifizieren ohne zu einer unnötig großen Anzahl zu gelangen, nicht berechenbar ist. Diese Problemstellung wird ebenfalls in Kapitel 14 von [1] behandelt.

Die partielle Auswertung wurde als ein Prozeß beschrieben, der zwei (oder mehr) Stufen hat. Zuerst wird eine Einteilung B aus dem Programm und der anfänglichen Einteilung B' berechnet, ohne Gebrauch von den konkreten Werten der statischen Eingabevariablen zu machen. Danach findet die eigentliche Programmspezialisierung statt, wobei die statischen Variablen entsprechend der Einteilung ausgenutzt werden, nicht jedoch die konkreten, während der Spezialisierung berechneten Werte. Diese Vorgehensweise wird partielle Offline-Auswertung genannt. Wenn jedoch die konkreten Werte, die während der Programmspezialisierung berechnet werden, die ausgeführten Aktionen beeinflussen können, spricht man von partieller Online-Auswertung.

Fast alle Offline-Strategien, einschließlich der hier vorgestellten, stützen ihre Entscheidungen auf die Ergebnisse eines Vorprozesses, der Bindezeitanalyse.

Viele partielle Auswerter mischen Online- und Offline-Methoden, da beide Strategien ihre Vorteile haben. Der Hauptvorteil der partiellen Online-Auswertung ist, daß sie während der Spezialisierung manchmal mehr statische Informationen herausfinden kann. Daraus ergeben sich in der Regel bessere residuale Programme. Offline-Techniken dagegen machen die Generierung von Compilern usw. durch Selbstanwendung handhabbarer und führen durch die Verwendung einfacherer Spezialisierungsalgorithmen zu schnelleren Systemen.

Kapitel 7 von [1] enthält eine detaillierteren Vergleich von partieller Online- und Offline-Auswertung.

5 Zusammenfassung und Ausblick