F#

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#).

Etter at jeg hadde målt ytelsen på litt F#-kode, og blitt overrasket over resultatene, oppfordret Einar W. Høst meg til å ta en titt på IL-koden. Jeg har nå sjekket den genererte koden ved hjelp av JustDecompile, og her viser jeg frem et par av de tingene jeg fant ut.

Har du ikke fått med deg disse ytelsesmålingene jeg gjorde så kan du først lese postene Litt F#-kode for å måle kjøretid og Sammenligne kjøretider mellom F# og C#.

Rekursjon

En av oppdagelsene jeg gjorde da jeg målte kjøretid var at den raskeste måten å løse Euler1-oppgaven i F# på var å bruke en rekursiv algoritme. Dette var like raskt som en enkel for-løkke i C# (men bare når jeg bygget i RELEASE-modus).

Den rekursive funksjonen jeg testet var:

let rec inner acc n =
    match n with
    | 1000001L -> acc
    | n when n % 3L = 0L -> inner (acc + n) (n + 1L)
    | n when n % 5L = 0L -> inner (acc + n) (n + 1L)
    | _                  -> inner  acc      (n + 1L)

I RELEASE-modus ble dette kompilert ned til en statisk metode. Dissassemblet til C# ser den slik ut:

internal static long inner@82(long acc, long n)
{
    while (n != 1000001L)
    {
        if (n % 3L != 0)
        {
            if (n % 5L != 0)
            {
                n = n + 1L;
                acc = acc;
            }
            else
            {
                n = n + 1L;
                acc = acc + n;
            }
        }
        else
        {
            n = n + 1L;
            acc = acc + n;
        }
    }
    return acc;
}

Den rekursive funksjonen er altså redusert/optimalisert til en enkel while-løkke. Da er det ikke spesielt overraskende at den var så rask.

Når den samme koden var kompilert i DEBUG-modus ble det laget en egen klasse for den rekursive funksjonen. Og funksjonskallet ble utført via en eller annen hjelpefunksjon. Algoritmen var blitt redusert til en while-løkke, men den opprettet en rekke temporære verdier som er optimalisert bort i RELEASE-versjonen.

Mutasjoner

Jeg målte en annen løsning på oppgaven som bruke en for-løkke og en muterbar variabel (en variabel som kan endre verdi). Dette så slik ut:

let mutable result = 0L
for i in 1L..1000000L do
    if i % 3L = 0L || i % 5L = 0L
    then result <- result + i

Denne algoritmen brukte mye lengre tid enn den rekursive løsningen. Men hvorfor? Er mutasjoner veldig tidkrevende i F#?

Igjen tok jeg en titt på koden som ble produsert, og oversatt til C# så den slik ut:

long i;
bool flag;
long result = 0L;
IEnumerable<long> nums = Operators.OperatorIntrinsics
                                .RangeInt64(1L, 1L, 1000000L);
IEnumerator<long> enumerator = nums.GetEnumerator();
try
{
    while (enumerator.MoveNext())
    {
        i = enumerator.Current;
        if (i % 3L != 0)
        {
            flag = i % 5L == 0L;
        }
        else
        {
            flag = true;
        }
        if (flag)
        {
            result = result + i;
        }
    }
}
finally
{
    IDisposable disposable = enumerator as IDisposable;
    if (disposable != null)
    {
        disposable.Dispose();
    }
}

Her ser vi at varibelen som muteres – result – er en helt vanlig long, og det er ingen spesiell kode knyttet til mutasjoner. Forskjellen mellom immutable og mutable er altså noe som finnes i F#, men som forsvinner når koden kompileres ned til IL-kode.

Det som tar det meste av tiden her må være RangeInt64 – sansynligvis det at vi må gjøre ett funksjonskall og en property-aksessering mot enumeratoren til rangen for hver iterasjon.

Dette er en oppfølger til blogposten Litt F#-kode for å måle kjøretid, hvor jeg blant annet målte tiden på ulike løsninger på Euler1-problemet. Det kom som en stor overraskelse at den rekursive varianten var såpass mye raskere enn å bruke løkker og muterbare variabler.

Spørsmålet jeg da stod igjen med var hvor rask den rekursive F#-varianten var i forhold til en løsning i C# – det har jeg nå undersøkt, og det er disse resultatene jeg skal presentere her. Og mot slutten kommer det en overraskelse!

Et testprogram

Jeg valgte å lage et testprogram i C#. Programmet inneholder tre ulike varianter av Euler1: En som bruker en for-løkke, en som bruker Linq, og en crazy variant som bruker GOTO. I Main-metoden kjører jeg disse tre samt de fire orginale variantene fra F#-bloggposten.

public class Program
{
    public static void CSharpTest1()
    {
        long result = 0;
        for (int i = 0; i < 1000000; i++)
            if (i % 3 == 0 || i % 5 == 0)
                result += i;
        Console.WriteLine("\nResult by for loop (C#): "
            + result);
    }
    public static void CSharpTest2()
    {
        Console.WriteLine("\nResult by Enumerable (C#): "
            + Enumerable.Range(1, 1000000)
                .Where(n => n % 3 == 0 || n % 5 == 0)
                .Select(Convert.ToInt64)
                .Sum());
    }

    public static void CSharpTest3()
    {
        int i = 0;
        long result = 0;
    Loop:
        if (++i > 1000000)
            goto End;
        if (i % 3 == 0 || i % 5 == 0)
            result += i;
        goto Loop;
    End:
        Console.WriteLine("\nResult by goto (C#): "
            + result);
    }

    static void Main(string[] args)
    {
        Benchmark.Measure("C# for loop ",
                          Program.CSharpTest1);
        Benchmark.Measure("C# sequence ",
                          Program.CSharpTest2);
        Benchmark.Measure("C# goto     ",
                          Program.CSharpTest3);
        Benchmark.Measure("F# mutable  ",
                          MyFSharpProject.Program.test1);
        Benchmark.Measure("F# sequence ",
                          MyFSharpProject.Program.test2);
        Benchmark.Measure("F# ref cell ",
                          MyFSharpProject.Program.test3);
        Benchmark.Measure("F# recursion",
                          MyFSharpProject.Program.test4);

        Console.ReadLine();
    }
}

Resultatet

Og nå er du vel spent? Kjøringen av dette testprogrammet gav følgende output, presentert som en graf:

Resultatet er nedslående. Det er forsåvidt greit nok – og ikke uventet – at en rekursiv løsning er treigere enn en for-løkke i C#, selv om F# har tail call optimization. Men hvorfor er sekvens-løsningen i F# så veldig mye mere tidkrevende enn sekvens-løsningen i C#?

For sikkerhets skyld forsøkte jeg også å kjøre alle variantene fra en F# executable (man vet jo aldri), men det gav akkurat det samme resultatet.

Og det var da det slo meg: Jeg kompilerer testene mine i DEBUG modus! Kan det hende kjøretiden vil ble bedre i RELEASE? Jeg er ikke vandt til at det har så mye å si i C#, men kanskje det er anderledes i F#?

RELEASE-modus

Så jeg endret prosjektene til å kompilere i RELEASE-modus, og forsøkte C#-testprogrammet på nytt. Ingen merkbar endring!

Ok – hva om jeg tester fra F# igjen da? Og da ble resultatet anderledes!

I RELEASE-modus på F# runtime ble plutselig den rekursive algoritmen nøyaktig like rask som for-løkken i C#. Kompilatoren har altså sansynligvis vært i stand til å transformere rekursjonen til mer eller mindre den samme IL-koden som for-løkken. De andre variantene ble også betydelig raskere, selv om de fortsatt er et stykke fra den optimale løsningen.

Så det er på tide med en Note To Self: Mål alltid performance i RELEASE. Kompileringsmodus har mye å si for optimalisering av F#-kode.

I forrige blogpost (Telle ord-forekomster med F#) brukte jeg en funksjon som het benchmark til å måle hvor lang tid det tok å kjøre programet mitt. Nå vil jeg “avsløre” hva som skjuler seg bak denne funksjonen.

Da jeg eksperimenterte med ulike algoritmer i F# for å prosessere større datamengder hadde jeg behov for å enkelt kunne måle og sammenligne kjøretider på ulike funksjoner. Dette behovet har jeg hatt før, og i 2010 førte det til at jeg lagde biblioteket QuickBencher (tilgjengelig på CodePlex). Bibloteket var kraftig inspirert av tilsvarende funksjonalitet som er å finne i Ruby.

Jeg kunne selvfølgelig ha brukt QuickBencher fra F# også. Men det jeg i stedet gjorde var å røske ut den sentrale innmaten fra bibloteket, og kode det om til et par hendige F#-funksjoner. Her følger en gjennomgang av koden.

Noen typer som holder på data

Først importerer jeg noen navnerom jeg kommer til å bruke mye:

open System
open System.Diagnostics

Deretter lager jeg min første datatype, som er en record jeg kaller ProcessorTime. Formålet med denne er å holde på informasjon om forbrukt tid. Disse tidene kommer fra en prosess (System.Diagnostics.Process), og jeg inkluderer en statisk metode på typen min for å opprette en ProcessorTime-instans basert på en prosess. Dette ser slik ut:

type ProcessorTimes =
    { User   : TimeSpan
      System : TimeSpan
      Total  : TimeSpan }
    static member get (p : Process) =
        { User   = p.UserProcessorTime
          System = p.PrivilegedProcessorTime
          Total  = p.TotalProcessorTime }

Videre trenger jeg en liten hjelpefunksjon får å få tak i forskjellen mellom to Timespan (i sekunder):

let getDuration start stop =
    let duration : TimeSpan = stop - start
    duration.TotalMilliseconds / 1000.0

Og da kan jeg lage min andre datatype, som heter ProcessorDuration. Denne holder tidsinformasjon fra en prosess for to ulike tidspunkt – et starttidspunkt og et stopptidspunkt. Den har også et felt for å holde på forløpt klokketid. ProcessorDuration representerer rett og slett en benchmark-måling.

I tillegg har jeg overstyrt typens ToString-metode til å gi en printbar representasjon av målingen. Tekstformateringen som er brukt er den samme som du finner både i QuickBencher og i Ruby sin benchmark-funksjonalitet.

type ProcessorDuration =
    { Start     : ProcessorTimes
      Stop      : ProcessorTimes
      ClockTime : int64 }
    override x.ToString () =
        sprintf "%f user, %f system, %f total (%f)"
            (getDuration x.Start.User x.Stop.User)
            (getDuration x.Start.System x.Stop.System)
            (getDuration x.Start.Total x.Stop.Total)
            (float x.ClockTime / 1000.0)

Start og stopp

Funksjonen startBenchmark gjør det du antar at den gjør – den begynner å måle tiden. Men den gjør en ting til: Den oppretter og returnerer en lexical closure (altså en funksjon som har referanser til frie variabler fra det scopet hvor den ble opprettet). Denne closuren skal så brukes til å stoppe målingen, og den vil returnere resultatet i form av en ProcessorDuration-instans.

Slik er funksjonen implementert:

let startBenchmark ()=
    let proc = Process.GetCurrentProcess()
    let startTimes = ProcessorTimes.get proc
    let stopwatch = Stopwatch.StartNew()
    (fun () ->
        stopwatch.Stop()
        { Start = startTimes
          Stop = ProcessorTimes.get proc
          ClockTime = stopwatch.ElapsedMilliseconds })

Benchmark

Vi har kommet frem til selve rosinen – benchmark-funksjonen som måler forbrukt tid for en vilkårlig funksjon. Ta først en titt på koden, som ser slik ut:

let benchmark label thunk callback =
    let getResult = startBenchmark()
    let temp = thunk()
    callback label (getResult().ToString())
    temp

benchmark har altså tre parametre. Nummer én er en label som skal identifisere akkurat denne målingen. Typen er ikke gitt – det er typisk tenkt at det skal være en streng, men det kan være hva som helst.

Parameter nummer to heter thunk. I funksjonell programmering er thunk enkelt fortalt betegnelsen på en parameterløs closure. Dette er rett og slett funksjonen som skal måles.

Det tredje parameteret er en callback som vil bli evaluert etter at målingen er foretatt. Argumentene til callbacken vil være labelen og resultatet av målingen. Dermed er det altså signaturen til callbacken som avgjør hvilken type label’en må være.

Etter å ha startet en måling, eksekvert thunken, og gitt resultatet til callbacken, vil benchmark returnere resulatet fra thunken. Dette vil gjøre det enklere å snike inn benchmarking uten for mye endringer i eksisterende kode.

Benchmark til konsollet

I 99% av tilfellene ønsker du sansynligvis bare å printe ut målingen til konsollvinduet, så jeg lagde en enklere versjon av benchmark for akkurat det. Den er selvsagt enkel, men jeg tar den med for kompletthets skyld:

let benchmarkPrintn label thunk =
    benchmark label thunk (printfn "%s: %s")

En interessant demonstrasjon

For å vise hvordan benchmark virker vil jeg løse Project Euler-oppgaven nummer 1, en gjenganger på denne bloggen. Jeg skal finne summer av alle multipler av 3 og 5. Men denne gangen inkluderer jeg multipler helt opp til og med 1’000’000 – for det tar såpass lang tid at det blir noe å måle.

Jeg designer fire ulike løsninger på problemet, og er veldig spent på hva målingene vil vise.

let test1 ()=
    let mutable result = 0L
    for i in 1L..1000000L do
        if i % 3L = 0L || i % 5L = 0L
        then result <- result + i
    printfn "\nResult by for loop and mutation: %s"
            (string result)

let test2 ()=
    {1L..1000000L}
    |> Seq.filter (fun x -> x % 3L = 0L || x % 5L = 0L)
    |> Seq.fold (fun acc x -> acc + x) 0L
    |> string
    |> printfn "\nResult by range, filter and fold: %s"  

let test3 ()=
    let result = ref 0L
    {1L..1000000L}
    |> Seq.iter (fun x -> if x % 3L = 0L || x % 5L = 0L
                          then result := !result + x)
    printfn "\nResult by iter and reference cell: %s"
            (string !result)

let test4 ()=
    let rec inner acc n =
        match n with
        | 1000001L -> acc
        | n when n % 3L = 0L -> inner (acc + n) (n + 1L)
        | n when n % 5L = 0L -> inner (acc + n) (n + 1L)
        | _                  -> inner  acc      (n + 1L)
    printfn "\nResult by recursion: %s"
            (string (inner 0L 1L))

Når jeg så benchmarker de fire testene…

do
    benchmarkPrintn "For and mutation" test1
    benchmarkPrintn "Range, filter, fold" test2
    benchmarkPrintn "Iter and referece cell" test3
    benchmarkPrintn "Recursion" test4

…får jeg følgende output:

Result by for loop and mutation: 233334166668
For and mutation: 0.249602 user, 0.000000 system, 0.249602 total (0.250000)

Result by range, filter and fold: 233334166668
Range, filter, fold: 0.405603 user, 0.000000 system, 0.405603 total (0.417000)

Result by iter and reference cell: 233334166668
Iter and referece cell: 0.265202 user, 0.000000 system, 0.265202 total (0.260000)

Result by recursion: 233334166668
Recursion: 0.031200 user, 0.000000 system, 0.031200 total (0.033000)

At sekvensoperasjoner som filter og fold (test2) gir svakere kjøretid enn for-løkker og mutering av data (test1 og test3) er skuffende men ikke overraskende i et språk som F#. Men resultatet fra test4 veltet meg nesten av stolen! Rundt 85% reduksjon i kjøretid sammenlignet med forløkke-varianten ved bruk av rekursjon var totalt uventet, og viser at F# er blodtrimmet og optimalisert for algoritmer som bruker halerekursjon.

Til slutt

Hvis ytelse er viktig for deg så er det viktig å faktisk måle hvor lang tid ting tar. Å anta er skummelt, og å endre/optimalisere kode uten å holde track på kjøretid er ikke å anbefale. Da trenger du verktøy som det jeg har laget og vist frem i denne bloggposten, som er enkle å bruke, og som gjør én ting og gjør den godt.

I dagens blogpost går jeg gjennom litt F#-kode jeg skrev for en konkret oppgave på jobben. Oppgaven ble først løst i Ruby, men jeg trengte bedre ytelse, og kodet det derfor etterpå i F#. Er du en F#-nybegynner kan det godt tenkes du kan plukke med deg flere tips her. Jeg vil forsøke å trekke frem noen av de mer avanserte elementene i koden.

Oppgaven

Hin dagen lagde jeg et lite script for å telle opp antall forekomster av ord i en tekstfil – altså gruppere resultatet på hvert ord i filen (“bil” forekom 17 ganger, “båt” forekom 5 ganger osv.). Dette ville jeg gjøre for å kunne lage en ord-sky basert på tekstfilen. Her er for eksempel en ord-sky over de ti siste postene på bloggen min:

Det kan se ut som om jeg er litt selvopptatt :)

Her er en beskrivelse av scriptet:

1. Ta inn stien til en fil med tekst som første argument.
2. Les linje for line, og splitt linjen opp i ord.
3. Fjern punktum, komma, utropstegn eller kolon hvis det er siste tegn i ordet.
4. Se bort fra ordet hvis det er ett av ordene i en svarteliste.
5. Inkrementer en teller for antall forekomster av hvert ord.
6. Etter at alle ordene er registrert med antall, fjern ord som ikke forekomer mer enn X ganger.
7. Skriv ut resultatet til en fil, med ett ord og antallet pr linje.

Resultatfilen kan jeg så bruke som innput til Wordle og få generert en ord-sky. Ganske enkelt egentlig, og jeg laget raskt et script for dette i Ruby. Er du interessert finner du scriptet her.

Trengte bedre ytelse

Som jeg sa innledningsvis ønsket jeg bedre ytelse enn hva Ruby kunne gi meg. Filen jeg trengte å analysere var på over 50 MB og bestod av 500.000 linjer. Den inneholdt ca 518.000 unike ord, og over 6 millioner ord totalt. Jeg jobber jo med SMS, og dette var faktisk en halv million SMS-meldinger som skulle analyseres.

På min superduper-spekkede laptop brukte Ruby-scriptet mitt 88 sekunder på denne filen, og konsumerte 185 MB minne. Dette var med Ruby versjon 1.9.3. Til sammenligning bruker F#-programmet jeg nå skal lage under 16 sekunder på den samme filen (82% reduksjon i kjøretid), og trenger ikke mer enn 50 MB RAM (73% reduksjon).

88 sekunder er en evighet, mens jeg har tolmodighet nok til å vente i 16.

BONUSOPPGAVE TIL LESEREN: Klarer du å skrelle mer tid av algoritmen – enten i Ruby eller F#?

En løsning i F#

I F# må du definere en funksjon før du kan bruke den, så det er naturlig både å kode og å presentere koden bottom up.

Partial Application av infix operator

open System
open System.Collections.Generic

let blacklist = [""; "på"; "og"; "er"; "om"; "fra"; "med"; "i"; "to";
                 "det"; "å"; "ditt"; "til"; "ved"; "fra"; "for"; "av";
                 "en"; "din"; "du"; "at"; "vi"; "har"; "vil"; "nå";
                 "det"; "som"; "dere"; "kan"; "vår"; "så"]

Først importerer jeg et par navnerom (samme som using i C#), og så lager jeg en liste med de ordene jeg ikke ønsker å inkludere i analysen.

Jeg trenger også en liten funksjon for å sjekke om et ord er svartelistet:

let blacklisted (word : string) =
    List.exists ((=) (word.ToLower())) blacklist

Her bruker jeg exists-funksjonen i modulen List. Den tar to argumenter: En funksjon som returnerer true hvis elementet er funnet, og listen man skal lete i. Men funksjonsargumentet her er litt spesielt. Hva betyr ((=) (word.ToLower()))?

Dette er en såkalt partial application, som jeg har snakket om mange ganger før. = er en funksjon som sjekker om to verdier er like. Den brukes normalt infix, det vil si at den plasseres mellom sine to argumenter. Men om vi plasserer den mellom to paranteser blir den omgjort til en normal prefix-funksjon.

Det neste jeg har gjort er å sende ett – og bare ett – argument til funksjonen. Dette blir da omgjort til en ny funksjon som forventer ett argument til. ((=) (word.ToLower())) er dermed en funksjon som sjekker om noe er lik lowercase-versjonen av strengen word. De fre følgende uttrykkene er helt ekvivalente, og returnerer alle true:

((=) ("Foo".ToLower())) "foo"

(fun x -> ((=) ("Foo".ToLower())) x) "foo"

(fun x -> x = "Foo".ToLower()) "foo"

Å lage en egen infix operator

Vi går videre. Nå vil jeg lage en funksjon som stripper bort siste tegn fra en streng, men bare hvis det siste tegnet er en av et bestemt sett med tegn. I Ruby var dette gjort på én linje med gsub og et regulært uttrykk, men i F# benytter jeg anledningen til å eksperimentere litt.

(* Removes c from s if c is the last char *)
let (?<<) (s:string) (c:char) =
    let lastIndex = s.Length - 1
    if lastIndex >= 0 && s.LastIndexOf c = lastIndex
    then s.Substring (0, lastIndex)
    else s

Her har jeg laget en funksjon med det litt merkelige navnet ?<<. I tillegg har jeg lagt paranteser rundt, og slik blir det en operator på lik linje med pluss, minus, gange og deling.

Det ser rart ut, men den er elegant i bruk:

let stripPunctuation (word : string) =
    word ?<< '.'
         ?<< ','
         ?<< '!'
         ?<< ':'

La oss si at word inneholder strengern "foo!". Funksjonen ?<< kalles da først med argumentene "foo!" og '.', og resultatet er "foo!" (ingen endring altså). Dette resultatet blir nå første argument til den neste ?<<-funksjonen, som har ',' som andre argument. Og slik fortsetter det. Den tredje ?<< kalles med "foo!" og '!', og returnerer da bare "foo".

Denne teknikken kalles gjerne pipelining.

Å jobbe med en Dictionary

I dette programmet vil jeg bruke en generisk Dictionary<Key, Value>, slik som mange av oss er vandt til fra C#. Koden som følger er ikke spesielt funksjonell, fordi jeg baserer meg på å “mutere” (dvs. endre) dataene i dictionarien direkte. Jeg har likevel valgt å gjøre det fordi jeg jo “oversatte” et Ruby-script som gjorde det på denne måten, og fordi det vil være minst like raskt som en mere funksjonell løsning som ikke muterer data.

Først definerer jeg en ny type. Dette gjør jeg egentlig kun for å være litt eksplisit i koden, og slippe å måtte skrive Dictionary<string, int> fullt ut diverse steder.

type WordMap = Dictionary<string, int>

Jeg lager så en hjelpefunksjon som inkrementerer telleren for et bestemt ord, eller setter verdien 1 om ordet ikke finnes i dictionarien m fra før:

let increment (m : WordMap) word =
    if m.ContainsKey word
    then m.[word] <- m.[word] + 1
    else m.[word] <- 1

Når man muterer en variabel i F# bruker man ikke = slik man gjør i typiske imperative språk. I stedet bruker man <-.

let countWord acc word =
    if not (blacklisted word)
    then increment acc word

countWord er en funksjon som teller et ord fra filen jeg analyserer, men kun hvis ordet ikke er svartelistet. acc er en WordMap, men jeg behøver ikke fortelle F# det (det kan jo ikke være noe annet).

På tide å telle ordene

Nå har vi kommet til selve funksjonen som parser en fil og teller opp ordene i den – og her bruker vi alt vi har laget sålangt. Dette er den delen av programmet som konsumerer så og si all kjøretiden.

let parseWords fileName =
    let accumulator = new WordMap()
    let counter = countWord accumulator
    use file = IO.File.OpenText fileName
    while not file.EndOfStream do
        let words = file.ReadLine().Split [|' '|]
                    |> Array.map stripPunctuation
        Array.iter counter words
    accumulator

Når jeg oppretter variabelen counter så bruker jeg partial application igjen – du husker kanskje at countWord er en funksjon som tar to argumenter, men her gir jeg bare ett.

Legg også merke til nøkkelordet use som jeg bruker når jeg åpner filen. Dette er det sammen som using i C#, og file vil bli lukket/disposed før variabelen går ut av scope.

Filtrere bort skjeldne ord

Jeg ønsker også å fjerne ord som ikke gjentas mer enn X ganger i input-filen. Jeg har eksperimentert litt, og funnet at X = 1000 fungerer bra for de filene jeg jobber med, så jeg hardkoder likegreit denne verdien.

let trimRareWords pairsWithIntValue =
    Seq.filter (fun (KeyValue(_, count)) -> count > 1000)
               pairsWithIntValue

Argumentet til trimRareWords kommer til å være en WordMap, altså en Dictionary<string, int>. Og det kan man også se på som en sekvens med KeyValue<string, int>. Derfor kan jeg bruke Seq.filter til å luke bort ord. I den anonyme funksjonen jeg sender til filter bruker jeg pattern matching til å plukke ut antallet forekomster for et ord.

Skrive ut i Wordle-format

For å produsere filen på det formatet jeg ønsker trenger jeg to funksjoner til. Den første tar et ord med tilhørende antall og lager en tekststreng som Wordle vil forstå:

let wordleLine (KeyValue(word, count)) =
    sprintf "%s:%i" word count

Så trenger jeg også en funksjon som kan ta en sekvens av slike strenger og skrive dem til en fil:

let linesToFile fileName ls =
    IO.File.WriteAllLines(fileName, seq ls)

Main

Da gjenstår det bare å sy det hele sammen. Jeg må ta imot input-filnavnet (argument til programmet) og sette opp en sekvens med funksjoner som kan ta imot dette og produsere Wordle-filen.

For å måle og rapportere hvor lang tid dette tar har jeg brukt en funksjon jeg har kalt benchmark. Denne vil jeg presentere i en blogpost senere, men den tar i alle fall to argumenter: En streng som vil bli brukt som en label ved rapportering, og en parameterløs funksjon (også kalt en thunk). Den vil eksekvere thunken, måle og printe ut hvor lang tid den tok, og returnere resultatet av thunken – som i dette tilfellet er unit (altså ingen verdens ting).

[<EntryPoint>]
let main argv =
    benchmark "Elapsed"
              (fun () -> Seq.head argv
                      |> parseWords
                      |> trimRareWords
                      |> Seq.sortBy (fun (KeyValue(_, v)) -> v)
                      |> Seq.map wordleLine
                      |> linesToFile "out2.txt")
    0 // return an integer exit code

Og da var vi ferdige! Jeg håper du lærte noe. Og hvis du tror du kan lære meg noe, så vil jeg gjerne høre det – forslag til strukturelle forbedringer, eller ting som vil redusere kjøretiden mottas med takk!

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.

Jeg fortsetter å leke meg med F# – for å trene og lære. I dag vil jeg vise hvor enkelt det er å sende en SMS-melding fra F# ved å bruke PSWinCom’s SMS API.

Alt jeg trenger å gjøre for å bruke API’et er å poste litt XML over http(s). XML’en skal se slik ut:

<?xml version="1.0"?>
<SESSION>
    <CLIENT>gatewaybruker</CLIENT>
    <PW>gatewaypassord</PW>
    <MSGLST>
        <MSG>
            <ID>1</ID>
            <SND>avsender</SND>
            <RCV>4799999999</RCV>
            <TEXT>meldingstekst</TEXT>
        </MSG>
    </MSGLST>
</SESSION>

Hjelpefunksjon for XML

Som sagt skal jeg bygge opp litt XML. Biblotekene i .NET-rammeverket har selvfølgelig klasser for å gjøre dette, men jeg holder det enkelt og lager i stedet en liten hjelpemetode jeg kaller tag:

let tag tag content =
    sprintf "<%s>%s</%s>" tag content tag

tag tar to argumenter (hvor dene ene faktisk også heter tag), og returnerer en XML-streng. Denne funksjonen blir nesten som en liten mini-DSL for å bygge XML-dokumenter.

Formatere SMS XML’en

Jeg splitter opp konstruksjonen av XML-dokumentet i to funksjoner: En som formaterer en enkelt melding, og en som tar en liste med meldinger og formaterer det komplette dokumentet.

Her er den første:

let makeSms id sender receiver message =
    tag "MSG" (
        (tag "ID" id) +
        (tag "SND" sender) +
        (tag "RCV" receiver) +
        (tag "TEXT" message))

Og her følger den andre:

let makeRequest user password messages =
    """<?xml version="1.0"?>""" +
    tag "SESSION" (
        (tag "CLIENT" user) +
        (tag "PW" password) +
        (tag "MSGLST" <| String.concat "" messages))

Hvis jeg nå vil lage et dokument for å se at det ser riktig ut kan jeg for eksempel gjøre følgende:

let test = makeRequest
            "tormar" "secretpassword"
            [makeSms "1" "TMAN" "4799999999"
                     "This is a test from FSharp"]

test inneholder nå XML’en.

Sende XML over HTTP

Å gjøre en HTTP POST fra .NET er også ganske enkelt. Til det bruker jeg en System.Net.WebClient. Da får jeg illustrert et par nyttige ting som hvordan man oppretter og bruker .NET-objekter i F#, og hvordan man sørger for at objekter som krever det blir disposet.

La meg først importere System.Net, og lage en variabel som holder på adressen til SMS gateway’en:

open System.Net

let gatewayUrl = "http://gw2-fro.pswin.com:81/"

Deretter lager jeg funksjonen postXml, som gjør det navnet sier at den gjør:

let postXml url xml =
    using (new WebClient()) ( fun client ->
        client.BaseAddress <- url
        client.Headers.Add("Content-Type", "application/xml")
        client.UploadString("/", xml) )

Legg merke til at using tar en anonym funksjon som siste argument. Denne får inn objektet (client) og gjør selve sendingen. using vil så sørge for at Dispose() blir kalt når den anonyme funksjonen har gjort sitt.

Send SMS’en

Jeg kan nå sende SMS’en og ta vare på XML-responsen ved å gjøre følgende kall:

let result = postXml gatewayUrl test

Og det var det hele! Så enkelt kan det være å sende SMS fra F#-kode.

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!

Jonas Follesø (@follesoe) er en velkjent utvikler i .NET-miljøet. Han har forelest på blant annet TechEd, REMIX, MSDN Live, JavaZone, Smidig, ROOTS og NDC, og kan smykke seg med titler som Microsoft Most Valued Professional, Microsoft Regional Director, MSDN Guru og MSDN Honor Avard. Han har også mye erfaring fra mobilutvikling – både for Windows Phone og for iPhone via MonoTouch.

Jonas kaller seg forsker, og dykker derfor ned i mye forskjellig. I dag blogger han om F#.

Hvem er du?
En som er lidenskapelig opptatt av programmering.

Hva er jobben din?
Scientist i BEKK – noe som innebærer å holde selskapet oppdatert på faglige trender og bidra til det Norske fagmiljøet, i tillegg til å være utvikler/arkitekt i prosjekter.

Hva kan du?
Har jobbet med .NET-plattformen siden v1.0 var i beta. Elsker å lære programmeringsspråk – særlig funksjonelle. Glad i mobilutvikling – både på iOS og Windows Phone.

Hva liker du best med yrket ditt?
Å skape noe nytt og spennende fra enkle bestanddeler. Den store variasjonen, både innen teknologi og domene – og ikke minst at jeg får betalt for å jobbe med hobbyen min; programmering.

Utforskende programmering med F# Type Providers

F# er et open source, funksjonelt først, statisk typet programmeringsspråk fra Micosoft. Språket er tilgjengelig både for Microsoft .NET og Mono. Versjon 3.0 ble lansert sammen med Visual Studio 2012 tidligere i høst.

F# er et utrolig spennende språk, som kanskje ikke har fått den oppmerksomheten det fortjener. I denne bloggposten vil jeg vise hvordan man kan gjøre utforskende programmering mot strukturerte data ved hjelp av F# 3.0 Type Providers. Forhåpentligvis kan dette være med på å inspirere deg til å ta en nærmere titt på språket og noen av de spennende mulighetene som finnes i F# 3.0.

Utforskende programmering er et begrep som eksempelvis brukes om det å utforske hvordan en algoritme skal implementeres, hvilke datastrukturer man har behov for, eller hvordan man skal kommunisere med et eksternt system eller datakilde. Noen språk har bedre støtte for denne typen programmering enn andre. Dynamiske språk som Ruby, Python og Clojure er alle kjent for å ha en REPL (en kommandolinje interpreter) som kan brukes til interaktiv programmering, dvs man kan skrive inn kode og få den eksekvert umiddelbart. Man kan så definere nye klasser, funksjoner eller metoder, og så teste disse direkte fra REPL-vinduet.

C# og VB.NET, som er hovedspråkene på .NET plattformen, har ikke god støtte for denne typen programmering. F# derimot har utmerket støtte for interaktiv programmering. I F# Interactive kan man skrive kode og få denne eksekvert umiddelbart. Man kan også skrive kode i Visual Studio, og deretter markere de kodelinjene man vil ha eksekvert via verktøyet F# Interactive. På denne måten kan man gradvis utforske et problemområde, eksekvere deler av koden, og så teste dette ut. F# kan også brukes som et script-språk, dvs man kan distribuere skript-filer som ikke må kompileres på forhånd.

Ett av de viktigste fokusområdene for F#-teamet under utviklingen av F# 3.0 var å gjøre den enorme mengden av strukturerte data vi omgir oss med tilgjengelig som en integrert del av F#-utviklingsmiljøet. Tradisjonelt har det vært en utfordring å integrere eksterne data i statisk typede programmeringsspråk siden de som regel ikke deler noen felles representasjon av dataene. Måten dette har vært løst på har i hovedsak vært via kodegenerering. Hvis du ønsker å konsumere en SOAP-tjeneste fra Java eller C# er må du som regel bruke et eksternt verktøy som leser WSDL-filen og generer C#- eller Java-klasser med samme struktur som typene eksponert av tjenesten, og en klientklasse med metoder for hver av operasjonene du kan kalle på tjenesten. Et annet vanlig scenario er å konsumere data fra en relasjonsdatabase. Her finnes det verktøy som kan lese databasestrukturen og generere klasser som har samme form som tabellene i databasen, med metoder som genererer SQL-spørringer.

Ulempen med kodegenerering er at du får flere store, og gjerne lite lesbare, kodefiler i kodebasen din.  Disse må sjekkes inn i versjonskontrollsystemet og bygges som en del av løsningen din. Dersom webtjenesten får en ny operasjon eller en tabell i databasen skulle endre navn får du ikke kompileringsfeil før du eventuelt regenererer koden for å oppdatere integrasjonen med disse kildene. Kodegenerering er også en forholdsvis tung prosess som hindrer utforskende programmering.

Type Providers

F# teamet har introdusert en ny og innovativ løsning på denne problemstillingen: Type Providers.

En Type Provider i er i hovedsak tre ting:

• En design-time komponent som kan lage nye typer ved behov
• En kompilator- og IDE-utvidelse
• Et statisk motstykke til dynamiske programmeringsspråk og teknikker

I eksempelet nedenfor bruker jeg en WsdlService Type Provider for å konsumere en tjeneste for å konvertere temperaturer mellom Celsius og Fahrenheit. Det viktige her er at jeg ikke har generert masse kode for å kalle tjenesten. Jeg bruker kun et F#-bibliotek. Idet jeg bruker WsdlService-typen går Type Provideren ut på nettet, leser WSDL-en til tjenesten og lager en ny F#-type med de metodene jeg trenger for å kalle den. Dette skjer umiddelbart, og jeg får full IntelliSense/statement completion som forteller meg hvilke metoder som er tilgjengelig på tjenesten. Dersom en av operasjonene på tjenesten skulle bytte navn vil jeg få en kompileringsfeil. Type Provideren kjører altså som et del av F# sin type-checker/kompilator (som også Visual Studio bruker for å gi meg IntelliSense). Det blir ikke generert F#-kildefiler eller annen kode som må legges til. Jeg har heller ingen prosjektfil – kun et enkelt F# skript. Type Providere kan sees på som en form for “compile time meta programming”.

F# 3.0 kommer med flere innebygde Type Providere. I det neste eksempelet konsumerer jeg OData-tjenesten som eksponerer Netflix sin videokatalog. Her ønsker jeg å lage en liste over de 5 beste julefilmene gitt ut siden år 2000. Igjen slipper jeg bruke et eget verktøy for å generere masse kode for å representere datatypene til Netflix. Så snart jeg har tar i bruk ODataService Type Provideren går den ut på nettet, leser metadataen OData tjenesten og gir meg de nødvendige typene for å kalle tjenesten. Jeg får full IntelliSense når jeg gjør LINQ-spørringer og får også forslag til hvilke felter som er tilgjengelige når jeg skal filtrere hvilke filmer jeg er interessert i.

F# 3.0 kommer med Type Providere for WSDL-tjenester, OData-tjenester og SQL-databaser. Viktigst av alt er at Type Provider-mekanismen er utvidbar. Det finnes allerede en rekke tredjeparts Type Providere tilgjengelig på NuGet.  Det finnes også Type Providere for datakilder som Excel, Freebase, Xaml, Regex og en rekke andre.

Freebase er en online, Creative Commons-lisensiert grafdatabase med mer enn 23 millioner entiteter,  og flere hundre millioner fakta om disse entitetene. Dataene er strukturerte og det finnes definerte skjema for alt fra grunnstoffene og kjemiske sammensetninger, til skuespillere, fotballag, bøker og TV-serier. Freebase er et av de største eksemplene på bruk av semantisk web. Google, som eier Freebase, har blant annet integrert informasjon fra Freebase inn i sine søkeresultater.

Siden antallet tilgjengelige typer (skjema) er så stort, og i konstant vekst, ville det vært upraktisk å brukt tradisjonell kodegenerering til å lage et statisk typet API. Freebase baserer seg på JSON for datautveksling, noe de og påpeker i dokumentasjonen for det offisielle Java API-et:

Unfortunately, Java’s strongly typed nature and unlike other languages like Javascript and Python where it belongs as a first class citizen, makes it very unnatural to use JSON as a data format with the API.

This is why this library is built around the concept of a telescopic JSON API that is designed to make it easier not only to parse and serialize data in JSON formats, but also to construct, modify and manipulate JSON data directly inside code with as little syntax overhead as possible

I praksis mister du statisk typing når du benytter deg av Java (eller C#) API-et til Freebase. I F# derimot kan du utforske Freebase og fortsatt beholde statisk typing. Dersom nye skjema blir lagt til vil disse automatisk bli tilgjengelige fra F#. Eksempelet nedenfor viser hvordan det ser ut når man utforsker Freebase for å skrive ut grunnstoffene sortert etter vekt.

Jeg håper denne introduksjonen til utforskende programmering ved hjelp av F# Type Providers har vært spennende. Type Providers åpner for en rekke nye muligheter. Selv om dataaksess er det F#-teamet har fokusert på så er jeg sikker på at man vil se andre spennende bruksområder nå som vi har muligheten til å koble oss på kompilatoren og selv generere nye typer som umiddelbart blir tilgjengelige i utviklingsmiljøet. F# har mange andre spennende egenskaper – og om du har lyst til en introduksjon til språket vil jeg anbefale Try F# som lar deg programmere F# i nettleseren.

Jeg vil også oppfordre alle C#- og .NET-utviklere til å se nærmere på F#. Har du Visual Studio 2012 har du allerede F# tilgjengelig. Selv om du ikke skriver selve produksjonskoden din i F# er det ingenting i veien for å åpne F# Interactive og gjøre litt utforskende programmering på CLR-en. Det er og viktig å poengetere at F# ikke er begrenset til utforskende programmering. Du kan lage vanlige prosjekter i, og F# er også designet for å kunne integreres sømløst med .NET-kode skrevet i andre språk. Det er for eksempel ingen ting i veien for å skrive dataaksesskoden for din neste applikasjon i F#. Da kan du bruke Type Providers og så konsumere denne koden fra en C# front-end. F# er også tilgjengelig for en rekke plattformer, og du kan skrive alt fra webapps til Windows Phone- og Windows 8-applikasjoner i F#. Det ryktes også at neste versjon av MonoTouch vil få støtte for F# i tillegg til C#, for utvikling av iOS-applikasjoner.

Dersom du har lyst å lære mer om Type Providers vil jeg anbefale å lese  Microsoft Research sin publikasjon “F#3.0 – Strongly-Typed Language Support for Internet-Scale Information Sources”.

Om du har lyst å lære mer om funksjonell programmering, og få en introduksjon til språkene Clojure, Scala, Erlang, JavaScript og F# vil jeg oppfordre deg til å delta på «Functional Programming Day» i Oslo 17. desember.

PS: Jonas har bursdag i dag, så gratuler ham med dagen!