Enable JavaScript.

Translating Decision Tables

Recently, I got to thinking about the little-known technique I used in 1970 to translate decision tables into PL/I programs. I don't know who originated the technique, but I had some fun with it at the time. Here's an explanation for the programmers among my readers (and for anyone else interested in logic).

First, a quick review of Boolean logic (named after George Boole, a 19th century English mathematician). We begin by defining a bit as a unit of memory that can hold one of two values, of which '1' = true and '0' = false. A bit string is a series of such bits, such as '1010'. Next, we define some functions that operate on bits. The following tables summarize the operations of the functions AND, OR and NOT for the bit strings a and b.

  a | b |AND       a | b | OR       a |NOT 
+---+---+---+    +---+---+---+    +---+---+
| 1 | 1 | 1 |    | 1 | 1 | 1 |    | 1 | 0 |
+---+---+---+    +---+---+---+    +---+---+
| 1 | 0 | 0 |    | 1 | 0 | 1 |    | 0 | 1 |
+---+---+---+    +---+---+---+    +---+---+
| 0 | 1 | 0 |    | 0 | 1 | 1 |
+---+---+---+    +---+---+---+
| 0 | 0 | 0 |    | 0 | 0 | 0 |
+---+---+---+    +---+---+---+ 

Now, what's a decision table and why should programmers use them?

Most programs contain statements of the form:

IF SEX = 'male'
   THEN DO (some actions);
   ELSE DO (some actions);

This is pretty simple, but what if the program logic involves not only SEX but also AGE, HEIGHT and WEIGHT? The typical solution to such multi-variable logic is to code a series of IF, THEN, ELSE statements, essentially a branching tree of conditions and actions, as in the following PL/I code.

IF SEX = 'male'
   THEN IF HEIGHT > 6.0
      THEN DO /* Rule R1 */
         ( action 1;
           action 2;
           action 3;
         );
      ELSE DO /* Rule R2 */
         ( action 2 );
   ELSE IF HEIGHT > 6.0
      THEN DO /* Rule R3 */
         ( action 3 );
      ELSE DO /* Rule R4 */
         ( action 1;
           action 2;
         );

This isn't very complicated, but notice that tests and actions are repeated. This isn't good programming practice. The exponential number of rules generated by a larger number of tests makes such coding a lot more difficult. The programmer should first determine all of the possible combinations of conditions and actions. Starting right out coding IF, THEN, ELSE statements without prior analysis work can be a recipe for disaster — however common this practice happens to be.

Decision tables are an alternative way of analyzing a set of conditions and specifying the actions to be performed under those conditions. Here is an example of a simple decision table that tests only two conditions:


                             |    Rules      |
                             | R1  R2  R3  R4|
               ==============+===+===+===+===+
    Tests T1:  SEX = 'male'  | 1 | 1 | 0 | 0 |
          T2:  HEIGHT > 6.0  | 1 | 0 | 1 | 0 |
               ==============+===+===+===+===+
  Actions A1:  action 1      | X |   |   | X |
               --------------+---+---+---+---+
          A2:  action 2      | X | X |   | X |
               --------------+---+---+---+---+
          A3:  action 3      | X |   | X |   |
               ==============+===+===+===+===+

Since there are two conditions to be tested, there are 22, or 4, possible rules that associate test results (in which 1 = TRUE and 0 = FALSE) with one or more actions (indicated by X's). An important thing to note is that all possible rules are identified by the decision table, making it impossible to miss any combinations of conditions. Note also that each action can be required for more than one rule.

Decision tables can be translated into code by logical operations on bit strings. But first, here are some things to remember about PL/I:

  • When the result of the condition clause of an IF statement is a bit string that contains '1' bit in any position, the condition is true. For example,
    IF '0100'B THEN DO (some actions) does the actions.
  • Text between /* and */ is a comment and not executable.

Now, to translate our simple decision table into PL/I:

  1. Declare the following variables as bit strings:
    DECLARE T1 BIT(4) INIT('1100'B) STATIC;
    /* The negation of this bit string is '0011' */
    DECLARE T2 BIT(4) INIT('1010'B) STATIC;
    /* The negation of this bit string is '0101' */
    DECLARE (R1, R2, R3, R4, A1, A2, A3 ) BIT(4);
    DECLARE RESULTS  BIT(4); 
    
  2. For each rule, AND the bit strings defined for each test, as specified by the rule:
    R1 = T1 AND T2;
    /* ('1100' AND '1010') = '1000' */
    R2 = T1 AND (NOT T2);
    /* ('1100' AND '0101') = '0100' */
    R3 = (NOT T1) AND T2;
    /* ('0011' AND '1010') = '0010' */
    R4 = (NOT T1) AND (NOT T2);
    /* ('0011' AND '0101') = '0001' */
    
  3. For each action, OR the rule bit strings for which the action is to be done:
    A1 = R1 OR R4;
    /* '1000' OR '0001' is '1001' */
    A2 = R1 OR R2 OR R4;
    /* '1000' OR '0100' OR '0001' is '1101' */
    A3 = R1 OR R3;
    /* '1000' OR '0010' is '1010' */ 
    
  4. For each case where the program logic is to be evaluated (for example, for each employee in a database), the following PL/I code would then be executed. Note that no tests or actions are repeated.
    /* Test conditions */
       IF SEX = 'male' 
         THEN RESULTS = T1;
         ELSE RESULTS = NOT T1;
       IF HEIGHT > 6.0
         THEN RESULTS = RESULTS AND T2;
         ELSE RESULTS = RESULTS AND (NOT T2);
    /* Perform selected actions */
       IF RESULTS AND A1 
         THEN DO (action 1);
       IF RESULTS AND A2
         THEN DO (action 2);
       IF RESULTS AND A3
         THEN DO (action 3);
    

Pretty simple, isn't it? And efficient too because steps 1 to 3 only have to be done once. Great, but does this technique really work? Let's try it out.

  1. /* Set variable values for test of R1 */
       SEX = 'male';
       HEIGHT = 6.5;
    /* Test conditions */
       IF SEX= 'male'
       /* True in this case */
         THEN RESULTS = T1;
         /* '1100' */
         ELSE RESULTS = NOT T1;
         /* '0011' */
       IF HEIGHT > 6.0
       /* True in this case */
         THEN RESULTS = RESULTS AND T2;
         /* ('1100' AND '1010') = '1000' */
         ELSE RESULTS = RESULTS AND (NOT T2);
         /* ('1100' AND '0101') = '0100' */
    /* Perform selected actions */
       IF RESULTS AND A1
       /* ('1000' AND '1001') = '1000' */
         THEN DO (action 1);
         /* True, do action 1 */
       IF RESULTS AND A2
       /* ('1000' AND '1101') = '1000' */
         THEN DO (action 2);
         /* True, do action 2 */
       IF RESULTS AND A3
       /* ('1000' AND '1010') = '1000' */
         THEN DO (action 3);
         /* True, do action 3 */
    
  2. /* Set variable values for test of R2 */
       SEX = 'male';
       HEIGHT = 5.5;
    /* Test conditions */
       IF SEX = 'male'
       /* True in this case */
         THEN RESULTS = T1;
         /* '1100' */
         ELSE RESULTS = NOT T1;
         /* '0011' */
       IF HEIGHT > 6.0
       /* False in this case */
         THEN RESULTS = RESULTS AND T2;
         /* ('1100' AND '1010') = '1000' */
         ELSE RESULTS = RESULTS AND (NOT T2);
         /* ('1100' AND '0101') = '0100' */
    /* Perform selected actions */
       IF RESULTS AND A1
       /* ('0100' AND '1001') = '0000' */
         THEN DO (action 1);
         /* False, do not do action 1 */
       IF RESULTS AND A2
       /* ('0100' AND '1101') = '0100' */
         THEN DO (action 2);
         /* True, do action 2 */
       IF RESULTS AND A3
       /* ('0100' AND '1010') = '0000' */
         THEN DO (action 3);
         /*  False, do not do action 3 */
    
  3. /* Set variable values for test of R3 */
       SEX = 'female';
       HEIGHT = 6.5;
    /* Test conditions */
       IF SEX= 'male'
       /* False in this case */
         THEN RESULTS = T1; 
         /* '1100' */
         ELSE RESULTS = NOT T1;
         /* '0011' */
       IF HEIGHT > 6.0
       /* True in this case */ 
         THEN RESULTS = RESULTS AND T2;
         /* ('0011' AND '1010') = '0010' */
         ELSE RESULTS = RESULTS AND (NOT T2);
         /* ('0011' AND '0101') = '0010' */
    /* Perform selected actions */
       IF RESULTS AND A1
       /* ('0010' AND '1001') = '0000' */
         THEN DO (action 1);
         /* False, do not do action 1.*/
       IF RESULTS AND A2
       /* ('0010' AND '1101') = '0000' */
         THEN DO (action 2);
         /*  False, do not do action 2. */
       IF RESULTS AND A3
       /* ('0010' AND '1010') = '0010' */
         THEN DO (action 3);
         /*  True, do action 3 */
    
  4. /* Set variable values for test of R4 */
       SEX = 'female';
       HEIGHT = 6.5;
    /* Test conditions */
       IF SEX= 'male'
       /* False in this case */
         THEN RESULTS = T1;
         /* '1100' */
         ELSE RESULTS = NOT T1;
         /* '0011' */
       IF HEIGHT > 6.0
       /* False in this case */
         THEN RESULTS = RESULTS AND T2;
         /* ('0011' AND '1010') = '0010' */
         ELSE RESULTS = RESULTS AND (NOT T2); 
         /* ('0011' AND '0101') = '0001' */
    /* Perform selected actions */
       IF RESULTS AND A1
       /* ('0001' AND '1001') = '0001' */
         THEN DO (action 1);
         /* True, do action 1 */
       IF RESULTS AND A2
       /* ('0001' AND '1101') = '0001' */
         THEN DO (action 2);
         /* True, do action 2 */
       IF RESULTS AND A3
       /* ('0001' AND '1010') = '0000' */
         THEN DO (action 3);
         /* False, do not do action 3. */
    

So the bit string technique does work in all cases. It can also be used for decision tables that test more than two conditions. However, it requires bit strings of length 2n, where n is the number of conditions. Thus, it quickly becomes awkward and inefficient for larger values of n. The most complex decision table that I personally translated with this technique tested five conditions, thereby requiring bit strings of length 25 or 32.

Traduction des tables de décision

Récemment, j'ai pensé à la technique peu su que j'ai utilisée dans les années 1970 pour traduire les tables de décision à programmes en PL/I. Je ne sais pas qui était l'auteur de cette technique, mais j'ai eu grand plaisir à le faire à ce moment-là. Voici une explication pour les programmeurs parmi mes lectures (et pour d'autres qui auraient de l'intéret en logique).

D'abord, une brève revue de Boolean logique (nommé d'après George Boole, un mathématicien anglais du 19e siècle). Nous commençons avec la définition d'un bit, l'unité de mémoire qui tient un entre deux valeurs, de laquelle '1' = vrai et '0' = faux. Une chaîne de bits est une série de tels bits, par exemple, '1010'. Puis, nous définissons quelques fonctions qui opèrent sur des bits. Les tables suivantes résument les opérations des fonctions AND, OR et NOT pour les chaînes de bits a and b.

  a | b |AND       a | b | OR       a |NOT 
+---+---+---+    +---+---+---+    +---+---+
| 1 | 1 | 1 |    | 1 | 1 | 1 |    | 1 | 0 |
+---+---+---+    +---+---+---+    +---+---+
| 1 | 0 | 0 |    | 1 | 0 | 1 |    | 0 | 1 |
+---+---+---+    +---+---+---+    +---+---+
| 0 | 1 | 0 |    | 0 | 1 | 1 |
+---+---+---+    +---+---+---+
| 0 | 0 | 0 |    | 0 | 0 | 0 |
+---+---+---+    +---+---+---+ 

Maintenant, qu'est-ce qu'une table de décision et pour-quoi elle devrait être utilisée par des programmeurs ?

La plupart des programmes comprennent des phrases de la forme suivante :

IF SEX = 'mâle'
   THEN DO (des actions);
   ELSE DO (des actions);

Cela est assez simple. Mais, si la logique du programme ne comprend pas que seulement SEX, mais aussi AGE, TAILLE et POIDS ? La solution typique à une telle logique de plusieurs variables est de coder une série des phrases IF, THEN, ELSE, essentiellement un arbre à plusieurs branches des conditions et des actions, comme dans le code en PL/I suivante.

IF SEX = 'mâle'
   THEN IF TAILLE > 6.0
      THEN DO /* Règle R1 */
         ( action 1;
           action 2;
           action 3;
         );
      ELSE DO /* Règle R2 */
         ( action 2 );
   ELSE IF TAILLE > 6.0
      THEN DO /* Règle R3 */
         ( action 3 );
      ELSE DO /* Règle R4 */
         ( action 1;
           action 2;
         );

Ce n'est pas trop complique, mais remarquez que quelques essais et actions sont répétés. Cela n'est pas la meilleure pratique en programmation. Le nombre exponentiel de règles qui sont produits par un plus grand nombre d'essais rendent une telle programmation beaucoup plus difficile. D'abord, le programmeur doit déterminer toutes les combinaisons possibles des conditions et des actions. Commençant immédiatement à coder des phrases IF, THEN, ELSE sans avoir à faire l'analyse d'abord est une recette pour le désastre — bien que cette pratique soit commun.

Les tables de décision sont une façon alternative d'analyser une série de conditions et de spécifier des actions à faire pour ces conditions. Voici un exemple d'une simple table de décision qui essaie seulement deux conditions :


                             |    Règles     |
                             | R1  R2  R3  R4|
               ==============+===+===+===+===+
   Essais T1:  SEX = 'mâle'  | 1 | 1 | 0 | 0 |
          T2:  TAILLE > 6.0  | 1 | 0 | 1 | 0 |
               ==============+===+===+===+===+
  Actions A1:  action 1      | X |   |   | X |
               --------------+---+---+---+---+
          A2:  action 2      | X | X |   | X |
               --------------+---+---+---+---+
          A3:  action 3      | X |   | X |   |
               ==============+===+===+===+===+

Depuis qu'il y a deux conditions à essayer, il y a 22, ou 4, règles qui associent les résultats des essais (pour lesquels 1 = TRUE et 0 = FALSE) avec un ou plus d'actions (indiquée par des X). Une chose importante à noter est que toutes les règles possibles sont identifiées par la table de décision. Il est impossible de manquer quelques combinaisons de conditions. Notez aussi que chaque action peut être utilisé par plusieurs règles.

Les tables de décision peuvent traduire en code par des opérations logiques sur des chaînes de bits. Mais d'abord, voici quelques choses à se souvenir à propos de PL/I :

  • Les mots définis par PL/I sont en anglais. Dans les exemples dans cette article, on peut les traduire ainsi :
    IF = si, THEN = puis, ELSE = autre, DO = faites,
    AND = et, OR = ou, NOT = non, TRUE = vrai, FALSE = faux
    .
  • Les noms des variables et les commentaires peuvent être en français.
  • Quand le résultat de la proposition d'un IF phrase est un chaîne de bits qui inclut '1' dans quelques positions, la proposition est vraie. Par exemple,
    IF '0100'B THEN DO (des actions) fait des actions.
  • Le texte entre /* et */ est un commentaire et il n'est pas exécutable.

Et maintenant, voici comment on peut coder notre simple table de décision en PL/I :

  1. Déclarer les variables suivantes comme des chaînes de bits :
    DECLARE T1 BIT(4) INIT('1100'B) STATIC;
    /* Le négation est '0011' */
    DECLARE T2 BIT(4) INIT('1010'B) STATIC;
    /* Le négation est '0101' */
    DECLARE (R1, R2, R3, R4, A1, A2, A3 ) BIT(4);
    DECLARE RESULTATS  BIT(4);
    
  2. Pour chaque règle, AND les chaînes de bits déclarer pour chaque essai, tel que spécifié par la règle :
    R1 = T1 AND T2;
    /* ('1100' AND '1010') = '1000' */
    R2 = T1 AND (NOT T2);
    /* ('1100' AND '0101') = '0100' */
    R3 = (NOT T1) AND T2;
    /* ('0011' AND '1010') = '0010' */
    R4 = (NOT T1) AND (NOT T2);
    /* ('0011' AND '0101') = '0001' */
    
  3. Pour chaque action, OR les chaînes de bits pour lesquels l'action doit être faite :
    A1 = R1 OR R4;
    /* ('1000' OR '0001') = '1001' */
    A2 = R1 OR R2 OR R4;
    /* ('1000' OR '0100' OR '0001') = '1101' */
    A3 = R1 OR R3;
    /* ('1000' OR '0010') = '1010' */
    
  4. Pour chaque cas où la logique du programme doit être évaluée (par exemple, pour chaque employé dans une base de donner), le PL/I code suivant serait exécuté. Notez bien qu'il n'y a pas d'essais ou d'actions qui sont repetés.
    /* Essayez les conditions */
       IF SEX = 'mâle'
         THEN RESULTATS = T1;
         ELSE RESULTATS = NOT T1;
       IF TAILLE > 6.0
         THEN RESULTATS = RESULTATS AND T2;
         ELSE RESULTATS = RESULTATS AND (NOT T2);
    /* Exécutez les actions choisi */
       IF RESULTATS AND A1 
         THEN DO (action 1);
       IF RESULTATS AND A2
         THEN DO (action 2);
       IF RESULTATS AND A3
         THEN DO (action 3);
    

Très simple, n'est-ce pas ? Et aussi efficace parce que les pas 1 à 3 doivent être faits seulement une fois. Bien, mais est-ce que cette technique marche vraiment ? Essayons-la.

  1. /* Mettez les valeurs dans les variables 
       pour le test de R1 */
       SEX = 'mâle';
       TAILLE = 6.5;
    /* Essayez les conditions */
       IF SEX= 'mâle'
       /* Vrai en ce cas */
         THEN RESULTATS = T1;
         /* '1100' */
         ELSE RESULTATS = NOT T1;
         /* '0011' */
       IF TAILLE > 6.0
       /* Vrai en ce cas */
         THEN RESULTATS = RESULTATS AND T2;
         /* ('1100' AND '1010') = '1000' */
         ELSE RESULTATS = RESULTATS AND (NOT T2);
         /* ('1100' AND '0101') is '0100' */
    /* Exécutez les actions choisi */
       IF RESULTATS AND A1
      /* ('1000' AND '1001') = '1000' */
         THEN DO (action 1);
         /* Vrai, faites l'action 1 */
       IF RESULTATS AND A2
      /* ('1000' AND '1101') = '1000' */
         THEN DO (action 2);
         /* Vrai, faites l'action 2 */
       IF RESULTATS AND A3
      /* ('1000' AND '1010') = '1000' */
         THEN DO (action 3);
         /* Vrai, faites l'action 3 */
    
  2. /* Mettez les valeurs dans les variables 
       pour le test de R2 */
       SEX = 'mâle';
       TAILLE = 5.5;
    /* Essayez les conditions */
       IF SEX = 'mâle'
       /* Vrai en ce cas */
         THEN RESULTATS = T1;
         /* '1100' */
         ELSE RESULTATS = NOT T1;
         /* '0011' */
       IF TAILLE > 6.0
       /* Faux en ce cas */
         THEN RESULTATS = RESULTATS AND T2;
         /* ('1100' AND '1010') is '1000' */
         ELSE RESULTATS = RESULTATS AND (NOT T2);
         /* ('1100' AND '0101') is '0100' */
    /* Exécutez les actions choisi */
       IF RESULTATS AND A1
       /* ('0100' AND '1001') = '0000' */
         THEN DO (action 1);
         /* Faux, ne faites pas l'action 1 */
       IF RESULTATS AND A2
       /* ('0100' AND '1101') = '0100' */
         THEN DO (action 2);
         /* Vrai, faites l'action 2 */
       IF RESULTATS AND A3
       /* ('0100' AND '1010') = '0000' */
         THEN DO (action 3);
         /* Faux, ne faites pas l'action 3 */
    
  3. /* Mettez les valeurs dans les variables 
       pour le test de R3 */
       SEX = 'femelle';
       TAILLE = 6.5;
    /* Essayez les conditions */
       IF SEX= 'mâle'
       /* Faux en ce cas */
         THEN RESULTATS = T1;
         /* '1100' */
         ELSE RESULTATS = NOT T1; 
         /* '0011' */
       IF TAILLE > 6.0
       /* Vrai en ce cas */
         THEN RESULTATS = RESULTATS AND T2;
         /* ('0011' AND '1010') = '0010' */
         ELSE RESULTATS = RESULTATS AND (NOT T2);
         /* ('0011' AND '0101') = '0010' */
    /* Exécutez les actions choisi */
       IF RESULTATS AND A1
       /* ('0010' AND '1001') = '0000' */
         THEN DO (action 1);
         /* Faux, ne faites pas l'action 1.*/
       IF RESULTATS AND A2
       /* ('0010' AND '1101') = '0000' */
         THEN DO (action 2);
         /* Faux, ne faites pas l'action 2. */
       IF RESULTATS AND A3
       /* ('0010' AND '1010') = '0010' */
         THEN DO (action 3);
         /* Vrai, faites l'action 3 */
    
  4. /* Mettez les valeurs dans les variables 
       pour le test de R4 */
       SEX = 'femelle';
       TAILLE = 5.5;
    /* Essayez les conditions */
       IF SEX= 'mâle'
       /* Faux en ce cas */
         THEN RESULTATS = T1;
         /* '1100' */
         ELSE RESULTATS = NOT T1;
         /* '0011' */
       IF TAILLE > 6.0
       /* Faux en ce cas */
         THEN RESULTATS = RESULTATS AND T2;
         /* ('0011' AND '1010') is '0010' */
         ELSE RESULTATS = RESULTATS AND (NOT T2); 
         /* ('0011' AND '0101') = '0001' */
    /* Exécutez les actions choisi */
       IF RESULTATS AND A1
       /* ('0001' AND '1001') = '0001' */
         THEN DO (action 1);
         /* Vrai, faites l'action 1 */
       IF RESULTATS AND A2
       /* ('0001' AND '1101') = '0001' */
         THEN DO (action 2);
         /* Vrai, faites l'action 2 */
       IF RESULTATS AND A3
       /* ('0001' AND '1010') = '0000' */
         THEN DO (action 3);
         /* Faux, ne faites pas l'action 3. */
    

Alors, la technique de chaîne de bits marche dans tous les cas. Elle pourrait aussi être utilisée pour les tables de décision qui essaient plus que de deux conditions. Cependant, ils ont besoin de chaînes de bits d'une longueur de 2n, où n répresente le nombre des conditions. Ainsi, il devient rapidement malcommode et inefficace pour les n à grande valeur. La table de décision la plus complexe que j'ai traduite moi-même avec cette technique a essayé cinq conditions et a eu besoin des chaînes de bits d'une longueur de 25 ou 32.