4 ms·

State Machines in Go

• amourdezombi 14y 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 14y ago
    Yes, you can even attach a method to a function type.
  • dsymonds 14y 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 14y 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/002939.html http://www.complang.org/pipermail/ragel-users/2013-February/...
• JulianMorrison 14y 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 14y 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 http://www.youtube.com/watch?v=HxaD_trXwRE)
    • JulianMorrison 14y 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.
• ericbb 14y 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 14y 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 http://golang.org/src/pkg/regexp/exec.go
• chubot 14y 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-alternative-to-state-machines/ 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?
  • ericbb 14y 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 http://rosettacode.org/wiki/Synchronous_concurrency
    • chubot 14y 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.
      • ericbb 14y ago
        If I were writing unwrap_protocol in Go, my first take would probably to use an io.ByteReader interface constructed using bufio.NewReader(bytes). The function can then use ReadByte as needed to consume the stream. Apologies if I'm overlooking something. I only skimmed the article. And you're on the right track regarding how channels work. They can be synchronous if you like. Effectively, such channels have no buffering. Also, you don't need to use OS threading at all to solve such problems in Go. It's possible to run code with lots of cooperating goroutines in a single OS thread. Edit: By the way, I'm not familiar with Python so I'm just guessing at how the send method and the yield form work.
• signa11 14y 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 14y 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-in-go-and.html http://blog.golang.org/2011/09/two-go-talks-lexical-scanning...