Prolog programmieren?
ich verstehe die sprache gar nicht . Für die klausur muss ich nur Listen und Rekursion verstehen kann,das konzept versteh ich nur den syntax gar nicht .Finde das ganz komisch kann mich jemand aufklären?
1 Antwort
Listen werden immer in eckigen Klammern geschrieben. Ihre Elemente werden jeweils durch ein Komma getrennt.
Beispiel:
:- initialization(main).
main :- Numbers = [1, 2, 3].
Innerhalb des main-Prädikats wird eine Variable Numbers erstellt, die eine Liste an Zahlen aufnimmt.
Die Werte einer Liste müssen dabei nicht zwingend vom gleichen Typ sein. So kannst du beispielsweise ebenso Sublisten einfügen:
Numbers = [1, [2, 3]]
Diese Liste hat nun zwei Elemente: Eine Zahl (1) und eine Liste bestehend aus den Zahlen 2 und 3.
Listen bauen sich außerdem rekursiv auf. Sie bestehen immer aus einem Wert (dem ersten Wert / Kopf) und einem Verweis auf eine andere Liste (alle Werte mit Ausnahme des Kopfs). Das heißt, diese Liste:
Numbers = [1, 2, 3]
hat ein Element 1 und eine Subliste, die die restlichen Werte (2, 3) beinhaltet. Würde man diese Subliste explizit herausextrahieren, bestände sie erneut aus einem Wert (2) und einer Referenz auf eine Liste, die die 3 (sowie eine leere Liste) trägt.
Diese Struktur wird auch gut mit Hilfe des display-Prädikats deutlich:
display(Numbers) % output: '.'(1,'.'(2,'.'(3,[])))
Prolog erlaubt nun mit dem Pipe-Operator noch eine Zerlegung in die beiden Teilstücke:
:- initialization(main).
main :-
Numbers = [1, 2, 3],
[Head | Tail] = Numbers,
write(Head), % output: 1
nl,
write(Tail). % output: [2, 3]
So eine Zerlegung kannst du auch schon beim initialen Anlegen der Liste vorgeben:
[Head | Tail] = [1, 2, 3]
Des Weiteren dient der Pipe-Operator dazu, neue Elemente vor eine Liste zu hängen. Im folgenden Fall wird eine Liste mit der 5 am Anfang erstellt:
:- initialization(main).
main :-
Numbers = [1, 2, 3],
Numbers2 = [5 | Numbers],
write(Numbers2). % output: [5, 1, 2, 3]
Das Wissen darüber, wie Listen funktionieren und zerlegt werden können, kann man nun nutzen, um sich jedes einzelne Listenelement rekursiv ausgeben zu lassen:
:- initialization(main).
main :-
Numbers = [1, 2, 3],
print_elements(Numbers).
print_elements([]) .
print_elements([Head | Tail]) :-
write(Head),
nl,
print_elements(Tail).
Zuerst wird die Liste erstellt und an ein Prädikat print_elements übergeben, welches bereits bei der Wertaufnahme eine Teilung vorgibt. Der Kopfwert wird auf der Konsole ausgegeben, der Rest an einen neuen Aufruf des print_elements-Prädikats weitergegeben. Dieses zerlegt dieses Teilstück wieder und verfährt wie zuvor. Sobald es nichts mehr zum Zerlegen gibt (also eine leere Liste vorliegt), trifft der erste print_elements-Fakt zu und es wird nichts gemacht. Er dient also als eine Art Abbruchbedingung für die Rekursion.
Der folgende Abschnitt verdeutlich noch einmal den rekursiven Callstack (jede Einrückung verdeutlicht den Kontext eines Aufrufs von print_elements):
print_elements([1, 2, 3]):
write(1)
nl
print_elements([2, 3]):
write(2)
nl
print_elements([3]):
write(3)
nl
print_elements([]):
.
Noch ein weiteres Beispiel (bei dem diesmal die Anzahl der Elemente in der Liste ermittelt wird):
:- initialization(main).
main :-
Numbers = [1, 2, 3],
number_of_elements(Numbers, Counter),
write(Counter).
number_of_elements([], 0) .
number_of_elements([_ | Tail], Counter) :-
number_of_elements(Tail, Subcounter),
Counter is Subcounter + 1.
Erneut dient ein Fakt als Abbruchbedingung. Wenn eine leere Liste übergeben wird, entspricht deren Länge 0. Das Prinzip ist im Übrigen ähnlich zu dem vorherigen Beispiel: Die übergebene Liste wird bei jedem Aufruf des Prädikats weiter aufgeteilt und die Subsequenz weitergegeben. Eine Zählervariable wird dabei immer weiter inkrementiert. Da das Kopfelement nicht explizit gebraucht wird, habe ich einen Unterstrich als Variablenname gewählt.
Callstack des rekursiven Aufrufs (jede Einrückung verdeutlicht den Kontext eines Aufrufs von number_of_elements):
number_of_elements([1, 2, 3], Counter):
number_of_elements([2, 3], Counter):
number_of_elements([3], Counter):
number_of_elements([], 0):
.
Counter is 0 + 1
Counter is 1 + 1
Counter is 2 + 1
Zu guter Letzte könnte man noch auf ein paar hilfreiche Systemprädikate verweisen, mit denen sich Listen manipulieren oder prüfen lassen. Zum Beispiel member oder append.
?- member(1, Numbers). % check if Numbers contains 1
?- append([1, 2, 3], [4, 5, 6], Numbers). % Numbers = [1, 2, 3, 4, 5, 6]
Eine vollständige Übersicht vorhandener Systemprädikate findest du in der Referenz einer Prolog-Implementation (z.B. GNU-Prolog oder SWI-Prolog).
Zu Rekursion wiederum ist es wichtig, zu wissen, wie man Prädikate (Fakten und Regeln) erstellt und wie Rekursion generell funktioniert.
Prädikate sollen im Grunde logische Aussagen treffen. So trifft dieser Fakt:
likes(Marie, Anna).
deklarativ eine wahre Aussage. Mittels einer Regel kann man logische Beziehungen zwischen Fakten formulieren:
friends(personA, personB) :-
likes(personA, personB),
likes(personB, personA).
enemies(personA, personB) :-
not(likes(personA, personB)),
not(likes(personB, personA)).
Die Fakten nach dem Präfixoperator (:-) treffen logische Aussagen, die linke Seite kann als Schlussfolgerung dazu verstanden werden. Sie ist wahr, wenn die Fakten zutreffen.
Bei diesem Beispiel:
:- initialization(main).
main :- is_ancestor(klaus, richard).
is_parent(klaus, gert).
is_parent(gert, richard).
is_parent(richard, bernhard).
is_ancestor(Child, Ancestor) :-
is_parent(Child, Ancestor),
write('is ancestor').
is_ancestor(Child, Ancestor) :-
is_parent(Child, X),
is_ancestor(X, Ancestor).
hätten wir bereits eine Rekursion, die versucht, einen Vorfahren von klaus zu finden. Zuerst versucht das Programm die erste is_ancestor-Klausel. Da sie keinen Fakt findet, welcher richard als Elternteil von klaus ausweist, geht sie in die zweite is_ancestor-Klausel. In dieser wird ein neuer Fakt aufgeführt, der besagt, dass X ein Vorfahr von klaus sein kann. Anschließend ruft sich das Prädikat selbst noch einmal auf, es geht erneut zuerst in die erste Klausel. Diesmal sucht die nach einem Fakt, der auf is_parent(X, richard) zutreffen könnte. Der Fakt is_parent(gert, richard) lässt sich hierbei zuordnen.
Um Rekursion verstehen und anwenden zu können, bedarf es vor allem Übung. Meines Erachtens ist es auch hilfreich, sich den Callstack zu skizzieren, wobei man allerdings aufpassen sollte, mit kleinen konkreten Werten/Ketten zu arbeiten, um Zeit und Aufwand zu sparen.
Wenn man eigene rekursive Abläufe entwickeln möchte, ist es hilfreich, sich zuerst zu überlegen, welche grundsätzliche Operation wiederholt werden muss und wie man sie wieder stoppen kann. Des Weiteren kann es sein, dass man einen berechneten Zustand weitertragen muss. Dafür sollte eine Variable definiert werden.
Erneut ein einfaches Beispiel, bei dem die Summe aller Zahlen einer Liste berechnet werden soll:
- Grundsätzliche Operation: Der Kopf der Liste wird mit der aktuellen Summe addiert.
- Der Rest der Liste sowie die aktuelle Summe sind jeweils Daten, die mit jedem Rekursionsschritt weitergegeben werden müssen.
- Irgendwann ist die Liste leer. Dies kann man als Fakt vorgeben, welcher sogleich den Abbruch der Rekursion kennzeichnet.
sum_of_numbers([], 0).
sum_of_numbers([Head | Tail], Sum) :-
sum_of_numbers(Tail, TailSum),
Sum is Head + TailSum.
Callstack bei einer Liste [4, 5, 6]:
sum_of_numbers([4 | [5, 6]], Sum):
sum_of_numbers([5 | [6]], Sum):
sum_of_numbers([6 | []], Sum):
sum_of_numbers([], 0)
Sum is 6 + 0
Sum is 5 + 6
Sum is 4 + 11
Versuche dich am besten selbst an Übungsaufgaben. Zum Beispiel:
- Drehe die Reihenfolge der Elemente einer Liste um.
- Entferne die Duplikate in der Liste [1, 2, 3, 3, 4, 1].
- Prüfe, ob diese Liste [e, b, b, e] einem Palindrom entspricht.
- Tausche alle Vorkommen eines Elements in einer Liste mit einem anderen Wert aus.
- Suche in dieser Liste [0, 1, 1, 2, 3, 5, 8, 13] nach den Zahlen 7 und 8. Bei Fund wird die Zahl in der Konsole ausgegeben, bei Nichtfund der Wert -1.
- Berechne die ersten neun Ziffern der Fibonacci-Reihenfolge.
Des Weiteren wäre es nicht schlecht, sich ein paar zusätzliche Lernquellen zu suchen. Ein paar Beispiele: