// Finite State Machine
// Peter Salvi, 2009

// As for the problem of forward references, we have two options:
// v1) Declare every state before its first reference.
//     The `defineMultiple' method is aimed to facilitate this.
// v2) Identify states with symbols (ie. immutable sequences, literal strings)
//     This means an extra indirection at every transition using `doString'.

// Transition objects hold an input / state pair
Transition := Object clone
Transition set := method(input, state,
  self input := input
  self state := state
  self)

// The main prototype. Every state is represented as a clone of this.
// The default `nextState' method uses `transitions' to decide the next state.
State := Object clone
State init := method(
  self transitions := List clone)
State addTransition := method(input, state,
  self transitions append(Transition clone set(input, state)))
State nextState := method(input,
  transitions foreach(trans,
    if(trans input == input,
      return(trans state)))
  Exception raise("undefined behaviour"))

// First let's see the version with forward declaration.
// We need a special `stop' state:
stop := State clone
// Now we can define `run'
State run := method(inputs,
  if(inputs isEmpty, "reject",
    next := self nextState(inputs at(0))
    if(next != stop, next run(inputs slice(1)),
      if(inputs size == 1, "accept", "early accept"))))

// Using symbols (strings) only makes it simpler, since we don't need
// the `stop' state (it is less efficient though):
State run := method(inputs,
  if(inputs isEmpty, "reject",
    next := self nextState(inputs at(0))
    if(next != "stop", doString(next) run(inputs slice(1)),
      if(inputs size == 1, "accept", "early accept"))))

// This method defines multiple clones of itself in the sender object.
// This is useful for the implementation using forward declarations.
State defineMultiple := method(
  names := call message arguments foreach(name,
    doString("call sender " .. name .. " := self clone")))

// Usage example for v1:

State defineMultiple(start, foo, bar, baz)

start addTransition(0, foo)
start addTransition(1, bar)

foo addTransition(0, foo)
foo addTransition(1, baz)

bar nextState := method(input, if(input == 0, bar, foo))

baz addTransition(0, stop)

start run(list(1, 0, 1, 1, 0))  // accept
start run(list(0, 1, 0, 0, 1))  // early accept
start run(list(1, 0, 1, 0, 0))  // reject
start run(list(1, 0, 1, 1, 1))  // (exception)

// Usage example for v2:

start := State clone
start addTransition(0, "foo")
start addTransition(1, "bar")

foo := State clone
foo addTransition(0, "foo")
foo addTransition(1, "baz")

bar := State clone
bar nextState := method(input, if(input == 0, "bar", "foo"))

baz := State clone
baz addTransition(0, "stop")

start run(list(1, 0, 1, 1, 0))  // accept
start run(list(0, 1, 0, 0, 1))  // early accept
start run(list(1, 0, 1, 0, 0))  // reject
start run(list(1, 0, 1, 1, 1))  // (exception)