Stream: contributing

Topic: gen_dev HigherOrder

Ahmad Sattar (Feb 01 2023 at 18:52):

Hey, I've been trying to grok how I should go about implementing List.map and friends in the gen_dev backend. As far as I can tell it should be handled throughCallType::HigherOrder, but it seems that the calls are consumed by the CallType::ByName call type in the expression building step build_expr. I'm not quite sure how I should proceed. I've looked in the WASM and LLVM backends but I am not quote confident enough when I look at the code paths there . Any pointers would be appreciated :)

Folkert de Vries (Feb 01 2023 at 19:01):

I can help more in a bit but generally I think the wasm backend will be more helpful here I think

Ahmad Sattar (Feb 01 2023 at 19:05):

Thank you! I'll have another look at the wasm backend in the meanwhile

Brian Carroll (Feb 01 2023 at 20:08):

I wrote most of the Wasm backend, including this part, and I'm happy to help. Busy now but free this time tomorrow.

Ahmad Sattar (Feb 01 2023 at 20:11):

Awesome, thanks! Will ping if I'm still stuck tomorrow this time :)

Ahmad Sattar (Feb 01 2023 at 21:21):

I think I found a solution by always building the function call regardless of the function symbol being defined_in_app_module. It now correctly crashes at the HigherOrder call type which I was aiming for

Folkert de Vries (Feb 01 2023 at 21:22):

nice!

Folkert de Vries (Feb 01 2023 at 21:22):

yeah a tricky thing here is that the HigherOrder functions need an extra function to be defined. A pointer to this function is given to zig, so it can call it

Ahmad Sattar (Feb 01 2023 at 21:23):

Yes, okay. Will give it a shot :)

Folkert de Vries (Feb 01 2023 at 21:23):

because zig does not (cannot, really) know about the specific roc types, this happens with void pointers

Folkert de Vries (Feb 01 2023 at 21:28):

so say we have something like

inc : I64 -> I64
inc = \x -> x + 1

List.map [1i64] inc

Then we need something like (in rust types)

fn inc(_: i64) -> i64 { 
    // generated as normal
}

fn caller(captured: *const c_void, arg1: *const c_void, result: *const c_void) { 
    let x = unsafe { std::ptr::read(arg1.cast::<i64>()) };
    // if there were a capture, we'd read that here too

    let answer = inc(x);

    std::ptr::write(result.cast::<i64>(), answer);
}

Then we call the zig list_map function with the caller

Ahmad Sattar (Feb 01 2023 at 21:33):

Oh, very interesting. This is insightful to know

Ahmad Sattar (Feb 01 2023 at 21:35):

So the zig list_map function relies on result to function sort of like an out-parameter in this case?

Folkert de Vries (Feb 01 2023 at 21:36):

yes, result will be a pointer to the correct element in the output list

Brian Carroll (Feb 02 2023 at 08:22):

Some places in the Wasm backend you might want to look at:

When the Wasm backend encounters a higher-order call to one of the builtins, it just "registers" the fact that a wrapper function needs to be generated later. This is the caller in Folkert's Rust pseudo-code above. Registering it records a a name, a layout, and an enum saying which kind of wrapper it is (for a mapping function or a sorting function).
https://github.com/roc-lang/roc/blob/main/crates/compiler/gen_wasm/src/low_level.rs#L2307-L2308

Later on, when the backend has finished generating all of the procedures defined in the IR, it starts generating some "helper functions" that are not in the IR. These include higher-order wrappers, as well as == functions for data structures, and refcounting functions.

When we generate the body of the higher-order wrapper, we use the info we "registered" earlier. That happens here:
https://github.com/roc-lang/roc/blob/main/crates/compiler/gen_wasm/src/backend.rs#L491-L609

By the way, when you see stuff about "function index" in Wasm you should think "function address" for machine code.

Brian Carroll (Feb 02 2023 at 08:23):

I don't know whether this architecture will work well or not with the native code backends.

Folkert de Vries (Feb 02 2023 at 08:24):

the dev backend already uses the refcounting and == generation right, so that seems like a logical place to do this caller generation as well

Brian Carroll (Feb 02 2023 at 09:19):

I'm not sure if that'll work. You're referring to the mono code_gen_help module that generates IR for == and refcount. Those functions are relatively high level from the backends point of view. They have loops and conditions and stuff. So it makes sense.
But the caller is a much more low level thing. I'm not sure if we can express it as IR in a way that makes sense for all dev backends. But maybe we can.

Brian Carroll (Feb 02 2023 at 11:31):

Hmm you could probably express it as calls to unbox. But those are pretty easy to just generate directly. So going through IR might not be worth it.

Ahmad Sattar (Feb 02 2023 at 14:48):

That explains why I saw ProcSource being defined only in the WASM module. That's quite an interesting way to handle this

Brian Carroll (Feb 02 2023 at 17:58):

Yeah I wanted to avoid having the code generator recurse into itself. I think that would make it much harder to think about and to debug, when it's already quite hard!

Ahmad Sattar (Feb 03 2023 at 19:29):

I've looked a little more on the wrapping logic, and I think I'm not familiar enough with the codebase yet to take on implementing higherorder just yet, unfortunately!

Folkert de Vries (Feb 03 2023 at 19:40):

you'll get there! they are not too important I think we can actually write List.map in standard roc (List.mapWithIndex is pure roc, no fancy lowlevels required) so we could always make examples work that way

Ahmad Sattar (Feb 03 2023 at 20:15):

Very neat, i just looked it up! I think the little exploration wasn't totally for nothing, though. I'll see if I can open a PR soon fixing some subtle literal loading issues I was running into

Brian Carroll (Feb 04 2023 at 09:31):

If we implemented all of the List.mapN functions like this, we could delete a lot of complex backend code! The only higher-order lowlevel would be sortWith.

Folkert de Vries (Feb 04 2023 at 13:28):

yeah, I'll go over the benchmarks again. A problem here is how to limit the number of RC operations. By default, List.get will increment, and then at the end of the mapping the whole list is decremented

Folkert de Vries (Feb 04 2023 at 13:28):

and for performance we'd need to short-circuit that somehow

Folkert de Vries (Feb 04 2023 at 14:10):

hmm, criterion consistently hits some sort of memory error on my machine

Folkert de Vries (Feb 04 2023 at 14:11):

even for trivial programs

Ahmad Sattar (Feb 04 2023 at 17:10):

Does this happen when you benchmark List.mapN implemented in roc?

Folkert de Vries (Feb 04 2023 at 19:27):

yeah there is a benchmark setup in the test_gen crate, but running it gives weird segfaults for me

Folkert de Vries (Feb 04 2023 at 19:28):

I wrote that setup originally too, but I don't think we really changed anything about compilation since I first wrote it

Last updated: Jul 26 2025 at 12:14 UTC