[Haskell-cafe] State Machine and the Abstractions

[Heinrich Apfelmus]

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
>     patrol
> 
> [...]
> 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

    do
      moveTo point1
      moveTo point2
      shoot
      moveTo point3
      ...etc.

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 
pairing states.


(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.)



Best regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com