Fletch Canny (Jan 03 2024 at 03:33): Fletch Canny (Jan 03 2024 at 03:33):This may not be possible given the lack of currying in Roc, but would it be possible to do TCO when the return value is a monad? I ported over Elm's random library which use a Generator monad, and it's a nice interface but because it works by nesting function calls it doesn't allow for TCO for recursive functions. Is there a way for this to ever be a compiler feature, especially since monads aren't recognised by the compiler? Just curious.
Brendan Hansknecht (Jan 03 2024 at 04:24):You are talking about using an rng in a function. So they become mutually recursive I guess
Fletch Canny (Jan 03 2024 at 04:52):I mean it could be an rng function, it could be a caching monad, it could be any kind of a -> (b, a) monad. If I'm using a monad to pass parameters around implicitly it's just annoying that a consequence of that is that I can no longer TCO, especially in a language designed to be friendly and fast. I'm not even sure if languages like Haskell sidestep the issue but it feels like something that should be possible.
Fletch Canny (Jan 03 2024 at 04:52):Maybe via inlining the bind method for your monad, I'm not sure.
Ayaz Hafiz (Jan 03 2024 at 05:55):If the call is hidden behind an intermediate lambda, it’s not really a tail call and probably won’t result in a large stack size unless the RNG is called iteratively without a function that can itself be TCOd
Ayaz Hafiz (Jan 03 2024 at 05:55):If the call is behind a constructor (like Ok), Roc implements tail recursion modulo cons, which allows TCO even behind constructors.
Fletch Canny (Jan 03 2024 at 09:48):Sure but if you just substituted a monadic opaque type of the form a -> (v, a) with their structural counterparts, then uncurried all the functions which use said monad, then it is tail call optimized.
Brendan Hansknecht (Jan 03 2024 at 17:00):If we did our own inlining of these one use lambdas, it would mostly fix the issue, correct?
Brendan Hansknecht (Jan 03 2024 at 17:09):Also, @Fletch Canny, can you give a concrete example with some code.
Fletch Canny (Jan 04 2024 at 08:02):Brendan Hansknecht said:
Also, Fletch Canny, can you give a concrete example with some code.
It's funny, I was trying to replicate some code which would demonstrate this-
seed : Seed
seed = Random.mkSeed 0
nothingGenerator1 : {} -> Random.Generator {}
nothingGenerator1 = \{} ->
_ <- Random.nat |> Random.andThen
nothingGenerator1 {}
expect
{} == Random.generate (nothingGenerator1 {}) seed
nothingGenerator2 : {}, Seed -> ({}, Seed)
nothingGenerator2 = \{}, s0 ->
s1 = Random.next s0
nothingGenerator2 {} s1
expect
{} == (nothingGenerator2 {} seed).0
Where the first expectation should yield a stack overflow (due to lack of tco) and the second one should just hang, but I actually encountered a compiler bug I'd never seen before because of that.
An internal compiler expectation was broken.
...
thread '<unnamed>' panicked at 'I thought a non-nullable-unwrapped variant for a lambda set was impossible: how
could such a lambda set be created without a base case?', crates/compiler/mono/src/layout.rs:1713:61
But a version of the code which doesn't yield a compiler bug (The only thing that was causing it was the definition of nothingGenerator1)-
nothingGenerator1 : {} -> Random.Generator {}
nothingGenerator1 = \{} ->
if Bool.true then
_ <- Random.nat |> Random.andThen
nothingGenerator1 {}
else
Random.constant {}
Doesn't even stack overflow.
Any idea why this wouldn't stack overflow?
Brendan Hansknecht (Jan 04 2024 at 18:31):My guess: It's getting optimized away to an infinite loop that does nothing
Brendan Hansknecht (Jan 04 2024 at 18:33):So for these examples, if we do our own inlining of single use lambdas, everything should be tail recursive. I think that will be the general case for these sorts of libraries.
We definitely want to do our own inlining eventually, this kind of code is an easy case of always inline.
Brendan Hansknecht (Jan 04 2024 at 18:36):Also, just curious, how does currying help with this?
Fletch Canny (Jan 06 2024 at 01:20):Brendan Hansknecht said:
Also, just curious, how does currying help with this?
I just figured a curried language would have better optimizations surrounding this type of monadic operation given that the context of the monad is essentially curried. a -> Generator a is a -> Seed -> (a, Seed) which is a curried function.
Last updated: Jul 06 2025 at 12:14 UTC