scalacheck Произвольные неявные и рекурсивные генераторы

Я вижу очень очевидную ошибку в scalacheck, так что если она действительно существует, я не вижу, как люди используют ее для рекурсивных структур данных.

Эта программа завершается с ошибкой StackOverflowError до того, как scalacheck вступает во владение при построении значения Arbitrary. Обратите внимание, что тип Tree и генератор для Trees дословно взяты из это руководство по 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

Еще более странно, если вы измените структуру двоичного дерева так, чтобы значение сохранялось в Nodes, а не в Leafs, и измените определение leafs и nodes так:

  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) ?


scala recursive-datastructures scalacheck
person Daniel Martin    schedule 07.11.2013    source источник
comment
Предположение: может быть, ваш первый trees всегда оценивает оба аргумента, а тот, который использует if, - нет?   -  person pedrofurla    schedule 07.11.2013
comment
Жаль, oneOf действительно строг: scalacheck.googlecode.com/svn/artifacts/1.7/doc/api/org/   -  person pedrofurla    schedule 07.11.2013

Ответы (3)


arrow_upward
12
arrow_downward

Проблема в том, что когда Scala оценивает trees, это заканчивается бесконечной рекурсией, поскольку trees определяется в терминах самого себя (через nodes). Однако, когда вы помещаете какое-либо выражение, отличное от trees, в качестве первой части вашего for-expression в nodes, Scala задерживает вычисление остальной части for-expression (обернутой в цепочки вызовов map и flatMap), и бесконечные рекурсии не будет.

Как говорит педрофурла, если бы oneOf не было строгим, этого, вероятно, не произошло бы (поскольку Scala не будет сразу оценивать аргументы). Однако вы можете использовать Gen.lzy, чтобы указать на лень. lzy берет любой генератор и откладывает оценку этого генератора до тех пор, пока он действительно не будет использован. Итак, следующее изменение решает вашу проблему:

def trees: Gen[Tree] = Gen.lzy(Gen.oneOf(leafs, nodes))
person rickynils    schedule 07.11.2013
comment
Это по-прежнему терпит неудачу примерно в одной трети времени внутри кода scalacheck, но он действительно отвечает на мой вопрос и перемещает StackOverflowError из создания объекта Arbitrary туда, где он оценивается. Принимаю этот ответ, но я опубликую отдельно то, что мне в конечном итоге пришлось сделать, чтобы помочь людям, которые находят это с помощью веб-поиска. - person Daniel Martin; 07.11.2013

arrow_upward
12
arrow_downward

Несмотря на то, что после ответа Rickard Nilsson выше я избавился от константы StackOverflowError при запуске программы, я все равно нажал a StackOverflowError примерно в одном случае из трех, когда я действительно попросил scalacheck проверить свойства. (Я изменил 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.

person Daniel Martin    schedule 07.11.2013

arrow_upward
2
arrow_downward

Небольшое обобщение подхода в собственном ответе Дэниела Мартина заключается в использовании 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)
person Alexey Romanov    schedule 17.06.2016