Hva er en Monad?
- Friday, August 13th, 2010
- Skriv en kommentar
Monad er et ord med mange betydninger; det brukes blant annet innenfor ulike filosofiske grener for å beskrive “universets essens”, eller som et slags navn på Gud. Det kjente tegnet fra kinesisk filosofi og kosmologi, som kineserne kaller T’ai-Chi, kalles også the Great Monad i Vesten, og representerer den underliggende harmonien mellom motstridende krefter i universet (mann/kvinne, yin/yang, hard/myk, sol/måne). Men ordet har også en betydning i matematikken, og den er overført til informatikk, hvor det er mest kjent som en feature i programmeringsspråket Haskell.
Windows PowerShell er også kjent under kodenavnet Monad, men meg bekjent er dette ikke relatert til betydningen i de funksjonelle språkene.
Mange betrakter monads som det mest skumle og uforståelige med funksjonelle språk, og det tar tid å skjønne hva det er for noe. Jeg har akkurat begynt å forstå det selv, og dette er forklaringen jeg skulle ønske jeg hadde sett før jeg begynte å lese de mer teoretiske beskrivelsene. Forhåpentligvis kan dette være til hjelp for andre som sliter med det samme, men jeg gir ingen garantier.
Du skal ikke se bort fra at du har brukt monader allerede
Da jeg begynte å lese meg opp på F# lærte jeg at man har monads der også, men at man kaller dem computation expressions. Og så sa læreboken at LINQ i .net også er computation expressions. Tidligere har jeg også hørt at LINQ er en form for list comprehension, som jeg lærte meg da jeg begynte å bruke Erlang, og som jeg senere har funnet igjen i flere andre språk. (List comprehension er en slags spesialsyntaks for å generere lister.) Det viser seg at list comprehensions kan kalles bruk av en list monad, og monad comprehension er en mer generell variant av list comprehensions.
Ok, du ble kanskje ikke noe klokere av dette, men saken er at alle disse tingene henger sammen på et vis. Du vil forhåpentlig vis se lyset mot slutten av blogposten!
For å skape noen nye hjernekoblinger kan vi først ta tak i litt Ruby-kode. Følgende er en banal, liten kodesnutt som deklarerer et par variabler som brukes til å beregne og skrive ut en verdi:
m = n * 3.1415
puts m # Skriver ut: 4200.1855
Dette er imperativ kode, slik man for eksempel finner i C og alle etterfølgerne av det språket. I Ruby har vi derimot muligheten til å gjøre koden mer funksjonell ved å gjøre følgende:
yield x * 3.1415
end
times_pi(1337) {|m| puts m} # Skriver ut: 4200.1855
Legg merke til at det ikke er noen likhetstegn i denne koden – det deklareres ingen variabler. I stedet kaller man en metode (times_pi) hvor man sender med en anonym funksjon som et av argumentene (en kodeblokk). Denne kodeblokken kalles så i funksjonen ved å bruke nøkkelordet yield. Når metodekallet er ferdig finnes det ingen variabler – ingen state!
For å bli en dyktig Ruby-utvikler må man endre tankemønsteret man bruker fra kode som i det første, imperative eksempelet til kode som det man finner i det andre eksempelet hvor man bruker kodeblokker. Men dette er også et stort steg på veien mot å lære seg funskjonell programmering. Times_pi er nemlig en høyere-ordens funksjon (den tar en funksjon som et parameter), og koden har ingen variabler / state. Vi har snudd måten vi tenker på (en slags Inversion of Control).
Hva har dette med monad å gjøre?
Jeg skal snart vise deg en monad, men ta først en titt på følgende, skrekkelige eksempel på Clojure-kode:
(def pi 3.1415) ; pi = 3.1415
(def n 1337) ; n = 1337
(def m (* n pi)) ; m = n * pi
(println m) ; Skriver ut: 4200.1855000000005
Her har jeg skrevet imperativ kode i Clojure, noe det ikke akkurat er laget for (men det fungerer). I virkeligheten ville jeg ha gjort det slik:
n 1337
m (* n pi)]
(println m)) ; Skriver ut: 4200.1855000000005
Let lar meg definere et sett med verdier som så er tilgjengelig innenfor let-kallet. Når let-kallet er ferdig opphører verdiene å eksistere. Let er faktisk en monad – i Haskell er den kjent som Identity Monad. Det let gjør er å transformere argumentene sine til en kjede med funskjonskall, og resultatet blir noe sånn som dette:
((fn [n]
((fn [m]
(println m))
(* n pi)))
1337))
3.1415) ; Skriver ut: 4200.1855000000005
Den koden er jo nærmest uleselig, og i alle fall ekstremt vanskelig å skrive (selv for dette lille eksempelet). Og det er hele poenget: Let-monaden lar meg på en enkel måte skrive imperativ-lignende kode – noe som ser ut som statements – som så blir omformet og kjedet sammen i en pipeline av funksjonskall (ren funskjonell kode).
Så hva er en monad?
Monader er altså i prinsippet, slik jeg ser det, syntaktisk sukker som omformer kode til funksjonskall etter bestemte regler. Tenk for eksempel på LINQ, som er en spørre-syntaks som under panseret blir omformet til funksjonskallene Select(), Where(), etc. Det er en formell teori knyttet til monad som snakker om bind og return, og forteller hvordan denne omformingen skal fungere. Dette er derimot ikke så viktig før man skal lage sine egne monads.., og jeg er ikke der enda. Det har derimot ikke hindret meg fra å bruke monads lenge uten å vite at det var det jeg gjorde i det hele tatt.
Monads er dermed ikke så skummelt lenger. List comprehensions og LINQ hjelper meg til å unngå løkker, og til å skrive bedre og mer deklerativ kode. Og let-monaden er helt uvurderlig i Clojure.
Andre monader
En annen, velkjent monad kalles Maybe-monad. Den fungerer i prinsippet slik at hvis én av handlingene i sekvensen/pipelinen returnerer null/ingenting så vil hele monaden returnerer det samme. På den måten kan monader forenkle kode hvor man normalt må sjekke for null. Det samme prinsippet kan brukes for å forenkle unntakshåndtering.
Ellers er vel ingen omtale av monad komplett uten å nevne I/O (input/output). Haskell bruker monads til dette, og det garanterer at I/O-handlinger (som jo har sideeffekter) kun utføres én gang, og i riktig rekkefølge. Det er altså ikke riktig at Haskell er et språk uten sideeffekter, slik jeg har blitt fortalt. Men språket krever at handlinger som har sideeffekter utføres i spesielle strukturer (altså monads) som håndterer sideeffektene på riktig måte. Dermed står man friere til å betrakte koden som “rent funksjonell”, og man kan utføre andre deler av koden i “valgfrie” rekkefølger, benytte lazy evaluering effektivt etc.
Vel, det var mine betraktninger rundt monad, og en forklaring for dem som bare har litt erfaring med funksjonelle språk. Det er kun kort tid siden jeg følte at jeg begynte å forstå konseptet, så om du betrakter noe av dette som feil får du bare si fra. Min kunnskap er selvsagt langt fra komplett, så jeg vil gjerne høre andre synspunkter.
Kategorier: LISP/Clojure, Polyglot, Ruby.
RSS feed for kommentarene.
Tilbaketråkk.
August 14th, 2010 at 1:15 am
Beklager, men jeg tror du har missforstått litt.
«Monader er altså i prinsippet, slik jeg ser det, syntaktisk sukker som omformer kode til funksjonskall etter bestemte regler.»
Eeh, ikke akkurat. En monade er definert som trippletten av en polymorfisk datatype, en funksjon som setter en verdi inn i datatypen, og en funksjon som fôrer innholdet i datatypen inn i en funksjon som returnerer den samme datatypen (men kanskje med annet innhold), dvs. (M, bind, return) for en eller annen datatype M. Selv uten det syntaktiske sukkeret som do-natasjon i Haskell og let-notasjon i Clojure (selv om jeg tviler litt på at dette faktisk er en monade (jeg ser ingen bind/return)) er det fortsatt monader vi snakker om, med mindre en evaluerer vekk bind/return.
«Det er altså ikke riktig at Haskell er et språk uten sideeffekter, slik jeg har blitt fortalt.»
Jo det er det, la meg prøve å forklare igjen: (med fancy unicode så bloggen din ikke spiser teksten)
En sideeffekt er at en funksjon gjør noe annet enn å ta sine read-only argumenter og frie variabler og returnerer output, f.eks. at den printer “Hello, world!” eller at den oppdaterer en variabel som i «(set! var (+ var 1))». En ren funksjon er en funksjon uten sideeffekter (i.e «((fn [pi] ((fn [n] ((fn [m] (println m)) (* n pi))) 1337)) 3.1415)» er ikke rent da det har «println» i seg.) Så hvordan kan en da ha en funksjon som printer noe i et rent funksjonelt språk?
Svaret er at en tar det som skal skrives på som et argument og returnerer en kopi av av det med det påskrevet. Men, akk, takket være kaosteori kan å skifte farge på en piksel på skjermen din i Norge forårsake tornadoer i Kina, så hvis du skal endre på noe i virkeligheten må du ta med deg hele universet både inn og ut av funksjonen. Takket være kvantefysikk vet vi og at å observere virkeligheten kan endre den, så en må returnere den oppdaterte versjonen da og:
getLine ∷ RealWorld → (RealWorld, String)
putStrLn ∷ String → RealWorld → (RealWorld, ())
Sammenlign så dette med de samme rutinene i Haskell:
getLine ∷ IO String
putStrLn ∷ String → IO ()
Men hva er IO?
ghci> :info IO
data IO α = IO (RealWorld → (RealWorld, α)) — Litt forenklet output.
Jo, det er en polymorfisk datatype av α som inneholder en funksjon som tar RealWorld inn og returnerer en oppdatert RealWorld og noe av type α ut. Hvis en så lager seg en bind og en return kan IO bli en monade, og de ser slik ut: (uten at du egentlig trenger å forstå nøyaktig hva som skjer for å lese videre)
return ∷ α → IO α
return x = IO (λ realWorld → (realWorld, x))
(≫=) ∷ IO α → (α → IO β) → IO β
(IO x) ≫= f = IO (λ realWorld → let (newWorld, y) = x realWorld; IO z = f y in z newWorld)
Ved å ha (RealWorld → (RealWorld, α)) inni en datatype og hindre tilgang til denne på andre måter enn return og bind hindrer man og at noen plutselig lager to universer. Kanskje kjekt å kunne når en får kvantedatamaskiner, men ikke enda.
Bruk av IO-monaden får dette:
greet ∷ RealWorld → (RealWorld, ())
greet originalWorld = let {
(world1, ()) = putStrLn “Hva heter du?” originalWorld;
(world2, name) = getLine world1
} in putStrLn (“Hei, ” ⊕ name ⊕ “!”) world2
Til å bli dette:
greet ∷ IO ()
greet = putStrLn “Hva heter du?” ≫= (λ _ → getLine ≫= (λ name → putStrLn (“Hei, ” ⊕ name ⊕ “!”)))
Eller med syntaktisk sukker i haskell (helt identisk det over):
greet = do {
putStrLn “Hva heter du?”;
name ← getLine;
putStrLn (“Hei, ” ⊕ name ⊕ “!”);
}
En ting å notere seg er at RealWorld-s tur gjennom programmet, enten gjemt i monaden eller eksplisitt, er informasjon om hvilken rekkefølge ting skal evalueres i, og det følger derfor at kode i IO-monaden (samt andre State eller ST-monader) strengt tatt ikke er deklarativ. Litt tounge-in-cheek er det mange som sier at Haskell er deres favoritt blant imperative språk. :P
August 14th, 2010 at 2:05 pm
Takk for at du tok deg tid, Ameth. Jeg håper du kan verdsette at jeg skrev denne blogposten for dem som ikke har peiling på hva monads er for noe. Mitt publikum er først og fremst .net-utviklere, og mange av dem har aldri tatt i et funksjonelt språk.
Å dra frem en definisjon som “trippletten av en polymorfisk datatype..” var derfor akkurat det jeg ville unngå. Jeg skraper kun i overflaten på hvordan monads virker og brukes, og forsøker i stedet å gi den uinnvidde et glimt av hva det er for noe. Jeg velger å tro at min fremgangsmåte er pedagogisk bedre.
Ulike kilder sier ting på ulike måter, men flere kilder jeg har lest bruker begrepet syntaktisk sukker om monader. Jeg skjønner hva du mener, men i praksis (kanskje ikke i prinsippet slik som jeg sa) er dette viktig for å forstå hva det dreier seg om. Det kan dog hende vi har ulike meninger om hva syntaktisk sukker er for noe..
Jeg beklager også at jeg er litt slurvete når det gjelder bruk av begreper som “ren funskjonell kode” o.l., men igjen fokuserer jeg på å formidle en ide fremfor å være vitenskapelig presis. Noen steder må man kutte noen hjørner for å ikke miste folk på veier, om du skjønner?!
For å oppsummere skjønner jeg ikke helt hva du mener jeg har missforstått – jeg tror bare du reagerer på at jeg ikke er så presis og at jeg utelater masse detaljer. Kan det stemme?
Når det gjelder “let” i clojure så er det hentet fra linken du gav meg i kommentaren din til min forrige post. Siterer fra linken:
“Let’s start with the simplest monad, known as the identity monad in the Haskell world. It’s actually built into the Clojure language, and you have certainly used it: it’s the let form.”
Når det gjelder Haskell skal jeg ikke kommentere så mye – det er interessant det du forteller. Jeg vil vente litt før jeg “bestemme meg for” om det er godt nok til å hevde at Haskell er et språk uten sideeffekter.
August 14th, 2010 at 5:19 pm
«Pedagogisk bedre:» Det kan godt være det er enklere å forstå som syntaktisk sukker, men hvis det ikke er riktig leder det så lett til missforståelser. Jeg husker jeg ble dritsur på barneskolen når jeg plutselig fant ut at det fantes noe som het operatorpresedens i stedet for å bare regne fra venstre til høyre slik jeg hadde lært opp til da.
«Syntaktisk sukker:» Jeg mener det er at det er en måte å skrive ting på som er «sukret», dvs. enklere og mer rett frem, selv om den er identisk til en annen måte på alle måter og oppfattes av maskinen når programmet kjøres som det samme (ikke inkludert optimalisering). F.eks. macroer i lisp lager syntaktisk sukker. 4 er ikke syntaktisk sukker for 2+2 da de ikke oppfattes av maskinen som det samme.
«jeg tror bare du reagerer på at jeg ikke er så presis og at jeg utelater masse detaljer:» Når du skrev at monader var syntaktisk sukker fikk det meg til å tro at du mente at f.eks. «do s ← getLine; putStrLn s» var monadisk mens «getLine ≫= putStrLn» ikke var det, for dette er syntaktisk sukker som omformer koden til å bruke funksjonen (≫=). Hvis du har en annen oppfattelse av hva syntaktisk sukker er kan det være derfra missforståelsen kom fra.
«Når det gjelder “let” i clojure…:» Den er en monade hvis ser på funksjonsapplikasjon som en flippet versjon av bind i identity-monaden, så det kan ha vært ett av disse pedagogiske verktøyene igjen (men hvis du ser på det slik er absolutt all kode monadisk…). Lenken går og videre og viser «(domonad identity-m …)» hvis innhold ser helt likt ut og som faktisk er monadisk rett etter at den skriver dette.
August 14th, 2010 at 10:18 pm
Jeg synes din beskrivelse av syntaktisk sukker er fin. Om et år eller to, når jeg har internalisert dette her, gjort kunnskapen til min egen, ville jeg nok ha reagert på denne blogposten på samme måte som det du gjorde. Dette med pedagogikk er vanskelig – det føles ikke så bra at man må “sukre” sannheten litt av og til.
Men menneskers forståelse fungerer i trappetrinn, vi må hele tiden bygge på det vi kan fra før, og kan ikke ta for store steg om gangen. For dem som er lengre oppe i trappa virker det rart hvordan de lengre nede snakker og tenker – de husker ikke lenger stegene de måtte gjennom (bortsett fra en og annen halv-traumatisk erindring om å ha blitt løyet til av en autoritetsfigur man stolte på) ;)
September 4th, 2010 at 11:01 pm
Jeg har lenge forsøkt å forstå Monads og relatert kunnskap, men jeg har i grunnen bare gitt opp.
Det er mye mulig at jeg bruker det allerede, men jeg kommer aldri til å bruke begrepet “Monad”, og kommentarene til Arneth illustrerer årsaken til hvorfor det veldig bra.
Problemet mitt med å forstå monads er at de som skal forklare det (og jeg mener ikke deg Torbjørn) klarer ikke å forklare det for folk som ikke allerede forstår alle begrepene.
De går i ring, de definerer en Monad som noe som er en Monad, men de klarer ikke, for meg ihvertfall, å skrive enkle begreper som jeg forstår. Jeg trodde jeg var relativt smart innenfor programmering, men disse Monad-forklaringene er tydeligvis for folk langt smartere enn meg, fordi de får meg til å føle meg så inderlig dum.
Det blir som å forklare hva integralet av en sirkel, til en som ikke kan matematikk, som å begynne med derivasjon.
De snakker om dualiet, tror jeg, og masse annet, som du må allerede være en matematiker og sett-teoretiker for å forstå.
Og da har jeg forlengst fallt av lasset.
Jeg beklager Monad-elskere, men dere *må* snakke klarere for at andre skal forstå dere.
Dette:
>> En monade er definert som trippletten av en polymorfisk datatype, en funksjon som setter en verdi inn i datatypen, og en funksjon som fôrer innholdet i datatypen inn i en funksjon som returnerer den samme datatypen (men kanskje med annet innhold), dvs. (M, bind, return) for en eller annen datatype M”.
Er *ikke* lett å forstå. Mulig det er nøyaktig, men det er *ikke* pedagogisk.
Så lær dere å lære bort.
Sorry for at jeg hijacket kommentar-feltet ditt Torbjørn, håper du fortsetter og klarer å trenge igjennom til meg, jeg tror ikke de andre klarer det lenger.
September 5th, 2010 at 3:32 am
«de definerer en Monad som noe som er en Monad» … det er slik definisjoner virker: Et menneske er et rasjonelt dyr, et rasjonelt dyr er et menneske; et hjerte er en hul muskel som pumper blod rundt i kroppen, en hul muskel som pumper blod rundt i kroppen er et hjerte. Det er ikke å gå i ring.
Men jeg kan prøve enkle begreper:
En monade er en boks som kan inneholde en ting, og 2 tilhørende funksjoner: En funksjon som pakker tingen ned i boksen («return») og en funksjon som pakker den opp, men funksjonen som pakker den opp kan bare gi tingen til en funksjon som vil returnere en boks av samme type, selv om tingen inni boksen kan være noe annet. Det sies at den binder innholdet til funksjonen, og den heter derfor «bind». Så lenge monaden kun gjør dette er den identity-monaden, og er som beskrevet over, men så lenge return og bind oppfyller visse lover (utelatt her) er det mye gøy en kan gjøre med dem:
Det nærmeste eksemplet på en monade i virkeligheten jeg kommer på akkurat nå er postsystemet: Du «return»-er brevet ned i en konvolutt med frimerke på og så, ved å poste det, «bind»-er du innholdet til brevvennen, som så forhåpentligvis er så hyggelig at han sender brev tilbake (bortsett fra at posten ikke pakker opp brevet før de leverer det til ham, ikke krever at han sender et brev tilbake (en skulle kanskje tro at han kjører sin egen bind-operasjon for å levere det til deg, men det er ikke tilfellet), og diverse andre unøyaktigheter ofret i pedagogismens navn, men fra senderens perspektiv er det ganske riktig).
Et annet eksempel er liste-monaden: Her kan boksen (dvs. listen) inneholde mer enn én ting, men tingene må fortsatt være av samme type, f.eks. tall. «return» gir her en liste med ett element i seg, men hvordan kan bind både pakke opp innholdet fra listen og gi mer enn én verdi til funksjonen? Svaret er at den kjører funksjonen mange ganger, en gang for hver verdi i listen, og så tar den alle boksene den fikk tilbake og slår dem sammen. Dvs. at bind oppfører seg som beskrevet her: http://blog.kjempekjekt.com/2010/06/13/selectmany/
Det er dog viktig å bemerke seg at en boks alene ikke er en monade, men kun en boks sammen med tilhørende «return» og «bind»-funksjoner som tolker hvordan boksen er satt sammen, hvordan en behandler innholdet, etc.
September 28th, 2010 at 12:54 am
En monad i seg selv er ikke interresant, det er instansene av en som er det.
En bra forklaring på IO monaden er her:
http://www.haskell.org/haskellwiki/IO_inside
(signaturen til liftM der er feil)
Det er ingenting å forstå med monader som ikke er gitt i definisjonen av en monad. Det å se at noe er en instans av en monad kan dog være vanskelig. Kun gjennom erfaring vil du forstå dette. Start med IO monaden.
December 9th, 2011 at 9:11 am
[...] Du finner også såkalte Computation expressions, som så langt jeg har forstått er det samme som monader. [...]