ScalaCheck 生成 StackOverflowError

Question

我想创建生成器(用于 ScalaCheck)来生成命题公式。如果我创建一个生成器来生成带有变量和逻辑运算符的公式(例如:A 和 B)，那么一切都是正确的。但如果我添加 or，暗示而不是，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
  }
}