Implied State Space Size

‹ Water Transfer Printing | You monkeys you ›

Consider these two if statements:

If statement #1

if (color == RED and has_thorns == TRUE)
  return "Roses are red"
else if (num_petals == 5)
  return "Violets are blue"

If statement #2

if (species == ROSE)
  return "Roses are red"
else if (species == VIOLET)
  return "Violets are blue"

Statement 2 is easier to understand and reason about because it has a smaller "implied state space size." It only reads from a single one-dimensional variable, so the number of possible states is small.

For example, if this were the entire list of flower species supported by our software:

+------------------+
|Species           |
+------------------+
|Anthurium         |
|Bird of Paradise  |
|Carnation         |
|Chrysanthemum     |
|Daffodil          |
|Daisy             |
|Gardenia          |
|Hibiscus          |
|Iris              |
|Lily              |
|Orchid            |
|Plumeria          |
|Rose              |
|Sunflower         |
|Sweet Pea         |
|Tulip             |
|Violet            |
+------------------+

there would be 17 possible states under consideration by the if statement. Some programming languages will allow you to define species as an enumeration, preventing the code from entering an invalid state, and thus making it quick and straightforward to confirm that Statement 2 is free from bugs.

Statement 1 implies a much larger state space. The fact that it reads from three separate variables implies that we may need to consider the Cartesian product of has_thorns, color, and num_petals. For example, if our software supported 8 colors, and flowers with 1–12 petals, then the number of possible states would be 12 × 8 × 2 = 192.

+---------------------------------+---------------------------------+
|         has_thorns = TRUE       |        has_thorns = FALSE       |
+---------------------------------+---------------------------------+
|color         num_petals         |color         num_petals         |
|       1 2 3 4 5 6 7 8 9 10 11 12|       1 2 3 4 5 6 7 8 9 10 11 12|
|red    x x x x x x x x x x  x  x |red    x x x x x x x x x x  x  x |
|pink   x x x x x x x x x x  x  x |pink   x x x x x x x x x x  x  x |
|white  x x x x x x x x x x  x  x |white  x x x x x x x x x x  x  x |
|yellow x x x x x x x x x x  x  x |yellow x x x x x x x x x x  x  x |
|green  x x x x x x x x x x  x  x |green  x x x x x x x x x x  x  x |
|purple x x x x x x x x x x  x  x |purple x x x x x x x x x x  x  x |
|orange x x x x x x x x x x  x  x |orange x x x x x x x x x x  x  x |
|blue   x x x x x x x x x x  x  x |blue   x x x x x x x x x x  x  x |
+---------------------------------+---------------------------------+

There's no way to tell by looking at the code in "If Statement #1" which of these possible states is valid.  For example, blue flowers with 5 petals and no thorns might be a valid combination, but blue flowers with 5 petals and thorns might not be.  The code could have a conditional branch for an invalid situation, or it could be missing a conditional branch for a valid situation, and nobody would know.

If you want to write code which is easy to read, understand and maintain, you should try to globally minimize your code's implied state space size.

Subscribe to All Posts - Wesley Tanaka