scalacheck Ixtiyoriy implisitlar va rekursiv generatorlar

Men skalacheck bilan juda aniq xato bo'lib tuyulayotganini ko'rmoqdaman, shuning uchun agar u haqiqatan ham mavjud bo'lsa, odamlar uni rekursiv ma'lumotlar tuzilmalari uchun qanday ishlatishini ko'ra olmayman.

Ushbu dastur Arbitrary qiymatini yaratishda skalacheckni o'z zimmasiga olishdan oldin StackOverflowError bilan muvaffaqiyatsiz tugadi. Esda tutingki, Tree turi va Trees uchun generator so'zma-so'z ushbu skalacheck qo'llanmasi.

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
}

G'alati tomoni shundaki, hech narsaga ta'sir qilmasligi kerak bo'lgan o'zgarishlar dasturni ishlashi uchun o'zgartiradi. Misol uchun, agar siz trees ta'rifini bunga o'zgartirsangiz, u hech qanday muammosiz o'tadi:

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

Hatto g'alati, agar siz ikkilik daraxt strukturasini o'zgartirsangiz, qiymat Leafs emas, balki Nodes da saqlanadi va leafs va nodes ta'rifini quyidagicha o'zgartirsangiz:

  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)

Keyin u ham yaxshi ishlaydi.

Bu yerda nima bo'lyapti? Nima uchun Arbitrary qiymatini yaratish dastlab stekning to'lib ketishiga olib keladi? Nima uchun skalacheck generatorlari generatorlarning boshqaruv oqimiga ta'sir qilmasligi kerak bo'lgan kichik o'zgarishlarga juda sezgir bo'lib tuyuladi?

Nima uchun yuqoridagi oneOf(0, 1) bilan ifodalaganim asl oneOf(leafs, nodes) ga to'liq mos kelmaydi?


scala recursive-datastructures scalacheck
person Daniel Martin    schedule 07.11.2013    source manba
comment
Tahminlar: birinchi trees har doim ikkala argumentni baholaydi, if dan foydalanadigan esa buni baholamaydimi?   -  person pedrofurla    schedule 07.11.2013
comment
Bu uyat, oneOf haqiqatan ham qattiqqo‘l: scalacheck.googlecode.com/svn/artifacts/1.7/doc/api/org/   -  person pedrofurla    schedule 07.11.2013

Javoblar (3)


arrow_upward
12
arrow_downward

Muammo shundaki, Scala trees ni baholaganda, u cheksiz rekursiya bilan yakunlanadi, chunki trees o'z-o'zidan aniqlangan (nodes orqali). Biroq, nodes ga trees dan boshqa iborani nodes dagi ifodaning birinchi qismi sifatida qo'yganingizda, Scala ifodaning qolgan qismini (map va flatMap chaqiruvlar zanjiriga o'ralgan) va cheksizni baholashni kechiktiradi. rekursiya sodir bo'lmaydi.

Pedrofurla aytganidek, agar oneOf qat'iy bo'lmasa, bu sodir bo'lmaydi (chunki Skala dalillarni darhol baholamaydi). Biroq, dangasalik haqida aniq bo'lish uchun Gen.lzy dan foydalanishingiz mumkin. lzy har qanday generatorni oladi va u haqiqatan ham foydalanilgunga qadar ushbu generatorni baholashni kechiktiradi. Shunday qilib, quyidagi o'zgarish muammoingizni hal qiladi:

def trees: Gen[Tree] = Gen.lzy(Gen.oneOf(leafs, nodes))
person rickynils    schedule 07.11.2013
comment
Bu hali ham skalacheck kodi ichidagi vaqtning uchdan birida bajarilmaydi, lekin u mening savolimga so'ralganidek javob beradi va StackOverflowError ni Arbitrary ob'ektini yaratishdan tashqariga va u baholanadigan joyga ko'chiradi. Bu javobni qabul qilaman, lekin men buni veb-qidiruv orqali topadigan odamlarga yordam berish uchun oxir-oqibat nima qilishim kerakligini alohida e'lon qilaman. - person Daniel Martin; 07.11.2013

arrow_upward
12
arrow_downward

Yuqoridagi Rikard Nilssonning javobidan keyin dastur ishga tushganda doimiy StackOverflowError dan xalos bo‘lgan bo‘lsam-da, men hali ham urgan bo‘lardim. a StackOverflowError taxminan bir marta uch marta men aslida xususiyatlarini tekshirish uchun scalacheck so'radim. (Men yuqoridagi Main ni .check ni 40 marta ishlatish uchun o'zgartirdim va uning ikki marta muvaffaqiyatli bo'lishini, keyin stekning to'lib ketishi bilan muvaffaqiyatsiz bo'lishini, keyin ikki marta muvaffaqiyatli bo'lishini va hokazo.)

Oxir-oqibat, men rekursiyaning chuqurligiga qattiq blok qo'yishga majbur bo'ldim va men kelajakda rekursiv ma'lumotlar tuzilmalarida skalacheckdan foydalanganda shunday qilaman deb o'ylayman:

  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)

Ushbu o'zgarish bilan skalacheck hech qachon StackOverflowError bilan ishlamaydi.

person Daniel Martin    schedule 07.11.2013

arrow_upward
2
arrow_downward

Daniel Martinning o'z javobidagi yondashuvni biroz umumlashtirish sized. Shunga o'xshash narsa (sinovdan o'tmagan):

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