Dette semesteret har jeg tatt ti poeng i funksjonell programmering, med språket Scheme Lisp (PLT). Nå sitter jeg og undres, hva er dette språket egentlig? Jeg ser jo at det rent syntaktisk er annerledes de andre programmeringsspråk jeg har lært meg, i det at man har en hel drøss med parenteser. Den skiller seg fra objekt-orientert programmering ved at man ikke kan lage klasser og objekter sånn uten videre. Ei heller blir programmet man skriver tolket ovenifra og ned, som ved C eller Basic. Og enkelte ting som verditilordning blir det gjort et stort nummer ut av; dette er i grunnen ikke “funksjonelt” (selv om det tydeligvis er implementert i funksjonelle språk, i det minste Scheme). Hva er funksjonell programmering?
Halerekursjon?
Det første jeg lærte som var eget i Scheme, var den halerekursive egenskapen. Si at man har en metode som kaller på seg selv med nye argumenter. I andre språk, som for eksempel Java, ville hvert selvrefererende kall metoden begår resultere i at en ny versjon av metoden blir kopiert inn i datamaskinens minne. Interpreteren til Scheme sørger her i stedet for at ny versjon av metoden (prosedyren) blir instansiert, og den gamle slettet – så sant alle argumenter blir oppdatert, og man ikke trenger en utregning i en tidligere instans av metoden:
int fib (int a, int b, int antall, int hvorLenge) {
// Hvis vi ikke har kommet til riktig nr i rekken:
if(antall < hvorLenge)
// Regn ut neste:
return fib(b, (a + b), (antall + 1), hvorLenge);
return b; // Returner nummer i rekken
}
I prinsippet har denne metoden nok informasjon til å slippe å kjøre rekursivt. Dette vil også skje, hvis man implementerer algoritmen i Scheme (se under). Andre programmeringsspråk vil derimot ha problemer med dette. Faktisk vil den eneste måten å iterere gjennom fibonacci-tallrekken i Java være å bruke en løkke, for eksempel for-løkken. Denne gidder jeg ikke lime inn en kopi av, men her får dere Scheme-varianten, som faktisk er hale-rekursiv:
(define (fib a b antall hvorLenge)
;; Hvis vi ikke har kommet til riktig nr i rekken:
(if (< antall hvorLenge)
;; Regn ut neste:
(fib b (+ a b) (+ 1 antall) hvorLenge)
b)) ;; Returner nummer i rekken
(En viktig semantisk forskjell på disse to algoritmene (den i Java og den i Scheme), er at Java-versjonen ikke inneholder en “else” i if-forgreningen. Hvis if-testen ikke slår til her, går den ned og returnerer b. I Scheme-versjonen, derimot, er evalueringen av b (som fører til at b blir returnert) andre ledd i if-setningen. Denne forskjellen kommer av at Java har en veldig streng kompilator, som sier i fra at metoden ikke returnerer en verdi hvis begge returneringene befinner seg inne i en if-forgrening.)
Halerekursjon er en fin finesse ved Scheme, men er det virkelig dette som definerer hva “funksjonell programmering” er? Her ser vi ingen direkte tilknytning til algoritmer, vi har bare optimalisert hvordan programmet blir kjørt. Jeg tror ikke dette gir oss noe svar på hva funksjonell programmering er, så vi går videre.
Eksplorativ verden?
Noe annet unikt som skiller Scheme fra andre språk jeg tidligere har sett på, er den eksplorative innfallsvinkelen. Dette gjøres, slik jeg ser det, på to måter:
For det første lever man i utgangspunktet i en helt statisk verden. Man endrer aldri på verdien til en “variabel” (navnet blir her noe misvisende, den varierer jo nettop ikke). Trenger man nye verdier, lages disse fortløpende. På denne måten kan man altså lage seg statiske virkeligheter, for deretter å kunne utforske disse med de algoritmer og funksjoner som man implementerer.
For det andre har man i LISP noe som kalles REPL: Read, Evaluate, Print-Loop. Dette er en interaktiv kommando-linje, hvor man kan skrive definisjoner på nye verdier og funksjoner rett inn, og kalle på disse for å se hvordan de evalueres. For eksempel kan man bare skrive
> (fib 0 1 0 10)
så får man svaret på hvilket tall som er nummer 10 i fibonacci-rekken. Man trenger altså ikke lagre kallet på prosedyren sammen med kildekoden, og kompilere hele programmet, for å få noe vettug ut av prosedyren man har lagd. Dette er blant annet en flott måte å debugge programmet på. Vi programmerere kan også lage halv-ferdige programmer, og få full utbytte av disse gjennom REPL, hvor vanlig dødelige brukere er avhengig av at noen tar seg tid til å lage et brukergrensesnitt.
Denne eksplorative verden er noe jeg anser som viktigere enn halerekursjon for å nærme oss hva det vil si at et språk er funksjonelt. Her er det funksjonene, og de operasjoner de utfører, som er viktig, og en funksjon har en veldig streng definisjon i matematikken og logikken: Gir man en funksjon samme verdi, skal den alltid komme med samme svar. Altså gir det mening å operere med statiske verdier. Gir en prosedyre ulike svar hvis matet med samme verdi, er det ikke strengt tatt en funksjon lenger.
REPL er nyttig, men ikke nødvendigvis veldig matematisk funksjonelt.
Man kan i Lisp endre verdier etter at de er satt, og dette gjøres selvfølgelig relativt ofte. Tenk å for eksempel implementere et bank-system, og aldri få muligheten til å sette ny verdi på brukernes saldoer. Poenget er at destruering av pekeres verdier burde gjøres minst mulig, for på den måten å sikre en mer funksjonell innfallsvinkel, tror jeg. LISP kommer litt i vinden igjen i disse multi-prosessor tider, og noe av dette skyldes nok at man kan kjøre en del funksjonelle prosedyrer parallelt uten å være redd for at utregningene i den ene er avhengig av den andre, funksjoner skal jo gi samme svar gitt de samme verdier.
Lat evaluering?
Enda en kul finesse ved Scheme er lat evaluering. Her utsetter man evalueringen av en verdi eller en prosedyre til senere, når man har bruk for den. Først og fremst brukes nok dette til å definere strømmer, sekvenser hvor vi ikke regner ut neste ledd før vi får bruk for den. Dette er en hendig måte å uthente de data vi måtte trenge, for eksempel fra fibonacci-sekvensen:
(define (fibgen a b)
(cons-stream a (fibgen b (+ a b))))
Her definerer vi en fibonacci-generator, hvor rekken starter med tallene a og b, og neste tall, a + b, blir regnet ut når man trenger denne. Neste tall i rekken igjen er selvfølgelig b + (a + b), og neste igjen er (b + (a + b)) + (a + b) og så videre. Altså, neste tall i rekken er summen av de to foregående. Med følgende kommando, definerer man fibonacci-rekken fra 0:
(define fibs (figgen 0 1))
Denne konstruksjonen representerer hele fibonacci-sekvensen, uten å regne ut mer enn det du trekker ut av den. Dette er altså en hendig måte å representere uendelige rekker. Lat evaluering er på denne måten definitivt med på å gjøre et språk mer funksjonelt: Man kan her for eksempel enkelt operere med matematiske funksjoner som jobber på uendelige rekker av tall. For et hendig bibliotek for å bruke strømmer i Scheme, se blant annet her.
Fore funksjoner med funksjoner?
LISP har også den geniale mulighet at man kan fore en prosedyres argumenter med andre prosedyrer igjen. Dette er en unik måte å abstrahere funksjoner, og samtidig en måte å bygge stadig mer komplekse funksjoner uten å jobbe rundt problemet alt for mye. Man kan enkelt for eksempel lage en prosedyre som akkumulerer en mengde tall med samme operasjon, for eksempel addere eller multiplisere tallene i en rekke sammen:
>(akkumuler + 0 '(1 2 3 4))
10
>(akkumuler * 1 '(1 2 3 4))
24
Denne tar en funksjon (+ eller *) som argument, og man har da abstrahert tanken om å utføre en operasjon på en tallrekke. Denne kan også være gjenstand for å lage ytterligere (potensielt mer avanserte) prosedyrer, noe jeg ikke vil i dybden på her. (Bare så det er nevnt, kan også returverdien til en prosedyre være en annen prosedyre.)
Nå begynner vi å snakke om å gjøre et dataspråk mer matematisk funksjonelt. Hvis en matematiker kommer med en definisjon av en funksjon hvor et av argumentene selv er en funksjon, står vi ikke lenger fast, men kan bare skrive det rett ut i språket vårt!
For de spesielt interesserte, her er hele akkumuler-prosedyren:
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
Konklusjon
Gitt turing-kompletthet så kan alle programmeringsspråk uttrykke den samme regnekraft som et hvilket som helst annet. Allikevel er forskjellige språk designet for å løse forskjellige problemer mest mulig elegant og enkelt for sitt domene. I så måte er LISP genialt for å uttrykke algoritmer og funksjoner. Veldig ofte ser prosedyren i LISP ut som den matematiske funksjonen i seg selv, for eksempel ved implementasjonen av fibonacci-sekvensen. Den statiske verden man gjerne oppererer i er perfekt i henhold til den matematiske definisjon av funksjoner: En tilordning som i hvert element i sin definisjonsmengde angir kun én ufallsverdi. (Det femte tallet i fibonacci-sekvensen er alltid verdien 5.)
Med halerekursjon kan man implementere selvrefererende matematiske funksjoner og være mindre redd for at beregningskraften vil vokse eksponensielt, da kompilatorens innebygde støtte for halerekursjon optimaliserere algoritmen til en iterativ prosedyre hvor dette er mulig. Ofte må man allikevel jobbe litt rundt dette for at kompilatoren skal skjønne hvor dette er mulig.
Med lat evaluering kan man jobbe på store (uendelige) mengder, og anvende funksjoner av disse, uten å være redd for at datamaskinen regner ut hele mengden før man starter å jobbe med den. Og med den eksplorative tilnærmingsmåten kan man nettop sikre at en funksjon alltid returnerer samme svar gitt samme argumenter. Å fore prosedyrer som argumenter til andre prosedyrer sørger for at man kan bygge stadig mer komplekse funksjoner uten omveier.
Tips oss hvis dette innlegget er upassende