In Support of Implication for C++

The paper:

I have a deck of cards. Each card has a number (integer) on the front, and is either red or blue on the back. (This is axiomatic, I know it a priori). My friend lays out four cards on the table in front of us at random. I see two face up, showing 3 and 8, and two face down, showing a red back and a blue back.

(Image from, CC by-sa 4.0)

My friend makes a claim: “if a card has an even number on the face, it has a blue back.” Which cards do I need to turn over to test this claim?

This is the famously unintuitive Wason Selection Task. It’s answered incorrectly by the majority of people, even people trained in logic (math students, graduates, and yes, professors). Of course you, savvy Internet reader, know the answer is that we need to turn over 8 and red to test the claim.

My friend made a statement that was an implication. “Even number on front => blue on back”. It was difficult to unravel this, so we might conclude that implication is unintuitive and hard to think about. But hold on. Let me posit another situation:

I’m a pub owner in the UK (where the legal drinking age is 18), and I see four people drinking at a table in the corner. Two of them I know – Alice is 16 and Bob is 25. I can’t see what they’re drinking. I don’t know their two friends, but I can see what they’re drinking – one has Coke, the other has lager.

Whose drinks/ages do I need to check to make sure there’s no underage drinking going on?

(Image from, CC by-sa 4.0)

Most people find this question much easier to answer, and much more intuitive to understand: I need to check that Alice (16) isn’t drinking alcohol, and that the lager-drinker is over 18. I don’t need to check what Bob (25) is drinking. And I don’t need to check the age of someone drinking Coke.

But this is precisely the same logical situation as with the cards! “Under 18 => drink is non-alcoholic”.

Implication in C++

Why do I bring this up? To illustrate an intellectual honesty trap: just because we don’t immediately understand something, or we think it’s complex, or we don’t see a use case for it, or it’s unfamiliar, we shouldn’t conclude that it’s not useful, or too hard for “the average C++ programmer” to understand.

This is also very close to the “won’t somebody think of the children (junior programmers)!?” argument, by the way. Let me assure you, the “children” are just like you – and they are all right.

I’ve had cause to use implication in my day job twice in the last month. The first case was in code review; the second in library design and implementation. As a regular programmer, I also suffer from implication being non-intuitive in some cases, but I worked through some truth tables, and my library is better for it. It would be even better if C++ had a direct way to express implication.

Here’s one library case: you want to simplify a Boolean expression programmatically. What do you do? You could hard-code some simplification rules of Boolean algebra and go on your way. But if you want your library to handle generic values, you might take the approach I did, and allow users to express implication between their values.

ABA or BA and BA => B
Truth table for various operators

If we have two (opaque, user-defined) values A and B, how can we simplify the expression A and B? Well, if the user can tell us that A => B is true, then we know that we can disregard the third line of the above table, and that A and B simplifies to A, and A or B simplifies to B. And it turns out that by adding just a few elementary implication rules (false => X, X => true, X => X) to the library, and allowing users to customize complement (not) and implication, we have pretty much all we need to simplify expressions.

I would also point out that in everyday code, as is so often the case, just because we don’t recognize implication doesn’t mean it isn’t there. Everyone has implication in their code. Not just the workaday Boolean expressions, either – every time you write a function, you’re expressing an implication. This is the Curry-Howard correspondence. Quite possibly, we’ve gotten by for years or decades without caring, but again, we shouldn’t dismiss the utility of thinking this way for those that do.

C++ is large. It contains multitudes. By design. I bring up this quote from Bjarne a lot, because it’s fundamental:

[C++] was designed to provide a toolset for professionals, and complaining that there are too many features is like the “layman” looking into an upholsterer’s tool chest and exclaiming that there couldn’t possibly be a need for all those little hammers.

Bjarne Stroustrup, The Design and Evolution of C++, section p199

In P2971, Dr Walter E Brown lays out a solid argument for adding an implication operator to C++, with explanations, use cases, design tradeoffs and implementation experience. This is a well-crafted paper; it has everything we tell new contributors is desirable. It’s quite proper to argue constructively over the details and choices here, but let’s not dismiss the idea just because it’s unfamiliar and we don’t yet understand a use case in our code.