Polyglot

Hvis du aldri før har sett det jeg nå skal demonstrere, og du samtidig er klar til å forstå det, så kan du se frem til en ganske stor a-ha-opplevelse. Teknikken du vil få se er avansert og enkel på samme tid. Noen vil si det er trivielt, mens andre vil bruke lang tid på å skjønne det.

I denne posten vil jeg bruke F# til å presentere et problem med rekursiv traversering av tre-strukturer. Jeg vil så bruke continuation-passing style til å løse problemet.

Rekursiv tre-summering

I blogposten Funksjonell lek med trær i F# definerte jeg en generisk tre-datatype. Jag lagde en generell funksjoner som traverserte trærne, en slags fold eller reduce for trær.

Det jeg skal gjøre nå er omtrent det samme, men jeg har valgt å holde det enda enklere. Først definerer vi en type IntTree som brukes til å bygge trær. En node i treet er enten en bladnode som holder på et heltall, eller en node med to undernoder. Dette er altså et binærtre.

type IntTree =
    | Leaf of int
    | Node of IntTree * IntTree

Nå kan jeg bygge et tre på denne måten:

let tree = Node(Node(Node(Leaf 5,
                          Leaf 8),
                     Leaf 2),
                Node(Leaf 2,
                     Leaf 9))

Tegner vi opp dette treet grafisk ser det slik ut:

Nå kan vi lage en summeringsfunksjon for slike trær. Dette er en enkelt, reksursiv funksjon som består av to regler:

1. Summen av en bladnode er like verdien bladnoden holder på.
2. Summen av et tre er lik summen av deltreet til venstre pluss summen av deltreet til høyre for noden vi begynner med.

En slik funksjon uttrykkes elegant i F#:

let rec sumTree tree =
    match tree with
    | Leaf n             -> n
    | Node (left, right) -> sumTree left
                          + sumTree right

For å teste sumTree hopper jeg over i F# interactive:

> sumTree tree;;
val it : int = 26

Summen rapporteres korrekt som 26.

Utfordring med dype trær

sumTree har derimot én utfordring. Du ser at det er to rekursive kall for hver node, og at verdiene fra disse kallene plusses sammen. Vi har dermed ingen halerekursjon, og kontrollstacken vil vokse.

For små trær er ikke dette noe problem. Og godt balanserte trær kan inneholde mange elementer før treet blir dypt. Men sett at vi har et tre som ikke er så godt balansert.

La oss lage noen tall å jobbe med:

> let rnd = new System.Random();;

val rnd : System.Random

> let numbers =
    List.init 100000 (fun _ -> rnd.Next(-50, 51));;

val numbers : int list =
  [-46; -43; -22; -3; 20; 0; -43; -19; -50; 28; 35; -26; 20;
   40; -4; -42; 5; 37; 27; -9; 28; 38; 29; 2; -23; -4; -29;
   41; 10; 47; 39; -23; 37; 42; 12; -10; 1; -4; -39; ...]

numbers inneholder nå hundre tusen tall mellom –50 og 50. Jeg kan så konstuere et ubalansert tre basert på disse tallene:

> let imbalancedTree =
     numbers |> List.fold (fun currentTree num ->
        Node(Leaf num, currentTree)) (Leaf 0);;

val imbalancedTree : IntTree =
  Node
    (Leaf 49,
     Node
       (Leaf -3,
        Node
          (Leaf -38,
           Node
             (Leaf 42,
              Node
                (Leaf 11,
                  ...

Dybden på imbalancedTree er nå hundre tusen. Hva skjer om jeg forsøker å summere tallene i dette treet?

> sumTree imbalancedTree;;

Process is terminated due to StackOverflowException.

Jepp, der fikk vi en stack overflow! Den rekursive algoritmen måtte gjøre 100.000 kall til sumTree før den kunne plusse sammen høyre og venstre deltre, og hvert kall konsumerte en liten bit av stacken. Det går ikke!

Vi må finne på noe annet…

Continuation-passing style

Begrepet Continuation-passing style (CPS) ble skapt av Gerald Jay Sussman og Guy L. Steele i 1975 da de begynte utviklingen av programmeringsspråket Scheme.

En funksjon skrevet i denne stilen tar ett ekstra argument: en “continuation”, det vil si en funksjon. Når CPS-funksjonen har kalkulert sitt resultat “returnerer” den dette resultatet ved å kalle continuation-funksjonen med resultatverdien som argument.

Utviklere som bruker asynkrone API’er, for eksempel utviklere som programmerer for node.js, bruker mye callbacks – og det er egentlig CPS. Men teknikken har flere bruksområder. Nå skal jeg bruke CPS til å fikse problemet med den rekursive funksjonen sumTree.

sumTree goes CPS

Jeg skal lage en ny summeringsfunksjon. Den vil ha to parametre, og følgende signatur:

tree:IntTree -> cont:(int -> 'a) -> 'a

For dem som ikke er så vandt til å lese F#/ML/Haskell-signaturer:

• Første parameter tree er en instans av et IntTree
• Andre parameter cont er en funksjon som tar inn en integer og returnerer en verdi av den generiske typen a
• Funksjonen vil til slutt returnere en verdi at typen a

Og her er den nye funksjonen:

let rec sumTreeCont tree cont =
    match tree with
    | Leaf n -> cont n
    | Node (left, right) ->
        sumTreeCont left (fun leftSum ->
            sumTreeCont right (fun rightSum ->
                cont (leftSum + rightSum)))

Til å begynne med ser funksjonen nokså lik ut, men når vi kommer til den rekursive delen tar det litt av. Jeg gjør et rekursivt kall for det venstre deltreet, og bygger en ny continutation som jeg sender med. I den nye continuation’en er det et nytt kall til summeringsfunksjonen for det høyre deltreet, og der sender jeg med den orginale continuation-funksjonen.

Har du sett slik kode før så er det ikke så vanskelig. Men om du ikke er kjent med dette så vil det sansynligvis ta litt tid å bygge opp en inuitiv følelse for hva som skjer her. Jeg har derfor forsøkt å lage en litt forenklet illustrasjon av hva som skjer om jeg skal summere tallene i et lite tre med bare én vanlig node og to bladnoder:

Rekursjonen her har fire “trinn”. I trinn 2 ser du at vi bare jobber med bladnoden med verdien 4, men at vi tar vare på kalkulasjonen vi må utføre siden (summering av det høyre deltreet). Når venstre side er ferdig kan vi så utføre det vi har tatt vare på (trinn 3). Helt til slutt vil den orginale continuation-funksjonen bli evaluert.

Nå kan vi forsøke å summere tallene i det ubalanserte treet. Jeg sender med en continuation som vil ta summen og produsere en tekststreng som sier hva resultatet er (her bruker jeg partial application som jeg har snakket om mange ganger før).

> sumTreeCont imbalancedTree (sprintf "Result is: %d");;
val it : string = "Result is: 8549"

Og denne gangen fungerte det. Summeringsfunksjonen bruker nå halerekursjon, og kompilatoren kan dermed optimalisere den til å ikke “spise opp stacken”.

Konklusjon

Det kan væe vanskelig å få en god, intuitiv forståelse for hvordan algoritmer og funksjoner som bruker continuations fungerer. Men continuation-passing style kan løse utfordringer som det kan være svært vanskelig å løse på andre måter. Denne stilen har vært praktisert siden Vietnamkrigen (ingen sammenheng forøvrig), og jeg ser på det som en viktig teknikk som en komplett utvikler bør ha i verktøykassen sin.

PS: Denne blogposten er inspirert av boken Real-World Functional Programming (med eksempler i C# og F#).

For 17 år siden startet jeg med objektorientert programmering – jeg har det i blodet, og koder på den måten hver arbeidsdag (i alle fall ikke langt unna). Men for noen år siden begynte jeg også å se på funksjonell programmering, og denne bloggen har etterhvert fått mer og mer innhold om funksjonelle språk og teknikker.

Disse to paradigmene kan til en viss grad defineres ut fra forskjellen mellom dem; dvs. at de er i konflikt med hverandre, de har avvikende meninger om hvordan man skal designe løsninger. Etterhvert har jeg fått en viss forståelse for denne konflikten, eller mer presist jeg forstår mer og mer om hvilke tradeoffs de to paradigmene har i forhold til hvordan de vil jeg skal utføre jobben min.

Det er dette som får meg til å skrive denne teksten, hvor jeg vil kaste ut noen tanker om forholdet mellom paradigmene, og om hvordan de kan og bør sameksistere.

Kompleksitet

“Anyone can make the simple complicated. Creativity is making the complicated simple.” – Charles Mingus (innflytelsesrik jazzmusiker)

Programmering er å administrere kompleksitet. Vi skal løse et problem. Vi kan si at problemet uansett har en viss mengde kompleksitet, og beskrivelsen av løsningen tilfører ytterligere kompleksitet. Vår jobb er å strukturere denne kompleksiteten på en slik måte at den er enklest mulig å forstå, enklest mulig å verifisere (korrekthet), og enklest mulig å endre/bygge videre på. Alt dette samtidig som at løsningen må være god nok – da tenker jeg blant annet på krav til ytelse.

Og det er her de ulike programmeringsparadigmene og teknikkene kommer inn og tilbyr ulike måter å pakke inn kompleksiteten på.

OOP

Det objektorientert programmering tilbyr er å pakke inn kompleksitet i objekter. Internt i objektene kan det være mye kompleksitet, men de presenterer et tydelig grensesnitt til dem som skal forholde seg til objektene. Det som skjer på innsiden har ingen utenforstående noe med. Dette gjør programmer enklere å forstå, endre osv. Gitt at det er gjort på den “riktige” måten.

Men i tillegg til den skjulte kompleksiteten internt i objektene uttrykkes den viktige kompleksiteten for programmet i hvordan objektene samhandler med hverandre. Altså: Objekter er noe som er enkelt å forstå i seg selv – de er tydelige på hva de gjør – men når de brukes sammen med andre skapes det et komplekst nettverk av interaksjon.

Eller som foreleseren kanskje ville ha sagt det: En bil er en bil, og den er enkel å bruke. Du behøver ikke forstå hvordan den virker. Men når alle skal kjøre hjem klokken 16:00 oppstår det stor kompleksitet som kan være vanskelig å forstå.

I OOP har vi enkle objekter, men tillater kompleksitet i hvordan de fungerer sammen. For å forstå et objektorientert program må man kjenne samhandlingen mellom objektene, og hvilke bi-effekter disse samhandlingene har.

FP

Den sentrale enheten i funksjonell programmering er funksjonen. Og den ideelle funksjonen er enkel. Blant annet fordi den er en matematisk funksjon – gitt et bestemt input gir den alltid samme output. Funksjonen henger ikke på et objekt, og er ikke avhengig av tilstand.

Konvensjonen i funksjonell programmering er derimot å akseptere mer kompleksitet i dataene som funksjonene skal jobbe på. Og funksjonene har mer intim kunnskap om dataene de mottar. Når man skal forstå et typisk program fra den funksjonelle paradigmen må man vite mye mer om strukturen på dataene som flyter gjennom systemet. Men å forstå hvordan funksjonene samhandler er enklere.

Ingen av paradigmene kan altså fjerne kompleksitet, men den pakkes inn og plasseres på ulike steder.

OOP ∪ FP

Jeg har tidligere fortalt om hvordan min C#-kode de siste årene har utnyttet mer og mer av de funksjonelle egenskapene til språket. Og Rich Hickey har fortalt at han i flere år kun brukte den funksjonelle paradigmen når han kodet i C# (før han lagde Clojure). Han lagde da kun statiske klasser med statiske metoder, som i prinsippet blir som funksjonelle moduler av funksjoner uten tilstand. Det går altså an å bevege seg langt inn å bevege seg inn i FP fra OOP.

Det finnes også dem som benytter en funksjonelt språk som Scheme på en sånn måte at de programmerer objektorientert. Alt man tranger for å lage objekter er jo tross alt funksjoner med frie variabler.

Men det finnes en rekke språk som er designet for å forene og utnytte begge paradigmene. Til en viss grad gjør kanskje de fleste moderne programmeringsspråk dette. Men de mest åpenbare er språk som F#, Scala og Clojure.

Disse språkene inneholder altså elementer fra begge verdener. Samtidig som de typisk gjør det enklest å løse et problem på én måte, så tillater de den andre. Disse språkene blir som en union av OOP og FP.

Personlig synes jeg dette er utfordrende. Med mange muligheter får man også muligheten til å rote det til. Jeg vingler mellom OOP og FP når jeg programmerer, og den som skal lese og forstå koden må forholde seg til et større sett med teknikker og abstraksjoner.

OOP ∩ FP

Hva om man i stedet kombinerte de to paradigmene på en sånn måte at man håndhevet det beste fra dem begge?

I går kom jeg over en artikkel som het Functional programming in object oriented languages. Her forteller Simon Harris om en reise ikke helt ulik min egen – han programmerer i utgangspunktet objektorientert, men har fått mer og mer interesse for den funksjonelle paradigmen.

Simon har derimot gjort noen litt andre observasjoner og konklusjoner enn meg. Han er glad i OO, og bruker i større grad FP til å forbedre sin objektorientering. Gjennom å være disiplinert følger han flere av “reglene” fra funksjonell programmering i sine objektorienterte design.

Han bruker altså ikke OOP der hvor det er best og FP der det er best, men smelter det sammen til en kombinert paradigme. Han opererer i skjæringspunktet mellom OOP og FP.

Dette fikk meg til å tenke tanker jeg ikke har tenkt før. Hvordan ville et språk som kombinerte OOP og FP på denne måten se ut? Hvordan ville det vært å programmere i det?

Immutable objects

Hva om språket ikke tillot at objektenes data endret seg? For en C#-utvikler betyr det at alle felt ville vært merket med readonly. Det er dette vi ofte kaller for Value Objects. Kunne du programmert kun med slike objekter?

De som kjenner funksjonell programmering vil si “ja”, dette er mulig.

I artikkelen snakker Simon mye om egenskapene til et slikt designvalg; at de f.eks. gir et tydeligere skille mellom commands og queries (CQS, et prinsipp fra objektorientert programmering). Og at slike objekter danner grunnlaget for såkalte persistente datastrukturer (som er sentrale for ytelsen i språk som Clojure).

Hva om språket også håndhevet at alle metodene på objektet måtte bruke objektets tilstand på en eller annen måte? Altså at det ikke er lov med metoder som kunne vært statiske. Vil dette kunne føre til god objektorientering?  Vil det føre til mer komplett test coverage? Vil det gi kode som er enklere å forstå og endre? Simons erfaringer kan tyde på dette.

Tankene er nokså ferske, men jeg kunne godt tenkt meg å forsøke å kode i et slikt språk. Som Simon kan jeg selvfølgelig være disiplinert og forsøke å følge disse prinsippene når jeg jobber i OO-språk. Men egentlig fikk jeg mest lyst til å lage et nytt språk.

Kanskje jeg kan gjøre en mellomting og bruke Lisp med et sett med makroer som gjør denne måten å kode på enkelt?

Konklusjon

De ulike programmeringsparadigmene handler om ulike måter å strukturere kompleksitet og gjøre den håndterbar. Paradigmene har ulike tradeoffs: OOP tilbyr en objektabstraksjon som skjuler kompleksitet, men man må forstå hva som skjer når objektene samhandler. FP tilbyr funksjoner som er enkle å forstå, men man må forstå mere komplekse datastrukturer og datatransformasjoner (eller funksjonskomposisjoner).

Språk som kombinerer OOP og FP i dag gjør det ofte (slik jeg ser det) mulig å skrive kode som kombinerer “det værste” fra begge verdener. Hva om vi hadde et språk som oppfordret til å kun kombinere “de beste” elementene? FOP – funksjonell objektprogrammering!  Det ville vært et strengere språk som gav mange føringer til hvordan man skal kode. Men jeg tenker det det hadde vært spenende å prøve.

Vet du hva dette er?

function(callback) {
    return callback(1,function(callback) {
        return callback(2,function(callback) {
            return callback(3,function(callback) {
                return callback(undefined,undefined,true);
            },false);
        },false);
    },false);
};

For det første; dette er JavaScript. Koden er et eksempel på hvordan du kan representere lister i et språk som ikke har stort annet enn funksjoner. Funksjonene i dette eksempelet representerer listen bestående av elementene 1, 2 og 3. Jeg kommer tilbake til denne koden i slutten av artikkelen.

I forrige uke kom jeg over bloggposten List Out of Lambda. Bloggeren Steve Losh leker der med tanken: “Hva trenger man fra et programmeringsspråk egentlig?”. Steg for steg forklarer han hvordan man kan lage lister av enkle byggestener, noe jeg selv også forsøkte i Funksjonell lek med lister i F# for en måned siden. Steve gjør det bedre, og går også lengre i å bygge ulike liste-operasjoner og også tall og regneoperasjoner basert på funksjons-listene.

Jeg tenker blant annet at måten blogposten gjør det på er et bra utgangspunkt for å innøve grunnleggende forståelse for funksjonell programmering, og at det kan være en grei kata-lignende øvelse å gjøre fra tid til annen. Jeg foreslår først og fremst at du leser bloggposten til Steve – det jeg vil gjøre her er bare å gjengi kjernen i eksempelet hans. Jeg vil også sammenligne med en implementasjon i CoffeeScript og en i LispyScript (to språk som kompilerer til JavaScript).

Lister av funksjoner i JavaScript

Her følger koden som trengs for å definere og jobbe med lister: funksjonene cons, head, tail og isEmpty samt en funksjon emptyList som representerer den tomme listen. Steve bruker navnet prepend i stedet for cons, men jeg er såpass farget av Lisp at jeg synes cons er bedre.

(function() {

  var emptyList = function(callback) {
    return callback(undefined, undefined, true);
  };

  var cons = function(head, tail) {
    return function(callback) {
      return callback(head, tail, false);
    };
  };

  var head = function(lst) {
    return lst(function(head, tail){
      return head;
    });
  };
  var tail = function(lst) {
    return lst(function(head, tail){
      return tail;
    });
  };
  var isEmpty = function(lst) {
    return lst(function(head, tail, empty){
      return empty;
    });
  };

  var list1 = cons(1, cons(2, emptyList));

  console.log(head(list1));
  console.log(head(tail(list1)));
  console.log(isEmpty(tail(list1)));
  console.log(isEmpty(tail(tail(list1))));

})();

Sliter du med å forstå dette må du altså lese List Out of Lambda, som forklarer det veldig bra!

I slutten av koden ser du at jeg oppretter en liste jeg kaller list1 som i prinsippet består av elementene 1 og 2. Output fra scriptet blir “1″, “2″, “false” og “true”.

Lister av funksjoner i CoffeeScript

Siden det er mye funksjoner her tenkte jeg det ville være interessant å se hvordan koden ble seende ut i CoffeeScript.

empty_list = (callback) ->
  callback undefined, undefined, true

cons = (head, tail) ->
  (callback) -> callback head, tail, false

head = (lst) ->
  lst ((head) -> head)

tail = (lst) ->
  lst ((_, tail) -> tail)

is_empty = (lst) ->
  lst ((_, __, empty) -> empty)

list1 = cons 1, (cons 2, empty_list)

console.log (head list1)
console.log (head (tail list1))
console.log (is_empty (tail list1))
console.log (is_empty (tail (tail list1)))

Som du ser er koden mye mer kompakt, og den produserer nøyaktig den samme JavaScript-koden.

Men for en gangs skyld synes jeg det blir litt vel kompakt. Disse funksjonene som returnerer funksjoner blir rett og slett litt vanskelige å få tak på i CoffeeScript. Det er så få faste holdepunkter i koden, som stort sett bare består av piler, paranteser og variabelnavn. I dette tilfellet savner jeg faktisk strukturen som krøllklammer, function og return gir meg i JavaScript.

Kanskje det er en vanesak, men det er i alle fall en observasjon.

Lister av funksjoner i LispyScript

Jeg introduserte mine lesere for LispyScript første gang i posten JavaCoffeeLispyPogoScript i fjor høst. LispyScript er en Lisp-variant som kan brukes sammen med node.js, og som produserer JavaScript-kode. Her er koden vi jobber med oversatt til LispyScript:

((function ()

  (var empty_list
    (function (callback)
      (callback undefined undefined true)))

  (var cons
    (function (head tail)
      (function (callback)
        (callback head tail false))))

  (var head
    (function (lst)
      (lst (function (head tail empty) head))))

  (var tail
    (function (lst)
      (lst (function (head tail empty) tail))))

  (var is_empty
    (function (lst)
      (lst (function (head tail empty) empty))))

  (var list1 (cons 1 (cons 2 empty_list)))

  (console.log (head list1))
  (console.log (head (tail list1)))
  (console.log (is_empty (tail list1)))
  (console.log (is_empty (tail (tail list1))))))

Som vanlig synes jeg Lisp gir ganske vakker kode, og i alle fall for meg er den enklere å lese enn både JavaScript og CoffeeScript-variantene.

Lisp-makroer avslører hva som skjer

Og så fikk jeg en ide. Hva om jeg endret LispyScript-versjonen til å bruke makroer i stedet for funksjoner for cons, head, tail, is_empty og empty_list? Da vil det som skjer i runtime i den første versjonen i stedet skje i compile time. La oss teste det…

((function ()

  (macro empty_list ()
    (function (callback)
      (callback undefined undefined true)))

  (macro cons (head tail)
    (function (callback)
      (callback ~head ~tail false)))

  (macro head (lst)
    (~lst (function (head tail empty) head)))

  (macro tail (lst)
    (~lst (function (head tail empty) tail)))

  (macro is_empty (lst)
    (~lst (function (head tail empty) empty)))

  (var list1 (cons 1 (cons 2 (empty_list))))

  (console.log (is_empty (tail (tail list1))))))

Merk: Jeg har fjernet tre av console.log-kallene, kun for enkelhets skyld.

Hvis jeg nå kompilerer denne koden, og tar en titt på det resulterende JavaScriptet, vil lambda-listene avsløre hvordan de virker. Det du til nå har måttet forestille deg i ditt eget hode (eller som du så en preview av i starten av denne blogposten) blir nå mer eller mindre klart og tydelig:

// Generated by LispyScript v0.2.5
(function() {
    var list1 = function(callback) {
        return callback(1,function(callback) {
            return callback(2,function(callback) {
                return callback(undefined,undefined,true);
            },false);
        },false);
    };
    return console.log(list1(function(head,tail,empty) {
        return tail;
    })(function(head,tail,empty) {
        return tail;
    })(function(head,tail,empty) {
        return empty;
    }));
})();

Her er altså alle liste-operasjonene inlinet der de trengs i form av anonyme funksjoner – cons, head, tail osv. eksisterer ikke lengre som navngitte funksjoner.

Interessert i mer? Hva med å lese posten Message Passing Style som jeg skrev i 2011, hvor jeg snakker om objektorientert programmering basert på funksjoner (også med eksempel i JavaScript)?

Jeg fortsetter å eksperimentere med F#, og nå går vi over til noe litt mere avansert. MailboxProcessor er en klasse man finner i modulen Microsoft.FSharp.Control. Den er en slags agent som prosesserer meldinger asynkront. Den har en meldingskø som mange kan skrive til, men kun MailboxProcessor-agenten kan lese fra den.

Dette minner veldig om Actor Model, som jeg har eksperimentert med blant annet i Erlang tidligere. Se En introduksjon til Erlang og  Ping Ring del 5 for mer info – begge fra 2010.

I denne artikkelen vil jeg gi et grunnleggende eksempel på hvordan Actors fungerer i F#. Jeg vil lage starten på en asynkron kalkulator, og så bruke den til å plusse sammen en rekke tall.

En liten debug-funksjon

Når jeg skal illustrere hvordan asynkron kode fungerer kan det være greit å printe ut litt til konsollet, slik at man kan se hvilken rekkefølge ting skjer i. Derfor lager jeg en funksjon jeg kaller dbg som skriver ut en streng sammen med et timestamp (med millisekund-presisjon).

open System
open Microsoft.FSharp.Control

let dbg msg =
    printfn "%s %s"
        (DateTime.Now.ToString "HH:mm:ss,fff")
        msg

De to første linjene importerer namespacene jeg trenger i programmet. Hvis jeg nå kaller funksjonen noen ganger:

dbg "test 1"
dbg "test 2"
dbg "test 3"
dbg "test 4"

Vil jeg få output som dette:

08:32:30,834 test 1
08:32:30,835 test 2
08:32:30,835 test 3
08:32:30,835 test 4

Et tips: Jeg koder i F# i Visual Studio. Men jeg kompilerer ikke, og kjører ikke programmet med F5 som jeg ville gjort i C#. I stedet har jeg åpnet et vindu som kalles F# Interactive, og hvis jeg markerer litt kode i editoren og trykker Alt+ENTER vil koden eksekveres og resultatet vises i det vinduet.

En Actor-basert kalkulator

En actor skal som sagt prosessere meldinger. F# er sterkt typet, så jeg trenger en meldingstype. Jeg bruker en Discriminated Union til det i dette tilfellet. Her sier jeg at en melding kan være enten en pluss-operasjon med et tilhørende tall, eller en get-operasjon for å lese ut verdien til kalkulatoren. Get-operasjonen sin verdi er en AsyncReplyChannel<int>. Dette er et objekt som kan brukes til å sende en melding tilbake fra actoren til den som sendte Get-meldingen.

Her definerer jeg meldingstypene:

type Message =
    | Add of int
    | Get of AsyncReplyChannel<int>

Skulle dette vært en orntlig kalkulator hadde jeg lagt til meldinger for å gange, dele og trekke fra også, men Add er godt nok for dette eksempelet.

Og nå følger opprettelsen av actoren. Jeg oppretter en instans av MailboxProcessor, og sender inn en anonym metode. I den oppretter jeg en rekursiv funksjon som jeg kaller loop, og så kaller jeg den. Argumentet til loop er i dette tilfellet minnet til kalkulatoren, som i utgangspunktet er tallet 0.

let asyncCalculator = new MailboxProcessor<Message>(fun inbox ->
    let rec loop state =
        async { let! msg = inbox.Receive()
                match msg with
                | Add x ->
                    sprintf "Actor adding %d" x |> dbg
                    return! loop (state + x)
                | Get replyChannel ->
                    replyChannel.Reply state
                    return! loop state }
    loop 0)

Det første loop gjør er å forsøke å motta en melding fra mailboksen sin. Hvis mailboksen er tom vil dette kallet blokkere inntil det kommer en melding. Deretter avgjør loop hvilken type melding det er jeg har mottat, utfører det som skal gjøres, og kaller seg selv.

loop bruker noe vi kaller en asynkron blokk (eller asynkron workflow): async { .. }. Blokken er en computation expression, og har jeg forstått det riktig så inneholder den det Haskel-utviklere kaller en monade. Men du trenger ikke nødvendigvis forstå monader (en nesten umulig oppgave) for å bruke dem. Så vi kjører videre..

Sende meldinger til kalkulatoren

I kodesnutten nedenfor starter jeg først actoren. Deretter kjører jeg en løkke fra 1 til 10 og sender Add-meldinger ved hjelp av kalkulatorens Post-metode. Til slutt bruker jeg PostAndReply for å sende en Get-melding og vente på svaret. Siste linje skriver ut svaret.

asyncCalculator.Start()

for n in [1..10] do
    Add n |> asyncCalculator.Post

let result = asyncCalculator.PostAndReply(fun replyChannel ->
    dbg "Getting result"
    Get (replyChannel))

sprintf "Result is %d" result |> dbg

Når jeg kjører denne koden får jeg følgende output i F# Interactive-vinduet:

08:33:14,972 Getting result
08:33:14,977 Actor adding 1
08:33:14,977 Actor adding 2
08:33:14,977 Actor adding 3
08:33:14,978 Actor adding 4
08:33:14,978 Actor adding 5
08:33:14,978 Actor adding 6
08:33:14,978 Actor adding 7
08:33:14,978 Actor adding 8
08:33:14,979 Actor adding 9
08:33:14,979 Actor adding 10
08:33:14,979 Result is 55

Her ser du to ting: For det første så virker det som om actoren behandler meldingene i “riktig” rekkefølge. MailboxProcessor behandler meldingene sine synkront, og i den rekkefølgen de ankommer i køen. Og for det andre ser du at kalkulatore som forventet er asynkron, siden den ikke kom igang med å behandle meldingene før siste melding ble sendt (“Getting result” ble skrevet ut før actoren begynte å “adde”.

Asynkron “getter”

I koden over blokkerer jeg hovedtråden mens jeg venter på svar fra Get-meldingen. Det trenger jeg ikke å gjøre. I stedet for å bruke PostAndReply kan jeg bruke en annen variant som heter PostAndAsyncReply. Da må jeg sende Get-meldingen og vente på svaret i en async-blokk.

Slik ser det ut:

let asyncGetter =
    async {
        let! reply = asyncCalculator.PostAndAsyncReply(fun channel ->
            dbg "Getting result async"
            Get (channel))
        sprintf "Result is %d" reply |> dbg }

for n in [1..10] do
    Add n |> asyncCalculator.Post

Async.Start (asyncGetter)

dbg "Main thread done!"

Og da fikk jeg en litt mere spennende output:

08:45:37,670 Actor adding 1
08:45:37,670 Actor adding 2
08:45:37,670 Actor adding 3
08:45:37,670 Main thread done!
08:45:37,671 Actor adding 4
08:45:37,671 Actor adding 5
08:45:37,671 Actor adding 6
08:45:37,671 Actor adding 7
08:45:37,672 Getting result async
08:45:37,672 Actor adding 8
08:45:37,672 Actor adding 9
08:45:37,672 Actor adding 10
08:45:37,677 Result is 110

Denne gangen ser vi at kalkulatoren kommer igang med prosesseringen av Add-meldinger før hovedtråden er ferdig. Vi ser også at Get-meldingen blir fyrt avgårde før Add-prosesseringen er ferdig.

Konklusjon

Jeg har vært veldig fasinert av Actor Model siden jeg lørte om det for tre år siden, og det føles som en intuitiv og lur måte å designe samtidighetssystemer på. Men jeg har fortsatt aldri brukt det til noe fornuftig. Hovedgrunnen er nok at støtten for det har vært dårlig (eller lite kjent) på de plattformene jeg har utviklet for. Men nå vet jeg at støtten er der på .NET-plattformen!

For ordens skyld, du kan bruke MailboxProcessor fra andre .NET-språk enn F#. Da heter den FSharpMailboxProcessor.

Måten det gjøres på i F# virker grei nok – det er litt mere “knotete” enn i Erlang, men det der med AsyncReplyChannel var egentlig ganske elegant. Jeg ser derimot at jeg bør bli komfortabel med asynkrone workflows før jeg tør bruke MailboxProcessor for fullt.

For mer info om MailboxProcessor se MSDN og denne siden på wikibooks.

I forrige post lekte jeg med med cons-baserte lister. Nå har jeg gått over til tre-strukturer. Som utvikler får man veldig ofte bruk for trær av ett eller annet slag, så dette er noe det kan være greit å øve litt på av og til – og spesielt når man jobber med et nytt programmeringsspråk.

Et node-basert tre

Husker du cons-cellen fra forrige bloggpost? I Lisp bruker man rett som det er cons-celler til å lage trær med også. Det jeg skal gjøre nå ligner litt, men jeg skal gjøre det litt enklere.

Igjen bruker jeg en discriminated union til å definerer en generisk type. Denne gangen kaller jeg den Tree. Tree er en union av to muligheter: Enten er det en Branch (en gren altså), som har en verdi av den generiske typen samt en liste med flere tre-noder. Eller er den et Leaf (et blad), som bare har en verdi.

type Tree<'T> =
    | Branch of 'T * Tree<'T> list
    | Leaf of 'T

Forresten, når jeg nå snakker om lister så kommer jeg ikke til å bruke min hjemmesnekrede liste fra forrige post. Jeg skal bruke listene som finnes i F#.

En liste kan konstrueres på denne måten:

let aList = 1 :: 2 :: 3 :: 4 :: []

:: er det samme som cons-funksjonen fra sist, men den fungerer som en operator mellom to argumenter (i stedet for at begge argumentene kommer etterpå).

Jeg kan også opprette den samme listen slik som dette:

let aList = [1; 2; 3; 4]

Hadde vi brukt komma i stedet for semikolon hadde det lignet på arrays i de fleste andre språk. Til slutt kan jeg nevne at man også kan droppe semikolon-separatorene om man putter elementene i listen på hver sin linje, slik som dette:

let aList = [ 1
              2
              3
              4 ]

Men tilbake til trær! For å lage et bittelite tre med min nye datatype kan jeg nå gjøre slik som dette:

let smallTree = Branch ("root", [ Leaf "leaf" ])

Dette definerer treet smallTree, som består av en rot-node og en blad-node. Rot-noden holder verdien "root", og bladnoden holder verdien "leaf".

Traversering av trær

La oss lage et litt større tre:

let root =
    Branch
      ("root",
       [Branch ("branch1", [Leaf "A"
                            Leaf "B"])
        Branch ("branch2", [Leaf "C"
                            Branch ("D", [Leaf "E"])
                            Leaf "F"])])

En ASCII-representasjon av dette treet har du her:

            root
            /  \
      branch1  branch2
      /   |    |  \   \
     A    B    C   D   F
                   |
                   E

Det jeg nå vil lage er en funksjon som kan brukes til å besøke samtlige noder i treet. Det finnes to hovedstrategier for å besøke alle nodene, og vi kaller dem dybde-først og bredde-først. Bredde-først vil besøke alle nodene på et gitt nivå før det beveger seg videre ned i treet. Dybde-først vil i stedet gå helt til bunns i en gren, for så å snu, gå tilbake, og så helt ned i neste gren. Ta en titt på Wikipedia-artiklene om depth-first search og breadth-first search om du trenger å vite mer.

Jeg velger å bruke en dybde-først strategi, og kaller funksjonen visit:

let rec visit f tree =
    match tree with
    | Leaf    v       -> f v
    | Branch (v, sub) -> f v
                         List.iter (visit f) sub

visit er rekursiv, og tar i tillegg til treet inn en funksjon som skal kalles for hver node. Hvis noden som behandles er et Leaf, så vil den bare kalle funksjonen f med verdien av noden som argument. Hvis noden derimot er en Branch vil den først kalle f på verdien, men så iterere over alle subnodene og kalle visit på dem.

Nå kan jeg bruke visit-funksjonen på treet mitt, og sende med en funksjon som rett og slett bare skriver ut verdien i noden samt et mellomrom:

visit (printf "%s ") root

Output:

root branch1 A B branch2 C D E F 

Fra dette kan du se at visit har brukt dybde-først strategien.

En mere funksjonell fremgangsmåte

visit bruker ikke hva vi vil kalle en funksjonell fremgangsmåte. Den baserer seg i stedet på at funksjonen f som sendes inn har sideeffekter – i tilfellet over skrev jeg ut verdier til konsollet.

I stedet ønsker jeg en funksjon som kan traversere treet, kalle en funksjon for hver node, men ta vare på resultatene underveis. Til slutt skal den returnere “summen” fra alle nodene.

Høres dette kjent ut? Det var jo dette fold gjorde for lister! Det jeg ønsker meg er en fold-funksjon for trær. Jeg velger å kalle den treeFold:

let rec treeFold f acc tree =
    match tree with
    | Leaf    v       -> f acc v
    | Branch (v, sub) -> List.fold (treeFold f) (f acc v) sub

Denne funksjonen har én parameter mer enn visit, nemlig en akkumulatorverdi (acc). Her samles resultatet fra behandlingen av alle nodene. I den siste linjen kaller jeg F# sin fold-funksjon på alle undernodene til noden jeg behandler. Funksjonen som skal kalles på hver av dem er (treeFold f). Akkumulatorverdien er resultatet av å kalle f på denne nodens verdi: (f acc v).

Henger du med?

Nå kan jeg kalle treeFold og sende inn en funksjon som ikke har noen sideeffekter:

let result = treeFold (sprintf "%s %s") "" root

Og resultatet blir at result inneholder den samme strenger som tidligere ble skrevet ut til konsollet.

Å regne med trær

Nå skal jeg gjøre noe gøy! Jeg skal bruke trestrukturen jeg har laget til å utføre regnestykker. Jeg skal rett og slett laget et såkalt expression tree. Deretter vil jeg lage en funksjon som parser treet – dvs. besøker alle nodene og kalkulerer resultatet av regnestykket det representerer.

Regnestykket jeg vil modellere er 3 * 4 + 5 * 6. Som et tre vil det se slik ut:

            Plus
            /  \
     Multiply  Multiply
      /   |      |   \
     3    4      5    6 

Til dette trenger jeg en ny datatype jeg kaller CalcExpression, som i dette enkle eksempelet kan være en av tre ting: et tall, en multipliseringsoperator, eller en adderingsoperator.

type CalcExpression =
    | Number of int
    | Multiply
    | Plus

Og så kan jeg sette opp regnestykket som et tre:

let expression =
    Branch
      (Plus, [Branch (Multiply, [Leaf (Number 3)
                                 Leaf (Number 4)])
              Branch (Multiply, [Leaf (Number 5)
                                 Leaf (Number 6)])])

Da gjenstår det bare å lage parseren, som jeg har kalt calc. Den må skille mellom de ulike typene av CalcExpression, og vite hvordan den håndterer hver av dem. Finner den en addisjon må den plusse sammen alle subnodene (som kan være trær – derfor inneholder den rekursive kall til calc). Finner den en multiplikasjon må den gjøre det samme, men denne gangen gange sammen subnodene. Finner den et tall så returneres bare tallet.

let rec calc = function
    | Branch (Plus,     xs) -> List.fold (fun x y -> x + calc y) 0 xs
    | Branch (Multiply, xs) -> List.fold (fun x y -> x * calc y) 1 xs
    | Leaf   (Number n)     -> n
    | _                     -> failwith "Invalid expression tree"

Til slutt kan jeg finne svaret av regnestykket:

let answer = calc expression

.. som selvfølgelig er 42.

I kveld har jeg lekt meg litt med F#. Det er ikke et språk jeg kan så veldig godt, så da er det greit å øve på helt basic ting. Noe jeg ofte gjør er å implementere grunnleggende funksjoner som jobber på lister – som map, filter og fold. Du husker kanskje at jeg gjorde det samme i posten Den Lille Erlanger?

Og nå vil jeg dele hva jeg gjorde..

Lenkede lister

I stedet for å bruke F#’s innebygde liste-type så ville jeg denne gangen lage min egen. Dette er altså ingen instruksjon i hvordan man bør bruke F#, men jeg lærte endel av å gjøre denne øvelsen.

En lenket liste består av det vi kaller for cons-celler. Jeg endte opp med å bruke en såkalt discriminated union til å definere en cons-celle:

type Cell<'T> =
    | Cons of 'T * Cell<'T>
    | Nil

som jeg så kan bygge lister med:

let aList = Cons("one", Cons("two", Cons("three", Nil)))

En Cell er altså en generisk type som kan bestå av enten en Cons eller Nil. En Cons består av en tuplet av en verdi av den generiske typen pluss en ny Cons (som kan være Nil). Nil er rett og slett en tom liste, og brukes som du ser over til å terminere listen. Dette er Computer Science 101.

Kan F# bli til Lisp?

Cons-celler er hentet fra programmeringsspråket Lisp, og det slo meg at ved å lage en liten funksjon som jeg kaller cons kan jeg få konstruksjonen av lister til å se ut som om det var Lispkode jeg skrev. Her er funksjonen:

let cons a b = Cons(a, b)

Og når jeg bruker den for å lage en liste med ordene “one”, “two” og “three” ser det slik ut:

let aList' = (cons "one" (cons "two" (cons "three" Nil)))

Transformering av lister

Nå er det på tide å definere funksjonen map for denne listetypen jeg har laget. Den er rekursiv (legg merke til nøkkelordet rec) og den bruker pattern matching til å skille mellom en Cons og Nil. For hvert kall til map blir det laget en ny cons-celle.

let rec map f lst =
    match lst with
    | Cons(head, tail) -> Cons(f head, map f tail)
    | Nil              -> Nil

Nå kan jeg for eksempel bruke map til å transformere alle elementene i listen min til store bokstaver:

let aListUppercase = map (fun (s: string) -> s.ToUpper()) aList

PS: Her blir det bonuspoeng til dem som la merke til at map-funksjonen min ikke brukte hale-rekursjon. Mer om det senere…

Hvor mange elementer har jeg?

Ved å lage en funksjon som teller antall elementer i en cons-basert liste får jeg vist frem hvordan man kan lage og bruke indre funksjoner i en funksjon.

let length lst =
    let rec length' lst acc =
        match lst with
        | Cons(head, tail) -> length' tail acc + 1
        | Nil              -> acc
    length' lst 0

For å finne lengden på en liste gjør jeg da slik:

let listLength = length aList

Fold – den beste funksjonen av dem alle

Fold (også kjent som reduce, aggregate, accumulate, inject, compress m.m.) er en grunnleggende liste-funksjon. Den tar som argumenter en funksjon (f), en startverdi (acc) og en liste (lst). f kalles på acc og hvert element fra listen i tur og orden, og resultatet tas hele tiden vare på i en oppdatert versjon av acc.

let rec fold f acc lst =
    match lst with
    | Cons(head, tail) -> fold f (f acc head) tail
    | Nil              -> acc

Denne versjonen av fold kalles ofte foldl, eller left fold. Her er en illustrasjon av hva den gjør:

  :                            f
 / \                          / \
a   :       foldl f acc      f   c
   / \    ------------->    / \
  b   :                    f   b
     / \                  / \
    c  []                acc a

Ett problem med fold er at om den skal brukes til å produsere en ny liste (for eksempel om den brukes som grunnlag for map), så vil listen være reversert i forhold til input-listen.

Det går også an å lage en foldr – right fold – som ikke har dette revers-problemet:

let rec foldr f acc lst =
    match lst with
    | Cons(head, tail) -> f (foldr f acc tail) head
    | Nil              -> acc

Den er kanskje litt enklere å forså i forhold til hva den produserer:

  :                         f
 / \                       / \
a   :       foldr f acc   a   f
   / \    ------------->     / \
  b   :                     b   f
     / \                       / \
    c  []                     c   acc

Foldr har derimot et annet problem – den bruker ikke hale-rekursjon. Det rekursive kaller er nemlig ikke det siste som skjer i hvert kall, og det gjør at den raskt kan spise opp stacken om man behandler lange lister.

Men uansett, la oss bruke fold til noe fornuftig. Hva med å summere en liste? Her lager jeg først en liste med tall, deretter en sum-funksjon basert på fold, og finner til slutt summen som jeg tar vare på i sumNumbers:

let numbers = (cons 1 (cons 2 (cons 3 Nil)))
let sum = fold (fun x y -> x + y) 0
let sumNumbers = sum numbers

For litt siden lagde jeg en funksjon for å telle antall elementer i en liste. Den kan jeg lage på nytt nå som jeg har fold i verktøybeltet mitt:

let length2 = fold (fun acc _ -> acc + 1) 0

Reversere en liste

Det neste jeg gjorde var å lage en funksjon for å reversere en liste. Det kan være nyttig å ha, spesielt om man skal bruke den halerekursive fold-varianten mye. Som i den første length-funksjonen bruker jeg en indre funksjon, og pattern matchingen har nå blitt bittelitt mere avansert:

let reverse lst =
    let rec reverse' lst acc =
        match lst with
        | Cons(head, Nil)  -> cons head acc
        | Cons(head, tail) -> reverse' tail <| cons head acc
        | Nil              -> Nil
    reverse' lst Nil

Logikken her kan være litt vrien å skjønne, så forsøk verifiser for deg selv hva som foregår. Jeg plukker ett og ett element fra listen, og bygger opp en ny liste (acc) av disse. Når jeg sier reverse' tail <| cons head acc betyr det at resultatet av cons head acc sendes inn som andre argument til reverse'.

Filtrering

Funksjonen jeg sålangt mangler er den vi som regel kaller filter. Den filtrerer ut elementer fra en liste basert på resultatet av en predikatfunksjon (en funksjon som returnerer true eller false). Jeg kan implementere funksjonen slik som dette:

let filter p lst =
    let f acc x =
        if p x then cons x acc
        else acc
    foldr f Nil lst

Men her har jeg brukt foldr, og det er jo ikke bra! La oss bruke fold i stedet, og reversere listen igjen til slutt (slik at den opprinnelige rekkefølgen beholdes):

let filter2 p lst =
    let f acc x =
        if p x then cons x acc
        else acc
    fold f Nil lst |> reverse

Nå kan jeg lage et lite predikat som sjekker om et tall er et oddetall, og filtrere numrene mine med den:

let odd x = x % 2 <> 0
let oddNumbers = filter2 odd numbers

Oppsummering

Jammen ble det nok en blogpost om grunnleggende, funksjonelle liste-teknikker. Men det er viktige ting å ha kontroll på, og det gir meg alltid noe å bruke disse øvelsene når jeg skal lære meg nye språk – eller bare friske opp igjen gammel kunnskap. Jeg oppfordrer deg derfor til å gjøre det samme.

Og når du har god kontroll på lenkede lister kan du gå videre med trær, og deretter grafer (eller nettverk om du vil kalle dem det). Lister har du nesten alltid god støtte for i språk du bruker, men operasjoner på trær og grafer må man ofte lage på egen hånd. Kanskje jeg gjør det selv i morgen kveld, og at det da kommer en ny post snart om det. Den som følger med får se!

Jammen klarte jeg å levere et programmeringsspråk til PLT Games i januar også (se desember-bidraget Ropy her). README-filen sier det meste, så her er den gjengitt:

FORTHolito is a programming language – specifically an (incomplete) implementation of the FORTH programming language – made just for fun and for the learning experience. The interpreter is implemented in Ruby, and it has an interactive REPL.

But it’s more! It’s my entry into the PLT Games: Testing the Waters competition. I made it possible to write extensions to FORTHolito, and then wrote a test extension.

When you run FORTHolito with this extension all words you define have to include one or more tests – working examples of how the word operates.

Here’s an example of a word definition in FORTHolito:

: multiple-of? ( x n -- flag ) mod 0= ;

If I use the test extension however I would write it like this:

: multiple-of? ( x n -- flag ) mod 0=
  <EXAMPLE> given: 3 6  expect: true
  <EXAMPLE> given: 3 4  expect: false
;

FORTHolito (or FORTH basically) makes for some nice tests when all you do is operate on a data stack. The givens are just stack operations – “given 3 and 6 are pushed onto the stack”. What’s left on the stack when the word has been called is the expected part.

Try it out

FORTHolito is a small and limited language. But if you’re just curious about FORTH, or want to see how you can implement a simple language in Ruby, you should clone it and fire up the REPL.

FORTHolito have some basic options. Run it with –help to see how it’s used:

C:\dev\fortholito [master]> .\fortholito --help
Usage:

  FORTHolito [options] [files]

Options:
  --eval <code>         Evaluate code. Everything after --eval
                        is considered FORTHolito code. Code is
                        evaluated after files.
  --extend <extension>  Load an extension by name. Extensions
                        are loaded before files.
  --help                Display this help and exit.

When you enter the REPL this is what you’ll see:

C:\dev\fortholito [master]> .\fortholito
Welcome to FORTHolito version 0.2 by @tormaroe
Type 'help' and hit [ENTER] to get started..
ok

If you now type help you’ll get a list of useful words to try out:

ok  help
 SOME USEFULL WORDS YOU SHOULD TRY:
  words       \ display all words in the vocabulary
  describe    \ pop word (string) and show details
  .           \ pop and print the top item from the stack
  .s          \ display stack once
  showstack   \ toggle display of stack between commands
  stacktrace  \ display all modifications to stack for debugging
  help:stack  \ cheat sheet of stack overations
  bye         \ exit REPL
ok

To get a feel for how much (or how little) of FORTH I’ve implemented in FORTHolito, type words:

ok  words
 *                  +                  -                  -rot
 .                  .s                 /                  0<
 0<=                0<>                0=                 0>
 0>=                1+                 1-                 2*
 2/                 2drop              2dup               <
 <=                 <>                 =                  >
 >=                 abs                and                between
 bye                clear              cr                 depth
 describe           drop               dup                false
 help               help:stack         max                min
 mod                negate             nip                noop
 or                 over               push-range         rand
 rot                showstack          space              stacktrace
 swap               true               tuck               within
 words
ok

In addition to the words there are some constructs like if and iteration using begin..until and begin..while..repeat. You should have a look in the examples directory as well as the spec.rb file to learn more.

As a treat to Ruby developers I’ve also made it possible to drop into Ruby inside strings.

ok  "#{ 2 + 2 }"
ok  "2 + 2 equals "
ok  . . cr
2 + 2 equals 4
ok

Final thoughs

FORTHolito hasn’t become all I hoped it would be. I had big plans for the test extension when I started – it would become this great, interactive development environment for producing perfectly tested and safe code. I still believe my vision is possible, and possibly even useful, but it would take more time.

The drive and passion I had in the beginning has dissipated for now. But it was great fun while it lasted – and maybe some day I’ll pick up where I left off. Either way I did manage to enter into the PLT Games again.

FORTHolito finner du på Github.

Jeg har lest meg litt opp på noe som heter Parrot i det siste. Parrot er en virtuell maskin på samme måte som JVM (Java-platformen) og CLR (.NET på Windows). Parrot er VM’en som ligger bak Rakudo, den mest profilerte implementasjonen av Perl 6.

Mens JVM og CLR først og fremst er designet med tanke på statisk typede språk, er Parrot tilrettelagt for dynamiske språk. Dessuten er VM’en register-basert, mens JVM og CLR er stack-baserte. Dette betyr at Parrot’s simulering er tettere på hvordan den fysiske datamaskinen faktisk fungerer.

Grunnen til at jeg ser på Parrot er at det er en interessant platform for utvikling av nettopp dynamiske språk. Parrot har en mengde kompilerings-verktøy som gjør jobben brukbart enkel (det gjenstår selvsagt å se).

Parrot-kode

Parrot Intermediat Representation, eller PIR, er lavnivå-språket man normalt bruker får å kode mot Parrot. Parrot er basically et assembly-språk, men har noen høyerenivå-egenskaper i form av syntaktisk sukker. Under PIR finner man PASM – Parrot assembly uten dette sukkeret. Begge deler kan kompileres til PBC – Parrot Byte Code – som er det VM’en eksekverer.

Så hvis jeg skal lage et språk som skal kjøre på Parrot så må jeg lære meg PIR. Og her ser du mitt aller første PIR-program. Som vanlig har jeg laget kode som skriver ut summen av alle multipler av 3 eller 5 under 1000 (du finner dusinvis av løsninger på denne oppgaven i ulike språk her på bloggen).

Først har vi en subrutine som sjekker om et tall er et multippel av 3 eller 5:

.sub multiple_of_3_or_5
  .param int n
  $I0 = n % 3
  unless $I0 goto yes
  $I0 = n % 5
  $I0 = not $I0
  .return ($I0)
yes:
  .return (1)
.end

Rutinen tar ett parameter n av typen int. Jeg bruker et integer-register $I0 hvor jeg først tar vare på resten av å dele n på 3. Og så må jeg bruke goto – det er egentlig den eneste tingen jeg har for å styre programflyten i PIR, bortsett fra funksjonskall da. Merk også at integer-verdien 0 er det samme som false, mens alle andre tall er true. Resten burde da være mulig å forstå. Subrutinen returnerer altså 0 eller 1 alt etter om n er et multippel av 3 eller 5 eller ikke.

Og så har jeg laget en main-subrutine som ved hjelp av flere goto’s looper gjennom alle tall fra 1 til 999 og legger de til en sum om tallet skal inkluderes.

.sub main :main
  .local int sum, n
  n = 0
  sum = n

loop:
  inc n
  if n == 1000 goto end
  $I0 = multiple_of_3_or_5(n)
  if $I0 goto add_it
  goto loop

add_it:
  sum += n
  goto loop

end:
  say sum
.end

Her ser du ett av eksemplene på at PIR er enklere å kode i enn PASM – jeg kan deklarere lokale variabler som sum og n. I bakkant er dette bare ulike registre, men jeg kan i alle fall gi dem fornuftige navn.

Og det var det! Jeg er helt i startgropen, men vil eksperimentere med PIR og Parrot’s kopilatorverktøy en stund fremover for å se om jeg kan lage noe kult noe.

Hva er dette her?

Det du ser over er kildekoden til et program. Språket som er brukt heter Ropy, og programmet skriver som seg hør og bør ut teksten “hello, world”.

Ropy er altså et programmeringsspråk. Et ganske lite et. Og ganske ubrukelig egentlig, selv om det strengt tatt er turing-komplett, og dermed like “kraftig” som alle andre språk. Faktisk er det et forsøk på å lage en type språk vi kaller for en turing tarpit:

Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy.

Alan Perlis, Epigrams on Programming

Jeg lagde Ropy i løpet av et par kvelder i desember. Språket er mitt bidrag til desember-konkurransen på PLT Games (Programming Language Theory Games). Hver måned blir man bedt om å lage et nytt programmeringsspråk, og i den påfølgende måneden vil man kunne stemme på hvilket bidrag man synes er best for å avgjøre en vinner. Språkene skal bedømmes i forhold til innovasjon, kompletthet og hvor godt de følger det valgte temaet for den måneden.

Hvis du har fulgt denne bloggen en stund så vet du at det er én oppgave jeg alltid pleier å løse: Å finne summen av alle tall under 1000 som er delelige på 3 eller 5. Og her er løsningen i Ropy:

Ropy er et stack-basert språk. Programmet begynner å kjøre oppe til venstre, og følger så tegnene. Når programmet har flere steder det kan gå – når “tauet” deler seg – velges den første veien i klokkeretningen. Men hvis verdien øverst på stacken er “0″ velger den vei mot klokkeretningen. Med dette kan vi simulere både if og løkker.

Den erfarne leser vil se at Ropy er inspirert av Befunge, som jeg presenterte i julekalenderen 2011.

Ropy-tolkeren er skrevet i Ruby, og er på godt under 200 linjer. Du kan ta en titt på den her, og vil du teste den selv er det bare å laste ned. Du finner også en eksekverbar spesifikasjon som vil hjelpe deg å forstå hvordan språket virker.

Ropy community

Kort tid etter at jeg hadde gjort Ropy tilgjengelig på Github fikk jeg også en pull request – Steffen Hageland, kjent som etse, hadde utvidet språket. Så jeg er tydeligvis ikke alene om å være helt sprø :)

Her er et eksempelprogram skrevet av Steffen:

Jeg trenger din stemme!

Som sagt er Ropy laget som et bidrag til en konkurranse. Og da hadde det selvsagt vært gøy om jeg fikk noen stemmer. Alle kan registrere seg for å være med å avgjøre vinneren (du må ha en github-bruker), og hvis du vil gi meg eller Ropy litt “cred” på den måten blir jeg veldig glad.

Får jeg litt stemmer kan det kanskje inspirere meg til å delta flere ganger også. Kanskje det blir 12 egenproduserte programmeirngsspråk å presentere på bloggen i år?! I januar skal det konkurreres om å lage et språk som fokuserer på automatisert testing. Ideer mottas med takk!

De viktigste lenkene

• Ropy på Github
• PLT Games desember 2012.
• Fyren bak PLT Games heter Peter McKenna.

Noen utvalgte bidrag fra PLT Games du kan ta en titt på:

• Colossal – som gjør programmering om til et tekstbasert adventure-spill.
• nb – utfører programmer gjennom å simulere planet-baner i verdensrommet.
• Turtle Graphics – Klassisk Turtle, turing tar-pit style. Test ut her!
• turipong – utfører programmer ved å simulere en pong-ball som spretter fra vegg til vegg.
• Hugo – et språk som stort sett består av GOTO-statements, og som har en veldig morsom README.
• Seeker – programmene er node-grafer.
• wc3pl – et språk inspirert av Warcraft III
• cyprus – “modeled as chemical reactions happening within protocellular constructions, producing new chemicals”
• Ape – et interessant, minimalistisk språk implementert i noen få linjer F# av en Microsoft-ansatt språk-nerd.

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.

Funksjonell programmering og hva det kan gjøre for deg.

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å.

Hva det er.

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.

Så hvorfor?

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?

Sjekket evalueringsrekkefølge.

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.

Høyere rangs funksjoner.

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.

Matematisk og elegant

(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.

Functor

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

`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.

Monad

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 ++ "!")))

Poenget

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å.

Et eksempel: Allegro, bruk av fantomtyper til å holde orden på kontekst i en spesialisert monade.

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.

Annet

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.

Lær deg Haskell!