5 ms·

The author focuses on the state machine and parallel aspect of PBT, but there are other aspects that might have larger effect. One of these is coverage guided

The author focuses on the state machine and parallel aspect of PBT, but there are other aspects that might have larger effect. One of these is coverage guided PBT, check eg. Dan Luu's article: https://danluu.com/testing/ https://danluu.com/testing/ Another one, which I'm biased towards, is making shrinking automatic while keeping all the invariants you created while generating the values. I have a talk on this but the TL;DR is that - derived QuickCheck-like shrinker functions that work on values (shrink : a -> [a]) have issues with the constraints, making people turn off shrinking instead of dealing with the issues - rose tree "integrated shrinking" (eg. Hedgehog) follows the constraints of the generators, but has issues with monadic bind (using results of generators to dispatch to another generator) - the only approach that seems to magically "just work" is Hypothesis' "internal shrinking", which uses a layer of indirection to shrink lists of random choices instead of the values themselves. The disadvantage is that the generators are now parsers from the lists of bytes that can fail (introducing some inefficiency) and user can make a crazy generator that the internal shrinker will not be able to shrink perfectly. Nevertheless, it's the best DX of the three approaches, and given it's a small miracle people are testing at all, feels to me like the approach most worth building on as a testing library author.

AlexErrant 2y ago
> - rose tree "integrated shrinking" (eg. Hedgehog) follows the constraints of the generators, but has issues with monadic bind. We're at the limits of my amateur knowledge, but I believe this is a fundamental limitation of monadic bind/generators. Instead, you should prefer applicative generators for optimal shrinking. https://github.com/hedgehogqa/haskell-hedgehog/issues/473#issuecomment-1407709563 https://github.com/hedgehogqa/haskell-hedgehog/issues/473#is... In other words, applicative generators do not use "results of generators to dispatch to another generator", but instead shrinking is optimal due to the "parallel" nature of applicatives (I'm using "parallel" in the monadic sense, and not the sense of article's "threading" sense). Since applicatives are "parallel", they can shrink the generators independently. (Whereas monadic generators are in "series" and therefore shrinking one necessarily changes the behavior of the subsequent generator, as you noted.) Please feel free to link your talk if it's public!
- ctxc 2y ago
  I now realize how far I am from amateur knowledge, I don't understand any of this. But always interesting to discover an avenue I haven't explored before :)
  - AlexErrant 2y ago
    Haha yeah I kinda went off the deep end with applicatives. Here's a short primer on applicative vs monadic shrinking behavior using F# syntax https://github.com/hedgehogqa/fsharp-hedgehog/issues/419#issuecomment-1637154561 https://github.com/hedgehogqa/fsharp-hedgehog/issues/419#iss... You can think of `let!` as `let + await`, and `let! x ... and! y` as `await Parallel([x, y])`. Please feel free to ask any questions if it's still confusing!
    - Smaug123 2y ago
      Not quite accurate with the Parallel example, if I understand you correctly. Don Syme is explicit that applicative `async` should not implicitly start work in the thread pool (https://github.com/dotnet/fsharp/issues/10301#issuecomment-734280586 https://github.com/dotnet/fsharp/issues/10301#issuecomment-7...).
      - AlexErrant 2y ago
        My usage of "parallel/await" is entirely metaphorical; I was kinda going for a Javascript-esque syntax with "await Parallel" - I'm assuming most people aren't familiar with F#'s `and!`. It doesn't make sense for applicative generators to (necessarily) use the thread pool.
  - nine_k 2y ago
    To have an idea of monads being sequential, think about a JS Promise: promise.then(...).then(...).then(...)... Promises are (almost) monadic, and the chain is sequential. You can't make it parallel, and that's the point: monadic binding represents sequential computation, aka "the semicolon operator". To have an idea about applicatives being parallel, think about a list of functions, and a list of values; each function would be applied to a corresponding value, resulting in a list of results: results = [] for ix in range(functions): f = functions[ix] x = values[ix] results.append(f(x)) It's pretty obvious that you can do each f(x) in parallel and in any order, instead of the sequential code above. (Why would one care about this all? Because many daily things are functors, applicatives, and monads, e.g. a list is usually all three.)
epgui 2y ago
Anecdotally, Hypothesis was very far from "just working" for me. I don't think it's really production-ready, and that seems to be by design.[0] I did have quite a bit of prior experience with clojure.spec.alpha (with or without test.check), so despite some differences it's not like I was completely alien to the general ideas. [0] https://github.com/HypothesisWorks/hypothesis/issues/3493 https://github.com/HypothesisWorks/hypothesis/issues/3493
- eru 2y ago
  The issue seemed to be based on a misunderstanding of the implied probability distribution hypothesis uses to draw examples from?
  - epgui 2y ago
    The probability distribution in my case seemed to be a single result (the zero matrix) with P=1. So if that is intentional and by design, then you’re right, I don’t understand.
    - eru 2y ago
      Hypothesis doesn't try to give you a consistent probability distribution, especially not a uniform one. It has lots of heuristics to give you 'nasty' numbers in order to trigger more bugs. That's actually one big reason I prefer Hypothesis over eg Rust's proptest, which makes no attempt to give you 'nasty' numbers. Last time I checked, QuickCheck didn't make any attempts to give you floats well-known to cause trouble either (like inf, negative inf, different NANs, 0, 1, -1, the least positive float, the largest negative float, the largest finite float just before infinity etc.)
      - mjaniczek 2y ago
        There has been some research (can't find the paper right now but it was about F-metric or something?) suggesting uniform generators will trigger bugs more often than the edge-case-preferring ones. I'm still not too sure about whether I want to believe it though.
chriswarbo 2y ago
> - rose tree "integrated shrinking" (eg. Hedgehog) follows the constraints of the generators, but has issues with monadic bind > - the only approach that seems to magically "just work" is Hypothesis' "internal shrinking", which uses a layer of indirection to shrink lists of random choices instead of the values themselves. My preferred framework is falsify, which provides "internal integrated shrinking". It's similar to Hypothesis, but uses a tree of generators rather than a linear sequence (it's based on "selective functors", which are a nice interface that's also useful for e.g. validators). From https://hackage.haskell.org/package/falsify https://hackage.haskell.org/package/falsify > This library provides property based testing with support for internal integrated shrinking: integrated in the sense of Hedgehog, meaning that there is no need to write a separate shrinker and generator; and internal in the sense of Hypothesis, meaning that this works well even across monadic bind.
- mjaniczek 2y ago
  I've been talking with Edsko de Vries about Falsify when he was implementing it / writing the paper. Very cool stuff, although somewhat mind-bending :)

AlexErrant 2y ago

> - rose tree "integrated shrinking" (eg. Hedgehog) follows the constraints of the generators, but has issues with monadic bind. We're at the limits of my amateur knowledge, but I believe this is a fundamental limitation of monadic bind/generators. Instead, you should prefer applicative generators for optimal shrinking. https://github.com/hedgehogqa/haskell-hedgehog/issues/473#issuecomment-1407709563 https://github.com/hedgehogqa/haskell-hedgehog/issues/473#is... In other words, applicative generators do not use "results of generators to dispatch to another generator", but instead shrinking is optimal due to the "parallel" nature of applicatives (I'm using "parallel" in the monadic sense, and not the sense of article's "threading" sense). Since applicatives are "parallel", they can shrink the generators independently. (Whereas monadic generators are in "series" and therefore shrinking one necessarily changes the behavior of the subsequent generator, as you noted.) Please feel free to link your talk if it's public!

ctxc 2y ago
I now realize how far I am from amateur knowledge, I don't understand any of this. But always interesting to discover an avenue I haven't explored before :)
- AlexErrant 2y ago
  Haha yeah I kinda went off the deep end with applicatives. Here's a short primer on applicative vs monadic shrinking behavior using F# syntax https://github.com/hedgehogqa/fsharp-hedgehog/issues/419#issuecomment-1637154561 https://github.com/hedgehogqa/fsharp-hedgehog/issues/419#iss... You can think of `let!` as `let + await`, and `let! x ... and! y` as `await Parallel([x, y])`. Please feel free to ask any questions if it's still confusing!
  - Smaug123 2y ago
    Not quite accurate with the Parallel example, if I understand you correctly. Don Syme is explicit that applicative `async` should not implicitly start work in the thread pool (https://github.com/dotnet/fsharp/issues/10301#issuecomment-734280586 https://github.com/dotnet/fsharp/issues/10301#issuecomment-7...).
    - AlexErrant 2y ago
      My usage of "parallel/await" is entirely metaphorical; I was kinda going for a Javascript-esque syntax with "await Parallel" - I'm assuming most people aren't familiar with F#'s `and!`. It doesn't make sense for applicative generators to (necessarily) use the thread pool.
- nine_k 2y ago
  To have an idea of monads being sequential, think about a JS Promise: promise.then(...).then(...).then(...)... Promises are (almost) monadic, and the chain is sequential. You can't make it parallel, and that's the point: monadic binding represents sequential computation, aka "the semicolon operator". To have an idea about applicatives being parallel, think about a list of functions, and a list of values; each function would be applied to a corresponding value, resulting in a list of results: results = [] for ix in range(functions): f = functions[ix] x = values[ix] results.append(f(x)) It's pretty obvious that you can do each f(x) in parallel and in any order, instead of the sequential code above. (Why would one care about this all? Because many daily things are functors, applicatives, and monads, e.g. a list is usually all three.)

epgui 2y ago

Anecdotally, Hypothesis was very far from "just working" for me. I don't think it's really production-ready, and that seems to be by design.[0] I did have quite a bit of prior experience with clojure.spec.alpha (with or without test.check), so despite some differences it's not like I was completely alien to the general ideas. [0] https://github.com/HypothesisWorks/hypothesis/issues/3493 https://github.com/HypothesisWorks/hypothesis/issues/3493

eru 2y ago
The issue seemed to be based on a misunderstanding of the implied probability distribution hypothesis uses to draw examples from?
- epgui 2y ago
  The probability distribution in my case seemed to be a single result (the zero matrix) with P=1. So if that is intentional and by design, then you’re right, I don’t understand.
  - eru 2y ago
    Hypothesis doesn't try to give you a consistent probability distribution, especially not a uniform one. It has lots of heuristics to give you 'nasty' numbers in order to trigger more bugs. That's actually one big reason I prefer Hypothesis over eg Rust's proptest, which makes no attempt to give you 'nasty' numbers. Last time I checked, QuickCheck didn't make any attempts to give you floats well-known to cause trouble either (like inf, negative inf, different NANs, 0, 1, -1, the least positive float, the largest negative float, the largest finite float just before infinity etc.)
    - mjaniczek 2y ago
      There has been some research (can't find the paper right now but it was about F-metric or something?) suggesting uniform generators will trigger bugs more often than the edge-case-preferring ones. I'm still not too sure about whether I want to believe it though.

chriswarbo 2y ago

> - rose tree "integrated shrinking" (eg. Hedgehog) follows the constraints of the generators, but has issues with monadic bind > - the only approach that seems to magically "just work" is Hypothesis' "internal shrinking", which uses a layer of indirection to shrink lists of random choices instead of the values themselves. My preferred framework is falsify, which provides "internal integrated shrinking". It's similar to Hypothesis, but uses a tree of generators rather than a linear sequence (it's based on "selective functors", which are a nice interface that's also useful for e.g. validators). From https://hackage.haskell.org/package/falsify https://hackage.haskell.org/package/falsify > This library provides property based testing with support for internal integrated shrinking: integrated in the sense of Hedgehog, meaning that there is no need to write a separate shrinker and generator; and internal in the sense of Hypothesis, meaning that this works well even across monadic bind.

mjaniczek 2y ago
I've been talking with Edsko de Vries about Falsify when he was implementing it / writing the paper. Very cool stuff, although somewhat mind-bending :)