Erlang

Dette er en tutorial som lærer deg grunnleggende Erlang og noen grunnleggende teknikker fra funksjonell programmering. Formatet er inspirert av boken The Little Schemer (og de andre bøkene i den serien). Vi begynner helt fra scratch, men bygger raskt opp ganske mye kunnskap om språket. Følg nøye med!

Har du ikke peiling på hva Erlang er for noe kan du leste min lille introduksjon som jeg skrev i 2010.

La oss begynne…

X = 2.

X = 3,
Y = X.

X = 4,
Y = 5,
Y = X.

X = 6,
Y = 6,
Y = X.

X = foo.

{epler, bananer, plummer}

GivenName = "Bill",
SurName = "Gates",
Person = {person, GivenName, SurName}.

P = {person, "Steve", "Jobs"},
{person, G, S} = P.

P = {author, "Joe", "Armstrong"},
{person, G, S} = P.

P = {man, "Adam"},
{_, Name} = P,
Name.

[1, 2, 3, 4, 5].

[_, X, _] = [1, 2, 3].

L = [2, 4, 8, 16, 32],
[Head|Tail] = L,
Head.

L = [2, 4, 8, 16, 32],
[Head|Tail] = L,
Tail.

[Head|Tail] = [a].

[Head|Tail] = [].

L = [2, 4, 8, 16, 32],
[_|T] = L,
[_|T2] = T,
[H|_] = T2,
H.

L = [2, 4, 8, 16, 32],
[_, _, H | _] = L,
H.

double(X) -> X + X.

sum([A, B, C]) -> A + B + C.

second([_, X | _]) -> X.

second([_,X|_]) -> X;
second(_)       -> no_second_element. 

S1 = second([1]),
S2 = second([1, 2]).

count([ ])   -> 0;
count([_,T]) -> 1 + count(T).

count(List) -> count(List, 0). 

count([], Acc)    -> Acc;
count([_|T], Acc) -> count(T, Acc + 1). 

F = fun (X) -> X * 3 end,
F(3).

map(_, [])            -> [];
map(Fun, [Head|Tail]) ->
    [Fun(Head) | map(Fun, Tail)]. 

X = map(fun (X) -> X div 2 end,
        [2, 4, 8, 16]).

filter(_, [])    -> [];
filter(F, [H|T]) ->
    case F(H) of
        true -> [H | filter(F, T)];
        false -> filter(F, T)
    end. 

IsEven = fun (X) -> X rem 2 == 0 end.
X = filter(IsEven, [1,2,3,4,5,6]).

filter(F, L) -> filter(F, L, []). 

filter(_, [], Acc)    -> Acc;
filter(F, [H|T], Acc) ->
    case F(H) of
        true -> filter(F, T, [H|Acc]);
        false -> filter(F, T, Acc)
    end. 

IsEven = fun (X) -> X rem 2 == 0 end,
X = filter(IsEven, [1,2,3,4,5,6]).

fold(Acc, _, [])    -> Acc;
fold(Acc, F, [H|T]) -> fold(F(H, Acc), F, T).

fold(0,
     fun (X, Acc) -> X + Acc end,
     [1, 2, 3, 4]).

foo(F, List) ->
    G = fun (X, Acc) ->
            case F(X) of
                true -> [X|Acc];
                false -> Acc
            end
        end,
    fold([], G, List).

bar(F, List) ->
    G = fun (X, Acc) -> [F(X)|Acc] end,
    fold([], G, List).

is_man({man, _, _}) -> true;
is_man(_) -> false. 

L = [{man,   "Jan",     23}, 
     {woman, "Kari",    25}, 
     {man,   "Rune",    30}, 
     {man,   "Vidar",   44}, 
     {woman, "Cecilie", 35}],
L2 = filter(fun is_man/1, L),
L3 = map(fun ({_, _, Age}) -> Age end, L2),
X = fold(0, fun (X, Acc) -> X + Acc end, L3). 

fold({men, 0, women, 0},
     fun (P, Acc) ->
         {men, M, women, W} = Acc,
         case P of
             {man, _, Age} ->
                 {men, M + Age, women, W};
             {woman, _, Age} ->
                 {men, M, women, W + Age}
         end
     end,
     L).

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

Har du lyst til å se meg kode? Jeg har laget en code cast video jeg håper du vil like, men først litt bakgrunn…

Joe Armstrongs foredrag om Message Passing Concurrency in Erlang på QCon London i fjor forandret meg! Han viste meg en måte å trylle med kode på som inntil da hadde vært helt fremmed for meg. Etter det har Erlang, og deretter Clojure, formet nye mønstre i hjernen min, om hvordan det er mulig å skape fantastiske ting med dynamisk kode.

I presentasjonen lagde Armstrong noe han kalte for en universell server – en server som kunne bli hva som helst, bare ved at man sendte den ulike kommandoer. I min video lager jeg en lignende server i Clojure. Jeg forventer ikke at min video skal gi noen den samme kvasireligiøse a-ha-opplevelsen som Joe gav meg, men kanskje den kan gi deg noen nye ideer…

Jeg hadde veldig lyst til å bruke Daft Punk’s TRON Legacy soundtrack som bakgrunnsmusikk, men jeg turde til slutt ikke å bruke musikk jeg ikke har rettighetene til. Musikken er derfor hentet fra Mevio’s Music Alley. Skru på høytalerne!

The Universal Server from Torbjørn Marø on Vimeo.

Vil gjerne høre hva du synes!

Dette er del 5 i artikkelserien Ping Ring hvor jeg implementerer et og samme program i et utall ulike programmeringsspråk – for å se om det er noe å lære gjennom å gjøre det. Introduksjonen kan du lese her.

Jeg har ikke kunnet komme med noen banebrytende oppdagelser sålangt i denne serien. Språkene jeg har valgt har vært for like. Jeg har egentlig implementert nøyaktig det samme programmet i alle språkene, og ikke funnet noen forskjeller av stor nok betydning til å utrope ett av språkene som mere egnet for oppgaven enn de andre. Det er på tide å forsøke noe radikalt anderledes…

Derfor har jeg nå valgt Erlang. Mens C#, Ruby og Boo er objektorienterte språk, er Erlang funksjonsbasert. Dette betyr blant annet at jeg bør finne en alternativ måte å løse shared state på – i de tidligere implementasjonene har listener- og alerter-trådene begge hatt tilgang til en variabel med tidspunktet for sist innkommende ping. Slikt fnyser man av i den funksjonelle verden.

Viktigere er det at Erlang er designet med fokus på samtidighet, og dessuten mye brukt i løsninger som baserer seg på TCP og andre lavnivå-protokoller. Jeg hadde derfor store forventninger til Erlang-implementasjonen av Ping-Ring.

Actor model

Et sentralt begrep i Erlang er Actor Model. Det språket i praksis støtter er at man oppretter isolerte prosesser (actors), og at prosessene deretter enkelt kan sende meldinger til hverandre. Hver prosess har en inbox i form av en kø, og leser og behandler meldinger asynkront i forhold til resten av programmet.

Figuren nedenfor er et gjensyn fra Ping Ring del 2, og illustrerer designet jeg brukte da jeg har implementert løsningene i C# / Ruby / Boo. Her ser du at jeg hadde to tråder som delte en variabel, og som opprettet egne tråder hver gang et ping skulle sendes.

Neste figur illustrerer hvordan Erlang-løsningen skiller seg fra de foregående. Her har jeg tre selvstendige prosesser som hver holder på sin egen state, og som kommuniserer via meldinger. Både Listener og Alerter sender for eksempel melding til Pinger når de ønsker å få sendt en ping.

Mange ser på actor model som en bedre/mere riktig form for objektorientering, og spår at vi kommer til å få se flere språk med innebygd støtte for denne modellen i årene som kommer.

Problemene

Erlang gir meg altså muligheten til å lage et ganske elegant design for å løse denne oppgaven. Problemet ligger derimot i detaljene. Før du tar en titt på koden vil jeg gå gjennom noen av de tingene jeg ikke liker med løsningen jeg har kommet opp med.

Merk at noen av mine erfaringer helt sikkert kan skyldes at jeg fortsatt er ganske fersk i Erlang. Har du mer kunnskap enn meg er det bare å sette meg på plass.

Tidligere har jeg jobbet endel med lister i Erlang, og til det er det veldig egnet. Da jeg nå skulle gjøre helt enkle ting som å konvertere en streng til en integer, og konkatinere to strenger, oppdaget jeg at språket ikke var like elegant på alle områder. Jeg savnet også if, og måtte ty til en bråkete switch-case når jeg skulle avgjøre om det skulle sendes en initiell ping ved oppstart (se linje 22 til 25).

TCP-grensesnittet var også mye mere komplisert (low level) enn det jeg hadde å forholde meg til i de andre språkene (linje 36 til 51). Jeg skulle for eksempel gjerne hatt en “read_to_end” funksjon; do_recv() er min variant av den. Generelt føltes det som om jeg måtte skrive mere kode enn hva som burde være nødvendig, nesten samme hva jeg holdt på med.

Det mest utfordrende var derimot å klare å kjøre programmet fra kommandolinjen. Til slutt måtte jeg legge til et par ekstra overloads av start-funksjonen får å klare å håndtere kommandolinje-parametrene riktig (linje 4 til 16).

Ok, nok klaging – her er kildekoden i sin helhet:

Det jeg derimot følte ble veldig bra var det jeg kalte actor 2 og 3 (ping sender, linje 60, og ping watcher, linje 75). Watcheren ble spesielt elegant synes jeg. Her utnytter jeg Erlangs evne til å fyre av et event når jeg har ventet på en melding i x antall millisekunder. Jeg venter nemlig på pings på linje 76, og når ping kommer repeterer jeg bare (halerekursjon). Etter så mange sekunder som det er tillatt å gå uten pings (linje 78: after MaxDeley * 1000) aktiverer jeg derimot alarmen.

På den måten trenger jeg heller ikke å gjøre beregninger basert på klokketid, antall sekunder siden sist ping er jo MaxDelay ganger DelayCount.

Konklusjon

Actor-modellen er elegant, og passer veldig bra for denne oppgaven. Språket er derimot ikke så veldig bra å implementere i (eller eventuelt min kunnskap om det er for dårlig). Det er alt i alt lite tilfredstillende – kildekoden ser ikke fin ut, det er for mye av den, og den føles gammeldags. Jeg merker at jeg ønsker meg en fullgod implementasjon av actor model i et annet språk.

I neste runde av denne serien vil jeg bruke et språk som er enda eldre enn Erlang, men som har en syntax jeg synes er super-elegant…

Tidligere i serien: Introduksjon | Del 2 (C#) | Del 3 (Ruby) | Del 4 (Boo).

Kildekoden fra denne blogposten er tilgjengelig på Github. Der står du fritt til å forgrene løsningen og gjøre egne modifikasjoner om du ønsker det (for å illustrere et poeng eller lignende). Som alt annet på bloggen er koden lisensiert under Creative Commons.

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.

Når jeg skal lære meg et nytt programmeringsspråk så synes jeg det er greit å begynne med en bok. For når jeg vet lite om et tema fra før, er det bra å få en sammenhengende introduksjon som begynner med det som er helt basic, og bygger lag på lag med mer avansert stoff. Da går man sjelden glipp av noe viktig, og får en god og generell oversikt over alle muligheter man har. Jeg legger derfor en god del arbeid i å finne den beste boken om temaet jeg ønsker å lære meg.

Da jeg skulle ha meg en bok om Erlang hadde jeg derimot ikke så mange valg. Det fantes egentlig bare to. Men siden jeg allerede var utrolig inspirert av Joe Armstrong (både gjennom å lese Coders at Work, og da jeg så ham på QCon London), så var det ikke vanskelig å velge nettopp hans bok.

Programming Erlang: Software for a Concurrent World (2007) er en inspirerende bok skrevet av den som kan Erlang aller best. Joe er tydelig glad i språket han var med å utvikle for Ericsson. Det er en munter og lettlest bok, selv om temaet i utgangspunktet var ganske gresk for en OO-fokusert utvikler som meg.

Joe introduserer alle grunn-konseptene i språket – som det ikke er så mange av – og bruker resten av boken på å fortelle om hvordan Erlang egner seg til samtidighetsorientert programmering. Boken er ikke komplett, men han touch’er borti en god del ulike tema, og den fungerer derfor som en god inngangsport til videre læring.

Joe Armstrongs Programming Erlang, fra The Pragmatic Programmers-serien, anbefales på det varmeste!

Den andre boken jeg kunne ha valgt er O’REILLYs ERLANG Programming, skrevet av Francesco Cesarini og Simon Thompson. Den er nyere enn Joe’s bok (2009), og koster nesten dobbelt så mye på Amazon. Den går også (tilsynelatende – jeg har ikke lest boken) mye dypere inn på hvert tema, og dekker også områder som Joe utelot helt i sin bok.

Siden jeg bare var interessert i språket, ville lære mer om hva det var for noe – og skape noen nye hjernekoblinger – så var Programming Erlang perfekt for meg. Har du tenkt å faktisk bruke språket i et seriøst prosjekt vil jeg derimot tro at ERLANG Programming kan være veien å gå.

Flere bøker slippes i disse dager

Erlang er et HOT språk akkurat nå. Og der det er ny interesse dukker det alltid opp nye bøker. Første mars i år kom Mastering Erlang: Writing Real World Applications, en bok i The Expert’s Voice-serien. Dette er en bok for deg som allerede har lært deg litt Erlang, og som vil bli bedre, og lære å utnytte Erlang i profesjonell utvikling. Beskrivelsen på Amazon skryter voldsomt, men boken har ingen leseranmeldelser enda.., kanskje vi får vente litt og se.

Jeg må forresten nevne at jeg la merke til at forfatteren, Geoff Cant, blant annet har implementert en SMS Gateway i Erlang. Interessant for en PSWinCom‘er!

På Manning Publications kan man også finne en Erlang-bok. Den er riktignok ikke ferdig enda, men det er nok bare finpuss igjen, og gjennom Manning Early Access Program (MEAP) kan man få digital tilgang til den allerede. Boken heter Erlang and OTP in Action, og inneholder blant annet stoff om integrasjon mot C/C++, Java og .NET-applikasjoner. Den skryter også av å ha et større fokus på SOA og web-teknologier enn de andre bøkene. Boken skal ha mye eksempelkode, og være en bra hands-on guide.

Den siste Erlang-boken jeg har hørt om, Erlang Web Applications, skal komme i august i år. Erlang har noen veldig spesielle og interessante rammeverk og komponenter for webutvikling, som det kan være vel verdt å lære mer om. OTP inneholder modulen inets som har http-server mulighet, men mere kjent er webserveren Yaws. Mochiweb er et annet biblotek for å lage servere, mens Erlang Web, ErlyWeb og Nitrogen er rammeverk for å lage webapps.

Jeg anbefaler spesielt å ta en titt på demoene til Nitrogen – dette er en frisk, ny vri på pragmatisk webutvikling, ispedd en god del AJAX out of the box.

For å fullføre listen med webteknologier (de jeg har fått med meg i det minste) må jeg nevne erlydtl, som er en implementasjon av den populære Django template engine (normalt brukt fra Python) for Erlang, og sist men ikke minst herml, er Erlang-implementasjon av haml (en annen, spenstig template engine, oftest brukt fra Ruby).

Så der har du det altså – en komplett liste over alle bøkene som du kan vurdere om du har blitt inspirert av mine blogposter om Erlang, og har tenkt å sette deg inn i dette språket i år!

I denne blogposten får du se seks ulike løsninger på den aller enkleste oppgaven på Project Euler (jeg har snakket om hvordan jeg har brukt Euler til å lære meg nye programmeringsspråk her). Underveis vil du lære litt elementær Erlang-kode, se hvordan man kan parallellisere en enkel algoritme, og se hvilke ytelsesforbedringer det kan gi. Som en appetizer, her er ytelsen (forbrukt tid) på de ulike algoritmene relativt til hverandre:

  Og her er oppgaven…

Project Euler : Problem 1
Hvis vi lister alle naturlige tall under 10 som er multipler av 3 eller 5, så får vi 3, 5, 6 og 9. Summen av disse er 23. Finn summen av alle multipler av 3 eller 5 under 1000.

Version 1 : tail recursion

For å finne løsningen kaller vi først sum-funksjonen i linje 4 med grenseverdien (1000 ifølge oppgaven). Dette vil kalle sum-funksjonen definert i linje 7 til 14 med verdiene 1000, 1 og 0 (Limit, Current og Sum). Linje 7 sier i praksis at hvis Limit og Current er like (de to første verdiene) så skal vi bare returnere Sum (som er svaret på oppgaven). Hvis vi ikke har kommet dit enda skal vi først sjekke om Current skal inkluderes i summen, og legger den til hvis den skal det, før vi øker Current og kaller sum igjen.

Denne algoritmen er altså en rekursjon, eller mer presist en hale-rekursjon (fordi det siste som skjer i sum er at den kaller seg selv). Funksjonelle språk som Erlang er optimalisert for hale-rekursjon, og det vil ikke kunne gi stack overflow, slik språk som C# vil kunne gjøre om rekursjonen er for dyp.

Version 2 : Bruk av lists modulen

Etter å ha lært meg litt mer om mulighetene i Erlang fikk jeg lyst til å lage en versjon til av denne algoritmen. Det finnes nemlig en modul som heter lists som inneholder mange, greie funksjoner. Ved å kombinere seq, filter og sum derfra presterte jeg følgende, lille funksjonen som gav samme resultat.

Lists:seq(1, 1000) gir meg en liste med alle tallene fra 1 til 1000. Ved å bruke filter-funksjonen kan jeg så sortere ut alle tallene jeg er interessert i. Linje 7 er forøvrig en lambda (anonym metode). Lists:sum summerer tallene i listen.

Versjon 2 er jo mye mindre, men er den bedre? Til å finne løsningen når Limit er 1000 er denne algoritmen helt utmerket. Den yter derimot dårligere om jeg øker Limit (betydelig), fordi den genererer en lang liste – og den listen må holdes i minne. Version 1 holdt jo bare selve summen i minne, og modifiserte den for hvert tall. Når Limit er stor nok bryter faktisk versjon 2 helt sammen.

Version 3 : List comprehension (med custom range)

Erlang er det første programmeringsspråket jeg har lært meg hvor jeg kan bruke list comprehensions (LINQ i C# er et lignende konsept), og denne oppgaven kan også løses med en sånn. Versjon 3 er ekvivalent med versjon 2 – uttrykket er i praksis et filter over en liste. I denne versjonen genererer jeg derimot min egen range i stedet for å bruke lists:seq.

Versjon 3 har samme problem som forrige versjon i forhold til å bryte sammen om Limit blir alt for stor. Den er derimot mye raskere enn begge de foregående algoritmene (ytelses-måling dokumentert lengre nede).

Version 4 : List comprehension (med lists:seq)

Siden versjon 3 fungerte så bra måtte jeg teste den med bruk av lists:seq også, og den viste seg faktisk å være enda raskere. Lists:seq er altså ikke noe problem.., det var nok lists:filter som gav dårlig performance i versjon 2.

Version 5 : Parallellisering av version 1

Denne oppgaven er perfekt for parallellisering – den er det vi kaller “pinlig parallelliserbar”. Og siden Erlang er laget for parallellitet måtte jeg jo forsøke..

Alle algoritmene for å løse denne oppgaven tar i bunn og grunn en lang rekke tall og summerer dem sammen. Hvis man splitter opp den lange rekken i mindre deler, kan del-summen kalkuleres parallelt. Til slutt slår man sammen del-summene.

Mitt første forsøk på en parallell løsning er en kopi av versjon 1, hvor jeg oppretter ulike Erlang-prosesser for å finne summen for ulike intervaller, for så å samle sammen alle svarene. Linje 30 til 44 er mer eller mindre identisk med Versjon 1. I linje 28 sender en worker-prosess en melding tilbake til “master” med del-summen den har kommet frem til. Resten av koden oppretter worker-prosessene og samler sammen svarene.

Om jeg kjører denne parallelle utgaven av den orginale algoritmen på min arbeidsmaskin, og spesifiserer at den skal bruke 2 prosesser (altså dele arbeidet i to), så blir den nesten dobbelt så rask. Den bruker like mye CPU-tid som før, men arbeidet fordeles over mine to prosessorer, og svaret dukker derfor opp dobbelt så raskt (kun med et lite overhead for å administrere prosessene).

Noen forbedring utover dette klarer jeg derimot ikke å oppnå – ikke på min maskin. Hadde jeg hatt flere CPU’er ville jeg fått en høyere effekt om jeg splittet opp arbeidet ytterligere.

Version 6 : Parallellisering av version 4

Men jeg hadde fortsatt et håp om å få bedre utbytte av parallellitet, så jeg lagde en parallell utgave av versjon 4 også, den raskeste av de sekvensielle algoritmene. Denne gangen inneholder koden ikke noe nytt – denne er en kombinasjon av version 4 og 5..

Denne implementasjonen oppførte seg ganske anderledes; når den ble kjørt med et lavt antall prosesser var den ikke spesielt bra, i alle fall ikke for høye verdier av Limit, ettersom den holder listene i minne. Men etterhvert som jeg skrudde opp antall prosesser gikk prosesseringstiden ned betydelig. Det jeg kunne observere her var at samtidig som jeg utnyttet mine to prosessorer så gikk også den totale CPU-tiden ned fordi listene blir mindre når intervallet blir delt nok opp.

Resultater

En Limit på 1000 er for lite til å observere noen tydelig forskjell mellom algoritmene. 20 millioner gir derimot et greit utslag. Her følger er reell sammenligning av alle versjonene med 20000000 som Limit.

6> problem1:test(20000000).
'Version 1' calculates sum 93333316666668 in 4212 (4353) ms
'Version 2' calculates sum 93333336666668 in 4805 (5990) ms
'Version 3' calculates sum 93333316666668 in 2590 (3120) ms
'Version 4' calculates sum 93333336666668 in 2402 (2824) ms
'Version 5 (   1 proc )' calculates sum 93333316666668 in 4602 (4695) ms
'Version 5 (   2 procs)' calculates sum 93333316666668 in 4789 (2543) ms
'Version 5 (   5 procs)' calculates sum 93333316666668 in 4852 (2543) ms
'Version 5 (  10 procs)' calculates sum 93333316666668 in 4836 (2496) ms
'Version 5 ( 100 procs)' calculates sum 93333316666668 in 4758 (2527) ms
'Version 5 (1000 procs)' calculates sum 93333316666668 in 4914 (3074) ms
'Version 6 (   1 proc )' calculates sum 93333316666668 in 4274 (5990) ms
'Version 6 (   2 procs)' calculates sum 93333316666668 in 4509 (3744) ms
'Version 6 (   5 procs)' calculates sum 93333316666668 in 4524 (3167) ms
'Version 6 (  10 procs)' calculates sum 93333316666668 in 3619 (2543) ms
'Version 6 ( 100 procs)' calculates sum 93333316666668 in 2980 (1965) ms
'Version 6 (1000 procs)' calculates sum 93333316666668 in 2667 (1513) ms
'Version 6 (5000 procs)' calculates sum 93333316666668 in 2777 (1607) ms

Det første tallet for hver kjøring er CPU-tid, mens tallet i parantes er faktisk klokketid – begge i millisekunder. Legg merke til at begge de parallelle algoritmene begynner å “slite” om det opprettes for mange prosesser. Dette er naturlig fordi det er et overhead knyttet til å administrere og veksle mellom dem. 5000 processer er dog helt uproblematisk for version 6, selv om det optimale er nærmere 1000.

For å teste algoritmene brukte jeg følgende script..

Den første oppgaven jeg gav lærlingen min var å programmere et enkelt kommandolinje-basert kassaapparat i C#. Her er spesifikasjonen. Da jeg begynte å lære meg Erlang tenkte jeg det kunne være interessant å løse den samme oppgaven i det språket.

I denne blogposten følger løsningen jeg kom opp med. Har du lest det jeg har skrevet om Erlang i det siste, og har lyst til å se mer, så kan dette være et interessant eksempel å sette seg inn i.

Cash_register.erl er en implementasjon av en veldig enkel erlang-server (gen_server). Jeg kan opprette en instans av serveren i en erlang-sesjon, og sende prosessen meldinger for å utføre operasjoner på kassaapparatet – dette tilsvarer kommandolinje-grensesnittet beskrevet i den orginale oppgaven. Du kan se et eksempel på en slik sesjon i bunn av blogposten, men først skal vi ta en gjennomgang av koden.

Den første delen definerer modulen og det eksterne interfacet. Funksjonene start og stop starter og stopper logisk nok serveren. Deretter følger funksjonene for å liste tingene butikken selger, kjøpe en (eller flere) ting, se innholdet i handlekurven, og betale. Alle disse sender en melding til prosessen ?MODULE – og ?MODULE er bare en macro som erstattes med navnet på modulen (cach_register). Prosessen lever altså i sin egen “tråd”, og håndterer meldingene asynkront.

Og nå følger selve kassaapparat-logikken, koden som kjøres i server-prosessen og som håndterer kallene som gjøres i linje 14 til 18. Det hele er egentlig ganske enkelt, selv om det nok ser kaotisk ut ved første øyekast om man ikke er vandt til Erlang. Se på hver av handlerne og sammenlign med output når metodene kjøres (se den gule boksen i slutten av blogposten).

Spesielle ting å legge merke til: I linje 25 er det en list comprehension som lager en liste av alle tingene butikken selger kombinert med prisen for hver ting. Se også hvordan jeg oppdaterer handlekurven (State) i linje 30. I handleren som begynner på linje 39 kan du se en erlangsk switch/case, hvor jeg sjekker om det du betaler er nok for å dekke alle varene.

Du kan også legge merke til at linje 24 til og med 56 er én funksjon. Den har bare flere “innganger”, og bruker mønstergjenkjenning til å finne ut hvilken inngang som skal brukes basert på hvilken melding den mottar (se blogposten mønstergjenkjenning i erlang).

Den neste lille biten er noen små detaljer som ble brukt i del 2 – nemlig definisjonen av prisene for hver vare, og metoden som summerer opp totalprisen for alt i handlekurven (her bruker jeg også en list comprehension).

De siste fem linjene er egentlig ikke i bruk, men er nødvendige for at jeg skal kunne bruke gen_server-modulen. Legg merke til metoden “code_change” – den blir kalt om man endre modulens kode mens serveren kjører!

Til slutt må jeg bevise at programmet fungerer som det skal. Ved hjelp av et interaktivt Erlang shell kan jeg kompilere modulen min (prompt 1 nedenfor), starte serveren i en ny prosess (prompt 2), og begynne å handle: 

C:\Users\tormar\erlang_projects\cash_register>erl
Eshell V5.7.4  (abort with ^G)
1> c(cash_register).
{ok,cash_register}
2> cash_register:start().
{ok,<0.38.0>}
3> cash_register:list_items().
{items_in_shop,[{bread,3.99},{milk,2.5},{butter,4.0}]}
4> cash_register:buy(butter).
{bought,1,butter,price,4.0,total,4.0}
5> cash_register:buy(bread, 2).
{bought,2,bread,price,7.98,total,11.98}
6> cash_register:buy(milk, 4).
{bought,4,milk,price,10.0,total,21.98}
7> cash_register:show_cart().
{shopping_cart,[{milk,4},{bread,2},{butter,1}],total,21.98}
8> cash_register:checkout(20).

that_is_not_enough 

9> cash_register:checkout(50).
{received,50,total_to_pay,21.98,you_get_back,28.02}

10> cash_register:show_cart(). 

{shopping_cart,[],total,0}
11> cash_register:stop().
stopped
12>

PS til prompt 2: Det som returneres når jeg starter cash_register servicen er en Pid (process id).

Så, er det noen erfarne Erlang-utviklere der ute som vil kommentere min første gen_server? Det er sikkert mye å ta tak i her :)

For at du skal være villig til å bruke tid på et nytt programmeringsspråk er du sikkert interessert i å vite noe om hvor modent det er, og om det er noe som er brukende i praksis. Du vil ha bevis for at andre har brukt det. Erlang er ikke like stort som .Net, Java, Ruby eller Python, men det finnes likevel mange suksesshistorier.

Erlang var et internt språk hos teleselskapet Ericsson fra 1986 til 1998. De brukte språket til å programmere hardware brukt i GPRS og 3G nettverk verden over. I 1998 bestemte de seg for at de ikke lenger ville kode i et proprietært språk, og åpnet derfor opp kildekoden. Problem solved!

Andre brukere i tele-sektoren er T-Mobile, som bruker Erlang i sine SMS og autentiserings-systemer, og Motorola, som bruker Erlang i prosessering av samtaler knyttet til public safety (kilde: StackOverflow).

Flere bedrifter i andre bransjer, som også har behov for å utvikle systemer med høy ytelse og kapasitet, og med minimal eller ingen nedetid, har i de siste årene tatt i bruk Erlang. Av de mest profilerte prosjektene kan jeg nevne CouchDB (dokumentbasert database), RabbitMQ (meldingskø-system) og ejabberd (instant messaging server, bl.a. brukt i Facebook). Amazon har også brukt Erlang til å implementere SimpleDB, som tilbyr databasetjenester i Amazon Elastic Compute Cloud (EC2). Og Yahoo! har brukt Erlang i implementasjonen av sin sosiale bokmerke-tjeneste Delicious.

Erlang egner seg svært godt til å implementere server-software. Språket er designet fra grunnen av med tanke på skalerbarhet, stabilitet og høy ytelse. Man kan oppgradere kode mens systemet kjører, man kan sette opp noder på ulike maskiner som snakker enkelt sammen, og plattformen har til og med en innebygget, distribuert databaseløsning laget med fokus på høy grad av tilgjengelighet og ytelse.

Damien Katz, utvikler av CouchDB, sier om sine erfaringer med Erlang:

“The code is typically much more compact, elegant and reliable than it would be in more conventional languages.”

Katz bemerker derimot at det også er en rekke områder hvor han ikke ville benyttet Erlang. Han sier språket egner seg mindre bra til ting hvor man er mere avhengig av state, som i programmering av brukergrensesnitt, og han sa han slet noe voldsomt med å skrive enhetstester i Erlang (en erfaring jeg foreløpig ikke deler – enhetstester i Erlang er helt konge!). Her er blogposten hvor han forteller om Erlangs mange feil.

Erlang har også påvirket andre språk – ifølge wikipedia har både Clojure og Scala hentet inspirasjon derfra. Det har også Microsoft gjort i sitt inkubasjons-prosjekt Axum, som muligens kan utvikle seg til å bli .NET’s beste svar på utfordringene rundt parallell programmering.

Så hvis du vurderer å ta i bruk Erlang, så skal du vite at selv om språket i seg selv ikke er en tungvekter i bransjen, så er det mange tungvektere som bruker det. Oppmerksomheten rundt Erlang er sterkt voksende, samtidig som teknologien har vært vel utprøvd i mange år.

Pattern matching, eller mønstergjenkjenning, er en svært sentral teknikk i Erlang. I de fleste programmeringsspråk betyr for eksempel “=” tilordning av en verdi til en variabel. Ikke i Erlang. Her er nemlig “=” en pattern matching-operasjon. X = Y betyr: Evaluer høyresiden (Y), og match det så mot venstresiden (X). Om X allerede har en verdi, og den ikke er lik verdien av Y, vil X = Y kaste en exception.

For å illustrere hvordan mønstergjenkjenning kan brukes til å gjøre kode svært lesbar og deklerativ vil jeg vise litt kode jeg skrev da jeg løste oppgave nummer 54 på Project Euler. Her ble jeg bedt om å analysere en rekke poker-hender. Dette er en oppgave hvor jeg vet akkurat hvordan jeg ville løst det i et objektorientert språk, men å løse det i et funksjonsbasert språk var en ny og spennende utfordring.

Sidebar: Project Euler er en webside som inneholder hundrevis av programmeringsoppgaver, med vekt på matematisk forståelse. Man kan registrere seg for å holde track på hvor mange oppgaver man har løst. Jeg synes disse oppgavene er perfekte når man skal trene seg opp i et nytt prorgammeringsspråk, og jeg anbefaler utviklere på alle erfaringsnivå å prøve seg.

Her er funksjonen min for å sjekke om en poker-hånd er et fullt hus:

Funksjonen inneholder en case-statement, og i linje 62 ser du det første forsøke på å matche et mønster. Jeg sjekker om hånden er lik mønsteret X,X,X,Y,Y – dvs. først tre like verdier og så to andre, like verdier. Det er jo nettopp dette som er et hus i poker. I linje 63 forsøker jeg å matche den andre muligheten, som er X,X,Y,Y,Y (det finnes ikke flere permutasjoner fordi jeg har sortert kortene i linje 61).

Hvis et av de to mønstrene matcher hånden, returnerer jeg et positivt svar. Hvis ingen matcher (mønsteret _Other matcher hva som helst) returnerer jeg et negativt svar (no).

Jeg skriver altså ingen imperativ kode for å søke/loope gjennom hånden og sjekke hva den inneholder. Jeg deklarerer bare mønsteret for hvordan hånden må “se ut”, og erlang finner ut resten. Her er et eksempel til, hvor jeg sjekker om hånden inneholder tre like:

Mønstergjenkjenning i funksjonskall

Vi bruker også mønstergjenkjenning til å definere ulike “entrypoints” til funksjoner. Et typisk eksempel er fibonacci-funksjonen. Jeg kan definere fibonacci-følgen ved å si at de to første tallene er begge lik 1, og alle etterfølgende tall er lik summen av de to foregående tallene. I deklerative språk er det lett å lage funksjoner som genererer slike matematiske formler:

Funksjonen fib tar ett argument. Når metoden kalles vil Erlang bruke pattern matching til å avgjøre hvilken av de tre “versjonene” av fib som skal kalles. Er argumentet for eksempel tallet 2, vil den kalle fib(2) i linje 25, som rett og slett returnerer tallet 1.

Er argumentet i stedet tallet 3, vil linje 26 aktiveres (24 og 25 matcher ikke, men N matcher alle øvrige tall). Resultatet av fib(3) er fib(2) + fib(1). For å løse dette vil Erlang igjen kalle funksjonene i linje 24 og 25. Er utgangspunktet et større tall vil vi få en rekursjon i linje 26 – inntil vi kommer ned til fib(2) og fib(1).

Mønstergjenkjenning i enhetstester

Vi kan også bruke mønstergjenkjenning til å skrive elegante enhetstester i Erlang. Bruk av testdrevet utvikling er absolutt å anbefale når man programmerer i et nytt språk, fordi man lett gjør småfeil som det ellers kan være vanskelig å oppdage. Og sålangt har jeg bare positive erfaringer med å skrive funksjonsbaserte tester.

En enkel enhetstest av Erlangs innebygde metode for å reversere en liste kan for eksempel se slik ut:

Her bruker jeg funksjonen lists:reverse() på en liste som består av tallene 1, 2, 3 og 4. Det forventede resultatet er en liste som består av tallene 4, 3, 2 og 1. Likhetstegnet er som jeg nevnte i innledningen ingen tilordning – det er et forsøk på å matche resultatet av høyresiden mot det som står på venstresiden. Hvis høyresiden resulterer i noe annet enn listen 4, 3, 2, 1, vil likhetstegnet kaste en exception, og testen vil dermed feile.

Dette er elegant fordi det ligner mer en spesifikasjon enn en test. Funksjonen beskriver fakta, og hvis den faktiske implementasjoner fraviker denne definisjonen vil spesifikasjonen feile.

Samme teknikk brukte jeg på en funksjon for å vurdere om en poker-hånd er en straight (lagde ganske mange varianter av akkurat den funksjonen). Her plukker jeg først ut kortenes verdi i synkende rekkefølge i variablene A, B, C, D og E. Deretter forsøker jeg å påstå at A=B+1, at B=C+1 osv. Hvis dette går bra for alle kortene så vet jeg at jeg har en straight – fem kort i rekkefølge. Om så ikke er tilfelle vil det kastes en exception, som jeg catcher og returnerer i stedet “no” (“nei, det er ingen straight”).