Definitelytyped: @types/ramda - Use a trampolining technique to artificially increase depth of recursive type definitions

[mulias]

If you know how to fix the issue, make a pull request instead.

• [x] I tried using the @types/xxxx package and had problems.
• [x] I tried using the latest stable version of tsc. https://www.npmjs.com/package/typescript
• [x] I have a question that is inappropriate for StackOverflow. (Please ask any appropriate questions there).
• [x] [Mention](https://github.com/blog/821-mention-somebody-they-re-notified) the authors (see Definitions by: in index.d.ts) so they can respond.
  
  
  
  • Authors: @donnut, @tycho01, @mdekrey, @mrdziuban, @sbking, @afharo, @teves-castro, @1M0reBug, @hojberg, @samsonkeung, @angeloocana, @raynerd, @googol, @moshensky, @ethanresnick, @leighman, @CaptJakk, @deftomat, @deptno, @blimusiek, @biern, @rayhaneh, @rgm, @drewwyatt, @jottenlips, @minitesh, @krantisinh, @pirix-gh
  
  

If you do not mention the authors the issue will be ignored.

As tracked by https://github.com/Microsoft/TypeScript/issues/30188, the recently added recursive type for Curry is failing on TS3.4, since hitting the type instantiation depth limit of 50 now consistently gives a compiler error.

@pirix-gh points out in a comment on that issue that one way around the recursive limit is to complete the computation incrementally, using infer to save a intermediary variable and reset the instantiation depth. This is a pretty great trick, because it gives us everything we need to implement a continuation-passing trampoline:

Continuation-passing style is a popular intermediate format for compilers of function languages, because many control flow constructs can be elegantly expressed and tail call optimization is easy. When compiling to a language without optimized tail calls, one can avoid stack growth via a technique called trampolining. The idea is to not make the final continuation call inside the function, but to exit and to return the continuation to a trampoline. That trampoline is simply a loop that invokes the returned continuations. Hence, there are no nested function calls and the stack won’t grow.

To the best of my knowledge we can't implement the trampoline as a loop, but we can use it to greatly extends the lifespan or a recursive type.

I've put together a type level natural number library which uses this technique to handle over 1024 iterations of a recursive type. I'm not done with the readme yet, but hopefully it's pretty readable if you have experience with recursive types. In short:

• here's the definition for Add https://github.com/mulias/unnatural-ts/blob/master/src/big/Add.ts
• We represent a natural number as tuples of anys (nothing new here), so our goal is to construct a tuple of the appropriate length.
• We define Bounce, a type which computes a safe number of recursive steps (somewhere between 1 and ~40) and returns a continuation object that either contains the successfully computed result type, or the current incomplete state of the calculation.
• We tie everything together with a generic boilerplate type called Trampoline. This type wires together 32 bounces, and returns either the successfully computed result type or unknown.
• The repo implements a number of different operations and has tests, so I'm confident that this technique is generalizable to many different recursive types.

I'd be happy to try implementing Curry or other recursive types in this way, but I first wanted to gauge interest in using this kind of approach for @types/ramda. It seems like there's some uncertainty about using recursive types in TS right now, so I'm interested in figuring out how far this project wants to go down the recursive types path. Since recursive types aren't an officially supported feature, there's a danger in over-committing, and then having to re-work a bunch of types if a future TS upgrade breaks this technique. On the other hand, if recursive types continues to be a no-doc feature, using something like a trampoline gives us much more control over the behavior of these types.

[tycho01]

This isn't my call to make, but I for one would love to see this in, if only because:

• any techniques that have hit DT will automatically be used as part of TS regression testing;
• I'd definitely like for them to notice once they start breaking type recursion, as many advanced types rely on it.

[millsp]

Hi @mulias I haven't seen the types breaking on 3.4 or 3.5, I use this "trampoline technique" for ramda. Where is it failing?

I'm going to bring negative & positive number manipulation to TS soon (it's WIP)... And when it comes to adding numbers it its hard because of that limit of 50... TS should bring out something like annotations to tell the compiler that this is ok (iteration above 50) and TS should also stop pre-computing all the types that haven't received their input (generics) yet. Would reduce the amount of errors drastically!

[mulias]

@pirix-gh ohhh, misunderstanding on my part, I saw this a while ago and thought it was still an issue. I see now that it's more dated than I realized :)

Basically I thought that the recursive limit was still an issue for curry on 3.4, so I thought that the method I've been using to simplify trampolining might be helpful. If ramda isn't having issues with the current recursive types then that's great :+1:

[tycho01]

I'm going to bring negative & positive number manipulation to TS soon

I wish there were a way to do this without putting in every number you wanna be able to use! 😅

[millsp]

I wish there were a way to do this without putting in every number you wanna be able to us

I finally got to a neater solution, not based on my iterators idea... but still, the numbers have to be hard coded. But I think that it's good to have some kind of limit because otherwise it would make TS some kind of runtime, and I'm not sure that it's intended to work this way. It's a compromise. However, what I could do is to allow one to pass extra maps to extend the amount of numbers (currently -50 to 50).

[RyanCavanaugh]

• any techniques that have hit DT will automatically be used as part of TS regression testing

Just FYI, deliberately going around our depth limiter is likely to result in us telling you not to do that if it results in bugs 😉