Chooser Objects
From time to time I’m amazed to find a simple algorithm which seemed to be a low hanging fruit which was just overlooked. In this particular case it is about generating and utilizing test data in a both simple and flexible manner. Mark Seaborn described the method in his outstanding blog article How to do model checking of Python code. He distilled what we might call the Chooser Algorithm from a scientific paper which buries the message under all sorts of methodological considerations and special case treatments and other bloat. This is sad because good algorithms are the crown jewels of programming. It also helped that he provided an implementation in Python and not in C or some sloppy computing-scientist-only pseudo code notation which changes from author to author.
We can motivate Chooser objects as follows.
Suppose you have a control flow statement defined in a function f. The path the flow control takes is determined by the value of some variable x:
def f(*args):
...
x = g(*args)
if x>0:
...
else:
...When we want to test the if-statement alone we can ignore the value of x computed by g. A simple method to achieve this is to introduce a for-loop in the code which iterates over a range of values which represent jumps to the individual if-statement branches:
def f(*args):
...
x = g(*args)
for x in (1,-1):
if x>0:
...
else:
...However, this is a quite heavy change and we would likely not want to repeat this at another place. Instead of adding a for-loop we can introduce a non-deterministic choice over the values 1 and -1 and pull the iteration, represented by the loop, out of the function:
def test(chooser):
def f(*args):
...
x = g(*args)
x = chooser.choose([1,-1])
if x>0:
...
else:
...
f(1,2,3) # call f with appropriate argumentsHere we inserted a call to choose which represents a set of choices. No new control flow is introduced. The function f must be called as many times as there are choices passed to choose.
The repeated call of f is managed by a new function check which is part of the Chooser Algorithm. It actually calls the test function which has a uniform interface and keeps a single chooser parameter.
class ModelCheckEscape(Exception): pass
def check(func):
stack = [[]]
while stack:
chosen = stack.pop()
try:
func(Chooser(chosen, stack))
except ModelCheckEscape:
passThe check function creates a Chooser object and passes it to func which is represents the system under test. The Chooser constructor takes two arguments. One is a list called chosen popped from a stack of such lists, the other one is the stack itself which might be filled with new lists.
class ModelCheckEscape(Exception): pass
class Chooser(object):
def __init__(self, chosen, stack):
self._chosen = chosen
self._stack = stack
self._it = iter(chosen)
def choose(self, choices):
try:
choice = self._it.next()
if choice not in choices:
raise Exception("Program is not deterministic")
return choice
except StopIteration:
self._stack+=[self._chosen + [choice] for choice in choices]
raise ModelCheckEscape()This is the definition of the Chooser object. It is a tiny bit of elementary but ingenuous code. In order to understand what it does consider the following test function with its three calls of choose:
def test(chooser):
x = chooser.choose([True, False])
if x:
y = chooser.choose(["a", "b"])
else:
z = chooser.choose(["y", "z"])On each choose call a value is returned from the _it iterator. Those values must conform to the choices passed to choose for every call of choose. Otherwise a ChooserException is raised. So we expect _it to be an iterator wrapped around lists like [True, "a"], [True, "b"], [False, "y"], [False, "z"]. Those lists are associated with the choices being made at (x, y) or (x, z).
In fact we observe some more of those lists, starting with the empty list [] and the incompletely filled lists [True] and [False]. When _it is wrapped around an incomplete list one of the choose calls will raise a StopIteration exception at _it.next(). Assume for example that _it = iter([True]) then _it is already exhausted after x and choose and will raise StopIteration at the definition of y. At this point each of the choices at y i.e. “a” and “b” will produce a new list. Those lists are [True, "a"] and [True, "b"] which are now complete. New lists are pushed on the stack as long as incomplete lists are popped from the stack incheck().
As a special case we consider a simple linear sequence of choose calls
def test(chooser):
x = chooser.choose([True, False])
y = chooser.choose(["a", "b"])
z = chooser.choose(["y", "z"])The set of complete lists according to this sequence will be the Cartesian product of the choices: {True, False} x {”a”, “b”} x {”y”, “z”}. If you just want Cartesian products there are more efficient alternatives to create them though.
These are the Chooser basics. For Python you can download the used code here.
Choosers in C++
I gave a C++ and STL based implementation of Chooser objects. The Chooser C++ API closely follows the Python example. You can download the code from the linked document.
In its most general form the choose method has following signature:
template <typename Container>
typename Container::value_type choose(Container& choices)The return type is derived from the containers value_type attribute. Other than this the algorithm only relies on iterators which means that any STL container can be used. We can rewrite the simple test function above in C++:
void test(Chooser& chooser) {
int x = chooser.choose(2);
if x {
string s = "ab";
char y = chooser.choose(s);
}
else {
string s = "yz";
char z = chooser.choose(s);
}
}This is not all that much overhead. In case of the x definition we use an overloaded version of choose which takes a single integer parameter k. This is equivalent to a choice of values within the range {0, 1, …, k-1}. The most relevant case may be choose(2) which is the boolean choice.
The string type is an STL container type as well. More precisely it is a typedef for basic_string<char>. We can create a string object with a string literal but we cannot pass a string literal directly to choose which expects an explicit reference to a container from which the return type is derived ( char in this case ).
ChooserMixin classes
Suppose we want to introduce Chooser objects into arbitrary methods of an existing class. The Chooser Algorithm is implemented s.t. a Chooser object is explicitly passed as a parameter but this would require changes in a methods interface, something we try to avoid.
Visibility of Chooser instances in the local scope of a method can also be achieved by making them global or member variables. An inexpensive method which is safer than using globals is to use a mixin class. The mixin class defines aChooser instance and if some class wants to use it, it derives from the mixin.
class ChooserMixin {
protected:
Chooser chooser;
public:
void test() = 0;
void check()
{
...
this->chooser = Chooser(chosen, queue);
test();
...
}
}The test method is abstract. If f is the method we want to check, then the implementation of test would just invoke f with appropriate parameters:
void test() {
f(arg1, arg2, ...);
}
It’s easy to change
test without touching any other source code.
More advantages of ChooserMixins
When we use ChooserMixin we can define the choices C being used in chooser.choose(C) also as member variables. This makes choices configurable. A subclass of a ChooserMixin might read data from an external file or a database and populate the C container.
I wonder if it’s even possible to get rid of T x = chooser.choose(C)assignments in method source when using data binding techniques? In JavaFX we can restate the assigment in the form
var x = bind chooser.choose(C)
The bound variable x is updated whenever C is changed. Instead of creating a new instance of Chooser on each iteration, we replace the members defined in a single instance and trigger updates of C which in turn causes chooser.choose(C) to produce a new value. It remains to be examined if this idea is somehow practical.
