mandag 5. januar 2015 F# Funksjonell programmering
Einar, Bjørn Einar og Jonas fra Computas holdt en underholdende forelesning på NDC London i år som de kalte The State of State. Her snakket de mye om hvor nyttige endelige tilstandsmaskiner - eller Finite State Machines (FSM) - kan være. Dette er noe jeg også har skrevet om (se for eksempel En generisk state mashine fra 2009).
Et annet sentralt tema på konferansen var funksjonell programmering. Dette fikk meg til å tenke: Hvordan ser en funksjonell tilstandsmaskin ut?
La oss eksperimentere litt og se om vi kan finne det ut. Disclamer: Jeg har ikke googlet dette, men ville i stedet se hva jeg selv kunne komme opp med.
En FSM i den objektorienterte verden er en entitet som har en bestemt tilstand. Tilstanden kan for eksempel være Happy. Maskinen blir så påvirket av en hendelse. Dette kan endre tilstanden til for eksempel Angry. I tillegg kan overgangen fra en tilstand til en annen ha sideeffects.
Så hvordan skal vi gjøre dette i den funksjonelle programmeringsparadigmen? I FP løses alt med funksjoner, så da bør vel tilstandsmaskinen også være en funksjon. Funksjoner har ikke tilstand; i stedet kan vi lage en FSM-funksjon som tar inn en tilstand og en hendelse, og som returnerer en ny (potensiell) tilstand.
Hva med bieffekten av tilstandsendringen? Funksjonen kunne jo ha utført denne, men jeg har en mere spennende idé: Vi kan la funksjonen returnere bieffekten også!
Å skyve bieffekter ut av funksjonene, og kun gjøre det i den "ytterste" delen av programmet, er en generell FP-teknikk. Resultatet blir kode som er enklere å teste og å forstå.
Det er på tide å kode litt. La oss bruke F# til å implementere tilstandsdiagrammet i starten av denne artikkelen. Språkets algebraiske datatyper lar oss uttrykke tilstandene og hendelsene slik:
type EmoState = Happy | Sad | Angry
type EmoEvent = YellAt | Comfort | Mock
type EmoEffect = string -> unit
EmoEffect inkluderte jeg mest for dokumentasjonens skyld. Den sier at en effekt er en funksjon som tar inn en streng (navnet på personen) og ikke returnerer noe som helst.
La oss så definere noen sånne effekt-funksjoner:
let becomeAngry subject =
printfn "%s goes bananas!!!" subject
let becomeSad subject =
printfn "%s has a long face :-(" subject
let becomeHappy subject =
printfn "%s is happy again :)" subject
Nå kan vi lage en FSM-funksjon som definerer alle tilstandsendringer og returnerer ny tilstand og muligens en effekt.
let transition event state =
match state, event with
| Happy, YellAt -> Angry, Some (becomeAngry)
| Happy, Mock -> Sad, Some (becomeSad)
| Sad, Comfort -> Happy, Some (becomeHappy)
| Angry, Comfort -> Sad, Some (becomeSad)
| _, _ -> state, None
Typesignaturen til denne funksjonen er EmoEvent -> EmoState -> EmoState * (string -> unit) option. Vi kan teste den, og utføre bieffekten om der er noen med en hjelpemetode jeg kaller doEffect:
let doEffect subject (state, effect) =
match effect with
| Some (effect) -> effect subject
| None -> printfn "Transition had no effect."
state
let newState = transition Mock Happy
|> doEffect "Bob"
Koden skriver ut "Bob has a long face :-(" og newState får verdien Sad.
Fremgangsmåten jeg nettopp brukte fungerer greit nok; den kommuniserer godt og er enkel å forstå. Men den er ikke spesielt dynamisk - alle tilstandsendringene må hardkodes i transition.
En alternativ strategi kunne vært å lage en liste med overganger, og gi denne til en funksjon som genererte en ny tilstandsmaskin basert på dem. Dette er omtrent det jeg gjorde i min generiske FSM i C#.
La oss ta i bruk F# generics og definere en overgang slik:
type Transition<'s,'e,'x> = {
GivenState : 's
Event : 'e
ThenState : 's
Effect: ('x -> unit) option
}
Jeg kan nå lage en tilhørende funksjon transition som finner en overgang fra en sekvens med overganger:
let transition transitions event state =
let transitionLocator t =
t.GivenState = state && t.Event = event
match Seq.tryFind transitionLocator transitions with
| Some (t) -> t.ThenState, t.Effect
| None -> state, None
Typesignaturen til denne versjonen av FSM-funksjone er litt mer komplisert:
/// transitions:seq<Transition<'a,'b,'c>> ->
/// event:'b -> state:'a -> 'a * ('c -> unit) option
/// when 'a : equality and 'b : equality
Det er ikke tilfeldig at parameteret transitions kommer først. Jeg har nemlig tenkt å benytte partial application. Nedenfor definerer jeg alle overgangene og ender opp med en FSM-funksjon jeg kan bruke:
let fsm = transition
[{ GivenState = Happy
Event = YellAt
ThenState = Angry
Effect = Some (becomeAngry) }
{ GivenState = Happy
Event = Mock
ThenState = Sad
Effect = Some (becomeSad) }
{ GivenState = Sad
Event = Comfort
ThenState = Happy
Effect = Some (becomeHappy) }
{ GivenState = Angry
Event = Comfort
ThenState = Sad
Effect = Some (becomeSad) }]
F# forteller meg at fsm har typen EmoEvent -> EmoState -> EmoState * (string -> unit) option, som var det jeg håpte på. Jeg kan nå teste fsm på samme måte som tidligere, og får samme resultat:
let newState = transition Mock Happy
|> doEffect "Bob"
Jeg liker teknikken med en overgangstabell - den er fleksibel og gjenbrukbar. Men siden poenget var å utforske tilstandsmaskiner i et funksjonelt språk så vil jeg forsøke en ting til: Å komponere FSM ved hjelp av rene funksjoner.
Tenk at du har en funksjon makeTransition som kan ta inn en funksjonell tilstandsmaskin og informasjon om en overgang, og som gir deg en ny tilstandsmaskin hvor overgangen er lagt til.
I F# kan man definere funksjoner som kan brukes infix, og på grunn av måten jeg skal bruke makeTransition på så ønsker jeg at denne funksjonen skal være det. Derfor gir jeg den i stedet det litt snåle navnet -?->, som i mitt hode illustrerer en potensiell overgang.
let (-?->) fsm t =
fun event state ->
if t.GivenState=state && t.Event=event
then t.ThenState, t.Effect
else fsm event state
-?-> returnerer en funksjon som danner en closure over funksjonen fsm og overgangs-variabelen t. Denne closuren tar inn et event og en state. Hvis eventet og tilstanden matcher overgangen definert i t så returneres resultatet (ny state og potensiell effekt). Hvis ikke antar funksjonen at det kan finnes flere overganger definert i fsm, og evaluerer denne med argumentene.
Kode som dette gjør at jeg føler meg smart, men det er egentlig ganske grunnleggende rekursjon.
Nå kan jeg definere tilstandsmaskinen min igjen ved å komponere de ulike overgangene sammen med en default overgang som brukes om ingen andre overganger matchet event og state.
let defaultTransition _ state = state, None
let fsm =
defaultTransition
-?-> { GivenState = Happy
Event = YellAt
ThenState = Angry
Effect = Some (becomeAngry) }
-?-> { GivenState = Happy
Event = Mock
ThenState = Sad
Effect = Some (becomeSad) }
-?-> { GivenState = Sad
Event = Comfort
ThenState = Happy
Effect = Some (becomeHappy) }
-?-> { GivenState = Angry
Event = Comfort
ThenState = Sad
Effect = Some (becomeSad) }
Resultatet er at fsm kan brukes akkurat som tidligere, men i stedet for å slå opp overgangen i en sekvens av overganger vil den nå søke seg gjennom overgangene i en sekvens med funksjonskall. Om dette er en fordel eller ikke kommer kanskje an på hvordan tilstandsmaskinen skal brukes.
La meg avslutte med å vise hvordan man kan bruke fold til å kjøre gjennom en serie med hendelser.
let subject = "Sandra"
let initialState = Happy
let events = [YellAt; Mock; Comfort; Comfort]
events
|> Seq.fold
(fun state event ->
fsm event state
|> doEffect subject)
initialState
|> printfn "Final state is %A"
(* Skriver ut:
Sandra goes bananas!!!
Transition had no effect.
Sandra has a long face :-(
Sandra is happy again :)
Final state is Happy
*)
Jeg håper du har klart å henge med, og synes dette har vært interessant. Jeg synes i alle fall det er gøy å leke meg med ulike måter å modellere ting på i F#.
Her er noen eksterne lenker du kanskje vil ta en titt på nå som du har sett min fremgangsmåte: