Prolog
Prolog | ||||
---|---|---|---|---|
Paradigma | logisch programmeren, declaratieve taal, Modulair programmeren | |||
Verschenen | 1973 (50 jaar) | |||
Ontworpen door | Alain Colmerauer, Robert Kowalski, Philippe Roussel | |||
Implementaties | SICStus Prolog, SWI-Prolog, YAP, GNU Prolog, Visual Prolog en anderen | |||
Dialecten | ISO Prolog | |||
Invloed op | Mercury, Oz, Erlang | |||
Besturingssysteem | Multiplatform | |||
Bestandsextensies | pl, pro, P | |||
|
Prolog (uit het Frans "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 (grotendeels) declaratieve taal is.[1]
Ontwikkeling
Prolog werd oorspronkelijk in 1971-72[2][3] 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 de nieuwe taal werd door Colmerauers collega Philippe Roussel geïmplementeerd in Algol, in het najaar van 1972; diens vrouw bedacht de naam van de nieuwe taal. De eerste applicatie was een basaal dialoogsysteem dat met een gebruiker in het Frans kon converseren. In 1973 kreeg Colmerauers groep genoeg geld toegewezen om een tweede implementatie te ontwikkelen: een interpreter, geschreven in Fortran.[2]
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. 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[4] en heeft ertoe geleid dat vele moderne implementaties beide versies ondersteunen.
Edinburgh-standaard
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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/ee/1rightarrow_blue.svg/15px-1rightarrow_blue.svg.png)
In 1983 ontwierp David H.D. Warren een virtuele machine gericht op de taal Prolog: een instructieset die Prolog-compilers kunnen gebruiken als intermediair tussen de semantiek van Prolog, gebaseerd op het doorzoeken van een verzameling mogelijke oplossingen voor een logisch probleem, en de werking van computerprocessors. WAM-programma's kunnen vervolgens direct uitgevoerd worden door een interpreter, of verder vertaald naar machinecode. Warrens werk maakte als eerste de uitvoering van logische programma's snel genoeg voor algemeen gebruik.[5]
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 moet worden geïmplementeerd en het wiel veelvuldig opnieuw moet worden uitgevonden.[6] Tevens worden onvermijdelijk machine-afhankelijkheden (machine dependencies) geïntroduceerd, wat de portabiliteit niet ten goede komt.[bron?]
Quintus en SICStus
Omdat standaarden ontbraken of nog in de kinderschoenen stonden,[6] 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.[7] SWI-Prolog, bijvoorbeeld, implementeert belangrijke delen van de Quintus/SICStus-specificatie.[8]
Standaardisering
De eerste pogingen de taal te standaardiseren dateren uit 1985, toen de AFNOR de eerste Prologwerkgroep in het leven riep.[4] 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[6] 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 Prolog-programma's breken.
Ondanks ISO/IEC 13211-1 spreken Covington et al. in hun Coding guidelines voor Prolog van een gebrek aan een alomvattende standaard voor de taal; volgens hen is de kleine Prolog-gemeenschap gefragmenteerd en voornamelijk georganiseerd rond de verschillende implementaties, waarvan geen enkele dominant is.[9]
Gebruik
Omdat Prolog is gebaseerd op formele logica en met behulp van een inference engine zelfstandig conclusies kan trekken, is deze taal geschikt om kennis te modelleren en de mens te ondersteunen bij het trekken van conclusies uit gegevens. De taal is dan ook een veelgebruikt hulpmiddel voor het verwerken van natuurlijke taal,[1][10] datamining,[11][12][13] het interpreteren van de uitkomsten van metingen, modellen en simulaties[bron?] en het bouwen van expertsystemen en onderzoek naar kunstmatige intelligentie.
Hoewel het gebruik van Prolog zich in eerste instantie beperkte tot de academische wereld, werden de implementaties gaandeweg stabiel genoeg zodat de taal in commercieel gebruik kon worden genomen. Begin jaren 90 had Prolog een "stabiele niche" verworven op de markt voor programmeertalen.[14] Tot de gebruikers in de industriële wereld behoorden Boeing, dat met behulp van een expertsysteem handleidingen voor de assemblage van connectors met lijsten van benodigde gereedschappen, materialen, onderdelen en procedures samenstelde. Het National Center for Atmospheric Research in de VS gebruikte op Prolog gebaseerde software om kortetermijnweerberichten te genereren, in Boedapest hield 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 adviseerde een toepassing het personeel van een waterleidingbedrijf over optimaal gebruik van pompen, zodat de druk in het waterleidingsysteem gelijk verdeeld is.[15] Ongeveer in dezelfde periode, echter, publiceerden onderzoekers die bij de ontwikkeling van logisch programmeren betrokken waren, een artikel waarin zij stelden dat dit paradigma "ondanks de theoretische voordelen" niet doorgebroken was: van de vijfhonderd applicaties op de publieke lijst "Prolog-1000" werden er slechts enkele door meer dan honderd mensen gebruikt.[16] Een schatting uit 2003 hield het aantal Prolog-gebruikers op honderdduizenden.[17]
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,[18] 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.
Een meer recent voorbeeld is het gebruik in Watson, het computersysteem van IBM dat de Amerikaanse quiz Jeopardy! won.[10] In het Nederlandse taalgebied is er het ontleedprogramma Alpino, dat in Prolog is geschreven.[19]
Invloed
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 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 als 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,[bron?] verschilt echter sterk van andere dialecten. Het belangrijkste verschil is dat types in Turbo Prolog statisch worden geverifieerd en dus moeten worden gedeclareerd.
De programmeertaal Erlang werd oorspronkelijk geïmplementeerd in Prolog; de ontwerpers van de taal stellen dat Erlang, zonder Prolog en de geschiktheid daarvan voor rapid prototyping, niet bestaan zou hebben.[20] Erlang was oorspronkelijk een dialect, of extensie, van Prolog en de twee talen hebben nog steeds oppervlakkige overeenkomsten (vooral in de syntaxis), maar Erlang werd later losgekoppeld van Prolog en ontwikkeld tot een functionele taal in plaats van een logische.[21]
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.
Datatypen
Variabelen
Een variabele 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)
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
Integers en floats stellen diverse getallen voor. De notatie verschilt niet van die in andere talen.
Structuren (structure)
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)
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
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
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
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 kan worden aangepast aan veranderende omstandigheden zonder de broncode te wijzigen.
Vragen, unificatie en ongebonden variabelen
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, getallen, lijsten of structuren worden geünificeerd. Als dit is gebeurd, is de variabele niet langer ongebonden, maar heeft een specifieke waarde.
- Atomen (atoms) en getallen 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 geünificeerd.
- Structuren kunnen uitsluitend met andere structuren worden geünificeerd als ze
- dezelfde ariteit hebben en
- 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
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)
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
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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4f/4gates.png/400px-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 | → (succes) | ||
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
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
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
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(Persoon, Voertuig) :- 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. Bovenstaande wordt dan:
magBesturen(Persoon, Voertuig) :- heeftGeldigRijbewijs(Persoon, Voertuig). magBesturen(Persoon, Voertuig) :- not(rijbewijsNodig(_, Voertuig)).
Alternatieven, backtracking en de cut operator
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
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.
Als-dan-anders
Er zijn meerdere mogelijkheden om een als-dan-anders constructie te implementeren in Prolog. De klassieke manier[22] maakt gebruik van een cut-operator, zoals in het kachelvoorbeeld hierboven, maar prolog kent ook een operator die deze constructie (min of meer) implementeert.
(Conditie -> Waar ; Onwaar)
Als Conditie bewezen kan worden, probeer de Waar-clausule te bewijzen, anders probeer de Onwaar-clausule te bewijzen. Als de Onwaar-clausule ontbreekt, zal de hele clausule falen als Conditie niet bewezen kan worden. Dat wil zeggen dat de volgende clausules equivalent zijn.
(Conditie -> Waar) (Conditie -> Waar ; fail)
De semantiek van deze operator, zeker met betrekking tot backtracking en de cut, is echter anders dan men in procedurele talen (zoals Pascal of C) zou verwachten. De operator wordt soms afgeraden omdat de betekenis, zeker als ze genest zijn of cut-operators in een van beide takken voorkomen, niet erg duidelijk zou zijn,[23][24][25] hoewel Covington et al. de "als-dan-anders"-constructie juist als alternatief voor de cut aandragen om deterministische conditionals te implementeren.[9] De constructie kan in SICStus Prolog een snelheidsverbetering opleveren omdat het kostbare backtracking kan worden vermeden.[26]
airco(Temperatuur, Actie) :- (Temperatuur > 23 -> Actie=aan ; Actie=uit ).
Recursie
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
Een bijzonderheid van Prolog zijn Definite Clause Grammars (DCG), een manier om op eenvoudige wijze een syntaxis 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
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 lijst 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'].
![Etalagester](http://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Fairytale_bookmark_golden.svg/20px-Fairytale_bookmark_golden.svg.png)
Externe links
- (en) GNU-Prolog
- (en) SICStus Prolog
- (en) Strawberry Prolog
- (en) SWI-Prolog
- (en) Online Prolog-cursus
Bronnen
- Stuart J. Russell en Peter Norvig (2003). Artificial Intelligence: A Modern Approach. Prentice Hall, ISBN 0-13-080302-2.
- 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
- ↑ a b Pereira, Fernando C. N., Stuart M. Shieber (2002 (1987)). Prolog and Natural-Language Analysis. Microtome, pp. 35. Gearchiveerd op 10 april 2021.
- ↑ a b Alain, Colmerauer, Philippe, Roussel (1993). The birth of Prolog. Gearchiveerd op 14 januari 2012. ACM SIGPLAN Notices 28 (3): 37–52. DOI:10.1145/154766.155362.
- ↑ Robert A., Kowalski (1988). The early years of logic programming. Gearchiveerd op 9 november 2020. Communications of the ACM 31 (1): 38–43
- ↑ a b Prolog overview, de Ransar
- ↑ Russell en Norvig (2003:290–292).
- ↑ a b c SICStus Prolog -- the first 25 years, Mats Carlsson, Per Mildner
- ↑ Prolog-vergelijkingssite, Frank Bergmann
- ↑ SWI-Prolog website
- ↑ a b M. A. Covington, R. Bagnara, R. A. O'Keefe, J. Wielemaker en S. Price (2011). "Coding guidelines for Prolog". In Theory and Practice of Logic Programming 12(6). Tevens arXiv:0911.2899.
- ↑ a b "Natural Language Processing With Prolog in the IBM Watson System", Lally, Fodor, 2011
- ↑ SICStus Prolog Customer References (21 september 2014). Gearchiveerd op 14 april 2021.
- ↑ David Schmidt, Introduction to Prolog. Kansas State University (21 september 2014). Gearchiveerd op 5 maart 2015.
- ↑ Dzeroskisz, Multi-Relational Data Mining: An Introduction (21 september 2014). Gearchiveerd op 24 december 2014.
- ↑ (1994). 1983–1993: The wonder years of sequential Prolog implementation. Gearchiveerd op 11 december 2018. Journal of Logic Programming 19: 385–441
- ↑ Roth, Al, "The Practical Application of Prolog", 10 december 2002. Gearchiveerd op 16 april 2021. Oorspronkelijk in AI Expert, 1993.
- ↑ Zoltan Somogyi, Fergus Henderson, Thomas Conway en Richard O'Keefe (1995). Logic Programming for the Real World. ILPS'95 Postconference Workshop on Visions for the Future of Logic Programming.
- ↑ Russell en Norvig (2003:289).
- ↑ SICStus
- ↑ Alpino User Guide (n.d.). Rijksuniversiteit Groningen.
- ↑ J. L. Armstrong, S. R. Virding en M. C. Williams (1992). Use of Prolog for developing a new programming language. First Conference on the Practical Application of Prolog. Association for Logic Programming.
- ↑ J. L. Armstrong (1996). Erlang—a Survey of the Language and its Industrial Applications. Proc. INAP. Vol. 96. 1996.
- ↑ Prolog Programming, C. Marcus
- ↑ Frequently Asked Questions for SWI-Prolog
- ↑ Prolog Programming A First Course, Paul Brna, University of Edinburgh
- ↑ "The Prolog Dictionary", Bill Wilson, School of Computer Science and Engineering
- ↑ Sicstus documentatie