Re: [Haskell-cafe] State Machine and the Abstractions
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State Machine and the Abstractions
Try these two first: Domain Specific Languages for Cellular Interactions http://www.cs.missouri.edu/~harrison/papers/embc04.pdf The Essence of Multitasking http://www.cs.missouri.edu/~harrison/papers/amast06.pdf There are more resumptions (and "reactions") in "Achieving Information Flow Security Through Precise Control of Effects" and "Domain Separation by Construction". http://people.cs.missouri.edu/~harrisonwl/publications.html On 29 May 2011 22:06, Yves Parès wrote: > @Stephen: Resumption monads? It looks interesting, but I fait to see which > paper is about it... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State Machine and the Abstractions
I suggest you take a look at MonadPrompt and/or Operational (two competing packages, one of which I wrote). And yes, you probably need some operation Concurrent :: [Mission ()] -> Mission () or Interrupt :: Mission () -> Mission Bool -> Mission () -> Mission () which runs its first argument until the second argument returns True, then switches. On Fri, May 27, 2011 at 12:06 PM, Yves Parès wrote: > Hello, > > 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 far so good, but there, the only advantage to use a monad instead of a > list of MoveTo's is the do-notation. > And I lack the expression of tests. Using a GADT it could be: > > data Mission a where > MoveTo :: Point -> Mission () > ShootAt :: Unit -> Mission Bool -- If we have destroyed it or not > EnemiesAround :: Mission [Unit] -- The enemies that are maybe in sight > LowHealth :: Mission Bool -- If I should retreat > ... > > -- (Monad Mission could be nicely expressed using Heinrich Apfelmus' * > operational* package) > > patrol = do > MoveTo point1 > MoveTo point2 > enemies <- EnemiesAround > mapM_ ShootAt enemies > patrol > > Aaaand... here comes the trouble: the actions are done *sequentially*. > My units will move and then look at enemies, they will not monitor their > environment while they move. > 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. > Moreover, the last line (the recursive call to patrol) is wrong, as it will > restart the patrol from the beginning, and not from where it has been left. > But this could be corrected by addind a test like "which point is the > closest". > > So I thought about Arrows, as they can express sequential and parallel > actions, but I don't know if it would be a right way to model the > interruptions/recoveries. > What do you think about it? Do you know of similar situations and of the > way they've been solved? > > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > > ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State Machine and the Abstractions
Yes, for my first example, the kind is wrong. I knew it, I just wrote it "to show", not to be correct Haskell, sorry. @Antoine: Well, yes, internally, I think this is how it will be implemented. What I wondered was if arrows would provide a nice interface to it. @Stephen: Resumption monads? It looks interesting, but I fait to see which paper is about it... 2011/5/28 Chuzzle Guevero > For one, you have a kind error. You use Mission as a Monad when it only has > kind *. I don't know much of arrows, but I suggest writing the combinators > you want to have with specialized types, and see where that takes you. If it > happens to lead to an implementation of Arrow, yay. If it doesn't, then you > at least still have something that functions. > >> Message: 13 >> Date: Fri, 27 May 2011 21:06:10 +0200 >> From: Yves Par?s >> Subject: [Haskell-cafe] State Machine and the Abstractions >> To: Haskell-Cafe >> Message-ID: >> Content-Type: text/plain; charset="iso-8859-1" >> >> >> Hello, >> >> 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 far so good, but there, the only advantage to use a monad instead of a >> list of MoveTo's is the do-notation. >> And I lack the expression of tests. Using a GADT it could be: >> >> data Mission a where >> MoveTo :: Point -> Mission () >> ShootAt :: Unit -> Mission Bool -- If we have destroyed it or not >> EnemiesAround :: Mission [Unit] -- The enemies that are maybe in >> sight >> LowHealth :: Mission Bool -- If I should retreat >> ... >> >> -- (Monad Mission could be nicely expressed using Heinrich Apfelmus' * >> operational* package) >> >> patrol = do >> MoveTo point1 >> MoveTo point2 >> enemies<- EnemiesAround >> mapM_ ShootAt enemies >> patrol >> >> Aaaand... here comes the trouble: the actions are done *sequentially*. >> My units will move and then look at enemies, they will not monitor their >> environment while they move. >> 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. >> Moreover, the last line (the recursive call to patrol) is wrong, as it >> will >> restart the patrol from the beginning, and not from where it has been >> left. >> But this could be corrected by addind a test like "which point is the >> closest". >> >> So I thought about Arrows, as they can express sequential and parallel >> actions, but I don't know if it would be a right way to model the >> interruptions/recoveries. >> What do you think about it? Do you know of similar situations and of the >> way >> they've been solved? >> > > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State Machine and the Abstractions
For one, you have a kind error. You use Mission as a Monad when it only has kind *. I don't know much of arrows, but I suggest writing the combinators you want to have with specialized types, and see where that takes you. If it happens to lead to an implementation of Arrow, yay. If it doesn't, then you at least still have something that functions. Message: 13 Date: Fri, 27 May 2011 21:06:10 +0200 From: Yves Par?s Subject: [Haskell-cafe] State Machine and the Abstractions To: Haskell-Cafe Message-ID: Content-Type: text/plain; charset="iso-8859-1" Hello, 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 far so good, but there, the only advantage to use a monad instead of a list of MoveTo's is the do-notation. And I lack the expression of tests. Using a GADT it could be: data Mission a where MoveTo :: Point -> Mission () ShootAt :: Unit -> Mission Bool -- If we have destroyed it or not EnemiesAround :: Mission [Unit] -- The enemies that are maybe in sight LowHealth :: Mission Bool -- If I should retreat ... -- (Monad Mission could be nicely expressed using Heinrich Apfelmus' * operational* package) patrol = do MoveTo point1 MoveTo point2 enemies<- EnemiesAround mapM_ ShootAt enemies patrol Aaaand... here comes the trouble: the actions are done *sequentially*. My units will move and then look at enemies, they will not monitor their environment while they move. 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. Moreover, the last line (the recursive call to patrol) is wrong, as it will restart the patrol from the beginning, and not from where it has been left. But this could be corrected by addind a test like "which point is the closest". So I thought about Arrows, as they can express sequential and parallel actions, but I don't know if it would be a right way to model the interruptions/recoveries. What do you think about it? Do you know of similar situations and of the way they've been solved? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State Machine and the Abstractions
On 27 May 2011 20:06, Yves Parès wrote: > So I thought about Arrows, as they can express sequential and parallel > actions, but I don't know if it would be a right way to model the > interruptions/recoveries. > What do you think about it? Do you know of similar situations and of the way > they've been solved? Resumption monads? Take a look at William Harrison's work especially the CellSys DSL and the models of operating systems: http://people.cs.missouri.edu/~harrisonwl/publications.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State Machine and the Abstractions
On Fri, May 27, 2011 at 2:06 PM, Yves Parès wrote: > Hello, > > 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 far so good, but there, the only advantage to use a monad instead of a > list of MoveTo's is the do-notation. > And I lack the expression of tests. Using a GADT it could be: > > data Mission a where > MoveTo :: Point -> Mission () > ShootAt :: Unit -> Mission Bool -- If we have destroyed it or not > EnemiesAround :: Mission [Unit] -- The enemies that are maybe in sight > LowHealth :: Mission Bool -- If I should retreat > ... > > -- (Monad Mission could be nicely expressed using Heinrich Apfelmus' > operational package) > > patrol = do > MoveTo point1 > MoveTo point2 > enemies <- EnemiesAround > mapM_ ShootAt enemies > patrol > > Aaaand... here comes the trouble: the actions are done sequentially. My > units will move and then look at enemies, they will not monitor their > environment while they move. > 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. > Moreover, the last line (the recursive call to patrol) is wrong, as it will > restart the patrol from the beginning, and not from where it has been left. > But this could be corrected by addind a test like "which point is the > closest". > Could this be expressed using a new verb in your language? > data Mission a where > MoveTo :: Point -> Mission () > ShootAt :: Unit -> Mission Bool -- If we have destroyed it or not > EnemiesAround :: Mission [Unit] -- The enemies that are maybe in sight > LowHealth :: Mission Bool -- If I should retreat > . . . > Tasks :: [Mission ()] -> Mission () -- goals to be achieved concurrently > Options :: [Mission ()] -> Mission () -- pick one of these You'd then need to analysis and interpretation tools to correctly do the right thing with it. If the game is state-machine driven, you would need sub state-machines for each possibility under 'Tasks' or 'Options'. Antoine > So I thought about Arrows, as they can express sequential and parallel > actions, but I don't know if it would be a right way to model the > interruptions/recoveries. > What do you think about it? Do you know of similar situations and of the way > they've been solved? > > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > > ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] State Machine and the Abstractions
Hello, 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 far so good, but there, the only advantage to use a monad instead of a list of MoveTo's is the do-notation. And I lack the expression of tests. Using a GADT it could be: data Mission a where MoveTo :: Point -> Mission () ShootAt :: Unit -> Mission Bool -- If we have destroyed it or not EnemiesAround :: Mission [Unit] -- The enemies that are maybe in sight LowHealth :: Mission Bool -- If I should retreat ... -- (Monad Mission could be nicely expressed using Heinrich Apfelmus' * operational* package) patrol = do MoveTo point1 MoveTo point2 enemies <- EnemiesAround mapM_ ShootAt enemies patrol Aaaand... here comes the trouble: the actions are done *sequentially*. My units will move and then look at enemies, they will not monitor their environment while they move. 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. Moreover, the last line (the recursive call to patrol) is wrong, as it will restart the patrol from the beginning, and not from where it has been left. But this could be corrected by addind a test like "which point is the closest". So I thought about Arrows, as they can express sequential and parallel actions, but I don't know if it would be a right way to model the interruptions/recoveries. What do you think about it? Do you know of similar situations and of the way they've been solved? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
