Property testing

Property testing is a strategy for verifying the correctness of complex programs and libraries. It involves defining a set of properties that programs should obey. Essentially, the programmer writes a specification for their work.

You define properties with a property testing library, like Haskell's QuickCheck.¹ These libraries also enable users to generate sample data to drive properties during test execution.

For example, this ScalaCheck property says a JSON parser can decode any object it encodes:²

object JsonSpecification extends Properties("encode & decode") {
  property("roundtrip") = Prop.forAll(json) { json =>
    Json.decode(Json.encode(json)) == Right(json)
  }
}

We will write property tests for a sorting algorithm to illustrate the value of property testing.

Fluency with Scala -- or a similar functional programming language -- is required to follow the rest of this post.³

Properties VS Assertions

In a typical unit test, we assert that the function under test behaves as expected for a single input value. A property test verifies that a function behaves correctly for a family of input values.

If a test function has a finite domain, ScalaCheck can generate input exhaustively. Otherwise, we have to resort to sampling.⁴ Regardless, a single property test for a function usually gives us more confidence that our code works than multiple unit tests.

However, table-driven tests are better at documenting edge case behavior. They also ensure tests always run for edge case input. For JSON parsing, edge case input includes empty JSON strings, arrays, and objects.

A specification for sorting

A sorting algorithm satisfies two properties:

1. It permutes its input to form its output, and
2. it reorders its input according to a total order.

Stable sorting algorithms satisfy a third property: they preserve the relative order of elements with identical sort keys.⁵

Sorting algorithms act on linear data structures like arrays and lists. Most sorting algorithms admit side effects, which makes them awkward to use in functional programming.

Fortunately, the top-down variant of mergesort can sort a list without performing side effects. We will look at this sorting algorithm as it leads to elegant property definitions.

Mergesort

Top-down mergesort is a divide-and-conquer algorithm. It splits a list in two, recursively sorts the partitions, and then merges them.

Suppose we have two functions,

1. split, which divides a list into two lists, and
2. merge, which combines two sorted lists into a longer sorted list;

then we can write mergesort as a pure function:

def sort[T](list: List[T])(implicit ordering: Ordering[T]): List[T] =
  list match {
    case Nil         => Nil
    case head :: Nil => list
    case _ =>
      split(list) match {
        case (left, right) => merge(sort(left), sort(right))
      }
  }

This version of mergesort performs an asymptotically optimal number of comparisons, despite being pure.⁶

split is a general-purpose function.⁷ Like sort, split is recursive:

def split[T](list: List[T]): (List[T], List[T]) =
  list match {
    case Nil => (Nil, Nil)
    case head :: tail =>
      split(tail) match {
        case (left, right) => (right, head :: left)
      }
  }

By switching the position of left and right, split ensures that its return values differ in length at most by one.⁸

merge is easier to implement than split:

import math.Ordering.Implicits.infixOrderingOps

def merge(l: List[T], r: List[T]): List[T] =
  (l, r) match {
    case (Nil, _) => r
    case (_, Nil) => l
    case (lh :: lt, rh :: _) if lh <= rh =>
      lh :: merge(lt, r)
    case (_, rh :: rt) =>
      rh :: merge(l, rt)
  }

Testing, Testing

To use ScalaCheck, we need to be aware of two data types it exports: Gen, and Prop.

A Gen[T] instance encodes all the information necessary to produce samples of type T. Prop allows us to define properties. A Prop instance verifies a property by sampling a Gen[T] instance.

Writing generators

sort is a generic function — it would be pretty useless otherwise. We can’t write generators for the infinite number of input types that generic functions accept. We have to limit ourselves to a handful of types. For the sake of simplicity, let's feed sort with positive integer lists.

We can use the combinators ScalaCheck provides to write a generator for lists:

val ints: Gen[List[Int]] =
  Gen.listOf(Gen.posNum[Int])

ScalaCheck will choose the number of lists to generate when running a test. It will also pick the size of the largest list. ScalaCheck may not behave as we want it to by default.⁹

Writing properties

The first property practically writes itself if we already have a counter abstraction:

object SortingSpecification extends Properties("sort") {
  property("permutes its input") =
    Props.forAll(ints) { list =>
      Counter(sort(list)) == Counter(list)
    }
}

Scala has no counter type in its standard library, so we must write our own. Thankfully, it is straightforward to implement Counter:

case class Counter[K] private (keys: Map[K, Int]) {
  def apply(key: K): Int = keys.getOrElse(key, 0)

  def +(key: K): Counter[K] = {
    val count = this(key) + 1
    Counter(keys + (key -> count))
  }

  def -(key: K): Counter[K] = {
    val count = Math.max(this(key) - 1, 0)
    Counter(keys + (key -> count))
  }
}

object Counter {
  def empty[K]: Counter[K] = new Counter(Map.empty)

  def apply[K](keys: Seq[K]): Counter[K] =
    keys.foldLeft(Counter.empty[K])(_ + _)
}

The second property is also simple to write:

import math.Ordering.Implicits.infixOrderingOps

def isSorted[T](list: List[T])(implicit ordering: Ordering[T]): Boolean =
  list.zip(list.tail).forall { case (left, right) => left <= right }

object SortingSpecification extends Properties("sort") {
  property("returns a sorted list") =
    Prop.forAll(ints)(isSorted compose sort)
}

If sort is faulty ScalaCheck will

1. "shrink" input to find the smallest list it cannot sort, and
2. print out the seed of the failing test run to aid debugging.

failing seed for sort is 1GSNrW_g7K6qDK0yf7ZVqjncxQGRBA2_afg_I2PsRKC=
! sort.`permutes its input`: Falsified after 10 passed tests.
> ARG_0: List("1", "1", "0")
> ARG_0_ORIGINAL: LIst("10", "95", "78", "13", "64")

If you want more insight into how ScalaCheck works, look at the book Functional Programming in Scala. In chapter eight, readers develop a property testing library from first principles.