Properties as a Compass: Precise Programming ✛ ✎

Original: "Accurate Programming: Thinking about programs in terms of properties"
· Walid Taha, Veronica Gaspes, Rex Page
arXiv:1109.0786 · 2011-09-05 · arXiv non-exclusive · independent analysis · 3 min
Programs are not just code; they are mathematical properties that can be checked automatically.

Fog thickens over the line "def max(a: Int, b: Int): Int". What does it do? It returns the larger of two numbers, but how can you verify that? You could write a dozen tests with specific pairs: max(2,3)=3, max(5,5)=5, max(-1,0)=0. Still, a nagging doubt remains: what if it breaks for, say, a million and minus a million? Instead of staring into the fog, a developer can grab a compass, and that compass is called a property.

A property is a statement about a program that must hold for all inputs. Not "for 2 and 3 it returns 3", but "for any a and b, the result is at least as large as each of them". Such a statement can be written not only on paper but also in code. The ScalaCheck library can generate hundreds of random values, plug them into the property, and report if any of them violates it. This is property-based testing: instead of manually enumerating examples, you automatically check a law.

A property is like a compass: it doesn't guide you along a single route but sets a direction that holds for any path. For the max function, three such directions are symmetry (max(a,b)=max(b,a)), idempotence (max(a,a)=a), and the least upper bound property (the result is at least as large as each argument and no larger than any other such number). Together, they fully define what "maximum" means.

But properties don't just verify finished code; they help you write it. Take the function sum, which adds up a list of numbers. One property is monotonicity: if you take a list and add a positive number to it, the sum increases. Seems obvious. But ScalaCheck finds a counterexample: for the list [65536] and adding 1, the sum doesn't increase; it stays 65537, due to integer overflow in some languages. The compass pointed to a rock that ordinary tests missed.

Properties can be refined, like adjusting a compass. The function count counts the elements of a list. The first property, "the result is non-negative", is too weak: even a function that always returns zero satisfies it. Add the property "for a list with one element, the result is 1", and zero is ruled out, but other impostors remain. Gradually, step by step, the properties converge to a single correct implementation.

And here's the twist: the program itself is also a property. If a function always returns 42, you can describe it with the property "for any input, the result is 42". The line between specification (what we want) and implementation (how we do it) blurs. Precise programming is an approach where the developer keeps in mind not only the code but also the properties that the code must satisfy. It's a bridge between testing and formal verification: we don't prove the program entirely, but we get most of the guarantees for a fraction of the cost.

The fog lifts. The line "def max" no longer looks like a mystery: it has three compass properties, each of which can be checked automatically. Programming stops being guesswork and becomes navigation on a map we draw ourselves.

The name ScalaCheck alludes to the idea of automatic property checking, not to 'checking Scala'—it is a tool for checking properties in Scala.

In the series 'Westworld', robot behavior is governed by complex rules, but their correctness is not guaranteed. Precise programming could help formulate and check behavioral properties, preventing unexpected failures.

Scientists
Erwin SchrödingerHugh Everett IIIMax BornAlbert EinsteinJohn von NeumannAugustin-Louis Cauchy
Concepts
accuracy automation optimization diagnostic accuracy Natural Language Processing real time quantum algorithm drug design open source convergence Machine Learning computer simulation speech recognition personalized medicine artificial intelligence Robotics computation classification exact solution precision