Prolog Zielexpansion

Jan Burse, erstellt 13. Okt 2011 Bevor wir mit der neuen 0.9.x Serie der Jekejeke Prolog Ausgaben gestartet sind führten wir Zielexpansion ein. Wir dachten uns das System sein unvollständig ohne Zielexpansion obwohl Zielexpansion nicht durch den ISO Kernstandard vorgeschrieben wird. Zielexpansion kann mittels dem Prolog Schalter clause_expand ein und ausgeschaltet werden. Der Expansionsmechanismus selbst ist in Prolog geschrieben. Falls Zielexpansion eingeschaltet ist wird die Dateikonsultierungsroutine zuerst einen Aufruf von expand_term/2 und somit auch von expand_goal/2 durchführen bevor sie ein Fakt oder eine Regel hinzufügt. Für Prologneulinge empfiehlt es sich die Zielexpansion als das C #define für Prolog vorzustellen. Aber da sind kleine Unterschiede. Der Prolog Zielexpansionsmechanismus kennt die Syntax der Sprache. Die Dateikonsultierungsroutine wird ihre Expansionsversuche nicht auf einer String basieren sondern auf dem schon geparsten Term. Die Prolog Zielexpansion verfügt über einige Gemeinsamkeiten mit der C Vorverarbeitung. Um eine Zielexpansion zu definieren muss der Endbenutzer nur einige goal_expand/2 Fakten oder Regeln einstöpseln. Über Patterns oder Bedingungen im Regelkörper kann der Endbenutzer bedingte Expansion bereitstellen. Falls ein goal_expand/2 Fakt oder eine Regel misslingt bleibt der Term unverändert. Das deckt einen Teil der C #ifdefine Funktionalität ab, jedoch auf eine mehr dynamischen Art und Weise. Wir können weitere Vergleiche des Zielexpansionsmechanismus mit Lisp-Makros anstellen. Lisp-Makros kennen auch die Syntax da sie auf den S-Ausdrücken aufbauen. Aber einige Problem mit dem Gültigkeitsbereich von Variablen haben zu Vorschlägen von sogenannten hygienischen Makros geführt. Der Prolog Zielexpansionsmechanismus auf der anderen Seite ist nicht so stark von Problemen mit dem Gültigkeitsbereich von Variablen betroffen. Dadurch dass goal_expand/2 Fakten und Regeln beim Aufruf automatisch neue Variablen bereitstellen, erhält man die Erzeugung von lokalen Variablen während des Umschreibens umsonst. Schliesslich weil keine Prädikate und Module lokal in einer Klausel eingeführt werden können, gibt es selten Verwirrung zu Prädikatnamen. Die Arbeitsweise der Zielexpansion soll durch ein kleines Beispiel illustriert werden. Das Beispiel soll einige Zahlen und deren Quadrat auflisten. Es wird dabei die Zahlen rechtsbündig formatieren. Zur Erleichterung haben wir unser eigenes forthem/2 Prädikat definiert. Dieses Prädikat erlaubt es uns einen Schleife auszuführen ohne Variablenbindungen zu hinterlassen. Als weitere Erleichterung haben wir das Prädikat printf/2 definiert. Es handelt sich dabei um eine sehr einfache Version die ein alleinstehendes Prozentzeichen (%) als Position für einen Ausdruck deuten kann der zu einer Nummer ausgerechnet werden soll. Wir können unser kleines Beispiel ausführen indem wir das Prädikat squares/0 aufrufen welches wie folgt definiert ist: squares :- forthem(between(1,10,X),printf(' % * % = %\n',[X,X,X*X])). Wir sind dann daran gegangen die Definitionen für forthem/2 und printf/2 durch Expansionsregeln zu ersetzen. Die Expansionsregel für forthem/2 ergibt sich sogleich. Keine Massnahmen für Hygiene sind notwendig. Die Expansion kann direkt mit Zielargumenten umgehen: goal_expansion(forthem(C,A), \+ (C, \+ A)). Die Expansion für printf/2 unterscheidet zwei Fälle. Wir gehen von der Annahme aus, dass beim Aufruf des Prädikats das zweite Argument zu einer Liste instanziiert ist. Der erste Fall trifft zu wenn das Argumentlist leer ist. Im generierten Code werden wir einen Schreibbefehl der Formatstring finden: goal_expansion(printf(S,[]), write(S)). Der zweite Fall trifft zu wenn die Argumentliste nicht leer ist. Die Regel wird dann die Formatstring untersuchen und das erste Argument aufbrauchen. Im generierten Code finden wir eine neue lokale Variable um das Ergebnis der Ausrechnung des Arguments festzuhalten. Die Regel wird eine weitere Expansion des Restes der Argumente an den Zielexpansionsmechanismus delegieren indem ein neuer printf/2 Aufruf im expandierten Ziel zu finden ist. Diese Delegation ist möglich da der Zielexpansionsmechanismus die Expansion wiederholt so lange es Änderungen gibt: goal_expansion(printf(S,[E|T]), (write(P), H is E, radjust(H), printf(Q,T))) :- sub_atom(S,B,_,A,'%'), sub_atom(S,0,B,_,P), sub_atom(S,_,A,0,Q). Wenn wir den Prolog Text konsultieren, der von der Zielexpansion Gebrauch macht, und wenn wir ein listing(squares/0) ausführen, werden wir das Ergebnis der Zielexpansion sehen: squares :- \+ (between(1, 10, X), \+ (write(' '), _B is X, radjust(_B), write(' * '), _C is X, radjust(_C), write(' = '), _D is X * X, radjust(_D), write('\n'))). In der Praxis würde man die Definitionen von forthem/2 und printf/2 nicht entfernen. Sie können als Rückhalt dienen wenn Ziele dynamisch hergestellt werden, die diese Prädikate enthalten. Man kann dann auch die Expansion unterbinden falls das zweite Argument von printf/2 eine Variable ist da der Code, der von diesem Aufrufmuster Gebrauch macht, Rückhalt in den entsprechenden Definitionen findet. Der Ansatz, den wir bisher verfolgt haben, suggeriert eine spezielle Sicht der Zielexpansion. Wir können Ihn als Mittel, um Prädikate teilweise zur Kompilierzeit auszurechen, deuten. Die goal_expansion/2 Fakten und Regeln definieren eine Strategie zur teilweisen Ausrechnung des vorliegenden Prädikats. Und die goal_expansion/2 Fakten und Regeln können systematisch entwickelt werden. Falls eine goal_expansion/2 Klausel einen Körper hat, so finden wir im Körper die Ziele die während der Kompilierzeit ausgerechnet werden. Im Ergebnisargument finden wir die Ziele die während der Laufzeit ausgerechnet werden sollen. Die goal_expansion/2 Fakten und Regeln definieren nichts anderes als die Trennlinie zwischen Kompilierzeit und Laufzeit. Die vorgängig aufgezeigte systematische Entwicklung von goal_expansion/2 Fakten und Regel kann als korrekt gezeigt werden, solange reines Prolog beteiligt ist. In der Praxis finden wir oft die Nutzung von unreinen Prolog Prädikaten wie z.B. var/1 um Terme zu überprüfen oder \+/1 für die Negation durch Misslingen. Unreine Prädikate machen die allgemeine Gültigkeit des systematischen Ansatzes zu Nichte. Gründe für diese Unzulänglichkeit können in einem unterschiedlichen Überlaufen von Variablenbindungen durch die Zielexpansion in ihren Kontext zur Kompilierzeit und unter normalen Bedingungen zur Laufzeit. Beispiele sind schnell gefunden, so arbeiten z.B. die folgenden zwei Prolog Programme in Bezug auf var/1 unterschiedlich: p(1). q(X) :- var(X), p(X). q(1) :- var(1). Nichtsdestotrotz handelt es sich bei der Zielexpansion um eine attraktive Technik die in vielen Prolog Systemen vorzufinden ist. Es gibt verschiedene Anwendungsgebiete. Teilweise ausgerechnete Prädikate lassen sich schneller ausführen da ein gewisser Aufwand schon während der Kompilierzeit erbracht wurde. Dies scheint nicht so wichtig in dem squares Beispiel das wir gegeben haben, aber die Expansion von Prädikaten an Angelpunkten kann zu zusätzlicher Geschwindigkeit führen. Es gibt nun einige Spracheigenheit die sich in verschiedenen Prologsystemen wiederfinden, die nur attraktiv werden durch die den Geschwindigkeitsgewinn der Zielexpansion. So benutzt z.B. Jekejeke Prolog die Zielexpansion für die Realisierung von DCGs. Wir werden in einem späteren Tagebucheintrag das Thema fortführen und weitere Details lüften.

Kommentare