Arc Forumnew | comments | leaders | submitlogin
QuickCheck for Arc (bitbucket.org)
5 points by fallintothis 4876 days ago | 8 comments


2 points by fallintothis 4876 days ago | link

Hadn't seen it done yet, so I decided to learn how Haskell's QuickCheck (http://www.cse.chalmers.se/~rjmh/QuickCheck/) works by writing an Arc version.

The idea is that you can automatically test a program by providing a set of properties it should follow. QuickCheck then randomly generates a lot of test cases to see if the properties hold and lets you look at the distribution of the test data. Properties are boolean expressions universally quantified over certain types of arguments. They are written in Arc using the utilities that quick-check.arc defines.

After some technical difficulties, I've ported what was my initial tutorial (which was too long for the forum) to the wiki: http://bitbucket.org/fallintothis/quick-check/wiki/Home

Edit: Ugh. Seems my messing around has broken BitBucket. At the time of this edit, http://bitbucket.org/fallintothis/quick-check/src points to an old version, http://bitbucket.org/fallintothis/quick-check/src/ (with a trailing slash) points to the new one. Sorry about that. http://bitbucket.org/fallintothis/quick-check/src/28760e9413... is the correct version, anyway. At least hg pull and the wiki seem to work.

-----

2 points by shader 4875 days ago | link

Very nice, clean and easy to use unit test system for arc. It seems like a very flexible system, and the generators idea makes it seem pretty extensible. On the whole its a fantastic piece of code that demonstrates clearly the readability and conciseness of arc (presuming it works of course :P ). I think it would make a great addition to Anarki.

One thing that might be nice to show in your tutorial is how to use it more like a traditional unit test syste. i.e. specify ranges of values to test. I don't mean write lots of test cases, but rather an example generator that produces all of the important edge cases, and then as many as possible inside the desired range. I would look at this more myself right now, but bit bucket seems to be down.

I do have one comment though (concerning the wiki): rev is not idempotent. Technically, an idempotent function f is one such that

  (f (f x)) = (f x)
Absolute value is a good example of such a function.

However,

  (rev (rev x)) = x != (rev x)
The correct term seems to be "involutary", according to http://en.wikipedia.org/wiki/Involution_%28mathematics%29

-----

3 points by fallintothis 4858 days ago | link

Okay! I've finally gotten around to writing this. Sorry it took so long.

One thing that might be nice to show in your tutorial is how to use it more like a traditional unit test syste[m].

Well, they serve different purposes. QuickCheck properties are universally quantified: every x should satisfy (p x). There are obviously practical problems with testing these, so we use a flood of random values for x. Unit tests are existentially quantified: for this particular x, (p x) should be satisfied.

In practice, people unwittingly reinvent one in terms of the other. In a unit-testing library, they'd change the existential property into a "universal" one, in the sense that we can test random values (which is as universal as we usually get).

  (unit-test test-foo
    "foo holds for strings"
    (let x (rand-string (rand max-int*)) ; whatever max-int* is
      (foo x)))
This is an anti-pattern that is solved more cleanly with QuickCheck by abstracting away the random generation.

  (prop prop-foo (x 'string)
    "foo holds for strings"
    (foo x))
Conversely, we can change a universal statement into an existential one easily. Just don't use any parameters to prop.

  (prop prop-foo ()
    "foo doesn't break on an edge case"
    (let x edge-case
      (foo x)))
This, too, is an anti-pattern. E.g., a unit-testing library would probably have better facilities for shared data set-up/tear-down, grouping together tests into suites, and asserting several things per test. (The last one's not necessarily true if we try to keep "functional-programming-y" about it like QuickCheck does.) As it stands, this is a square peg in a round hole for quick-check.arc. It'll run (prop-foo) 100 times, testing a property that's verifiable after only 1 run.

In a way, QuickCheck properties seem more powerful. You test a range of random data instead of the same ol' '(8 6 7 5 3 0 9), "foobarbaz" test inputs. QuickCheck lets you discover edge cases. In the presence of such a tool, unit-tests become less of a default ("Agile Methodology dictates we write unit tests first!!") and more of a backup plan in the fight against regressions: discover edge cases with QuickCheck, then make sure those edge cases never break your code again with unit tests.

Even so, you'll still want to write unit tests for other reasons. If you know a priori that a certain input should produce a certain output, it's easy to put that in a unit test. Often, to test it as a universal property basically relies on the very program you're writing. Silly example, for illustration: converting Roman numerals to integers. You could write

  (generate roman-int (int-between 1 4000))

  (prop test-roman (x 'roman-int)
    (is x (roman->int (int->roman x))))
which is a useful property, but relies on both roman->int and int->roman having been written correctly. As long as int->roman and roman->int are inverses, they'll pass the property. They could even be something stupid like

  (def roman->int (x) (+ x 5))

  (def int->roman (x) (- x 5))
So you need to test just one of them. How do you do that?

  (is (int->roman x) ???)
x is random, so you won't know what the other side of this equality should be. In this case, you'd want unit tests against known values -- 1 and "I", 4 and "IV", etc.

This problem with inverses actually came up when I was testing sscontract (http://arclanguage.org/item?id=11179), hence test/canonical.arc: http://bitbucket.org/fallintothis/contract/src/d1b4ff38afaf/....

Now! You probably knew that stuff already. But it gives us a framework for my understanding, so we can discuss the rest of your post.

i.e. specify ranges of values to test. I don't mean write lots of test cases, but rather an example generator that produces all of the important edge cases, and then as many as possible inside the desired range.

I'm not exactly sure what you mean. Per the above, it doesn't sound like a "traditional unit test system". Specifying ranges of values sounds like what QuickCheck is supposed to do. But there's no real way of automatically knowing all of the important edge cases, so I assume you mean that edge-cases are provided manually. That seems to contradict your "don't write lots of test cases" line, though. Finally, "as many as possible inside the desired range" makes me think you're talking about disjoint input sets to a single property: first test all of the edge cases, then start randomizing.

Using quick-check.arc to do the random testing it's meant to do, that's

  (sized edge-case n
    (rand-choice      ; or frequency, if you want to bias the choices
      edge-case-1
      edge-case-2
      edge-case-3
      (arbitrary default-range n)))

  (prop foo (x 'edge-case)
    (bar x))
But that won't enumerate all of the edge cases. It will with fewer than 100 of them, on average, but it's all still random. You could un-randomize the generation a little bit with something like

  (let index 0
    (sized edge-case n
      (if (< index (len list-of-edge-cases))
          (do1 (list-of-edge-cases index)
               (++ index))
          (arbitrary default-case n))))
Then each call goes through list-of-edge-cases in sequence. Once it gets to the end, it starts pumping out arbitrary values.

  arc> (= list-of-edge-cases '(foo bar baz))
  (foo bar baz)
  arc> (= default-case 'int)
  int
  arc> (arbitrary 'edge-case 10)
  foo
  arc> (arbitrary 'edge-case 10)
  bar
  arc> (arbitrary 'edge-case 10)
  baz
  arc> (arbitrary 'edge-case 10)
  -10
  arc> (arbitrary 'edge-case 10)
  -5
If you have more edge-cases than the number of times quick-check runs (presumably 100, though sometimes more with whenever clauses and such), you still won't go through all of them. So you could manually go through each edge case separately from the quick-check call, then run quick-check, and...

Square peg, meet round hole.

However, this thread's gotten me interested in writing a proper unit-testing library for Arc. The main considerations are API design and the output's readability. After figuring those out, the programming part's easy. And there are lots of example libraries to base it off of. We'll see if I get around to it any time soon. (Maybe this weekend? No promises, though; I've got a bunch of work to do.)

What becomes important and interesting, then, is to automate the synergy between QuickCheck and unit tests. Instead of "run QuickCheck, get a failure, copy/paste into a unit test, fix code, run QuickCheck again, pass, run unit tests, pass", there should be a way to spill over QuickCheck failures into unit tests transparently, so we don't even need to think about it. Again, easy enough to do, once I settle on the way it should be done. Is that closer to what you meant?

-----

2 points by akkartik 4858 days ago | link

(Request: please post an email on your profile.)

"this thread's gotten me interested in writing a proper unit-testing library for Arc.. automate the synergy between QuickCheck and unit tests. Instead of "run QuickCheck, get a failure, copy/paste into a unit test, fix code, run QuickCheck again, pass, run unit tests, pass", there should be a way to spill over QuickCheck failures into unit tests.."

I'd love to help. I've been testing a lot with arc. Readwarp has more tests than code.

One recent idea to improve testing is to run tests in dependency tree order: http://arclanguage.org/item?id=12721

-----

1 point by fallintothis 4875 days ago | link

I do have one comment though (concerning the wiki): rev is not idempotent.

Egads! How embarrassing. That'll teach me to double-check my abstract algebra. :) Thank you, and fixed.

but bit bucket seems to be down

Yeah, there were notices about some maintenance thing or other. Side note: the /src/ vs. /src thing seems fixed now.

One thing that might be nice to show in your tutorial is how to use it more like a traditional unit test syste[m].

I have plenty to say about that, but I can't type it all right now, so I'll have to get back to you in a little bit. Sorry!

-----

1 point by rntz 4874 days ago | link

rev isn't idempotent, however, rev:rev (rev composed with itself) is, which is I suspect what fallintothis was thinking. "Involutary" (which term I've never run across prior to this) appears to be a term for just this property: that the square is idempotent.

-----

2 points by shader 4874 days ago | link

Involution is more strict than the square being idempotent; it also must be the identity function. I.e. abs^2 is idempotent but abs itself is not involutary, since abs^2(-1) = 1 != -1

-----

1 point by aw 4876 days ago | link

Looks cool!

I'm not actually able to read the tutorial on my laptop... the paragraphs are wider than my screen, and if I scroll down to the bottom to get the horizontal scrollbar, the paragraph I'm trying to read scrolls up off the screen. Would it be possible to word-wrap them?

Ah, I'm able to read the tutorial in the wiki. Thanks!

-----