With the input below, this maximum calculation returns six:
func maxStep(a, b float64) float64 {
if a > b {
return a
}
return b
}
Start below every finite value, at negative infinity, and repeatedly call that helper with the next element. That's a fold. This input fits inside one block:
90, 80, 70, NaN, 6, 5, 4, 3
NaN means not a number. Ordered comparisons involving it are false. The helper therefore returns its second argument when either argument is NaN.
What worries me is how easily I can explain a different program by accident.
Where did ninety go?
The running maximum reaches 90, then NaN replaces it because 90 > NaN is false. On the next step NaN > 6 is false too, so six replaces the NaN. The remaining values leave us with 6. If I describe this as “ignoring NaNs”, somebody can reasonably skip the NaN and keep 90. They have followed my explanation and built an operation that returns ninety, and I'm quite capable of writing small print that I wouldn't pass myself, apparently. Knowing what I meant doesn't help the person implementing what I wrote. Here the contract has to say what each NaN position does. Correcting that sentence and changing the helper have different consequences for existing users.
Who gets to choose?
Giving a calculation more workers should help it finish sooner, but I'm much less keen on that setting choosing the answer too. Floating-point arithmetic can make that happen, because changing how the additions are grouped changes where their intermediate results get rounded.
For Floatyboat, the array language I'm building, I want to be able to ask for a repeatable result. Then I start trying to write down what repeatable means, run it again, keep the answer. Repeating a result within one build and reproducing it in somebody else's implementation are different promises.
I'm interested in the second one too. Another implementer shouldn't have to guess which details of my code to copy.
The compiler, runtime and library can all have a say in how work gets divided. Freedom to regroup additions can help performance and can change the last bits of the answer. Whether that's useful depends on the application. That decision belongs with the application’s requirements.
I find it useful to separate four approaches:
| Approach | What happens to the choice? |
|---|---|
| Order-granting | The implementation may choose the grouping within the rules it has been given. |
| Order-fixing | A chosen grouping stays fixed across the variations covered by the contract. |
| Order-independent | The arithmetic gives the same result across the permitted regroupings. |
| Order-accepting | Different results are accepted according to a stated criterion. |
I call the first one granting because I'm granting the implementation permission to choose. Fixing keeps a particular grouping.
Order-independent arithmetic takes that grouping out of the result, and even keeping track of rounding losses (as compensated summation does) doesn't automatically get me there.
Accepting is a decision about the answer I need. An application might tolerate a stated numerical difference while another needs matching bits for a regression comparison. What does “close enough” mean here? I need that answer before I can accept the result.
A caller can demand that an operation be order-fixed. That's a requirement to meet, rather than another way to perform the calculation.
Writing the request is easy enough, but I still have to stop a later optimisation from regrouping the work.
These choices can work together. A caller might accept variation even though the implementation happens to fix its grouping. Which freedom has the caller agreed to give away?
“My implementation currently uses this grouping” describes some code. “A compatible implementation must preserve this grouping” tells somebody else what they are required to do. That's a normative statement. It belongs to the contract they must obey.
Writing “the same answer” feels reassuring, then I start wondering what I would accept as the same, and I want to argue with my own sentence. I can be quite tiresome about these few words. The grouping, the build, whose implementation we're running.... Lawyers have it easy.
A reduction combines many inputs into one result. For an order-fixed reduction I could specify blocks of 4,096 elements by input position. Each block starts from a specified value, such as zero for addition, and combines its elements strictly left to right. Then the block results are combined left to right too. More workers can take different blocks without redrawing those parentheses because the block size belongs to the calculation rather than being whatever division happens to suit today's worker count. Now changing that size is no longer an innocent tuning decision. Another implementation needs the same rule. Matching bits also needs agreed input bits and arithmetic rules, including rounding and special-value behaviour, so the parentheses can't do it alone.
And that's more of a commitment than saying my program gave the same answer twice. I have to decide which details I'm prepared to keep before asking somebody else to rely on them.
Can this example tell the difference?
The maximum example exposes a difference between operation rules. Checking a grouping needs inputs that can expose a grouping difference too.
For ordinary 64-bit floats, compare adding three values with the left pair grouped first, (a + b) + c, against grouping the right pair first, a + (b + c):
| Inputs | Left grouping | Right grouping |
|---|---|---|
1, 2, 3 | 6 | 6 |
0.1, 0.2, 0.3 | 0.6000000000000001 | 0.6 |
The first row lets me change the grouping without noticing, and I could check it a thousand times and learn very little about whether my implementation keeps the promised parentheses. The decimal inputs separate these two alternatives because the intermediate rounding differs.
What has that check established?
I call this witness adequacy. For an input, an operation and a specified set of alternative groupings, count the distinct output bit patterns. Here the first input gives one pattern and the second gives two.
That count tells me whether these inputs distinguish these alternatives. Which alternatives matter? That's still my call. At least I can see when my example leaves them indistinguishable.
Which changes break the promise?
For this contract, I'd make a change to the required result bits a major version change. Adding an operation without changing existing results could be a minor one. A corrected explanation that preserves the agreed behaviour belongs in the changelog without pretending the arithmetic changed.
When code and documentation disagree, the code doesn't win by being executable. I have to decide what users are entitled to rely on. Preserving the helper's behaviour means correcting the NaN sentence. Choosing the NaN-ignoring behaviour means changing the required answer from six to ninety and treating that as a compatibility change.
I'm going to keep the specified grouping and the helper's NaN behaviour in this contract, with examples that separate them from the alternatives. Someone implementing it elsewhere should be able to work out why the answer is six before they run my code.