direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Prolog-Tipps

Aufgabenblatt 4, Aufgabe 2b)

Wie man eine Liste mit Integer-Zahlen erstellt, steht am Ende dieser Seite. Noch wichtiger: alle 0..n-elementigen Teilmengen einer n-elementigen Liste bilden: ebenfalls am Ende dieser Seite.

 

Bei der Lösung kann man z.B. so verfahren:

zuerst einen Generator für Folgezustände (egal ob zulässig oder unzulässig, hauptsache ALLE möglichen Folgezustände werden generiert) schreiben und danach die Zulässigkeit testen:

folgezustand( AktuellerZustand, FolgeZustand ) :-

generiere( AktuellerZustand, FolgeZustand ),

checke_zulaessigkeit( Folgezustand ).

 

generiere/2 erzeugt einen Folgezustand und im Backtrackingfall den nächsten, bis keiner mehr generierbar ist. Achten Sie dabei darauf, nicht durch Permutation denselben Zustand mehrfach zu generieren!

checke_zulaessigkeit/1 überprüft, ob der generierte Zustand auch zulässig ist (im Rahmen der Aufgabenstellung).

 

 

Beachten Sie: auch Bootsfahrten ohne Tier sind möglich (und in manchem Problem auch zur Lösung notwendig, z.B. bei n=3 und k=1).

 

Wenn Sie die Tiere auf einer Uferseite als Liste von Zahlen repräsentieren, dann achten Sie darauf diese Liste sortiert zu verwalten. Denn tiefensuche/2 nutzt als Zyklentest member/2. member funktioniert mittels Unifikation: ein Element [3,2,1] unifiziert aber nicht ein Element [1,2,3]. Am besten, Sie nutzen sort/2, welches das 1.Listenargument lexikographisch sortiert und als Ergebnis im 2. Argument unifiziert.

 

In der Zustandsbeschreibung muss das Boot nicht mit modelliert werden, es geht auch ohne.

 

Natürlich dürfen (und müssen) Sie startzustand/1 um weitere ARgumente erweitern, z.B. startzustand( N, K, StartZustand ).

 

Warnings und Fehlermeldungen

  • Syntax error: Operator expected: kommt bei falscher Syntax, insbesondere wenn die Klammer nicht direkt hinter dem Prädikatensymbol kommt, z.B. bei
      p (X).
    Oder wenn hinter einer Klausel der abschließende Punkt, Komma oder Semikolon fehlt, z.B. bei
      t(V):- true
      t(V):- true.
  • Singleton variables: [Var1, Var2, ...]: Diese Warning besagt, dass die in der Liste angeführten Variablen nur jeweils EINMAL in der Klausel vorkommen. Dies deutet auf einen Schreibfehler hin, wie z.B. in
      t(Variable) :- integer(Varialbe),write(Variable),nl.
    Es kann aber auch sein, dass die Variable garnicht benötigt wird, wie z.B. in
      t(A,B) :- write(A), nl.
    Dann entweder die Variable weglassen, oder eine anonyme Variable benutzen (_B).
  • Clauses of action_sequence/2 are not together in the source- file: Alle Klauseln eines Prädikats sollten direkt hintereinander stehen. Diese Warning kann aber (zumindest in SWI-Prolog) ignoriert werden.

Aufgabenblatt 2

  • Zeile 54: :- dynamic( at_position/3 ). ist eine Compiler-Anweisung. Alles, was mit assert/1 und retract/1 verändert wird muss als dynamic deklariert sein. Ansonsten würde Prolog eine Fehlermeldung "try to redefine static pred..." ausgeben.
    Eine Anweisung
      :- P.
    wird beim consulten direkt ausgeführt, d.h. P wird aufgerufen. Das ist dasselbe, als wenn man
      ?- P.
    auf der Konsole eingibt. Mittels derartiger ":- P." -Anweisungen kann man sicherstellen, dass beim Laden eines Programms bestimmte Initialisierungen ausgeführt werden.
  • Zeile 242 ff: Signaturen:
    '+'
    bedeutet in einer "Signatur", dass es sich um eine Input-Variable handelt (muss instantiiert, nicht frei sein).
    '?' bedeutet, kann frei oder belegt sein.
    '-' bedeutet: muss freie Variable sein, die (üblicherweise) im Prädikat instantiiert wird.
    Beispiel:
      max( A, B, A ) :- integer(A), integer(B), A>B, !.
      max( A, B, B).
    Diese Definition würde die Signatur
      %max( +Integer, +Integer, ?Integer )
    tragen, denn die beiden ersten Argumente werden auf integer/1 geprüft, während das dritte Argument frei sein kann (dann wird es instantiiert) oder mit einem Integer belegt sein kann (dann funktioniert max/3 als Test).

Utilities

Um alle Lösungen in einer Liste aufzusammeln, wird das Prädikat bagof/3 (bzw. setof/3, welches Duplikate vermeidet) verwendet. Dieses Prädikat scheitert leider wenn der Call des ersten Arguments scheitert. Um dem abzuhelfen, sollte safe_bagof/3 verwendet werden:

 

/*

  alle Lösungen in einer Liste sammeln

  Prolog kennt bagof/3, das aber scheitert, wenn keine Lösung existiert, daher

   safe_bagof( -VarSpec, +Predicate, ?ResultList )

*/

safe_bagof( Vars, Predicate, ResultList ) :-

  bagof( Vars, Predicate, ResultList ), !.

safe_bagof( _Vars, _Predicate, [] ). % return empty list on fail

 

 

retract/1 ist nichtdeterministisch, d.h. bei einem Retry nach einem Fail unterhalb kann retract erneut ausgeführt werden, was zumeist aber nicht beabsichtigt ist. In diesem Falle bitte entweder once(retract(Term)) nutzen, oder aber ein selbst definiertes safe_retract/1 verwenden:

/*

  maximal 1 mal ein Fakt retracten

  safe_retract( +Predicate )

*/

safe_retract( Predicate ) :-

  once(retract(Predicate)), !.

safe_retract( _Predicate ).

 

 

asserta/1 fügt eine Klausel an den Anfang der Datenbasis ein. Dies hat den Vorteil, dass wenn die Klausel einmal gerufen wird, dann immer die zuletzt hinzugefügte als erstes Ergebnis gefunden wird. Im Gegensatz dazu fügt assert/1 die Klausel ans Ende. Wenn man also "neue" Daten als aktuellste einpflegen möchte, dann sollte man asserta(Term) nutzen. Der Zugriff auf das aktuellste Element erfolgt dann mittels once(Term), um Backtracking auszuschalten und nur das aktuellste Element zu verwenden.

 

 

Integer-Listen generieren:

%% integer_list_with_step( +Start, +End, +Step, ?List )

integer_list_with_step( I, End, Step, List ) :-

  integer( I ),

  integer( End ),

  integer( Step ),

  Step > 0,

  c_integer_list_with_step( I, End, Step, List ).

 

c_integer_list_with_step( I, End, Step, List ) :-

  I > End ->

    List = []

    ;

    List = [I|RestList],

    NI is I+Step,

    c_integer_list_with_step( NI, End, Step, RestList ).

 

Teilmengen aus einer durch eine Liste repräsentierte Menge generieren (auch: Test auf Teilmenge):

% subset( ?SubList, +List ) Sublist is subset of List

subset( [], _ ).

subset( [H|T], List ) :-

  choose_one(H,List,RestList),

  subset(T,RestList).

 

choose_one( H, [H|T], T ).

choose_one( Elem,[_|T], Rest ) :-

  choose_one( Elem, T, Rest ).