Change shrinking algorithm from flat streams to lazy trees.

[laelath]

This changes the shrinking algorithm used from flat ordered streams of a term and it's shrinks to a lazily evaluated tree of shrinks. This change allows the algorithm used to find a shrunken counterexample to use the structural information of a term and vastly improves the performance of shrinking terms like lists and programs. This PR also adds a new gen:with-shrinks combinator that takes a generator and a shrink function, and replaces the shrink tree for the generated value with recursive applications of the provided shrinking function.

~This PR is currently missing is the hash generators, but other than that is complete.~ hash generators have been implemented.

The new shrinking method means that any generators made with make-gen are not compatible with this PR, however all generators built from generator combinators should be compatible.

I am also considering changing the lazy list inside the shrink-tree structure to a stream of subtrees.

Closes #5

[Bogdanp]

I've skimmed this and think it looks fine. I'm going to want to try to see exactly how much stuff this is going to break in the wild and do a deeper review. Do you think you'll want to make more changes here or can I go ahead and review this tomorrow?

[laelath]

I think I definitely want to change the shrink tree structure from a promise of a list of shrink trees to a stream of shrink trees, because I've run into issues shrinking larger generated programs. That should be backwards compatible with what I already have since lists are implicitly streams, but I'm not sure when I'll have time to implement that, and it could be a separate pr too since it should be backwards compatible

[Bogdanp]

OK, cool. In that case, I'll wait until you make those changes. I don't think there's any rush to merge.

I've looked at my projects, and none of them use make-gen, nor do the projects I can find on GitHub that use the library, so I think it's safe to change it. I'll add a note to make-gen on the master branch that it's likely to change.

[laelath]

Changed the shrink-trees to use streams! Some other potentially controversial changes that I made are that I changed gen:tuple to allow taking zero args (just produces empty lists), this was mainly so I could add gen:tuple* that takes a list of generators and produces a tuple by sampling from each one. I also changed the contract on gen:frequency to only require that there is at least one non-zero element, rather than requiring that all the frequencies be non-zero. I did this because it still produces the right behavior (as long as the sum is non-zero), and it makes it easier to use computed frequencies.

[Bogdanp]

Thanks! This is great. I made some of my own changes on top in this branch. Would you mind giving that branch a spin to make sure I haven't broken anything for your use case? Mostly, the changes are organizational and I've kept most of your additions except for gen:tuple* (since it's just (apply gen:tuple gs)) and gen:list-len (since it's just (apply gen:tuple (make-list len g))). If you feel strongly about including those two generators, we can, but my preference is to avoid providing overlapping generators if possible.

If everything looks good to you, I'll squash and merge that branch. Thanks again!

[laelath]

Those changes look good, except for some reason it takes noticeably longer to sample using bp-shrink-trees. But looking at your changes I am not sure why this would be the case, since if anything I would think you would have removed a bunch of contract checks.

[Bogdanp]

That's strange. When I test it against your lang-gen repo, I get the following timings with your branch:

cpu time: 1337 real time: 1352 gc time: 25
cpu time: 1280 real time: 1297 gc time: 24
cpu time: 1264 real time: 1285 gc time: 21

And with mine:

cpu time: 579 real time: 586 gc time: 15
cpu time: 573 real time: 583 gc time: 13
cpu time: 614 real time: 623 gc time: 14

Where the test program looks like this:

#lang racket/base

(require rackcheck
         "lang-gen.rkt")

(define gen:expr
  (lang-generator
   #:values 'integers 'booleans 'characters 'eof
   #:forms 'app 'if 'cond 'case 'let1 'let 'let* 'begin
   #:ops 'add1 'sub1 'abs 'not 'zero? 'integer?))

(collect-garbage)
(collect-garbage)

(random-seed 1337)
(time
 (for ([_ (in-range 100)])
   (sample (gen:expr '() (TAny)))))

Were you testing against some other kind of generator?

[laelath]

Oh sorry, the most recent branch is refactor. But tbh the performance difference was small enough that it probably doesn't matter, even if what I was running was testing it properly, which I'm not sure it was

[Bogdanp]

Ah, OK, in that case, I will go ahead and squash and merge these changes. Thanks again!