State Machines in Go

http://denis.papathanasiou.org/?p=1190

by dpapathanasiou • 13 years ago

56 17 13 years ago

denis.papathanasiou.org

signa11• 13 years ago

please consider adding an 'fsm-trace' or some such, which is basically an array of values, each having time, input-msg, current-state and next-state (at the very least), so that debugging these becomes easier...

PuerkitoBio• 13 years ago

The end state could be a map[string]struct{}, since it is only used to test the presence of the string. The bool value is unused, and an empty struct takes no memory, so it would be an admittedly tiny optimization.

Related: Rob Pikes' lexical scanning talk (state machines in Go): http://blog.golang.org/2011/09/two-go-talks-lexical-scanning...

amourdezombi• 13 years ago

One thing that hasn't been articulated in the recent HN articles about Go: method sets can be defined for _any_ type, not just structs.

mseepgood• 13 years ago

Yes, you can even attach a method to a function type.

dsymonds• 13 years ago

Any named type. You can't stick a method on []string; you have to name it first, then add methods to its name (T or *T).

nickbp• 13 years ago

Ragel supports Go output. There's been some recent fixes according to the mailing list, so you may need to get a recent version straight from git: http://www.complang.org/pipermail/ragel-users/2013-February/...

JulianMorrison2• 13 years ago

Personally I'd model a state machine in Go as

    type State int
    type Transition int

    func (s State) Next(t Transition) (State, error) {
      /* doubly nested switch goes here */
    }

zemo• 13 years ago

    type state struct {
        // add any fields you need to persist here
    }

    type transition func(*state) transition

same as in Lexical Scanning in Go (http://www.youtube.com/watch?v=HxaD_trXwRE)

JulianMorrison2• 13 years ago

The reason I didn't do that is a function from state to state is pure in a functional programming sense as well as being simple, free from virtual dispatch and indirection, and thus fast. It's also easy to harness for testing, because it's side effect free and stateless.

If you wanted to extend it to perform actions on state change, I'd extend the return values to (State, Action, error) where Action is "type Action int" as well, and use the Action in another switch. Thus you are free to pick which actions you care about, and test the actions separately from the state engine.

ericbb4• 13 years ago

It's interesting to contrast this design with what Rob Pike presented in his talk on the Go template lexer. Some differences:

(1) Pike's is more static: there is no Machine struct and states are identified with handlers so that there is no table lookup in the loop.

(2) Pike chose to go with a modifiable lexer struct rather than threading a cargo value through the machine.

(3) Pike used nil for all end states.

The main design questions are probably:

(a) Do you need to construct machines at runtime?

(b) Do you need state names available at runtime?

stevvooe• 13 years ago

For an example of a runtime state machine, you may want to take a look at Russ Cox's implementation of NFA simulation for regexp in go [1]. The concepts may be a little impenetrable for a Sunday, but there are some interesting references in the source.

[1] http://golang.org/src/pkg/regexp/exec.go

chubot3• 13 years ago

Since Go has goroutines, I wonder if you can do something like this:

http://eli.thegreenplace.net/2009/08/29/co-routines-as-an-al...

Basically use stack state and goroutines to avoid explicit states. Unlike Python, Go might take multiple threads to do this?

ericbb4• 13 years ago

I was going to translate the example to Go but it's such an uninspiring example because the frame_receiver "coroutine" has no state and might as well have been a simple procedure.

For an simple example--written in many languages including Python and Go--with two stateful coroutines, you can check this out: http://rosettacode.org/wiki/Synchronous_concurrency

chubot3• 13 years ago

Well unwrap_protocol is the one with state. It could be more complex with 2 stateful coroutines, but it still shows the idea with 1. I would be interested in the comparison between Python and Go there, although I can basically imagine it. More interesting is if the nondeterminism of Go has any effect (performance or otherwise).

That is, Go doesn't provide synchronous dataflow. Thanks for the link, I will be looking at that!

edit: or maybe it does with a channel size of 1? The Rob Pike lexer talk mentioned a few times here was doing some trick with that.

State Machines in Go

Related Stories