ScalaCheck генерирует StackOverflowError - PullRequest
Новая
       11

ScalaCheck генерирует StackOverflowError

2 голосов
/ 18 апреля 2019

Я хочу создать генераторы (для 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
    }
  }
}

1 Ответ

2 голосов
/ 20 апреля 2019

Очевидная интуиция заключается в том, что определение myGenFormula является рекурсивным. Это было бы объяснением переполнения стека.

Одна часть решения этой проблемы - добавление Gen.lzy в правильные места для myGenFormula. Это гарантирует выполнение одного пути генераторов и исключает ненужное выполнение всех рекурсивных генераторов.

Существует вторичная проблема с определением для myGenFormula, которая вызывает переполнение стека. Как написано, определение для myGenFormula статистически вряд ли закончится. Генератор genVar является оконечным генератором, но он одинаково взвешивается с другими несимметричными генераторами. Ничто не мешает ScalaCheck генерировать бесконечную глубину структур данных до достижения переполнения стека.

Есть два способа помочь завершить рекурсивные генераторы в ScalaCheck. Вы можете передать числовой аргумент глубины с помощью Gen.sized вашим генераторам, или вы можете использовать Gen.frequency.

Существует также проблема инициализации с взаимно рекурсивными генераторами. Вам нужно использовать ключевое слово lazy в генераторе val s, которое ссылается на myGenFormula, чтобы избежать этого.

Вот решение, которое включает в себя 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
  }
}
...