Stream: bugs

Topic: recursion in a record

Ayaz Hafiz (Dec 31 2024 at 01:44):

Is this a bug?

Scalar : {
    value : F64,
    deps : List Scalar,
}

── CYCLIC ALIAS in grad.roc ────────────────────────────────────────────────────

The Scalar alias is self-recursive in an invalid way:

3│  Scalar : {
    ^^^^^^

Recursion in aliases is only allowed if recursion happens behind a
tagged union, at least one variant of which is not recursive.

Or am I doing something wrong?

Sam Mohr (Dec 31 2024 at 01:46):

That's how it has been for a while, right?

Ayaz Hafiz (Dec 31 2024 at 01:46):

i have no clue haha

Sam Mohr (Dec 31 2024 at 01:47):

Standard solution is

Scalar : [NoDeps F64, WithDeps {
    value : F64,
    deps : List Scalar,
}]

Ayaz Hafiz (Dec 31 2024 at 01:47):

that works, ty

Sam Mohr (Dec 31 2024 at 01:48):

I'm not a pro, but I presume that constraint is because of lambda sets? It might change with the changes going on

Ayaz Hafiz (Dec 31 2024 at 01:49):

i don't think it should have anything to do with lambda sets.. i think probably just an unnecessary restriction

Sam Mohr (Dec 31 2024 at 01:50):

It shouldn't have anything to do with them, yes

Sam Mohr (Dec 31 2024 at 01:50):

I'm working (slowly) on the can rework, I can look into it

Ayaz Hafiz (Dec 31 2024 at 01:50):

ty

Sam Mohr (Dec 31 2024 at 01:51):

Oh actually, I think it's because records aren't refcounted

Sam Mohr (Dec 31 2024 at 01:51):

And we don't currently intelligently know that List is refcounted

Sam Mohr (Dec 31 2024 at 01:52):

So without knowing that certain builtins can terminate recursion, we are worried that recursive records will be infinite in size

Sam Mohr (Dec 31 2024 at 01:52):

So we need some way to determine which data types are heap-allocated and mark recursion termination

Anthony Bullard (Dec 31 2024 at 01:53):

Yeah the recursion has to be behind a pointer or you don’t know the size of the object at compile time

Richard Feldman (Dec 31 2024 at 01:54):

yeah it was just never implemented fully

Richard Feldman (Dec 31 2024 at 01:54):

I think the check is just "does the alias appear again in itself"

Richard Feldman (Dec 31 2024 at 01:54):

there need to be exceptions added to it, such as this one

Sam Mohr (Dec 31 2024 at 01:56):

I think just handling List would work, since Dict and Set are implemented in native Roc using List

Richard Feldman (Dec 31 2024 at 02:01):

yeah, plus if we move Dict and Set to Zig (as has been discussed before) presumably it would be easy to add them to that list of exceptions :big_smile:

Ayaz Hafiz (Dec 31 2024 at 02:13):

yeah seeing it’s under List is sufficient. or any other recursive union

Brendan Hansknecht (Dec 31 2024 at 02:56):

Yeah, super old bug

Brendan Hansknecht (Dec 31 2024 at 02:57):

I tried enabling recursion through list and box a long time ago, but didn't figure it out.

Sam Mohr (Dec 31 2024 at 02:59):

Wait, would Box actually work? Yes, Box is heap-allocated, but it always has a value behind it. So

Scalar : { value : F64, next : Box Scalar }

has a known, finite size, but would take up infinite memory, right?

Sam Mohr (Dec 31 2024 at 02:59):

Unless Box can be null in a way I don't know

Brendan Hansknecht (Dec 31 2024 at 02:59):

Yeah, in roc today, it would be just list, box, and recursive tag. Of course recursive records could automatically box if we wanted.

Brendan Hansknecht (Dec 31 2024 at 02:59):

Oh yeah, box doesn't work I guess

Brendan Hansknecht (Dec 31 2024 at 03:01):

Would need to be an optional box of some sort

Brendan Hansknecht (Dec 31 2024 at 03:01):

This is still different than raw recursive tags though

Brendan Hansknecht (Dec 31 2024 at 03:01):

So would need an exception in current roc

Last updated: Jul 05 2025 at 12:14 UTC