This work is licensed under a
Creative Commons Attribution-NonCommercial-ShareAlike 4.0
International License.
Prolog was de eerste redelijk succesvolle poging om een programmeertaal te maken waarin logische regels de code vormen. De onderliggende simpele ( en verleidelijke ) visie voor deze programmeertaal is: de taak van een programmeur is het beschrijven van een probleem. De programmeur hoeft alleen maar ( in de taal van de logica ) een declaratieve beschrijving te geven van de situatie rond het probleem. De programmeur zou verder geen instructies hoeven te geven hoe de computer dat de oplossing van het probleem moet bereiken. Om de oplossing van het probleem te krijgen hoeft de programmeur slechts vragen te stellen. Het systeem, onderliggend aan de taal, moet zelf maar uitvinden hoe het tot het antwoord komt.
Dat is het idee en Prolog heeft al flinke stappen genomen om dit te realiseren.
p:- p.
We bekijken nogmaals (een deel van) onze oorspronkelijke afstammeling kennisbank (laten we dit afstammeling1.pl noemen):
Laten we verder gaan met het aanbrengen van veranderingen. In het volgende programma (afstammeling3.pl)
De op het oog kleine verandering van afstammeling2.pl naar afstammeling3.pl heeft dus procedureel rampzalige gevolgen. In Prolog terminologie hebben we hier een klassiek voorbeeld van een links recursieve clausule, ofwel een clausule waarin het meest linkse doel in de body gelijk is ( uitgezonderd de namen van de argumenten ) aan de head van de clausule. Ons voorbeeld heeft laten zien dat zulke links recursieve clausules makkelijk tot niet eindigende (non-terminating) berekeningen leiden. De volgorde van de doelen, in het bijzonder links recursief, kan de bron zijn van alle ellende wanneer er sprake is van non-termination.
We zijn er nog niet helemaal. Eerder hebben we opgemerkt dat we een klein voorbehoud moeten maken bij de volgorden van clausules. We zeiden dat de volgorde van clausules alleen de volgorde van de oplossingen verandert, maar gaat niet altijd op wanneer we met niet-eindigende clausules werken. Laten we eens naar het vierde ( en tevens laatste ) programma kijken (afstammeling4.pl).
Dus in het geval van niet-eindigende clausules kan de volgorde van de clausules tot antwoorden leiden. Alhoewel het hier toch ook de volgorde van de doelen is die echt bepalend is voor het verschil. De volgorde van de clausules blijft minder belangrijk. Om beëindiging te garanderen moeten we dus vooral aandacht geven aan de volgorde van de doelen in de body van de clausules.
Wat hebben we nu gezien? We hebben vier verschillende programma's gezien die precies de zelfde logica beschrijven, maar die door de procedurele stappen die Prolog uitvoert om vragen te beantwoorden heel verschillend kunnen werken. Het veranderen van de volgorde van clausules in de kennisbank heeft geen heel grote gevolgen (afstammeling1 en afstammeling2). Echter het veranderen van de volgorde van doelen in de body in een recursieve clausule kan desastreus aflopen (afstammeling3 en afstammeling4), bij het beantwoorden van een vraag kan Prolog in een oneindigende aanroep van de recursieve clausule komen.
Wat zijn de consequenties van onze discussie het produceren van werkende Prolog-programma's? Het is waarschijnlijk het beste om het volgende te zeggen. Vaak kunt je het algemene idee (het grote beeld) krijgen van hoe je het programma moet schrijven door declaratief te denken, dat wil zeggen door te denken in termen die het probleem nauwkeurig beschrijven. Dit is een uitstekende manier om problemen te benaderen, en zeker een manier die het meest in overeenstemming is met de geest van logisch programmeren. Maar als je dat eenmaal hebt gedaan, moet je nadenken over hoe Prolog procedureel gaat werken met kennisbanken die je hebt geschreven. In het bijzonder, om te zorgen voor beëindiging, moet je controleren of de door jou gegeven doelvolgorde verstandig is. De basisvuistregel is dat je nooit als het meest linkse doel van de body niet dezelfde clausule neemt als die in de head van de clausule. Plaats dergelijke recursieve doelen juist zo ver mogelijk rechts in de rij van doelen in de samengestelde head. Dat wil zeggen, plaats ze achter de doelen die testen voor de verschillende (niet-recursieve) beëindigingsvoorwaarden.
Ken je deze houten Russische poppetjes (Matryoshka poppetjes) waarin de kleinere
in de grotere passen? Rechts is een schematische weergave.
We hebben de volgende kennisbank:
Binaire bomen zijn bomen waar alle knopen precies nul of twee nakomelingen
hebben. De kleinste binaire boom heeft slechts één knoop deze knoop is dan zowel wortel als blad. We representeren
de uiteinden van de boom, ofwel de bladeren met het predicaat blad( Label ).
Bijvoorbeeld blad(3)en blad(7), zijn bladeren. Bladeren hebben nul nakomelingen,
maar kunnen wel uitbreiden door het blad te laten vallen en daar twee steeltjes met
nieuwe blaadjes voor in de plaats te zetten. Zie de figuur hiernaast.
Als we twee binaire bomen (B1 en B2)hebben kunnen we die als volgt combineren met de functor boom/2 : boom(B1,B2). Met de bladeren blad(1) en blad(2) kunnen we de binaire boom: boom(blad(1),blad(2)) maken. Deze kunnen we dan weer samenvoegen met blad(4) tot de boom: boom(boom(blad(1),blad(2)),blad(4)).
Maak nu een predicaat wissel/2, die het spiegelbeeld maakt van de binaire boom in het eerste argument en het resultaat plaatst in het tweede argument. Bijvoorbeeld: