About Jolt.NET Libraries

Inspired by the Boost C++ libraries, Jolt.NET aims to complement the .NET Base Class Library (BCL) with algorithms, data structures, and general productivity tools. It is the hope of the authors that the features of Jolt.NET will one day be part of, or represented in the BCL and the .NET Framework.

Draft Implementation of the Finite State Machine

Good day all!

Revision #17566 contains a somewhat usable implementation of the FiniteStateMachine (FSM) class. I say somewhat, because the current class interface and available features are not providing the level of abstractions needed to encapsulate the error-prone tasks of using an FSM.

Overview
Here is a quick overview of what can be done with the current implementation.
  • Programmatically add states and transitions to an FSM.
  • Specify a predicate per transition, denoting which input symbols cause the transition.
  • Construct an enumerator to walk the FSM, one input symbol at a time.
For most cases, one is interested if a collection of input symbols are accepted or rejected by an FSM. With the current implementation, you would need to feed the symbols to the enumerator one at a time and check the enumerator's return value for failure. Also, the FSM has no notion of a final state, so the caller of the enumerator has the burden of checking the validity of the resulting state. All of this is tedious work, and will be encapsulated in the FSM class as part of a future work item.

The following is a code sample that demonstrates the usage of the FSM to validate a Canadian postal code.


// Validates a Canadian postal code (xnx-nxn, where x is a letter and n is a digit; e.g. H0H-0H0).
bool ValidatePostalCode(string postalCode)
{
FiniteStateMachine<char> fsm = new FiniteStateMachine<char>;
fsm.AddState("start");
fsm.AddState("final");
fsm.AddState("letter_0");
fsm.AddState("letter_1");
fsm.AddState("letter_2");
fsm.AddState("hyphen");
fsm.AddState("digit_0");
fsm.AddState("digit_1");

fsm.AddTransition(new Transition<char>("start", "letter_0", Char.IsLetter));
fsm.AddTransition(new Transition<char>("letter_0", "digit_0", Char.IsDigit));
fsm.AddTransition(new Transition<char>("digit_0", "letter_1", Char.IsLetter));
fsm.AddTransition(new Transition<char>("letter_1", "hyphen", ch => ch == '-'));
fsm.AddTransition(new Transition<char>("hyphen", "digit_1", Char.IsDigit));
fsm.AddTransition(new Transition<char>("digit_1", "letter_2", Char.IsLetter));
fsm.AddTransition(new Transition<char>("letter_2", "final", Char.IsDigit));

IFsmEnumerator<char> enumerator = fsm.CreateStateEnumerator("start");
foreach(char symbol in postalCode)
{
if(!enumerator.NextState(symbol)) { return false; }
}

return enumerator.CurrentState == "final";
}

Overall, a bit laborious but it sets a good foundation to get the internals working.

QuickGraph and FSM Persistence
The FSM classes use QuickGraph as the underlying storage for the representation of the FSM. I chose to use this library over the tabular FSM representation because the graph data structure avoids a sparse FSM table, and that the graph library supports graph serialization, persistence, and visualization. A quick comparison of the two data structures shows that navigation speed of the graph from vertex to vertex is on the same order as a table lookup, however the memory overhead is slightly higher due to the management of hash tables versus a single two-dimensional array. In the future, I may consider abstracting the data storage of the FSM into a policy to support the tabular implementation.

I've also been concerned with the ability to serialize and persist a graph that contains dynamic data structures such as anonymous delegates. How does one represent a non-static method call in XML? I've verified that the binary serializer supports method and parameter serialization, but this doesn't bode well with users that want to manage and create an FSM in a human-readable file. So, I'm going to revisit this issue when addressing the serialization work item; the QuickGraph graph visualizers may have some native support to address this issue.

0 comments: