arXiv:2203.00652cs.PL
Parsing Randomness: Unifying and Differentiating Parsers and Random Generators
Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.
Abstract
"A generator is a parser of randomness." This perspective on generators for random data structures is well established as folklore in the programming languages community, but it has apparently never been formalized, nor have its consequences been deeply explored. We present free generators, which unify parsing and generation using a common structure that makes the relationship between the two concepts precise. Free generators lead naturally to a proof that a large class of generators can be factored into a parser plus a distribution over choice sequences. Further, free generators support a notion of derivative, analogous to familiar Brzozowski derivatives of formal languages, that allows analysis tools to "preview" the effect of a particular generator choice. This, in turn, gives rise to a novel algorithm for generating data structures satisfying user-specified preconditions.
> But it's still a "blind" fuzzer and it would be nice to write one that gets feedback from code coverage somehow There have been simplistic attempts at this, e.g. instead of performing 100 tests, just keep going as long as coverage increases. The Choice Gradient Sampling…
chriswarboView on HNParent context