A while ago I wrote a semi-port of Haskell’s QuickCheck. Easy enough – a property is like a test method but with arity 1, into which you inject data – potential counterexamples to your theory. In Haskell, the type system can, through unification, figure out the type of the generator required for that property. What to do in a dynamic language?
There are a number of type inference techniques for dynamic languages – k-CFA, demand-driven type inferencing with subgoal pruning, RoelTyper. I’m going to use a very simple technique.
First, some terminology. In Smalltalk, “protocol” usually means one of two things: either “what messages does this object understand?” or “does this object understand the Foo protocol?”, where Foo might be “Stream”, or “Collection”. We’re going to use the latter meaning. In particular, given a JUnit-like theory, we want an answer to the question “What objects – what instances of what classes – satisfy the protocol sent to the datum injected into this theory?”
With a decompiler to hand, it’s easy enough to generate an AST of the theory over which we can walk: walk the
MessageNodes and look for things with a receiver
't1' which will be the name given to the first temporary variable, i.e., the argument of the unary method. This won’t work for anything hidden through a
#perform: – think of this as the
eval of Smalltalk code.
and invoked by our
TheoryTyper (which could be called a
Let’s try out our new toy. To recap, we wish to write a theory and have the system automatically find the right types of things to test the theory. So let’s try the “monadic laws”:
And lo! our duck-finder says, with the
Either monads loaded:
The keen-eyed will notice a law missing from the above – the associativity law for monads. Given monadic blocks
g – that is, unary blocks that take some value and return a value wrapped up in whatever monad you’re using – we can express this law as
but from where do we get
g? Our naive duck-finding fails: we would need to extend our “type inference”. One possible (and fairly ugly) solution is to make
m‘s class responsible through helpers: add
sampleBlockG messages to the protocol and we could write:
m is a bit harder than in the previous examples:
because all we have to work with is the send of
>>=. Arguably it would be clearer to return
a Set(Either Maybe) because the other classes are subclasses of these two.
However, despite the limitations of this technique, one can express theories in a nicely modular way. The monadic laws will simply run against any monadic classes (that is, any classes that understand
#>>= on the instance side and
return: on the class side) present in the image.