Page 2 of 3
Re: Teach me: Finite State Machines (FSM) - Hardcore Theory
Posted: Thu Jan 22, 2009 9:20 pm
by nor0101
Are you familiar with the Prolog programming language?
Horn clauses make it dead simple to implement an FSA.
Re: Teach me: Finite State Machines (FSM) - Hardcore Theory
Posted: Thu Jan 22, 2009 9:20 pm
by Chris Corbyn
arborint wrote:Yes, if you implement using a State-Transition table then instead of one handler per State, you only need one handler per Event. There are always many, many more States than Events.
This is what I'm really interested in. The project I'll be putting this to use in is JavaScript based (which makes pseudo-code generation easy) and I know that for what I'll be doing, the number of possible combinations of state + event (in my case "state" + "X valued lookahead lexical token") is going to be enormous.
I could achieve my task very inefficiently without a FSM, but with a FSM I can see how the code will sort of "find a considerably narrowed down execution path" in the overall logic.
I'm actually at work at the moment but I'll chime back in later

I can do this table (man, I feel like I'm at school

) in bits and pieces as I work

Re: Teach me: Finite State Machines (FSM) - Hardcore Theory
Posted: Thu Jan 22, 2009 9:21 pm
by Chris Corbyn
nor0101 wrote:Are you familiar with the Prolog programming language?
Horn clauses make it dead simple to implement an FSA.
I'm not, but that sounds interesting. Horn you say?

Re: Teach me: Finite State Machines (FSM) - Hardcore Theory
Posted: Thu Jan 22, 2009 9:29 pm
by nor0101
A quick google search yielded the following PDF - it provides an intro to Prolog along with notes on FSM's.
http://www.google.com/url?sa=t&source=w ... 1-WUxOa2NA
An FSM can be abstracted to a directed graph structure, and I have written a paths algorithm in Prolog... PM if you'd like to take a look, don't want to get too off topic.
Re: Teach me: Finite State Machines (FSM) - Hardcore Theory
Posted: Thu Jan 22, 2009 9:59 pm
by Christopher
Chris Corbyn wrote:This is what I'm really interested in. The project I'll be putting this to use in is JavaScript based (which makes pseudo-code generation easy) and I know that for what I'll be doing, the number of possible combinations of state + event (in my case "state" + "X valued lookahead lexical token") is going to be enormous.
I think you could do something interesting in Javascript because it is already event and callback driven.
Re: Teach me: Finite State Machines (FSM) - Hardcore Theory
Posted: Thu Jan 22, 2009 10:06 pm
by josh
Chris Corbyn wrote:FSMs have all kinds of applications and as far as I understand it, they *should* be fairly commonly understood in computer science (doesn't *every* computer program boil down to a FSM in the end?). I feel a little uneducated in this respect

I actually have never written even a simple FSM so I'm hoping to learn something here.
Yes and no, if a state space is very small FSMs can break the logic down better. I'd say an algorithm is more like a FSM and programs as an overall state have too many separate "agents" interacting to list all state spaces linearly like this.
For example trying to model a real world situation would not work with a FSM, since to model a real world situation you would have to take many state spaces into account, including improbable ones. For instance my roomba vacume runs a FSM, it has several modes, wall finding, etc... I would have thought it would have been a lot better if they made it more ad-hoc ( like not repeatedly ram into objects. That's why I brought up bayesian statistics, instead of representing actions and transitions you use probabilities so your program can be more rational )
Re: Teach me: Finite State Machines (FSM) - Hardcore Theory
Posted: Thu Jan 22, 2009 10:10 pm
by Chris Corbyn
Here's the table in the way @arborint intended it (I hope). It's a little bigger than I intended for this example but at least it's finite
Code: Select all
Start State | Event | End State
----------------------------------------------------------
Engine Off | Turn Ignition On | Engine On
Engine On | Turn Ignition Off | Engine Off
Engine On | Press Gas | Accelerating
Accelerating | Steer Left | Accelerating Turning Left
Accelerating | Steer Right | Accelerating Turning Right
Accelerating | Press Brake | Steady Speed
Acclerating Turning Left | Press Brake | Steady Speed Turning Left
Acclerating Turning Right | Press Brake | Steady Speed Turning Right
Steady Speed | Turn Left | Steady Speed Turning Left
Steady Speed | Turn Right | Steady Speed Turning Right
Steady Speed | Press Gas | Accelerating
Steady Speed | Press Brake | Decelerating
Steady Speed | Press Brake | Decelerating
Steady Speed Turning Left | Press Gas | Accelerating Turning Left
Steady Speed Turning Right | Press Gas | Accelerating Turning Right
Steady Speed Turning Left | Press Brake | Decelerating Turning Left
Steady Speed Turning Right | Press Brake | Decelerating Turing Right
Decelerating | Turn Left | Decelarating Turning Left
Decelerating | Turn Right | Decelerating Turning Right
Decelerating | Press Brake | Engine On
Decelerating | Press Gas | Accelerating
Declerating Turning Left | Press Gas | Accelerating Turning Left
Declerating Turning Right | Press Gas | Accelerating Turning Right
Decelerating Turning Left | Press Brake | Engine On
Declerating Turning Right | Press Brake | Engine On
Re: Teach me: Finite State Machines (FSM) - Hardcore Theory
Posted: Thu Jan 22, 2009 10:13 pm
by Chris Corbyn
@jshpro2
I understand you
I need very strict rules for what I'm doing though... a parser making decisions based on "ad-hoc" logic, probabilities and bayesian logic would do some odd things

Re: Teach me: Finite State Machines (FSM) - Hardcore Theory
Posted: Thu Jan 22, 2009 10:13 pm
by Benjamin
I'm following this thread as I'm sure the need will arise in the future for me to know how to do this.
I just wanted to say however, that from a design standpoint, it would seem practical to me to create data entry pages to build, test and perfect the event/state matrix. Going further, if all of this data was stored in a database table, perhaps code could be written that would use the database matrix to drive the logic, or even output the actual source to drive the application. Thoughts?
Re: Teach me: Finite State Machines (FSM) - Hardcore Theory
Posted: Thu Jan 22, 2009 11:53 pm
by Christopher
Chris Corbyn wrote:Here's the table in the way @arborint intended it (I hope). It's a little bigger than I intended for this example but at least it's finite

Yes, very finite.
Obviously there is only one Current State of the system at any one time, so the state-machine will need know that. (Note that sub-systems can also be state-machines with many internal States, but only one external State)
The simplest implementation would be to code the Event Handlers so that they check the Current State of the system and if appropriate changes the Current State to a new State -- then do the work right then and there. If you don't have too many Events and States that could work well.
A next step would be to decouple the state-machine from the work to be done. So the state-machine receives Events and as appropriate changes the Current State to a new State. The system then reads the Current State of the state-machine after the Event has been processed or it can poll the state-machine. That can be pretty data driven, and can also lend itself to code generation.
For real world situations you often need both States and Transitions. The state machine is still decoupled from the work to be done, but communicates both the new State and how the system needs to change to get there. Transitions are often parametrized functions (in the mathematical sense).
Re: Teach me: Finite State Machines (FSM) - Hardcore Theory
Posted: Fri Jan 23, 2009 1:34 am
by sergio-pro
Sure, there can be a lot of states. And this is only an example implementation.
And now you can generate all states in this code structure, like these guys do:
http://www.nunnisoft.ch/nunnifsmgen/en/home.jsp
Re: Teach me: Finite State Machines (FSM) - Hardcore Theory
Posted: Fri Jan 23, 2009 1:34 am
by Chris Corbyn
Ok, I think we'll do this (if people don't mind), the "obvious" but perhaps lengthy and tedious way first, and then see if we can evolve it and refactor down to something a little easier to add states to.
I'm not too sure what you mean by "Transitions are often parametrized functions (in the mathematical sense)"?
I'm going to cycle home, then have a stab at the simple implementation

Re: Teach me: Finite State Machines (FSM) - Hardcore Theory
Posted: Fri Jan 23, 2009 1:40 am
by Chris Corbyn
@sergio-pro, in a language like PHP or C where passing callbacks around usually requires concrete functions/classes to be written I'd (reluctantly) take a code generation approach for a large FSM. I'm (fingers crossed) not going to have to apply that concept in JavaScript since "code generation" can almost happen on the fly (using function objects).
EDIT | Code generation is the wrong term in JS. I'm just referring to running arbitrary blocks of code without having to generate a function for those blocks of code.
Re: Teach me: Finite State Machines (FSM) - Hardcore Theory
Posted: Fri Jan 23, 2009 4:26 am
by Chris Corbyn
I feel like I lost my evening coding this

Lots of copy & paste and repetitive code!
Code: Select all
<?php
class Car
{
const EVENT_TURN_ENGINE_ON = 1;
const EVENT_TURN_ENGINE_OFF = 2;
const EVENT_PRESS_GAS = 3;
const EVENT_PRESS_BRAKE = 4;
const EVENT_STEER_LEFT = 5;
const EVENT_STEER_RIGHT = 6;
private $_states = array();
private $_currentState;
public function __construct()
{
$this->_states = array(
'engineOff' => new Car_States_EngineOffState($this),
'engineOn' => new Car_States_EngineOnState($this),
'accelerating' => new Car_States_AcceleratingState($this),
'acceleratingTurningLeft' => new Car_States_AcceleratingTurningLeftState($this),
'acceleratingTurningRight' => new Car_States_AcceleratingTurningRightState($this),
'steadySpeed' => new Car_States_SteadySpeedState($this),
'steadySpeedTurningLeft' => new Car_States_SteadySpeedTurningLeftState($this),
'steadySpeedTurningRight' => new Car_States_SteadySpeedTurningRightState($this),
'decelerating' => new Car_States_DeceleratingState($this),
'deceleratingTurningLeft' => new Car_States_DeceleratingTurningLeftState($this),
'deceleratingTurningRight' => new Car_States_DeceleratingTurningRightState($this)
);
$this->setState('engineOff');
}
public function turnEngineOn()
{
$this->_currentState->handleEvent(self::EVENT_TURN_ENGINE_ON);
}
public function turnEngineOff()
{
$this->_currentState->handleEvent(self::EVENT_TURN_ENGINE_OFF);
}
public function pressGas()
{
$this->_currentState->handleEvent(self::EVENT_PRESS_GAS);
}
public function pressBrake()
{
$this->_currentState->handleEvent(self::EVENT_PRESS_BRAKE);
}
public function steerLeft()
{
$this->_currentState->handleEvent(self::EVENT_STEER_LEFT);
}
public function steerRight()
{
$this->_currentState->handleEvent(self::EVENT_STEER_RIGHT);
}
public function isInState($stateName)
{
return ($this->_currentState === $this->_states[$stateName]);
}
public function setState($stateName)
{
$this->_currentState = $this->_states[$stateName];
}
}
/*** States for the Car ***/
interface Car_State
{
public function handleEvent($evt);
}
abstract class Car_States_AbstractState implements Car_State
{
protected $_car;
public function __construct(Car $car)
{
$this->_car = $car;
}
protected function _log($message)
{
printf("%s\n", $message);
}
}
class Car_States_EngineOffState extends Car_States_AbstractState
{
public function handleEvent($evt)
{
switch ($evt)
{
case Car::EVENT_TURN_ENGINE_ON:
$this->_log('Turning engine on');
$this->_car->setState('engineOn');
break;
default:
$this->_log('Not allowed');
}
}
}
class Car_States_EngineOnState extends Car_States_AbstractState
{
public function handleEvent($evt)
{
switch ($evt)
{
case Car::EVENT_TURN_ENGINE_OFF:
$this->_log('Turning engine off');
$this->_car->setState('engineOff');
break;
case Car::EVENT_PRESS_GAS:
$this->_log('Accelerating');
$this->_car->setState('accelerating');
break;
default:
$this->_log('Not allowed');
}
}
}
class Car_States_AcceleratingState extends Car_States_AbstractState
{
public function handleEvent($evt)
{
switch ($evt)
{
case Car::EVENT_PRESS_BRAKE:
$this->_log('Going steady');
$this->_car->setState('steadySpeed');
break;
case Car::EVENT_STEER_LEFT:
$this->_log('Accelerating and turning left');
$this->_car->setState('acceleratingTurningLeft');
break;
case Car::EVENT_STEER_RIGHT:
$this->_log('Accelerating and turning right');
$this->_car->setState('acceleratingTurningRight');
break;
default:
$this->_log('Not allowed');
}
}
}
class Car_States_AcceleratingTurningLeftState extends Car_States_AbstractState
{
public function handleEvent($evt)
{
switch ($evt)
{
case Car::EVENT_PRESS_BRAKE:
$this->_log('Slowing to steady speed, turning left');
$this->_car->setState('steadySpeedTurningLeft');
break;
case Car::EVENT_STEER_RIGHT:
$this->_log('Straightening up, accelerating');
$this->_car->setState('accelerating');
break;
default:
$this->_log('Not allowed');
}
}
}
class Car_States_AcceleratingTurningRightState extends Car_States_AbstractState
{
public function handleEvent($evt)
{
switch ($evt)
{
case Car::EVENT_PRESS_BRAKE:
$this->_log('Slowing to steady speed, turning right');
$this->_car->setState('steadySpeedTurningRight');
break;
case Car::EVENT_STEER_LEFT:
$this->_log('Straightening up, accelerating');
$this->_car->setState('accelerating');
break;
default:
$this->_log('Not allowed');
}
}
}
class Car_States_SteadySpeedState extends Car_States_AbstractState
{
public function handleEvent($evt)
{
switch ($evt)
{
case Car::EVENT_PRESS_GAS:
$this->_log('Speeding up');
$this->_car->setState('accelerating');
break;
case Car::EVENT_PRESS_BRAKE:
$this->_log('Slowing down');
$this->_car->setState('decelerating');
break;
case Car::EVENT_STEER_LEFT:
$this->_log('Going steady, turning left');
$this->_car->setState('steadySpeedTurningLeft');
break;
case Car::EVENT_STEER_RIGHT:
$this->_log('Going steady, turning right');
$this->_car->setState('steadySpeedTurningRight');
break;
default:
$this->_log('Not allowed');
}
}
}
class Car_States_SteadySpeedTurningLeftState extends Car_States_AbstractState
{
public function handleEvent($evt)
{
switch ($evt)
{
case Car::EVENT_PRESS_GAS:
$this->_log('Speeding up whilst turning left... watch out!');
$this->_car->setState('acceleratingTurningLeft');
break;
case Car::EVENT_PRESS_BRAKE:
$this->_log('Slowing down whilst going left');
$this->_car->setState('deceleratingTurningLeft');
break;
case Car::EVENT_STEER_RIGHT:
$this->_log('Straightening up, going steady');
$this->_car->setState('steadySpeed');
break;
default:
$this->_log('Not allowed');
}
}
}
class Car_States_SteadySpeedTurningRightState extends Car_States_AbstractState
{
public function handleEvent($evt)
{
switch ($evt)
{
case Car::EVENT_PRESS_GAS:
$this->_log('Speeding up whilst turning right, careful!');
$this->_car->setState('acceleratingTurningRight');
break;
case Car::EVENT_PRESS_BRAKE:
$this->_log('Slowing down, turning right');
$this->_car->setState('deceleratingTurningRight');
break;
case Car::EVENT_STEER_LEFT:
$this->_log('Straightening up, going steady');
$this->_car->setState('steadySpeed');
break;
default:
$this->_log('Not allowed');
}
}
}
class Car_States_DeceleratingState extends Car_States_AbstractState
{
public function handleEvent($evt)
{
switch ($evt)
{
case Car::EVENT_PRESS_GAS:
$this->_log('Reaching a steady speed');
$this->_car->setState('steadySpeed');
break;
case Car::EVENT_PRESS_BRAKE:
$this->_log('Coming to a standstill');
$this->_car->setState('engineOn');
break;
case Car::EVENT_STEER_LEFT:
$this->_log('Going left, decelerating');
$this->_car->setState('deceleratingTurningLeft');
break;
case Car::EVENT_STEER_RIGHT:
$this->_log('Going right, decelerating');
$this->_car->setState('deceleratingTurningRight');
break;
default:
$this->_log('Not allowed');
}
}
}
class Car_States_DeceleratingTurningLeftState extends Car_States_AbstractState
{
public function handleEvent($evt)
{
switch ($evt)
{
case Car::EVENT_PRESS_GAS:
$this->_log('Picking up speed to a steady pace whilst turning left');
$this->_car->setState('steadySpeedTurningLeft');
break;
case Car::EVENT_PRESS_BRAKE:
$this->_log('Coming to a standstill');
$this->_car->setState('engineOn');
break;
case Car::EVENT_STEER_RIGHT:
$this->_log('Straightening up, decelerating');
$this->_car->setState('decelerating');
break;
default:
$this->_log('Not allowed');
}
}
}
class Car_States_DeceleratingTurningRightState extends Car_States_AbstractState
{
public function handleEvent($evt)
{
switch ($evt)
{
case Car::EVENT_PRESS_GAS:
$this->_log('Reaching a steady speed, turning right');
$this->_car->setState('steadySpeedTurningRight');
break;
case Car::EVENT_PRESS_BRAKE:
$this->_log('Coming to a standstill');
$this->_car->setState('engineOn');
break;
case Car::EVENT_STEER_LEFT:
$this->_log('Straightening up, declerating');
$this->_car->setState('decelerating');
break;
default:
$this->_log('Not allowed');
}
}
}
Example:
Code: Select all
$car = new Car();
$car->pressGas();
$car->turnEngineOn();
$car->pressGas();
$car->pressBrake();
$car->steerLeft();
$car->steerRight();
$car->pressBrake();
$car->steerRight();
$car->turnEngineOff();
$car->pressGas();
$car->steerLeft();
$car->pressBrake();
$car->pressBrake();
$car->turnEngineOff();
Output:
Code: Select all
Not allowed
Turning engine on
Accelerating
Going steady
Going steady, turning left
Straightening up, going steady
Slowing down
Going right, decelerating
Not allowed
Reaching a steady speed, turning right
Straightening up, going steady
Slowing down
Coming to a standstill
Turning engine off
Please don't let me write anything like that again

Re: Teach me: Finite State Machines (FSM) - Hardcore Theory
Posted: Fri Jan 23, 2009 5:24 am
by josh
Yeah... that's what I was getting at. Why not define "constraints" and hueristic cost functions and let the computer search the state space. For instance a solution that drove the car into an obstacle would impede the goal solving and thus would rank lower on the hueristic. That's what I was trying to get at is though technically any logic can be "serialized" into a linear flow like this, that is just one paradigm to define the logic. You would still need a framework that defined the constraints though