Een Prolog voorbeeld

 
11 juni 2013

Afgelopen week heb ik een presentatie gegeven over Prolog. Daar hanteerde ik een bepaald voorbeeld om de eigenschappen van de taal te illustreren. Om de code uitwerking nog eens rustig te kunnen bekijken, hier een uitwerking van het vakantie voorbeeld.

Het probleem:

Een groep vrienden gaan op een lange reis met meerdere auto`s. Maak een planning voor wie in welke auto rijdt.

Dus het probleem is dat we personen moeten verdelen over een aantal auto`s.

Om het eenvoudig te houden kunnen we eerst kijken naar een enkele auto. Daar geld voor dat de auto een aantal zitplaatsen heeft en deze zitplaatsen bezet moeten worden door onze groep vrienden. Een regel om te kijken kijken of de planing van een auto voldoet aan deze eisen zou er bijvoorbeeld zo uit kunnen zien:

 geldig(auto(AantalZitpl, Inzit), Vrienden) :-
    length(Inzit, AantalZitpl),
    subset(Inzit, Vrienden).

Een auto met inzittenden is geldig als het aantal inzittenden gelijk is aan het aantal zitplaatsen en de inzittenden ook voorkomen in de lijst van vrienden. Of wel zit de auto precies vol en gaan er geen vreemden mee. Nu kunnen we Prolog vragen stellen op basis van deze regel. Is het bijvoorbeeld geldig dat Jay en Robin de Smart tweezitter nemen:

| ?- geldig(auto(2, [jay, robin]), 
    [jay, robin, kim, wil]).
yes
| ?-

In het bovenstaande stukje stellen we dus Prolog die vraag. En het antwoord is ‘yes’ dit is een geldige bezetting van een auto met twee zitplaatsen. Voor een ongeldig voorbeeld: Wat nu als we Jay, Robin en Kim in deze auto willen proppen?

| ?- geldig(auto(2, [jay, robin, kim]), 
    [jay, robin, kim, wil]).
no
| ?-

En Prolog geeft netjes aan dat dit geen goede invulling is. Het zelfde zien we als Anne mee wilt in de auto.

| ?- geldig(auto(2, [anne, robin]), 
    [jay, robin, kim, wil]).
no
| ?-

Omdat Anne kennelijk geen deel uitmaakt van het vrienden groepje is het antwoord ook hier ‘no’.

Tot nu toe hebben we redelijk simple vragen gesteld over de bezetting van een auto. Als dit het enige was dat we met Prolog konden dan was het misschien grappig, maar niet bijster spectaculair. De echte interessante vragen komen als we niet zomaar vragen of een bepaalde invulling geldig is, maar ook nog bepaalde informatie weg laten.

| ?- geldig(auto(4,X), 
    [kim, wil, jose, jay, leslie, sasha, hennie, 
        robin]).

X = [leslie,sasha,hennie,robin] ?

yes

In het bovenstaande voorbeeld hebben we de inzittenden vervangen met de variable X. Dat wil zeggen dat we effectief open laten wie de inzittende zijn voor de auto. In het antwoord zien we nu de grote kracht van Prolog naar boven komen. We zien namelijk dat het antwoord uit twee delen bestaat. In het eerste gedeelte geeft Prolog een suggestie voor de invulling van de variable X, ‘X = [leslie,sasha,hennie,robin]’ en als tweede deel ‘yes’. De interpretatie is hier dat als we Leslie, Sasha, Hennie en Robin in de auto plannen dan hebben we een geldige bezetting.

Nu we een enkele auto kunnen in plannen kunnen we proberen de rest van de vrienden ook in te plannen. De onderstaande regel is wat ingewikkelder dan de geldig regel van voor heen.

vakantie([], []).
vakantie([Auto | Rest], Vrienden) :-
	geldig(Auto, Vrienden),
	auto(_,Inzit) = Auto,
	subtract(Inzit, Vrienden, OverigeVr),
	vakantie(Rest, OverigeVr).

Samengevat stelt deze regel dat een vakantie geldig is als de lijst van auto`s geldig is. Dit gebeurt door de regel in tweeën te delen. Het eerste gedeelte is eigenlijk de meest eenvoudige situatie: We hebben geen auto`s en er gaat niemand mee. Niet de meest spannende vakantie, maar het is wel een geldige. Het tweede gedeelte geeft aan dat een vakantie geldig is als de eerste auto geldig is en een vakantie met de rest van de auto`s en de vrienden die niet in de auto zitten ook geldig is.

Met deze regel kan ik dus aan Prolog vragen of de vakantie planning geldig is zoals bij de geldig regel beschreven voor auto`s. Spannender is het natuurlijk om de planning te laten maken:

| ?- vakantie([auto(4,Inz1), auto(4,Inz2)], 
    [kim, wil, jose, jay, leslie, sasha, hennie, 
        robin]).
Inz1 = [leslie,sasha,hennie,robin]
Inz2 = [kim,wil,jose,jay] ?
yes

Hierboven is te zien dat we een vraag stellen over de vakantie regel met twee variabelen Inz1 en Inz2. Het resultaat is een aardig suggestie voor de bezetting van onze kleine colonne.

Natuurlijk zijn er in een echte situatie nog meer eisen dan alleen dat het aantal inzittenden moet kloppen. Dat is op dit moment namelijk het enige wat in de geldig regel bepaald hebben. Maar waarschijnlijk willen we ook dat er in elke auto iemand ook daadwerkelijk een rijbewijs heeft. Laten we deze eis ook toevoegen.

Eerst moeten weten wie er allemaal een rijbewijs heeft. Dit kunnen we op verschillende manier regelen. We zouden dit bijvoorbeeld als feiten kunnen opschrijven. Feiten in Prolog zijn regels zonder condities. Of te wel een regel waarbij alles vanaf ‘:-‘ weg gelaten is. Feiten voor rijbewijs zouden er dan bijvoorbeeld zo uit kunnen zien:

rijbewijs(kim).
rijbewijs(jose).

Dit is een eenvoudige manier om ze op te schrijven, maar het nadeel is dan wel dat we dit vastleggen in ons code bestand. Daarom heeft het vaak de voorkeur om de informatie meegeven bij te test. In dit geval kunnen we het verwerken in de lijst van vrienden die we ook mee geven.

| ?- vakantie([auto(4,Inz1), auto(4,Inz2)], 
    [persoon(kim, rijbewijs), 
     persoon(wil,geen_rijbewijs), 
     ...]).

Met behulp van een Prolog functor veranderen we de lijst van namen in een lijst van persoon records die een naam en een rijbewijs term bevatten. ‘Kim’ wordt dus ‘persoon(kim, rijbewijs)’ terwijl ‘Wil’ ‘persoon(wil, geen_rijbewijs)’ wordt.

De volgende stap is dan het detecteren of er een persoon met rijbewijs bij de inzittenden van een auto zit. Hiervoor kunnen we het predicaat ‘member’. Dit predicaat is waar als een term in de lijst voor komt. Bijvoorbeeld:

| ?- member(wil, [kim,wil, robin, jose]).
yes
| ?- member(harry, [kim, wil, robin, jose]).
no

Dus de term ‘Wil’ geeft yes omdat wil in de lijst voorkomt, terwijl ‘Harry’ no oplevert omdat die niet in de lijst voorkomt. Dit kunnen we dus ook doen met een lijst van onze persoon functors.

| ?- member(persoon(robin, rijbewijs), [
                persoon(kim, rijbewijs),
                persoon(wil, geen_rijbewijs),
                persoon(jose, geen_rijbewijs),
                persoon(jay, geen_rijbewijs),
                persoon(leslie, geen_rijbewijs),
                persoon(sasha, rijbewijs),
                persoon(hennie, geen_rijbewijs),
                persoon(robin, rijbewijs)]).
yes

Op het eerste gezicht lijkt dit misschien helemaal niet handig. Voor deze test moeten we namelijk een persoon functor aanbieden en krijgen we terug of deze erin zit of niet. Dus ‘persoon(robin, rijbewijs)’ geeft yes in het voorbeeld hierboven, maar persoon(jose, rijbewijs) geeft no. Maar wat als we de naam van de personen met rijbewijzen niet weten? Is het member predicaat dan niet nuttig? In een normale taal zou het antwoord duidelijk zijn dat member niet nuttig is, maar dit is Prolog en Prolog interpreteert alles op zijn eigen manier.

Stel namelijk dat we niet zoeken naar ‘persoon(robin, rijbewijs)’, maar naar ‘persoon(Naam, rijbewijs)’, waarbij naam een variabele is. Als we de test dan nog een keer uitvoeren krijgen we een ander resultaat.

member(persoon(Naam, rijbewijs), [
                persoon(kim, rijbewijs),
                persoon(wil, geen_rijbewijs),
                persoon(jose, geen_rijbewijs),
                persoon(jay, geen_rijbewijs),
                persoon(leslie, geen_rijbewijs),
                persoon(sasha, rijbewijs),
                persoon(hennie, geen_rijbewijs),
                persoon(robin, rijbewijs)]).
Naam = kim ?
yes

Net als bij onze geldig regel van het begin, heeft Prolog geprobeerd de test waar te maken ondangs dat er open variabelen in onze zoek term voorkwamen. En het antwoord is dan ook dat als we bijvoorbeeld ‘Kim’ in vullen voor Naam de term ‘persoon(Naam, rijbewijs)’ in de lijst voorkomt.

Dit kunnen we gebruiken om een regel op te stellen waarbij we eisen dat er tenminste een persoon met rijbewijs in een auto gepland wordt.

ten_minste_een_rijbewijs(Personen) :- 
    member(persoon(_,rijbewijs), Personen).

Hierbij maken we gebruik van de speciale variabele ‘_’. Deze variabele kunnen we gebruiken als de waarde ons niet interesseert. Hierboven willen we alleen weten of er een rijbewijs aanwezig is, de naam van de eigenaar is niet belangrijk. Daarom is de Variabele Naam van het eerdere voorbeeld vervangen door ‘_’.

Deze regel voegen we ook nog toe aan ons geldig predicaat voor de bezetting van de auto.

geldig(auto(AantalZitpl, Inzittenden), Vrienden) :-
	length(Inzittenden, AantalZitpl),
	subset(Inzittenden, Vrienden),
	ten_minste_een_rijbewijs(Inzittenden).

En we proberen nog een keer onze vakantie te plannen. De test ziet er nu een stuk grote uit omdat we de lijst met namen vervangen hebben door persoon functors, maar het formaat van de test en het antwoord blijven gelijk.

| ?- vakantie([auto(4,Inz1), auto(4,Inz2)], [
                persoon(kim, rijbewijs),
                persoon(wil, rijbewijs),
                persoon(jose, geen_rijbewijs),
                persoon(jay, geen_rijbewijs),
                persoon(leslie, geen_rijbewijs),
                persoon(sasha, geen_rijbewijs),
                persoon(hennie, geen_rijbewijs),
                persoon(robin, geen_rijbewijs)]).

Inz1 = [
    persoon(wil,rijbewijs),
    persoon(sasha,geen_rijbewijs),
    persoon(hennie,geen_rijbewijs),
    persoon(robin,geen_rijbewijs)]
Inz2 = [
    persoon(kim,rijbewijs),
    persoon(jose,geen_rijbewijs),
    persoon(jay,geen_rijbewijs),
    persoon(leslie,geen_rijbewijs)] ?
yes

Boven is nu te zien dat de twee personen die een rijbewijs hebben in onze lijst mooi verdeelt zijn over de twee auto`s, met ‘Wil’ in de eerste en ‘Kim’ in de tweede auto. Dit geeft dus aan dat zolang als we een conditie kunnen definiëren voor een beperking van onze planning kan Prolog een oplossing genereren of aangeven dat er geen oplossing is. We kunnen ons voorbeeld nog verder uitbreiden met bijvoorbeeld de wensen van sommige personen om bij elkaar te willen zitten of juist niet bij elkaar.

De geldig regel wordt dan een stukje groter als we de nieuwe tests toevoegen, maar de structuur blijft gelijk:

geldig(auto(AantalZitpl, Inzit), Vrienden) :-
	length(Inzit, AantalZitpl),
	subset(Inzit, Vrienden),
	ten_minste_een_rijbewijs(Inzit),
	zijn_fans_en_idolen_bij_elkaar(Inzit),
	zijn_haters_en_gehaten_uit_elkaar(Inzit).

Het bestand met de volledig uitgewerkte code is hier te vinden. Met dit voorbeeld heb ik een kort blik willen geven in de wereld van logische programmeer talen en vooral willen illustreren hoe krachtig het paradigma kan zijn voor bepaalde problemen. Dus als je volgende keer eens een dergelijk probleem tegen komt, denk eens aan Prolog.


Werken met ?
Kijk dan bij onze mogelijkheden voor zowel starters als ervaren engineers.


Categorieën: Development, Overige talen en platformen

Tags: , ,