Stream: compiler development

Topic: non-nullable unwrapped closures

Ayaz Hafiz (Mar 27 2023 at 23:02):

So apparently closures can be recursive and their own base case, as long as "something else" evaluates whether it's satisfied the base case or not. This is from Nick's example in #beginners > recursive closures

interface A exposes [recurTest] imports []

const = \val ->
    const1 = \{} -> Ok val
    const1

map = \parser, f ->
    iMap = \input ->
        when parser input is
            Ok a -> Ok (f a)
            Err  -> Err
    iMap

orElse = \parser1, parser2 ->
    iOrElse = \input ->
        when parser1 input is
            Ok a -> Ok a
            Err  -> parser2 input
    iOrElse

two = const 2u8

recurTest = two |> map List.single |> orElse recurTest

main =
    when recurTest {} is
        Ok n -> n == [1u8, 2u8]
        Err -> Bool.false

expect main

Ayaz Hafiz (Mar 27 2023 at 23:03):

We can generate the layout okay, that's all good. The problem is how we generate the reference to recurTest in the orElse call

procedure : `A.recurTest` [<rnnu>C *self {U8, {}}]
procedure = `A.recurTest` ():
    let `A.49` : U8 = CallByName `A.two`;
    let `A.50` : {} = Struct {};
    let `A.39` : {U8, {}} = CallByName `A.map` `A.49` `A.50`;
    let `A.40` : [<rnnu>C *self {U8, {}}] = CallByName `A.recurTest`;
    let `A.38` : [<rnnu>C *self {U8, {}}] = CallByName `A.orElse` `A.39` `A.40`;
    ret `A.38`;

we unconditionally generate the lambda set for recurTest before we call orElse, since the language is eager. But of course this causes a stackoverflow

Ayaz Hafiz (Mar 27 2023 at 23:04):

On the one hand this is programmer error because, what else could we do? The language is eager

Ayaz Hafiz (Mar 27 2023 at 23:07):

on the other hand, the only reason this happens is because recurTest is defunctionalized, and so isn't entirely hidden behind the \{} -> - and the only way to understand that is to understand the compilation model of lambda sets

Ayaz Hafiz (Mar 27 2023 at 23:10):

It's not clear to me how we (1) detect this a-priori or (2) how to compile it differently so that the construction of the recursive part of the lambda set is actually hidden behind an explicit forcing of the recurTest thunk. Like ideally it would be

procedure : `A.getRecurTest` {}
procedure = `A.getRecurTest ` ():
  ret {}

procedure : `A.recurTest` [<rnnu>C *self {U8, {}}]
procedure = `A.recurTest` ():
    let `A.49` : U8 = CallByName `A.two`;
    let `A.50` : {} = Struct {};
    let `A.39` : {U8, {}} = CallByName `A.map` `A.49` `A.50`;
    let `A.40` : {} = CallByName `A.getRecurTest `;
    let `A.38` : [<rnnu>C *self {U8, {}}] = CallByName `A.orElse` `A.39` `A.40`;
    ret `A.38`;

but I'm not sure how we get here

Richard Feldman (Mar 28 2023 at 03:12):

what if we said you can only recurse with an explicit lambda?

Richard Feldman (Mar 28 2023 at 03:13):

e.g. you can write x = \anything -> # goes on to reference x but not x = # not a lambda, goes on to reference x

Richard Feldman (Mar 28 2023 at 03:13):

we can detect that problem during canonicalization

Richard Feldman (Mar 28 2023 at 03:14):

so turn it into an error before lambda sets get involved in the first place

Ayaz Hafiz (Mar 28 2023 at 03:26):

That doesn’t resolve the problem. If you wrap “recurseTest” in a thunk (“recurseTest = \{} -> …”) the issue persists

Ayaz Hafiz (Mar 28 2023 at 03:27):

the reason being, the lambda set is the same under the thunk

Ayaz Hafiz (Apr 12 2023 at 21:20):

Found another instance of this: https://github.com/roc-lang/roc/issues/4725. The problem is the same.

Ayaz Hafiz (Apr 12 2023 at 21:21):

Note that the issue is a type checker bug, but after the type checker bug is resolved, the program runs into the above problem.

Ayaz Hafiz (Jul 20 2023 at 02:19):

Can somebody please move this thread to #compiler development (public) ?

Richard Feldman (Jul 20 2023 at 10:31):

sure, done!

Ayaz Hafiz (Jul 20 2023 at 13:41):

Thanks

Ayaz Hafiz (Jul 20 2023 at 13:42):

We need to figure out how to solve this. I know Brendan ran into it trying effect interpreters in pure roc and #beginners > Compiler stack overflow on recursive parser has the same thing

Ayaz Hafiz (Jul 20 2023 at 13:42):

I don't really know what to do. We need to force evaluation of these kinds of lambda sets as thunks rather than constructing them eagerly. But how we get there is totally unclear to me.

Richard Feldman (Jul 20 2023 at 13:47):

so regarding how to detect this scenario: can it be detected using dependencies between identifiers, e.g. using the dependency graph we build in canonicalization?

Richard Feldman (Jul 20 2023 at 13:50):

and follow up idea: if we can detect it prior to mono, we can insert a canonical IR wrapper node that explicitly forces the thunk

Ayaz Hafiz (Jul 20 2023 at 13:54):

I don't think so. It's only applicable to these lambda sets that are self-recursive and have only one constructor. I don't see how we can detect that before inference

Ayaz Hafiz (Jul 20 2023 at 13:55):

now, maybe we could inject a wrapper after inference, or during mono. but how exactly do we do that? it's not clear to me. we need to propogate all the information somehow, and that piece is unclear to me

Richard Feldman (Jul 20 2023 at 13:58):

we could always add the wrapper during canonicalization, but put a Variable on it to detect whether forcing is needed later during mono

Richard Feldman (Jul 20 2023 at 13:58):

so if it turns out it wasn't needed, we just make it be a no op in mono

Ayaz Hafiz (Jul 20 2023 at 13:59):

Maybe I'm not following but then I think we have the inverse problem of having to propogate information that the wrapper should be removed

Richard Feldman (Jul 20 2023 at 14:02):

I may have misunderstood the comment about earlier about getting the layout being not a problem

Richard Feldman (Jul 20 2023 at 14:11):

so I'm assuming that if we have a variant like Expr::MaybeForceBecauseRecursive(Variable, Expr) and that Variable is Equal (from a constraint perspective) to the Variable for the top level value that we might need to force, then later on after that variable has been solved, we know whether it's applicable or not

Richard Feldman (Jul 20 2023 at 14:13):

so the Expr::MaybeForce gets added during canonicalization because it looks like we might have this scenario, then solving tells us the rest of the info about whether we're actually in this scenario, and then when mono encounters this expr it has all the info needed to determine whether to generate a force

Ayaz Hafiz (Jul 20 2023 at 14:15):

How do you decide whether that Expr should be created?

Richard Feldman (Jul 20 2023 at 14:17):

if it looks like a recursive call - so the easy case would be if it's a call to a symbol that we're in the process of being declared, but if I remember right, I think we already have some dependency graph stuff in there to detect less direct recursion than that

Ayaz Hafiz (Jul 20 2023 at 14:21):

there is no syntactically recursive function in the program https://roc.zulipchat.com/#narrow/stream/395097-compiler-development-.28public.29/topic/non-nullable.20unwrapped.20closures/near/344983279 though

Richard Feldman (Jul 20 2023 at 14:22):

sorry, those links don't work on mobile for some reason (I'm at the pediatrician) - what's that link go to? :sweat_smile:

Ayaz Hafiz (Jul 20 2023 at 14:24):

the first message in the thread

Richard Feldman (Jul 20 2023 at 14:24):

ah I see - maybe syntactic self-reference then?

Richard Feldman (Jul 20 2023 at 14:25):

like it doesn't call itself, but its definition refers to itself

Ayaz Hafiz (Jul 20 2023 at 14:27):

but the self-reference is not a function

Ayaz Hafiz (Jul 20 2023 at 14:27):

iOrElse is where you'd want to perform the transformation

Richard Feldman (Jul 20 2023 at 14:27):

ahh right

Richard Feldman (Jul 20 2023 at 14:30):

I'm not sure if this could help, but it came to mind: we've talked before about doing compile time evaluation of top level expressions

Richard Feldman (Jul 20 2023 at 14:31):

could that help here?

Richard Feldman (Jul 20 2023 at 14:43):

actually - working backwards, I think what we want is a different specialization of iOrElse, right? Like we want it to force (or not) depending on what it's passed?

Richard Feldman (Jul 20 2023 at 14:43):

which would generally mean we want multiple different specializations of it, I'd assume

Ayaz Hafiz (Jul 20 2023 at 14:44):

yes

Richard Feldman (Jul 20 2023 at 14:47):

ok, so if that's the case, then it seems like the propagation mechanicsm would be type unification, yeah?

Richard Feldman (Jul 20 2023 at 14:48):

or at least that seems like the most natural fit

Richard Feldman (Jul 20 2023 at 14:54):

like for example maybe we do the syntax detection, insert the Expr node around recurTest, and then during constraint gen (and/or mono?), when we see that Expr node, we can take steps to propagate some extra type information from that recurTest argument into orElse at the call site, and then from there into iOrElse

Richard Feldman (Jul 20 2023 at 14:54):

but a different call site could specialize differently, so I guess it would have to be a mono thing and not a constraint gen thing?

Ayaz Hafiz (Jul 20 2023 at 15:09):

Yeah, the mechanics here are what I don't think is straightforward. Like, how do we go from a syntactic detection on recurTest to seeing that iOrElse needs to be fixed? And how do you actually update the variables based on each specialization site?

Ayaz Hafiz (Jul 20 2023 at 15:10):

It might be doable in principle but in practice it seems very difficult

Ayaz Hafiz (Jul 20 2023 at 15:11):

i feel like we should try to find the simplest possible implementation, and all the ideas so far feel very complicated. on the other hand, i have no good ideas for a simple implementation

Ayaz Hafiz (Oct 21 2023 at 16:55):

We need to figure out a solution to this if we want to make any headway on the "lazy function" style bugs that are popping up more frequently from users. I still don't have any good ideas. @Folkert de Vries do you have any thoughts?

Ayaz Hafiz (Oct 21 2023 at 17:46):

maybe you can check it at generalization time

Richard Feldman (Oct 21 2023 at 18:39):

:thinking: what would that look like?

Ayaz Hafiz (Oct 21 2023 at 18:42):

i don’t know

Richard Feldman (Oct 21 2023 at 18:48):

should we schedule a video chat next week to brainstorm ideas?

Ayaz Hafiz (Oct 21 2023 at 20:51):

Sure. I’m free most times after Wednesday after 2023-10-25T11:00:00-04:00

Richard Feldman (Oct 21 2023 at 22:04):

I'm also available at that time, for up to 2.5 hours. After that I'm busy for the rest of the day.

Ayaz Hafiz (Oct 21 2023 at 22:25):

@Folkert de Vries ? and anyone else interested

Brendan Hansknecht (Oct 21 2023 at 22:29):

Vaguely interested, but I'll be traveling.

Folkert de Vries (Oct 22 2023 at 01:04):

Should be able to make that.

Agus Zubiaga (Oct 22 2023 at 06:52):

It’s prob gonna be way over my head, but I’d like to join if that’s ok, and maybe learn by osmosis :grinning:

Ayaz Hafiz (Oct 22 2023 at 12:41):

sure! ok let’s do the time i posted

Ayaz Hafiz (Oct 22 2023 at 12:41):

Ill send a meeting link at that time

Richard Feldman (Oct 22 2023 at 14:31):

Ayaz Hafiz said:

i feel like we should try to find the simplest possible implementation, and all the ideas so far feel very complicated. on the other hand, i have no good ideas for a simple implementation

thinking ahead of what to talk about: one possible thing we could talk about is "if we assume there's no simple solution, what's a complicated solution that we can implement incrementally?" - e.g. "ok now it fixes this one situation, but not all known situations"

that could (for example) get us to a point where we could fix some of the specific bugs people have been running into, potentially including recursive parsers

Folkert de Vries (Oct 25 2023 at 15:03):

@agus (and others, maybe) https://meet.jit.si/roc-types-bugfix-discussion

Ayaz Hafiz (Oct 25 2023 at 15:03):

Running a few minutes late

Richard Feldman (Oct 25 2023 at 15:03):

@Agus Zubiaga fyi!

Last updated: Jul 06 2025 at 12:14 UTC