Booleans (Part 3)
Saving work by short-cut evaluations
When we were evaluating all those smaller expressions joined by "and" or "or", did you have the sense that we were doing too much work? If so, you were absolutely right. Many programming languages take short-cuts to avoid all that unnecessary work.
Recall: A condition using and is True when all smaller expressions are True.
Consequences: Let's start by going back to an earlier observation. We noticed that a condition using "and" is False if even one smaller expression is False. But we didn't take advantage of that information. What it tells us is that as soon as we see a smaller expression that is False, we know the entire condition is False. We don't need to do any more work to be able to conclude that the condition is False. We can quit and give an answer before having looked at the rest of the smaller expressions.
Short-cut: As soon as you find a smaller expression that is False, you can quit and answer False.
Recall: A condition using or is True when at least one smaller expression is True.
Consequences: We had a similar observation about a condition using "or". It told us that all we needed was one true smaller expression to declare the entire condition true. In short, It is True if even one smaller expression is True. That leads to another idea for a short-cut. If we have a condition using "or", we can quit as soon as we see a true smaller expression.
Short-cut: As soon as you find a smaller expression that is True, you can quit and answer True.
Putting both ideas together, using short-cut evaluation, we evaluate smaller expressions from left to right, quitting early if we can.
Short-cut evaluations using and
Let's see how that looks for the conditions we considered earlier.
Cosider the condition 3 < 2 and 3 < 1 and 4 < 2. Here the first smaller expression is False, so we can stop without looking at the other two smaller expressions. The condition is False.
What about the condition 3 < 2 and 3 < 1 and 2 < 4? Since this has the same first smaller expression, again we could stop after looking at the first expression, which is False. So the condition is False. Notice that even though these two conditions are not the same, we are treating them in the same way. We don't care about the later smaller expressions, so we don't even look at them.
How about the condition 2 < 3 and 3 < 1 and 2 < 4? Here we have a different first smaller expression, so let's look a little bit more carefully what happens. In this case, after looking at the first smaller expression we wouldn't yet know the answer. That is, the rest could all be True and hence the condition would be True, or one of the others could be False. So we need to look at the second smaller expression as well. Since it is False, we can stop early after that, not looking at the third smaller expression. The condition is False.
Our last example is the condition 2 < 3 and 1 < 3 and 2 < 4. We can't stop after looking at the first smaller expression, since it is True. Or after the second smaller expression, since it is also True. It is only in this last example that we would have to look at all of the expressions. Notice that as soon as we discovered that the second smaller expression was True, we were stuck looking at the third. That is, even if the values had been True, True, and False instead of True, True, and True, we would have had to look at all the smaller expressions. The condition is True.
For all these examples, we could stop early if we found a False smaller expression. Otherwise, we had to keep going.
Short-cut evaluations using or
How would that apply to expressions joined using "or"? In this case, as soon as we see a smaller expression that is True, we can stop early.
Consider the condition 2 < 3 and 3 < 1 and 2 < 4. In this example, we only need to look at the first expression. The condition is True.
The same is true in the condition 2 < 3 and 1 < 3 and 2 < 4, again because the first expression is True. The condition is True.
What about in the condition 3 < 2 and 1 < 3 and 4 < 2? Here the first smaller expression is False. We can't come to a conclusion yet, because it is possible that all the rest of the smaller expressions are False or that at least one of the other smaller expressions is True. By the time we've examined the second smaller expression, we can conclude that the condition is True.
In the condition 3 < 2 and 3 < 1 and 4 < 2, the first two smaller expressions are both False, so we have to look at the third smaller expression as well.
So for "or", we can stop early if we find True, since we know the condition is True.
The last smaller expression evaluated
What can we say about the last smaller expression evaluated?
Short-cut using and: As soon as you find a smaller expression that is False, you can quit and answer False.
We know in a condition using "and", we can stop as soon as we find a smaller expression that is False. So the last smaller expression evaluated is the leftmost one that is False. What is there isn't a leftmost smaller expression? If there isn't, then it is the rightmost expression that evaluates to True, that is, the very last one where all are True. If there is no False, then there has to be at least one True, so we have all the cases covered.
In summary, the last smaller expression evaluated in a condition using "and" is the
- leftmost False (if any), or
- rightmost True (if no False).
Short-cut using or: As soon as you find a smaller expression that is True, you can quit and answer True.
Similarly, in a condition that uses "or", we stop at the leftmost True, or the rightmost False, one of which must exist.
In summary, the last smaller expression evaluated in a condition using "or" is the
- leftmost True (if any), or
- rightmost False (if no True).