Posts Tagged ‘ C++

Generic Finite State Machine Library in C++

This is a little C++ template library I wrote over Christmas break in 2012 that implements a generic Turing Machine customizable to theoretically any task via static data tables that specialize for a specific input and output vectors, and a specific state transition matrix.

The example isn’t completely finished IIRC but that’s okay. It’s done enough to demonstrate the basic concepts that we can write simple little programs that leverage static data tables (e.g. SCDL models) to do whatever we want.

As a side note, while developing this example I found many roads leading me to the strange and wonderful land of  boost::proto. Proto can (and actually should) be used to implement my generic FSM. Why? If we convey all the structural and logical details of our design captured in SCDL to the C++ compiler, then the C++ compiler can optimize the ever-living bajesus out of it.

So for example, in my little library when “clock” edge (actually modelled as a function call) occurs, my simple algorithm performs several table lookup operations. But in my intended use case these tables are static data. I failed to convey to the compiler this detail so what it gave me was a generic library that can handle dynamically reconfigurable FSM (which I don’t need) at  the cost of imposing additional overhead in the case of static tables.

What we would ideally like to be able to do is transform SCDL “machine” models (so the static model data that comprises in the I/O vectors and state transition matrix) into a native runtime that an assembly language dog could not further optimize by hand. So no table lookups, just inline blazing fast code.

Given the simplicity of this little C++ program, later I may extend it a bit and try installing some variation of it server side for performing simulation runs (e.g. turn it into a webservice basically).