Trampolines

[edmundnoble]

All of matryoshka's recursion operators at the moment are not stack-safe. However, always trampolining them can be a performance issue. Therefore, is there any interest in representing recursion schemes in a recursion-less fashion, so that they can be executed in a trampolined or partially-trampolined (a la http://blog.higher-order.com/blog/2015/06/18/easy-performance-wins-with-scalaz/) context?

One way to do this without sacrificing the ability to make plain (not trampolined) recursive calls for data which is known to be small is to write recursion schemes in CPS, such that an ordinary recursive function

def f(a: A): B

is represented as:

def f(a: A, loop: A => Trampoline[B]): Trampoline[B]) 

Then the scheme can make calls to loop instead of explicitly recursing, and it can be executed with each step trampolined, or with none of them trampolined, or with only steps exceeding some maximum stack size trampolined.

[sellout]

Thanks for opening this. It’s certainly something I’ve thought about and others have brought up. It just hasn’t affected us (SlamData) in practice yet, so we haven’t prioritized it.

I think the first step is to come up with some test cases (marked pending initially) that trigger stack overflows that are fixed by trampolining, so we can try a few different approaches.

[edmundnoble]

@sellout Makes sense, but it would require coverage of every recursion scheme in the entire library, seeing as they can all stack overflow. Perhaps migrating to a uniform representation of recursion schemes which can be tested on its own will be less prohibitive?

[sellout]

Curious on your feelings on this now. We’ve made some significant strides in terms of the way things are defined (although some of it hasn’t yet been PRed).

Almost all Recursive operations are now implemented in terms of cata (and Corecursive/ana), and while the default implementation of cata/ana isn’t stack-safe, they’re overridden in Mu/Nu. Also, if you are using something with direct & eager recursion (like Fix or Cofree or whatever), you can opt to use cataM[Trampoline] explicitly, no?

[edmundnoble]

Agreed. cataM[Trampoline] should provide sufficient stack-safety.

[sellout]

Cool, then I’m closing this and will expect specific issues for cases when this isn’t enough.

[ahoy-jon]

Hi ! cataM[Trampoline] wasn't enough to provide stack safety.

For reference, I let that here :

def cataTrampoline[E[_],A](t: Fix[E])(f: Algebra[E, A])
                  (implicit BT: Traverse[E]):Trampoline[A] = {
  //with regular cata being :
  //t.hylo[E,A](f, x => x.unFix)
  t.hyloM[Trampoline,E,A](
    x => Trampoline.delay(f(x)),
    x => Trampoline.delay(x.unFix))
}

[edmundnoble]

cataM[Trampoline] doesn't provide stack-safety, you're right. It uses pure[Trampoline] which is too strict in this case. That cataTrampoline should be fine.