C: Logikprogrammering med Prolog

Datorprogrammering med "vanliga" programmeringsspråk, som C, C++, Java och C#, betyder att man talar om för datorn vad den ska göra, i detalj och steg för steg. Som programmerare kan man ibland uppleva det som att man ger instruktioner till världens snabbaste, men också mest korkade, mattegeni. Datorn kan addera en miljard tiosiffriga tal på en sekund, men man måste peka på vart och ett av talen, i tur och ordning, och tala om att ja, det där talet ska också med.

Det finns andra sätt att programmera, som inte handlar om den sortens steg-för-steg-instruktioner. Vi ska titta lite på ett sådant sätt, nämligen så kallad logikprogrammering, med ett språk som heter Prolog.

Det är inte meningen att ni ska lära er Prolog, eller få en särskilt djup förståelse för logikprogrammering, utan ni ska bara se och förstå att det finns andra sorters programmering.

Här är ett (något förenklat) släktträd:

Ett släktträd med Anna, Bertil, Cecilia, David, Elin och Filip

Anna är förälder till Bertil. Bertil är förälder till Cecilia och David. Cecilia är förälder till Elin och Filip.

Att ange "fakta" i Prolog

I programmeringsspråket Prolog kan man skriva så här för att ange att Anna är förälder till Bertil:
förälder(anna, bertil).
Vi beskriver hela släktträdet som en liten "databas" av fakta:
förälder(anna, bertil).
förälder(bertil, cecilia).
förälder(bertil, david).
förälder(cecilia, elin).
förälder(cecilia, filip).

Sökning i Prolog

Nu kan man fråga vem som är förälder till cecilia:
förälder(X, cecilia).
X är en variabel, och Prolog-systemet kommer nu att leta fram vilka X som uppfyller villkoret att X är förälder till Cecilia. Vi får svaret:
X = bertil
Notera att Prolog-systemet inte bara utförde ett program steg för steg. Vi har ju egentligen inte skrivit något program, utan bara angett vilka fakta som gäller, om vem som är förälder till vem. I stället behövde Prolog-systemet leta i sin "databas" efter vilka förälder-fakta som finns om Cecilia.

Faktaruta:

"Vanlig" programmering, som i C, C++, Java och C#, kallas för imperativ programmering. Programmeraren ger "kommandon" till datorn, som steg för steg talar om vad den ska göra: Lägg ihop de här två talen! Skriv ut resultatet! Upprepa samma sak tusen gånger!

Logikprogrammering, som i Prolog, kallas deklarativ programmering. Man ger inga steg-för-steg-kommandon till datorn, utan man talar om (eller "deklarerar") vad som ska gälla för svaret, och sen får datorn själv välja hur den ska göra för att få fram ett svar som uppfyller kraven.

Även språket SQL, som används för att söka i databaser, brukar räknas som deklarativt. Man anger de villkor som svaret ska uppfylla, och sen får datorn söka i databasen hur den vill för att hitta de data som uppfyller villkoren.

Vi kan gå åt andra hållet också:

förälder(cecilia, X).
Prolog-systemet kommer nu att, på ett eller annat sätt, leta fram vilka X som uppfyller villkoret att Cecilia är förälder till X. Prolog svarar:
X = elin
X = filip
(Användaren måste trycka semikolon och trycka på enter emellan de olika svaren.)

Regler i Prolog

Vi kan också ange regler. Om två personer har samma förälder, så är de syskon. Så här kan man skriva det i Prolog:
syskon(X, Y) :- förälder(F, X), förälder(F, Y).
Man kan läsa ut denna regel så här: Två personer, låt oss kalla dem X och Y, är syskon om det finns en tredje person, låt oss kalla henne F, som både är förälder till X och förälder till Y. (Ok, jag sa aldrig att Prolog var lätt, bara att det inte kräver att man skriver steg-för-steg-program.)

Låt oss nu fråga vem som är syskon med Cecilia.

syskon(cecilia, X).
Prologen svarar:
X = cecilia
X = david
Men vad nu? Att David är syskon till Cecilia håller vi nog med om, men varför tycker Prologen att Cecilia är syskon till sig själv? Jo, det beror på att av alla personerna i databasen (Adam, Bertil, Cecilia, David, Elin och Filip) så är det två som är barn till Cecilias förälder: Cecilia och David. Det finns inget inbyggt i Prolog som säger att två variabler (som X och Y) inte kan referera till samma person.

Vi kan modifiera syskon-regeln så att man inte är syskon med sig själv:

syskon(X, Y) :- förälder(F, X), förälder(F, Y), X \= Y.
Det där säger att två personer, kallade X och Y, är syskon om det finns en person, kallad F, som både är förälder till X och förälder till Y, och X inte är samma som Y.

Nu blir det som vi tänkt oss. Vi skriver:

syskon(cecilia, X).
Och Prologen svarar:
X = david

Det som vi ska komma ihåg här är att det inte var något steg-för-steg-program som kördes, och att det överhuvudtaget inte fanns något steg-för-steg-program. Vi bara angav några fakta, och en regel, och sen fick Prolog-systemet självt använda sina fakta och sin regel för att räkna ut ett X som uppfyller vad vi sagt!

Men processorn där inne i datorn arbetar fortfarande steg för steg, och det finns inget magiskt sätt att komma ifrån det. Så egentligen fanns det ett steg-för-steg-program som kördes på datorn, nämligen Prolog-systemet självt. Det är ett steg-för-steg-program, kanske skrivet i C, men det är så smart skrivet att vi kan skriva in Prolog-program som inte behöver skrivas som steg-för-steg-program, och så räknar Prolog-systemet ut hur det ska göra för att "köra" Prolog-programmet.

Överkurs: Rekursiva regler i Prolog

Nu ska vi prova något som är lite mer komplicerat. Om vi tittar på bilden med släktträdet så ser vi att Bertil är förfader till Elin. Vet Prolog-system om det? Nej, Prolog-systemet har (än så länge) aldrig hört ordet "förfader", och vet inte vad en förfader är. Det måste vi först berätta.

Vi bestämmer oss för räkna även föräldrar som förfäder. Alla som finns "rakt ovanför" en person i trädet räknas som den personens förfäder. En förfader X till en ättling Y är alltså någon som antingen är förälder till Y, eller som är förälder till en förälder, i två eller flera steg, till Y. Man skulle kunna skriva så här:

X är förfader till Y, om X antingen är förälder till Y, eller om X är förälder till en mellanperson M, och M sen i sin tur är förfader till Y.

Det där är en så kallad rekursiv definition, där definitionen själv innehåller det begrepp som man just håller på att definiera. Det kan kännas lite ovant i början, men strunta i så fall i det. Det är bara ett exempel, och jag lovar att det fungerar.

Vi skriver det som Prolog:

förfader(X, Y) :- förälder(X, Y).
förfader(X, Y) :- förälder(X, M), förfader(M, Y).
Och så frågar vi vem som är förfader till Cecilia:
förfader(X, cecilia).
Prologen svarar:
X = bertil
X = anna

Vi kan också fråga vem Cecilia är förfader till:

förfader(cecilia, X).
Prologen svarar:
X = elin
X = filip


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 5 november 2010