F#


tirsdag 6. desember 2011 F# Julekalender Polyglot

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.

fsharp

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!


comments powered by Disqus