fredag 21. desember 2012 Julekalender Funksjonell programmering Haskell Monad
Christian Rødli Amble bør være kjent for de mest trofaste leserne av denne bloggen. Han har bidratt med mange gode kommentarer til blogpostene mine de siste årene, og da jeg skulle finne 24 gjestebloggere til å fylle julekalenderen i år, føltes det som en selvfølge å spørre om Christian ville være med.
Han har bidratt med en nokså avansert artikkel. Han snakker om den beryktede monaden, og jeg må innrømme at jeg synes det er vanskelig å henge med. Tar du utfordringen?
Hvem er du?
En som syntes «Real Programmers Don't Use Pascal» var litt for kul for 6-7 år siden.
Hva er jobben din?
Programmerer ved Tingtun AS i Lillesand.
Hva kan du?
Funksjonell programmering og algoritmer.
Hva liker du best med yrket ditt?
Å finne den passende abstraksjonen for problemet for hånden, og bruke denne til å løse problemet på en effektiv måte.
Jeg har programmert i Haskell i et par år nå, og jeg mener dette er Veien, Lyset og Frelsen. Dette er et forsøk på å forklare hvorfor for en uinitiert.
Denne bloggposten inkluderer også min monadetutorial. Å skrive en slik en når en føler at en endelig har skjønt det er et lite "rite of passage" for Haskell-programmerere, og jeg har ikke fått laget en før nå.
Haskell er et rent funksjonelt sterkt og statisk typet programmeringsspråk med ikke-striks semantikk.
Rent funksjonelt vil si at du ikke kan ha sideeffekter. En funksjon må alltid returnere det samme hvis den blir gitt de samme argumentene, og kan ikke gjøre noe annet enn å regne ut sitt resultat. Dvs. ingen input/output, ingen modifisering av variabler, og i hvert fall ingen GOTO-er.
Sterk og statisk typing regner jeg med de fleste skjønner, men Haskell har også typeinferens som gjør at en sjeldent trenger å nevne typene eksplisitt. Ellers er typesystemet ganske avansert med typefunksjoner, typeklasser, og mye annet snacks, som til sammen blir til et turingkomplett programmeringsspråk som ligger oppå programmet ditt og passer på at du ikke finner på noe tull. Hvis du absolutt vil kan du lage deg full aritmetikk på typenivå, og det finnes et eksempel på quicksort i det og.
Ikke-striks semantikk vil si at uttrykk reduseres fra utsiden og inn. Har du (a+(b*c)) reduseres først +, så a eller (b*c). Du vet ikke rekkefølgen argumentene blir evaluert i, og må programmere for å ta hensyn til dette. Dvs. har du (f(x) && g(y)) aner du ikke om f og g blir evaluert i den rekkefølgen, samtidig, eller i det hele tatt hvis en av dem gir False. Det er helt opp til kompilatoren og definisjonen av &&, selv om de som oftest tar et hint og gjør hva du tror. Siden f og g uansett ikke har lov til å ha sideeffekter som kan endre deres verdier så spiller ikke dette så stor rolle. De fleste Haskell-kompilatorer implementerer ikke-striks semantikk i form av lat evaluering, dvs. den evaluerer noe når den trenger det.
Det over sier hva Haskell er ved å sammenligne med andre typer språk, og så si hva det ikke er. Du må hele tiden forholde deg til en steril og matematisk verden et godt stykke unna hvordan programmet ditt faktisk kjøres, og med typesystemet som hele tiden passer på deg blir BDSM-opplevelsen komplett. Så hvorfor vil jeg utsette meg for dette?
Du fjerner en del bugs ved å ikke tillate modifisering av variabler:
> list = [3,2,1] > inPlaceSort list -- Dvs. inPlaceSort(list), Haskell utelater parenteser i funksjonskall. > first = head list
Hvis du bytter plass på linje 2 og 3 vil programmet fortsatt fungere og ha riktige typer, men resultatet blir feil. Derimot:
> list = [3,2,1] > sortedList = sort list > first = head sortedList
Å bytte rekkefølge nå i et imperativt språk vil fortelle deg at du prøver å referere til variablen sortedList før den blir satt. Siden variabler uansett ikke kan endres i Haskell blir alle satt på en gang, og koden over gir riktig resultat selv med linje 2 og 3 byttet, mens det første eksemplet er umulig å skrive på en gyldig måte.
Se e.g. på disse funksjonene:
> sum xs = if null xs then 0 else head xs + sum (tail xs) > product xs = if null xs then 1 else head xs * product (tail xs)
Her er sum-funksjonen i python hvis du har problemer med å skjønne syntaksen:
>>> def sum(xs): >>> if len(xs) == 0: >>> return 0 >>> else: >>> return xs[0] + sum(xs[1:])
Det er et mønster som går igjen: de eneste bitene som skiller funksjonene er hva en returnerer hvis listen er tom, og hvilken operator en setter mellom elementene i listen. I Haskell er funksjoner førsteklasses objekter på lik linje med tall og strenger, og de kan sådan gis som argumenter til andre funksjoner, og en operator er bare en helt vanlig funksjon. Funksjoner som tar andre funksjoner som argumenter kalles høyere rangs funksjoner, og brukes ofte i funksjonelle språk, hvilket gir bedre modularitet.
Det mønsteret over kalles i Haskell for foldr, og er definert slik:
> foldr f z xs = if null xs then z else f (head xs) (foldr f z (tail xs))
sum og product kan da defineres ut fra foldr:
> sum xs = foldr (+) 0 xs > product xs = foldr (*) 1 xs
foldr er tidligere omtalt på denne bloggen som reduce, sammen med eksempler på andre høyere rangs funksjoner.
Men i motsetning til de fleste andre språk så kan ikke funksjoner ha sideeffekter, og en er derfor garantert at de følger spillereglene.
(Advarsel: "litt" komplisert)
Haskell er som nevnt et veldig matematisk språk, og mange av konseptene i standardbibliotekene kommer fra kategoriteori. Du må ikke kunne kategoriteori for å kunne Haskell, men det hjelper litt da det er omtrent som ofte brukte designmønstre for funksjonelle språk, for ikke å nevne at det er veldig kult. Her tenkte jeg å forklare noen av de mest sentrale konseptene, functorer og monader.
Men først må vi innom typesystemet litt:
> 1 :: Int
:: vil si "har type", dvs. her sier en eksplisitt at 1 er av type Int. Det på venstre side av :: er vanlig kode og det på høyre side er typesignaturen.
Konkrete typer og typekonstruktører begynner på en stor bokstav (utenom [] som også er en konkret typekonstruktør).
> [1,2,3] :: [Int]
[Int], en liste med heltall, kan også skrives litt mer eksplisitt som ([] Int). Her er [] en typekonstruktør som tar ett argument, en annen type (Int over), og returnerer en type ([Int]). Dette korresponderer til List<int> i C#.
Typer og typekonstruktører har også typer:
> [] :: * -> * > [Int] :: *
Typen til en type eller en typefunksjon/typekonstruktør kalles for "kind." * uttales som "type", så det over sier at [] er en typekonstruktør som tar en type som argument og returnerer en type.
> map :: (a -> b) -> [a] -> [b]
a -> b vil si "er en funksjon som tar a som argument og returnerer b". Når det er små bokstaver i en typesignatur er det typevariabler. Disse kan stå for hvilke som helst typer og typefunksjoner. Koden over beskrives slik: "map er en funksjon som tar en funksjon fra a til b som første argument, en liste med a-er som andre argument, og returnerer en liste med b-er, der a og b kan være hva som helst."
> map (\x -> x + 1) [1,2,3] -- [2,3,4]
\ uttales lambda og lager en ny funksjon. I eksemplet over mappes en funksjon som tar x som argument og returnerer x + 1 over en liste.
En `Functor` er en generalisering av `map` over datatyper som tar ett argument. I kategoriteori heter det egentlig en endofunctor.
> fmap :: Functor f => (a -> b) -> f a -> f b
Det som kommer før => fungerer omtrent som en predikatfunksjon som begrenser domenet til f til å bare gjelde instanser av Functor. Functor her er en typeklasse.
> Functor :: (* -> *) -> Constraint
Dvs. Functor er en typefunksjon som tar en typekonstruktør fra type til type som argument og returnerer et Constraint, en begrensning på typevariablene i resten av signaturen. En instans av en typeklasse for en datatype lages ved å definere noen funksjoner, for Functor en fmap for en verdi av f.
Hvis en bytter ut f med [] i typen til fmap så blir typesignaturen den samme som for map. [] er en instans av Functor og fmap for lister gjør virkelig det samme som funksjonen map.
> fmap (\x -> x + 1) [1,2,3] -- [2,3,4]
Du kan selvsagt lage dine egne datatyper, og gjøre dem instanser av Functor ved å gi dem egne definisjoner av fmap.
`IO` er en datatype som enkapsulerer en handling som skjer i kontekst av virkeligheten utenfor programmet. Inni en IO a er det en funksjon som tar en spesiell unik RealWorld-variabel som representerer virkeligheten og alt i den, og returnerer noe av type a og en oppdatert utgave av virkeligheten. Siden funksjoner i Haskell må returnere det samme så lenge argumentene til de er de samme tillater det at e.g. getLine, les en linje fra stdin, returnerer forskjellig streng hver gang siden den får en forskjellig virkelighet som argument å lese fra hver gang. Det er selvsagt bare teoretisk, men det har ikke hindret noen i å lage et bibliotek som manipulerer denne variabelen. Det virker dessverre ikke, selv om jeg er hellig overbevist om at gud skrev universet i Haskell.
> getLine :: IO String -- Les en String fra terminalen. > print :: Show a => a -> IO () -- Ta noe det går an å vise og print det til terminalen. (Show er noe alla __repr__ i Python)
Alle Haskell-programmer har én slik `IO`-handling som kjøres når programmet starter, nemlig `main`-funksjonen av type IO (). (), uttalt `unit`, brukes ofte når en vil returnere ingen ting men har en typevariabel å fylle inn. IO () er altså en handling som bare utfører interaksjoner med virkeligheten.
Så langt kan vi nok til å lage et program med
> main = print 5
og få et flott 5-tall på skjermen når det kjøres. Men det er ikke så veldig oppmuntrende for vår alles kommende Haskell-karriere.
Hvis du har fulgt veldig godt med og er usedvanlig flink til å tolke hva jeg forsøker å kommunisere, tenker du kanskje "kan det være at `IO` er en `Functor`? Kan en da kanskje `fmap`-e `print` over `getLine` og få printet resultatet?"
I så fall, godt tenkt!, men ikke helt. Alle `Monad`er er også `Functor`er, og `IO`-instansen gjør det forventede, nemlig mapper funksjonen på resultatet av handlingen, men den resulterende typen er dessverre ikke helt hva en skulle håpe på:
> fmap print getLine :: IO (IO ())
Det er altså en `IO`-handling som returnerer en `IO`-handling. En trenger noe å flate det ut med, og det er her `Monad`er kommer inn:
> join :: Monad m => m (m a) -> m a > join (fmap print getLine) :: IO ()
En `Monad`e er altså noe som setter sammen to like datatyper inni hverandre på en utflatende måte. For `IO` setter den det sammen i sekvensiell handling, først den ytterste så den innerste.
Lister er også `Monad`er, lite overraskende implementert som `concat`.
> join [[1,2,3],[4,5,6]] -- [1,2,3,4,5,6]
Å sende innholdet i en `Monad`e inn i en funksjon som `print` er såpass vanlig at det finnes en egen funksjon for det:
> a >>= f = join (fmap f a) -- >>= uttales "bind" > (>>=) :: Monad m => m a -> (a -> m b) -> m b
Faktisk er det denne som definisjonen av en `Monad`e er gitt i termer av i Haskell, mens `join` er mer kategoriteoretisk. De kan uansett defineres ut fra hverandre, men jeg synes `join` gir en bedre og mer intuitiv forståelse av hva `Monad`er faktisk er, nemlig et monoid i kategorien av endofunctorer.
> main = getLine >>= print -- Les en linje og print den ut igjen.
Navnet `bind` kommer fra at en tenker en binder resultatet til en funksjon. Merk at `bind` for lister er det samme som concatMap (SelectMany i C#):
> words :: String -> [String] -- Splitt en streng på mellomrom. > fmap words ["dette er", "en test"] -- [["dette","er"],["en","test"]] > ["dette er", "en test"] >>= words -- ["dette", "er", "en", "test"]
Det blir ganske slitsomt å skrive en haug med >>=-er, og derfor har Haskell do-notasjon, som er syntaktisk sukker for akkurat dette:
> main = do putStrLn "Skriv navnet ditt:"
> navn <- getLine
> putStrLn ("Hei, " ++ navn ++ "!")
Er det samme som:
> main = putStrLn >>= (\_ -> getLine >>= (\navn -> putStrLn ("Hei, " ++ navn ++ "!")))
Haskell-kode er på et høyere abstrakt nivå. Monader er et design-mønster en kan bruke til å blant annet lage en konkretisering av abstraksjonen som gjeninnfører imperativ programmering. Det er som om semikolonene i et vanlig programmeringsspråk kunne modifiseres til å gjøre hva en ville med uttrykkene på hver side. Det gir et utrolig kraftig verktøy, og myriaden av monadene som finnes gir en god indikasjon på det: Det kan brukes til å lage parsere, mange forskjellige DSL-er, GOTO, continuation passing style som ser ganske rett frem ut, korutiner, ikkedeterminisme, osv., osv.
Med noe som heter monadeomformere går det også an å kombinere funksjonalitet fra flere monader inn i en. Trenger du en blanding av parser og korutine som også kan kjøre IO? Ikke noe problem, bare stack dem oppå hverandre og løft funksjonene du bruker opp på riktig nivå.
Allegro er et bibliotek for å lage 2D-spill, med støtte for bildemanipulasjon, tekst-output, lyd, MIDI, og input fra tastatur og joysticker. Jeg begynte på et lite spill som brukte SDL, men kom meg ikke over at det ikke gikk an å blitte til transparente overflater, så da var det bare å finne på noe nytt, og Allegro så veldig egnet ut. Jeg har allerede laget rå bindinger til C-funksjonene, og pusler så smått med en litt mer Haskellifisert kokt utgave.
I C-API-et har en en funksjon som heter drawLine der du gir den noen kordinater, en farge og en tykkelse, og så tegner den en linje på hvaenn slags bitmap du forhåpentligvis har fortalt den at det skal tegne på. Har du ikke gjort dette? Segfault. Prøver du å kalle getJoystick uten først å kallt installJoystick for å initialisere systemet? Segfault. Noe som helst allegro-relatert uten å først kalle initialize? Segfault. Dette går igjen i hele API-et.
God Haskell-ånd er å gjøre runtime-feil om til kompileringsfeil med typesystemet. Idéen jeg har er å lage et tynt lag oppå `IO`-monaden som holder en fantomtype, dvs. som bare finnes i typesystemet. Denne fantomtypen inneholder hva som er i konteksten, og med disse typepredikatfunksjonene sørger en for at drawLine bare kan kalles når Bitmap er i der, dvs. det er noe å tegne på. Et par nye funksjoner som withBitmap kjører handlinger med en bitmap i konteksten. En funksjon som heter runAllegro henter ut handlingene og returnerer dem som IO. Denne er polymorfisk på forskjellige kontekster som har installX-funksjoner, og kaller automatisk disse i riktig rekkefølge så funksjonene kan brukes trygt.
Dermed blir det mindre en trenger å huske på, og samtlige ubehagelige segfaults fjernes.
Ting jeg ikke har tatt med, men som også er gode grunner til å lære Haskell er: Pattern matching, currying, automatisk parallellisering, Template Haskell (kode som skriver kode), god performance, haugevis av biblioteker i hackage, STM, og masse annet.