Prolog
Prolog (Fr. programmation en logique, "programmeren met logica") is een logische programmeertaal die ontworpen werd door Robert Kowalski en Alain Colmerauer aan de universiteit van Marseille (Frankrijk) in het jaar 1973. De taal heeft een sterk logisch en declaratief karakter: feiten en relaties worden gedeclareerd in een eenvoudig soort database die bevraagd kan worden.
Inhoud |
[bewerk] Inleiding
Oorspronkelijk was Prolog enkel bedoeld als een normale, alternatieve programmeertaal voor applicaties, maar algauw zag men dat de eenvoudige syntax ook kon gebruikt worden voor een logische programmeertaal voor alle doeleinden. Dit idee werd vooral bekrachtigd wanneer Prolog de eerste keuze was van het Japanse Fifth Generation Computer Project. Het Fifth-Generation Computer Project was een reusachtig Japans overheidsproject tijdens de jaren '80, dat als doel had een nieuwe revolutionaire supercomputer te ontwikkelen met Kunstmatige Intelligentie mogelijkheden.
Prolog heeft drie belangrijke voordelen ten opzichte van andere gelijkaardige talen:
- De syntaxis en semantiek van Prolog is sterk gebaseerd op de predikatenlogica.
- Prolog voorziet automatische backtracking, dit is een eenvoudig en snel systeem om objecten op te zoeken, wat een veelgebruikte functie is van A.I.
- Prolog ondersteunt redeneringen in meerdere richtingen. Concreet wil dit zeggen dat argumenten vrij in meerdere procedure-aanroepen kunnen worden gebruikt, zodat dezelfde procedure-definitie op meerdere manieren kan worden gebruikt zodat verschillende redeneringen ontstaan.
Ondanks deze mogelijkheden, moet Prolog niet aan snelheid inboeten ten opzichte van andere logische programmeertalen. Prolog is volgens velen ook een uitstekend leermiddel om Kunstmatige Intelligentie beter te kunnen begrijpen.
[bewerk] Intelligentie en computers
Computers zijn niet intelligent, ook al doen ze soms heel ingewikkelde dingen, en rekenen ze nog zo snel. Ze missen de interactie met de omgeving. Je zou ze kunnen vergelijken met planten, ze doen waarvoor ze gebouwd zijn, en hebben daar niet echt invloed op. Computers zijn alleen structuur. Maar computers zijn wel in staat om andere dingen te simuleren, ook intelligentie, waar interactie voor nodig is.
Het is de vraag wanneer een computer 'intelligent' genoemd mag worden. Is het vertonen van intelligent gedrag voldoende (d.w.z. de computer is op een slimme manier geprogrammeerd, maar hij is wel echt gewoon geprogrammeerd), of stellen we hogere eisen aan een definitie van intelligentie? (NB.: Hetzelfde vraagstuk speelt bij mensen; zijn wij 'echt' intelligent omdat wij een bewustzijn hebben, of zijn wij ook maar een combinatie van chemische stofjes en elektrische stootjes?).
Kunstmatige intelligentie kan voor de mens van belang zijn omdat kunstmatig intelligente computers gemakkelijker bepaalde taken van ons over kunnen nemen, danwel beter van pas komen door te assisteren op een (voor mensen) logische manier.
Kunstmatige Intelligentie voor computers betekent meestal geavanceerde Software Engineering, ingewikkelde software voor complexe problemen die moeilijk op de normale manier kunnen worden opgelost. AI programma's maken echter geen gebruik van normale procedures zoals je die zou gebruiken in Java of Visual Basic. Deze programma's zijn op een meer natuurlijke manier opgebouwd, deze programma's denken niet als een machine, maar eerder als een natuurlijke persoon. Net zoals mensen niet perfect zijn, zijn kunstmatig intelligente programma's ook niet perfect en kunnen ze dus ook fouten maken.
Kunstmatige Intelligentie omvat:
- Computers laten communiceren door middel van een menselijke taal zoals het Engels. De output gebeurt dan door ofwel tekst te tonen op een scherm ofwel door spraaktechnnologie. De input gebeurt door tekst die ingetypt wordt door een gebruiker of door spraakherkenning. (natuurlijke talen),
- Computers complexe, gerelateerde feiten laten onthouden en hieruit conclusies te laten trekken. (inference),
- Computers zelf acties laten plannen om het beoogde doel te bereiken (planning),
- Computers advies laten geven op basis van gecompliceerde regels voor verscheidene situaties (expert systemen),
- Computers dingen laten herkennen door middel van camera's (vision),
- Computers zelf laten bewegen en dingen laten gebruiken (robotica). De Prolog-taal heeft vooral betrekking op de echte kern elementen van Kunstmatige Intelligentie, namelijk inference, expert systems en planning. De andere drie elementen zijn voor meer gespecialiseerde doeleinden. Toch kunnen we zeggen dat alle zes elementen heel moeilijk aan te leren en te gebruiken zijn. Vooraleer men echte vooruitgang kan zien in één van deze vlakken, is er vaak jarenlange research nodig. De sleutel tot kunstmatige intelligentie is reductionisme, dit is de graad waarin een programma afwijkt van het menselijke denken. Reductionisme omvat dus hoe vaak een programma overeenstemt met het menselijke gedrag en ook hoe groot de afwijking is van het gedrag als het programma daadwerkelijk afwijkt. AI-technieken en –ideeën, zijn moeilijker te begrijpen dan de meeste andere elementen van de informatica. Er zijn namelijk veel meer details waarop men moet letten. Kunstmatige Intelligentie is op zijn best wanneer het gebruikt wordt voor complexe problemen waar algemene principes geen (of geen volledige) oplossing kunnen bieden. Deze complexiteit duidt echter ook de limiet aan voor een programmeur. Een programmeur kan een complex probleem maar oplossen tot het niveau waarop hij er zelf niets meer van begrijpt. Meestal zijn AI programma's simulaties, waarbij de programmeur een bepaalde situatie creëert en dan het programma laat uitvoeren. Hij weet dus niet op voorhand hoe het programma zal reageren, in tegenstelling tot klassieke programma's waarbij de programmeur heel goed weet wat er gebeurt.
[bewerk] Regels voor intelligent gedrag
De kunstmatige intelligentie die het makkelijkst te begrijpen is, is de kunstmatige intelligentie die gebruik maak van vaste regels, en dus in een bepaalde situatie ook altijd hetzelfde doet. Toch kan deze soort kunstmatige intelligentie voor heel complex gedrag zorgen.
Neem nu bijvoorbeeld een school vissen. Het lijkt dat het een heel ingewikkeld proces is om met een hele school vissen een bepaalde richting uit te gaan zonder dat de groep uit elkaar valt of dat er vissen in de knel komen. Toch zijn er maar drie basisregels voor nodig:
- wijk uit voor obstakels,
- houd een gelijke afstand tot de vissen naast je, en pas je snelheid aan,
- houd de richting van de groep aan. Op deze manier kun je een hele groep vissen in een school laten zwemmen. De groep vissen heeft natuurlijk geen vast doel waar ze met z'n allen heen gaan, maar het gedrag als een grote groep staat vast. Met een paar aanpassingen zou je ervoor kunnen zorgen dat vissen die voedsel waarnemen, naar daar te sturen. De andere vissen zullen dan hun richting bijstellen. Deze regels kun je nog verbeteren door er bepaalde prioriteiten aan te verbinden. Als er bijvoorbeeld heel ver een beetje voedsel is, en dichtbij een gevaar, dan is het beter als de vissen uitwijken voor het gevaar, in plaats van recht naar het eten te zwemmen. Het gevaar heeft dan een hogere prioriteit. Op deze manier kan je de prioriteit ook laten afhangen van de afstand tot het voedsel bijvoorbeeld en hoe hongerig de vis is. In de natuur is dit alles gebeurd door evolutie. Door telkens uitbreidingen te maken op de manier waarop de vis denkt, wordt het programma waarmee de vis denkt steeds ingewikkelder. Met een vis is dat nog niet zo'n probleem, maar als je dit gaat toepassen op een mens is het al gauw zo ingewikkeld, dat je niet meer weet waar je een regel voor maakt, en dat het project vastloopt. De programmeur moet dus een grens trekken in de complexiteit.
[bewerk] De Prolog taal
[bewerk] Constructie van een Prolog programma
Een computerprogramma dat werd geschreven in Prolog is opgebouwd uit een sequentie van secties. Niet elke sectie moet aanwezig zijn. De volgende secties kunnen bestaan:
[bewerk] Constants
Constanten zijn een type variabele dat in de meeste programmeertalen vervat zit. Een constante wordt meteen bij zijn declaratie van een waarde voorzien. Die waarde kan later niet meer worden veranderd. Ze worden in deze vorm geschreven:
<id> = <definition>
Volgend is een voorbeeld van een constants-sectie:
blue = 5 gray = 0xaa language = dutch is_car = true
[bewerk] Domains
In de domains-sectie wordt gedeclareerd wat de domeinen van de argumenten van de predicaten werkelijk zijn. De compiler wordt geïnformeerd over de argumenten van de predicaten. De domains-sectie wordt om twee redenen gebruikt.
1. Bestaande domeinen kunnen een distinctieve naam krijgen. Zo worden ze leesbaarder. Bijvoorbeeld:
- België is een land in Europa met een bevolking van 10,6 miljoen mensen.
Deze informatie kan als volgt in een predicaat worden gedeclareerd:
predicates country(string, string, long)
Als iemand deze code moet lezen zal hij problemen hebben met het begrijpen van de betekenis van de 3 argumenten. Door domeinen te gebruiken kan dit predicaat meer elegant en verstaanbaar worden geschreven.
domains name, continent = string population = long predicates country(name, continent, population)
2. In de domain-sectie worden ook de samengestelde domeinen gedeclareerd. Dat zijn domeinen die uit meerdere stukken informatie bestaan die als één worden behandeld. Het klassieke voorbeeld:
domains comp_type = address(string, integer, integer, string) goal client5 = address(beekdal, 4, 2920, kalmthout)
[bewerk] Facts
Een Prolog programma is een verzameling van feiten en regels. Het is mogelijk die feiten te updaten terwijl het programma loopt. Daarvoor heeft het programma een dynamische – of interne database. Prolog heeft een speciale facts-sectie om die dynamische feiten te declareren. Vroeger heette die sectie database, maar die term geraakte buiten gebruik.
[bewerk] Predicates
In het vakgebied van de computerprogrammatie is een predicaat gekend als een operator of functie die een boolean genereert. Waar of vals dus. Als een predicaat gedefinieerd wordt in de clauses-sectie moet ze vooraf in de predicates-sectie gedeclareerd worden. Anders heeft Prolog geen idee waarover je spreekt. De predicaten vertellen Prolog tot welk domein de argumenten van de predicaten behoren. Neem dit predicaat bijvoorbeeld:
predicates ball(sporter) usesBall(sporter, useBall)
In de clauses-sectie worden deze predicaten gebruikt om feiten af te leiden uit andere feiten. Bijvoorbeeld door dit te schrijven:
clauses ball(X):-usesBall(X,Y),Y=yes.
Deze lijn zegt dat een sport X een bal gebruikt als usesBall waar blijkt als het argument useBall op yes staat.
[bewerk] Clauses
Clauses zijn het belangrijkste onderdeel van een Prolog programma. Zij vormen de sequentie die door het programma wordt gevolgd. Alle feiten en regels die het programma inhoudt worden hier geschreven. Ze worden geschreven met behulp van predicaten die eerder in de predicates-sectie werden gedeclareerd. De clauses die bij een bepaald predicaat horen moeten achter elkaar geplaatst worden. De aldus gevormde sequenties van clauses die een predicaat definiëren worden procedures genoemd. Als Prolog een doel probeert te bereiken zal het aan het begin van de clauses-sectie beginnen en alle clausen naar beneden aflopen terwijl het naar feiten en regels zoekt die overeenkomen. Aan elke clause wordt een pointer gezet. Als een clause niet naar een oplossing lijkt te leiden wordt teruggekeerd naar die pointer van waaruit dan verder wordt gezocht. Het is mogelijk om in deze sectie vragen aan de gebruiker te stellen en de antwoorden als invoer te gebruiken voor argumenten.
De volgende clause kan enkel in waar of vals resulteren. Een sport X gebruikt een bal of gebruikt er geen.
clauses ball(X):-usesBall(X,Y),Y=yes.
De voorlaatste clauses in the sectie zijn diegene die een uiteindelijke oplossing geven voor het gegeven probleem. Als de sport X binnen gespeeld wordt met een bal en zonder hulpstuk of net kan het programma besluiten dat de sport in kwestie basketbal is.
category(X,"basketball player"):- indoor(X),ball(X),noTool(X),noNet(X).
Als die categorie fout blijkt te zijn zal Prolog verder zoeken in de volgende regels.
category(X,"volleyball player"):- indoor(X),ball(X),noTool(X),net(X). category(X,"golf player"):- outdoor(X),ball(X),tool(X),noNet(X).
De laatste clauses zullen iets zijn in de aard van volgende code:
clauses
…
run:-consult("sporters.txt"),
write("Give the name of the sportsman: "),
readln(X),
category(X,Y),
write(X," is a ",Y),nl,
save("sporters.txt").
goal
run.
Het programma zal beginnen met run in de goal-sectie. Van daaruit zal het de clauses beginnen uitvoeren die als voorwaarden in de clauses-sectie staan. Als elk van die clauses succesvol is, is run succesvol, en dus is het programma succesvol. Deze code vertelt Prolog wat je wil hebben. Het is de belangrijkste code in het programma.
[bewerk] Goal
De goal-sectie ziet er hetzelfde uit als een regel. Het is een lijst van subdoelen. De goal-sectie is het beginpunt van het programma. Prolog zal met het eerste subdoel beginnen en alle subdoelen één voor één afwerken.
[bewerk] Keywords
1. De volgende woorden zijn Prolog-keywords maar werden reeds in het bovenstaande punt uitgelegd: constants, domains, facts, predicates, clauses en goal.
2. De predicaten in de predicaten-sectie kunnen voorafgegaan worden door een keyword dat het type aangeeft. Die keywords zijn:
- Erroneus: altijd afsluiten,
- Failure: altijd falen,
- Procedure: altijd slagen,
- Determ: slagen of falen,
- Multi: één of meerdere oplossingen,
- Nondeterm: geen of meerdere oplossingen.
3. Zoals gezegd kan Prolog dynamisch feiten leren. Dat betekent dat het programma slimmer wordt tijdens de uitvoering. Al die kennis gaat echter verloren als het programma afgelopen is. Daarom werden twee keywords geïmplementeerd die die feiten opslaan in een bestand op de harde schijf. Eerst is er het keyword save(<filename>). Als dit in de clauses-sectie wordt gezet zal Prolog alle dynamisch geleerde feiten in haar database opslaan in het bestand dat tussen de haakjes werd aangegeven. Als dat bestand al bestaat wordt het overschreven. Dan is er het keyword consult(<filename>). Daarmee wordt het gegeven bestand geopend en worden alle feiten die zich erin bevinden naar de database gekopieerd. Het bestand moet bestaan of er komt een fout waardoor het hele programma faalt.
4. Prolog programma's kunnen ook met de gebruiker communiceren. Daardoor kan het programma vragen stellen, antwoorden krijgen en ook de oplossing van het probleem weergeven. Uitvoer wordt gegeven met het keyword write(<text>). De gegeven tekst wordt op het scherm weergegeven. Als het programma invoer nodig heeft wordt het keyword readln(<variable>) gebruikt. Het programma zal worden onderbroken tot de gebruiker op <enter> heeft gedrukt. Alle karakters die op de lijn voor deze <enter> werden getypt worden naar de aangeduide variabele gekopieerd. Tenslotte zijn ook nog openread, openwrite en closefile beschikbaar voor in- en uitvoer naar bestanden.
5. Feiten kunnen ook worden gedeclareerd met determ of met single. Zie de volgende code waar counter single werd gedeclareerd.
facts single counter(integer)
Single betekent dat er exact 1 resultaat moet zijn. Een feit dat gedeclareerd werd met determ moet 0 of 1 resultaten hebben.
6. Soms is het nuttig om feiten en regels toe te voegen aan de database van het programma tijdens de uitvoering. Bijvoorbeeld om afgeleide feiten te gebruiken om nieuwe feiten af te leiden. Deze clauses kunnen toegevoegd worden met het volgende predicaat:
assert(<term>) of asserta(<term>)
De eerste zal <term> toevoegen aan het einde van de database. De tweede zal de term toevoegen aan het begin. Op dezelfde manier kunnen feiten weer worden verwijderd uit de database. Dat gebeurt met dit predicaat:
retract(is_dog("Cody")
Er bestaat ook het keyword retractall() dat alle entiteiten in de database verwijdert die voldoen aan een gegeven voorwaarde.
retractall(X)
[bewerk] Symbolen
1. In Prolog wordt commentaar omgeven door /* <comment> */ of voorafgegaan door % <comment>.
2. Het symbool _ (underscore) wordt als anonieme variabele gebruikt. Het verschil is dat, behalve dat het geen naam heeft, de variabele nooit een waarde zal krijgen. Neem volgend feit bijvoorbeeld.
facts is_dog_of(Cody, _ )
Het resultaat zal zijn dat eender wat in het volgende
goal is_dog_of(Cody, <persons name>)
waar is. Het maakt niet uit wat als <persons name> werd gegeven.
4. Prolog kent ook de operatoren +, -, * en / voor respectievelijk optellen, aftrekken, vermenigvuldigen en delen. Deze voorgedefinieerde operatoren laten toe een som te schrijven als
5 + 3 in plaats van + (5, 3)
5. Lijsten zijn in Prolog een geordende verzameling van Prolog termen. Ze worden aangegeven met de [ en ] (vierkante haken) symbolen. Een lijst met een gekend aantal elementen wordt als volgt gemaakt:
[1, two, Three, [4, 4.5], 5]
Deze lijst heeft 5 elementen. 1, two En 5 zijn waarden, Three is een variabele en [4, 4.5] is een sublijst. Lijsten bestaan in Prolog uit twee delen. Een head dat het eerste element in de lijst voorstelt en een tail die alle elementen behalve de head voorstelt. Deze head+tail constructie wordt gebruikt om door de lijst te lopen en elementen toe te voegen of te verwijderen.
write_list([H|T]) :- write(H), write_list(T).
Deze code schrijft de elementen van een lijst één voor één op het scherm door middel van recursie. Eerst wordt de head van de lijst geschreven. Die is gekend door de variabele H. De rest van de lijst is de tail gekend door de variabele T. Dan roept de functie zichzelf op met T als argument. Binnen die tail is het eerste element weer gekend als head.
[1, 2, 3, 4] [2, 3, 4] [3, 4] [4] []
De volledige lijst heeft 4 elementen. 1 Is de head, [2,3,4] is de tail. Deze tail is een lijst op zichzelf. Erbinnen is 2 de head en [3,4] weer de tail. Deze recursie gaat verder tot de lijst leeg is.
6. Unificatie wordt in Prolog aangegeven met het symbool = (gelijkheidsteken). Hieronder zal unificatie worden uitgelegd.
[bewerk] Variabelen
In Prolog worden variabelen ook logische variabelen genoemd. Ze worden voorgesteld door een reeks karakters, cijfers en de _ (underscore). Een aantal voorbeelden van geldige namen voor variabelen in Prolog zijn:
- X
- Number_of_cars
- _counter115
Deze variabelen hebben de clause waarin ze voorkomen als bereik. Als twee namen hetzelfde zijn verwijzen ze naar dezelfde variabele. Er is ook een speciale anonieme variabele die wordt aangeduid door het symbool _ (underscore). Deze variabele is een plaatshouder in situaties waarin de waarde van de variabele onbelangrijk is.
[bewerk] Datatypen
Prolog kent meerdere datatypen:
- Integer: De integer in Prolog is een getal van -8388608 tot +8388608.
- Real: De real is een datatype voor decimale getallen.
- Character: Een character bevat één enkel karakter van eender welke soort. Het kan A, a, 1, -, _, € of eender welk ander karakter zijn.
- String: De tekenreeks werd als een apart datatype geimplementeerd. Het is dus geen lijst van characters. Daarom kunnen head-tail operaties er niet op toegepast worden. Er zijn wel ingebouwde functies beschikbaar om strings naar lijsten van characters om te zetten en omgekeerd.
- Boolean: De boolean is het meest eenvoudige datatype. Ze gebruikt slechts één bit in het geheugen. De waarde is 1 of 0. In Prolog en de meeste andere programmeertalen worden die waarden voorgesteld door de constanten true en false.
- Symbol: Dit is het type variabele dat slechts één maal ingesteld kan worden. Het resultaat van een unificatie tussen meerdere termen wordt erin opgeslagen. Alhoewel ze als datatype wordt beschreven, is het meer een variabele waarin eender wat kan worden opgeslagen.
- Unificatie: Het concept unificatie is één van de hoofd ideeën achter Prolog. Het is het mechanisme van het binden van de waarden van variabelen. Het kan gezien worden als een eenmalige toewijzing.
- De operatie wordt geschreven met het symbool = (gelijkheidsteken). Een niet-ingestelde variabele kan geunificeerd worden met een atoom, term of een andere niet-ingestelde variabele en zo effectief zijn alias worden.
- Een Prolog atoom kan geunificeerd worden met hetzelfde atoom. Een term kan geunificeerd worden met een andere term als de hoogste functiesymbolen en ariteiten van de termen gelijk zijn en als de parameters gelijktijdig geunificeerd kunnen worden.
- De volgorde van de opeenvolgende unificaties is onbelangrijk omdat Prolog een declaratieve taal is.
[bewerk] Vergelijking met conventionele talen
Prolog is een volwaardige programmeertaal, zeer geschikt voor het schrijven van regels. Omdat het een volwaardige taal is kan Prolog gebruikt worden om elke gewenste applicatie te schrijven. Net als alle andere programmeertalen heeft Prolog haar sterke en zwakke punten. De sterke punten van Prolog zijn de zwakke van conventionele talen, en de sterke punten van die conventionele talen zijn de zwaktes van Prolog. Hoewel Prolog onafhankelijk kan worden gebruikt complementeert ze eigenlijk conventionele programmeertalen als ze samen worden gebruikt in een applicatie. Prolog is een logische taal die gebruikt wordt door programma's die niet-numerieke objecten gebruiken. Daarom wordt ze veel gebruikt voor kunstmatige intelligentie. De taal is in staat problemen op te lossen zonder vooraf te weten hoe.
[bewerk] Conventionele talen
De term conventionele taal wordt veel gebruikt in dit hoofdstuk. Eerst zullen we uitleggen wat met die term wordt bedoeld.
Er zijn vele verschillende vormen van programmeren en veel programmeerparadigma's. Prolog behoort tot het constraint programming, wat op zijn beurt valt onder logic programming. Constraint programming definiëert een aantal voorwaarden waaraan een oplossing moet voldoen in plaats van de stappen te definiëren die tot de oplossing leiden. Hier worden met de term conventionele talen alle programmeertalen bedoelt die onder een ander programmeerparadigma vallen en dus wel stappen definiëren om de oplossing te bereiken.
Enkele talen die onder deze term vallen zijn Visual Basic, C, Java, Pascal en COBOL.
[bewerk] Programmeertechniek
De programmeertechniek die in Prolog wordt gebruikt is het declaratief programmeren. Dat betekent dat de programmeur aan de computer zegt wat hij moet doen. Conventionele talen gebruiken een techniek die proceduraal programmeren heet. Hier wordt de computer verteld hoe hij iets moet doen.
Aan een Prolog programma kan worden gevraagd om een glas water te vullen. Aan de hand van de regels die het kent, kan het programma die taak vervullen. Een conventioneel programma kan dit niet. Elke stap moet in de juiste volgorde geprogrammeerd worden. De sequentie zal beginnen met het nemen van het glas en eindigen met het neerzetten van de fles water. Daar zien we de link met kunstmatige intelligentie.
[bewerk] Regels en instructies
Prolog programma's bestaan niet uit een reeks instructies zoals een conventioneel programma. In plaats daarvan is er een reeks regels. Die regels definiëren relaties tussen entiteiten. Oplossingen worden gevonden door query's toe te passen op die regels. Het programma kan dynamisch regels toevoegen aan haar database en alzo bijleren. Weer zien we een link met kunstmatige intelligentie.
[bewerk] Continuations
Net als conventionele programmeertalen kent Prolog de forwarding continuation. Dit is de plaats waar een programma naartoe moet gaan als de oproep van een procedure succesvol is verlopen. Prolog houd de punten waar ze beslissingen moest nemen en de genomen beslissing bij. Als ergens een verkeerde beslissing wordt genomen keert het programma terug naar zo'n punt. Dat wordt backtracking genoemd. Omdat conventionele programma's sequentieel zijn houden ze die punten niet bij en kennen ze geen backtracking.
[bewerk] Datatypen
Er zijn verschillen tussen Prolog en conventionele programmeertalen wat betreft de behandeling van datastructuren. Uiteindelijk zijn die verschillen in het voordeel van de programmeur omdat de structuren van Prolog gemakkelijker zijn om mee te werken en om te definiëren. Ze zijn ook beter beschermd tegen fouten zoals illegale geheugentoegangen. De controle over de waarden is ook zeer verschillend. De ingebouwde zoekmogelijkheden zijn, eenmaal duidelijk, een zeer krachtig middel om mee te programmeren.
[bewerk] Variabelen
In Prolog worden variabelen ook logische variabelen genoemd. Deze logische variabelen zijn wild cards voor Prolog's pattern matching en unificatie. Ze nemen gewoonweg de waarde aan die het resultaat was van de unificatie van andere Prolog termen.
In conventionele programmeertalen hebben variabelen een specifiek datatype en verwijzen ze naar een plaats in het geheugen. Het zijn Pointers.
[bewerk] Waarde van variabelen
In conventionele programmeertalen kunnen variabelen zo vaak als gewenst van waarde veranderd worden als de nieuwe waarde van het juiste datatype is. In Prolog daarentegen kunnen variabelen enkel een waarde krijgen van het mechanisme dat unificatie heet. Een variabele kan enkel van geen waarde naar een waarde gaan. Een niet-ingestelde variabele kan geunificeerd worden met een atoom, term of een andere niet-ingestelde variabele en zo zijn alias worden.
Het belangrijkste verschil is dat je het volgende kan doen in conventionele talen maar niet in Prolog:
X = X + 1 en X = 2 X = 3
en dat eens ingesteld de waarde niet meer veranderd kan worden door een later doel.
[bewerk] Recursie
In conventionele programmeertalen wordt meestal gebruikgemaakt van for- en while lussen voor het herhaald instellen van variabelen. Omdat variabelen in Prolog niet heringesteld kunnen worden zijn er geen lusstructuren in de taal. In de plaats daarvan wordt recursie gebruikt. Recursie komt voor als een functie zichzelf oproept tijdens de uitvoer van het programma. Het resultaat is dat elke keer de functie opgeroepen wordt, ze zichzelf opnieuw oproept, en zo wordt een soort lus gemaakt.
De predicaten in Prolog kunnen recursief zijn. Elke recursieve oproep heeft haar eigen variabelen. Er is een link tussen de variabelen van het oproepende predicaat en die van het opgeroepen predicaat.
[bewerk] Constraints
Constraints of beperkingen zijn een soort informatie die vaak voorkomt in de specificaties van programmeeropdrachten. Bijvoorbeeld:
- De breedte moet groter zijn dan 5 meter.
is een constraint. Conventionele programmeertalen laten niet toe dat zulke informatie in een expressie wordt geprogrammeerd. De breedte van een object zou in de constructor van elke klasse die ze nodig heeft gecontroleerd moeten worden met een if-then-else constructie. Dat is een omslachtig proces.
Beperkingen bieden vaak bijkomende informatie. Als gekend is dat X en Y beiden kleiner zijn dan 10 en dat X+Y > 10 dan is elke oplossing uitgesloten. Er moeten geen waarden worden getest. Een aantal Beperkingen zouden kunnen bestaan op X. Elke beperking apart kan geen waarde voor X bepalen maar gecombineerd kunnen ze dat wel. Dat is een krachtige manier van redeneren en dit soort model voor probleemoplossing is in veel gevallen bruikbaar. Conventionele programmeertalen ondersteunen het echter niet.
[bewerk] Samenvatting
Een samenvatting van de verschillen tussen Prolog en conventionele programmeertalen:
| Prolog | Conventionele - | |
|---|---|---|
| Programmering: | declaratief | procedureel |
| Instructies: | regels | instructies |
| Continuations: | forwarding & backtracking | enkel forwarding |
| Datatypen: | eenvoudiger | minder eenvoudig |
| Variabelen: | wild card | pointer |
| Waarden: | eenmaal instellen | vrij gebruik |
| Lussen: | recursie | while - en for-lus en recursie |
| Constraints: | programmeerbaar | niet programmeerbaar |
[bewerk] Kunstmatige intelligentie via Prolog
[bewerk] Feiten afleiden
We kunnen feiten, of facts, in een computer opslaan. Bij kunstmatige intelligentie willen we dat de computer deze opgeslagen feiten beoordeelt en hieruit nieuwe feiten afleidt. Dit principe wordt inference genoemd.
Het beoordelen en afleiden van feiten berust op drie basisconcepten:
[bewerk] Feiten opvragen (queries)
Eén ding dat we met deze feiten kunnen doen, is ze opvragen. Dit is de gebruikelijke methode voor Prolog Interpreters, dit is software die Prolog code interpreteert en uitvoert. De interpreter wacht op gegevens van de gebruiker, die hij dan kan opzoeken in de feiten database. Een Prolog interpreter is geen AI programma, maar een tool om AI programma's die in Prolog geschreven zijn, uit te voeren.
Je kan zien dat de Prolog interpreter in query modus staat, wanneer er een ? verschijnt vooraan elke lijn. De query modus werkt ongeveer op dezelfde manier als andere standaard database query talen zoals SQL of QUEL. Om dit enigszins te verduidelijken, hebben we een klein voorbeeldprogramma. Stel dat we volgende feiten in de computer hebben ingevoerd:
a_kind_of(enterprise,ship). a_kind_of(kennedy,ship). part_of(enterprise,u_s_navy). part_of(kennedy,u_s_navy). part_of(u_s_navy,u_s_government). a_kind_of(u_s_government,government). color(ship,gray). location(enterprise,15n35e). has(u_s_government,civil_service_system).
Deze feiten die nu bekend zijn bij de Prolog interpreter, worden ook een Prolog Database genoemd. Deze database kan echter ook geladen worden vanuit bestanden. In query modus kunnen we nu het volgende typen:
- ? - part_of(kennedy,u_s_navy).
Na deze vraag, zal de interpreter antwoorden met yes of no al naargelang het opgevraagde feit bekend is of niet. In dit geval zal dit dus een 'yes' zijn, aangezien het opgevraagde feit, in de Prolog database staat. We noemen dit ook een query success. Vragen we daarentegen het volgende:
- ? - part_of(pequod,u_s_navy).
Hierop zal de computer antwoorden met no omdat het opgevraagde feit niet gevonden werd. Dit wordt ook wel een query failure genoemd.
[bewerk] Werken met variabelen
Dit soort queries is heel eenvoudig en zijn eigenlijk niet zo interessant voor een applicatie. Wat interessanter is, zijn queries met één of meerdere variabelen. De Prolog interpreter zal dan proberen die variabelen in te vullen op basis van de feitendatabase. Zo kunnen we bijvoorbeeld vragen of een part_of, een enterprise heeft als eerste argument en eender wat als tweede argument. De query ziet er dan als volgt uit:
- ? - part_of(enterprise,X).
We kunnen dit als volgt lezen:
- Vind een X, zodanig dat part_of(enterprise,X) waar is.
De Prolog interpreter zal dan de feiten doorlopen en proberen van een X te vinden die het antwoord true geeft. Wanneer er een overeenkomst wordt gevonden, dan verschijnt er X=, gevolgd door het tweede argument. In dit geval zal je dan het antwoord X=u_s_navy krijgen.
[bewerk] Multi-directional queries
Een variabele kan op elke plaats voorkomen in het predicaat van een query. Dus we kunnen ook de query ?- part_of(X,u_s_navy) uitvoeren, waarna de interpreter zal antwoorden met X=enterprise. We kunnen dus flexibel zijn over welke argumenten de input (constanten) zijn en welke argumenten de output (variabelen) zijn. Dit betekent dus concreet dat Prolog verschillende vragen kan beantwoorden afhankelijk waar we de variabelen plaatsen in de query.
[bewerk] Alternatieve antwoorden
In sommige gevallen kan de X parameter meerdere waarden aannemen, waarvoor de query true is. In dat geval zal de Prolog interpreter de eerste juiste waarde zoeken en ze afprinten op de console. Om een (eventueel) volgende waarde weer te geven, moet de gebruiker het teken ; (puntkomma) ingeven. Dit teken kan je blijven ingeven zolang er andere waarden gevonden worden. Wanneer er geen nieuwe waarden meer zijn, dan zal Prolog no tonen op de console.
Dus als we bijvoorbeeld de query ?-a_kind_of(X,ship). Uitvoeren, dan krijgen we achtereenvolgens volgende antwoorden:
X=enterprise X=kennedy no
[bewerk] Meerdere paramaters
Een query kan ook meerdere parameters bevatten. Zo kunnen we bijvoorbeeld ook de query ?- part_of(X,Y). uitvoeren of met andere woorden
- welke dingen zijn onderdeel van andere dingen.
We krijgen hierop meerdere antwoorden, wanneer we telkens ; typen op de console:
X=enterprise, Y=u_s_navy; X=kennedy, Y=u_s_navy; X=u_s_navy, Y=u_s_government; no
bij het zoeken naar antwoorden, overloopt de interpreter de database van boven naar onder. De gegeven antwoorden staan dus in dezelfde volgorde als dat ze in de database staan.
[bewerk] Multi-condition queries
De Prolog interpreter laat je ook toe om meerdere voorwaarden op te geven die allen true moeten zijn in een query. Zo kan je dus een chain of reasoning of een opeenvolging van redeneringen opstellen. Stel dat we de kleur (K) willen weten van het schip Enterprise. Als we de query
- ? - color(enterprise,K)
intikken, dan krijgen we het antwoord no. In de database heeft het feit Color enkel betrekking op het object schip niet op enterprise. Het probleem van informatie op de verkeerde plaats komt vaak voor bij AI-systemen. Om dit toch te kunnen vragen, kunnen we eerst vragen of er een type T is waartoe de Enterprise behoort en dan of dit type de kleur K heeft:
- ? - a_kind_of(enterprise,T), color(T,K).
Deze query bevat een and functie die twee predicate uitdrukkingen verbindt. Beide uitdrukkingen moeten true zijn vooraleer het antwoord true is. Op de achtergrond zal de interpreter eerst de query ? - a_kind_of(enterprise,T) uitvoeren. Hij zal dan het antwoord ship vinden. Vervolgens voert de interpreter de query ?-color(ship,K) uit en krijgt hij het antwoord gray. De interpreter zal dan beide antwoorden afdrukken op de console:
T=ship, K=gray
We kunnen dus besluiten dat een , (komma) tussen twee uitdrukkingen in een query, dezelfde betekenis heeft als een logische AND.
Er is ook een logische or mogelijk voor query expressies. Een or kan men verwezenlijken door een ; (puntkomma) te plaatsen tussen de uitdrukkingen, zoals bijvoorbeeld:
- ? - color(enterprise,C); color(ship,C).
Hierbij vragen we
- Welke kleur heeft de Enterprise OF Welke kleur heeft een schip in het algemeen?.
[bewerk] Negatieve predicate expressions
We hebben nu de logische and en or gezien. Het enige wat we nu nog moeten hebben om de Booleaanse wiskunde te vervolledigen is een negatie of not. In Prolog kunnen we dit eenvoudig verwezenlijken door middel van het ingebouwde predicaat not. Een not predicaat is waar wanneer de argumenten ervan vals zijn. Dus de query
- ? - not(color(enterprise,green)).
heeft als antwoord true omdat er geen feit is in de database dat zegt dat de Enterprise groen is. Dit principe wordt ook wel negation as failure genoemd.
[bewerk] Backtracking
Laten we nu even in detail bekijken hoe de Prolog interpreter complexe queries afhandelt. Om dit eenvoudiger uit te leggen, zullen we nu even uitgaan dat er enkel queries gebruikt worden met komma's (and's) of negaties (not's) en geen punt-komma's (or's). Predicate uitdrukkingen in een query worden telkens van links naar rechts beoordeeld. Dit wil dus zeggen dat de meest linkse expressie eerst wordt geprobeerd, vervolgens de tweede expressie (eventueel met de gevonden parameter van de eerste expressie), enzovoort. De query wordt dus in een welbepaalde volgorde uitgevoerd zoals de lijnen code in een conventionele programmeertaal.
Maar stel dat een query bestaat uit drie uitdrukkingen A, B en C. De interpreter evalueert de query en constateert dat uitdrukking C fout is. Dat wil zeggen dat uitdrukkingen A en B wel juist waren. Als deze situatie zich voordoet, dan zal de interpreter een backtracking functie toepassen. Concreet wil dit zeggen dat de interpreter teruggaat naar een vorige expressie in de query en hij zal dan proberen om voor die expressie een andere waarde te vinden. Als de query dan nog fout is, dan gaat de interpreter nog een expressie terug, enzovoort.
Wanneer de interpreter uiteindelijk uitkomt bij de meest linkse expressie in de query na het backtracken, dan wil dat zeggen dat de query altijd false is. Op de console zal dan het antwoord no verschijnen en het backtracken stopt.
Het doel van backtracking is om queries een tweede kans te geven om toch te slagen. Dit gebeurt dus door eerdere expressies opnieuw te proberen. Backtracking is heel belangrijk bij kunstmatige intelligentie, omdat vele AI-methoden intelligentie guessing methodes gebruiken om een oplossing te vinden. Je zou dus kunnen zeggen dat een AI-programma gokt bij het zoeken naar een oplossing. Het programma kan uiteraard verkeerd gokken en dan is backtracking een goede manier om deze fout te herstellen.
We nemen als voorbeeld de query
- ? - part_of(X,Y), has(Y,civil_service_system).
die vraagt of er een X is die onderdeel is van Y en deze Y moet een civil service system hebben. We gebruiken nog steeds dezelfde Prolog database zoals in de eerdere voorbeelden. We sommen nog even de feiten op die betrekking kunnen hebben op deze query, namelijk de predicaten met de naam part_of en has:
part_of(enterprise,u_s_navy). part_of(kennedy,u_s_navy). part_of(u_s_navy,u_s_government). has(u_s_government,civil_service_system).
Hieronder ziet u in detail wat de Prolog interpreter zal doen om deze query te beantwoorden.
1. Hij neemt de eerste uitdrukking in de query en stelt de X gelijk aan enterprise en vervolgens wordt de Y gelijk gesteld aan u_s_navy. De informatie die hij gekozen heeft slaat hij op in de database.
2. Vervolgens gaat hij over naar de tweede expressie en probeert hij de subquery
- ? - has(u_s_navy,civil_service_system).
op te lossen. De Y werd dus vervangen door de waarde u_s_navy die hij in de eerste expressie aan Y had toegewezen. Deze subquery is fout, aangezien er zo geen feit bestaat.
3. De interpreter moet nu teruggaan naar de vorige uitdrukking (backtracking). Uit de feiten database weet hij nu dat de laatst geprobeerde waarden voor part_of niet juist waren. De interpreter probeert nu een tweede mogelijkheid door X te binden aan kennedy en Y aan u_s_navy. Deze informatie wordt ook terug opgeslagen.
4. Vervolgens probeert hij de subquery
- ? - has(u_s_navy,civil_service_system).
op te lossen. Dit is eigenlijk dezelfde query als in stap 2, maar de interpreter is niet slim genoeg en herinnert zich het antwoord niet. De subquery zal dus terug fout zijn.
5. Dus past de interpreter weeral backtracking toe. Nu kiest de interpreter de derde en laatste mogelijkheid: voor X u_s_navy en voor Y u_s_government.
6. De waarde van Y is nu veranderd en de interpreter probeert nu de subquery
- ? - has(u_s_government,civil_service_system).
op te lossen. Deze query is wel juist want dit feit staat in de facts database.
7. Beide subqueries zijn nu juist, dus de hele query is ook juist. De interpreter toont dan de resultaten op de console:
X=u_s_navy, Y=u_s_government
Merk op dat de interpreter geen backtracking had moeten toepassen, als we gewoon de volgorde van de query hadden veranderd
- ? - has(Y,civil_service_system), part_of(X,Y).
omdat er maar één feit is voor het has predicaat. De feiten in volgorde zetten vereist namelijk een grondige analyse op voorhand. Maar het is echter onmogelijk om de database volledig in de juiste volgorde te zetten voor alle queries in een applicatie.
Het automatische backtracking in Prolog heeft zo zijn voor- en zijn nadelen. Een groot voordeel is dat combinatie-problemen veel gemakkelijker te specifiëren zijn dan in de meeste andere computer talen, omdat bij Prolog de interpreter meer werk doet. Dit betekent ook dat Prolog een meer flexibele taal is dan andere conventionele talen. Een nadeel van Prolog is dat de programma's trager draaien dan die geschreven in andere talen. Verder zijn ze ook moeilijker te begrijpen en te debuggen.
[bewerk] Voorbeeld
Een voorbeeld van een volledig Prolog-programma. Het programma stelt via de console een aantal vragen aan de gebruiker en zal op basis van de antwoorden trachten te achterhalen wat de sport is die de gebruiker in gedachten heeft.
domains
sporter, sporterType,sport = symbol
sportCode = integer % 1 = indoor; 2 = outdoor; 3 = water
useBall,useTool,useNet = symbol % yes/no
facts
sportType(sporter, sportCode)
ballType(sporter, useBall)
toolType(sporter, useTool)
netType(sporter, useNet)
predicates %rfdimitri@hotmail.com, bogaert.thomas@pandora.be
nondeterm category(sporter,sport)
nondeterm run
nondeterm indoor(sporter)
nondeterm outdoor(sporter)
nondeterm water(sporter)
nondeterm ball(sporter)
nondeterm noBall(sporter)
nondeterm tool(sporter)
nondeterm noTool(sporter)
nondeterm net(sporter)
nondeterm noNet(sporter)
nondeterm whatKindOfSport(sporter, sportCode)
nondeterm usesBall(sporter, useBall)
nondeterm usesTool(sporter, useTool)
nondeterm usesNet(sporter, useNet)
clauses
indoor(X):-whatKindOfSport(X,Y),Y=1.
outdoor(X):-whatKindOfSport(X,Y),Y=2.
water(X):-whatKindOfSport(X,Y),Y=3.
ball(X):-usesBall(X,Y),Y=yes.
noBall(X):-usesBall(X,Y),Y=no.
tool(X):-usesTool(X,Y),Y=yes.
noTool(X):-usesTool(X,Y),Y=no.
net(X):-usesNet(X,Y),Y=yes.
noNet(X):-usesNet(X,Y),Y=no.
whatKindOfSport(X,Y):-sportType(X,Y),!.
whatKindOfSport(X,Y):-write("What kind of sport does ",X," play? (1=indoor,2=outdoor, 3=water): "),readint(Z),Y=Z,assert(sportType(X,Y)).
usesBall(X,Y):-ballType(X,Y),!.
usesBall(X,Y):-write("Does ",X," use a ball for his sport? (yes/no): "),readln(Z),Y=Z,assert(ballType(X,Y)).
usesTool(X,Y):-toolType(X,Y),!.
usesTool(X,Y):-write("Does ",X," use any tool when playing his sport? (yes/no): "),readln(Z),Y=Z,assert(toolType(X,Y)).
usesNet(X,Y):-netType(X,Y),!.
usesNet(X,Y):-write("Does ",X," use a net when playing his sport? (yes/no): "),readln(Z),Y=Z,assert(netType(X,Y)).
category(X,"football player"):-outdoor(X),ball(X),noTool(X).
category(X,"waterpolo player"):-water(X),ball(X).
category(X,swimmer):-water(X),noBall(X).
category(X,"basketball player"):-indoor(X),ball(X),noTool(X),noNet(X).
category(X,"volleyball player"):-indoor(X),ball(X),noTool(X),net(X).
category(X,"golf player"):-outdoor(X),ball(X),tool(X),noNet(X).
category(X,"snooker player"):-indoor(X),ball(X),tool(X).
category(X,"tennis player"):-outdoor(X),ball(X),tool(X),net(X).
category(X,boxer):-indoor(X),noBall(X),noTool(X).
category(X,"weight lifter"):-indoor(X),noBall(X),tool(X).
category(X,runner):-outdoor(X),noball(X).
run:-consult("sporters.txt"),
write("Give the name of the sportsman: "),
readln(X),
category(X,Y),
write(X," is a ",Y),nl,
save("sporters.txt").
goal
run.
[bewerk] Conclusie
Een computer op zich is niet voorzien van kunstmatige intelligentie. Deze vorm van intelligentie moet voortkomen uit een gespecialiseerd programma voor complexe problemen die niet kunnen worden opgelost via conventionele programmeertalen. Kunstmatige intelligentie kan men dus vatten als computers dingen laten doen die intelligent lijken. Het uiteindelijke doel is om computers nuttiger te maken voor ons, door een betere interactie met de gebruiker door middel van kunstmatige intelligentie.
Kunstmatige intelligentie berust op een aantal essentiële principes zoals bijvoorbeeld inference, het opslaan van feiten en feiten kunnen afleiden, of zoals backtracking, het eenvoudig en snel opzoeken van opgeslagen feiten.
De belangrijkste componenten van de Prolog taal zelf zijn de feiten (de eigenlijke kennis) die opgeslagen zitten in een soort database. Een andere belangrijke component zijn de predicaten, wat een operator of functie is die een boolean waarde als uitkomst heeft. Verder hebben we nog de clauses die het eigenlijke uitvoerbare programma vormen. De clauses worden geschreven met behulp van predicaten. De Prolog interpreter zal alle clauses van boven naar onder aflopen terwijl het naar feiten en regels zoekt die overeenkomen. In deze clauses kunnen ook variabelen gebruikt worden. Deze logische variabelen zijn wild cards voor Prolog's pattern matching en unificatie. Ze nemen gewoonweg de waarde aan die het resultaat was van de unificatie van andere Prolog termen. In conventionele programmeertalen hebben variabelen een specifiek datatype en verwijzen ze naar een plaats in het geheugen. Het zijn pointers.
Prolog is een logische taal die gebruikt wordt door programma's die niet-numerieke objecten gebruiken. Daarom wordt ze veel gebruikt voor kunstmatige intelligentie. De taal is in staat problemen op te lossen zonder vooraf te weten hoe.
[bewerk] Zie ook
[bewerk] Externe links
| Overzicht van programmeertalen |
|
Industrieel: |
