Re: [go-nuts] Tiny FSM

2017-09-24 Thread 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!

On Sunday, September 24, 2017 at 2:59:31 PM UTC+3:30, Jesper Louis Andersen 
wrote:
>
> 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
>
>
> On Sun, Sep 24, 2017 at 11:47 AM dc0d  
> wrote:
>
>> Nice! At least I've not reinvented any wheel this time! Just rediscovered 
>> it!
>>
>> Thanks!
>>
>> On Sunday, September 24, 2017 at 12:43:51 PM UTC+3:30, Jan Mercl wrote:
>>
>>> On Sun, Sep 24, 2017 at 11:07 AM dc0d  wrote:
>>>
>>> https://youtu.be/HxaD_trXwRE?t=14m7s
>>>
>>> -- 
>>>
>>> -j
>>>
>> -- 
>> 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.
>>
>

-- 
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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [go-nuts] Tiny FSM

2017-09-24 Thread 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


On Sun, Sep 24, 2017 at 11:47 AM dc0d  wrote:

> Nice! At least I've not reinvented any wheel this time! Just rediscovered
> it!
>
> Thanks!
>
> On Sunday, September 24, 2017 at 12:43:51 PM UTC+3:30, Jan Mercl wrote:
>
>> On Sun, Sep 24, 2017 at 11:07 AM dc0d  wrote:
>>
>> https://youtu.be/HxaD_trXwRE?t=14m7s
>>
>> --
>>
>> -j
>>
> --
> 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+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>

-- 
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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [go-nuts] Tiny FSM

2017-09-24 Thread dc0d 
Nice! At least I've not reinvented any wheel this time! Just rediscovered 
it!

Thanks!

On Sunday, September 24, 2017 at 12:43:51 PM UTC+3:30, Jan Mercl wrote:
>
> On Sun, Sep 24, 2017 at 11:07 AM dc0d  
> wrote:
>
> https://youtu.be/HxaD_trXwRE?t=14m7s
>
> -- 
>
> -j
>

-- 
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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [go-nuts] Tiny FSM

2017-09-24 Thread Jan Mercl 
On Sun, Sep 24, 2017 at 11:07 AM dc0d  wrote:

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

-- 

-j

-- 
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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[go-nuts] Tiny FSM

2017-09-24 Thread 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!

-- 
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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.