Stream: compiler development

Topic: Lambda set "propagation"


view this post on Zulip Agus Zubiaga (Aug 10 2024 at 18:25):

I'm trying to fix a bug in module params where the lambda sets are empty for functions passed through params.

I know the function types are being unified because I get accurate type errors if they don't match, and I can even see the lambda sets being unioned properly by adding some logging in solve. However, when mono is computing the layout, the set comes up empty from the perspective of the imported module. So I must be missing something between solve and mono.

How do unioned lambda sets "propagate" from the importer module subs to the importee's? I know we copy exposed types from the modules we import, but this is the opposite, right? The module passing the function (and adding it to the lambda set) is the one that imports, and I guess at some point we must union all of them?

view this post on Zulip Ayaz Hafiz (Aug 11 2024 at 05:01):

they don't propagate that way

view this post on Zulip Ayaz Hafiz (Aug 11 2024 at 05:01):

there is no cross-module sharing of types

view this post on Zulip Ayaz Hafiz (Aug 11 2024 at 05:03):

are you instantiating the imported module with the correct types/values from the importee when you try to compile it?

view this post on Zulip Ayaz Hafiz (Aug 11 2024 at 05:03):

if you can share a concrete example of where things are breaking down it might help

view this post on Zulip Agus Zubiaga (Aug 11 2024 at 11:39):

Sure. Here's a silly but simple example:

module { add } -> [addAndDouble]

addAndDouble : I64, I64 -> I64
addAndDouble = \a, b ->
    2 * add a b

and an app that uses it:

app [main] { pf: platform "./platform/main.roc" }

import TestParam { add: \a, b -> a + b  }

main =
    Num.toStr (TestParam.addAndDouble 2 3)

This typechecks and if I change add in the app to something that wouldn't compile, I get type errors:

Something is off with the params provided by this import:

3│  import TestParam { add: \a, b -> "$(a) + $(b)"  }
                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

This is the type I inferred:

    { add : Str, Str -> Str }

However, TestParam expects:

    { add : I64, I64 -> Int Signed64 }

In my branch, mono extends the procs in the module with params with one more argument for the params record, and that seems to work properly for simple values.

However, when I pass a function, the layout for add (in TestParam) has an empty lambda set:

Function(
    [
        InLayout(I64),
        InLayout(I64),
    ],
    LambdaSet {
        set: [],  // <----
        args: [
            InLayout(I64),
            InLayout(I64),
        ],
        ret: InLayout(I64),
        representation: InLayout(VOID),
        full_layout: InLayout(
            31,
        ),
    },
    InLayout(I64),
)

By adding some logging in unify (for #UserApp), I can see that add lambda sets are unioned properly:

[crates/compiler/unify/src/unify.rs:1888:5] ctx = Context {
    first: 80,   // <--- #UserApp's version of add
    first_desc: LambdaSet(LambdaSet { solved: UnionLabels { length: 1, labels_start: 225, values_start: 235, _marker: PhantomData<roc_module::symbol::Symbol> }, recursion_var: None, unspecialized: SubsSlice { start: 0, length: 0 }, ambient_function: 2901 }), r: 1, m: none c: None,
    second: 2882, // <--- TestParam's add typ
    second_desc: LambdaSet(LambdaSet { solved: UnionLabels { length: 0, labels_start: 223, values_start: 232, _marker: PhantomData<roc_module::symbol::Symbol> }, recursion_var: None, unspecialized: SubsSlice { start: 149, length: 0 }, ambient_function: 2877 }), r: 0, m: Mark(5) c: None,
    mode: EQ,
}
[crates/compiler/unify/src/unify.rs:1888:5] new_lambda_set = LambdaSet(
    LambdaSet {
        solved: UnionLabels {
            length: 1,  // <-----
            labels_start: 226,
            values_start: 236,
            _marker: PhantomData<roc_module::symbol::Symbol>,
        },
        recursion_var: None,
        unspecialized: SubsSlice { start: 0, length: 0 },
        ambient_function: 2901,
    },
)

However, this is on #UserApp's side. From my limited understanding, I thought that the problem was that this unioned lambda set never makes it to TestParam's side, but I guess you're saying this is not how it works?

Ayaz Hafiz said:

there is no cross-module sharing of types

view this post on Zulip Agus Zubiaga (Aug 11 2024 at 11:53):

I don't understand what's the mechanism by which the importer lambdas make to the importee's lambda set. If I pass { add } to Test.addAndDouble as an explicit arg (instead of params), I can see that the lambda set in its layout is indeed not empty. How does that work?

view this post on Zulip Agus Zubiaga (Aug 11 2024 at 12:03):

My guess was that there must be somewhere in load where these are copied from the solve output of #UserApp to eventually make it to the mono Env of Test, but I might be thinking about it wrong

view this post on Zulip Ayaz Hafiz (Aug 11 2024 at 22:15):

I don't understand what's the mechanism by which the importer lambdas make to the importee's lambda set. If I pass { add } to Test.addAndDouble as an explicit arg (instead of params), I can see that the lambda set in its layout is indeed not empty. How does that work?

To your first sentence, i think no such mechanism currently exists. As to the second question, that works because when we specialize the app module, we insert a request to specialize TestParam.addAndDouble with the add function (this is in a variable called needed_specializations I believe). The TestParam module is later specialized, and this function is seen as needing specialization

view this post on Zulip Ayaz Hafiz (Aug 11 2024 at 22:17):

The way I would think about it is, in an example like

# B.roc
addAndDouble : (I64 -> I64), I64, I64 -> I64
addAndDouble = \f, a, b ->
    2 * add a b

# App.roc
add = \a, b -> a + b
main = B.addAndDouble add 2 3

addAndDouble is actually generic over the exact function f it takes in. Let's call that function _a, then the type of addAndDouble is really forall _a. (I64 -[_a]-> I64), I64, I64 -> I64

view this post on Zulip Ayaz Hafiz (Aug 11 2024 at 22:19):

when we see B.addAndDouble add 2 3 in App.roc we know okay we actually need a specialization of B.addAndDouble with type (I64 -[App.add]-> I64), I64, I64 -> I64. That requirement gets added to needed_specializations. Whenever B.roc is compiled, we pull out the required specialization of B.addAndDouble and compile it

view this post on Zulip Ayaz Hafiz (Aug 11 2024 at 22:20):

https://github.com/roc-lang/roc/blob/9fc6dccb9f67f265dc0f162a32fb95c1717f4075/crates/compiler/mono/src/ir.rs#L8504-L8521

view this post on Zulip Ayaz Hafiz (Aug 11 2024 at 22:20):

https://github.com/roc-lang/roc/blob/9fc6dccb9f67f265dc0f162a32fb95c1717f4075/crates/compiler/mono/src/ir.rs#L3059-L3062

view this post on Zulip Ayaz Hafiz (Aug 11 2024 at 22:22):

With module params you're taking a step up from the function, and I think it must now be the case that a mechanism is needed to instantiate the module as a whole with the values passed to it

view this post on Zulip Agus Zubiaga (Aug 11 2024 at 22:22):

Oh, I see

view this post on Zulip Agus Zubiaga (Aug 11 2024 at 22:23):

That’s very clarifying

view this post on Zulip Ayaz Hafiz (Aug 11 2024 at 22:23):

It might be easier to lower module params to be an extra parameter on functions or something before doing the rest of the compilation pipeline. That might eliminate the need for any changes in later stages entirely

view this post on Zulip Agus Zubiaga (Aug 11 2024 at 22:24):

Earlier than mono?

view this post on Zulip Agus Zubiaga (Aug 11 2024 at 22:24):

I have thought about doing an earlier pass, but I thought it might bad for perf

view this post on Zulip Agus Zubiaga (Aug 11 2024 at 22:25):

It’ll probably be easier to get right, though

view this post on Zulip Ayaz Hafiz (Aug 11 2024 at 22:25):

yeah it'll be much simpler, you'll be lowering to a form that already exists rather than adding a new case

view this post on Zulip Agus Zubiaga (Aug 11 2024 at 22:32):

Do you think that'd be ok for perf? All modules with params and those that call into module with params would have to go through it

view this post on Zulip Agus Zubiaga (Aug 11 2024 at 22:35):

The current approach is sure riddled with tricky cases I spent a ton of time to get right :sweat_smile:

view this post on Zulip Agus Zubiaga (Aug 11 2024 at 22:35):

I'm definitely tempted to simplify it

view this post on Zulip Ayaz Hafiz (Aug 11 2024 at 22:51):

i would do it the easiest way and worry about perf later tbh. my general learning from a project like Roc is that the biggest perf wins are surprising and even though the only way to have the best perf is to optimize to the limit, the 80-90% wins will surprise you and i don't think this will be one of them

view this post on Zulip Agus Zubiaga (Aug 11 2024 at 23:10):

yeah, that sounds right

view this post on Zulip Agus Zubiaga (Aug 11 2024 at 23:11):

I bet I can skip a lot of decls by gathering an array of indexes that I need to touch in the earlier stages

view this post on Zulip Agus Zubiaga (Aug 11 2024 at 23:13):

I'll give this approach a try tomorrow! If it works, module params would be much less invasive in the compiler, and I'd be more confident about the impl

view this post on Zulip Agus Zubiaga (Aug 11 2024 at 23:14):

I wish I had brough this up earlier, but I guess I learned a bunch of stuff :upside_down:


Last updated: Jul 06 2025 at 12:14 UTC