Implementing state machine transitions with Gödel encoded switch statements

Title:       Implementing state machine transitions with Gödel encoded switch statements
Author:      William Bourke
Email:       bill_7991371@yahoo.com
Member ID:   5803131
Language:    C, C++
Platform:    Platforms Independent
Technology:  C++, State machines
Level:       Intermediate
Description: C++ technique for implementing fast, maintainable state machines with Gödel numbering and switch statements
Section      General Programming
SubSection   Algorithms and Recipes
License:     Public domain

Introduction

A common problem with implementing state machines is how to represent a table of branches in a form that can be executed efficiently at run time, but that is clear enough to be maintainable later. Non-trivial state machines can have dozens of states, with several state variables representing each state, and many branches from each state.

enum { Large, Small } Size;
enum { Red, Green, Blue } Color;

if (Size == Large)
    if (Color == Green)
        LargeGreen ();
    else
        LargeRedOrBlue ();
else
    if (Color != Blue)
        SmallRedOrGreen ();
    else
        SmallBlue ();

The example shows a typical implementation, using nested "if" statements. Even with only a few possible values for the two state variables, the transition logic is becoming hard to parse.

A technique that satisfies the two objectives of human clarity and machine efficiency is to use Gödel numbering to represent state transitions in switch statements.

Gödel Numbering

Kurt Gödel was a mathematician who lived in the 20th century. One of his contributions to the field was a method of mapping strings of tokens to a unique natural number.

Gödel's original prime factorization model assigned a number to each symbol in the string, and a prime number to every position in the string. The Gödel number is then calculated as:

p0^So * p1^S1 * ... * pn^Sn

where pi is the positional prime and Si is number assigned to the symbol at that position.

For example, the string BCA could be encoded by assigning each letter a number, A = 1, B = 2, C = 3. Assign the primes 2, 3 and 5 to the 3 possible positions in the string - more primes are needed for a longer string. The Gödel number is then:

2² * 3³ * 5¹ = 4 * 9 * 5 = 180

The original string of symbols can be recovered by factoring the Gödel number into primes and counting the number of each prime.

More generally, Gödel numbering refers to any mapping of strings of symbols to natural numbers, so the natural numbers can be processed in place of the strings of symbols.

C++ Application

The technique discussed here uses a macro to Gödel encode a string of state variables to a constant, then using the constant in the "case" section of a switch statement. Instead of exponentiation and multiplication to encode strings, as in Gödel's original model, this technique uses multiplication and addition. First define a macro that computes the following function

((s0 * p0 + s1) * p1 + .. + Sn-1) * Pn + Sn

where pi is the position multiplier. The position multiplier Pi is selected to be larger than the largest symbol Si-1. Note, there is no last position multiplier. Recoding the size/color example above.

enum { Large, Small } Size;
enum { Red, Green, Blue } Color;

#define SizeColor(size, color) (size * 3 + color)

switch (SizeColor (Size, Color)) {
    case SizeColor (Large, Green):   LargeGreen (); break;
    case SizeColor (Large, Red):
    case SizeColor (Large, Blue):    LargeRedOrBlue (); break;
    case SizeColor (Small, Green):
    case SizeColor (Small, Red):     SmallRedOrGreen (); break;
    case SizeColor (Small, Blue):    SmallBlue (); break;
}

#undef SizeColor

The "#undef" on the last line helps reduce name-space clutter.