fredag 23. april 2010 Erlang Pattern matching
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:
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).
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").