13,045,001 members (45,717 online)
Tip/Trick
alternative version

#### Stats

12K views
4 bookmarked
Posted 6 Aug 2010

# Implementing state machine transitions with Gödel encoded switch statements

, 6 Aug 2010
 Rate this:
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

## 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.

## Share

 Software Developer (Senior) YouSendIt.com 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.

## You may also be interested in...

 First Prev Next
 Reason for my vote of 5 Nice and practical idea Grof6-Sep-10 1:12 Grof 6-Sep-10 1:12
 Reason for my vote of 5 Very interesting and useful tip! Nuri Ismail17-Aug-10 3:25 Nuri Ismail 17-Aug-10 3:25
 Nice tip ThatsAlok9-Aug-10 19:55 ThatsAlok 9-Aug-10 19:55
 Reason for my vote of 5 A simple but useful tip. José Vitor8-Aug-10 3:40 José Vitor 8-Aug-10 3:40
 Last Visit: 31-Dec-99 18:00     Last Update: 22-Jul-17 1:54 Refresh 1