ScalaCheck 产生 StackOverflowError

Question

我想创建生成器（用于 ScalaCheck）来生成命题公式。如果我创建一个生成器来生成带有变量和逻辑运算符（例如：A 和 B）的公式，一切都是正确的。但是如果我添加或，暗示而不是，ScalaCheck 生成 Exception: java.lang.WhosebugError.

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
  }
}

ScalaCheck 产生 StackOverflowError

ScalaCheck generates StackOverflowError

scala

scalacheck