newPackage("StateTables",
     Version => "1.0", 
     Date => "June 27, 2004",
     Authors => {{Name => "Daniel R. Grayson", Email => "dan@math.uiuc.edu"}},
     HomePage => "http://www.math.uiuc.edu/~dan/Macaulay2/",
     Headline => "A Macaulay 2 package for building finite state machines",
     DebuggingMode => true
     )
export {stateTable, StateTable, MultipleKey, space, digit, upper, lower, alpha, alphanum, default, testfun}
foo=55
testfun = () -> foo
StateTable = new Type of HashTable
StateTable.synonym = "state table"
fixStateTableEntry := method()
fixStateTableEntry Option := (v) -> fixStateTableEntry(v#0,v#1)
fixStateTableEntry(Thing,Thing) := (a,s) -> {a,s}
new StateTable from List := (StateTable,v) -> hashTable splice (fixStateTableEntry \ v)
stateTable = method(Dispatch => Thing, TypicalValue => StateTable)
stateTable List := StateTable => x -> new StateTable from x
MultipleKey = new Type of BasicList
MultipleKey.synonym = "multiple key"
fixStateTableEntry(MultipleKey,Thing) := (a,s) -> apply(toSequence a, i -> {i,s})
space = new MultipleKey from characters " \f\n\r\t"
digit = new MultipleKey from characters "0123456789"
upper = new MultipleKey from characters "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
lower = new MultipleKey from characters "abcdefghijklmnopqrstuvwxyz"
alpha = join(upper,lower)
alphanum = join(alpha,digit)
StateTable || StateTable := StateTable => (x,y) -> merge(x,y,(f,g) -> c -> (f c; g c;) )

beginDocumentation()
document { Key => "StateTables",
     Headline => "a package for building finite state machines",
     EM "StateTables", " is a package for building finite state machines (or
     automata).  The state of a machine is a state table (of class ", TO "StateTable", ")
     that is used to tell what the next state will be.",
     Subnodes => {
	  "Types:",
	  TO "StateTable",
	  TO "MultipleKey",
	  "Functions:",
	  TO "stateTable",
	  "Methods:",
	  TO (symbol ||,StateTable,StateTable)
	  }}
document { Key => "StateTable", 
     Headline => "the class of all state tables",
     SeeAlso => MultipleKey,
     "State tables are transition tables, implemented as hash tables, for use in the implementation
     of finite state machines.  The state of such a machine can be mostly
     encapsulated in a state table whose keys are the possible inputs and whose
     values are the functions to be applied if the corresponding key is received as input.  A side effect
     of those functions, provided by the user, may be to change the current state.",
     PARA {
	  "In this example, we construct an automaton that returns the length of
	  the largest word inside parentheses in a string, exiting when it
	  encounters the right parenthesis."
	  },
     EXAMPLE {
	  ///outsideParens = stateTable {
/// |	  ///     "(" => c -> goto insideParens,
/// |	  ///     default => identity
/// |	  ///     };///,
	  ///insideParens = stateTable { 
/// |	  ///     alpha => c -> maxlen = max(maxlen,len = len + 1), 
/// |	  ///     space => c -> len = 0,
/// |	  ///     ")" => c -> break maxlen,
/// |	  ///     default => identity
/// |	  ///     };///,
          ///goto = s -> state = s;///,
	  ///accept = c -> if state#?c then state#c c else state.default c;///,
	  ///machine = str -> (
/// |	  ///     len = maxlen = 0;
/// |	  ///     state = outsideParens;
/// |	  ///     scan(characters str, accept));///,
          ///machine "and therefore (run kitty run) it is"///
     	  }     
     }

document { Key => "stateTable",
     Headline => "create a state table",
     Usage => "stateTable p",
     Inputs => {
	  "p" => {
	       ofClass List, " of pairs ", TT "t => f", ", where t is a key
	       or ", ofClass MultipleKey, ", and ", TT "f", " is ", ofClass Function, ""} },
     Outputs => {
	  { ofClass StateTable, " whose keys and values are obtained from ", TT "p" }
	  },
     PARA {},
     "When the automaton provided by the user is in state ", TT "x", " and receives input ", TT "t", " the function 
     ", TT "f", " should be called with argument ", TT "t", ".  The
     function ", TT "f", " is responsible for adjusting the state of the automaton if necesary.",
     PARA {},
     "If ", TT "t", " is ", ofClass MultipleKey, ", such as ", TO "digit", ", then the specified action is provided for each entry of ", TT "t", ".",
     EXAMPLE {
	  "action1 = x -> x;",
	  "action2 = x -> x;",
	  "stateTable { a => action1, b => action2 }",
	  "stateTable { a => action1, digit => action2 }"
	  }
     }

TEST ///
     assert( stateTable { a => sin } || stateTable { b => cos } === stateTable { a => sin, b => cos })
     assert( #( stateTable { a => sin } || stateTable { a => cos } ) === 1 )
     ///

document { Key => "MultipleKey",
     Headline => "the class of all multiple keys",
     "A multiple key is a type of list of keys, which when encountered by ", TO "stateTable", " as
     a key when making a state table, will create entries for each of the keys in 
     the list, all with the same function as value.",
     EXAMPLE {
	  "a = new MultipleKey from {1,2,3}",
	  "f = c -> null;",
	  "stateTable { a => f }",
	  },
     SeeAlso => "StateTable"
     }
document { Key => "alphanum",
     Headline => "recognizing alphanumeric characters",
     Usage => "stateTable { alphanum => f , ...}",
     BaseFunction => stateTable,
     Inputs => { "f" => Function => "" },
     Consequences => { TT "f", " will be run each time an alphanumeric character is presented as input" },
     EXAMPLE {
	  "alphanum",
	  "stateTable { alphanum => identity }"
	  }
     }
document { Key => "space",
     Headline => "recognizing white space characters",
     Usage => "stateTable { space => f , ...}",
     BaseFunction => stateTable,
     Inputs => { "f" => Function => "" },
     Consequences => { TT "f", " will be run each time a white space character is presented as input" },
     "We use ", TO "peek'", " to display the space characters properly in the following example.",
     EXAMPLE {
	  "peek'_2 space",
	  "f = c -> null;",
	  "peek'_2 stateTable { space => f }"
	  }
     }
document { Key => "digit",
     Headline => "recognizing digits",
     Usage => "stateTable { digit => f , ...}",
     BaseFunction => stateTable,
     Inputs => { "f" => Function => "" },
     Consequences => { TT "f", " will be run each time a digit is presented as input" },
     EXAMPLE {
	  "digit",
	  "f = c -> null;",
	  "stateTable { digit => f }"
	  }
     }
document { Key => "upper",
     Usage => "stateTable { upper => f , ...}",
     BaseFunction => stateTable,
     Inputs => { "f" => Function => "" },
     Consequences => { TT "f", " will be run each time an uppercase letter is presented as input" },
     Headline => "recognizing uppercase letters",
     EXAMPLE {
	  "upper",
	  "f = c -> null;",
	  "stateTable { upper => f }"
	  }
     }
document { Key => "lower",
     Usage => "stateTable { lower => f , ...}",
     BaseFunction => stateTable,
     Inputs => { "f" => Function => "" },
     Consequences => { TT "f", " will be run each time a lowercase letter is presented as input" },
     Headline => "recognizing lowercase letters",
     EXAMPLE {
	  "lower",
	  "f = c -> null;",
	  "stateTable { lower => f }"
	  }
     }
document { Key => "alpha",
     Usage => "stateTable { alpha => f , ...}",
     BaseFunction => stateTable,
     Inputs => { "f" => Function => "" },
     Headline => "recognizing letters",
     Consequences => { TT "f", " will be run each time an alphabetic letter is presented as input" },
     EXAMPLE {
	  "alpha",
	  "f = c -> null;",
	  "stateTable { alpha => f }"
	  }
     }
document { Key => (symbol ||, StateTable, StateTable),
     Headline => "merge two state tables",
     Usage => "x || y",
     BaseFunction => stateTable,
     Inputs => { "x" => null, "y" => null },
     Outputs => { {
	       "the keys and values in the output are those occuring in ", TT "x", " or in ", TT "y", ",
	       except that if there is a key that appears in both tables, the new key is a function that calls the two functions
	       provided by ", TT "x", " and ", TT "y", " in turn, with the arguments it received; the return value is discarded."
	       } },
     EXAMPLE {
	  "f = x -> print hi;",
	  "g = y -> print ho;",
	  "x = stateTable {a => f, b => f}",
	  "y = stateTable {b => g}",
	  "w = x || y",
	  "w#b()"},
     "We can use ", TO "code", " to examine the source code for the the new function ", TT "w#b", ", which is embedded
     in the source code that implements the method for computing ", TT "x || y", ".",
     EXAMPLE {
	  "code w#b"
	  }
     }
document { Key => "default",
     Headline => "a symbol used as a key in state tables",
     Usage => "stateTable { default => f, ...}",
     BaseFunction => stateTable,
     Inputs => { "f" => Function => "" },
     Consequences => {
	  {"The symbol ", TT "default", " may be used by your automaton to indicate that the default
	       action for an input not matching any of the other keys in the state table should
	       be to run the function ", TT "f", "."}
	  }
     }