Click here to Skip to main content
11,408,835 members (59,997 online)
Click here to Skip to main content

Tagged as

Implementing state machine transitions with Gödel encoded switch statements

, 6 Aug 2010 CPOL
Rate this:
Please Sign up or sign in to vote.
Uses Gödel numbering constants from program state for use with C++ 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:


p0So * p1S1 * ... * pnSn


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:


22 * 33 * 51 = 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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

William Bourke
Software Developer (Senior) YouSendIt.com
United States United States
Bill works at YouSendIt.com, a managed file transfer start-up in Campbell, California.
In his spare time, Bill enjoys mountain biking and designing algorithms.

Comments and Discussions

 
GeneralReason for my vote of 5 Nice and practical idea PinmemberGrof6-Sep-10 2:12 
GeneralReason for my vote of 5 Very interesting and useful tip! PinmemberNuri Ismail17-Aug-10 4:25 
GeneralNice tip PinmemberThatsAlok9-Aug-10 20:55 
GeneralReason for my vote of 5 A simple but useful tip. PinmemberJosé Vitor8-Aug-10 4:40 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.150414.5 | Last Updated 6 Aug 2010
Article Copyright 2010 by William Bourke
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid