Editorial: Ain’t that the truth?!

It is sometimes difficult to tell if two things are identical or equivalent. Other times, it is much easier. If these two pages’ worth at the start of Overload 135 were topical based insights and opinions, it would count as an editorial of sorts. If, instead, it were me trying to unpack what counts as equivalence specifically, or more generally, truth we could be here for a very long time without an editorial. I shall therefore avoid too much philosophy and start with Booleans. Clearly, there is more than one: otherwise we wouldn’t say ‘Booleans’. George Boole was an English mathematician in the 19th century. He started his career as a school teacher in Yorkshire, but ended up in academia, despite never obtaining a degree. He published many papers, starting with differential equations, but more famously contributing towards the algebra of logic. This algebra operates on two symbols, {0, 1} or an equivalent, combined with AND and OR connectives or operations. Different symbols can be used – the structure of the algebra will not change. Sometimes extra operations, like NOT are introduced. Shannon proved this algebra’s use for describing switching circuits, making it “ indispensable in the design of computer chips and integrated circuits ” [ Wolfram ].

Some programming languages have a Boolean type, often called bool , in his memory. One suspects Boolean is too much typing, and shorter names like long , or char tend to be preferred. The word boole may have the same number of letters as short , but much programming tends to be afflicted by a grand vowel shortage, as often evidenced by variables names or function names. One random selection of code on the internet quickly found a function to draw a line in a cube called cubLine [ RosettaCode ]. Mocking code is all too easy though, and to be fair modern IDEs are making this vowel shortage less prevalent, though some languages tend to produce terser code than others and we tend to be stuck with keywords. My personal history of encounters with truth types begins with the very ‘shouty’ BOOLEAN in MFC, interspersed with some macros defining BOOL ending up with bool . Never work on a code base that has

  #define TRUE 0
  #define FALSE 1

I do seriously wonder where the ‘e’ went though; bool it is then.

Do we actually require a Boolean type? If we need to perform a set of statements conditionally, we need a way to do a high level equivalent of a jump instruction. Even if we created a fictional language that just had JZ – jump on zero – the comparison with zero would be made, and the jump performed if the value were zero. This may not require a Boolean type, but is mathematically, or at least philosophically, equivalent to checking the truth of a statement. Some languages do not have any types, and some are quite loose where they do have a type system. It is rather too easy to coerce almost anything to a Boolean in C++. Previously people resorted to the so-called safe bool idiom [ Safe Bool], if they remembered, which avoided you being able to compare two totally disparate things which could be treated as bools, such as an int and a std::basic_ios . C++11 introduced explicit conversion operators [ Stroustrup ], providing a neater solution to the problem.

I was amused to find the phrase ‘Truthy’ used in JavaScript a while ago. The Mozilla Developer Network states that a truthy value is one “ that translates to true when evaluated in a Boolean context. All values are truthy unless they are defined as falsy (i.e., except for false, 0, "", null, undefined, and NaN) ” [ MDN ]. Falsy has of course correctly omitted the ‘e’. Falsey would be incorrect and silly. Objects are supposed to be True, or is that TRUE, or true rather, when ToBoolean is called, but document.all has unique behaviour, or rather a “ wilful violation of the ECMAScript standard ” [ MDN ] for legacy code. Aside from this quirk, since all (other) objects are truthy,

  new Boolean(false)

is truthy [ Padolsey ]. Truthy might be more explicit and honest than C++ accidental coercions, however being able to create a new false object thereby making it true is of note. I shall resist commenting on Variant Bool types with a TRUE value of -1. (Thanks to Chris Oldwood for the reminder.) The truth can be twisted and blurred with great ease in any context. A recent suggestion that a claim in the media was “ 100% false ” just emphasises the fuzziness that happens. What status would a 50% false statement have? Can something really be partially true? First order logic might be clearer; as we move to higher order logic things become less well-behaved [ HOL ].

Boolean algebra has defining laws – commutativity, associativity and so on – making it an algebra. When combined with other theorems such as De Morgan’s laws

!(A&B) = (!A) | (!B) and !(A | B) = !A & !B,

proofs of equivalence between various statements can be made. More generally, a simple truth table allows you to prove equivalence between expressions, thereby simplifying them. Many of us have resorted to symbolic manipulation to neaten up some confusing nested if s and else s in code, I’m sure. If the derivation of an equivalent formulation is correct then the code will have identical behaviour; however, when faced with a tangled mess it is safest to have tests to verify this, as we all know. Though Boolean logic works precisely, real code has a tendency to take on a life of its own. As the quote goes “ No obvious deficiencies .”

I have avoided asking what is meant by truth so far. Some may claim mathematics deals with truth, though it is less controversial to say mathematics and logic give us ways to deduce equivalence. If A ⇒ B and A is given, B may be concluded. Mathematics also gives us a precise definition of equivalence, though I shall pull back from a maths lesson on posets, cosets and the like. Theorems allow us to draw further conclusions from a given starting point. On many occasions we arrive at a conclusion which may run against our intuition. We may not have discovered a new truth per se , but discovering something we believed does not hold true can be startling and exciting in equal measures. That there are more real numbers than whole numbers, even though there are infinitely many of each usually gives people pause for thought. There are many other examples. Our intuition is often incorrect. There are a variety of ways to prove something mathematically. There are a variety of ways that people attempt to prove things; authority, intimidation, tautology, stubbornness, … [ Wilson ] The toolkit of sound proof is large. We can use proof by contradiction, for example starting with the assumption that √2 is rational, we can conclude something inconsistent and are thereby forced, if we are reasonable, to accept that √2 is irrational. Othertimes, a simple counterexample will work. All primes are odd. Ah, apart from 2. So not all primes are odd. People do invoke the phrase “ The counterexample that proves the rule, ” though they are missing the point somewhat. I personally love proof by induction, though it can take a while to realise why it works, and several initial attempts accidentally end up assuming that which was to be proved on-route. Using logical equivalence, for example that A ⇒ B is identical to ! A ⇒ ! B can inspire a different approaching to proving (or disproving) a given statement, in this case a proof by contraposition. There are many other approaches to proofs. For those interested, some material is available based on an Open University proofs workshop [ Stibbe ]. We still haven’t defined identical of course. Furthermore, do any of these proof methodologies give us truth? I shall leave these questions as an exercise for the reader (proof by boredom?) and stick with the easier claim that such approaches certainly can uncover incorrect intuition and falsify conjectures.

Moving on from Mathematics, the essence of science could be regarded as falsifiability, circumventing the need to define truth or prove anything is true. Karl Popper [ Standford ] was an eminent philosopher of science. He insisted that a statement or model needed to be falsifiable in order to be scientific. Other types of statements are available but cannot be regarded as scientific. If one observation could falsify a statement, such as all swans are white, this is a genuine theory. On the other hand, he held that Freud’s psychoanalytic ‘theories’ were unfalsifiable stories, and had similar views on Marx’s account of history. Neither is science. Though both may seem to provide a model that fits observations, there is no way to prove them incorrect so they must remain as fiction rather than science. When we debug a chewy problem we often have a spark of intuition which we weave into a story to explain the observed behaviour. We must then try specific observations to ascertain whether our tale is in fact correct, so our tale must also relate to things we can observe. The alternative might be just hitting things with a hammer until they work. This is a tongue in cheek way to disambiguate science and engineering though. If our code has worked fine up to now, this is a falsifiable statement. We can keep observing and see if this continues. We can even try to make it break, say under load. We can never conclude our code is verifiably correct. “ Conclusively falsifiable is not conclusively verifiable. ” [ Standford ]

Some branches of computing use proofs of correctness, though these appear to be quite niche. In fact, formal verification strictly speaking would require a proof of termination which takes us to the halting problem. This can be avoided by proving partial correctness – that if an answer is returned, it will be correct. Does this mean all program of the form

  while (true) ; 

are partially correct? It is often joked that mathematics tends to be exactly and precisely correct but not much use. There are many similar jokes, but the physicist and engineer lost in a hot air balloon over a field, asking a mathematician where they are, are fabled to be given the correct, but useless answer, “ In a hot air balloon. ” Precisions and proofs are useful, in the right context. There is more to life than a stick utilitarian stance though. Some things are beautiful, or surprising, or just fun. Some things end up being useful at a much later date. Complex numbers might initially seem like a very abstract concept, but they can make the mathematics of electronic circuits easier. This is not why they were introduced. Starting with the observation that the square of any natural number is a natural number, and the square of any integer is the natural numbers plus zero, means negative numbers have no square root. Suppose they do. Call √(-1) = i and see what happens. You could ask why i , what’s wrong with j , or even k . You could use all three, and let ijk = -1, giving what’s known as the Quaternions, arriving at non-commutative numbers. Asking ‘Why?’, or ‘What if?’, can end up at some surprising and counter-intuitive places.

In order to prove something mathematical you often need to start with one or two specific examples to form some intuition before proceeding more formally. Indeed, that can provide a counterexample. Intuition, though often incorrect, can be useful. With practise in a given realm, you can sharpen your intuition. Mechanics can often diagnose a potential cause of a problem, by listening, or even smell. When our code goes wrong, we do sometimes have a gut feeling about the area to look in or the sort of problem to go hunting for. We need to avoid using one hunch as a tool to apply to everything else in sight though. If we’ve been stung by an off-by-one error, we can then tend to assume this is the cause of anything else odd we see. When you have a hammer, everything looks like a nail. Our circle of influence can limit our approaches too. If everyone around us insists on unit testing, we will be horrified if we end up meeting people who don’t unit test. If we follow a group of like-minded people on Twitter, and thought Brexit was a terrible idea, we’d be taken aback when the referendum voted for Brexit. We do end up surrounding ourselves with people we tend to agree with, listening in echo chambers. We can also end up searching out references that back up our position. Confirmation bias creeps in to many areas. People seek out positive data, and disregard negative data. ‘See I told you so,’ when one example fitting a theory presents itself, but never an “ Oh, perhaps I was incorrect ” when falsifying data rears its head. We should avoid echo chambers, be aware of our assumptions, and realise we aren’t always right. Like-minded people can spark creativity though, and sometimes you need some basic assumptions to even get things going. Intuition can be the starting point of ideas too. History (or Gödel) has shown the strict logic cannot ever give a complete and consistent framework. Einstein said,

There is no logical path leading to these ... laws. They can only be reached by intuition, based upon something like an intellectual love of the objects of experience. [Stanford]

Do what you love, ain’t that the truth.

References

[HOL] https://en.wikipedia.org/wiki/Higher-order_logic

[MDN] https://developer.mozilla.org/en-US/docs/Glossary/Truthy

[Padolsey] http://james.padolsey.com/javascript/truthy-falsey/

[RosettaCode] http://rosettacode.org/wiki/Draw_a_cuboid#Perl

[Safe Bool] https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Safe_bool

[Standford] http://plato.stanford.edu/entries/popper/

[Stibbe] http://www.shirleenstibbe.co.uk/proofs-2/4557195004

[Stroustrup] http://www.stroustrup.com/C++11FAQ.html#explicit-convertion

[Wilson] http://jwilson.coe.uga.edu/emt668/emat6680.f99/challen/proof/proof.html

[Wolfram] http://mathworld.wolfram.com/BooleanAlgebra.html