HUMIT2720 - V?r 2005

PROLOG

PROLOG er et rikt programmeringsspråk som man vil bruke litt tid på å mestre helt, men de enkleste prinsippene kan forklares på et par sider, og det er forbløffende hvor langt man kan komme med bare dem:

Grunnprinsipper

Et PROLOG-program inneholder
fakta, som
far(per,kari) eller mor(susanne,per), og
regler, som
farmor(X,Y):-mor(X,Z),far(Z,Y).
(Her leses tegnet :- som hvis, mens kommaene til høyre leses som og.)

Vi er interessert i hva som kan bevises fra et slikt program; for eksempel kan vi kalle opp programmet ved å stille spørsmålet

?- farmor(susanne, kari).

og så motta svaret

yes

eller eventuelt motta benektende svar på spørsmålet ?- farmor(kari,susanne). Og så kan vi legge inn variabler i spørsmålet (variabler er tegnstrenger med stor forbokstav) og for eksempel spørre om hvem susanne er farmor til, slik:

?- farmor(susanne,Noen)

og i dette tilfellet få svaret

Noen = kari

Hvis programmet inneholder flere fakta eller regler enn dem vi tok med ovenfor, er det mulig at susanne beviselig er farmor til flere, i så fall kan vi motta flere alternative svar, det vil si flere løsninger av samme format Noen = person. (Når man kjører PROLOG interaktivt, vil de fleste versjoner bare presentere en løsning av gangen, og vente på semikolon og return fra oss før de leter etter flere.)

I programmet ovenfor inneholder faktaene ingen variabler, og reglene bare variabler. Dette er ikke nødvendig; vi kan for eksempel ha fakta som forfar(adam,X) som forteller at adam er forfar til alle (alt), eller forfar(adam,X):-menneske(X), som forteller at han er forfar til alle mennesker. (Inkludert seg selv!)

Legg også merke til at fakta i grunnen er spesialtilfeller av regler der vi ikke tar med noen betingelser etter tegnet :-. (Og derfor like godt tar vekk selve tegnet også.)

John Fisher har gitt oss lov til å kikke på disse eksemplene, hvorav 2.1 burde v?re forståelig allerede nå.

Funksjons-symboler

Eksempelet ovenfor er spesielt enkelt; vi bruker bare

predikater, som
far, mor, farmor, forfar,
konstanter, som
susanne, per, kari, adam, og
variabler, som
X, Y, Z, Noen.

Denne delen av Prolog er akkurat rikholdig nok til å definere enkle databaseoperasjoner, og kalles derfor gjerne DATALOG. Vi kan få til mer hvis vi også tar med funksjons-symboler, som her: 

pluss(0,Y,Y).
pluss(succ(X),Y,succ(Z)):-pluss(X,Y,Z).
I dette tilfellet er pluss et predikat med tre argumentplasser og 0 en konstant, mens succ er et funksjons-symbol med en argumentplass. Fra dette programmet kan man bevise ting som 
pluss(succ(succ(0),succ(succ(0)),succ(succ(succ(succ(0))))).

(Tenk på 0 som vanlig null, og tenk på succ som etterfølgerfunksjonen for de naturlige tall. Da ser vi at programmet definerer forholdet mellom to tall og summen.)

Programmet kan brukes på flere måter; til addisjon: 

?- pluss(succ(succ(0),succ(succ(0)),Sum).

Sum = succ(succ(succ(succ(0))))

eller til subtraksjon: 

?- pluss(succ(succ(0)),Diff,succ(succ(succ(succ(0))))).

Diff = succ(succ(0))

Lister

De som kjenner Scheme vil vite at listestrukturer der bygges opp ved hjelp av nil og cons. For eksempel gir uttrykket cons(1,cons(2,cons(3,nil))) oss listen [1,2,3]. Det er naturlig å se på nil som en konstant, og å se på cons som et funksjons-symbol med to argumentplasser. I PROLOG skriver vi dem som [] og [ | ], altså lar vi uttrykket [1 | [2 | [3 | []]]] representere listen [1,2,3]. Når vi kommuniserer med PROLOG, vil systemet imidlertid pynte på dette uttrykket, og skrive det som [1,2,3] i stedet.

Når vi skal sjekke om et element er med i en liste, bruker vi predikatet member, som kan defineres ved følgende program: 

member(First,[First|Rest]).
member(Element,[First|Rest]) :- member(Element,Rest).

(Det er to tilfeller å sjekke: Elementet kan v?re lik første element i listen, eller det kan v?re med i resten av listen.)

Fisher's ''tutorial'' inneholder mange eksempler på bruk av lister; eksempel 2.9 er en videreføring av eksempelet 2.1 nevnt ovenfor, med bruk av lister.

Aritmetikk

Predikatet pluss ovenfor forutsetter at tallet 10, for eksempel, representeres med uttrykket 
succ(succ(succ(succ(succ(succ(succ(succ(succ(succ(0))))))))))
Et dobbelt så stort tall tar dobbelt så stor plass, etc. I praktiske tilfeller er dette ubrukelig, og Prolog har derfor innebygde operatorer for mer realistisk tallbehandling, som for eksempel i følgende spørsmål og svar: 
?- N is 5 + 5.

N = 10

Dette kan brukes til å beregne summen av alle tall i en liste: 

sum([],0).
sum([First|Rest],N) :- sum(Rest,M), N is M + First.
Med tilsvarende funksjoner * og - for multiplikasjon og subtraksjon, kan vi også beregne fakultet av et positivt tall, altså resultatet av å multiplisere alle positive tall som er mindre eller lik det gitte tallet. 
fakultet(1,1).
fakultet(N,FN) :-
     N1 is N-1,
     fakultet(N1,FN1),
     FN is FN1*N.
Disse innebygde operatorene har en litt annen oppførsel enn andre funksjons-symboler. En konsekvens er at sum bare kan brukes slik: 
?- sum([1,2,3,4],Sum).

Sum = 10
Vi får feilmelding hvis vi prøver noe sånt som 
?- sum(Liste,10).
(Forklaring: Når PROLOG beregner en løsning, vil variablene bli bundet til konkrete verdier i en bestemt rekkefølge. Et uttrykk som X is Y + Z kan brukes til å bestemme en verdi for X hvis verdier for Y og Z allerede er bestemt. is er imildertid implementert slik at informasjon ikke kan flyte motsatt vei, fra venstre mot høyre, og vi får derfor en feilmelding hvis PROLOG møter betingelsen X is Y + Z før Y og Z har fått sine verdier bestemt.)

Tilsvarende gjelder for fakultet. Dette er til forskjell fra predikatet pluss ovenfor, som kan brukes like godt ''begge veier''. Flere eksempler på bruk av de innebygde aritmetiske operatorene finner dere i Fisher's ''tutorial''.

Oppdatert av Tore 20. august 2002