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.

More by Author

Get the Free Newsletter!

Subscribe to Developer Insider for top news, trends & analysis

Must Read