Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

implement trampolines for flatmap, map, filter, merge. #2900

Conversation

myuwono
Copy link
Contributor

@myuwono myuwono commented Mar 26, 2022

in this PR

  • implement trampolines for flatmap, map, filter, merge.
  • Remove suspension point allocation in single shot builder.

fixes #2896

Context:

Arb.flatMap, Arb.map, Arb.filter and Arb.merge was previously implemented using callbacks, where it creates a new arb which .edgecase and .sample function directly calls the receiver arb's function. While this works for shallow nestings, on bigger nestings and more complex structures this approach can easily exhaust the call stack.

In this PR i implemented a simple trampoline to transform the receiver Arb<A> to TrampolineArb<A>. TrampolineArb<A> stores the initial arb and all subsequent operation chains inside a list, which will be executed in order of application. This allows us to compose a longer chain of flatMaps without blowing up the stack. Visually it looks like this:

receiverArb
  .flatMap { value -> fn1(value) } 
  .flatMap { value -> fn2(value) } 
  ...
  .flatMap { value -> fnN(value) } 

// translated to
`TrampolineArb(receiverArb)`
[
  () -> Arb0
  (sampleOrEdgecase) -> Arb1,
  (sampleOrEdgecase) -> Arb2,
  ...
  (sampleOrEdgecase) -> ArbN
]

That function will then be computed by collapsing the function list from left to right and applying the random source from the context of .sample(rs) or .edgecase(rs). If one is familiar with the trampoline implementation of Free Monad, this more or less the same mechanism implemented without tail recursion and trampoline data type.

Similarly within arbitrary { } builder, it appears that suspensions also has a limit on the number of suspension points that can be stored. Since Continuations are single-shot anyway, we can instead pass in the type of action that the call site needs, e.g. whether it is an edgecase generation or sample generation. This way we can get rid of the .resume() call within the .bind() in favour of just a simple return.

…pension point allocation in single shot builder.
@myuwono myuwono marked this pull request as draft March 26, 2022 01:56
@myuwono myuwono changed the title implement trampolines for flatmap, map, filter, merge. [WIP] implement trampolines for flatmap, map, filter, merge. Mar 26, 2022
@myuwono myuwono changed the title [WIP] implement trampolines for flatmap, map, filter, merge. implement trampolines for flatmap, map, filter, merge. Mar 26, 2022
@myuwono myuwono requested a review from sksamuel March 26, 2022 03:16
@myuwono myuwono marked this pull request as ready for review March 26, 2022 03:21
@sksamuel sksamuel merged commit 8e9c423 into master Mar 26, 2022
@sksamuel sksamuel deleted the bugfix/trampoline-flatmap-and-remove-bind-suspension-allocation branch March 26, 2022 18:08
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Flaky java.lang.StackOverflowError using generators.
2 participants