EMZETT.
Login

Emzett Wiki

Prolog: Backtracking, Cut und Kontrolle

Properties1
tagsprogrammiersprachen, prolog

4 Min. Lesezeit

Kurz: Prolog probiert Regeln von oben nach unten. Schlägt ein Ziel fehl, geht es zum letzten Entscheidungspunkt zurück (Backtracking) und probiert die nächste Alternative.

Teil des Kurses Prolog

Kapitel 4 von 8 im Kurs Prolog. Mit Fortschritt, Quiz und Zertifikat auf der Lernseite.

Wie Prolog sucht

Prolog probiert Regeln von oben nach unten. Schlägt ein Ziel fehl, geht es zum letzten Entscheidungspunkt zurück (Backtracking) und probiert die nächste Alternative.

farbe(rot).
farbe(gruen).
farbe(blau).
form(kreis).
form(quadrat).
 
main :-
    forall((farbe(F), form(G)), format("~w ~w~n", [F, G])).

Ausgabe:

rot kreis
rot quadrat
gruen kreis
gruen quadrat
blau kreis
blau quadrat

Cut (!) beschneidet den Suchbaum

! verwirft alle noch offenen Alternativen. Man nutzt es für Determinismus und Effizienz:

max(X, Y, X) :- X >= Y, !.
max(_, Y, Y).
 
klasse(N, klein) :- N < 10, !.
klasse(N, mittel) :- N < 100, !.
klasse(_, gross).
 
main :-
    max(3, 9, A), writeln(A),
    max(9, 3, B), writeln(B),
    klasse(5, K1), klasse(50, K2), klasse(500, K3),
    writeln([K1, K2, K3]),
    findall(K, klasse(5, K), AlleFuer5), writeln(AlleFuer5).

Ausgabe:

9
9
[klein,mittel,gross]
[klein]

Achtung

Ein Cut verändert die Bedeutung des Programms (rotes Cut), wenn er Lösungen abschneidet. Setze ihn sparsam und teste das Prädikat mit allen Argument-Kombinationen.

Negation und if-then-else

\+ bedeutet „nicht beweisbar“ (Negation als Fehlschlag). Besser lesbar ist ( Bedingung -> Dann ; Sonst ):

vogel(spatz).
vogel(pinguin).
kann_nicht_fliegen(pinguin).
 
fliegt(X) :- vogel(X), \+ kann_nicht_fliegen(X).
 
zeige(X) :- ( fliegt(X) -> format("~w fliegt~n", [X]) ; format("~w fliegt nicht~n", [X]) ).
 
main :-
    zeige(spatz), zeige(pinguin), zeige(hund),
    ( \+ member(z, [a, b]) -> writeln('z fehlt') ; true ),
    X = 7,
    ( X > 5, X < 10 -> writeln('zwischen 5 und 10')
    ; X >= 10 -> writeln('groß')
    ; writeln('klein') ).

Ausgabe:

spatz fliegt
pinguin fliegt nicht
hund fliegt nicht
z fehlt
zwischen 5 und 10

findall, bagof, setof

Sammelt alle Lösungen eines Ziels:

alter(mia, 17).
alter(tom, 25).
alter(zoe, 17).
alter(ben, 31).
 
main :-
    findall(N, alter(N, _), Namen), writeln(Namen),
    findall(N-A, alter(N, A), Paare), writeln(Paare),
    findall(N, alter(N, 17), Siebzehn), writeln(Siebzehn),
    ( findall(N, alter(N, 99), L), L == [] -> writeln('niemand mit 99') ; true ),
    setof(A, N^alter(N, A), Alter), writeln(Alter),
    forall(bagof(N, alter(N, A), Gruppe), format("~w: ~w~n", [A, Gruppe])),
    aggregate_all(count, alter(_, _), Anzahl), writeln(Anzahl),
    aggregate_all(max(A, N), alter(N, A), max(Hoechst, Wer)), writeln(Wer-Hoechst).

Ausgabe:

[mia,tom,zoe,ben]
[mia-17,tom-25,zoe-17,ben-31]
[mia,zoe]
niemand mit 99
[17,25,31]
17: [mia,zoe]
25: [tom]
31: [ben]
4
ben-31

Dynamische Fakten

Mit assert/retract verändert man die Wissensbasis zur Laufzeit:

:- dynamic zaehler/1.
:- dynamic gesehen/1.
 
zaehler(0).
 
erhoehe :- retract(zaehler(N)), N1 is N + 1, assertz(zaehler(N1)).
 
main :-
    erhoehe, erhoehe, erhoehe,
    zaehler(Z), writeln(Z),
    assertz(gesehen(a)), assertz(gesehen(b)),
    findall(X, gesehen(X), Alle), writeln(Alle),
    retractall(gesehen(_)),
    ( gesehen(_) -> writeln(noch_da) ; writeln(leer) ).

Ausgabe:

3
[a,b]
leer

Ausnahmen

sicher_teilen(A, B, E) :-
    catch(E is A / B, error(evaluation_error(zero_divisor), _), (E = unendlich)).
 
main :-
    sicher_teilen(10, 2, X), writeln(X),
    sicher_teilen(1, 0, Y), writeln(Y),
    catch(atom_length(_, _), error(Fehler, _), (print_message(silent, Fehler), writeln('Instanziierungsfehler'))),
    catch(throw(mein_fehler(42)), mein_fehler(Code), (format("gefangen: ~w~n", [Code]))),
    catch(X2 is foo + 1, error(type_error(T, W), _), (format("Typfehler ~w ~w~n", [T, W]))),
    ( var(X2) -> writeln(ungebunden) ; true ).

Ausgabe:

5
unendlich
Instanziierungsfehler
gefangen: 42
Typfehler evaluable foo/0
ungebunden

Merke

  • Prolog sucht tiefenorientiert und geht bei Fehlschlag per Backtracking zurück
  • ! (Cut) schneidet Alternativen ab; \+ negiert; -> / ; ist if-then-else
  • findall, bagof, setof, aggregate_all sammeln Lösungen
  • assertz/retract ändern Fakten zur Laufzeit; catch/throw behandeln Fehler

Übungsaufgabe

Finde mit findall alle Paare aus zwei Listen, deren Summe 10 ergibt.

Quiz zur Selbstkontrolle

Weiter im Kurs

Zurück: Listen und rekursive Strukturen

Weiter: Klassische Probleme lösen

Alle Kapitel: Prolog im Überblick

Graphansicht

Backlinks