Unificatie

We hebben in de vorige hoofdstukken al vragen in Prolog gesteld aan onze kleine kennisbanken. Bij deze vragen kreeg je een antwoord, True of False, bij vragen met een variabele kreeg je ook mogelijke waarden die in de kennisbank aanwezig zijn, b.v. persoon(karin,vrouw). (True) en persoon(Naam, man). (True, Naam = geert) . In het laatste geval heeft Prolog het atoom geert toegekend aan de variabele Naam.
Omdat de basis van Prolog het vinden waarheden is in een programma voorzien van feiten en regels, staan we in dit hoofdstuk wat langer stil bij de essentie van die waarheden en hoe je die op de juiste manier moet ordenen om tot uitspraken te kunnen komen.

We beginnen met de uitleg van de term Unificatie (Unification) in Prolog.

Haal nog even de mogelijke termen op uit je geheugen:

Constanten. Dit waren getallen (b.v. 59) of atomen (b.v. geert).
Variabelen. (b.v. Naam, X, Klas )
Samengestelde termen. (b.v. persoon(karin,vrouw), algemeen functor(term1,term2,...))

Met deze termen in gedachten geven we een eerste, nog niet heel precieze, definitie van unificatie:
Unificatie is het proces waarin wordt getracht twee termen in balans te brengen, zijn ze gelijk of zijn ze gelijk te maken. Ofwel: twee termen unificeren als ze gelijk zijn of als ze variabelen bevatten die een term als waarde kan worden gegeven zodat uiteindelijk de overgebleven termen gelijk zijn.

Dit betekent bijvoorbeeld dat de termen geert en geert unificeren omdat ze gelijk zijn. Evenzo unificeert 59 met 59 (zelfde getal) en persoon(karin,vrouw) met persoon(karin,vrouw) (zelfde samengestelde term). Echter geert unificeert niet met johan, 59 niet met 61 en persoon(karin,vrouw) niet met persoon(sylvia,vrouw), want de termen zijn niet gelijk.

Hoe zit het met de termen Naam en sylvia? Als je de term unificatie al begrijpt zeg je gelijk "die twee termen unificeren want ik kan de variabele Naam de waarde sylvia geven. sylvia en sylvia unificeren dus ook Naam en sylvia unificeren.". Ook kindVan(geert,harry) en kindVan(geert,X) unificeren want aan X kan de waarde harry worden toegekend. Kunnen de termen kindVan(geert,X) en kindVan(X,patrick) unificeren? Nee dit kan niet, in de kennisbank is geen waarde voor X te vinden zodat X zowel een ouder is van geert als een kind van patrick. X zou de waarde harry of louise kunnen krijgen om kindVan(geert,X) waar te maken, echter zowel kindVan(harry,patrick) en kindVan(louise,patrick) zijn geen feiten in de kennisbank.

In het algemeen zijn we niet alleen geïnteresseerd in het feit dat twee termen unificeren, maar willen we ook weten welke waarden we variabelen moeten geven om unificatie mogelijk te maken. De kracht van Prolog is dat het antwoorden op dit soort vragen kan geven. Wanneer Prolog twee termen unificeert, geeft het waarden aan de variabelen zodat de termen achteraf echt gelijk zijn. Prolog kan deze zoektocht over meerdere (complexe) regels in een programma uitvoeren en is daardoor uitermate geschikt om op regels gebaseerde problemen te analyseren.

Waarschijnlijk heb je nu wel een beetje een gevoel wat unificatie is. Hieronder vindt je de precieze definitie van de unificatie regels in Prolog:

Als term1 en term2 constanten zijn dan unificeert term1 met term2 als en alléén als ze het zelfde atoom of het zelfde getal zijn.
Als term1 een variabele is en term2 is van een willekeurig type, dan unificeert term1 met term2, en heeft term1 de waarde term2. Evenzo als term2 een variabele is, dan unificeert term1 met term2, en heeft term2 de waarde term1. (Als term1 en term2 beide variabelen zijn, krijgen ze de waarde van elkaar, we zeggen dat ze een waarde delen.)
Als term1 en term2 complexe termen zijn dan unificeren ze als en alléén als ze dezelfde functor en ariteit hebben en alle overeenkomstige argumenten paarsgewijs unificeren, en waarden van variabelen éénduidig zijn. (Zie het voorbeeld kindVan() hierboven.)
Twee termen unificeren als en alléén als dit uit één van de drie bovenstaande regels volgt.

De vierde regel kunnen we niet weglaten. De regel vertelt ons dat als unificatie niet lukt op basis van één van de regels 1 t/m 3 er geen mogelijkheid tot unificatie van de twee termen mogelijk is. Bijvoorbeeld: geert unificeert niet met kindVan(geert,harry). Waarom niet? Wel, de eerste term is een constante en de tweede term een complexe term. Regel 1 kunnen we niet toepassen omdat de tweede term geen constante is. Regel 2 kunnen we niet toepassen omdat er geen variabele aanwezig is. Regel 3 niet omdat term1 geen complexe term is. Gelukkig hebben we dan regel 4, die zegt dat er dan toch iets mis moet zijn en er geen unificatie is.

Voorbeelden

Om er zeker van te zijn dat we deze definitie volledig snappen, gaan we een aantal voorbeelden bekijken. In deze voorbeelden gebruiken we het in Prolog ingebouwde predicaat (regel) =/2 (Je weet hopelijk nog dat /2 betekent dat het predicaat twee argumenten nodig heeft).

Gebruik weer SWISH om de voorbeelden na te spelen. Gebruik zo nodig de kennisbank uit les1.

Het predicaat =/2 test of twee termen unificeren. De vraag

?- =(geert,geert).

levert true als antwoord en de vraag

?- =(geert,harry).

levert false als antwoord.

Meestal stellen we deze vraag niet op deze nog al onnatuurlijke manier. Het is veel mooier als we het = teken tussen de twee termen zouden mogen zetten. Dit kan (deze manier van schrijven noemt men dan de infix notatie voor predicaat =/2)! Dus bovenstaande vragen worden dan

?- geert = geert. en ?- geert = harry.

Waarom geeft Prolog true als antwoord bij de vraag ?- geert = geert.? Dit lijkt een stomme vraag, natuurlijk unificeren deze twee termen, maar op basis van welke regel uit de bovenstaande definitie? Het is heel belangrijk om systematisch over unificatie na te denken (want unificatie is de basis van Prolog), dit houdt in dat we alle voorbeelden koppelen aan de vier bovenstaande regels.

Dus nog een keer de vraag: Waarom geeft Prolog true als antwoord bij de vraag ?- geert = geert.?
Regel 1 geeft al gelijk uitsluitsel, geert en geert zijn gelijke atomen en dus gelijke constanten en dus unificeert geert met geert.

Dezelfde redenering verklaart het resultaat van de vragen:

?- 2 = 2. True ?- geert = harry. False

In beide gevallen gaat het hier om constanten en is regel 1 van toepassing om de conclusie te trekken dat de eerste vraag true levert, want twee gelijke getallen, en de tweede vraag false, want twee niet gelijke atomen.

Regel 1 heeft nog wel iets verrassends:

?- geert = 'geert'. True

Blijkbaar beschouwt Prolog het atoom geert en het atoom 'geert' als identiek. Soms is dit handig maar het gaat mis bij

?- '2' = 2. False

want '2' is een atoom en 2 een getal. Ook bij de vraag voor het atoom 'Henk' gaat het niet volgens regel 1. Laten we hier de aanhalingstekens weg dan is Henk een variabele en geen atoom. Nu geeft

?- Henk = 'Henk'. Henk = 'Henk' True

Maar niet omdat regel 1 geldt. Term 1 Henk is een variabele die we kunnen unificeren door Henk de waarde 'Henk' te geven en deze waarde is gelijk aan term 2 'Henk'. Dit is precies wat regel 2 in dit geval eist en dus unificeren Henk en 'Henk'. Ook X en sylvia unificeren om dezelfde reden

?- sylvia = X. X = sylvia

Nu een belangrijk voorbeeld: Wat gebeurt er bij de vraag

?- X=Y.

Swish geeft terug

X=Y True

Niet in alle Prolog versies krijg je dit antwoord. Het kan ook zijn dat het antwoord iets is in deze vorm:

X = _5071 Y = _5071

Wat gebeurt er hier? In essentie is dit het zelfde. _5071 is een variabele (begint met een lage min). Regel 2 zegt als twee variabelen unificeren, dan delen ze dezelfde waarde. Prolog heeft een nieuwe variable _5071 gemaakt en X en Y delen vanaf dit moment de waarde van deze nieuwe variabele. Het nummer 5071 had natuurlijk net zo goed een ander nummer kunnen zijn.

Nog een voorbeeld met variabelen en atomen. Het antwoord op de vraag

?- X = geert, X = harry. False

komt als volgt tot stand. Het ,/2 predicaat is het en (and) predicaat en A,B is True alleen als A de waarde True heeft en B de waarde True. Hier scheidt de komma twee doelen, het unificeren van X en geert en tegelijkertijd het unificeren van X en harry. Ieder doel afzonderlijk is te unificeren, maar als X, op basis van regel 2, de waarde geert krijgt toegewezen in het linker doel, dan is dat ook de waarde die met harry moet unificeren in het rechter doel. Echter X is nu harry en volgens regel 1 unificeren harry en geert niet.

Tijd voor een voorbeeld met complexe termen:

?- k(s(g),Y) = k(X,t(m)). X = s(g), Y = t(m)

Het is duidelijk dat we hier te maken hebben met complexe termen, dus we beginnen gelijk met regel 3. Hebben de twee termen de zelfde functor, ja beide k, de zelfde ariteit, ja beide twee, en unificeren de argumenten paarsgewijs? Wel s(g) en X unificeren volgens regel 2, want X is een variabele die we de waarde s(g) kunnen geven. Om dezelfde reden lukt dit voor Y en t(m).

Nog een voorbeeld met complexe termen:

?- p(q(g,h), r(f)) = p(X,r(Y)). X = q(g,h), Y = f

Kun je nu stap voor stap uitleggen waarom hier sprake is van unificatie? Antwoord
Complexe termen dus op naar regel 3.

Zelfde functor? Ja, p.
Zelfde ariteit? Ja, twee.
Unificeren q(g,h) en X? Ja volgens regel 2 unificeren deze twee termen en wordt X gelijk aan q(g,h).
Unificeren r(f) en r(Y)? We hebben hier weer te maken met complexe termen dus regel 3 moet weer van stal.
- Zelfde functor? Ja, r.
- Zelfde ariteit? Ja, één.
- Unificeren f en Y? Ja op basis van regel 2, variabele Y krijgt de waarde f.

Aan alle regels is voldaan dus er is sprake van unificatie.

Een laatste voorbeeld:

?- kindVan(X,X) = kindVan(geert,harry). False

Waarom? Complexe termen dus op naar regel 3. Zelfde functor en ariteit? Ja, kindVan en twee. Unificeren X en geert? Ja volgens regel 2 en nu is X gelijk aan geert. Unificeren X en harry? Omdat X net geert is geworden is dan de vraag unificeren geert en harry? Volgens regel 1 klopt dit niet. Er is dus geen sprake van unificatie.

De occurs controle

Unificatie is een bekend concept dat in vele takken van de computerwetenschappen wordt gebruikt. Het concept is diepgaand onderzocht en er zijn veel unificatie algoritmen aanwezig. Prolog gebruikt gebruikt niet het standaard unificatie algoritme wanneer het bovenstaande regels gebruikt. In plaats daarvan neemt Prolog een kortere weg. Je moet weten hoe Prolog afwijkt.

Beschouw de volgende vraag:

?- vader(X) = X.

Zijn de twee termen te unificeren? Een standaard algoritme (dit behandelen we zo bij de occurs controle). zou hier als antwoord geven: "Nee, dat is niet mogelijk". Waarom niet? Kies een willekeurige waarde voor X, bijvoorbeeld ada, dan wordt de linker kant vader(ada). Stel nu de vraag:

?- vader(ada) = ada. False

Het antwoord hierop is negatief op basis van regel 4. We hadden ook vader(vader(ada)) voor X kunnen kiezen. De linker kant wordt dan vader(vader(vader(ada))). Ook dit unificeert niet met vader(vader(ada)). Welke waarde je ook voor X kiest er zal geen unificatie mogelijk zijn.

Toch geeft SWI-prolog geen fout terug bij de vraag

?- vader(X) = X. X = vader(X).

Ofwel we krijgen een nog op te lossen gelijkheid. Regel 2 zegt dat we aan X de waarde vader(X) geven en hier stopt SWI-prolog. Andere versies van Prolog gaan op basis van dezelfde regels verder in hun zoektocht naar een geschikte X en willen ook de X in vader(X) een waarde geven. Omdat net X de waarde vader(X) heeft gekregen realiseren deze versies van Prolog dat vader(X) eigenlijk vader(vader(X)) zou moeten zijn, maar ook hier zit weer een X in en vader(vader(X)) zou dan eigenlijk vader(vader(vader(X))) moeten zijn enzovoorts. Er komt geen einde aan en Prolog loopt vast. De oplossing zou dus een oneindige serie van vader aanroepen moeten zijn.

X = vader(vader(vader(vader(...))))))))

Wiskundig misschien interessant, maar berekeningen op de computer kunnen alleen eindigheid aan.

Swi-prolog besluit dus op de vraag ?- vader(X) = X. dat er unificatie mogelijk is, maar voorkomt het vastlopen van Prolog. Ook bij de vraag

?- X = vader(X), Y = vader(Y), X = Y. X=Y, Y = vader(Y)

laat SWI-Prolog zich niet uit over de werkelijke waarden voor X en Y.

Er zijn dus twee verschillende antwoorden op de vraag unificeert vader(X) met X. Het antwoord van de het standaard unificatie algoritme zegt nee, terwijl Prolog vindt dat dit wel het geval is. Ofwel er is eigenlijk geen "echt" antwoord op deze vraag. Het is wel van belang te beseffen wat Prolog in dit geval doet.

In de opdrachten later in dit hoofdstuk vragen we je om te experimenteren in SWI-prolog. Hier willen we nog even wat kwijt over het verschil tussen het Prolog algoritme en het standaard algoritme voor unificatie. Gezien de verschillende antwoorden lijken de twee algoritmen in de basis verschillend. Dit is echter niet het geval. Er is slechts een simpel verschil in de taak om bijvoorbeeld vader(X) en X te unificeren. Het standaard algoritme voert in het unificatie proces van twee termen als eerste de zogenaamde occurs check (komt voor controle) uit. Dit betekent dat, als er wordt gevraagd een variabele te unificeren met een term, er eerst wordt gecontroleerd of de variabele ook in de term voorkomt. Als dit het geval is dan besluit het standaard algoritme dat er geen unificatie mogelijk is (dit is het geval in vader(X) = X ). Pas als de variabele niet in de term aanwezig gaat het verder met het unificatie proces.

Het standaard algoritme is eigenlijk pessimistisch. Alleen als de term de variabele niet bevat is het veilig om te bepalen of de variabele met de term unificeert en kan het unificatie proces niet vastlopen. Prolog is optimistisch en gaat er van uit dat je niet iets "gevaarlijks" gaat doen. Omdat Prolog een programmeertaal is, is het een intelligente strategie om niet te veel te controleren. Unificatie is één van de belangrijkste processen in Prolog. Controle processen vertragen het uitvoeren van een programma en zijn dus niet wenselijk als het niet echt nodig is. De verantwoordelijkheid voor zinvolle unificatie vragen wordt dus bij de programmeur gelegd in plaats van bij het standaard unificatie proces.

Prolog geeft je wel de mogelijkheid om standaard unificatie uit te voeren met het predicaat unify_with_occurs_check/2. Op de vraag

?- unify_with_occurs_check(vader(X),X).

krijg je het antwoord False.

Programmeren met unificatie

Zoals we al eerder hebben vermeld is unificatie een basisoperatie in Prolog. Het speelt de sleutelrol in het zoeken naar bewijzen in Prolog (dit leren we zo) en is alleen daarom al essentieel. Als je beter in Prolog wordt, zal het je duidelijk worden dat unificatie op zichzelf al heel belangrijk is. Soms kun je zinvolle programma's schrijven waarin alleen complexe termen voorkomen en waarmee je met unificatie een gewenst resultaat kan krijgen.

Een simpel voorbeeld, (Ivan Bratko) is de volgende tweeregelige kennisbank:

verticaal(lijn(punt(X,Y),punt(X,Z))).

horizontaal(lijn(punt(X,Y),punt(Z,Y))).

Er zijn twee predicaten namelijk verticaal\1, die definieert wat er moet gelden voor een verticale lijn, namelijk dat de x-coördinaten van de twee punten die de lijn vastleggen aan elkaar gelijk zijn en horizontaal/1, die definieert wat een lijn horizontaal maakt, namelijk de y-coördinaten van de twee punten die de lijn vastleggen moeten gelijk zijn.

In eerste instantie lijkt dit voorbeeld te makkelijk om interessant te zijn, er zijn slechts twee feiten en geen regels. Maar wacht eens even, de twee feiten zijn gemaakt met complexe termen als argument, die ook weer complexe termen als argument hebben. Er zijn in dit geval dus 3 lagen van complexiteit in één term. Meer nog, de argumenten in punt zijn ook nog eens variabelen. De concepten verticale lijn en horizontale lijn zijn dus heel algemeen opgesteld. Laten we nog dit nog even nader bekijken.

Op het laagste niveau vinden we de complexe term met functor punt en de twee argumenten X en Y die natuurlijk bedoeld zijn voor getallen die respectievelijk de x- en y-coördinaat van een punt in een tweedimensionaal assenstelsel voorstellen. Twee punten leggen een lijn vast, op het tweede niveau worden de punten met de complexe term met functor lijn en twee argumenten, ieder argument een punt. De topniveaus verticaal en horizontaal gebruiken nu het concept lijn, met de bovengenoemde eigenschappen voor horizontale en verticale lijnen.

Laten we eens een paar voorbeelden van het gebruik van deze kennisbank bekijken.

?- verticaal(lijn(punt(1,1),punt(1,3))). True

(Bij het stellen van de vraag krijg je in Swish de melding over "singleton variables", let hier nog even niet op, dit heeft geen effect op de logica. ) Dit zou duidelijk moeten zijn: de vraag unificeert met de definitie van verticaal/1 in onze kleine kennisbank, omdat de X-coördinaten in de twee punten gelijk zijn. In de vraag

?- verticaal(lijn(punt(1,1),punt(3,2))). False

is dit niet het geval dus Prolog antwoordt met False.

We kunnen ook meer algemene vragen stellen b.v.:

?- horizontaal(lijn(punt(1,1),punt(2,Y))). Y = 1

Hier is onze vraag: als we een horizontale lijn willen waarop het punt (1,1) ligt en een ander punt met x-coördinaat 2, wat zou dan de y-coördinaat van dat punt moeten zijn? Prolog komt in dit geval met slechts één oplossing.

Bekijk nu de vraag

?- horizontaal(lijn(punt(2,3),P)). P = punt(_1454, 3)

De vraag is: als we een horizontale lijn willen door het punt (2,3) en een ander punt P, welke punten zijn dan toegestaan? In het antwoord P = punt(_1454,3) zien we een variabele _1454 voor de x-coördinaat en de constante 3 voor y-coördinaat. Dat de x-coördinaat een variabele is betekent dus dat we daar een willekeurig getal voor kunnen nemen. De y-coördinaat ligt echter vast.

Een algemene opmerking: Het antwoord op de laatste vraag, punt(_1454,3), noemen we gestructureerd. Dat wil zeggen, het antwoord is een complexe term die een geavanceerd concept representeert (namelijk "ieder punt waarvan de y-coördinaat gelijk is aan 3"). Deze structuur was gemaakt door alleen van unificatie gebruik te maken en niets anders: b.v. er is geen logische gevolgtrekking gebruikt om dit antwoord te maken.
Het maken van structuur met unificatie is een zeer krachtig idee gebleken bij het programmeren in Prolog. Meer nog, als een programma is geschreven dat heel veel gebruik maakt van unificatie, dan is het vrijwel zeker extreem efficiënt. In de hoofdstukken taalverwerking 1 en 2 zullen we kennis maken met een elegant voorbeeld.

Nog een algemene opmerking: Deze manier van programmeren is vooral nuttig in applicaties waar de belangrijkste concepten een hiërarchische structuur hebben ( zoals: lijn opgebouwd uit punten), de complexe termen kunnen dan gelijk in deze hiërarchische structuur worden geschreven. Ook kan dan unificatie worden gebruikt om de hiërarchie te ondervragen. Taal bevat een dergelijke hiërarchie ( verdiep je maar eens in de manier van zinsbouw ) en het is dus niet zo raar dat taalanalyse met behulp van computers met Prolog wordt gedaan. Een toepassing die jij misschien al bent tegen gekomen is: vraag en antwoord robots bij webwinkels of overheidsdiensten. Jouw getypte vragen worden geanalyseerd om het meest waarschijnlijke antwoord te geven.

Gelijk zijn of gelijk maken: Unificatie

Editor:

Bron: Learn Prolog Now!

Wat leer je in dit hoofdstuk:

Unificatie

Voorbeelden

De occurs controle

Programmeren met unificatie