Developers can face impossible things in their daily work. It’s impossible to directly represent infinity or to hold infinite precision on a discrete physical computer. Storage and representations are bounded. Ignoring or being unaware of this impossibility can lead to bugs or systems behaving differently than expected.
Kevlin Henney gave a keynote about Six Impossible Things at QCon London 2022 and will be presenting at QCon Plus May 10-20, 2022.
There are many times when software developers find themselves trying to work out how difficult something would be to do or they find themselves working on something that is much harder than expected. There are, however, some things that are impossible, Henney argued:
By impossible, I don’t mean "really, really hard" or "is not feasible in the time or budget" or "impractical". When I say "impossible", I mean actually impossible according to our understanding of how the universe works.
The first impossible thing that Henney presented was "representations can be infinite". The most obvious manifestation of this impossibility is that we can run out of space, whether in memory or in storage, as he explained:
The illusion of unbounded memory or storage is supported both by the availability of cheap hardware and mechanisms such as garbage collection and virtual memory. But they are still just illusions. Storage is bounded.
Another way this boundedness affects programmers is that their data representations are also bounded. As the illusion works most of the time, it is easy to fall into the trap of thinking that bit-bounded integers are actually integers and will respect the axioms of arithmetic, Henney said. This leads to some great bugs where two positive 32-bit numbers are added to give a negative 32-bit number, as in the case of the Bentley bug:
A binary search algorithm was "proven" correct by Jon Bentley in "Writing Correct Programs" in 1983, then proven incorrect by a bug report against the standard Java libraries in 2006.
InfoQ interviewed Kevlin Henney about impossible things and the consequences it can have for developers.
InfoQ: How did you come up with the metaphor of six impossible things?
Kevlin Henney: It was a coincidence of a quotation and an interest in the limits of what is possible.
The quote is from Lewis Carroll’s Through the Looking-Glass, when Alice is in conversation with the White Queen:
Alice laughed. "There’s no use trying," she said. "One can’t believe impossible things."
"I daresay you haven’t had much practice," said the Queen. "When I was your age, I always did it for half-an-hour a day. Why, sometimes I’ve believed as many as six impossible things before breakfast."
InfoQ: What consequences does "representations can be infinite" have for software developers?
Henney: We can define a value to stand in for infinity, but this is a placeholder. There is no way to represent infinity or infinite precision on a discrete physical computer. This means that not only can we not represent any and all integers, but that even within limits, say between 0 and 1, we cannot represent any and all real numbers.
We approximate with a variety of types, such as floating-point numbers, fixed-point numbers and rational numbers, but between 0 and 1 there’s an infinitude of numbers that are irrational or otherwise beyond reasonable precision of representation. What makes this trickier is that one size does not fit all: a solution that works sufficiently well in one context, such as using floating-point numbers as an approximation for real numbers in engineering applications, works poorly in another, such as currency manipulations, which are better addressed with fixed-point numbers.
There is no perfect solution. In many cases, imperfection is OK; sometimes these limitations and approximations don’t matter. What does matter is that many developers are unaware of them and the nature of the types they are using. Developers are still routinely surprised, for example, by the issues that arise from using floating-point numbers for currency values.