risorse | macchina a stati funzionale
Negli ultimi anni si fa un gran parlare di programmazione funzionale. Tra gli svariati articoli che si trovano in rete sull'argomento, uno in particolare ha attirato la mia attenzione in questi giorni: A Functional-Style State Machine in C++, di Tamir Bahar. Ho voluto cimentarmi anch'io nell'impresa di realizzare una macchina a stati finiti in C++ secondo i dettami del paradigma funzionale.
Ho trovato questo esercizio in rete:
Design a virtual cat by constructing a state machine. The cat should behave as follows:
- it starts out happy;
- if you pet it, it purrs;
- if you feed it, it throws up;
- if time passes, it gets hungry and rubs against your legs;
- if you feed it when it is hungry, it purrs and gets happy;
- if you pet it when it is hungry, it bites you;
- if time passes when it is hungry, it dies.
Graficamente, la macchina a stati si presenta così:
Funzionamento del gatto virtuale
La classica implementazione procedurale mappa stati, input e output su costanti. La funzione di transizione fa uso di due switch annidati per determinare, a partire dallo stato di partenza e dall'input quali debbano essere l'output e lo stato di arrivo:
#include <cassert>
#include <stdexcept>
enum State {
HAPPY,
HUNGRY,
DEAD,
};
enum Input {
PET,
FEED,
TIME_PASSES,
};
enum Output {
PURRS,
THROWS_UP,
RUBS,
BITES,
UNDEFINED
};
static State state;
Output cat(Input input) {
switch (state) {
case HAPPY:
switch (input) {
case PET:
state = HAPPY;
return PURRS;
break;
case FEED:
state = HAPPY;
return THROWS_UP;
break;
case TIME_PASSES:
state = HUNGRY;
return RUBS;
break;
}
break;
case HUNGRY:
switch (input) {
case PET:
state = HUNGRY;
return BITES;
break;
case FEED:
state = HAPPY;
return PURRS;
break;
case TIME_PASSES:
state = DEAD;
return UNDEFINED;
break;
}
break;
case DEAD:
throw std::runtime_error("cat is dead");
}
throw std::runtime_error("invalid cat state");
}
int main() {
state = HAPPY;
assert(cat(PET) == PURRS);
assert(state == HAPPY);
assert(cat(FEED) == THROWS_UP);
assert(state == HAPPY);
assert(cat(TIME_PASSES) == RUBS);
assert(state == HUNGRY);
assert(cat(PET) == BITES);
assert(state == HUNGRY);
assert(cat(FEED) == PURRS);
assert(state == HAPPY);
assert(cat(TIME_PASSES) == RUBS);
assert(state == HUNGRY);
assert(cat(TIME_PASSES) == UNDEFINED);
assert(state == DEAD);
}
A volte conviene sostituire il doppio switch annidato, obiettivamente poco elegante, con una tabella che contiene tutte le transizioni di stato previste. La funzione di transizione si riduce ad una banale ricerca della corretta transizione da attivare. Di seguito una possibile implementazione, in cui le transizioni sono rappresentate dalla quadrupla (stato-di-partenza, input, stato-di-arrivo, output):
#include <algorithm>
#include <cassert>
#include <stdexcept>
...
struct Entry {
State source_;
Input input_;
State destination_;
Output output_;
bool matches(State source, Input input) const {
return source_ == source && input_ == input;
}
};
const Entry table[] = {
{ HAPPY, PET, HAPPY, PURRS },
{ HAPPY, FEED, HAPPY, THROWS_UP },
{ HAPPY, TIME_PASSES, HUNGRY, RUBS },
{ HUNGRY, FEED, HAPPY, PURRS },
{ HUNGRY, PET, HUNGRY, BITES },
{ HUNGRY, TIME_PASSES, DEAD, UNDEFINED },
};
const int entries = sizeof(table) / sizeof(table[0]);
Output cat(Input input) {
switch (state) {
case HAPPY:
switch (input) {
case PET:
state = HAPPY;
return PURRS;
break;
case FEED:
state = HAPPY;
return THROWS_UP;
break;
case TIME_PASSES:
state = HUNGRY;
return RUBS;
break;
}
break;
case HUNGRY:
switch (input) {
case PET:
state = HUNGRY;
return BITES;
break;
case FEED:
state = HAPPY;
return PURRS;
break;
case TIME_PASSES:
state = DEAD;
return UNDEFINED;
break;
}
break;
case DEAD:
throw std::runtime_error("cat is dead");
}
throw std::runtime_error("invalid cat state");
}
Output cat(Input input) {
const auto entry = std::find_if(
std::begin(table), std::end(table),
[&](const Entry& entry) { return entry.matches(state, input); });
if (entry == std::end(table))
throw std::runtime_error("unexpected state/input pair");
state = entry->destination_;
return entry->output_;
}
...
Nei casi in cui sia richiesto generare degli effetti collaterali durante una transizione di stato, la tabella delle transizioni viene arricchita con un puntatore a funzione che viene invocata direttamente dalla funzione di transizione.
Rispetto all'implementazione basata su switch, questa è decisamente più flessibile: per modificare o estendere la macchina a stati è sufficiente agire sulla sua definizione, mentre la funzione di transizione cat rimane inalterata.
La tipica implementazione di una macchina a stati secondo il paradigma a oggetti si rifà al pattern State della Gang of Four. Si definisce dapprima la classe astratta per modellare lo stato:
enum Output {
PURRS,
THROWS_UP,
RUBS,
BITES,
UNDEFINED
};
class Cat;
class State {
public:
virtual Output pet(Cat& cat) = 0;
virtual Output feed(Cat& cat) = 0;
virtual Output time_passes(Cat& cat) = 0;
};
Mentre gli output conservano la natura di valore, gli input sono modellati come azioni applicate sugli stati, che diventano invece oggetti. Cat è un oggetto che rappresenta il contesto nel quale la macchina a stati sta operando; viene qui dichiarato per rendere compilabile il codice della classe State, e verrà definito più avanti.
Si prosegue con l'implementazione degli stati concreti, la cui responsabilità è di attuare il comportamento associato e indicare al contesto qual'è il prossimo stato da raggiungere:
class Happy : public State {
public:
Output pet(Cat& cat) override;
Output feed(Cat& cat) override;
Output time_passes(Cat& cat) override;
};
class Hungry : public State {
public:
Output pet(Cat& cat) override;
Output feed(Cat& cat) override;
Output time_passes(Cat& cat) override;
};
class Dead : public State {
public:
Output pet(Cat&) override {
throw std::runtime_error("cat is dead");
}
Output feed(Cat&) override {
throw std::runtime_error("cat is dead");
}
Output time_passes(Cat&) override {
throw std::runtime_error("cat is dead");
}
};
class Cat {
...
};
Output Happy::pet(Cat& cat) {
cat.setState<Happy>();
return PURRS;
}
Output Happy::feed(Cat& cat) {
cat.setState<Happy>();
return THROWS_UP;
}
Output Happy::time_passes(Cat& cat) {
cat.setState<Hungry>();
return RUBS;
}
Output Hungry::pet(Cat& cat) {
cat.setState<Hungry>();
return BITES;
}
Output Hungry::feed(Cat& cat) {
cat.setState<Happy>();
return PURRS;
}
Output Hungry::time_passes(Cat& cat) {
cat.setState<Dead>();
return UNDEFINED;
}
Cat infine è l'oggetto che si occupa di fornire l'interfaccia d'accesso alla macchina a stati e di tener traccia dello stato corrente (il Context secondo la terminologia GoF):
class Cat {
std::unique_ptr<State> state_;
public:
Cat() : state_(std::make_unique<Happy>()) {}
Output pet() { return state_->pet(*this); }
Output feed() { return state_->feed(*this); }
Output time_passes() { return state_->time_passes(*this); }
template <class T>
void setState() { state_ = std::make_unique<T>(); }
};
Anche se non esplicitamente richiesto dal pattern, aggiungiamo alcuni metodi per identificare lo stato corrente, utili per il test della macchina a stati appena completata. La versione definitiva del codice object-oriented diventa perciò:
#include <cassert>
#include <memory>
#include <stdexcept>
enum Output {
PURRS,
THROWS_UP,
RUBS,
BITES,
UNDEFINED
};
class Cat;
class State {
public:
virtual bool is_happy() const { return false; }
virtual bool is_hungry() const { return false; }
virtual bool is_dead() const { return false; }
virtual Output pet(Cat& cat) = 0;
virtual Output feed(Cat& cat) = 0;
virtual Output time_passes(Cat& cat) = 0;
};
class Happy : public State {
public:
bool is_happy() const override { return true; }
Output pet(Cat& cat) override;
Output feed(Cat& cat) override;
Output time_passes(Cat& cat) override;
};
class Hungry : public State {
public:
bool is_hungry() const override { return true; }
Output pet(Cat& cat) override;
Output feed(Cat& cat) override;
Output time_passes(Cat& cat) override;
};
class Dead : public State {
public:
bool is_dead() const override { return true; }
Output pet(Cat&) override { throw std::runtime_error("cat is dead"); }
Output feed(Cat&) override { throw std::runtime_error("cat is dead"); }
Output time_passes(Cat&) override { throw std::runtime_error("cat is dead"); }
};
class Cat {
std::unique_ptr<State> state_;
public:
Cat() : state_(std::make_unique<Happy>()) {}
bool is_happy() const { return state_->is_happy(); }
bool is_hungry() const { return state_->is_hungry(); }
bool is_dead() const { return state_->is_dead(); }
Output pet() { return state_->pet(*this); }
Output feed() { return state_->feed(*this); }
Output time_passes() { return state_->time_passes(*this); }
template <class T>
void setState() { state_ = std::make_unique<T>(); }
};
Output Happy::pet(Cat& cat) {
cat.setState<Happy>();
return PURRS;
}
Output Happy::feed(Cat& cat) {
cat.setState<Happy>();
return THROWS_UP;
}
Output Happy::time_passes(Cat& cat) {
cat.setState<Hungry>();
return RUBS;
}
Output Hungry::pet(Cat& cat) {
cat.setState<Hungry>();
return BITES;
}
Output Hungry::feed(Cat& cat) {
cat.setState<Happy>();
return PURRS;
}
Output Hungry::time_passes(Cat& cat) {
cat.setState<Dead>();
return UNDEFINED;
}
int main() {
Cat cat;
assert(cat.is_happy());
assert(cat.pet() == PURRS);
assert(cat.is_happy());
assert(cat.feed() == THROWS_UP);
assert(cat.is_happy());
assert(cat.time_passes() == RUBS);
assert(cat.is_hungry());
assert(cat.pet() == BITES);
assert(cat.is_hungry());
assert(cat.feed() == PURRS);
assert(cat.is_happy());
assert(cat.time_passes() == RUBS);
assert(cat.is_hungry());
assert(cat.time_passes() == UNDEFINED);
assert(cat.is_dead());
}
Nella soluzione ad oggetti si perde traccia della selezione della transizione da eseguire, perché implicitamente risolta a run-time dal polimorfismo. Si assiste inoltre una “diffusione” del codice che viene suddiviso tra le diverse specializzazioni della classe State.
Alterare la macchina a stati vuol dire in questo caso intervenire sugli stati concreti ed eventualmente aggiungerne di nuovi. Rispetto all'implementazione procedurale basata sulla tabella, dove le correzioni erano limitate al vettore delle transizioni, in questo caso le modifiche vanno apportate a tutti gli stati coinvolti. L'oggetto Cat e l'interfaccia State sono senza dubbio i componenti più stabili della soluzione proposta.
In questo caso lo stato è rappresentato da una funzione che, una volta applicata ad un valore di ingresso, produce il valore d'uscita e il nuovo stato, anch'esso rappresentato da una funzione.
In C++ purtroppo non è possibile definire una funzione che presenti tra i suoi parametri d'uscita un (puntatore a) funzione con la sua stessa signature. Supponendo infatti di voler denominare il tipo cercato State e considerando temporaneamente una versione semplificata della funzione di transizione:
State happy() {
return ...;
}
Il tipo della funzione happy è:
State (*)()
In C++ tuttavia non è lecito scrivere:
typedef State (*State)();
e nemmeno:
using State = State (*)();
La ricorsione si può tuttavia spezzare introducendo un function-object (sempre tralasciando per il momento l'implementazione e concentrandoci invece sulla compilabilità del codice):
struct State {
State operator()() { return *this; }
};
int main() {
State cat;
// go to next state
cat = cat();
}
Ricordando che la transizione di stato avviene a fronte di un valore di ingresso e che la stessa produce un valore d'uscita che va accoppiato allo stato d'arrivo, la classe State diventa:
#include <tuple>
enum Input {
PET,
FEED,
TIME_PASSES,
};
enum Output {
PURRS,
THROWS_UP,
RUBS,
BITES,
UNDEFINED
};
struct State {
using Result = std::pair<State, Output>;
State operator()() { return *this; }
Result operator()(Input) { return std::make_pair(*this, UNDEFINED); }
};
int main() {
State cat;
// go to next state
cat = cat();
Output output = UNDEFINED;
std::tie(cat, output) = cat(PET);
}
La funzione di transizione vera e propria può essere iniettata in State all'atto della costruzione:
...
struct State {
using Result = std::pair<State, Output>;
using Fn = Result(*)(Input);
Fn fn_;
State(Fn fn) : fn_(fn) {}
Result operator()(Input input) {
return std::make_pair(*this, UNDEFINED);
return fn_(input);
}
};
State::Result HAPPY(Input input) {
return std::make_pair(HAPPY, UNDEFINED);
}
int main() {
State cat = HAPPY;
// go to next state
Output output = UNDEFINED;
std::tie(cat, output) = cat(PET);
}
Il codice che implementa la macchina a stati richiesta è quindi:
#include <cassert>
#include <tuple>
enum Input {
PET,
FEED,
TIME_PASSES,
};
enum Output {
PURRS,
THROWS_UP,
RUBS,
BITES,
UNDEFINED
};
struct State {
using Result = std::pair<State, Output>;
using Fn = Result(*)(Input);
Fn fn_;
State(Fn fn) : fn_(fn) {}
Result operator()(Input input) { return fn_(input); }
bool operator==(Fn fn) const { return fn_ == fn; }
};
State::Result HAPPY(Input);
State::Result HUNGRY(Input);
State::Result DEAD(Input);
State::Result HAPPY(Input input) {
return std::make_pair(HAPPY, UNDEFINED);
if (input == PET)
return State::Result(HAPPY, PURRS);
else if (input == FEED)
return State::Result(HAPPY, THROWS_UP);
else if (input == TIME_PASSES)
return State::Result(HUNGRY, RUBS);
else
throw std::runtime_error("invalid cat state");
}
State::Result HUNGRY(Input input) {
if (input == PET)
return State::Result(HUNGRY, BITES);
else if (input == FEED)
return State::Result(HAPPY, PURRS);
else if (input == TIME_PASSES)
return State::Result(DEAD, UNDEFINED);
else
throw std::runtime_error("invalid cat state");
}
State::Result DEAD(Input) {
throw std::runtime_error("cat is dead");
}
int main() {
State cat = HAPPY;
Output output = UNDEFINED;
std::tie(cat, output) = cat(PET);
assert(cat == HAPPY);
assert(output == PURRS);
std::tie(cat, output) = cat(FEED);
assert(cat == HAPPY);
assert(output == THROWS_UP);
std::tie(cat, output) = cat(TIME_PASSES);
assert(cat == HUNGRY);
assert(output == RUBS);
std::tie(cat, output) = cat(PET);
assert(cat == HUNGRY);
assert(output == BITES);
std::tie(cat, output) = cat(FEED);
assert(cat == HAPPY);
assert(output == PURRS);
std::tie(cat, output) = cat(TIME_PASSES);
assert(cat == HUNGRY);
assert(output == RUBS);
std::tie(cat, output) = cat(TIME_PASSES);
assert(cat == DEAD);
assert(output == UNDEFINED);
}
Riappare in questo caso lo switch esplicito sul valore d'ingresso, che nella soluzione a oggetti è risolto dall'interfaccia State:
// Object-oriented `happy` // Functional `happy` class Happy : public State { State::Result HAPPY(Input input) { public: ... Output pet(Cat& cat) { if (input == PET) cat.setState<Happy>(); return State::Result(HAPPY, PURRS); return PURRS; } Output feed(Cat& cat) { else if (input == FEED) cat.setState<Happy>(); return State::Result(HAPPY, THROWS_UP); return THROWS_UP; } Output time_passes(Cat& cat) { else if (input == TIME_PASSES) cat.setState<Hungry>(); return State::Result(HUNGRY, RUBS); return RUBS; } else throw std::runtime_error("..."); }; }
D'altro canto, il dispatch esplicito dell'input allo stato corrente della soluzione object-oriented è implicito nella soluzione funzionale, perché lo stato corrente è la funzione di transizione:
int main() { int main() { Cat cat; State cat = HAPPY; assert(cat.is_happy()); Output output = UNDEFINED; assert(cat.pet() == PURRS); std::tie(cat, output) = cat(PET); assert(cat.is_happy()); assert(cat == HAPPY); assert(output == PURRS); assert(cat.feed() == THROWS_UP); std::tie(cat, output) = cat(FEED); assert(cat.is_happy()); assert(cat == HAPPY); assert(output == THROWS_UP); ... ... } }
Pagina modificata il 10/09/2017