How to write a generator for a hierarchical structure

Question
21

I’ve indeed seen the book on ScalaCheck, and have been tempted to order it from Amazon. I’m about 20% through the Alvin Alexander book Functional Programmning Simplified (the Scala edition). When I finish that one, I may take a look at the ScalaCheck book. Thanks for the recommendations. It’s now on my amazon wish list.

22

What I’m trying to do is use a function which already knows how to generate a random Bdd, and persuade the testing framework to use that function. genRandomBdd needs an argument to tell it the number of levels (representing the number of variables in the Boolean function the Bdd represents), each additional level doubles the size on average, and consequently doubles the calculation time. So I have a function genNumVars generate a random integer with a special distribution. 1 twice as likely as 2, 2 twice as likely as 3, etc… but capped by a given maximum.

23

Okay, so maybe we just need to Gen-ify this path. If 6 is basically the constant you want, then you should be able to do this (based on the ScalaCheck book, remembering that I don’t know this topic well):

  val intGen: Gen[Int] = for {
    size <- Gen.const(6)
  } yield Bdd.genNumVars(size)

This basically wraps the operation in Gen-ness. (The value of the top line in any for comprehension determines the type of Monad you’re working with.)

Similarly, if you wanted a range of values to pass into genNumVars, you could do:

  val intGen: Gen[Int] = for {
    size <- Gen.choose(1, 6)
  } yield Bdd.genNumVars(size)
1 Like
24

!!!Yippeeeeee!!! That suggestion seems to work well. Many thanks for your patience. Here is the version of the code. It’s not very much in the end. But far from trivial in its subtlety.
I have some diagnostic println calls in there just to prove to myself, that it is indeed taking a considerably large number of different Bdds.

import org.scalacheck._
import org.scalatest._
import org.scalatest.prop._
import robdd._

class BddSuite2 extends FunSuite
  with Matchers
  with GeneratorDrivenPropertyChecks {

  val bddGen: Gen[Bdd] = for {
    unused <- Gen.const(1)
  } yield Bdd.genRandomBdd(Bdd.genNumVars(8))

  private implicit val arbitraryBdd: Arbitrary[Bdd] = Arbitrary(bddGen)

  test("bdd double negation") {
    forAll { b: Bdd =>
      println(s"random bdd=${b}")
      assert(b == Not(Not(b)))
    }
  }

  test("d'morgan"){
    forAll { b1: Bdd => {
      forAll { b2:Bdd =>{
        println(s"b1=${b1}")
        println(s"b2=${b2}")
        assert(Not(And(b1,b2)) == Or(Not(b1),Not(b2)))
        assert(Not(Or(b1,b2)) == And(Not(b1),Not(b2)))
      }}
    }}
  }
}

Here is an excerpt of the disgnostic output.

random bdd={1+{2+4-T}-3}
random bdd={3-5}
random bdd={1-3}
random bdd={2+{3+{4+5!-5}-5}-{3+{4+F-5!}-T}}
random bdd={1+{3+4!}-{2+4-T}}
random bdd={3+5-T}
random bdd={2+F-3!}
random bdd=T
random bdd={1+{3+F-5!}-{2-4!}}
random bdd=1

b1={1+{3+F-4!}-{3+F-4}}
b2=2
b1={1+{3+F-4!}-{3+F-4}}
b2=3!
b1={1+{3+F-4!}-{3+F-4}}
b2={1+F-3!}
b1={1+{3+F-4!}-{3+F-4}}
b2={1+{2+3!-3}-3!}
b1={1+{3+F-4!}-{3+F-4}}
b2={2+F-{3+{4-5}-4!}}
b1={1+{3+F-4!}-{3+F-4}}
b2=2
b1={1+{3+F-4!}-{3+F-4}}
b2=2!
b1={1+{3+F-4!}-{3+F-4}}
b2=2!
b1={1+{3+F-4!}-{3+F-4}}
b2=F
b1={1+{2-{4+6-{5-6}}}}
b2=F
b1={1+{2-{4+6-{5-6}}}}
b2={1+3-{2+3-T}}
25

BTW, I can also replace the two intGen and bddGen by the single bddGen

  val bddGen: Gen[Bdd] = for {
    unused <- Gen.const(1)
  } yield Bdd.genRandomBdd(Bdd.genNumVars(8))
26

Yep. Personally, I would probably do:

  val bddGen: Gen[Bdd] = for {
    size <- Gen.const(8)
    num = Bdd.genNumVars(size)
  } yield Bdd.genRandomBdd(num)

Very much a matter of taste, though…

27

A related question, @jducoeur, when there’s a failure, the prop based testing framework is supposed to try to reproduce the failure with as small a test case as possible. What do I need to do to facilitate that? Won’t the generator above, always generate numbers with the same frequency? Ideally, I’d like to allow the framework to limit the maximum (8 in the case as programmed). Right? Can I modify the to allow this?

28

For ScalaCheck, I honestly don’t know, but the term you want to Google for is “shrinking”. I know we changed the details of the approach for the new ScalaTest harness, but I don’t know offhand how it is implemented in ScalaCheck.

1 Like