Property based testing without reimplementing the code under test

Question

Given a very simple method such as:

  def squaredDistance(p1: Point, p2: Point) = 
    math.pow(p1.lon - p2.lon, 2.0) + math.pow(p1.lat - p2.lat, 2.0)

What are some valuable property-based tests that don't simply reimplement the method?

I can only think of testing for result >= 0.0, which is pretty broad.

Answer 1

In general, your tests should normally not reimplement the code under test. This can happen to you with traditional tests as well. In fact, from my experience, property-based testing tends to be better for avoiding re-implementations.

When you think about the properties, you specifically do not think about implementation details (i.e. do not think about how you come to some result/property, but instead consider the result/property itself).

Property-based testing is particularly useful for mathematical properties. A square distance function, being quite well-founded in mathematics, is therefore a good match. Nevertheless, it takes a lot of experience. If you have a solid background in mathematics and/or predicate logic, it is so much simpler to find good properties. If all you know is traditional fixed input vs expected output testing, then you are in for a steep learning curve.

So let's look at the function in question a little bit closer. We do have something that works based on Point, so we will need a generator for that - I assume for this answer, that you got that covered already. The resulting value, according to your type signature, is a Double.

First off, property-based tests help you stamp down sub-optimal types. In particular, we know that squared distances always have to be non-negative. A 'Double' doesn't cover that information yet. So there's your first property that you get for free -> limit the result type to more closely resemble the mathematical result domain of the function.

Next, you can look at classical mathematics to find out general relations available for functions/properties and you will come across terms like "(anti-)symmetry" or "transitivity", all of which can be examined to check whether they should hold for your squared distance function. If they do, then you have yourself another well-defined property.

Let's say we add properties to ensure symmetry and transitivity, as well as non-negativeness. Next, you can look at numbers at the border of your domains and realize, that an output of 0 is something special and you add another property for the 0-distance being equivalent to being the same points.

Now you have 4 properties in place already. What I found in my experience of property-based testing is that you often need to make sure that you don't run into this problem: you have defined properties over your domain, but unfortunately, an implementation as simple as if (p1==p2) 0 else 1 satisfies all four properties.

Why is that? Because all our properties so far concentrated on the input. The output domain of the function is way under-defined still. One way to handle this would again be to add samples (input vs expected output), but can't we find a property for the output domain that does better?

In fact, some though (aka experience) tells you that when you generate a point, and then generate others, you could argue on the spread of distance values you'll get. You have to be careful to rule out equal points (due to the 0 distance) and the symmetry of distances. (for example, the distance from 0,0 to 1,0 and 0,1 is the same).

There are a lot of possible properties, but let's just make up one example: for each generated point, you use a normal int/double-generator to generate more points that differ in only one coordinate (for example, you start with (3, 15) and generate (3, 4) (3,7), (3,20), ...). When you remove duplicates form these and check the distance from your fixed point (3,15) to all the other (unique!) points, then you know that the distances/results must also be unique. So spoken in a more code-like fashion, you create a set of these other points, not including the fixed point, then calculate the distances for each of these to the fixed point and add the results to another set. Finally, you verify the sets are of equal size. I highly doubt, that your implementation code looks even remotely similar to that.

If you want to be safer, you could add two properties, one per axis (tuple-arity, whatever you want to call it). By adding these properties that essentially describe your output domain as opposed to your input domain, you immediately make it very hard for any hard-coded implementations like the example given above to still succeed.

However, and this is a major point of property-based testing, none of these six properties I have discussed so far guarantee that the actual results of your function resemble the square distance between numbers! So in my experience, you still need a few fixed input vs expected output tests in addition. The cool thing though, is that you can actually get away from your previous preconception that you even need a square distance. Once you start thinking about the actual properties of your functions, you often realize that the even being a "square distance" is nothing than an unimportant implementation detail that you might not even need to care about. So do you just want to have a distance function, or does it matter whether it's squared, euclidean, or something else entirely?

In my experience, if you need to limit it down to the exact function, you need to add in some fixed input vs expected output tests, as the properties in their generality provide still too much freedom. Happy to hear if there's another practical way to deal with this, but as usual, I'm just not seeing a silver bullet here.

Answer 2

I think that specifically for this example (distance metrics) one could check as well that triangle inequality (https://en.wikipedia.org/wiki/Triangle_inequality) holds.

This would not confirm that this is indeed squared distance, but will rule out a lot of incorrect distance implementations.

As well, as distances are mathematically metrics, one could check all four properties of metrics from here https://en.wikipedia.org/wiki/Metric_(mathematics), and as well, translation invariance, which holds as well for squared distance.

As mentioned in other answers, specific test cases for distance could be useful as well (or a distance from zero from answer of original author).

When doing specific checks, the danger is that one quickly runs in limitations of floating number implementations, which would show that in many specific cases the properties that should by mathematical definition hold are broken due to floating point limitations. This could be partially remediated by using high-precision arithmetics.

Answer 3

In the end, I thought of more properties and this became quite a useful test.

1. The squared distance between any point and itself is 0.0
2. The distance between any two distinct points is > 0.0, measured from either point
3. For any number n, the distance between Point(0,0) and Point(n,n) is n*n*2 (this one normalises one point to see the effect on another)

Here are these properties as implemented in Scala

  def pointSelfZeroSqDist = prop { p: Point =>
    squaredDistance(p, p) mustEqual 0.0
  }

  def pointOtherPositive = prop { (p1: Point, p2: Point) =>
    (squaredDistance(p1, p2) must be_>(0.0)) and
    (squaredDistance(p2, p1) must be_>(0.0)).unless(p1 == p2)
  }

  def sameDistanceEitherWay = prop { (p1: Point, p2: Point) =>
    squaredDistance(p1, p2) mustEqual squaredDistance(p2, p1)
  }

  def fromZero = prop { n: Double =>
    squaredDistance(Point(0, 0), Point(n, n)) mustEqual n*n*2
  }

Answer 4

I can think of a few extra properties, but I agree that they don't cover the full range of possibilities..

1. Given two points: A and B, selecting any point P between them (e.g. A.X < P < B.X (or vice versa) and A.Y < P.Y < B.Y (or vice versa)), the following should hold: Distance(A, P) + Distance (P, B) = Distance(A, B).
2. If A and B form a diagonal, then: Distance(A, (B.X, A.Y)) + Distance((B.X, A.Y), B) < Distance(A, B)
3. Distance(A, B) = Distance(B, A)

Hope that helps.

Answer 5

Short answer: test against hard-coded expected outputs.

Long answer:

You should be able to tell what is the expected output from a given input, by following the logic in your head or on paper, before implementing. Take the inputs and the outputs and turn them into tests, one by one, coding the algorithm little by little.

However, like in your example (squareDistance), the "little by little" part may feel too dogmatic, and it does so because the tests are not giving you any feedback if you already know exactly what code you need to write. So in these cases, I'd suggest to implement the code directly, then run it against a few inputs to get the outputs, check if they are correct manually, and then create tests where the inputs and outputs are hard-coded.

So, regardless of whether the tests come first or after, you should not duplicate the logic within the tests - keep only the inputs and their respective expected results.