Nulldata (Apr 30 2023 at 13:21): Nulldata (Apr 30 2023 at 13:21):Hello, I've been looking into Tail Recursion Modulo Cons (TRMC).
Here are my thoughts so far:
The approaches I've read about so far implements TRMC using destination patching.
While the mono-IR doesn't have a direct way of representing the mutation that would need to be preformed, maybe reuse could do the job.
Something like, transforming:
map = \f, l ->
when l is
Nil -> Nil
Cons x xs -> Cons (f x) (map f xs)
Into this (pseudocode):
map = \f, l ->
dst0 = Nil
let joinpoint j f l dst =
when l is
# Redundant in this case
Nil -> reuse dst Nil
Cons x xs ->
x' = f x
dst' = Nil
# Effectively write to dst
_ = reuse dst (Cons x' dst')
jump j f xs dst'
in
jump j f l dst0
I'm not sure if this is an elegant solution to not introducing the required mutating constructs into the mono-IR or a gross misuse of reuse:)
Also, I must admit that I haven't fully dug in to how layouts work and how reuse interacts with them (started looking at the code yesterday).
So maybe for some layouts the termninal tags of a union are not valid "patchable" destinations?
In that case perhaps passing the outer union and a patch-index and reuse'ing the slot via an UnionAtIndex access would work?
If this approach is valid, then this transform should probably either be a part of make_tail_recursive or run just before it.
Since it would use reuse et al, the pass(es) should probably be moved to after insert_reset_reuse_operations instead of at the start of get_specializd_procs_without_rc.
Would moving the tail-recursion pass to after the ref-counting passes affect anything else?
Folkert de Vries (Apr 30 2023 at 13:43):this reminds me, we chatted with Anton Lorenzen a while ago and he mentioned that Daan Leijen had some trick for how TRMC is actually implemented in Koka
Folkert de Vries (Apr 30 2023 at 13:44):I've had thoughts similar to ^. I think what you run into though is that Nil is represented as a null pointer. hence re-using it won't work.
Folkert de Vries (Apr 30 2023 at 13:45):and generally a problem is that the papers assume you have one element of "scratch space" available at the start of the recursion, which is suboptimal. I would like it to actually be in-place
Folkert de Vries (Apr 30 2023 at 13:45):but that means unrolling the recursive function, which would be tricky
Folkert de Vries (Apr 30 2023 at 13:47):also, in general, cool that you're looking into this! we'd benefit from actually implementing TRMC a lot!
Ayaz Hafiz (Apr 30 2023 at 13:50): dst' = Nil
# Effectively write to dst
_ = reuse dst (Cons x' Nil)
jump j f xs dst'
To clarify, I think you'd really want something like
dst' = Nil
# Effectively write to dst
- _ = reuse dst (Cons x' Nil)
+ _ = reuse dst (Cons x' dst')
jump j f xs dst' # index into the new `Nil` cell above
here, right?
Nulldata (Apr 30 2023 at 13:51):Yes! Fixed the original post
Ayaz Hafiz (Apr 30 2023 at 13:51):Folkert, does reuse have to be 1-to-1 with reset?
Ayaz Hafiz (Apr 30 2023 at 13:52):this reminds me, we chatted with Anton Lorenzen a while ago and he mentioned that Daan Leijen had some trick for how TRMC is actually implemented in Koka
aside: yeah, they said they would send us a note on how they do it sometime later this spring or summer
Folkert de Vries (Apr 30 2023 at 13:53):no they'll publish a paper on FBIP. I think I should follow up about that TRMC thing
Nulldata (Apr 30 2023 at 13:53):this reminds me, we chatted with Anton Lorenzen a while ago and he mentioned that Daan Leijen had some trick for how TRMC is actually implemented in Koka
Ooh, nice, I'll have a look at that (maybe we should steal some of their benchmarks too)
I've had thoughts similar to ^. I think what you run into though is that Nil is represented as a null pointer. hence re-using it won't work.
Yeah I feared that, but would the "passing outer value + patch index" index then work?
and generally a problem is that the papers assume you have one element of "scratch space" available at the start of the recursion, which is suboptimal. I would like it to actually be in-place
but that means unrolling the recursive function, which would be tricky
Maybe instead of unrolling, we could replace the inductive case(s) with a call to a generated helper which then basically has the body of my proposed transform, modulo that it would take the outer structure and a patch index instead, so that it's guarranteed to do an in-place update?
Folkert de Vries (Apr 30 2023 at 13:53):eh, let's see. strictly speaking reuse is not tied to reset
Folkert de Vries (Apr 30 2023 at 13:58):something like this?
map = \f, l ->
when l is
Nil -> Nil
Cons x xx -> helper f x xx l
helper = \f, x, xx, dst ->
when xx is
Nil -> Cons@dst (f x) xx
Cons y yy ->
_ = Cons@dst (f x) xx
helper f y yy xx
the challenge is of course to recognize the inductive cases
Folkert de Vries (Apr 30 2023 at 13:59):e.g. we also want this to work for (binary) trees
Nulldata (Apr 30 2023 at 14:27):something like this? ...
Yes something like that. Though wouldn't yours replace the input list l in-place?
Folkert de Vries (Apr 30 2023 at 14:28):yes. that only works if the input and output types are roughly similar
Folkert de Vries (Apr 30 2023 at 14:28):for us anyway
Folkert de Vries (Apr 30 2023 at 14:29):ah I understand better now what you originally intended. If we cannot re-use the input list, then using Nil as the dst is exactly what you want
Folkert de Vries (Apr 30 2023 at 14:29):because the reuse will allocate the required space
Folkert de Vries (Apr 30 2023 at 14:30):but, if the update can happen in-place, we'd like that too of course
Nulldata (Apr 30 2023 at 14:32):Yeah, I mean we're not necessarily trying to avoid fresh allocs all together. After all the input list might still live after the call, so constructing a whole new output list is fine in those cases. We mainly want to use the reuse in order to enable tail-recursion
Folkert de Vries (Apr 30 2023 at 14:33):yes, limiting scope a bit here is probably a good idea
Richard Feldman (Apr 30 2023 at 14:37):also, hi and welcome @Nulldata! :wave:
Nulldata (Apr 30 2023 at 14:40):As for detection, a naïve approach would maybe be:
Look for tail position constructor calls, check if one of the arguments is a recursive call, and then mark that slot as the "hole"
Since, we're working with a pure functional language, I guess the argument position/order of the recursive call doesn't actually matter?
This doesn't handle mutually recursive functions nor more advanced cases, but might be a good starting point
Folkert de Vries (Apr 30 2023 at 14:40):sure, you're right that order of arguments does not matter
Nulldata (Apr 30 2023 at 14:51):Great
Ayaz Hafiz (Apr 30 2023 at 15:02):this is the detection heuristic koka uses (1, 2)
Nulldata (May 06 2023 at 10:41):So I haven't been able to work much on this so far. I mainly have the weekends for this and this weekend is kinda busy for me.
But I have started the first step, which is moving the tail_recursion transform past the RC/Reuse transforms to avoid introducing Reuse instructions before them.
I've made a draft PR for tracking: https://github.com/roc-lang/roc/pull/5382
Most of the mono changes caused by the moving of the tail_recursion transform seem to be just renamings, except this one: https://github.com/roc-lang/roc/pull/5382/files#diff-41b4132f97c437f17a0b8a438ad86d2c5311451161e13f58357e6bdb3781f065
Which looks kinda odd. I'll look more into it later.
Last updated: Jul 05 2025 at 12:14 UTC