I wrote an article on Property Testing about a year ago. Isocpp.org even linked to it which was pretty cool. Recently, I uncovered a fantastic talk by Jessica Kerr about property testing. Kerr’s talk reinvigorated my languid research effort toward generated testing. Kerr presented the idea (novel to me) that properties aren’t rigid. Properties don’t need to exclude all possible incorrect results for a given function. Properties simply must reduce the size of the incorrect space. This may seem like semantics, but it is easier to exclude a wild-ass-guess that verify it is correct. Additionally, some domains may not have a solidly defined answer,a nd the result my be probabilistic in nature. This post will focus on deterministic problems for the moment, but realize that property testing is vastly more general than mundane example testing. How properties reduce the size of the problem space makes me imagine this Figure.
Following Kerr’s references, I found a set of projects from a predicate-logic course. This course provides 20 separate projects excellently cast for a property-driven-design tutorial. These projects are unique since besides the typical requirements they enumerate the predicate functions each requirement typifies. Predicate functions are to a predicate-logician as properties are to a computer scientist. These enumerated properties (predicates) clarified many points I misunderstood about property testing.
This post will step through the design of the first project minmax using C++. My primary goal for this article is to address a concern raised by a colleague, “Does pulling in more complexity — a fancy test generator — actually increase quality?”
I wrote my first article for codestrokes in February 2011 - right as I was accepted to graduate school. My goal was to improve my writing in preparation for writing a thesis. While through grad school I started with more traditional writing tool. I started to learn to write, and I found my writing style: Simplicity. I started writing with a big fancy word processor. I blogged with a massive database backed blogging engine. By the time I finished my thesis, I was writing in vim. I used a makefile to check spelling and check for simple grammatical rules. The process was much simpler to manage. This motivated me to convert my blog to a static site. This post describes my process on simplifying my writing process.
Currently, I'm on a testing kick. One might say tests are shiny. I don't
know if they are really shiny as much as I found another cool use for
uniform_int_distribution<>. A use which, as a side effect, might make me
appear to be a better software developer. (This assumes a negative bug rate is
proportional to better software). I've started playing with Property Testing.
Property Testing is a form of unit testing where the programmers defines
properties, or invariants about the code. A
framework library (ok,
seriously its a framework because it calls your code) generates random
constrained inputs and calls your test functions. It's pretty cool, and while
I was playing around with the framework, I found a real bug, related to my
ignorance of C++'s auto type deduction.
Let's steal a simple example from my CSE 565 Software Verification class: a payroll function. Here is the specification:
I worked the title of this article several times before I finally settled on the subtly epic heading you see above. Hopefully this title will funnel people off google into my blog (delicious SEO). I wanted to push the A.I. component of my solution because A.I. is awesome and mysterious, and cool (and can like solve jeopardy). I was quickly disillusioned however. Really, A.I. isn’t magic, rather it’s just the same thing computers have been doing for a long time: computing. Sadly this realization took several months in an A.I. class before I was sufficiently crestfallen. A.I. patterns including the hill climbing algorithm used here are indeed “intelligent” but really it a reflecting of the algorithm designer, not the entity executing the algorithm. So I built a substitution cipher solver in C++. It’s fast it uses random numbers i.e. non-deterministic, it uses an A.I. algorithm i.e. Intelligent, it uses threads i.e. Massively, it deciphers i.e. luminates the text and it solves super stuff therefore the title is completely justified. I give you my Massively Intelligent Non-Deterministic Luminating Effortless Super Solver (MINDLESS). If none of that interests you then please stick around and follow the side quest of looking for emotionally charged parenthesis.