Exkurs: CHR

[Camping_RIDER]

Aloha ;)

Prolog ist sowieso sehr kurz gekommen; die Hälfte des Semesters hatte Haskell für sich und die andere Semesterhälfte teilen sich Prolog und CHR (Constraint Handling Rules, falls das kein Begriff ist - keine Ahnung wie weit das konkret verbreitet ist) - und da unser Prof. der Erfinder von CHR ist, ist der Prolog-Teil eben doch recht kurz gekommen.

CHR war mir bis jetzt kein Begriff, es sieht aber interessant aus und erinnert mich zumindest syntaktisch an lineare Programmierung.

Grundsätzlich ist CHR keine eigenständig lauffähige Sprache, sondern eine Art "Sprache in der Sprache", d.h. CHR bedient sich einer beliebigen Hostsprache (es gibt Implementierungen für verschiedenste Sprachen).

Das Grundkonzept an CHR ist ein dynamischer Constraint-Speicher und der Zustand des Programms bemisst sich dann am Vorhandensein oder nicht-vorhandensein bestimmter Constraints in diesem Speicher. Die elementarste Operation in CHR ist damit das Ablegen eines Constraints im Constraint-Speicher.

Die Programmierung findet mithilfe von drei Arten von Regeln statt (die Regeln haben jeweils eine id und können noch Bedingungen, also ein Guard-Statement, haben):

Simplifizierungsregel

"<=>"

Falls bestimmte constraints im Constraint-Speicher liegen, ersetze diese durch andere Constraints

Prolog-Pseudocode: Regel-ID @ Head-wegwerfen <=> Guard | Body

Propagierungsregel

"==>"

Falls bestimmte constraints im Constraint-Speicher liegen, füge diesem weitere Constraints hinzu

Prolog-Pseudocode: Regel-ID @ Head-behalten ==> Guard | Body

Simpagationsregel

Mischung aus "<=>" und "==>"

Falls bestimmte constraints im Constraint-Speicher liegen, entferne einen Teil von diesen constraints und füge dafür neue constraints hinzu

Prolog-Pseudocode: Regel-ID @ Head-behalten \ Head-wegwerfen <=> Guard | Body

Die Regeln werden alle nacheinander linear angewandt; jedesmal wenn sich der constraint-Speicher verändert werden nochmal alle Regeln angewandt, bis der constraint-Speicher sich nicht mehr verändert (Programmende).

Beispiel für ein CHR-Kuchenteigrezept in der Hostsprache Prolog (in swi-prolog lauffähig):

% CHR-Library einbinden

:- use_module(library(chr)).

% Deklaration der Constraints mit Anzahl möglicher Parameter

:- chr_constraint ei/0,eigelb/0,eiweiss/0,butter/1,puderzucker/1,mehl/1,vanillezucker,teig/1.

% Küchenwerkzeug: Eitrenner - entfernt Ei aus dem Speicher und fügt dafür eigelb und eiweiss hinzu (Simplifizierungsregel)

eitrenner @ ei <=> eigelb,eiweiss.

% Küchenwerkzeug: Küchenmaschine - wenn alle Zutaten in ausreichender Menge vorhanden sind, wird daraus der Teig gemischt (Simplifizierungsregel mit Guard)

kuechenmaschine @ butter(B),puderzucker(P),mehl(M),vanillezucker,eigelb <=> B >= 200, P >= 100, M >= 300 | M1 is M - 300, B1 is B - 200, P1 is P - 100, butter(B1),puderzucker(P1),mehl(M1),teig(620).

% Küchenwerkzeug: große Schüssel - darin kann der Teig zusammengefügt werden, wenn er nicht auf einmal in die Küchenmaschine gepasst hat ;) (Simplifizierungsregel)

grosse_schuessel @ teig(X),teig(Y) <=> Z is Y + X, teig(Z).

Im SWIPL kann das dann z.B. folgendermaßen gestartet werden / ergibt folgende Ausgabe:

% Eingabe - Anfangs-Constraints abspeichern
?- butter(500), puderzucker(800), mehl(600), vanillezucker,vanillezucker, ei, eigelb.
eiweiss

% Ausgabe - Inhalt des Constraint-Speichers nach Programmende
butter(100)
puderzucker(600)
mehl(0)
teig(1240)
true ;
false.

Das ist natürlich quasi ein sinnlos-Programm, veranschaulicht aber die Wirkungsweise der Simplifizierungsregel und des Constraint-Speichers ganz gut (und Propagierungsregeln sind ziemlich trivial und Simpagation ist lediglich eine Mischung von beidem).

Falls das nicht schon too much war - die Einführung in CHR fand bei uns mit Hilfe einer einzelnen PPP statt, ich war mal so frech und hab die bei mir ge-up-t.

Grüße,

RIDER