Logische Programmiersprache
Logische Programmiersprachen verwenden die Prädikatenlogik (erster Stufe) zur Beschreibung des zu lösenden Problems. Das bedeutet, dass es sich bei den manipulierten Daten um sogenannte Terme handelt und dass anstelle von Prozeduren oder Funktionen herkömmlicher Programmiersprachen Prädikate formuliert werden.
Die folgende Aufzählung gibt beispielhaft fünf Terme wieder:
• 1
• a
• paar(a,b)
• [2 1 3 4]
• X
Man kann erkennen, dass Zahlen wie die 1 und Konstanten (z.B. a) einfach aufgebaute Terme sind. Komplizierter ist der dritte Term, der wie die Anwendung der Funktion paar auf die Argumente a und b aussieht. Es handelt sich bei Termen jedoch um rein syntaktische, passive Ausdrücke, die nur für sich selbst stehen und nicht, wie z.B. der mathematische Ausdruck 1 + 2, einen zugeordneten Wert besitzen. Der vierte Term ist eine vierelementige Liste. Der fünfte Term der Aufzählung ist eine Variable. Variable werden von Konstanten durch Großschreibung des Anfangsbuchstaben unterschieden.
Prädikate sind wahr/falsch-Aussagen über die Menge aller Terme (oder über das kartesische Produkt zweier oder mehrerer Mengen von Termen).
Ein Beispiel für ein einstelliges Prädikat ist das Prädikat prim(X), das genau dann erfüllt sein soll, wenn X eine Primzahl ist. Ein mehrstelliges Prädikat ist plus(X, Y, Z). Es soll erfüllt sein, wenn Z die Summe von X und Y ist.
Ein Programm einer logischen Programmiersprache besteht aus mehreren Definitionen für Prädikate. Prädikate können beispielsweise durch Hornklauseln beschrieben werden. Hornklauseln haben die Form
P <- Q1 & Q2 & ... & Qn.,
was bedeuten soll, dass P aus der Konjunktion der Qi folgt.
Die Ausführung eines Logikprogramms basiert auf einer Art von Backward Chaining. Ausgehend von einem zu beweisenden Faktum werden die Hornklauseln gegen die Pfeilrichtung bearbeitet.
Für das Prädikat wegeanzahl(W, H, N) werden nun die definierenden Hornklauseln angegeben. Das Prädikat beantwortet folgende Frage:
Wieviel kürzeste Wege existieren in einem Gitterrechteck mit w Zellen in horizontaler und h Zellen in vertikaler Richtung von der oberen, linken zur unteren, rechten Ecke?
Falls die Höhe oder die Breite Null ist, ist die Lösung trivial, es existiert ein Weg. Man drückt das durch die Hornklauseln
wegeanzahl(0, H, 1) <- .
wegeanzahl(W, 0, 1) <- .
aus.
Von der oberen, linken gelangt man entweder über den Punkt A oder über den Punkt B zur rechten, unteren Ecke. Das hellgrüne Rechteck hat eine um Eins kleinere Breite und Höhe als das größere Rechteck. Es gilt also:
wegeanzahl(W, H, Z) <- wegeanzahl(W, H', X)
& wegeanzahl(W', H, Y)
& H' is H - 1
& W' is W - 1
& Z is X + Y.
Durch Überlegungen aus dem Bereich der Kombinatorik kann man übrigens einen anderen Lösungsweg finden. Ein kürzester Weg von links-oben nach rechts-unten macht entweder Schritte nach rechts oder Schritte nach unten. Jeder kürzeste Weg hat eine Länge von (W + H) Einheiten. Beschreibt man einen kürzesten Weg durch eine Buchstabenfolge aus "R" für rechts und "U" für unten, so hat diese Buchstabenfolge also eine Länge von (W + H) und enthält genau W-mal das "R" und H-mal das "U". Die Anzahl verschiedener, derartiger Buchstabenfolgen ist (W + H)! : (W! H!).
Siehe auch: Prolog
Die folgende Aufzählung gibt beispielhaft fünf Terme wieder:
• 1
• a
• paar(a,b)
• [2 1 3 4]
• X
Man kann erkennen, dass Zahlen wie die 1 und Konstanten (z.B. a) einfach aufgebaute Terme sind. Komplizierter ist der dritte Term, der wie die Anwendung der Funktion paar auf die Argumente a und b aussieht. Es handelt sich bei Termen jedoch um rein syntaktische, passive Ausdrücke, die nur für sich selbst stehen und nicht, wie z.B. der mathematische Ausdruck 1 + 2, einen zugeordneten Wert besitzen. Der vierte Term ist eine vierelementige Liste. Der fünfte Term der Aufzählung ist eine Variable. Variable werden von Konstanten durch Großschreibung des Anfangsbuchstaben unterschieden.
Prädikate sind wahr/falsch-Aussagen über die Menge aller Terme (oder über das kartesische Produkt zweier oder mehrerer Mengen von Termen).
Ein Beispiel für ein einstelliges Prädikat ist das Prädikat prim(X), das genau dann erfüllt sein soll, wenn X eine Primzahl ist. Ein mehrstelliges Prädikat ist plus(X, Y, Z). Es soll erfüllt sein, wenn Z die Summe von X und Y ist.
Ein Programm einer logischen Programmiersprache besteht aus mehreren Definitionen für Prädikate. Prädikate können beispielsweise durch Hornklauseln beschrieben werden. Hornklauseln haben die Form
P <- Q1 & Q2 & ... & Qn.,
was bedeuten soll, dass P aus der Konjunktion der Qi folgt.
Die Ausführung eines Logikprogramms basiert auf einer Art von Backward Chaining. Ausgehend von einem zu beweisenden Faktum werden die Hornklauseln gegen die Pfeilrichtung bearbeitet.
Für das Prädikat wegeanzahl(W, H, N) werden nun die definierenden Hornklauseln angegeben. Das Prädikat beantwortet folgende Frage:
Wieviel kürzeste Wege existieren in einem Gitterrechteck mit w Zellen in horizontaler und h Zellen in vertikaler Richtung von der oberen, linken zur unteren, rechten Ecke?
Falls die Höhe oder die Breite Null ist, ist die Lösung trivial, es existiert ein Weg. Man drückt das durch die Hornklauseln
wegeanzahl(0, H, 1) <- .
wegeanzahl(W, 0, 1) <- .
aus.
Von der oberen, linken gelangt man entweder über den Punkt A oder über den Punkt B zur rechten, unteren Ecke. Das hellgrüne Rechteck hat eine um Eins kleinere Breite und Höhe als das größere Rechteck. Es gilt also:
wegeanzahl(W, H, Z) <- wegeanzahl(W, H', X)
& wegeanzahl(W', H, Y)
& H' is H - 1
& W' is W - 1
& Z is X + Y.
Durch Überlegungen aus dem Bereich der Kombinatorik kann man übrigens einen anderen Lösungsweg finden. Ein kürzester Weg von links-oben nach rechts-unten macht entweder Schritte nach rechts oder Schritte nach unten. Jeder kürzeste Weg hat eine Länge von (W + H) Einheiten. Beschreibt man einen kürzesten Weg durch eine Buchstabenfolge aus "R" für rechts und "U" für unten, so hat diese Buchstabenfolge also eine Länge von (W + H) und enthält genau W-mal das "R" und H-mal das "U". Die Anzahl verschiedener, derartiger Buchstabenfolgen ist (W + H)! : (W! H!).
Siehe auch: Prolog