test.check

Add nested property support

Details

  • Type: Enhancement Enhancement
  • Status: Open Open
  • Priority: Minor Minor
  • Resolution: Unresolved
  • Affects Version/s: None
  • Fix Version/s: None
  • Component/s: None
  • Labels:
    None

Description

Including functionality to add support for nested properties would be beneficial. An example of how this may work follows:

(defn exists?
  [e coll]
  (some #{e} coll))

(defn remove-elem
  [e coll]
  (remove #{e} coll))

;; this test should fail, and illustrates nested properties
(quick-check (for-all [v (gen/vector gen/int)]
               (for-all [e (elements v)]
                 #(exists? e (remove-elem e v)))))

The requirement for this is support for reifying properties, which is not currently implemented.

Original issue - GitHub #10

Activity

Hide
Maciej Jaśkowski added a comment -

What's the status of this issue?
It would help us a lot to have this functionality up and running in the following case: I want to verify my path finding algorithm finds optimal solution in the given graph G, so I generate the graph and a big number of random paths and check that all the random paths are "less optimal" then the one found by the algorithm.

Having nested for-all that would be simple. Is there a way around?

Show
Maciej Jaśkowski added a comment - What's the status of this issue? It would help us a lot to have this functionality up and running in the following case: I want to verify my path finding algorithm finds optimal solution in the given graph G, so I generate the graph and a big number of random paths and check that all the random paths are "less optimal" then the one found by the algorithm. Having nested for-all that would be simple. Is there a way around?
Hide
Reid Draper added a comment - - edited

Sorry for the lack of update here. Nested properties are still in a bit of hammock-time on my part. The good news is they are merely convenient, and you can achieve the exact same effect with clojure.test.check.generators/bind. You can see an example of bind being used here.

Show
Reid Draper added a comment - - edited Sorry for the lack of update here. Nested properties are still in a bit of hammock-time on my part. The good news is they are merely convenient, and you can achieve the exact same effect with clojure.test.check.generators/bind. You can see an example of bind being used here.
Hide
Maciej Jaśkowski added a comment -

Apparently I need some more hints because all I can generate (using gen/bing, btw) are pairs '(graph list-of-random-paths)

That is useful as long as the algorithm works as expected. However, once it fails it's pretty hard to figure out which of random-paths failed it.

Show
Maciej Jaśkowski added a comment - Apparently I need some more hints because all I can generate (using gen/bing, btw) are pairs '(graph list-of-random-paths) That is useful as long as the algorithm works as expected. However, once it fails it's pretty hard to figure out which of random-paths failed it.
Hide
Reid Draper added a comment -

Can you show me how you would write the test with nested properties, and then perhaps I can help you rewrite it to use bind instead?

Show
Reid Draper added a comment - Can you show me how you would write the test with nested properties, and then perhaps I can help you rewrite it to use bind instead?
Hide
Maciej Jaśkowski added a comment - - edited

Great! Thank you!

Please, find the most important part below.

(defn gen-matrix-and-paths [size]
    (gen/bind
      (gen-matrix gen/s-pos-int size)
      (fn [matrix]
        (let [ nodes (into [] (range (count matrix)))
               gen-perms (gen-permutations nodes)
               perms (distinct (gen/sample gen-perms 500)) ]
          (gen/tuple 
            (gen/return matrix) 
            (gen/return perms))))))

gen-matrix generates a square matrix of incidence e.g. [[0 1] [4 0]]
gen-permutations generates a permutation of provided vector

Show
Maciej Jaśkowski added a comment - - edited Great! Thank you! Please, find the most important part below.
(defn gen-matrix-and-paths [size]
    (gen/bind
      (gen-matrix gen/s-pos-int size)
      (fn [matrix]
        (let [ nodes (into [] (range (count matrix)))
               gen-perms (gen-permutations nodes)
               perms (distinct (gen/sample gen-perms 500)) ]
          (gen/tuple 
            (gen/return matrix) 
            (gen/return perms))))))
gen-matrix generates a square matrix of incidence e.g. [[0 1] [4 0]] gen-permutations generates a permutation of provided vector
Hide
Reid Draper added a comment -

I'm confused. What issue are you running into? The code you've pasted uses bind, and not a nested property.

Show
Reid Draper added a comment - I'm confused. What issue are you running into? The code you've pasted uses bind, and not a nested property.
Hide
Maciej Jaśkowski added a comment - - edited

Ok but now I can only write something like this:

(prop/for-all [data (gen-matrix-and-paths 6)]
   (let [ [matrix random-paths] data ]
     (not-worse-then-others? tsp matrix random-paths))))

which, if my 'tsp' algorithm is not working correctly would point me to a matrix and a vector (length 500) of paths one of which is counterexample. It would be better if instead I got the matrix and a single counterexample.

Show
Maciej Jaśkowski added a comment - - edited Ok but now I can only write something like this:
(prop/for-all [data (gen-matrix-and-paths 6)]
   (let [ [matrix random-paths] data ]
     (not-worse-then-others? tsp matrix random-paths))))
which, if my 'tsp' algorithm is not working correctly would point me to a matrix and a vector (length 500) of paths one of which is counterexample. It would be better if instead I got the matrix and a single counterexample.
Hide
Reid Draper added a comment -

I'm still not sure what this would look like using a nested-property. Can you please write the code the way you'd like to see it as a nested property? This will involve at least two for-alls.

Show
Reid Draper added a comment - I'm still not sure what this would look like using a nested-property. Can you please write the code the way you'd like to see it as a nested property? This will involve at least two for-alls.
Hide
Maciej Jaśkowski added a comment -

Sure!

I would like to write something like that:

(prop/for-all [matrix (gen-matrix 6)]
  (prop/for-all [random-path (gen-random-path matrix)]
    (<= (cost (tsp matrix)) (cost random-path))))
Show
Maciej Jaśkowski added a comment - Sure! I would like to write something like that:
(prop/for-all [matrix (gen-matrix 6)]
  (prop/for-all [random-path (gen-random-path matrix)]
    (<= (cost (tsp matrix)) (cost random-path))))
Hide
Maciej Jaśkowski added a comment -

ping!

Show
Maciej Jaśkowski added a comment - ping!
Hide
Reid Draper added a comment -

Ok, let's translate that to using gen/bind. Just like with nested properties, bind allows you to create generators that depend on the value of another generator. For example, your gen-random-path depends on the previously generated matrix variable. So let's write a generator that returns both a matrix and a random-path.

(def matrix-and-path
  "Return a two-tuple of [matrix random-path]"
  (gen/bind (gen-matrix 6)
            (fn [matrix]
               (gen/tuple (gen/return matrix) (gen-random-path matrix)))))

(prop/for-all [[matrix random-path] matrix-and-path]
  (<= (cost (tsp matrix)) (cost random-path))
Show
Reid Draper added a comment - Ok, let's translate that to using gen/bind. Just like with nested properties, bind allows you to create generators that depend on the value of another generator. For example, your gen-random-path depends on the previously generated matrix variable. So let's write a generator that returns both a matrix and a random-path.
(def matrix-and-path
  "Return a two-tuple of [matrix random-path]"
  (gen/bind (gen-matrix 6)
            (fn [matrix]
               (gen/tuple (gen/return matrix) (gen-random-path matrix)))))

(prop/for-all [[matrix random-path] matrix-and-path]
  (<= (cost (tsp matrix)) (cost random-path))

People

Vote (2)
Watch (2)

Dates

  • Created:
    Updated: