During one of classes here, I came across an interesting concept which was somewhat hard to explain to the students. This post is as much an attempt to present the idea as it is an attempt to clear my own thoughts on the matter.
We were writing an implementation of Life and using this to explain TDD and some design principles. As is well known, the rules of life to move from one generation to the next are as follows.
The way we went about this was to first write a few tests and functions to create a grid, to make a cell alive and to make a cell dead. After that, we were writing a function
run_generation to implement the four rules above. We were doing this by writing a test for a rule and then updating the
run_generation function to implement the rule. The first test looked something like this
0 implies a dead cell and
1 a live one.
This is simple enough. It asserts that given such a condition, the cell in the top left corner should die. The implementation of
run_generation that made this pass was like so.
So, this makes the test green and we marked it as such but here’s where things get interesting. My claim was that it’s not just a broken implementation making the test pass but that it’s a complete implementation and which perfectly implements rule 1. And that’s where the confusion started.
The questions that came up were things like “Where are we checking that it has fewer than 2 live neighbours?”, “Won’t it kill the cell even if it has 2 neighbours?” etc.
There’s a notation in classical logic called logical implication. The symbol used is a right arrow (→). It’s often read as “implies” so
p → q is “p implies q”. It’s also sometimes read as “if p, then q”. What does this mean? Logical connective operators like
→ are often described using a truth table. This is a list of all permutations of the inputs and the resulting outputs. So, a truth table for
a and b would be something like this
|a||b||a and b|
This tells us that if
a and b is
False in all cases except if both
b are True. This is a precise and complete way of saying what
a and b means. Now, consider the truth table of →.
|a||b||a → b|
This tells us that that the only way in which
a → b can be
False is if
The expression is equivalent to
b or (not a). Meaning that either
b should be
a should be
False. This means
bis True, then we can be sure that the statement is
Trueregardless of the value of
ais False, then we can be sure that the statement is
Trueregardless of the value of
b. We say that the statement in this case is vacuously true.
If we can guarantee either of these, we can be sure of our implementation.
I’ll stop here lest you accuse me of going all Smullyan on you .
So, if we have a rule that’s of the form
a → b, we just have to make sure this truth table is satisfied. Now let’s look at the rule we’re trying to implement.
Any live cell with fewer than two live neighbours dies.
or stated in the form of a logical implication,
If a live cell has less than two live neighbours, it should die.
“a live cell has less than two neighbours” → “it dies”.
Now, we’re going to try to implement this. A direct translation of the rule would be something like
But this is a logical implication
a → b where
a is “a live cell has less than two neighbours” and
b is “it dies”.
We can implement
a → b by just making sure that
True. Then, as per the truth table, the statement will be true (ie. our code will be correct) regardless of the value of
How do we do that? We simply
kill(cell) and since we start with all cells set to dead (
0), this is
Let’s look at this implementation. Can it ever violate the truth table? Well, the only way in which it can is we let
False even if
True. But, we set everything to dead explicitly so
b is never
False hence the final result is always
So, let’s answer some questions.
Where are we checking that it has fewer than 2 live neighbours?
We don’t need to. If
True, then the statement is
True regardless of the value of
Won’t it kill the cell even if it has 2 neighbours?
That’s a situation where
False, then the statement is
True. This is because we care only about the result if
b can be anything.
You’re just ignoring the if part and making this unconditional. You can’t do that to every if condition. Actually, I can. If this were the only rule, it would be enough but there are other rules too.