Merry Christmas all!
I've been working on flushing out the interface to the FiniteStateMachine (FSM) class and have reached a point of near-completion; you may review the source code at revision 17779. The current implementation will let one add states and transitions to an FSM, set/clear an FSM's final state(s), and set/clear an FSM's start state. State enumeration and input symbol acceptance are also supported, along with an implicit error state. For examples on how to accomplish these tasks, please review the Jolt FSM documentation.
The following diagram shows the public interface of the available classes and their methods (less constructors for brevity).
The methods that are missing from this interface are those to serialize/deserialize the FSM, and those that allow you to export the FSM to a QuickGraph data structure. The latter methods are important because they enable the former, and they also provide access to the transitions and states of the FSM (as edges and vertices, respectively). Having access to the graph also allows analysis via QuickGraph algorithms. Thus, the next work item I will take on will be in adding these missing methods, and also to address the serialization/deserialization issues I brought up in my previous post. Some of the work-items that are required for this task are to ensure that transition (edge) labels are created when converting the graph to GLEE, MSAGL, GraphViz, or GraphML, along with making sure a final state is appropriately tagged in the target format.
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.
The following is a code sample that demonstrates the usage of the FSM to validate a Canadian postal code.
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.
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
Wednesday, December 10, 2008
Jolt.NET Intial Release and Future Features
Preparing the Initial Release
internal class List<T>
{
// ... list methods ...
public class Iterator<T>
{
// ... iterator methods ...
}
}
As you can see, the frequency of this situation is rare. You wouldn't be able to use the nested type outside the scope of the assembly, so you wouldn't be able to mock it to begin with. However, such a situation becomes valid when the assembly grants internal access to another assembly. So, I would like to revisit this usage in the future and perhaps add some ability for a client to provide a list of friend assemblies to the ProxyTypeBuilder or ProxyAssemblyBuilder.
Future Features
I first had the idea for Jolt.NET about one year ago after working on a .NET port of the Boost Graph Library (BGL). I had completed a generic Graph<T> data structure with some rudimentary algorithms, including serialization support. It was at that point that I discovered the .NET 1.1 version of QuickGraph, which looked like an abandoned project at the time -- ironically, my initial searches for a BGL port didn't produce anything :(. Today, the QuickGraph authors have implemented all the features that I had intended to, including Linq support! It trully is a formidable BGL port.
After implementing a solid graph data structure, my next goal was to build a generic finite state machine on top of the graph. And so, this will be the next big feature. Jolt.NET will contain a new library with the first feature being a generic finite state machine, using QuickGraph as its underlying data structure.
I also wanted to work on XML assertions for many of the popular managed-language testing tools, NUnit being one of them. This feature would basically extend the NUnit assertion set via a constraint, and allow one to write assertions like the following.
[Test]
public void VerifyXml()
{
Assert.That(GetXmlReader(), Is.Valid(GetXmlSchema()));
Assert.That(GetXmlReader(), Is.EquivalentTo(GetOtherXmlReader()));
Assert.That(GetXmlReader(), Is.EqualTo(GetXmlReader()));
}
After looking at the vision document for NUnit 3.0 and some discussions in NUnit-discuss, it looks like the implementation of feature is already under way, so I won't start work on in for Jolt.NET. Way to go guys!
0
comments
Monday, December 1, 2008
Subscribe to:
Posts (Atom)