Prolog & CHR

• Grundbegriffe der Logik sollten bekannt sein
• Theorie aus Foliensatz 8 wird wenig Bedeutung für die Klausur haben
• Hauptbestandteile der Programme in Prolog und CHR: Fakten, Prädikate, Regeln
• ...

Anders als in imperativen Programmiersprachen stehen Variablen nicht für Speicherplätze, sondern sind Platzhalter für genau einen Wert. Sie können, einmal gebunden, keinen anderen Wert mehr annehmen.

Konstanten

% fangen mit kleinem Buchstaben an
  otto, karl, mensch, person_, uni_mensa

% oder sind in Hochkommata eingeschlossen
  'Otto', 'Karl', 'Mensch', 'Person', 'Uni-Mensa'

% oder sind Zahlen
  1, 2.3, -5

Strukturen

% bestehen aus Funktionssymbol und Argumenten
  name(k1, k2, ..., kn)
% sind charakterisiert durch Namen und Anzahl der Argumente
  name/n         % "Funktor"
% können geschachtelt und mit unterschiedlichen Stelligkeiten
%    definiert werden

Prädikate

• Für uns: sehr ähnlich zu Strukturen
• Prädikate können nicht geschachtelt werden

Welche Typen werden in Prolog unterschieden?

Tupel

• Wie in Haskell:

  (1,2,'c')

• Häufig Definition eines Tupels über neues Prädikat, z.B.

  zahlenpaar(1,1)

• n-Tupel besitzt dann schlicht einen Funktor name/n

Grundrechenarten

+, -, *, /, //, mod

Exponentiation

^ und **

Arithmetische Vergleiche

=:=, =\=, <, >, =<, >=

"Gleichmachen von Termen": Zwei Terme sind unifizierbar, wenn sie entweder gleich sind, oder durch Bindung von Variablen gleich gemacht werden können.

Dabei sind folgende Regeln zu beachten:

• Konstanten sind nur mit sich selbst unifizierbar.
• Eine ungebundene Variable ist mit jedem Term unifizierbar, der die Variable selbst nicht enthält.
• Strukturen sind unifizierbar, wenn sie den gleichen Funktor besitzen und die Komponenten paarweise unifizierbar sind.

Unifikation geschieht über den "=" Operator.

Beispiele:

[A,B] = [a,b].
  % bindet A=a, B=b.

[A|B] = [a,b].
  % bindet A=a, B=[b].

[A, f(x,y)|R] = [f(R), B].
  % bindet A=f(R), B=f(x,y), R=[].

sum([X,Y],R) = sum([2,f(Y)],R).
  % nicht unifizierbar, da Y=f(Y).

Arithmetische Variablenbindungen werden in Prolog mit is durchgeführt statt =. Warum?

X = 4/5.
 % unifiziert nur X und "4/5", berechnet aber nichts
 
X is 4/5.
 % berechnet 4/5 und bindet X an diesen Wert

• Ein Prolog-Programm besteht aus einer Folge von Fakten und Regeln.
• Eine Berechnung wird angestoßen durch eine Anfrage.
• Die Berechnung entspricht dem Versuch, die Anfrage aus den "Programmformeln" abzuleiten. Es wird versucht, eine erfüllende Variablenbelegung zu finden.
• Das Ergebnis der Berechnung ist diese Variablenbelegung.

• Prolog-Fakten können einfach aufgelistet werden
• können neben Entitäten auch Variablen enthalten

Beispiele:

mensch(falco).
mensch(markus).

freunde(falco,markus).
freunde(markus,falco).

term(f(x,y)).
leere_liste([]).

prolog_ist_toll.
element(X, [X|_]).

• Hornklauseln, d.h. im Regelkopf steht genau ein Prädikat
• Allgemeiner Aufbau:

  kopf/n :- rumpf1, ..., rumpfn.
  

• Wechselseitige Abhängigkeiten vermeiden:

  elternteil(X,Y) :- kind(Y,X).
  kind(X,Y) :- elternteil (Y,X).

Beispiele:

freund(X,Y) :- freund(Y,X).
 % wird Problem bei Abfrage von freund(A,B).

grossvater(X,Y) :- mutter(X,M), vater(M,Y).
grossvater(X,Y) :- vater(X,V), vater(V,Y).

prolog_ist_toll :- sprache(prolog), toll(prolog).
es_gibt_tolle_sprache :- sprache(X), toll(X).

• Abarbeitung der Anfrage von links nach rechts
• Versuch, das Prädikat der Anfrage mit Fakt oder Regelkopf zu unifizieren
• Falls mehrere Fakten oder Regeln in Frage kommen, wird das erste (Backtracking: nächste) genommen
  Folge: Basis- vor Rekursionsfällen!
• Wird eine Regel angewandt, werden die Prädikate im Rumpf von links nach rechts ausgewertet.
• Gibt es weder passenden Fakt noch Regel, schlägt die Anfrage fehl.

(Übungsaufgabe SS12 8-4)
Gegeben sei folgendes Prolog-Programm:

(1)   a(u).
(2)   b(s).
(3)   b(t).
(4)   c(X) :- p(X),r(X).
(5)   c(X) :- q(X).
(6)   p(t).
(7)   q(t).
(8)   q(u).
(9)   r(s).

Anfragen:

• ?- a(X),c(X).
• ?- b(X),c(X).

(1)   a(u).
(2)   b(s).
(3)   b(t).
(4)   c(X) :- p(X),r(X).
(5)   c(X) :- q(X).
(6)   p(t).
(7)   q(t).
(8)   q(u).
(9)   r(s).

?- b(X),c(X).

member/2

... ist erfüllbar, wenn das erste Argument in der als zweites Argument übergebenen Liste enthalten ist.

member(X,[X|_]).
member(X,[_|Xs]) :- member(X,Xs).

append/3

... ist erfüllbar, die beiden ersten übergebenen Listen zusammengefügt gerade die letzte ergeben.

append([],L,L).
append([X|L1], L2, [X|L3]) :‐ append(L1, L2, L3).

Keine Unterscheidung zwischen Eingabe- und Ausgabeparametern in Prolog:

append([1,2],[3,4],[1,2,3,4]).   % true
append([1,2],[3,4],X).           % X = [1,2,3,4]
append([1,2],X,[1,2,3,4]).       % X = [3,4]
append(A,B,[1,2,3,4]).           % 5 Lösungen über Backtracking

reverse/2

... ist erfüllbar, wenn die erste übergebene Liste die Umkehrung der zweiten ist.

reverse([],[]).
reverse([H|T],Neu2) :- reverse(T,Neu), append(Neu,[H],Neu2).

lookup/3

... steht auf dem Cheatsheet. Was macht dieses Prädikat?

Ist erfüllt, wenn der übergebene Schlüssel in einer Liste aus Schlüssel-Wert-Paaren einen bestimmten Wert annimmt.

write/1

... schreibt übergebenen Wert in die Ausgabe.

write('Hello '), write(Name), write('!').

nl/0

... schreibt einen Zeilenumbruch in die Ausgabe.

write('Hello '), write(Name), write('!'), nl,
write('Alles klar?').

\+(Prädikat)

... ist erfüllbar, wenn Prädikat unerfüllbar ist.

\+(member([1,[2,3,4]]))       % true

• Wir verwenden CHR unter der Hostsprache Prolog - somit sind alle Syntaxregeln und Prädikate aus Prolog gültig.
• Statt Prädikaten arbeiten wir nun mit Constraints.
• Gegensatz zu Prolog: Gleiche Constraints können mehrfach vorkommen.
• Kein Backtracking.

Soll ein CHR Constraint benutzt werden, muss es am Anfang des Programms definiert werden:

% Allgemein:
%   chr_constraint Name/Stelligkeit.

chr_constraint leq/2.

chr_constraint prime/1, num/1, num/2.

Propagierungsregel

... erzeugt neue Constraints aus bestehenden Informationen.

Kopf1, ..., Kopfn ==> Rumpf1, ..., Rumpfn
% Die Constraints aus dem Kopf verbleiben im 
%   Constraint-Speicher, die im Rumpf kommen dazu.

Beispiel ("less-or-equal"):

leq(A,B), leq(B,C) ==> leq(A,C).

→ Häufige Anwendung bei der Generierung von Kandidaten. (Vgl. Primzahlsieb, Teiler)

Simplifizierungsregel

... entfernt bestehende Constraints und fügt ggf. neue hinzu.

Kopf1, ..., Kopfn <=> Rumpf1, ..., Rumpfn
% Die Constraints aus dem Kopf werden aus dem 
%   Constraint-Speicher entfernt, die aus dem Rumpf
%   hinzugefuegt.

Beispiel:

nord, sued <=> true.

→ Anwendung bei redundanten oder unwichtigen Informationen.

Simpagationsregel

... ist die Mischform aus den beiden vorangegangenen Regeln.

Kept1, ..., Keptn \ Removed1, ..., Removedn 
 <=> New1, ..., Newn
% Die Kept-Constraints aus dem Kopf werden im 
%   Constraint-Speicher belassen, die Removed-Constraints
%   entfernt, und die New-Constraints aus dem Rumpf
%   neu hinzugefügt.

Beispiele:

prime(N) \ prime(N) <=> true.

fib(B) \ fib(A) <=> A < B | N is A+B, fib(N).

Simpagationsregel (Forts.)

Anwendungen:

• wenn die Simplifizierung an das Vorhandensein bestehender Constraints gebunden ist, die nicht entfernt werden sollen
• sehr häufig: Duplikate eliminieren

... gibt's mit Lösungsvorschlägen hier:
fnogatz.github.io/talks/pdp-rep-13/prolog-chr/exercises.html

Credits

Thanks to Benjamin Erb for the html5slides and uulm template.

Title image: Miran Lipovača under CC BY-NC-SA 3.0