I del 1 og del 2 har du sett meg implementere Template Method pattern i C# – først i en tradisjonell, objektorientert variant, og så i en mere fleksibel variant inspirert av funksjonell programmering. Nå er det på tide å se hvordan det samme kan gjøre kun med funksjoner. Det er på tide å finne frem F#.

Først trenger vi selve templaten, eller algoritme-skjelettet om du vil. processLog er en funksjon som har fire andre funksjoner som parametre, og bruker disse til å prosessere loggfilen. En slik funksjon kalles en høyereordens funksjon.

10 let processLog init read processLine cleanup =
11     init()
12     for line in read() do
13         processLine line
14     cleanup()

Deretter oppretter jeg et par funksjoner for å finne og rapportere errors i loggfiler:

22 let errorInit() = printfn "Errors:"
23 
24 let errorLineProcessor line =
25     let m = Regex("^(\\d{17})\\s(\\w+)\\s(.+)$").Match(line)
26     if m.Success then
27         if m.Groups.Item(2).Value = "ERROR" then
28             printfn "%s: %s"
29                 (m.Groups.Item(1).Value)
30                 (m.Groups.Item(3).Value)

Det neste jeg trenger er FTP-stegene. Nedenfor oppretter jeg en funksjon som tar som innput en URL og returnerer to funksjoner – en for Initialize-steget i algoritmen og en for Cleanup-steget. Disse to funksjonene er lexical closures, fordi de har tilgang til URL-variabelen (mer om dette mange andre steder i bloggen).

33 (* Evaluates to a tuple of two closures *)
34 let makeFtpSteps url =
35     let setup = fun () -> printfn "Fetching log file from %s" url
36     let teardown = fun () ->
37         printfn "Archiving local log copy..."
38         printfn "Deleting log file %s" url
39     (setup, teardown)

Så kan jeg bruke funksjone jeg nettopp laget til å opprette de to closure’ene:

42 let (ftpFetch, ftpCleanup) =
43     makeFtpSteps "ftp://foobar.com/logs/my.log"

Å komponere funksjoner..

Jeg har nå to forskjellige funksjoner som skal kalles i Initialize-steget i templaten: ftpFetch og errorInit. I del 1 løste jeg dette ved at FTP-initialiseringsmetoden kalte baseklassens Initialize. I del 2 løste jeg det ved å ha en builder-klasse som kunne kombinere flere Action-delegater. Nå befinner jeg meg derimot i et funksjonelt språk, og da er det ingen sak å slå sammen to funksjoner til én:

48 (* Using forward composition operator to compose two functions *)
49 let errorInitWithFtpFetch = ftpFetch >> errorInit

errorInitWithFtpFetch er nå en ny funksjon som først evaluerer ftpFetch og deretter evaluerer errorInit. Om ftpFetch hadde hatt parametre ville den nye funksjonen også hatt det. Om ftpFetch hadde returnert noe, ville dette blitt sendt inn som argumenter til errorInit. Og om errorInit hadde hatt en returverdi så hadde dette vært returverdien til den nye metoden.

På tide å teste programmet

Da gjenstår det bare å mocke lesing av fil:

55 (* Faking it as usual... *)
56 let read() = [
57     "20120125180000000 DEBUG Tick!";
58     "20120125180100000 DEBUG Tick!";
59     "20120125180132112 ERROR Some error occurred";
60     "20120125180133056 ERROR Some other error...";
61     "20120125180200000 DEBUG Tick!"]

… og å kjøre selve programmet ved å kalle processLog-funksjonen med de riktige argumentene:

64 processLog
65     errorInitWithFtpFetch
66     read
67     errorLineProcessor
68     ftpCleanup

Output er identisk med løsningene fra del 1 og del 2.

Konklusjon

Løsningen jeg har kommet opp med her er betydelig enklere enn det du har sett før – her har vi ingen klasser som pakker inn koden og bestemmer hva vi kan og ikke kan gjøre. Løsningen er ekstremt fleksibel, og vil la meg kombinere funksjoner akkurat slik jeg ønsker. Objektene har vist seg å være helt overflødige – dette fordi Template Method i objektorientert design egentlig er et forsøk på å gjøre det samme som higher-order funksjons allerede gjør mye bedre.

Det eneste det kan se ut som om jeg har mistet er det å ha en LogProcessor-instans/objekt som jeg kan sende rundt og eksekvere når jeg måtte ønske. Men det løser vi selvsagt også lett. Å pakke inn et funksjonskall i en ny funksjon uten parametre slik som jeg gjør her kalles thunking:

71 (* Creating a thunk *)
72 let logProcessor() =
73     processLog
74         errorInitWithFtpFetch
75         read
76         errorLineProcessor
77         ftpCleanup
78 
79 (* Evaluating the thunk *)
80 logProcessor()

logProcessor er nå i prinsippet et objekt.

I del 4 vil jeg avslutte serien om Template Method ved å se på hvordan jeg kan bruke multippel arv til å gjøre en objektorientert implementasjon like fleksibel som som den løsningen du nå fikk se.

Har du hørt at programmer som er kodet etter den funksjonelle paradigmen ofte er kortere og er enklere å teste, og gjør det mye enklere å utnytte prosessorkraften på maskinen? Spennende, men hvilket språk skal man bruke da? F# er ett alternativ.

På Universitetet i Edinburg utviklet man tidlig på 70-tallet et programmeringsspråk man kalte ML. Språket støttet både imperativ og funksjonell programmering. F# er en moderne implementasjon av ML, først utviklet av Don Syme ved Microsoft Research for 10 år siden. Nå er språket i versjon 2, mens versjon 3 er i preview. Det er tilgjengelig i Visual Studio, og distribueres som et fullverdig språk på .NET-plattformen.

F# er et sterkt typet språk. Det her såkalte immutable types – data som ikke kan endres – som brukes til funksjonell programmering, men også mutable types som kan brukes til objektorientering. I F# kan man benytte alle biblotekene en som .NET-utvikler er vandt til å ha tilgang til, men måten du koder og tenker på er ganske anderledes.

Eh, hva er denne funksjonelle programmeringen for noe egentlig?

Funksjonell programmering (FP) er når man lager programmer som er som evaluering av matematiske funksjoner, og man forsøker å unngå tilstand og data som kan endres på underveis i programmet. Man legger altså vekt på å evaluere funksjoner, og mindre vekt på endring av variabler.

FP har sine røtter i lambda calculus, en formell beskrivelse av funksjonsdefinisjoner, evaluering av funksjoner, og rekursjon. Et par relaterte blogposter som utdyper betydningen av FP er programmeringsparadigmer – ulike måter å tenke på og hemmeligheten bak funksjonell programmering avslørt.

Litt kode

Jeg vil nå vise en hel rekke ulike løsninger på Euler problem nummer 1 implementert i F#. Selv om jeg har blogget litt om F# tidligere så er jeg helt nybegynner, og her er den første løsningen jeg kom opp med gjennom å google meg frem til funksjoner jeg kunne bruke:

10 let Euler1a =
11     Seq.unfold       (fun x -> Some(x, x+1)) 0
12     |> Seq.takeWhile (fun x -> x < 1000)
13     |> Seq.filter    (fun x -> x % 3 = 0 || x % 5 = 0)
14     |> Seq.fold      (fun x acc -> x + acc) 0
15     |> System.Console.WriteLine

Seq.unfold genererer en uendelig sekvens med tall. Jeg sender så sekvensen gjennom en rekke funksjoner for å begrense, filtrere, summere, og til slutt skrive ut resultatet.

Jeg fant derimot raskt ut at jeg kunne forenkle løsningen. Sekvenser kan lages enklere, og jeg behøver ikke bruke fold for å summere tall.

17 let Euler1b =
18     seq { 0 .. 999 }
19     |> Seq.filter(fun x -> x % 3 = 0 || x % 5 = 0)
20     |> Seq.sum
21     |> System.Console.WriteLine

Faktisk viste det seg også at Seq-bibloteket inneholdt en funksjon som jeg kunne bruke til å filtrere og summere i én operasjon, og da så det til slutt slik ut:

23 let Euler1c =
24     seq { 0..999 }
25     |> Seq.sumBy (fun x -> if x%3=0 || x%5=0 then x else 0)
26     |> System.Console.WriteLine

Men F# egner seg også til å implementere sett-baserte løsninger som dem jeg beskrev i denne bloggposten. I løsningen nedenfor oppretter jeg to sett med multipler av 3 og multipler av 5. Disse finner jeg unionen av, endrer settet til en sekvens, summerer og skriver ut.

28 let Euler1d =
29     (set {0..3..999}, set {0..5..999})
30     ||> Set.union
31     |> Set.toSeq
32     |> Seq.sum
33     |> System.Console.WriteLine

Jeg forsøkte også det andre alternativet av sett-løsninger hvor jeg legger sammen summen av alle 3-multipler og 5-multipler, og trekker fra summer av alle 15-multipler:

35 let Euler1e =
36     (seq {0..3..999} |> Seq.sum) +
37     (seq {0..5..999} |> Seq.sum) -
38     (seq {0..3*5..999} |> Seq.sum)
39     |> System.Console.WriteLine

Den neste løsningen er en rekursiv funksjon som bygger opp en sum basert på pattern matching. Løsningen er inspirert av bowlingkata-algoritmen jeg viste i blogposten Likheter mellom F# og Erlang. Jeg bruker et såkalt match expression med tre ulike muligheter: Hvis n er 1000 skal sum inneholdet svaret, og det returneres. Hvis ikke sjekker jeg om n er delelig på 3 eller 5, og hvis så er tilfelle så legger jeg n til sum, øker n med 1, og kaller funksjonen rekursivt. Hvis tallet ikke er delelig på 3 eller 5 skal det ikke inkluderes, og jeg kjører videre uten å endre sum.

43 let rec Euler1f n sum =
44     match n with
45         | 1000                          -> sum
46         | _ when n % 3 = 0 || n % 5 = 0 -> Euler1f (n+1) (sum+n)
47         | _                             -> Euler1f (n+1) sum
48 
49 System.Console.WriteLine (Euler1f 0 0)

Til slutt har jeg laget en forbedret pattern matching ved å bruke et såkalt active pattern. Denne teknikken brukes for å partisjonere data – i dette tilfelle splitte alle tenkelige tall i to grupper basert på om de er multipler av 3 eller 5 eller om de ikke er det. Selve match-uttrykket blir dermed renere.

56 let (|Multiple|NotMultiple|) n =
57     if n % 3 = 0 || n % 5 = 0 then Multiple else NotMultiple
58 
59 let rec Euler1g n sum =
60     match n with
61         | 1000        -> sum
62         | Multiple    -> Euler1g (n+1) (sum+n)
63         | NotMultiple -> Euler1g (n+1) sum
64 
65 System.Console.WriteLine (Euler1g 0 0)

Hvorfor bruke tid på F#

Jeg vil ikke at du absolutt skal lære deg F#, men jeg mener det er viktig at du lærer deg minst ett språk med fokus på funksjonell programmering. Og om du allerede har .NET-erfaring er F# da et naturlig valg. Er du Java-utvikler er det kanskje mer sansynlig at du vil gå for å lære deg Scala eller Clojure (som forresten begge finnes for .NET også).

Men nå snakker vi altså om F#, som er et modent språk, supportert av Microsoft, og som egner seg godt til praktisk utvikling av forretningsprogramvare. Visual Studio-støtten, og F#-støtten man finner i andre verktøy som f.eks. LinqPad, er også et stort pluss for dem som allerede bruker disse.

Jeg har derimot ikke inntrykk av at F# har fått den utbredelsen man kunne forvente. Det kan være flere grunner til dette, men ett av dem er nok at C# og VB.NET – de mest utbredte språkene på .NET – også har fått brukbar støtte for funksjonell programmering vha. Linq og lambda-uttrykk. F# har derimot endel egenskaper man ikke finner i disse andre språkene, og det er absolutt verdifullt å studere disse.

Hvordan komme igang

Har du Visual Studio 2010 har du allerede F# på maskinen, og det er bare å sette igang. På MSDN finner du all informasjon du behøver om språket og API’ene, samt flere guider, tutorials og videoer. På Visual F# Developer Center finner du siste nytt og community-relatert informasjon. Lykke til!

Jeg hadde meg en tur innom bloggen til Christian Abildsø a.k.a. @mcmuttons i dag, og oppdaget en blogpost han skrev for halvannet år siden om å gjøre bowling kata i F#. Og jeg synes koden han kom opp med var så vakker at jeg nesten bare måtte dele det.

Her bruker Christian patter matching til å beregne poengene for et sett med bowlingkast.

10 module Scorer
11 
12 let rec CalculateFrame rolls frame =
13     match rolls with
14         | _ when frame = 10         -> 0
15         | 10::y::z::rest            -> 10+y+z + CalculateFrame (y::z::rest) (frame+1)
16         | x::y::z::rest when x+y=10 -> 10+z   + CalculateFrame (z::rest)    (frame+1)
17         | x::y::rest                -> x+y    + CalculateFrame rest         (frame+1)
18         | _                         -> 0
19 
20 let CalculateScore rolls =
21     CalculateFrame rolls 0

Dette fikk meg til å se hvor kort avstand det kan være fra F# til et språk jeg selv har jobbet endel med, nemlig Erlang. Jeg har blogget om pattern matching i Erlang tidligere, og her kan du se hvordan Christians algoritme ville sett ut:

10 -module(scorer).
11 -export([calculate_score/1]).
12 
13 calculate_frame(Rolls, Frame) ->
14   case Rolls of
15     _ when Frame == 10        -> 0;
16     [10,Y,Z|Rest]             -> 10+Y+Z + calculate_frame([Y,Z|Rest], Frame+1);
17     [X,Y,Z|Rest] when X+Y==10 -> 10+Z   + calculate_frame([Z|Rest], Frame+1);
18     [X,Y|Rest]                -> X+Y    + calculate_frame(Rest, Frame+1);
19     _                         -> 0
20   end.
21 
22 calculate_score(Rolls) ->
23   calculate_frame(Rolls, 0).

Noen små syntaksforskjeller er det jo, men ellers er det jo det samme. Desverre, får jeg vel nesten si, er det F#-versjonen som har flest estetiske kvaliteter.

Det var det hele. Årets korteste blogpost fra denne kanten? :D

I de programmeringsspråkene vi kaller funksjonelle språk har vi normalt ikke objekter. Det finnes språk som støtter flere paradigmer, men objekter er ikke en del av den funksjonelle. Vi har likevel behov for noe som minner om objekter; en form for entiteter eller typer som har definerte felt, som funkjonene kan jobbe på.

Vi kaller dem algebraiske datatyper, og det finnes mange varianter. De vanligste minner gjerne om structs i C eller lignende språk, og i mange språk (spesielt dynamiske) bruker vi gjerne assosiative arrays på samme måte. Her skal jeg sammenligne om noen av de algebraiske datatypene jeg har møtt i min ferd gjennom den funksjonelle programmeringsverdenen.

records i Erlang

Når vi programmerer i Erlang bruker vi ofte tupler til å holde data som er relatert til hverandre. En tupel er et sett med verdier i en bestemt rekkefølge. Posisjonene har derimot ikke noe navn, og det blir derfor tungvindt og lite lesbart å bruke lange tupler med mange verdier.

For å bøte på dette har Erlang en datatype som heter record. En record er en tupel hvor hver posisjon har et navn, og verdiene kan aksesseres ved hjelp av det navnet. Her er et eksempel på definering av en record-type, opprettelse av “instanser” av typen, og bruk av den:

Run-metoden skriver linjene “Bass, Ed” og “Geffen, David” til konsollet. Bruken av person-recorden er som du ser nesten som om det var et objekt i et OO-språk.

Erlangs record-type har fått mye kritikk. Record er egentlig bare syntaktisk sukker som ble tilført språket ganske sent, og det er tungvindt å bruken den. Som du ser må man spesifisere record-typen (person) hver gang man aksesserer en verdi. Dette er fordi runtime egentlig ikke vet at det er en person – den oppfatter datatypen som en helt vanlig tuple.

StructMap i Clojure

Clojure har noe som ligner veldig på Erlangs record, og her heter det StructMap. Som navnet tilsier er det en slags blanding av en struct og et map (dictionary/hashtable/assosiativt array). Her er eksempelet fra Erlang oversatt til Clojure:

Hovedforskjellen fra Erlang er at man ikke trenger å spesifisere feltnavnene når man oppretter “instanser” av en StructMap. Man trenger heller ikke fortelle hvilken StructMap en verdi er når man skal hente ut felt.

I eksempelet her har jeg definert accessor-funksjoner som henter ut verdiene fra de ulike feltene – dette er en optimaliseringssak, og er ikke nødvendig. (:surname p) vil fungere akkurat som (surname p), men det går litt saktere (ifølge dokumentasjonen).

records i F#

F# (og OCaml etc.) har også en type vi kaller record. I motsetning til Erlang og Clojure har F# ingen dynamisk typing, og du ser derfor at jeg må spesifisere datatypen for hvert felt når jeg deklarerer Person nedenfor. Derimot har F# utmerket type inference, og jeg behøver derfor ikke å spesifisere “Person” hverken når jeg oppretter eller bruker Person-instanser – F# utleder hvilken type det er basert på feltnavnene jeg bruker.

F# har en annen algebraisk datatype som kalles Discriminated Union som man også bør ta en titt på (Haskell har det samme mener jeg). For en mere grunnleggende forståelse av disse typene anbefaler jeg å lese om algebraiske datayper på wikiperia.

Og mm noen skulle sitte på info om tilsvarende typer i Scala, Prolog eller andre språk jeg ikke har nevnt, er det bare å dele i kommentarfeltet.

Det siste året har jeg knyttet intim bekjentskap til bruk av såkalte higher order functions; først da jeg virkelig tok i bruk LINQ og lambda i C# 3.0, deretter da jeg lærte meg Ruby, og til sist nå når jeg lærer meg å bruke språk som Erlang og F# i den funksjonelle paradigmen. Jeg har lært om Lambda calculus, og hva en closure er for noe – ting jeg nå mener alle utviklere burde ha et forhold til.

For å gi deg, kjære leser, et bedre innblikk i noe av dette, vil jeg snakke litt om noen av disse funksjonene av “høyere orden”. Higher order function betyr i bunn og grunn bare en funksjon som tar som innput en annen funskjon som spesifiserer en del av hva den skal utføre.

Filtrer

Filter er en av de mest vanlige, høyere orden funskjonene som brukes på lister eller andre datastrukturer. Gitt en liste og et predikat så brukes filter-funksjonen til å returnere de elementene i listen som tilfredstiller predikatet. Jeg sier “filter” fordi det er det funksjonen heter i de fleste programmeringsspråkene. I C# heter derimot filter-funksjonen for IEnumerable<T> Where, og den kan for eksempel brukes slik:

var aList = new []{1, 2, 3, 5, 8, 13, 21, 33, 54};

var evenNumbers = aList.Where(n => n % 2 == 0);

// array contains: 2, 8, 54

Filter-funksjonen for Enumerations i Ruby heter select (evt. find_all). Her er samme eksempel i Ruby:

Projiser

Den neste av de mest brukte, høyere orden funksjonene er Map. Denne funksjonen tar en liste eller lignende, samt en funksjon for å omforme (“mappe”) elementene i listen til en ny type elementer. Dette kaller vi også en projisering (projection). C#-varianten av map heter Select (og er altså ikke det samme som select i Ruby). Ønsker jeg for eksempel å konvertere listen med tall om til en liste med strenger kan jeg gjøre det slik:

var evenNumbersAsString = evenNumbers.Select(n => n.ToString());

I de fleste andre språk heter funksjonen map, men i Ruby har man også et alias som heter collect.

Aggreger

Filter og map er fine funksjoner som er anvendelige og lette å forstå og å huske på. En som ikke er fullt så mye brukt, blant utviklere innenfor den imperative paradigmen i alle fall, er Fold. For å forvirre oss fremstår også denne funksjonen med ulike navn i de ulike språkene – som for eksempel Reduce, Accumulate, Compress og Inject. Og i .NET heter den Aggregate:

Console.Write(evenNumbersAsString.Aggregate(

    "", (accumulator, next) => accumulator + next + " "));

// prints "2 8 54 "

Ser du hvordan den virker? I motsetning til de andre funksjonene som returnerer lister, så returnerer Aggregate én verdi. En verdi som er bygget opp ved å kalle det spesifiserte lambda-uttrykket for hvert element i listen. Accumulator er både output og input til lamdaen. For det første elementet vil accumulator ha verdien som ble spesifisert som den første parameteren til Aggregate, altså en tom streng. Når funksjonen kalles igjen for det andre elementet vil accumulator ha verdien som ble returnert fra den første. Og så fortsetter det til listen er tom, og accumulator returneres.

Her er nesten samme eksempel i Ruby, hvor fold heter inject (eller reduce om du ønsker å bruke det):

Har du aldri brukt en slik funksjon ser dette sikkert ganske gresk ut. Den er på kanten til å være uleselig, og hvis du jobber i et team som ikke er så godt kjent med fold/aggregate så bør du kanskje være forsiktig med å bruke den. Men jeg lover deg at om du venner deg til denne funksjonen så vil du i mange tilfeller kunne produsere mere kompakt og elegant kode.

Oppsummering i F#

Her er et oppsummerende eksempel i F#. Jeg oppretter en liste, og bruker pipelining til å sende listen gjennom filter, map (projiser) og fold (aggreger), for til slutt å skrive ut den resulterende strengen.

open System

let aList = [1; 2; 3; 5; 8; 13; 21; 33; 54]

aList |> List.filter (fun n -> n % 2 = 0)

      |> List.map    (fun n -> n.ToString())

      |> List.fold   (fun acc n -> acc + n + " ") String.Empty

      |> Console.WriteLine