Would you like tea or coffee?
Or both?
This is an ongoing series. Please check out the collection for the rest of the articles.
Like many other languages, English is replete with grammatical ambiguities. Fortunately, we humans have a wonderfully sophisticated grasp of language, allowing us to weave and unweave complex, ambiguous expressions with little conscious effort. Sometimes we make mistakes when trying to figure out ambiguities but our interpretations are usually correct, or at least correct often enough to tolerate the occasional misunderstandings.
“Would you like tea or coffee?” is a classic example. The word “or” has two distinct meanings:
- A choice between two mutually exclusive options.
- A three-way choice between one option, the other, and both at once.
In the example above, it is implied that you may choose either tea or coffee, but not both; “or” follows the Definition 1. On the other hand, “Would you like milk or sugar in your tea?” implies that you may have only milk, only sugar, or both milk and sugar; “or” follows Definition 2. The only way to tell which “or” is being used is to look at the context. Often, there are no grammatical clues.
In an informal language like English, this kind of ambiguity is hardly a problem. As I suggested above, humans are good disambiguators: we know which definition of “or” is meant in context. Computers, however, are definitely not good disambiguators. In fact, computers do exactly what you tell them to do; they do not even attempt to interpret or disambiguate unless you teach them how (a topic we won’t reach for a while). Consequently, ambiguous words like “or” must be explicitly defined or not used at all. Usually, the two roles of “or” are split into two separate words: or and xor. or is the inclusive version, allowing the three-way choice between one, the other, and both. xor (pronounced “eksor”) is the exclusive version, allowing one or the other, but not both. It represents mutually exclusive options. Our favorite language Cake includes or and xor. Here is the full list of basic logic instructions in Cake:
- x or y: inclusive or; returns true if just x is true, just y is true, or both are true
- x xor y: exclusive or; returns true if only x is true or only y is true but returns false if x and y are both true or both false
- x and y: returns true if both x and y are true
- not x: returns the opposite of x: false if x is true, true if x is false
The and instruction does what you would expect. not should also be fairly intuitive: it simply negates the value it’s given. This kind of value — which is either true or false — is called a Boolean. This odd sounding term is named in honor of George Boole, a nineteenth century logician who, among other accomplishments, pioneered Boolean logic. This logic involves statements that are either true or false — there is no halfway in Boolean logic. Computer science relies heavily on this kind of logic so I think it’s a good area to delve into. Here’s an example of these instructions in action:
All of that simplifies to false, if you’re curious. Convention says that not takes precedence over and, which takes precedence over or, but pieces are often placed within parentheses to avoid confusion:
This says the same thing as the first expression but the parentheses make it much more readable. Placing each logical statement in parentheses usually makes the whole expression easier to understand, especially when there are many statements together, like above. But enough about form — let’s talk about function. The above statement is sort of pointless (I just wanted to show you what a logical expression looks like) so here is a more useful example:
This may look vaguely familiar. That’s because this is the leap instruction written differently! Let’s call this new version leap2 and the original one leap1. For easy comparison, here is the original instruction, leap1:
To understand why these two versions of leap do the same thing, let’s examine leap2 in more detail (if leap1 looks mysterious, please see the original post). In leap2, the code first tests if x is divisible by 4 using
If x is divisible by 4, this part returns true. Next, the and instruction to the right returns true only if the instructions to its left and right return true, so we must examine the part of the code to the right, enclosed in parentheses:
This part of the code consists of two instructions joined by an or; if either of these instructions returns true, the whole part does as well. The left hand side,
is true if and only if x isn’t divisible by 100. This is because x % 100 == 0 returns true if x is divisible by 100. Since not reverses any Boolean that it’s given, it returns false any time x is divisible by 100 and true any time it isn’t. The right hand side,
is true if x is divisible by 400. So the whole right side of the and instruction returns true if as long as either of these conditions returns true:
- x isn’t divisible by 100
- x is divisible by 400
Put both sides of the and instruction together and you get the complete requirements for a leap year: x must be divisible by 4 and meet one of the two requirements stated above. So the two instructions, leap1 and leap2, do the same thing in different ways. If you don’t believe me (and why should you — I am a stranger), try replacing x with actual years, like 1996, 2000, 2001, etc. Make sure to try leap years and non-leap years to show that both instructions always give the same, correct answer.
It’s worth stopping a moment and appreciating this equivalence. On the surface, the two instructions look very different. And to the computer, they are different. The computer performs different computations for each instruction. But if you plug in the same number to both versions, the same result will always pop out. To phrase it concisely, these two statements are logically equivalent. This does not mean, however, that they are computationally equivalent. What I mean by this is that one of the instructions may be faster to compute than the other, even though both results are the same. If one piece of code is computed faster than another piece, the pieces are not computationally equivalent — that’s basically what the term means. In this sense, one version may be better than the other, even though they produce the same answers. We’re not quite ready to discuss this idea further, but keep an eye out for it.
Metanote: I’ve written a second part to this post, but I want to develop it further and make sure it’s accessible before publishing it. While there is an inevitable learning curve when studying these kinds of things, I want to make it as gradual as possible.
