Ben's prikbord.

Over backtracking

In februari 2016 kwam het begrip backtracking weer eens aan de orde op een bijeenkomst van de AIgg. Dat gaf mij aanleiding gaf om iets te schrijven over backtracking en de taal prolog.

De mogelijkheid tot backtracking is bij prolog ingebouwd. Een prolog programma heeft als doel de oplossing van een probleem. Als een programma wordt uitgevoerd is dat een zoektocht naar de oplossing. Bij elke stap kan het programma slagen of falen. Soms zijn er meer keuzes mogelijk voor het vinden van een oplossing. Dan keert het programma terug naar de programmatoestand die nog niet was onderzocht. Dat is backtracking.

Backtracking met feiten

In prolog beschrijf je een probleem. Een voorbeeld. Stel dat Jan, Piet en Klaas je vrienden zijn. Dat ziet er in Prolog bijvoorbeeld uit als volgt:

 class predicates
    eigenvriend:(string Vriend) determ (i) multi (o).
clauses
    eigenvriend("Jan").
    eigenvriend("Piet").
    eigenvriend("Klaas").

In dit simpele stukje code is de mogelijkheid tot backtracking al aanwezig. Ook al kun je dat niet zien. Als je wilt weten of Piet een vriend van je is, dan vraag je:

eigenvriend("Piet").

De compiler loopt nu regel voor regel de code af. "Jan" wordt afgewezen. Het programma vervolgt zijn weg en "Piet" wordt geaccepteerd. (Er vindt unificatie plaats). Deze gang van zaken lijkt nog zeer op conventionele, procedurele talen. De uitvoering volgt echter een boomstructuur met eigenvriend()/1 als wortel en "Jan", "Piet" en "Klaas" als bladeren.

Alle extra code heeft te maken met de programmastructuur en de gebruiker. Er staat commentaar ter verdere verduideliking.

predicates
    onTestVriend : window::menuItemListener.
clauses
    onTestVriend(_Source, _MenuTag) :-
        voorbeelden::eigenvriend("Piet"), % Is Piet mijn vriend?
        stdio::write("Ja","\n"), % Jan niet maar Piet wel
        !.
    onTestVriend(_Source, _MenuTag):-
        stdio::write("Nee","\n").

Wil je weten wie al je eigen vrienden zijn? Dan gebruiken we een variabele:

eigenvriend(X)

De compiler kijkt naar de clause eigenvriend()/1, ‌vindt "Jan" en slaagt. In onderstaande code krijgt de compiler opdracht om verder te zoeken, en vindt "Piet". Dit herhaalt zich. Als er geen vriend meer gevonden wordt is er sprake van falen. Dan zijn we klaar.

clauses
    onTestVrienden(_Source, _MenuTag) :-
        voorbeelden::eigenvriend(X), % Wie zijn mijn vrienden?
        stdio::write(X,"\n"),
        fail.% Ga terug voor de volgende vriend.
    onTestVrienden(_Source, _MenuTag) :- % Door boom gewandeld. We zijn klaar.
        stdio::write("Alle vrienden gevonden","\n").
        

Gebruik van feiten en regels

Laten we zeggen dat je uitgaat van de gedachte "De vrienden van mijn vrienden zijn ook mijn vrienden.". En de volgende feiten en regels toevoegt:

clauses
    vriendsvriend("Jan","Kees").
    vriendsvriend("Piet","Karel").
    vriendsvriend("Klaas","Jan").
    vriendsvriend("Klaas","Karel").

clauses
    allevrienden(X,Y) :- % Stuur voor X en Y gevonden waarden terug.
         eigenvriend(X),% Zoek eerst een eigen vriend
         vriendsvriend(X,Y). % Zoek dan een vriend van je eigen vriend

In clause allevrienden()/2 wordt bij elke persoonlijke vriend gezocht om te zien of deze vriend ook vrienden heeft. Dat is dan ook een vriend van jou.

Hier valt te ontwaren dat het executiemodel van een prologprogramma zelf een boomstructuur heeft. In dit geval met allevrienden()/2 als wortel en eigenvriend()/1 en vriendsvriend()/2) als kinderen.

clauses
    onTestAlleVrienden(_Source, _MenuTag):-
        voorbeelden::allevrienden(X,Y),
        stdio::write("Persoonlijke vriend ",X," ","en diens vriend ",Y,"\n" ),
        fail.
    onTestAlleVrienden(_Source, _MenuTag).

Een tweede voorbeeld met feiten en regels. Je bent een moeder indien je een vrouw bent en een ouder. Deze regel is ondergebracht in de clause moeder()/2. De compiler ziet dat Willem-Alexander wel een ouder van Amalia is maar geen vrouw. Maxima voldoet daaraan wel.

clauses
    vrouw("Amalia").
    vrouw("Alexia").
    vrouw("Ariane").
    vrouw("Maxima").
    vrouw("Beatrix").

clauses
    ouder("Willem-Alexander","Amalia").
    ouder("Maxima","Amalia").
    

clauses
    moeder(X,Y) :-
        ouder(X,Y),
        vrouw(X).

Als je wilt weten wie de moeder is van Amalia dan vraag je dus:

moeder(X,"Amalia"),

clauses
    onTestMoeder(_Source, _MenuTag) :-
        voorbeelden::moeder(X,"Amalia"),
        stdio::write(X, " ïs de moeder ", "Amalia\n"),
        !. % Klaar
    onTestMoeder(_Source, _MenuTag) :- % Door boom gewandeld, niet gevonden.
        stdio::write("Niet gevonden\n").

Link

De volgende link op youtube is een aardige illustratie van bovenstaand betoog: Een demo