Logic-Grid: An Elegant Alternative to Your If-Else Nightmare!

Introduction

Deeply nested if-else and giant switch statements are a common sight in any complex logic implementation. Maintaining such a messy chunk of code is really a nightmare. In this article, I will describe a very effective technique that I call a logic-grid technique. This technique comes in very handy in implementing rule engines and finite state machines (FSM).

Typically, any logic has a set of boolean predicates that are evaluated to obtain a result or to perform an action. In the logic-grid approach, the results are stored in an array and the index of the array is calculated from a bitwise combination of boolean predicates. The key to this approach is that the logic is embedded into data instead of sequence of logic statements. Thinking beyond the bits and bytes, the approach draws parallel with the way people make decisions. We evaluate all the inputs available at a moment and make the best possible decision.

Description

Start by understanding the technique, implementing it, and comparing it to the standard logic statement approaches and also highlight its merits and limitations.

Take a look at the following logic:

if(a) {
   if(b) {
      result=1;
   } else {
      result=2;
   }
} else if(c) {
      if(b){
      result=3;
   } else {
      result=4;
   }
} else if(!c) {
      result=5;
}

As you can see, the result or output depends on the values of variables a, b, and c. Observe that variable a is a priority input. Usually, logic statements are constructed in a way that priority inputs are evaluated first. To convert the logic into a logic-grid, create a table with variables a, b, c, and result as columns. There are three boolean variables; hence, you can have 2^3 = 8 combinations and therefore 8 possible outcomes.

After evaluating each combination and obtaining the results (shown in Table 1):

Table 1

a b c result
1     1     0     1    
1 1 1 1
1 0 0 2
1 0 1 2
0 1 1 3
0 0 1 4
0 0 0 5
0 1 0 5

Note that input a, being a priority input, is entered into the left-most columns in the table or made the most significant bit. Now, re-arrange the table as follows (shown in Table 2)

Table 2

a b c result
0     0     0     5    
0 0 1 4
0 1 0 5
0 1 1 3
1 0 0 2
1 0 1 2
1 1 0 1
1 1 1 1

Observe the re-arranged table. You can easily deduce that each of a, b, and c can be encoded as a bit (1 - true and 0 - false) and the combination of these bits form an index to the array of results.

Here is a C++ code snippet for obtaining the result:

unsigned char getResult (bool a, bool b, bool c)
{
   static const unsigned char results [8] = {5,4,5,3,2,2,1,1};
   unsigned result = 0;
   unsigned char index = 0;    //if a is true, make the 3rd bit
                               //correspond to a 1
   if(a) index = index | 4;    //1xx - represents 3rd bit
   if(b) index = index | 2;    //x1x - represents 2nd bit
   if(c) index = index | 1;    //xx1 - represents 1st bit
   return results[index];      //look up and return the result
}

Here, I have taken a simple scenario only to provide insight into the technique without bogging you down with a complex interplay of logic. In reality, this technique scales superbly with the increase in logical complexity.

The right candidates for applying this technique are finite state machines (FSM), rule engines, and other logic-intensive applications. When I think of an FSM, the electromechanical switch comes to my mind, very much like a hello world program. An electromechanical switch has two states—on-state and off-state—and there can be two possible inputs: on-pressed and off-pressed.

You can model the switch's function by using three inputs and two outputs. The inputs are press-on, press-off, and current-state. The current state of the switch is considered an input because of the next state and output/action dependent on it. The outputs are action taken and next state (shown in Table 3).

Table 3

Press-on Press-off Current state Action Next state
0 0 OFF Don't care OFF
0 0 ON Don't care ON
0 1 OFF Do nothing OFF
0 1 ON Switch OFF OFF
1 0 OFF Switch ON ON
1 0 ON Do nothing ON
1 1 OFF Don't care OFF
1 1 ON Don't care ON

The "Don't care" action is specified for invalid inputs and "Do nothing" indicates that the inputs are valid but that there is no need to change state or do any action. Note that don't care and do nothing actions are used synonymously just to simplify the implementation.

Table 3 can be represented in C++ code as follows:

enum ACTIONS { DO_NOTHING, SWITCH_OFF, SWITCH_ON };
enum STATES { OFF_STATE, ON_STATE };
unsigned actions[] = {DO_NOTHING, DO_NOTHING, DO_NOTHING,
SWITCH_OFF, SWITCH_ON, DO_NOTHING, DO_NOTHING, DO_NOTHING};
unsigned next_state[] = {OFF_STATE, ON_STATE, OFF_STATE, OFF_STATE,
                         ON_STATE, ON_STATE, OFF_STATE, ON_STATE,
                         ON_STATE};

For any usable finite state machine, there are obviously more than two states. In the logic-grid approach, each input can have only two values: 0 or 1. If there are more than two states, you need more than one bit to represent each state. A workaround would be to represent each state as a bit. Now, there are four inputs because the Current state is divided into two inputs, OFF-STATE and ON-STATE (shown in Table 4). This approach requires a 16-byte array as opposed to an 8-byte array in the previous approach.

Table 4

Press-on Press-off Current state
OFF
Current state
ON
Action Next state
0 0 0 0 Invalid Invalid
0 0 0 1 Invalid ON
0 0 1 0 Invalid OFF
0 0 1 1 Invalid Invalid
0 1 0 0 Invalid Invalid
0 1 0 1 Switch OFF OFF
... ... ... ... ... ...
... ... ... ... ... ...

Encoding each state as a bit will lend the logic-grid incomprehensible. The large number of invalid inputs proves this. Moreover, it does not make sense to encode each state as a bit because a system will be in only one state at any one time.

A better approach is to create a 2-dimensional array with states as rows and inputs as columns. If there are 6 states and 4 inputs/signals, you can have a maximum possible 6 * 2^4 = 96 inputs. Otherwise, if you model each state as an input bit, we end up with 2^10 (6+4) inputs, a 1024 combination of inputs. Such an approach is discarded for obvious reasons.

Tables 5 and 6 show the two-dimensional array approach:

Table 5: Current State = OFF

Press-on Press-off Action Next state
0 0 Don't care OFF
0 1 Do nothing OFF
1 0 Switch ON ON
1 1 Don't care OFF

Table 6: Current State = ON

Press-on Press-off Action Next state
0 0 Don't care ON
0 1 Switch OFF OFF
1 0 Do nothing ON
1 1 Don't care ON

The 2D array is defined as follows:

unsigned actions[2][4] = { {DO_NOTHING, DO_NOTHING, SWITCH_ON,
                            DO_NOTHING},
                           {DO_NOTHING, SWITCH_OFF, DO_NOTHING,
                            DO_NOTHING}};
unsigned next_states[2][4] = { {OFF_STATE, OFF_STATE, ON_STATE,
                                OFF_STATE},
                               {ON_STATE, OFF_STATE, ON_STATE,
                                ON_STATE}};

The current state and the bitwise OR of inputs (on-pressed and off-pressed) are used as indexes as follows:

if(pressed_on) input_index = input_index | 2;   //make second bit on
if(pressed_off) input_index = input_index | 1;  //make first bit on
next_state = next_states[current_state][input_index];
action = actions[current_state][input_index];

Summary

Logic-grid is an attractive solution for logic-intensive applications. Because logic is embedded in data as opposed to code, future modifications in logic is a matter of changing the grid data. If the logic involving the existing parameters changes, the logic-grid is easier to maintain. However, adding new parameters or inputs requires expanding and re-evaluating the whole grid. For trivial logic, one is better off using a bunch of if-else statements. As a rule of thumb, use the technique for logic involving more than three parameters.



About the Author

Narendra Venkataraman

senior software engineer at Hewlett Packard Telecom Division. In his spare time, he blogs.

Comments

  • excellent and maintainable solution for logic intense code

    Posted by mpaut on 08/26/2008 10:27pm

    I had 3 inputs and an output that requires different kind of sequential action (no states). I have drawn already a table but did not know how to put it into the machine without if-then's. Then i found this article - now i got this bitmasking stuff! Made for the output sequence another table and bitmasked this again. Only a few lines of code and i can change actions/sequences with a wink! Great!

    Reply
  • embedding logic into data

    Posted by cilu on 07/01/2005 05:37pm

    Just after reading your article, some time ago, I had this great idea of embedding the logic into data (though with a different approach) in a project and it simplified so much the design. So thanks for the spark.

    • that's nice!

      Posted by vnaren on 07/02/2005 11:55am

      guess other folks would benefit if you can say a few words on how you applied:-)

      Reply
    Reply
  • Just make sure you comment your code

    Posted by RoyK on 04/20/2005 11:20am

    Or no one will be able to follow it and you might forget what you did at a latter point in time.

    • Re:Just make sure you comment your code

      Posted by vnaren on 04/22/2005 07:25am

      the comments are inline with code and i think i have given adequate explanation. Please let me know which parts need more explanation.

      Reply
    Reply
  • A very good design aid

    Posted by JoeLeTaxi on 04/20/2005 03:41am

    I started using decision tables (thats what logic grids are after all) back in the early 70's while writing code in a language called FileTab, other dinosaurs like me may remember it!

    • Re: A very good design aid

      Posted by vnaren on 04/22/2005 07:23am

      It is a technique that seems to be less known and least practised. I have seen an multi dimensional array based approach in "Code Complete" but not a bit wise approach i have explained here.

      Reply
    Reply
Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Confused by all the agile advice? Relax! With the Agile for Dummies eBook by your side you'll learn the fundamentals of agile and how to increase the productivity of your software teams while enabling them to produce higher-quality solutions that better fulfill customer needs much faster.

  • Live Event Date: April 22, 2014 @ 1:00 p.m. ET / 10:00 a.m. PT Database professionals — whether developers or DBAs — can often save valuable time by learning to get the most from their new or existing productivity tools. Whether you're responsible for managing database projects, performing database health checks and reporting, analyzing code, or measuring software engineering metrics, it's likely you're not taking advantage of some of the lesser-known features of Toad from Dell. Attend this live …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds