dat je zonder recursieve regels eigenlijk niet kan programmeren in Prolog,
dat de declaratieve betekenis van een Prolog programma
niet altijd overeenkomt met de procedurele betekenis.
Recursie
In de cursussen
Javascript
en PhP hebben
we het concept herhaling ( = iteratie ) behandeld. In één functie wordt
een zelfde code meerdere malen herhaald :
<script>
// Voorbeeld javascript iteratie: het optellen van 1 t/m 100:
function som(begin,eind)
{
var antwoord=0;
for(var i=begin; i <= eind; i++ )
{
antwoord+=i;
}
return antwoord;
}
alert(som(1,100));
</script>
In Prolog is deze vorm van herhaling niet mogelijk. Vaak is het ook
in Prolog nodig om een stuk code meerdere malen achter elkaar uit te voeren.
Dit is te realiseren door gebruik te maken van recursie. Bij recursie
wordt er in een functie slechts één berekening gemaakt waarbij één element van
de berekening het antwoord is van de aanroep van de zelfde functie. Niet alleen
Prolog biedt deze mogelijkheid, in bijna alle andere talen kan dit ook. Het voorbeeld
hierboven in Javascript omgezet naar recursie is:
:
<script>
// Voorbeeld javascript recursie: het optellen van 1 t/m 100:
function somR(n,eind)
{
if(n >= eind) return eind;
else return n + somR(n+1,eind);
}
alert(somR(1,100));
</script>
Je ziet dat de functie somR niet direct de herhaling doet, maar dat het
herhalingsproces tot stand komt door het aanroepen van dezelfde functie binnen
de functie, ofwel recursie. Na dit uitstapje naar Javascript gaan we
recursie implementeren in Prolog. Maakt het Javascript voorbeeld voor jou
recursie nog niet helemaal duidelijk? Hopelijk ben je na de rest van dit
hoofdstuk helemaal op de hoogte. Misschien herken je het begrip recursieve formule
ook uit rijen en reeksen in de wiskunde: een volgende term in de rij wordt berekend met het huidige element in de rij.
Voorbeeld wiskunde: Voor de rij u : 2,4,6,8 , ... geldt:
recursieve definitie van de rij:
u(n+1) = u(n) + 2; u(1) = 2 ; n = 1,2,3, ...
directe formule;
u(n)= 2 n; n = 1,2,3, ...
recursieve definities
Terug bij Prolog. Recursie kan alleen plaatsvinden in clausules (rules, clausules).
Predicaten kunnen recursief worden gedefinieerd. Kort door de bocht, een predicaat is recursief gedefinieerd als één of meerdere clausules naar zichzelf refereren.
In de vragen bij
les 2: elementen
heb je recursie al
een keer gezien. We bekijken nog een paar voorbeelden waarin we uitleggen
hoe een en ander werkt.
Op het eerste gezicht lijkt dit niet erg nieuw: het is gewoon een kennisbank
met drie feiten en twee regels. Maar de definitie van de tweede clausule van het
predicaat is_aan_het_verteren/2 is recursief. Je ziet namelijk dat in de body van is_aan_het_verteren/2, is_aan_het_verteren/2 weer aanwezig is. Dit zou in principe tot een oneindige
serie van aanroepen van is_aan_het_verteren/2 kunnen leiden (vergelijk de wiskundige
rij hierboven). Echter in de informatica moeten de meeste recursieve processen eindig of
te beëindigen zijn. Er moet dus altijd een ontsnappingsmogelijkheid aanwezig zijn
voor een goed werkend programma.
In ons voorbeeld is dat de eerste clausule van het
predicaat is_aan_het_verteren/2 (Bepalend is dat in de eerste clausule
is_aan_het_verteren/2 niet in de body aanwezig is ). We bekijken nu de declaratieve en procedurele
betekenis van deze definitie.
Het woord declaratief wordt gebruikt om te praten over de logische betekenis van
Prolog kennisbanken. De declaratieve betekenis van een Prolog kennisbank is eenvoudig
wat het zegt of wat het betekent, als we het lezen als een verzameling
van logische beweringen. De declaratieve betekenis van de recursieve definitie
is recht toe recht aan. De eerste clausule zegt (de niet recursieve die we ook wel de
basis clausule noemen): als X net Y heeft gegeten, dan is X nu Y aan het verteren. Dit
is natuurlijk een zinvolle definitie.
De tweede clausule ( de recursieve ) zegt: Als X net Z heeft gegeten en Z is Y aan het
verteren dan is X ook Y aan het verteren. Ook weer een zinvolle definitie.
We weten nu wat het hele predicaat is_aan_het_verteren/2 ons verteld, maar
wat gebeurt er als we een vraag stellen met deze definitie, ofwel hoe wordt deze
vraag door Prolog beantwoord, een procedurele bewerking.
In de Prolog terminologie is dit: wat is de procedurele betekenis?.
Ook de procedurele betekenis is recht toe recht aan. De definitie van de
basis clausule heeft precies de zelfde vorm als die van clausules die we
eerder hebben gezien. Als we vragen of X Y aan het verteren is, gebruikt Prolog deze
regel om de vraag om te zetten naar de vraag: heeft X net Y opgegeten?
Recursie in beeld
Als X niet Y heeft gegeten dan gaat Prolog naar de tweede clausule en
stelt dan de vraag
of X net Z heeft opgegeten en als Z Y aan het verteren is dan verteert X ook Y.
De tweede clausule wordt dus met twee subvragen beantwoord. Hopelijk eindigt het proces
van vragen stellen in het stellen van vragen waarvan de antwoorden
direct opgezocht kunnen worden in de feiten van de kennisbank.
De figuur hiernaast geeft een grafisch beeld van de situatie.
De vraag of Z Y aan het eten is, wordt dan ook eerst weer door de eerste clausule beantwoord,
ofwel heeft Z Y net opgegeten? Ook nu kan het weer zo zijn dat Z een ander beest heeft
gegeten dat Y al aan het verteren is, enzovoorts.
We gaan eens kijken hoe dit voorbeeld werkt.
Kopieer de bovenstaande kennisbank naar SWISH en stel eens de volgende vraag.
?- is_aan_het_verteren(ooievaar,mug).
Het antwoord hierop is true. Prolog heeft deze conclusie als volgt getrokken.
Eerst wordt de eerste (de basis) clausule aangeroepen, simpel omdat dit de eerste
clausule is die aanwezig is. Prolog zet dit om naar de vraag
?- net_gegeten(ooievaar,mug).
Het antwoord op deze vraag is false, want dit feit is niet in de kennisbank aanwezig.
Backtracking zorgt er dan voor dat Prolog de tweede clausule van is_aan_het_verteren/2
gaat beantwoorden. Deze wordt omgezet naar de samengestelde vraag
Prolog moet nu in kennisbank op zoek naar een Z die zowel de vragen
?- net_gegeten(ooievaar,Z).
en
?- is_aan_het_verteren(Z,mug).
positief beantwoord. En gelukkig als Z gelijk wordt gemaakt aan kikker dan
is het duidelijk dat
net_gegeten(ooievaar,kikker)
waar is en kan de vraag
?- is_aan_het_verteren(kikker,mug).
worden omgezet in de vraag
?- net_gegeten(kikker,mug).
die ook weer feitelijk waar is.
Dit was ons eerste voorbeeld van een predicaat dat recursief is gedefinieerd.
Voor we nog meer over recursieve clausules leren maken we nu eerst een praktische
opmerking. Hopelijk is het uit het bovenstaande duidelijk dat als je een recursief
predicaat schrijft, je altijd minstens twee clausules nodig hebt. Één basis clausule
waarmee je de recursie kan stoppen en één die de recursie bevat. Als je alleen
de recursieve clausule maakt dan kan Prolog eindeloos doorgaan met aanroepen van die
recursie. Een voorbeeld van zo'n een slechte kennisbank is:
p :- p.
Dat is alles. Niets meer. Het is mooi door de eenvoudigheid ervan. Vanuit een declaratief
standpunt niet eens zo onzinnig omdat het zegt: "Als eigenschap p waar is dan volgt daar
uit dat eigenschap p waar is". Niets tegen in te brengen.
Procedureel gezien is dit een beestachtig gevaarlijke clausule. Dit is namelijk
de uiterste van de gevaarlijke recursieve clausules: precies het zelfde ding aan
beide zijden van de nek en geen basis clausule om te ontsnappen. Bedenk maar eens
wat er gebeurd als we de volgende vraag stellen
?- p.
Prolog vraagt aan zichzelf: "Hoe bewijs ik p" en trekt de conclusie: "Hé daar
heb ik een clausule voor! Om te bewijzen dat p waar is met ik alleen maar te bewijzen
dat p waar is." Dus moet het weer aan zichzelf vragen: "Hoe bewijs ik p" en trekt de weer de conclusie: "Hé daar
heb ik een clausule voor! Om te bewijzen dat p waar is met ik alleen maar te bewijzen
dat p waar is." Dus moet het weer aan zichzelf vragen: "Hoe bewijs ik p" en trekt de weer de conclusie: "Hé daar
heb ik een clausule voor! Om te bewijzen dat p waar is met ik alleen maar te bewijzen
dat p waar is." En zo maar door.
Als je deze vraag stelt in Swish krijg je geen antwoord. Uiteindelijk zal je de vraag
moeten afbreken.
Voorbeeld 2: Afstammeling
Nu we iets weten van recursie in Prolog wordt het tijd om ons af te vragen waarom
het zo belangrijk is. Deze vraag kan op verschillende niveaus in Prolog programmeren worden beantwoord, maar hier houden we het redelijk praktisch. Hier beantwoorden we
de vraag: Als we iets zinnigs in Prolog willen programmeren is recursie
dan werkelijk zo belangrijk? En zo ja waarom?
Zoals altijd verduidelijken we de vraag en het antwoord met een voorbeeld. We bekijken
weer de kennisbank van geboorten uit les 1 en gaan
dan uitleg geven over de vragen uit les 2. We pakken
een paar feiten uit de kennisbank:
kindVan(geert,harry).
kindVan(harry,johan).
Deze feiten zeggen dat Geert een kind van Harry is en dat Harry een kind van Johan is.
Als nu een afstammelingsrelatie in onze kennisbank willen aanbrengen dan is Geert een
afstammeling van zowel Harry (= vader) als Johan (= opa). Met deze twee feiten
kunnen we op de volgende manier, nog zonder recursie,
clausules opstellen die deze afstammelingsrelatie weergeven (probeer uit in Swish):
Voor relaties t/m grootouder (oma/opa) gaat dit goed,
(Stel maar eens de vraag ?- is_afstammeling_van(geert,johan).)
maar als we nog verder terug
gaan in de tijd (overgrootouder, betovergrootouder, ...)
dan gaat onze eerste afstammelingsrelatie mis.
Geert is duidelijk een afstammeling van Carola,
maar de vraag ?- is_afstammeling_van(geert,carola).
wordt negatief beantwoord. Nu kunnen we natuurlijk meerdere versies zoals clausule 2 maken
om Geert een afstammeling van Carola te laten zijn, maar waar en waarom stop je?
Behalve dat je niet weet hoe diep je in een stamboom terug zal moeten is het
geen mooie en efficiënte oplossing. We kunnen de diepgang in de stamboom rustig
naar Adam en Eva
terugvoeren (of nog verder gaan als evolutie jouw ding is) met slechts twee clausules,
maar dan kunnen we niet zonder recursie.
Elegant hè! De declaratieve betekenis van de basis clausule is:
Als X een kind van Y is dan is X een afstammeling van Y. De recursieve
clausule zegt: Als X een kind van Z is en Z is een afstammeling van Y dan is
X een afstammeling van Y. Een waarheid als een koe!
We bekijken weer hoe Prolog de vraag ?- is_afstammeling_van(geert,carola). beantwoordt.
Het onderstaande diagram geeft de boom weergave van de procedure van de zoektocht die we hier stap voor stap toelichten. Eerst kijkt Prolog of de basis clausule (de eerste in de lijst) geldt en vertaalt de vraag
?- is_afstammeling_van(geert,carola).
naar de vraag
?- kindVan(geert,carola).
Omdat kindVan(geert,carola) geen deel uitmaakt van de feiten in de kennisbank loopt dit pad
dood. Prolog gaat via backtracking naar de tweede (recursieve) clausule en
vertaalt de vraag
Het eerste feit dat Prolog tegenkomt waarin Geert een kind is van iemand is het feit
kindVan(geert,harry).
Dus de variabele _633 wordt gelijkgesteld aan harry waardoor het
eerste deel van de samengestelde vraag waar is en Prolof het tweede deel van de
samengestelde vraag
?- is_afstammeling_van(harry,carola).
moet beantwoorden. Eerst wordt nu weer de basis clausule gekozen om de vraag
te beantwoorden en deze wordt omgezet naar de vraag
?- kindVan(harry,carola).
Omdat kindVan(harry,carola) geen deel uitmaakt van de feiten in de kennisbank loopt dit pad
dood. Prolog gaat via backtracking weer naar de tweede (recursieve) clausule en
vertaalt de vraag
Het eerste feit dat Prolog tegenkomt waarin Harry een kind is van iemand is het feit
kindVan(harry,johan).
Dus de variabele _733 wordt gelijkgesteld aan johan waarna de vraag
?- is_afstammeling_van(johan,carola).
moet worden beantwoord. Weer wordt eerst de basis clausule gekozen om de vraag
te beantwoorden en deze wordt omgezet naar de vraag
?- kindVan(johan,carola).
Omdat kindVan(johan,carola) weer geen deel uitmaakt van de feiten in de kennisbank
loopt dit pad ook weer
dood. Prolog gaat via backtracking weer naar de tweede (recursieve) clausule en
vertaalt de vraag
Het eerste feit dat Prolog tegenkomt waarin Johan een kind is van iemand is het feit
kindVan(johan,henk).
Dus de variabele _833 wordt gelijkgesteld aan henk waarna de vraag
?- is_afstammeling_van(henk,carola).
moet worden beantwoord. Dus weer naar de basis clausule met de vraag
kindVan(henk,carola).
.
Nu is er wel het feit kindVan(henk,carola) dus kan Prolog de vraag
?- is_afstammeling_van(geert,carola). dus positief beantwoorden.
In les 4 heb je deze boom structuur van de zoektocht (tree search)
ook al gezien. Zorg ervoor dat je dit concept in het beantwoorden van vragen echt begrijpt.
Boomstructuur zoektocht
Dit voorbeeld zou je nu duidelijk moeten hebben gemaakt dat het niet uitmaakt hoeveel
opeenvolgende generaties er in de kennisbank aanwezig zijn. Alleen bij een "missing link"
gaat het natuurlijk mis. De recursieve formule is zo algemeen en zo compact dat het
duidelijk is dat het moet werken.
Recursieve clausules zijn zeer belangrijk. Ze staan je toe om heel veel informatie
in een compacte en natuurlijke manier te definiëren. Als je Prolog programmeert zul
je meestal bezig zijn met het schrijven van recursieve formules.
Voorbeeld 3: Opvolger
In les 3 hebben we laten zien dat Prolog programmeren is gebaseerd
op unificatie en de bewijsvoering wordt vastgelegd door de structuur van het aanbieden
van de clausules. Nu we recursie kennen kunnen we interessantere voorbeelden van ditsoort structuren geven.
Tegenwoordig schrijven mensen gehele getallen in een tientallig stelsel (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, enz.) maar er zijn, zoals je waarschijnlijk weet, vele andere notaties.
Bijvoorbeeld computers, omdat ze zijn opgebouwd op uit/aan (0/1) elektronische schakelaars,
gebruiken een binaire (tweetallig) getalsysteem (bovenstaande rij wordt dan 0, 1, 10, 11,
100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, enz). Andere culturen gebruiken nog weer
andere getal systemen. De oude Babyloniers gebruikten een 60-tallig stelsel. De Romeinen
maakten er eigenlijk een beetje een rommeltje van, voor 5 (V), 10 (X), 50 (L),100 (C), 500 (D) en 1000 (M) zijn er verschillende symbolen en de volgorde is ook niet recht toe recht aan
zo is 999 gelijk aan CMXCIX (terugwerkend) en 888 DCCCLXXXVIII (altijd vooruit). Niet echt handig die Romeinen. Verzin maar eens een systematische manier voor staartdelen in de Romeinse
getal notatie. Je zult al snel merken dat dit heel lastig is. Waarschijnlijk hadden de
Romeinen daar specialisten voor.
Hier presenteren we nog een manier om getallen te schrijven die soms wordt gebruikt
in de wiskundige logica en ook in de getaltheorie. (Ook het wiskundige voorbeeld boven in dit
hoofdstuk zouden we hier kunnen gebruiken) De manier gebruikt slechts vier symbolen: 0, opvolger, en
de linker en rechter haakjes.
De getallen wordt dan gedefinieerd met behulp van inductie:
0 is een getal
Als X een getal is, dan is opvolger(X) dat ook.
.
Opvolger(X) is dan het getal dat je krijgt door één bij X op te tellen. Deze
definitie zegt dus dat 0 een getal is en dat alle andere getallen kunnen worden
gemaakt door opvolger er voor te zetten. ( In de getaltheorie definieer dus op deze
manier alle natuurlijke getallen en is oneindigheid ook bewijsbaar).
Hé denk je nu, deze definitie kunnen julle vast omzetten in een Prolog programma met behulp van recursie. De volgende kennisbank is het resultaat
getal(0).
getal(opvolger(X)) :- getal(X).
.
Stellen we een vraag als
getal(opvolger(opvolger(opvolger(0)))).
dan krijgen we het antwoord true.
We kunnen ook interessantere vragen stellen.
Wat gebeurd er bij de vraag :
getal(X).
We vragen hier eigenlijk "Hé geef eens een paar getallen".
De eerste 8 regels van het resultaat zijn dan
X = 0
X = opvolger(0)
X = opvolger(opvolger(0))
X = opvolger(opvolger(opvolger(0)))
X = opvolger(opvolger(opvolger(opvolger(0))))
X = opvolger(opvolger(opvolger(opvolger(opvolger(0)))))
X = opvolger(opvolger(opvolger(opvolger(opvolger(opvolger(0))))))
X = opvolger(opvolger(opvolger(opvolger(opvolger(opvolger(opvolger(0)))))))
X = opvolger(opvolger(opvolger(opvolger(opvolger(opvolger(opvolger(opvolger(0))))))))
Prolog is inderdaad aan het tellen, maar belangrijker is hoe doet Prolog dit.
Simpel gezegd, Prolog is aan het backtracken door de recursieve clausule en maakt getallen
door gebruik te maken van unificatie. Dit is een leerzaam voorbeeld en het is belangrijk dat
je het begrijpt. Gebruik je het swi-prolog programma dan kun je met het trace commando
van Prolog reconstrueren. Hier onder zie je weer een boomstructuur van de zoektocht. Als je de trace (klik op dit pad) vergelijkt
met de figuur dan zie je dat de "Redo" commando's verder gaan bij het laatste keuzepunt, de splitsing van twee takken, direct voorafgaand aan laatst gegeven antwoord in de boom.
Ofwel nog een keer backtracking in beeld.
Bouwen en gelijkstellen.
Recursie, unificatie en de zoektocht naar bewijs. Dit
zijn de basisideeën die deel uit maken van de kern van Prolog programmeren.
Telkens
wanneer we recursief gestructureerde objecten moeten maken of analyseren
(zoals bijvoorbeeld de gehele getallen) vormt het samenspel van deze ideeën ervoor
dat Prolog een krachtig instrument is om deze taken te verrichten. In het
hoofdstuk waar de lijsten ( Lists, rijen ), nog een erg belangrijke
component van Prolog, worden geïntroduceerd en in de hoofdstukken over taalverwerking
zal deze mix weer de belangrijkste taak krijgen.
Vele applicaties (waarvan computationele linguïstiek het belangrijkste voorbeeld is)
maken vooral gebruik van recursief gestructureerde objecten ( b.v. bomen en lijsten).
Voorbeeld 4: Optellen
Als laatste voorbeeld voegen we enkele rekenkundige bewerkingen toe aan het vorige
voorbeeld. Laten we eens proberen om optellen te definiëren. We willen dan
het predicaat telop/3 aan de kennisbank toevoegen. De eerste twee argumenten
van dit predicaat worden de twee op te tellen getallen en het derde argument gaat
uiteindelijk het antwoord bevatten. We willen dus een vragen kunnen stellen
als
?- telop( opvolger(opvolger(0)),
opvolger(0),
opvolger(opvolger(opvolger(0)))).
True
?- telop( opvolger(opvolger(0)),
opvolger(opvolger(0)),
opvolger(opvolger(opvolger(0)))).
False
?- telop( opvolger(opvolger(0)),
Y,
opvolger(opvolger(opvolger(0)))).
Y = opvolger(0)
Er zijn twee belangrijke eigenschappen van optellen die we hierin moeten
meenemen om de basis clausules op te stellen.
Als we 0 + 0 willen berekenen (de eerste twee argumenten zijn 0)
dan moet het antwoord ook 0 worden.
?- telop(0,0,Y).
Y = 0
Als we 0 bij een ander getal willen optellen (
één van de eerste twee argumenten is 0)
dan moet het antwoord het niet 0 argument zijn.
?- telop(0,opvolger(opvolger(0)),Y).
Y = opvolger(opvolger(0))
?- telop(opvolger(opvolger(0)),0,Y).
Y = opvolger(opvolger(0))
Stel nu dat we twee getallen X en Y willen optellen
( b.v. X = opvolger(opvolger(opvolger(0))) en Y = opvolger(opvolger(0))) en X en Y zijn
beide niet 0. Als we X1 definiëren als het getal dat één opvolger functor minder heeft
dan X ( X1 = opvolger(opvolger(0)) in ons voorbeeld ) en als we het resultaat van
de optelling van X1 en Y weten ( noem die Z ), dan is het makkelijk om de uitkomst van
de optelling van X en Y recursief te definiëren: we hoeven slechts één opvolger functor
toe te voegen aan Z. De hele definitie van het optel predicaat wordt dan
telop(0,Y,Y).
telop(opvolger(X),Y,opvolger(Z)) :- telop( X, Y, Z).
Wat gebeurt er nu als we onze getal kennisbank uitbreiden met deze definitie
en de volgende vraag stellen?
We gaan stap voor stap door de procedurele betekenis van deze vraag heen.
De trace van de zoektocht naar R is en de boomstructuur R is weergegeven
in de figuur hieronder. Onder deze figuur lichten we de stappen toe.
Het eerste argument in de vraag is niet 0. Dus de recursieve clausule wordt genomen
en de variabele R wordt gelijkgesteld aan de tijdelijke variabele
_1002 ( trace: Call: (8)) die op dit moment nog geen waarde heeft (= onbepaald ),
dit zorgt er ook voor dat R op dit moment nog onbepaald is.
De volgende stap is dat we de head van de vraag in Call:(8) gaan omzetten naar de
bewering uit de body van de recursieve formule ( trace: Call: (9)). Er wordt dan een functor opvolger
van het eerste argument weggehaald, het tweede argument blijft hetzelfde. Het derde argument
wordt weer een tijdelijke onbepaalde variabele _1240 waarvoor geldt _1002 = opvolger(_1240).
De calls 9, 10 en 11 worden op vergelijkbare manier opgebouwd, echter
de vraag in Call 11, kan worden beantwoord met de basis clausule. De variabele _1248
wordt op dat moment gelijkgesteld (geünificeerd) met Y ofwel
_1248 = opvolger(opvolger(0))
en dus zijn nu ook _1244, _1240, _1002 en R bepaald":
In de boomstructuur zie je de stap voor stap toewijzing van de variabelen
naast de verbindingslijnen.
Je ziet dat ook de optelling weer op een mooie compacte en recursieve manier
kan worden gedefinieerd.
Probeer eens het predicaat kleinerOfGelijkAan/2 te maken met X en Y de argumenten
waarvan bepaald moet worden of X kleiner of gelijk aan Y is. We geven je alvast de
basisclausule
kleinerOfGelijkAan(0,Y).
Deze basisclausule zegt dat wat Y ook is 0 is altijd kleiner of gelijk.
Wat moet de recursieve clausule zijn? Geef ook de zoektocht
naar het antwoord op de vraag ?- kleinerOfGelijkAan(opvolger(opvolger(0)),
opvolger(opvolger(0))). weer in
een boomvorm.
Antwoord
Het hele predicaat moet zijn
Waarom werkt dit? Wel als je de in de recursie van zowel van het eerste als
van het tweede argument de functor opvolger afhaalt, dan worden beide
getallen één kleiner.
Recursie kleinerOfGelijkAan in beeld
Het predicaat groterOfGelijkAan/2 met X en Y de argumenten
waarvan bepaald moet worden of X groter of gelijk aan Y is heel simpel
en volledig in één clausule te definiëren als
Waarom?
Antwoord
Fantastisch hè! Dit kan omdat wiskundig geldt: X ≤ Y dan is Y ≥ X.
Het predicaat kleiner/2 met X en Y de argumenten
waarvan bepaald moet worden of X kleiner is dan Y is ook heel simpel
en volledig in één clausule te definiëren als
Waarom?
Antwoord
Dit kan omdat wiskundig geldt: X + 1 ≤ Y dan is X < Y.
Wat moet dan het predicaat groter/2 met X en Y de argumenten
waarvan bepaald moet worden of X groter is dan Y?
Antwoord
groter(X,Y) :- groterOfGelijkAan(X,opvolger(Y)).
Dit kan omdat wiskundig geldt: X ≥ Y + 1 dan is X > Y.
Probeer eens het predicaat vermenigvuldig/3 te maken met X en Y de eerste
twee argumenten en het antwoord komt in het derde argument.
waarvan bepaald moet worden of X kleiner of gelijk aan Y is. We geven je alvast twee
basisclausules
De eerste basisclausule zegt dat wat Y ook is 0 keer iets is 0.
De tweede basisclausule zegt dat wat Y ook is 1 keer iets is iets.
Wat moet de recursieve clausule zijn? Bedenk dat 4 × 3 = 3 + 3 + 3 + 3.
Gebruik dus ook telop/3.
De vraag ?- vermenigvuldig(opvolger(opvolger(0)),
opvolger(opvolger(opvolger(0))),R). moet geven
R = opvolger(opvolger(opvolger(opvolger(opvolger(opvolger(0))))))
Antwoord
Waarom lukt het niet om met het huidige predicaat telop de
vraag
?- telop(opvolger(opvolger(0)),Y,opvolger(0)).
op te lossen en waarom geeft het volgende predicaat wel het juiste antwoord (false)
telop(0,Y,Y).
telop(opvolger(X),Y,opvolger(Z)) :-
kleinerOfGelijkAan(opvolger(X),opvolger(Z)),
kleinerOfGelijkAan(Y,opvolger(Z)),
telop( X, Y, Z).
Antwoord
De getallen analoog van de vraag is
telop(2,Y,1). Y moet ook bestaan uit opvolgers van 0 en dat kan niet want
het antwoord moet getalswaarde -1 hebben. In de eenvoudige versie van telOp gaat Prolog al in de fout bij 0. Terugkerend naar de plek kan Prolog alleen
samenstellingen van opvolger(0) maken en gaat daar eindeloos mee door.
Het nieuwe predicaat controleert eerst of het eerste argument kleiner of gelijk aan het derde argument, als dit niet zo is kan er geen antwoord
worden gevonden. Ook de tweede check zorgt ervoor dat het derde argument groter of gelijk is aan het tweede.
Tegenwoordig schrijven mensen gehele getallen in een tientallig stelsel (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, enz.) maar er zijn, zoals je waarschijnlijk weet, vele andere notaties.
Bijvoorbeeld computers, omdat ze zijn opgebouwd op uit/aan (0/1) elektronische schakelaars,
gebruiken een binaire (tweetallig) getalsysteem (bovenstaande rij wordt dan 0, 1, 10, 11,
100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, enz). Andere culturen gebruiken nog weer
andere getal systemen. De oude Babyloniers gebruikten een 60-tallig stelsel. De Romeinen
maakten er eigenlijk een beetje een rommeltje van, voor 5 (V), 10 (X), 50 (L),100 (C), 500 (D) en 1000 (M) zijn er verschillende symbolen en de volgorde is ook niet recht toe recht aan
zo is 999 gelijk aan CMXCIX (terugwerkend) en 888 DCCCLXXXVIII (altijd vooruit). Niet echt handig die Romeinen. Verzin maar eens een systematische manier voor staartdelen in de Romeinse
getal notatie. Je zult al snel merken dat dit heel lastig is. Waarschijnlijk hadden de
Romeinen daar specialisten voor.
