How to write a generator for a hierarchical structure

Question
1

I’m trying to understand generators and ScalaCheck. I finally stumbled upon scala-excercises which seems to give a pretty easy introduction. But I don’t understand it well enough to write a generator for the structure I need.

I want to generate a node given a positive integer N. I have a function which will generate such a structure. (BTW, I’m using a capital N simply so I can pattern match against it. Is this the correct way?)

  val rgen = scala.util.Random

  def genRandomBdd(N: Int): Bdd = {
    def recur(level: Int): Bdd = {
      val r = rgen.nextInt(2)    // 0 at 50%  and 1 at 50%
      (r, level) match {
        case (0, N) => BddTrue
        case (1, N) => BddFalse
        case (0, _) => recur(level + 1)
        case (_, _) => Bdd(level + 1, recur(level + 1), recur(level + 1))
      }
    }
    recur(0)
  }

So I can generate a random structure by calling genRandomBdd(N).
Now, how do I write the Gen definition for ScalaCheck? And where does the N come from?

Additionally since the structure is exponentially larger as a function of N, (i.e., a Bdd built from N is twice as big as the Bdd built from N-1) so I would like that when ScalaCheck runs the test that it chose N-1 twice as often as N. I.e., N=1 is twice as frequent as N=2, N=2 is twice as frequent as N=3, etc.

2

I don’t know ScalaCheck at all well (others might chime in), but the cognate in ScalaTest 3.1 (which has this stuff built in) would be more or less (NB: off the top of my head, forgive errors):

val bddGen: Generator[Bdd] = for {
  i <- ints
}
  yield genRandomBdd(i)

ints is the standard Generator for integers (it spits out randomized numbers, with a bit of biased towards the common edge cases), and this is simply transforming that to a Generator of Bdds.

I think it’s roughly similar for ScalaCheck, but can’t swear to that…

3

When I copy/paste the example from scala-excercises.org my system is not able to resolve the symbol check.

import org.scalatest.FunSuite
import robdd._

class BddSuite extends FunSuite {

  test("bdd with ScalaCheck") {
    import org.scalacheck.Gen
    import org.scalacheck.Prop.forAll

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

    val bddGen: Gen[Bdd] = for {
      i <- intGen
    }
      yield Bdd.genRandomBdd(i)

    check {
      forAll { b: Bdd => {
        b == Not(Not(b))
      }
      }
    }
  }

58

I have added the recommended (from scalacheck.org) line to my build.sbt file

libraryDependencies += "org.scalacheck" %% "scalacheck" % "1.14.0" % "test"

This indeed allows the compiler to find symbols such as Gen and forAll, but check is still missing.

Any suggestions?

4

Again, not a ScalaCheck expert, but I think check is inappropriate in this situation. Try just removing that, so that the forAll stands on its on – that’s what I would normally expect it to look like.

As far as I can tell, check is a method on Properties. This syntax might be legal if you are building your tests entirely in ScalaCheck, extending Properties instead of FunSuite, but I think it’s inappropriate inside ScalaTest.

5

Hmm. Ok, I’ll try it, but what is supposed to trigger the properties to get tested?

6

The forAll. :slight_smile:

You can either go with the ScalaTest way (forAll) or the ScalaCheck properties way (check).

ScalaTest documentation (both user guide and API docs) is really good - you should find everything there you need.

Best regards,
Patrick

7

Well the ScalaTest documentation is huge, and it is not obvious how to get started. I have absolutely no doubt that it is very great for the expert, but it is scary for the beginner. That’s why I was drawn by the scala-excercises description. It is just disappointing, that it does not seem to work as the page claims.

8

So here is an example of something that is completely unobvious to me using scalatest. This is the content of my file. The editor (and I presume also scalar), cannot resolve Generator nor forAll .

import org.scalatest._
import robdd._

class BddSuite2 extends FunSuite {
  test("bdd with ScalaCheck") {

    val intGen: Generator[Int] = for {
      i <- Bdd.genNumVars(6)
    } yield i

    val bddGen: Generator[Bdd] = for {
      i <- intGen
    }
      yield Bdd.genRandomBdd(i)

    forAll { b: Bdd => {
      b == Not(Not(b))
    }
    }
  }
}

39

What should I try to make it work?

9

You need to home in on one approach - ScalaTest Generator != ScalaCheck Gen. Furthermore, if you want to go with ScalaCheck, you must import ScalaCheck (ScalaTest only provides integration bindings, not the ScalaCheck API itself) and mix in GeneratorDrivenPropertyChecks.

Assume you have this code:

sealed trait BoolExp {
  def apply(): Boolean
}

case object True extends BoolExp {
  override def apply(): Boolean = true
}

case object False extends BoolExp {
  override def apply(): Boolean = false
}

case class Not(exp: BoolExp) extends BoolExp {
  override def apply(): Boolean = !exp()
}

case class And(a: BoolExp, b: BoolExp) extends BoolExp {
  override def apply(): Boolean = a() && b()
}

case class Or(a: BoolExp, b: BoolExp) extends BoolExp {
  override def apply(): Boolean = a() || b()
}

Then this code (in the same package in the test folder) should work:

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

class BoolExpTest
    extends FunSuite
      with Matchers
      with GeneratorDrivenPropertyChecks {

  private val boolExpGen: Gen[BoolExp] = {
    import Gen._
    val exp = lzy(boolExpGen)
    Gen.oneOf(
      const(True),
      const(False),
      exp.map(Not),
      for(a <- exp; b <- exp) yield And(a, b),
      for(a <- exp; b <- exp) yield Or(a, b)
    )
  }

  private implicit val arbitraryBoolExp: Arbitrary[BoolExp] =
    Arbitrary(boolExpGen)

  test("double negation") {
    forAll { exp: BoolExp =>
      Not(Not(exp))() should be (exp())
    }
  }

}

You may want to tweak configuration parameters and/or throw in sized generators later for better control of the tree shape, perhaps.

Best regards,
Patrick

1 Like
10

Note that this is all a little complex. The above link to “the ScalaTest way” isn’t actually the ScalaTest way – it’s ScalaTest-plus-ScalaCheck. So you are going to need both ScalaTest imports (for the extends FunSuite and the test syntax) and ScalaCheck imports (for Generator and forAll and such).

OTOH, as of ScalaTest 3.1, similar functionality has been built into ScalaTest proper. That will be available as org.scalatest.prop._ IIRC. But it’s new enough (like, I was working on it in January) that you may not want to get into it right now.

(As @sangamon alludes to, one way to tell the difference between the two is that ScalaCheck uses Gen, and the new ScalaTest version uses Generator. There are a bunch of little differences like that in the details, but conceptually both systems do the same stuff.)

11

Yeah, I’m a bit surprised – they tend to be good about this stuff, but appear to have overlooked some details in their introductions in this case.

And yeah, the ScalaTest docs can be a bit overwhelming. We do our best (and I take some pride in the new docs for the prop package), but are sorry when it isn’t clear…

12

Thanks Patrick, I’m trying to re-intepret that helpful piece of code into my application.
Can you explain what should be is? Is it commutative? I.e., is a should be b the same as b should be a?

Also, can you please explain whether the private indication is necessary. I’m probably going to eventually want to use Bdd generators in several different classes. Not now, but in the coming weeks.

Is it a problem that I’ve redefined the equals method? In my case I have redefined equals for the Bdd class to be eq. I.e., I want copies of object to be unequal. Is this compatible with the should be operator?

sealed abstract class Bdd (val ident:Int) {
  override def equals(that: Any): Boolean = {
    that match {
      case b: Bdd => this eq b
      case _ => false
    }
  }
...
13

Quick summary: ScalaTest is really, really fond of having its own little DSL. There are many dialects of it; which version you have available depends on your imports and/or mixed-in traits. The general buzzword here is “Matchers”, and it’s well worth familiarizing yourself with the Scaladocs for Matchers – I look at that page frequently when using ScalaTest.

So should be is basically just a synonym for equality, as an assertion. It produces slightly nicer output on failure than plain assert(), but the semantics are largely assert(a == b).

14

Also back to the original question, because I think I’m getting close to making it work.
I have a function which will generate a random integer with the distribution I want. I.e., given a maximum N, it will return an integer between 1 and N, with 1 being twice as likely as 2, and 2 being twice as likely as 3 etc. And given such an integer I have a function which will generate a random Bdd with that many levels.

object Bdd {
...

  val rgen = scala.util.Random

  def genRandomBdd(N: Int): Bdd = {
    def recur(level: Int): Bdd = {
      val r = rgen.nextInt(2)
      (r, level) match {
        case (0, N) => BddTrue
        case (1, N) => BddFalse
        case (0, _) => recur(level + 1)
        case (_, _) => Bdd(level + 1, recur(level + 1), recur(level + 1))
      }
    }
    recur(0)
  }

  def genNumVars(N:Int):Int = {
    // Generate an integer between 1 and N inclusive with a special distribution.
    // 1 is twice as likely as 2
    // 2 is twice as likely as 3
    // k is twice as likely as k+1 for each k>=1
    def recur(acc: Int, remaining: Int): Int = {
      (rgen.nextInt(2), acc, remaining) match {
        case (_, _, 0) => acc
        case (1, _, _) => recur(1 + acc, remaining - 1)
        case (_, _, _) => recur(acc, remaining - 1)
      }
    }
    recur(0, N)
  }
}

So here is what I’ve attempted based on Patrick’s example, but it’s not quite right yet.

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

class BddSuite2 extends FunSuite
  with Matchers
  with GeneratorDrivenPropertyChecks {

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

  val bddGen: Gen[Bdd] = for {
    i <- intGen
  } yield Bdd.genRandomBdd(i)

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

  test("bdd double negation") {
    forAll { b: Bdd =>
      Not(Not(b)) should be(b)
    }
  }
}

The compiler error I get is the following.

Error:(11, 26) value map is not a member of Int
      i <- Bdd.genNumVars(6)

Maybe someone can point out what’s wrong. Or am I completely on the wrong path altogether?

15

And If I’ve overridden == to mean eq, the should be respects that?

16

It’s not strictly a problem – folks do that all the time – but note that it is surprisingly dangerous, and tricky to get right. Suffice it to say, in the presence of possible sub-classes, there are a variety of possible traps. (So long as you’re not subclassing Bdd it’s probably fine, but I recommend thinking of this as a danger zone.)

Also, it is usually recommended to redefine hashCode if you are redefining equals – while it’s not strictly required, lots of code assumes that these behave in sync, so it’s easy to get into unobvious trouble if you override one and not the other.

17

That’s an extremely good question, and I don’t know offhand. I recommend reading through the Matchers section on checking equality.

18

Can I just replace Not(Not(b)) should be(b) with assert(b == Not(Not(b))) and dispense with the matchers?

19

The compiler error is correct, if a bit unhelpful.

The thing is, Gen is a Monad – which in squishy Scala terms means that it has definitions for the map and flatMap functions. Those functions are what allows a type to be used in a for comprehension – the for literally gets translated into calls to them.

genNumVars() returns a plain Int. Int isn’t a Monad, so it’s illegal to use in for because it doesn’t have a concept of map. You can’t just take any random value and casually use it as a Gen – you have to either start from an existing Gen, or use a utility function that turns your value into one.

So I guess the question is, what are you trying to do here? A Gen is, as the name suggests, a Generator – it produces a sequence of values of a desired type. intGen doesn’t really makes sense: it’s just taking one Int, the output of genNumVars. Which I think is legal, and there’s probably a utility function to do that in ScalaCheck, but I suspect isn’t what you want.

BTW, I should note that there’s a good (if somewhat out of date) book on ScalaCheck. This comes with a disclaimer that my boss is the publisher, but it’s basically how I learned this stuff.

20

Likely yes. The failure output won’t be as pretty and informative, but it ought to work.