torsdag 22. desember 2011 Julekalender Polyglot Prolog
Prolog er et såkalt logisk programmeringsspråk. Jeg snakket om det nylig i posten Hvem bor hvor?. Mens man i nord-amerika først og fremst tenker på Lisp når man snakker om kunstig intelligens og implementasjon av lingvistiske løsninger, bruker man i Europa og andre steder oftere nettopp Prolog.
Prolog er deklerativt: Et program er et sett med relasjoner representert gjennom regler og fakta. Å kjøre et prolog-program er å kjøre spørringer mot disse relasjonene. Språket er som en ultra-smart fyr som kan finne alle logiske slutninger basert på det du forteller den.
Da det ble implementert tidlig på 70-tallet var Prolog et av de aller første logiske programmeringsspråkene, og det er fortsatt et av de mest populære. Det finnes en rekke implementasjoner, og språket er flittig brukt innen forskning og utdanning.
Til å begynne med trodde mange at Prolog kom til å få stor utbredelse, og at det var et steg i retning av en helt ny type programmeringsspråk. Men utenfor forskningsmiljøene - i industrien forøvrig - har Prolog og logisk programmering hatt liten gjennomslagskraft.
Den eneste språket som "minner om" Prolog, som de fleste utviklere har et tett forhold til, og som også ble skapt tidlig på 70-taller, er SQL.
Vi vil begynne med å definere en slektsdatabase i Prolog. Først deklarerer vi noen fakta: Adam er en mann, Peter er en mann, osv..
27 man(adam). 28 man(peter). 29 man(paul). 30 31 woman(marry). 32 woman(eve).
Så kan vi legge til noen relasjoner:
34 parent(adam,peter). % means adam is parent of peter 35 parent(eve,peter). 36 parent(adam,paul). 37 parent(marry,paul).
Relasjonene var også fakta, men nå er det på tide med noen regler. Følgende regler bruker de definerte faktaene til å si hva det innebærer å vare en far eller mor:
39 father(F,C) :- man(F), parent(F,C). 40 mother(M,C) :- woman(M), parent(M,C).
F, C og M er variabler – alt som begynner med stor bokstav er variabler i Prolog. En far (F) må altså både være en mann og forelder til sitt barn (C).
Nå kan vi bruke det vi har definert til å spørre Prolog hvem som er faren til Paul:
?-father(X,paul).
Prolog vil svare X = adam.
Videre kan vi definere regler for andre familierelasjoner:
44 son(S,P) :- man(S), parent(P,S). 45 daughter(D,P) :- woman(D), parent(P,D). 46 47 siblings(A,B) :- parent(P,A), parent(P,B), A\=B. 48 % siblings have at least one common parent 49 % the test A\=B ensures siblings are different persons 50 51 uncle(U,N) :- man(U), siblings(U,P), parent(P,N). 52 aunt(A,N) :- woman(A), siblings(A,P), parent(P,N). 53 54 grand_parent(G,N) :- parent(G,X), parent(X,N).
Det var en smakebit. Nå skal vi se noe litt mere avansert..
Euler-oppgaven jeg løser i denne julekalenderen er ikke en typisk oppgave for Prolog – i alle fall ikke så langt jeg kan se. Jeg er kun en nybegynner i dette språket. Men jeg måtte nesten lage en løsning likevel, og med litt hjelp har jeg kommet frem til en løsning.
10 interesting_number(N) :- N rem 3 =:= 0. 11 interesting_number(N) :- N rem 5 =:= 0. 12 13 euler1(0, 0) :- true, !. 14 euler1(N, Answer) :- 15 N > 0, interesting_number(N), 16 Next is N-1, 17 euler1(Next, SubAnswer), 18 Answer is SubAnswer + N, !. 19 euler1(N, Answer) :- 20 N > 0, 21 Next is N-1, 22 euler1(Next, Answer).
I de to første linjene beskriver jeg regelen for hvilke numre jeg er interessert i: de som er delelige på 3 og de som er delelige på 5. Den neste tre-delte regelen er rekursiv, og hakket for kompleks til at jeg forsøker meg på en beskrivelse her og nå.
Det finnes som sagt en rekke implementasjoner av Prolog, og mange støtter ulike ekstra-funksjoner som filter og reduce, slik at oppgaven i praksis kan løses omtrent som i et hvilket som helst annet språk. Løsningen over er derimot en minimal løsning i "ren" Prolog.
Logisk programmering er en veldig interessant løsningsmodell, og utviklere bør kjenne til muligheten. Når det dukker opp et problem som egner seg for dette, vil det være fordelaktig å ha litt erfaring.
Nok en gang er det også et språk som vil lære deg nye måter å tenke på, og vil kunne gi deg ideer du kan dra nytte av i mere konvensjonelle språk.
Men det kan kanskje være urealistisk å lære seg en ny plattform og et litt sært språk for noe man kun skjelden har bruk for. Heldigvis kan man ved hjelp av bibloteker benytte logisk programmering i mange andre språk også. I prinsippet har man som regel da en komponent som implementerer en slags Prolog for den plattformen man jobber på, og et API for å deklerativt angi fakta og regler – i en syntaks man er kjent med.
Eksempler på dette er core.logic i Clojure, og ruby-prolog, en Prolog-lignende DSL for Ruby. De kan være litt vanskelige å finne!
Ellers finner du også støtte for logisk programmering i Oz. Og programmeringsspråket Mercury er en slags moderne arvtager av Prolog, som også støtter funksjonell programmering inspirert av Haskell.
Jeg startet med GNU Prolog. Et kanskje enda bedre alternativ er SWI Prolog, som har støtte for multi-threading, http request/response, og har et rikere støttebiblotek. Begge er open source og tilgjengelige for Windows, Mac og Unix.
Og så er det viktig å finne en god læringsressurs. LearnPrologNow.org er én mulighet. Sjekk også ut Prolog in Examples.
Ellers er det en bok jeg har hatt lyst til å lese en stund, og det er The Reasoned Schemer. Den handler ikke om Prolog direkte, men om hvordan man utvider Scheme (en Lisp) til å støtte logisk programmering. Boken vil gi deg en dyp forståelse for sammenhengen mellom funksjonell og logisk programmering.