dfa

README

dfa

The dfa package implements a deterministic finite automata for use to define stateful computations that are easier understood when transitions are specified explicitly. The API is more interested in using the DFA to clearly define stateful computation, rather than actually being used to recognize languages.

The implementation has all the normal compnents:

• a finite set of states (Q)
• a finite set of input symbols called the alphabet (Σ)
• a transition function (δ : Q × Σ → Q)
• a start state (q0 ∈ Q)
• a set of terminal states (F ⊆ Q)

For each transition, Q × Σ → Q, you must specify a function to run that will supply the next letter, rather than the input being on some "tape."

Importing

import "github.com/lytics/dfa"

Quick Example

    // Define states.
    Starting = dfa.State("starting")
    Finishing = dfa.State("finishing")

    // Define letters.
    Done = dfa.Letter("done")
    Repeat = dfa.Letter("repeat")

    // Error reporting is done by user code.
    var errors []error

    // Define stateful computations.
    starting := func() dfa.Letter {
        if err := do(); err != nil {
            errors = append(errors, err)
            return Repeat
        } else {
            return Done
        }
    }
    finishing := func() {
        fmt.Println("all finished")
    }

    // Order matter, set start and terminal states first.
    d := dfa.New()
    d.SetStartState(Starting)
    d.SetTerminalStates(Finishing)
    d.SetTransition(Starting, Done, Finishing, finishing)
    d.SetTransition(Starting, Repeat, Starting, starting)

    // Calls the given function in a new go-routine,
    // unless there were initialization errors.
    // Blocks until the DFA accepts its input or
    // its Stop() function is called. The final state
    // is returned, and accepted == true if the final
    // state is a terminal state.
    final, accepted := d.Run(starting)

    // Error handling is up to the user application.
    for _, err := range errors {
        ...
    }

Stateful Computations

The functions given when defining the transitions must have one of two types:

• func()
• func() dfa.Letter

Functions associated with a transition ending in a terminal state must give a function that returns no letter. Functions that transition to non-terminal states must return a letter.

GraphViz

Calling the GraphViz method will generate a string of GraphViz text which can then generate a flow diagram of the DFA.

    // States
    Starting := State("starting")
    Running := State("running")
    Resending := State("resending")
    Finishing := State("finishing")
    Exiting := State("exiting")
    Terminating := State("terminating")
    // Letters
    Failure := Letter("failure")
    SendFailure := Letter("send-failure")
    SendSuccess := Letter("send-success")
    EverybodyStarted := Letter("everybody-started")
    EverybodyFinished := Letter("everybody-finished")
    ProducersFinished := Letter("producers-finished")
    Exit := Letter("exit")

    d := New()
    d.SetStartState(Starting)
    d.SetTerminalStates(Exiting, Terminating)

    ...

    d.SetTransition(Starting, EverybodyStarted, Running, ...)
    d.SetTransition(Starting, Failure, Exiting, ...)
    d.SetTransition(Starting, Exit, Exiting, ...)

    d.SetTransition(Running, SendFailure, Resending, ...)
    d.SetTransition(Running, ProducersFinished, Finishing, ...)
    d.SetTransition(Running, Failure, Exiting, ...)
    d.SetTransition(Running, Exit, Exiting, ...)

    d.SetTransition(Resending, SendSuccess, Running, ...)
    d.SetTransition(Resending, SendFailure, Resending, ...)
    d.SetTransition(Resending, Failure, Exiting, ...)
    d.SetTransition(Resending, Exit, Exiting, ...)

    d.SetTransition(Finishing, EverybodyFinished, Terminating, ...)
    d.SetTransition(Finishing, Failure, Exiting, ...)
    d.SetTransition(Finishing, Exit, Exiting, ...)

    fmt.Println(d.GraphViz())

The above code generates the output:

digraph {
    "starting" -> "running"[label="everybody-started"];
    "resending" -> "exiting"[label="exit"];
    "starting" -> "exiting"[label="exit"];
    "running" -> "exiting"[label="failure"];
    "resending" -> "exiting"[label="failure"];
    "finishing" -> "exiting"[label="failure"];
    "starting" -> "exiting"[label="failure"];
    "running" -> "resending"[label="send-failure"];
    "running" -> "finishing"[label="producers-finished"];
    "running" -> "exiting"[label="exit"];
    "resending" -> "running"[label="send-success"];
    "resending" -> "resending"[label="send-failure"];
    "finishing" -> "terminating"[label="everybody-finished"];
    "finishing" -> "exiting"[label="exit"];
}

Which when given to the GraphViz command line tool would visualize the DFA like this:

Documentation

Overview

The dfa package implements a deterministic finite automata to define stateful computations that are easier understood when transitions are specified explicitly. The API is more interested in using the DFA to clearly define stateful computation, rather than actually being used to recognize languages.

Importing

import "github.com/lytics/dfa"

Example

Starting = dfa.State("starting")
Finishing = dfa.State("finishing")

Done = dfa.Letter("done")
Repeat = dfa.Letter("repeat")

var errors []error

starting := func() dfa.Letter {
    if err := do(); err != nil {
        errors = append(errors, err)
        return Repeat
    } else {
        return Done
    }
}

finishing := func() {
    fmt.Println("all finished")
}

d := dfa.New()
d.SetStartState(Starting)
d.SetTerminalStates(Finishing)
d.SetTransition(Starting, Done, Finishing, finishing)
d.SetTransition(Starting, Repeat, Starting, starting)

final, accepted := d.Run(starting)
...

for _, err := range errors {
    ...
}

Index

• type DFA
  • func New() *DFA
  • func (m *DFA) Alphabet() []Letter
  • func (m *DFA) GraphViz() string
  • func (m *DFA) Run(init interface{}) (State, bool)
  • func (m *DFA) RunSynchronous(init interface{}) (State, bool)
  • func (m *DFA) SetStartState(q0 State)
  • func (m *DFA) SetTerminalStates(f ...State)
  • func (m *DFA) SetTransition(from State, input Letter, to State, exec interface{})
  • func (m *DFA) SetTransitionLogger(logger func(State))
  • func (m *DFA) States() []State
  • func (m *DFA) Stop()
• type Letter
  • func (l Letter) String() string
• type State
  • func (s State) String() string

Types

type DFA

type DFA struct {
	// contains filtered or unexported fields
}

func New

func New() *DFA

func (*DFA) Alphabet

func (m *DFA) Alphabet() []Letter

Alphabet of the DFA.

func (*DFA) GraphViz

func (m *DFA) GraphViz() string

GraphViz representation string which can be copy-n-pasted into any online tool like http://graphs.grevian.org/graph to get a diagram of the DFA.

func (*DFA) Run

func (m *DFA) Run(init interface{}) (State, bool)

Run the DFA, blocking until Stop is called or the DFA enters a terminal state. Returns the last state and true if the last state was a terminal state.

func (*DFA) RunSynchronous

func (m *DFA) RunSynchronous(init interface{}) (State, bool)

RunSynchronous runs the DFA without a cancellable goroutine

func (*DFA) SetStartState

func (m *DFA) SetStartState(q0 State)

SetStartState, there can be only one.

func (*DFA) SetTerminalStates

func (m *DFA) SetTerminalStates(f ...State)

SetTerminalStates, there can be more than one. Once entered the DFA will stop.

func (*DFA) SetTransition

func (m *DFA) SetTransition(from State, input Letter, to State, exec interface{})

SetTransition, argument 'exec' must be a function that will supply the next letter if the 'to' state is non-terminal.

func (*DFA) SetTransitionLogger

func (m *DFA) SetTransitionLogger(logger func(State))

func (*DFA) States

func (m *DFA) States() []State

States of the DFA.

func (*DFA) Stop

func (m *DFA) Stop()

Stop the DFA.

type Letter

type Letter string

func (Letter) String

func (l Letter) String() string

type State

type State string

func (State) String

func (s State) String() string