Tiny FSM

[dc0d]

What cons (or pros) there might be in this implementation?

type State func() (State, error)


func (s State) Activate() (funcErr error) {
 next := s
 for next != nil && funcErr == nil {
 next, funcErr = next()
 }
 return
}


type FSM interface {
 Start() State
}

• Calling it a FSM (Finite State Machine) might be inaccurate. But that was what came to my mind at the moment.
  
• I got exited by this (and other amazing things than we can do in Go) but I wanted to make sure using this would not bring much harm into a code-base. I've used it just a bit, but couldn't see through future!
• Sample usage here;

Any feedback is most appreciated!

[Jan Mercl]

On Sun, Sep 24, 2017 at 11:07 AM dc0d <kaveh.sh...@gmail.com> wrote:

https://youtu.be/HxaD_trXwRE?t=14m7s

--

-j

[dc0d]

Nice! At least I've not reinvented any wheel this time! Just rediscovered it!

Thanks!

[Jesper Louis Andersen]

This method is common in functional programming as well. You are, essentially, computing a fixed point over the state machine (or in Rob's example a lexer state). That is, you are taking a set of state transitions and turning them into a function when looked at from the "outside".

If you have a description of a problem which can be cast as a state table, the method is often good. You can just 1-1 verbatim copy the state table into code and have the system derive a correct function out of it for you, which you can then call. Updates to the state machine naturally grafts itself into the correct points in the state system.

Another useful feature of such a representation is that it allows you to write different interpreters for your state machine. You can, for instance, add an operation in between each state transition quite naturally by altering your runner. Do something before you call the next state. If you define the correct methods, this allows you to naturally add debugging aids to a system.

The next level up in representations such as these are tagless-final representations[0], in which the state machine is written as an abstract DSL. By implementing different concrete functions for the abstract specification, you can interpret the same piece of code differently in different contexts. It is popular to use as a way to handle testing, or by writing a self-certifying FSM: verify the invariant between each function call. It also allows one to write optimization passes on the DSL and stack them up on top of each other. Or extend the DSL implementation gradually in a modular way.

A similar idea are those of "free constructions". Roughly speaking a construction is "free" if it "doesn't throw away information". For instance, the term "2 + 2" bears more information than "4". This is because if we have the result of the computation, 4, we don't know if this was computed from "1 + 3", "3 + 1", "0 + 4", "(2*2) + (3*5) - 15" and so on. Now, if we squint our eyes a bit and look at *programs* as free constructions. They are not throwing away essential information, and this means we can interpret the free program in different ways, e.g, by adding invariants, run the program either serially or parallel etc. Haskell defines a "Free Monad" for this purpose.

[0] http://okmij.org/ftp/tagless-final/index.html

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[dc0d]

I've done F# for some years before but it's not always very fruitful to apply practices from other domains. Also I've already implemented other version of the runner engine (the Activate method) for (as an example) handling a final state. But I've been discouraged from doing many things in Go, so I always try to double check if it's a good approach or not.

Keeping track of not-reduced state was a nice trick! I feel it can be used for undo scenarios (backtracking?).

Thanks for the informative and instructive reply!