scalacheck中的Arbitrary隐式类型和递归生成器

Question

我发现scalacheck存在一个非常明显的bug，如果真的存在这个问题，我无法理解人们如何在递归数据结构中使用它。

在构造Arbitrary值时，此程序在scalacheck接管之前因StackOverflowError而失败。请注意，Tree类型和Tree的生成器直接从这个scalacheck教程中取出。

package treegen

import org.scalacheck._
import Prop._

class TreeProperties extends Properties("Tree") {

  trait Tree
  case class Node(left: Tree, right: Tree) extends Tree
  case class Leaf(x: Int) extends Tree

  val ints = Gen.choose(-100, 100)

  def leafs: Gen[Leaf] = for {
    x <- ints
  } yield Leaf(x)

  def nodes: Gen[Node] = for {
    left <- trees
    right <- trees
  } yield Node(left, right)

  def trees: Gen[Tree] = Gen.oneOf(leafs, nodes)

  implicit lazy val arbTree: Arbitrary[Tree] = Arbitrary(trees)

  property("vacuous") = forAll { t: Tree => true }
}

object Main extends App {
  (new TreeProperties).check
}

更奇怪的是，一些本应该不影响程序运行的修改似乎会让程序正常工作。例如，如果您将trees的定义更改为以下内容，则可以顺利通过：

  def trees: Gen[Tree] = for {
    x <- Gen.oneOf(0, 1)
    t <- if (x == 0) {leafs} else {nodes}
  } yield t

更奇怪的是，如果您改变二叉树结构，使得值存储在节点上而不是叶子上，并修改叶子和节点的定义为：

  def leafs: Gen[Leaf] = Gen.value(Leaf())

  def nodes: Gen[Node] = for {
    x <- ints     // Note: be sure to ask for x first, or it'll StackOverflow later, inside scalacheck code!
    left <- trees
    right <- trees
  } yield Node(left, right, x)

它之后能够正常工作。

这是怎么回事？为什么构建Arbitrary值最初会导致堆栈溢出？为什么看起来scalacheck生成器对微小的更改如此敏感，而这些更改不应影响生成器的控制流？

为什么我的表达式oneOf(0,1)与原始的oneOf(leafs, nodes)没有完全等价？

- Daniel Martin

---

推测：您的第一个“trees”是否总是评估两个参数，而使用“if”的那个不会？ - pedrofurla

很遗憾，“oneOf”确实很严格：http://scalacheck.googlecode.com/svn/artifacts/1.7/doc/api/org/scalacheck/Gen$.html - pedrofurla

Answer 1

问题在于当Scala评估 trees 时，它会陷入无尽的递归，因为 trees 是通过 nodes 自我定义的。但是，当您在 nodes 中将一些其他表达式作为for-表达式的第一部分时，Scala将延迟for-表达式的其余部分（通过 map 和 flatMap 调用链包装），并且无限递归将不会发生。

正如 pedrofurla 所说，如果 oneOf 不是严格的，可能不会发生这种情况（因为Scala不会立即评估参数）。但是，您可以使用 Gen.lzy 显式地表示惰性。 lzy 接受任何生成器并延迟该生成器的评估，直到实际使用它为止。因此，以下更改解决了您的问题：

def trees: Gen[Tree] = Gen.lzy(Gen.oneOf(leafs, nodes))

- Rickard Nilsson

---

这仍然在scalacheck代码内部大约有三分之一的时间失败，但它确实按照我的问题进行了回答，并将 StackOverflowError 从 Arbitrary 对象的创建移动到其被评估的地方。接受这个答案，但我会单独发布我最终必须做的事情，以帮助那些通过网络搜索找到这个问题的人。 - Daniel Martin

Answer 2

尽管按照上面Rickard Nilsson的回答，可以消除程序启动时的常量StackOverflowError，但实际要求scalacheck检查属性时，仍会有约三分之一的概率遇到StackOverflowError。（我将上面的Main更改为运行.check 40次，会看到它成功两次，然后出现堆栈溢出错误，然后再成功两次，以此类推。）

最终，我不得不在递归深度上设置一个硬性阻塞，在未来使用scalacheck检查递归数据结构时，我想这就是我要做的事情：

  def leafs: Gen[Leaf] = for {
    x <- ints
  } yield Leaf(x)

  def genNode(level: Int): Gen[Node] = for {
    left <- genTree(level)
    right <- genTree(level)
  } yield Node(left, right)

  def genTree(level: Int): Gen[Tree] = if (level >= 100) {leafs}
                                       else {leafs | genNode(level + 1)}
  lazy val trees: Gen[Tree] = genTree(0)

有了这个改变，scalacheck就再也不会遇到StackOverflowError的错误了。

- Daniel Martin

Answer 3

在丹尼尔·马丁的回答中，稍微概括一下他的方法，可以使用sized。类似这样（未经测试）：

def genTree() = Gen.sized { size => genTree0(size) }

def genTree0(maxDepth: Int) = 
  if (maxDepth == 0) leafs else Gen.oneOf(leafs, genNode(maxDepth))

def genNode(maxDepth: Int) = for {
  depthL <- Gen.choose(0, maxDepth - 1)
  depthR <- Gen.choose(0, maxDepth - 1)
  left <- genTree0(depthL)
  right <- genTree0(depthR)
} yield Node(left, right)

def leafs = for {
  x <- ints
} yield Leaf(x)

- Alexey Romanov