[Haskell-cafe] State Machine and the Abstractions
apfelmus at quantentunnel.de
Mon May 30 15:53:28 CEST 2011
Yves Parès wrote:
> For the purposes of a simple strategy game, I'd like to build an EDSL that
> expresses missions. A mission could be represented as a state machine.
> With basic bricks such as actions (MoveTo, ShootAt...) or tests
> (EnemiesAround, LowHealth...), I could (ideally dynamically) build some
> strategic behaviors for the units.
> I will take the example of a patrol. Applied to a unit (or a group of
> units), it dictates : go from point 1 to point 2 and then go back and
> repeat. But when you detect an enemy near, leave the patrol path, destroy it
> and then resume your patrol where you left it.
> So if I consider my mission as a monad:
> data Mission = MoveTo Point | ShootAt Unit
> patrol = do
> MoveTo point1
> MoveTo point2
> So I need a way to say: A is your action of patrolling. B is your action of
> surveillance. Do both in parallel, but B is preponderant, as if it successes
> (if enemies are there) it takes over A. So, it is as if I was running two
> state machines in parallel.
There are several methods to specify state machines, sequential
composition of actions is just one of them. Let me elaborate.
First and foremost, you can express every state machine as an automaton.
For instance, your example above could be written as
state1 --> (MoveTo point1, state2)
state2 --> (MoveTo point2, state3)
state3 --> ((), state1)
An automaton is a set of states and transitions between them, and you
should imagine that all your state machines work like this.
Of course, while all state machines *work* like this, this does not mean
that you have to *specify* them like this. For instance, writing down
the states for a long sequence of actions like
would be very cumbersome, you'd have to invent one dummy state for each
action in the sequence. And this is where do-notation comes in: it's a
way to specify long sequences of actions and have the interpreter
automatically generate the intermediate dummy states!
As you note, however, not all state machines are sequences of actions,
far from it, actually. Sometimes, you want to write
Flee --> MoveTo point0
Attack --> shoot `during` MoveTo point1
Well, nobody forces you to use do-notation in that case, right?
In other words, I propose that you invent a small set of *state machine
combinators* that allow you to freely mix do-notation (or something less
powerful) with state transitions. Parallel composition corresponds to
(Chances are that you can express everything with do-notation by
introducing threads and combinators like during or fork , but I don't
know whether that's the best way to go about it. It's worth trying, but
keep in mind that the goal is to have an expressive set of combinators,
not to shoehorn everything into monads.)
More information about the Haskell-Cafe