https://kotlinlang.org
Join Slack
<@U12AGS8JG> do you still recall our convo about edgecases missing when there's one arb with empty e...
# kotest
m
@sam do you still recall our convo about edgecases missing when there's one arb with empty edgecases? i'd be inclined to look into fixing that in the next few days. would this be the right time for me to start looking at it or do i wait until 4.5?
s
yeah I remember us talking about it but can't remember what the issue was again or what we decided
m
If we bind 3 arbs, and if one have empty edgecases then the final arb has no edgecases. It was not great but we decided that it's acceptable because the Cartesian product with an empty list is always an empty list. We decided that we can fix it but decided to defer. I proposed that because we were doing the deprecation of the Arb samples that returns sequence. I was thinking it might be a bit much if we bundle those two in the same release.
s
Ok I recall now
what was the fix again, take a random value if edgecases is empty ?
👍 1
So we added that stuff in September according to git log so it would have gone into the 4.3 release in October. I think we could make the change for 4.5.
m
Awesome. Yeah. That was the proposition. Technically we have the rough sketch of it. https://kotlinlang.slack.com/archives/CT0G9SD7Z/p1598956183036700?thread_ts=1598866831.013300&amp;cid=CT0G9SD7Z I've modified that slightly and i think i got that to work.
s
If you would like to work on this, feel free, I think it's an important enhancement to arbs
m
Awesome expect a pr up by this weekend
👏🏻 1
Thanks Sam!
@sam thanks for your comments, i’m refactoring the code now. I like the idea of semi-random edges! I’m just trying to digest your idea there, so in terms of implementation, currently i do agree that 
EdgeCases.Random
as a sealed class member may raise some eyebrows (mine included). If i understand your comment correctly, is this what you’re thinking?
Copy code
sealed class EdgeCases<out A> {
   data class Static<A>(val values: NonEmptyList<A>) : EdgeCases<A>()
   data class SemiRandom<A>(val generate: (RandomSource) -> NonEmptyList<A>) : EdgeCases<A>()
}
When we’re operating in 
Arb
composition, the challenge is random seed would be provided much later. That means we need to think of a way to model 
EdgeCases
with the same principle to harvest 
rs
. In other words, if I were to oversimplify this a bit, we’ll probably get
Copy code
data class EdgeCases<out A>(val generate: (RandomSource) -> NonEmptyList<A>)
but yeah i think you’re also well aware of it, we basically have to have a common input domain, which is random seed
s
I was just throwing some thoughts out there to see what stuck
So one thing would be to change 
fun edgecases(): ...
to 
fun edgecases(rs: RandomSource):...
and then it's up to the arb if they want to return a static list or not
Another thing would be to introduce 3 levels, 
fun edges()
fun semiedges()
kind of thing (not sure if that's too much)
another way would be to return a function that accepts the RS and then returns, so 
fun edges() : (RandomSource) -> List<A>
which defaults to just 
= { edgecases() }
I'm not in the code right now so some of that may be nonsense 🙂
I think the easiest way would be to pass the random source into the edgecases method, and then Arb.bind can use that RS to call .sample on whatever it needs
m
So one thing would be to change 
fun edgecases(): ...
 to 
fun edgecases(rs: RandomSource):...
 and then it’s up to the arb if they want to return a static list or not,
another way would be to return a function that accepts the RS and then returns, so 
fun edges() : (RandomSource) -> List<A>
 which defaults to just 
= { edgecases() }
I think the easiest way would be to pass the random source into the edgecases method, and then Arb.bind can use that RS to call .sample on whatever it needs
yeah i do agree, that’s actually converging to this:
Copy code
data class EdgeCases<out A>(val generate: (RandomSource) -> NonEmptyList<A>)
except that we push the responsibility of conjuring edgecases to the arb implementation. That will work from the types perspective, implementation details can follow.
s
I don't think we even need the data class in this case ?
It's just wrapping a function
m
yeah that’s right
excellent, so I’ll refactor the code to boil this into arb, see how this goes. to confirm:
Copy code
Arb<A> {
   fun edges(rs: RandomSource): NonEmptyList<A>
}
We can also use List<A> with a 
check
that edgecases needs to be nonempty at generation time.. But i prefer that check done at compile time
s
I don't think edge cases should be non empty
there's plenty of arbs that won't have edge cases
but the RS should be supplied for cases where the arb can make an edge case with a random value
data class Person(val name: String)
what's the edge case for an Arb that generates that
m
ah right so you’re mentioning to push that defaulting to random at flatMap or bind. can do. I was thinking about types in here, so if we have this in 
Arb<A>
implementers can override edges to 
emptyList()
but yeah that’s legal as well. given we can guard it in flatMap that’s okay.
awesome
s
Yes exactly, I mean if you think we can do better, we can try, but just that edgecases(rs) should allow empty list for arbs where there are no sensible edgecase
can you call it 
fun edgecases(rs: RandomSource)
so it matches the other one ?
m
sounds good
s
the bind impl might need to change too, currently bindN delegates to bindN-1
m
so:
Copy code
Arb<A> {
   fun edgecases(rs: RandomSource): List<A>
}
bind will
Copy code
bind(arbA, arbB): Arb<B> {
   fun edgecases(rs: RandomSource): List<A> = // find out if any of the A or B edgecases is empty and default accordingly
}
flatmap will also work
Copy code
Arb<A>.flatMap(fn: (A) -> Arb<B>): Arb<B> {
   fun edgecases(rs: RandomSource): List<B> = this@flatMap.edgecases(rs).flatMap { a -> fn(a) // resolve edges here }
}
s
yea
m
the bind impl might need to change too, currently bindN delegates to bindN-1
what do you mean here?
s
Copy code
genA.bind(genB).bind(genC).bind(genD).bind(genE).bind(genF).bind(genG).map { (abcdef, g) ->
   val (abcde, f) = abcdef
   val (abcd, e) = abcde
   val (abc, d) = abcd
   val (ab, c) = abc
   val (a, b) = ab
   bindFn(a, b, c, d, e, f, g)
seems an odd way to do it
maybe it doesn't need to change, just talking out loud
m
ahh, yeah that was applicative right. we basically want product.
Copy code
Applicative[F[_]] {
   product(a: F[A], b: F[B]): F[(A, B)]
}
and then the rest will work by recursively applying product
👍🏻 1
i think they call it ap or something
s
ap inside applicative yes
m
qq do we need
Copy code
Arb<A>.withEdgecases(fn: (RandomSeed) -> List<A>): Arb<A>
and
Copy code
Arb<A>.modifyEdgecases(fn: (initial: List<A>, rs: RandomSeed) -> List<A>): Arb<A>
s
yeah probably
👍 1
m
😢
Copy code
Overload resolution ambiguity. All these functions match.
public fun <A> Arb<TypeVariable(A)>.modifyEdgecases(f: (initial: List<TypeVariable(A)>, randomSource: RandomSource) → List<TypeVariable(A)>): Arb<TypeVariable(A)> defined in io.kotest.property.arbitrary in file arbs.kt

public fun <A> Arb<TypeVariable(A)>.modifyEdgecases(f: (List<TypeVariable(A)>) → List<TypeVariable(A)>): Arb<TypeVariable(A)> defined in io.kotest.property.arbitrary in file arbs.kt
kotlin can’t resolve pick up lambda types, I think i need to hack this to use RandomSource as receiver type if we were to maintain backward compatibilty
Copy code
fun <A> Arb<A>.modifyEdgecases(f: RandomSource.(List<A>) -> List<A>): Arb<A> =
   arbitrary({ rs -> f(rs, this@modifyEdgecases.edgecases(rs)) }, { this.next(it) })
sam any suggestion on naming here, that hack is just awkward to use
s
can you paste in the two functions that clash
m
Copy code
fun <A> Arb<A>.modifyEdgecases(f: (List<A>) -> List<A>): Arb<A> = TODO()
fun <A> Arb<A>.modifyEdgecases(f: (List<A>, RandomSource) -> List<A>): Arb<A> = TODO()
s
Copy code
fun <A> Arb<A>.modifyEdgecases(f: (List<A>) -> List<A>): Arb<A> = TODO()

@JvmName("modifyEdgecasesRandom")
fun <A> Arb<A>.modifyEdgecases(f: (List<A>, RandomSource) -> List<A>): Arb<A> = TODO()
Does that work ?
m
trying
nope, the call site can’t figure it out
s
you could try 
listOf(2,3) + it
You could also just rename the second one to modifyEdgecasesWithRandom or something
(not as nice I know)
m
listOf(2,3) + it
 
nope kotlin gave up here too
s
its wierd it fails, because only one of the functions has a single parameter
m
yeah
s
and you didn't declare parmaeters in the lamba
m
yeah i mean theoretically it should work, but apparently it can’t, let me search in youtrack if there’s a workaround for this
s
it works if you do 
a -> a + listOf(2,3)
but that's not very user friendly
m
yeah not really, i bet lots of users will complain
s
or just get stuck and ask us
so we want to avoid that
m
and we do have that in our codebase, so if we do that our build will fail and we need to refactor lots
s
true
I think a different name is the best we can do
m
ok, so this doesn’t work. because i need to know whether that the edges is static / semi-random. list doesn’t have that information..
Copy code
Arb<A> {
   fun edgecases(rs: RandomSource): List<A>
}
s
you're just going to provide a seed and get back some edge cases right
and if the edge cases is empty, bind will go over to sample(rs)
m
so for instance this code:
Copy code
"Arb.bind(a,b,c,d) should compute the cartesian product of edges" {
   val arbA = Arb.string(1)
   val arbB = Arb.string().withEdgecases("a", "b")
   val arbC = Arb.string(1)
   val arbD = Arb.string().withEdgecases("a", "b")
   val arb = Arb.bind(arbA, arbB, arbC, arbD) { a, b, c, d -> a + b + c + d }
   arb.edgecases(RandomSource.seeded(1234L)) shouldContainExactlyInAnyOrder listOf(
      "Uaka", "%bca", "?aCb", "KbGb"
   )
}
instead of generating
Copy code
["Uaka", "%bca", "?aCb", "KbGb"]
it generates
Copy code
["Uaka", "Uakb", "%bca", "%bcb"]
because essentially when list is created, it’ll preserve its value instead of keep generating a new one
s
can you post up the bind code
m
Copy code
private fun <A, B, C> Gen<A>.bind(other: Gen<B>, fn: (A, B) -> C): Arb<C> {
   val thisArb = when (this) {
      is Arb -> this
      is Exhaustive -> this.toArb()
   }

   val otherArb = when (other) {
      is Arb -> other
      is Exhaustive -> other.toArb()
   }

   val arb = thisArb.flatMap { a -> otherArb.map { b -> fn(a, b) } }

   return object : Arb<C>() {
      override fun edgecases(): List<C> = arb.edgecases()
      override fun edgecases(rs: RandomSource): List<C> {
         val maybeEdgesA = NonEmptyList.fromList(thisArb.edgecases(rs))
         val maybeEdgesB = NonEmptyList.fromList(otherArb.edgecases(rs))
         return maybeEdgesA.fold(
            ifEmpty = {
               maybeEdgesB.fold(
                  ifEmpty = {
                     fn(thisArb.single(rs), otherArb.single(rs)).nel()
                  },
                  ifDefined = { edgesB ->
                     edgesB.map { b ->
                        val a = thisArb.single(rs)
                        fn(a, b)
                     }
                  }
               )
            },
            ifDefined = { edgesA ->
               maybeEdgesB.fold(
                  ifEmpty = {
                     edgesA.map { a: A ->
                        val b = otherArb.single(rs)
                        fn(a, b)
                     }
                  },
                  ifDefined = { edgesB ->
                     edgesA.flatMap { a: A ->
                        edgesB.map { b: B ->
                           fn(a, b)
                        }
                     }
                  }
               )
            }
         ).all
      }

      override fun sample(rs: RandomSource): Sample<C> = arb.sample(rs)

      override fun values(rs: RandomSource): Sequence<Sample<C>> = arb.values(rs)
   }
}
s
is this on a branch ?
actually doesn't matter
m
oh no it’s not - it’s on my local but this will work
Copy code
Arb<A> {
   fun edgecases(): (rs: RandomSource) -> List<A>
}
s
ok
m
or at least i have a feeling that it will
actually, now that i think about it, i don’t think that’ll work either that may work, because 
(rs: RandomSource) -> List<A>
is a kleisli
let me try that out first
s
What about something like this
Copy code
fun <A> edgesOrSample(edges: List<A>, gen: Gen<A>, rs: RandomSource): List<A> =
   if (edges.isEmpty()) listOf(gen.generate(rs).first().value) else edges

fun <A, B, C> Gen<A>.bind(other: Gen<B>, fn: (A, B) -> C): Arb<C> {

   val thisArb = when (this) {
      is Arb -> this
      is Exhaustive -> this.toArb()
   }

   val otherArb = when (other) {
      is Arb -> other
      is Exhaustive -> other.toArb()
   }

   return object : Arb<C>() {

      override fun edgecases(): List<C> = TODO() // previous cartesian combination
      override fun edgecases(rs: RandomSource): List<C> {
         val maybeEdgesA = thisArb.edgecases(rs)
         val maybeEdgesB = otherArb.edgecases(rs)
         // we don't create edges is none of the bound gens have edge cases
         return if (maybeEdgesA.isEmpty() && maybeEdgesB.isEmpty())
            emptyList()
         else
            edgesOrSample(maybeEdgesA, this@bind, rs).flatMap { a ->
               edgesOrSample(maybeEdgesB, other, rs).map { b ->
                  fn(a, b)
               }
            }
      }

      override fun sample(rs: RandomSource): Sample<C> = arb.sample(rs)
   }
}
m
I think that's going to run into a similar issue sam, because 
edgesOrSample
returns a concrete list
s
recap the issue ?
m
s
edgesOrSample is just a helper method that goes to sample(rs) if the edge cases are empty
it's not defined in arb
m
Yeah i know. The issue is around when the generation happen
With List, you have a concretely sampled item, so observe the second result vs the first one
The first is trully random because we have a lazily generated list.
s
in your example, what do you expect the edge cases to be, it's hard to work out from %bca etc what you expect to be there
Maybe shrink it down to 2 arbs to simply the example
m
yep so the expectation is:
Copy code
r1 a r2 a
r3 a r4 b
r5 b r6 a
r7 b r8 b
Instead we get
Copy code
r1 a r2 a
r1 a r2 b
r3 b r4 a
r3 b r4 b
notice how r1 and r2 as well as r3 and r4 are repeated because of concrete list
s
Ok, what's r ?
m
random
s
ok, strings have edge cases already
Ok I guess when minsize = maxsize they don't
m
yeah that’s not the issue. we kinda want a 
List<Edge<A>>
instead of 
List<A>
s
I don't know why what I pasted wouldn't work. Each time you invoke edgecases(rs) you're going to get a new random element.
m
this way we can interpret 
Edge<A> -> A
on every iteration
the issue is here
Copy code
val list = edgesOrSample(maybeEdgesA, this@bind, rs) // e.g. a, b
val anotherList = edgesOrSample(maybeEdgesB, this@bind, rs) // e.g. r1, r2

list.flatMap { first -> anotherList.map { second -> first to second } }
// a -> r1
// a -> r2
// b -> r1
// b -> r2
s
But you don't pull edges or sample out
I didn't do that in the example, I invoked it each time in the flat map
Copy code
edgesOrSample(maybeEdgesA, this@bind, rs).flatMap { a ->
  edgesOrSample(maybeEdgesB, other, rs).map { b ->
    fn(a, b)
  }  
}
m
oh yeah you did
s
If the maybeEdgesX are empty, they'll get a new random element each time
m
ah yeah! i made a silly mistake there
s
which to be honest, I'm not even sure if my (right?) way is right. Should the empty edge case be random each time, or just fixed. I mean is edge cases just becoming another non-edge case at this point.
m
i shouldn’t have assigned that to a val
s
if you have 4 arbs, 3 of which have edge cases, should be the 4th parameter be fixed while the other 3 cycle (obviously it would be random across different invocations of the test suite)
What I pasted works like what you wanted I think, but maybe we should consider if that's the right behavior
m
i think your right way is right (i hope this doesn’t confuse you even more). because essentially
Copy code
a, *
should work for any *
i.e. this should work
Copy code
1, x === 1, 1 or 1, 0
if we’re talking about boolean algebra
s
Copy code
val arbA = Arb.string().withEdgecases("a", "b")
val arbB = Arb.string().withEdgecases("c", "d")
val arbC = Arb.string().withEdgecases("e", "f")
val arbD = Arb.string(1)
In that scenario, I would probably expect (a, c, e, Z), (b, c, e, Z), (a, d, e, Z), (b, d, e, Z) and so on. Z being a random, but fixed element.
after all, we're just trying to fill in the bind with a missing edge case
m
In that scenario, I would probably expect (a, c, e, Z), (b, c, e, Z), (a, d, e, Z), (b, d, e, Z) and so on. Z being a random, but fixed element.
yeah ok so using the code sample you gave me i got the above behaviour, because of 
list.flatMap
s
I think the code I pasted would fix the first element and randomize the other one, pulling it out to vals would fix all parameters.
If you agree with me that any "missing" edge cases args should be a single fixed element for all edge cases generated in that run, then declare it all as vals before your flat map. If you think each missing edge case args should be random completely, then my code would work. While I think the former makes more sense, it's just a personal preference, I'm happy if you do whatever.
Either way, do you have enough to become unblocked ?
m
hmm.. the code that you pasted is good for monadic bind (flatMap) but i don’t think that’s going to work for (applicative) bind i think i gave you a wrong example. Here is the issue: imagine if we flip the situation
Copy code
fun list() = edgesOrSample(maybeEdgesA, this@bind, rs) // e.g. r1, r2
fun anotherList() = edgesOrSample(maybeEdgesB, this@bind, rs) // e.g. a, b
list.flatMap { first -> anotherList.map { second -> first to second } }
// r1 -> a
// r1 -> b
// r2 -> a
// r2 -> b
so this is the behaviour that you are after with
(a, c, e, Z), (b, c, e, Z), (a, d, e, Z), (b, d, e, Z)
s
Our bind isn't really applicative though is it, it's more like zip or mapN
🤔 1
I'm off to bed as I'm too old to rock n roll 🙂 I've invited you into the kotest org, so why don't you put up some test cases on a branch, with the work so far, and I'll have a play in the morning, because I think this is a lot more simple than we're making it sound here. And if I'm wrong, and am not fully understanding the issue, then at least I'll understand the issue when I run into the same problem 🙂
m
haha
sounds good
s
great thanks, appreciate you looking at this stuff.
m
@sam you’ve convinced me. my original idea was a bit too much to implement. 😆
i managed to solve that but i ended up creating a recursive type so that i can inject the rs after. I needed to create an 
Eval
type for trampolining etc. and I’m still in the middle of implementing flatmap and doing all the type gymnastics. it wasn’t worth it.
s
ok so it's coming along ok ?
m
haha yeah i’ve pushed that to the original branch, kept the bind to a monadic, so you’d get this behaviour
(a, c, e, Z), (b, c, e, Z), (a, d, e, Z), (b, d, e, Z)
s
I think that's good enough right
m
yeah
i can share my findings on the other one when i finished it just for fun somewhere here, it was a good exercise.
s
ok would be interested in seeing that
If you put the PR up I will merge when master becomes 4.5
m
i pushed it to the original branch, https://github.com/kotest/kotest/pull/2096/files we can iterate there. there’s quite a bit of changes, but should be pretty straightforward to review
thanks for your support @sam !
👍🏻 1
@sam sorry for the slow updates on the PR, things are pretty hectic on my side! The latest code should be ready for review in case you missed it.
3 Views
Open in Slack
PreviousNext
Powered by

kotlinlang

A modern programming language that makes developers happier.

Powered by