ScalaCheck生成StackOverflowError

Question

我想创建生成器(用于ScalaCheck)来生成命题公式。如果我创建一个生成器来使用变量和逻辑运算符(例如:A和B)生成公式，那么一切都是正确的。但是如果我加上或者，暗示或者不是，ScalaCheck会生成Exception: java.lang.StackOverflowError。

import org.scalacheck.Prop
import org.scalacheck.Properties
import org.scalacheck.Gen

object FormulaWffSpecification extends Properties("FormulaWff") {

  abstract class FormulaWff {
    def size: Int
    def depths: Int
  }
  case class And(left: FormulaWff, right: FormulaWff)     extends FormulaWff
  case class Or(left: FormulaWff, right: FormulaWff)      extends FormulaWff
  case class Implies(left: FormulaWff, right: FormulaWff) extends FormulaWff
  case class Not(son: FormulaWff)                         extends FormulaWff
  case class Var(string: String)                          extends FormulaWff

  val genAnd = for {
    left  <- myGenFormula
    right <- myGenFormula
  } yield And(left, right)

  val genOr = for {
    left  <- myGenFormula
    right <- myGenFormula
  } yield Or(left, right)

  val genImplies = for {
    left  <- myGenFormula
    right <- myGenFormula
  } yield Implies(left, right)

  val genNot = for {
    son <- myGenFormula
  } yield Not(son)

  val genVar = Gen.oneOf(Var("A"),Var("B"))

  def myGenFormula: Gen[FormulaWff] =
    Gen.lzy(Gen.oneOf(genVar, genAnd, genImplies, genOr, genNot))

  property("size(t) <= 2^(depths(t) + 1) - 1") = {
    Prop.forAll(myGenFormula) { f: FormulaWff =>
      f.size <= Math.pow(2, f.depths + 1) - 1
    }
  }
}

Answer 1

显而易见的直觉是，myGenFormula的定义是递归的。这就是堆栈溢出的原因。

解决这个问题的一个方法是确保在myGenFormula的正确位置添加Gen.lzy。这确保执行生成器的单个路径，并避免不必要地执行所有递归生成器。

myGenFormula的定义存在一个次要问题，它将导致堆栈溢出。正如所写的那样，myGenFormula的定义在统计上不太可能终止。genVar生成器是终止生成器，但它与其他非终止生成器具有相同的权重。没有什么可以阻止ScalaCheck在到达堆栈溢出之前生成无限深度的数据结构。

有两种方法可以帮助递归生成器在ScalaCheck中终止。您可以将带有Gen.sized的数值深度参数传递给生成器，也可以使用Gen.frequency。

还有一个相互递归生成器的初始化问题。您需要在引用myGenFormula的生成器val上使用lazy关键字来避免这种情况。

这里有一个解决方案，它在代码中散布lazy、Gen.lzy和Gen.frequency，这样它就可以运行并终止。您可能需要根据您的测试需求进行调整。

lazy val genAnd = for {
  left <- myGenFormula
  right <- myGenFormula
} yield And(left, right)

lazy val genOr = for {
  left <- myGenFormula
  right <- myGenFormula
} yield Or(left, right)

lazy val genImplies = for {
  left <- myGenFormula
  right <- myGenFormula
} yield Implies(left, right)

lazy val genNot = for {
  son <- myGenFormula
} yield Not(son)

val genVar =
  Gen.oneOf(Var("A"), Var("B"))

val myGenFormula: Gen[FormulaWff] =
  Gen.frequency(
    4 -> genVar,
    1 -> Gen.lzy(genAnd),
    1 -> Gen.lzy(genImplies),
    1 -> Gen.lzy(genOr),
    1 -> Gen.lzy(genNot))

property("myGenFormula") = {
  Prop.forAll(myGenFormula) { f: FormulaWff =>
    true
  }
}