Prolog

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Prolog
Paradigma Logisch programmeren
Verschenen in 1973
Ontworpen door Alain Colmerauer
Implementaties SWI-Prolog, GNU Prolog en anderen
Dialecten ISO Prolog
Invloed op Mercury, Oz, Erlang
Besturingssysteem Multiplatform
Portaal  Portaalicoon   Informatica

Prolog (Fr. programmation en logique, "programmeren met logica") is een logische programmeertaal. De taal is gebaseerd op predicatenlogica en heeft een sterk declaratief karakter. In plaats van de stappen die tot de oplossing van een probleem leiden, worden de voorwaarden waaraan de oplossing moet voldoen in logische termen beschreven. Vandaar dat Prolog een constraint based language is, een "op beperkingen gebaseerde taal".

Ontwikkeling[bewerken]

Prolog werd oorspronkelijk in het jaar 1973 ontworpen door Alain Colmerauer en zijn vakgroep aan de universiteit van Marseille (Frankrijk). Het was de eerste implementatie van de ideeën van Robert Kowalski over het gebruik van Horn-clausules als basis voor een programmeertaal. De eerste versie van Prolog was een interpreter, geschreven in Fortran. Hoewel deze versie nog tamelijk ruw was, was het een proof of concept van Kowalski's ideeën.

Een volgende mijlpaal werd bereikt met een Prologsysteem dat op een DEC PDP-10 van de Universiteit van Edinburgh draaide. Met name David H.D. Warren speelde hierbij een belangrijke rol met de ontwikkeling van de Warren Abstract Machine, een van de eerste virtuele machines. Deze versie van Prolog bood vele optimalisaties en uitbreidingen en was de eerste die kon worden gecompileerd naar DEC-10-machinetaal. Edinburgh Prolog geldt in velerlei opzicht nog steeds als richtinggevend. In 1995 werd Prolog door de ISO gestandaardiseerd, waarbij het Edinburgh-I/O-systeem en vele predicaten werden vervangen. Dit leidde tot enige kritiek[1] en heeft ertoe geleid dat vele moderne implementaties beide versies ondersteunen.

Edinburgh-standaard[bewerken]

Omdat veel werk aan vroege compilers en interpreters aan de Universiteit van Edinburgh plaatsvond, kreeg de uiteindelijke implementatie de status van de facto standaard voor vroege implementaties, de Edinburgh-standaard. Deze laat nog steeds sporen na, hoewel inmiddels een formele standaard bestaat. Grote delen van deze standaard worden door moderne implementaties nog steeds ondersteund.

Warren Abstract Machine[bewerken]

Nuvola single chevron right.svg Zie Warren Abstract Machine voor het hoofdartikel over dit onderwerp.

In 1983 ontwierp David H. D. Warren een virtuele machine gericht op de taal Prolog. Omdat deze machine niet alleen het compileren van Prolog naar bytecode mogelijk maakte, maar door verschillende optimalisaties Prologcode veel efficiënter uitvoert, is de WAM een de facto standaard voor Prolog geworden. Warrens publicatie uit 1983 heeft inmiddels cultstatus.[2]

Ondanks het feit dat het ook mogelijk is naar native machinetaal te compileren, zijn WAM's nog steeds vrij algemeen. De voordelen van een native implementatie zijn beperkt doordat vrij veel functionaliteit uiteindelijk toch in support-functies moeten worden geïmplementeerd en het wiel veelvuldig opnieuw moet worden uitgevonden.[2] Tevens worden onvermijdelijk machine-afhankelijkheden (machine dependencies) geïntroduceerd, wat de portabiliteit niet ten goede komt.

Quintus en SICStus[bewerken]

Omdat standaarden ontbraken of nog in de kinderschoenen stonden,[2] was er een wildgroei aan dialecten, waarbij iedere leverancier zijn eigen dialect gebruikte. Vanwege de industriële kwaliteit en de vele innovaties werd Quintus Prolog, dat in nauwe samenwerking met de Universiteit van Edinburgh was ontwikkeld, een de facto standaard. Tot de belangrijkste innovaties behoren de foreign language interface, dat het ontwikkelen van software in andere computertalen mogelijk maakte en een systeem om Prologbroncode in modules te verdelen en zodoende de ontwikkeling van grote systemen makkelijker te maken.

In de jaren 1985 tot 1990 ontstond uit een soortgelijke samenwerking in Zweden, waar ook andere vakgroepen en commerciële partijen aan deelnamen, het instituut SICS (Swedish Institute of Computer Science). Het hoofddoel van het onderzoek was de werklast over meerdere processoren te verdelen, or-parallel, waarbij verschillende alternatieven tegelijkertijd worden overwogen. Dit werd verwezenlijkt met het Aurora-project, waarin ook Warren een belangrijke rol speelde. Vanaf 1988 werd het project door de Zweedse overheid en marktpartijen gesubsidieerd om SICStus Prolog voor industriële toepassingen geschikt te maken, wat in 1991 resulteerde in versie 3.

In 1998 nam SICStus het bedrijf Quintus over en kondigde een "Grand Unified Compiler" aan (een toespeling op de Grand Unified Theory uit de natuurkunde), een fusie van Quintus- en SICStus-technologie, die echter niet van de grond kwam. Pas in 2007 resulteerden de inspanningen in versie 4 en 4.1 in 2009. SICStus is de grootste leverancier van Prolog-compilers en de innovaties op het gebied van parallellisatie en schaalbaarheid gelden als richtinggevend.[3] SWI-Prolog, bijvoorbeeld, implementeert belangrijke delen van de Quintus/SICStus-specificatie.[4]

ISO/IEC 13211-1[bewerken]

De eerste pogingen de taal te standaardiseren dateren uit 1985,[1] toen de AFNOR de eerste Prologwerkgroep in het leven riep. In 1987 vormde de ISO een werkgroep (ISO/IEC JTC1/SC22 group WG17). Te laat, want verschillende leveranciers hadden hun eigen versies en klantenkring ontwikkeld en verdedigden hun dialecten furieus tegen al te drastische ingrepen.

De vele verhitte, soms bijtende debatten[2] resulteerden uiteindelijk in de standaard ISO/IEC 13211-1 die in 1995 werd gepubliceerd. Het document standaardiseert niet alleen de syntaxis en formele semantiek van de taal, maar definieert ook unificatie, een centraal begrip, herdefinieert I/O-predicaten en introduceert een aantal constructies voor exception handling. Met name de herdefinitie van I/O-predicaten heeft kritiek opgeroepen omdat ze drastisch van de Edinburgh-implementaties verschillen en zodoende veel oude Prologprogramma's breken. Ondanks de weerstand wordt deze standaard tegenwoordig vrij breed geaccepteerd.

Gebruik[bewerken]

Omdat Prolog is gebaseerd op formele logica en met behulp van een inference engine zelfstandig conclusies kan trekken, is deze taal uitermate geschikt om kennis te modelleren en de mens te ondersteunen bij het trekken van conclusies uit (zeer) grote hoeveelheden gegevens. De taal is dan ook een uitstekend hulpmiddel voor datamining, het interpreteren van de uitkomsten van metingen, modellen en simulaties en het bouwen van expertsystemen en onderzoek naar kunstmatige intelligentie.

Hoewel het gebruik van Prolog zich in eerste instantie beperkte tot de academische wereld, is de taal inmiddels ook in gebruik in de industriële wereld en wordt onder andere door Boeing gebruikt om met behulp van een expertsysteem handleidingen voor de assemblage van connectors met lijsten van benodigde gereedschappen, materialen, onderdelen en procedures samen te stellen.[5] Het National Center for Atmospheric Research in de VS gebruikt op Prolog gebaseerde software om kortetermijnweerberichten te genereren, in Boedapest houdt een Prologapplicatie de concentraties van vervuilende stoffen in de gaten en adviseert over de te gebruiken extra filters als niveaus worden overstegen, en in het Verenigd Koninkrijk adviseert een toepassing het personeel van een waterleidingbedrijf over optimaal gebruik van pompen, zodat de druk in het waterleidingsysteem gelijk verdeeld is.

De krachtige inference engine, de mogelijkheid tot backtracking ("terugkrabbelen") en de eenvoud en flexibiliteit van de taal maken haar zeer geschikt voor Rapid Prototyping, vooral omdat ingewikkelde regels relatief simpel kunnen worden uitgedrukt. Dit maakt haar ook zeer geschikt om taaluitingen, natuurlijk of anderszins te interpreteren en voort te brengen. Prolog wordt dan ook vaak voor dit doel ingezet. Dat de taal al beschikt over mechanismen om syntaxis te definiëren, zoals Definite Clause Grammars, maakt haar uitermate geschikt voor dit doel. Het internationale ruimtestation ISS heeft Clarissa,[6] een in Prolog geschreven "fully voice operated procedure browser" om de astronauten te ondersteunen in de duizenden procedures die vereist zijn om het ruimtestation draaiend te houden.

Invloed[bewerken]

Omdat Prolog de eerste taal was die op predicaatlogica was gebaseerd, wordt zij nog steeds als richtinggevend beschouwd en geldt als de eerste taal gericht op constraint programming. De toepassing van formele logica om kennis te modelleren heeft inmiddels vele verschillende talen en applicaties opgeleverd, die echter vaak tot de academische en industriële wereld beperkt blijven. De Warren Abstract Machine echter, was als een van de eerste virtuele machines een innovatie die veel navolging kreeg, onder andere in de Java Virtual Machine.

De technieken die voor Prolog zijn ontwikkeld zijn tegenwoordig tamelijk wijd verspreid en beperken zich niet tot eerste orde, maar richten zich ook op tweedeordelogica en automated theorem proving, het bewijzen van wiskundige stellingen door middel van software. Talen zoals Erlang en Gödel implementeren dan ook vrij veel functionaliteit van Prolog.

In de jaren 80 van de vorige eeuw bracht Borland Turbo Prolog op de markt, dat nog steeds onder de naam Visual Prolog wordt gebruikt. Deze taal, die veel meer op hobbyisten dan op professionele gebruikers is gericht, verschilt echter zodanig van Prolog zelf, dat de naam eigenlijk misleidend is. Het belangrijkste verschil is dat types in Turbo Prolog statisch worden geverifieerd en dus moeten worden gedeclareerd, wat de flexibiliteit van Prolog teniet doet.

Ook in de literatuur heeft de taal enige sporen nagelaten. In de roman Dirk Gently's Holistic Detective Agency van Douglas Adams speelt een op Prolog gebaseerd expertsysteem een rol dat voor ieder gewenst politiek doel automatisch een redenering verzint die het idee onderbouwt. Overigens reageert een SWI-Prolog-systeem met "42" op onzinnige query's.

Datatypen[bewerken]

Variabelen[bewerken]

Een variable in Prolog wordt aangegeven met behulp van een hoofdletter en is een object dat met alles kan worden geünificeerd. Het is belangrijk hierbij op te merken dat zodra een variabele eenmaal aan een specifieke waarde is gebonden (door unificatie), deze binding niet weer ongedaan kan worden gemaakt.

Atomen (atom)[bewerken]

Een atom (uit het grieks atomos, ondeelbaar) is een unieke string die een enkel object representeert. Een atoom kan op twee manieren worden weergegeven:

  • Zonder aanhalingstekens als het atoom met een kleine letter begint en verder alleen letters, cijfers en underscores bevat (auto, vrachtwagen, fiets, dit_is_een_atoom).
  • Met aanhalingstekens als het atoom met een hoofdletter of cijfer begint of niet toegestane tekens bevat ('2CV', 'jan-willem', 'dit is ook een atoom').

Integers en floats[bewerken]

Integers en floats stellen diverse getallen voor. De notatie verschilt niet van die in andere talen.

Structuren (structure)[bewerken]

Een structuur is een complexe, geordende verzameling gegevens. Deze worden weergegeven door een functor gevolgd door een list van elementen tussen haakjes. Structuren kunnen worden genest.

klant(naam('Pietje', 'Puk'),
      adres('Dorpstraat', 1, '9999ZZ', 'Ergenshuizen'),
      telefoon('0123', '4567890')).

Lijsten (list)[bewerken]

Een lijst is een gespecialiseerde structuur gebaseerd op de voorgedefinieerde functor '.' (dot), die twee elementen kent: de kop (head) en de staart (tail), waarbij de staart een andere lijst is. De staart van het laatste element wordt weergegeven door een lege lijst: '[]'.

Een lijst ziet er dus zo uit:

 .(aap, .(noot, .(mies, [])))

Omdat deze notatie nogal omslachtig is, wordt echter meestal een notatie gebruikt waarbij de lijst wordt weergegeven door kommagescheiden elementen tussen een [- en een ]-teken. Het volgende is equivalent aan het bovenstaande en heeft dezelfde interne representatie:

 [aap, noot, mies]

Met behulp van de '|' operator wordt de kop van de lijst onderscheiden, zodat verschillende vormen van unificatie mogelijk zijn:

 ?- [Kop|Staart] = [aap, noot, mies].
 Kop=aap
 Staart=[noot, mies]
 true

 ?- [K1, K2|Staart] = [aap, noot, mies].
 K1=aap
 K2=noot
 Staart=[mies]
 true

Feiten, regels en de prologdatabase[bewerken]

Het hart van de taal Prolog wordt gevormd door een database waarin feiten (facts) en regels (clauses) worden opgeslagen. Ieder feit en iedere regel heeft een ariteit, het aantal argumenten dat de clause vereist.

Voorbeeld, een aantal feiten (facts) met ariteit 2:

voertuig(vrachtwagen, 'Scania').
voertuig(auto,        '2CV').
voertuig(motor,       'Harley-Davidson').
voertuig(brommer,     'Puch').
voertuig(fiets,       'Batavus').

Een clause (regel) brengt verband aan tussen twee of meer feiten. Bijvoorbeeld: Voor X is een rijbewijs 'c' nodig als X een voertuig is en X een vrachtwagen is.

rijbewijsNodig(c, X) :-
  voertuig(vrachtwagen, X).

Het verschil tussen facts en clauses is de ':-' operator, de neck, die de kop (head) van de clause scheidt van de definitie, de body. In feite is een fact een bijzondere clause die altijd slaagt.

Volgorde[bewerken]

Feiten en regels in de database hebben een vaste volgorde. Als meerdere clauses met dezelfde naam en ariteit (hetzelfde aantal argumenten) voorkomen worden ze geëvalueerd in de volgorde waarin ze in de broncode vermeld worden. Clauses met dezelfde naam en ariteit worden gegroepeerd om hun samenhang te benadrukken en worden als een samenhangend geheel gezien. Moderne compilers zullen een foutmelding genereren als deze niet zijn gegroepeerd.

Assert en retract[bewerken]

Feiten en regels hoeven niet vast in de programmatekst te worden gedefinieerd, maar kunnen ook worden toegevoegd met de assert ("stel vast")-predicaten asserta en assertz, die ze respectievelijk "als eerste" of "als laatste" definiëren. Met behulp van de predicaten retract en abolish kan men feiten en regels weer uit de database verwijderen, zodat de database wordt aangepast aan veranderende omstandigheden zonder de broncode aan te passen.

Vragen, unificatie en ongebonden variabelen[bewerken]

Met bovenstaande feiten en regels in de database is het mogelijk de Prologdatabase te ondervragen met een Prolog-"vraag" (question).

?-voertuig(V, 'Scania').
V=vrachtwagen
true

Onze vraag bevat een variabele 'V' die in eerste instantie "ongebonden" is, een unbound variable. Dat wil zeggen, dat 'V' geen bepaalde waarde heeft. Pas als 'V' met het atom 'vrachtwagen' wordt geünificeerd, heeft 'V' een waarde. Als een variabele eenmaal een waarde heeft, is het niet mogelijk deze binding weer te verbreken.

Het is verleidelijk de unificatie te zien als een toekenning (assignment) aan een variabele zoals die in imperatieve talen gebruikelijk is, maar unificatie is wezenlijk verschillend. Waar een toekenning altijd slaagt, faalt een unificatie tenzij aan de volgende regels wordt voldaan.

  • Ongebonden variabelen kunnen altijd met andere ongebonden variabelen worden geünificeerd.
  • Ongebonden variabelen kunnen altijd met atoms, integers of structuren worden geünificeerd. Als dit is gebeurd, is de variabele niet langer ongebonden, maar heeft een specifieke waarde.
  • Atomen (atoms) kunnen uitsluitend met andere atomen met een overeenkomstige waarde worden geünificeerd. Het atoom "vrachtwagen" kan met een ander atoom "vrachtwagen" worden geünificeerd, maar niet met een atoom "auto" of "fiets".
  • Lijsten kunnen met andere lijsten worden geünificeerd als alle afzonderlijke elementen kunnen worden geunificeerd.
  • Structuren kunnen uitsluitend met andere structuren worden geünificeerd als ze
    1. dezelfde ariteit hebben en
    2. alle leden van de structuur kunnen worden geünificeerd.

Merk op dat de unificatie van lijsten en structuren recursief is gedefinieerd, want elk lid van de structuur kan zelf een structuur zijn.

Directionaliteit[bewerken]

Omdat een Prolog-programma wordt gedefinieerd in termen van logische relaties in plaats van een sequentie van instructies, is er bij unificatie geen sprake van een bron wiens waarde wordt toegekend of een doel waaraan de waarde wordt toegekend. Een geslaagde unificatie van X en Y resulteert erin dat X en Y dezelfde waarde krijgen. Of X aan een waarde gebonden was en Y werd gebonden of andersom, maakt daarbij niet uit. Als beide variabelen gebonden zijn maar aan bovenstaande regels voldoen, slaagt de unificatie eveneens.

Dit werkt dit ver door en vele predicaten zijn non-directioneel in de zin dat geen echt onderscheid wordt gemaakt tussen in- en uitvoerparameters. Aan de hand van het member-predicaat, dat lidmaatschap in een lijst vaststelt kan dit worden geïllustreerd:

?- member(foo, [foo, bar, baz]).
true 

?- member(X, [foo, bar, baz]).
X = foo ;
X = bar ;
X = baz

Maar omdat member in logische termen is gedefinieerd, werkt het ook andersom:

?- member(foo, [X, bar, baz]).
X = foo ;
false.

?- member(foo, [X, Y, Z]).
X = foo ;
Y = foo ;
Z = foo.

Of zelfs

?- member(foo, List).
List = [foo|_G321] ;
List = [_G320, foo|_G324] ;
List = [_G320, _G323, foo|_G327] ;
List = [_G320, _G323, _G326, foo|_G330] ;
List = [_G320, _G323, _G326, _G329, foo|_G333] 

In het laatste geval, waar de vraag luidt of er een lijst bestaat waarvan 'foo' lid is, wordt List geünificeerd met een lijst bestaande uit 'foo' als kop en een dummy-variabele als staart. Dit is de kleinste lijst waar 'foo' lid van kan zijn, met slechts een element als de dummy met de lege lijst wordt geünificeerd. Het zoeken naar alternatieven resulteert in een (theoretisch) oneindig aantal lijsten van dummy-variabelen en het element 'foo'.

Doel (goal)[bewerken]

Een doel is in feite een vraag aan de Prologdatabase. Een doel wordt bereikt als het kan worden geünificeerd met de inhoud van de database. Om, bijvoorbeeld, bovenstaande clause "rijbewijsNodig(c, X)" te verwezenlijken moet het doel (goal) "voertuig(vrachtwagen,X)" worden verwezenlijkt. Dat kan alleen als X='Scania'.

?- rijbewijsNodig(c, X).
X='Scania'
true

Vier poorten[bewerken]

De werking van Prolog kan worden weergegeven door elk doel (goal) weer te geven als een knoop met vier poorten, waarbij Call en Retry ingangen zijn, en Exit en Fail uitgangen.

Om een doel te verwezenlijken wordt eerst de call-poort geprobeerd. Slaagt dit, dan wordt de goal verlaten door de exit-poort en wordt gepoogd het volgende doel te verwezenlijken. Als het doel niet verwezenlijkt kan worden, wordt de goal via de fail-poort verlaten en krijgt een vorig doel de kans via de retry-poort.

4gates.png
Call (in)
Vind het eerste alternatief en probeer het te verwezenlijken.
Exit (uit)
Succes! Probeer het volgende doel te verwezenlijken.
Retry (in)
Vind het volgende alternatief en probeer het te verwezenlijken. Faal als er geen alternatief is.
Fail (uit)
Mislukt! Als er een vorig doel is, probeer het via de Retry-poort, anders meldt de mislukking.

De vraag, of het doel, "rijbewijsNodig(c, 'Scania')" resulteert in de vraag "voertuig(vrachtwagen, 'Scania')" en komt dus overeen met een ketting van twee doelen, waarbij telkens exit naar call wijst en fail naar retry. Als de ketting van doelen van links naar rechts doorlopen kan worden (dat wil zeggen, alle doelen worden verwezenlijkt) en men deze door exit-poort kan verlaten, slaagt de conjunctie. Kan een van de doelen niet worden verwezenlijkt, gaat men door de fail-poort naar links en komt door de retry-poort van het voorafgaande doel. Als men door de retry-poort gaat, zal Prolog dit doel nogmaals proberen te verwezenlijken, maar kiest nu een alternatief. Pas als geen alternatieven meer voorhanden zijn, verlaat men de ketting aan de linkerkant via de fail-poort en de conjunctie faalt.

Call Exit Call Exit → (success)
rijbewijsNodig(c, 'Scania') voertuig(vrachtwagen, 'Scania')
Fail Retry Fail Retry

De query "rijbewijsNodig(c, '2CV')." Komt overeen met:

Call Exit Call Exit
rijbewijsNodig(c, '2CV') voertuig(vrachtwagen, '2CV')
Fail Retry Fail Retry

Merk op dat de laatste query niet verwezenlijkt kan worden, daar het doel "voertuig(vrachtwagen, '2CV')" niet met een entry in de database kan worden geünificeerd.

Het poorten-model is erg succesvol bij het traceren van de activiteit van de Prolog-interpreter.

Complexe regels[bewerken]

Regels zijn vaak complexer dan het bovenstaande zeer eenvoudige voorbeeld. Vaak moet aan twee of meer vereisten worden voldaan, soms aan slechts een van meerdere vereisten.

Conjuncties[bewerken]

Een conjunctie wordt gevormd door twee of meer goals die allen verwezenlijkt moeten worden. Dit wordt aangegeven door de goals met een komma te scheiden.

De vereiste "persoon P heeft het benodigde rijbewijs voor voertuig V", wordt dan geformuleerd als:

  • V is een voertuig waar rijbewijs R voor nodig is,

en

  • P is een persoon die lijst L van rijbewijzen heeft,

en

  • R komt voor in L
heeftGeldigRijbewijs(Bestuurder, Voertuig) :-
  rijbewijsNodig(Vereist, Voertuig),
  bestuurder(Bestuurder, Rijbewijzen),
  member(Vereist, Rijbewijzen).

Disjuncties[bewerken]

Een disjunctie wordt gevormd door twee of meer goals waarvan er één verwezenlijkt moet worden. Disjuncties worden aangegeven door de afzonderlijke goals te scheiden door een puntkomma ';'.

Een persoon P mag rijden met voertuig V als:

  • P het benodigde rijbewijs heeft

of

  • voor V geen rijbewijs nodig is.

Ofwel:

magBesturen(Voertuig, Persoon) :-
  heeftGeldigRijbewijs(Persoon, Voertuig);
  not(rijbewijsNodig(_, Voertuig)).

Omdat bij disjuncties makkelijk onvoorziene effecten kunnen optreden doordat de prioriteiten van de operators anders zijn dan de programmeur voor ogen had, worden disjuncties vaak als twee afzonderlijke clauses geschreven, zeker als de clause-met-disjunctie tamelijk ingewikkeld is.

Alternatieven, backtracking en de cut operator[bewerken]

In veel gevallen zijn er meerdere mogelijkheden een vraag te unificeren met de database. De vraag "voertuig(R, V)" zou in het bovenstaande voorbeeld een aantal mogelijke antwoorden hebben. Het overwegen van alternatieve antwoorden wordt wel backtracking genoemd.

?- voertuig(R, V).
R=vrachtwagen
V='Scania' ;
R=auto
V='2CV' ;
R=brommer
V='Puch' ;
R=fiets
V='Batavus' ;

Door de ;-toets wordt de Prologdatabase gedwongen een alternatieve oplossing te zoeken. Wordt een oplossing gevonden, wordt die gegeven. Dit kan ook worden geforceerd door het fail-predicaat, dat altijd mislukt (vandaar de naam), zodat altijd een ander alternatief wordt gezocht.

?- voertuig(_, V), writef("Voertuig %w\n", [V]), fail.
Voertuig Scania
Voertuig 2CV
Voertuig Harley-Davidson
Voertuig Puch
Voertuig Batavus
false.

Cut[bewerken]

In sommige gevallen is het zoeken naar een alternatief ongewenst, bijvoorbeeld als er al gegevens zijn uitgevoerd naar een randapparaat, om excepties af te handelen of om te voorkomen dat ongewenste alternatieven worden overwogen.

Dit kan worden bereikt door de cut, die wordt genoteerd als uitroepteken (!) en in feite zegt dat er geen alternatieven meer overwogen mogen worden. Met behulp van de cut kan bijvoorbeeld een if-then-else constructie worden geïmplementeerd.

kachel(Temperatuur, aan) :-
  Temperatuur < 18, !.
kachel(Temperatuur, uit) :-
  Temperatuur > 20, !.
kachel(_, afblijven).

?-kachel(21, Actie).
Actie=uit.
?-kachel(17, Actie).
Actie=aan.
?-kachel(19, Actie).
Actie=afblijven.

Zonder de cut zouden alternatieven worden overwogen, en worden twee antwoorden gevonden, aangezien de laatste clause altijd geldig is.

kachel(Temperatuur, aan) :-
  Temperatuur < 18.
kachel(Temperatuur, uit) :-
  Temperatuur > 20.
kachel(_, afblijven).

?-kachel(21, Actie).
Actie=uit.
Actie=afblijven.
?-kachel(17, Actie).
Actie=aan.
Actie=afblijven.

Recursie[bewerken]

Het komt vaak voor dat een regel in termen van zichzelf is gedefinieerd. Een lijst van letters, bijvoorbeeld, is lege lijst of een letter gevolgd door een lijst van letters. Vertaald in Prolog luidt de definitie:

charlist([Ch|Rest]) :-
  char_type(Ch, alpha),
  !,
  charlist(Rest).
charlist([]).

Deze vorm heet recursie (preciezer tail recursion) en komt veelvuldig voor in Prologprogramma's. De cut voorkomt onnodig terugzoeken, als Ch eenmaal als letter bekend is, zijn er geen alternatieven.

Een wat ingewikkelder voorbeeld zoekt alle letters uit een string en geeft die als resultaat terug.

charlist([Ch|Rest], [Ch|All]) :-
  char_type(Ch, alpha),
  !,
  charlist(Rest, All).
charlist([_|Rest], All) :-
  charlist(Rest, All).
charlist([], []).
?- charlist("87foo28723bar", L), writef("%s!\n", [L]).
foobar!
L = [102, 111, 111, 98, 97, 114].

Definite Clause Grammar[bewerken]

Een bijzonderheid van Prolog zijn Definite Clause Grammars (DCG), een manier om op eenvoudige wijze een syntax weer te geven in een vorm die sterk overeenkomt met de Backus Naur Form (BNF). Strikt genomen zijn DCG's geen onderdeel van de Prolog-standaard, maar ze komen in vrijwel elke implementatie voor.

Met behulp van DCG is het parsen van een integer tamelijk eenvoudig.

/* Een integer is een rij cijfers (digits). Is een rij digits
 * herkend, zet deze om naar een getal.
 */
integer(I) -->
        digits(Digits),
        {
          /* zet de gelezen rij cijfers om in een getal*/
          number_chars(I, Digits)
        }.
 
/* Een lijst van cijfers is een cijfer gevolgd door een lijst van cijfers... */
digits([D|Rest]) -->
        digit(D), !,
        digits(Rest).
/* ... of een lege lijst, als er geen invoer meer is. */
digits([]) -->
        [].
 
digit(D) -->
        [D],
        { 
          /* kijk na of D een cijfer is. */
          code_type(D, digit)
        }.

Voorbeeld[bewerken]

Een voorbeeld van een volledig Prolog-programma met enige kennis omtrent bestuurders, voertuigen en rijbewijzen.

/* Een prolog programma moet kunnen terugvallen op een paar
 * vaststaande feiten. In dit voorbeeld coderen we een beetje
 * kennis over bestuurders, voertuigen en rijbewijzen in de vorm van prolog
 * 'facts'. Logisch gezien zijn dit axioma's.
 */
 
voertuig(vrachtwagen, 'DAF').
voertuig(vrachtwagen, 'Scania').
voertuig(vrachtwagen, 'MAN').
voertuig(auto,        '2CV').
voertuig(auto,        'Fiat 500').
voertuig(auto,        'Golf GTI').
voertuig(motor,       'Harley-Davidson').
voertuig(motor,       'BMW').
voertuig(motor,       'Yamaha').
voertuig(brommer,     'Puch').
voertuig(brommer,     'Kreidler').
voertuig(brommer,     'Zundapp').
voertuig(fiets,       'Batavus').
voertuig(fiets,       'Union').
voertuig(fiets,       'Gazelle').
 
/* Dan een paar bestuurders die meer dan een rijbewijs
 * kunnen hebben.
 */
 
bestuurder(jantje,     [b, c, e]).
bestuurder(pietje,     [a, b, certificaat]).
bestuurder(keesje,     [b, e]).
bestuurder(klaasje,    [certificaat]).
bestuurder('jan-willem', []).
 
/* Vervolgens wordt door middel van een 'clause' gedefinieerd welk
 * rijbewijs voor welk type nodig is.
 */
 
rijbewijsNodig(c, X) :-
  voertuig(vrachtwagen, X).
rijbewijsNodig(b, X) :-
  voertuig(auto, X).
rijbewijsNodig(a, X) :-
  voertuig(motor, X).
rijbewijsNodig(certificaat, X) :-
  voertuig(brommer, X).
 
/* Met deze kennis is het mogelijk te zeggen of een bestuurder
 * een geldig rijbewijs heeft. Dat gebeurt alweer in een clause.
 *
 * Smoezen helpt niet...
 */
 
heeftGeldigRijbewijs(Bestuurder, Voertuig) :-
  rijbewijsNodig(Vereist, Voertuig),
  bestuurder(Bestuurder, Rijbewijzen),
  member(Vereist, Rijbewijzen).
 
/* Men mag echter op een 'Batavus', 'Gazelle' of 'Union' rijden zonder dat
 * men daarvoor een geldig rijbewijs heeft, maar zeggen dat iemand een geldig
 * rijbewijs heeft voor een fiets, is onzin. Iedereen mag fietsen en een
 * fietsrijbewijs bestaat niet.
 *
 * Dus is er een laatste 'clause' nodig.
 */
 
magBesturen(Bestuurder, Voertuig) :-
  heeftGeldigRijbewijs(Bestuurder, Voertuig).
magBesturen(Bestuurder, Voertuig) :-
  voertuig(_, Voertuig),
  bestuurder(Bestuurder, _),
  not(rijbewijsNodig(_, Voertuig)).

Het is nu mogelijk de Prologdatabase te ondervragen. Het predicaat 'bagof' maakt een list van alle succesvolle unificaties.

?- magBesturen(klaasje, 'DAF').
false.
?- magBesturen(klaasje, Voertuig).
Voertuig = 'Puch' ;
Voertuig = 'Kreidler' ;
Voertuig = 'Zundapp' ;
Voertuig = 'Batavus' ;
Voertuig = 'Union' ;
Voertuig = 'Gazelle'.

?- bagof(Voertuig, magBesturen(pietje, Voertuig), Voertuigen).
Voertuigen = ['2CV', 'Fiat 500', 'Golf GTI', 'Harley-Davidson', 'BMW', 'Yamaha', 'Puch', 'Kreidler', 'Zundapp'|...].

?- bagof(Bestuurder, magBesturen(Bestuurder, 'Union'), Bestuurders).
Bestuurders = [jantje, pietje, keesje, klaasje, 'jan-willem'].

?- bagof(Bestuurder, magBesturen(Bestuurder, '2CV'), Bestuurders).
Bestuurders = [jantje, pietje, keesje].

?- bagof(Bestuurder, magBesturen(Bestuurder, 'DAF'), Bestuurders).
Bestuurders = [jantje].

?- bagof(Voertuig, magBesturen(Bestuurder, Voertuig), Voertuigen).
Bestuurder = jantje,
Voertuigen = ['DAF', 'Scania', 'MAN', '2CV', 'Fiat 500', 'Golf GTI', 'Batavus', 'Union', 'Gazelle'] ;
Bestuurder = keesje,
Voertuigen = ['2CV', 'Fiat 500', 'Golf GTI', 'Batavus', 'Union', 'Gazelle'] ;
Bestuurder = klaasje,
Voertuigen = ['Puch', 'Kreidler', 'Zundapp', 'Batavus', 'Union', 'Gazelle'] ;
Bestuurder = pietje,
Voertuigen = ['2CV', 'Fiat 500', 'Golf GTI', 'Harley-Davidson', 'BMW', 'Yamaha', 'Puch', 'Kreidler', 'Zundapp'|...] ;
Bestuurder = 'jan-willem',
Voertuigen = ['Batavus', 'Union', 'Gazelle'].

Externe links[bewerken]

Bronnen

  • Prolog. Beschrijving van de standaard, W.F. Clocksin, C.S. Mellish, 1987, Kluwer Technische Boeken, ISBN 90-201-2074-3
  • Prolog Programming, Claudia Marcus, Arity Corporation, 1986, Addison Wesley, ISBN 0-201-14647-9
  • The practical application of Prolog, Dr. Dobbs

Voetnoten

Etalagester
Etalagester Dit artikel is op 5 januari 2012 in deze versie opgenomen in de etalage.