Stream: beginners

Topic: Help implementing recursive type?

Ian McLerran (Feb 04 2025 at 16:15):

Hey ya'll, I'm trying to implement a recursive type, and seem to have hit a brick wall. The error message for recursive types says:

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

I believe my recursive type meets these requirements - The recursion is within a tag union, and there is a variant in the union which is terminating. Is the problem because the tag union in my recursive type is wrapped in a record (or List), but must actually be a pure tag union?

Ian McLerran (Feb 04 2025 at 16:16):

I believe this should be adequate to show my type structure:

Expression : {
    subexpression: Subexpression,
    expression: [
        Expression Expression, # recursive
        NoExpression,
    ]
}
Subexpression : List [
    Match Match,
    Group Group, # recursive
    AnchorWordBoundary,
    AnchorNonWordBoundary,
]
Group: {
    modifier: [Capturing, NonCapturing]
    expression: Expression, # recursive
    quantifier: Quantifier,
}

Ian McLerran (Feb 04 2025 at 16:19):

For context, I am trying to express the syntax tree for the following grammar:

Expression ::= Subexpression ("|" Expression)?

Subexpression ::= SubexpressionItem+
SubexpressionItem
    ::= Match
      | Group
      | Anchor

Group ::= "(" GroupNonCapturingModifier? Expression ")" Quantifier?

Ian McLerran (Feb 04 2025 at 16:27):

Any suggestions on how I could massage this grammar into workable Roc types?

Brendan Hansknecht (Feb 04 2025 at 16:35):

In the current roc compiler, recursive types must be tags and they must be defined in one definition.

Brendan Hansknecht (Feb 04 2025 at 16:36):

I don't think we ever fixed the one definition restriction

Ian McLerran (Feb 04 2025 at 16:36):

Ah... so probably the fact that its not one definition is what is catching me up here...

Brendan Hansknecht (Feb 04 2025 at 16:36):

Yeah

Brendan Hansknecht (Feb 04 2025 at 16:37):

And I think you can use as to name subexpression in the single definition if necessary

Ian McLerran (Feb 04 2025 at 16:44):

Hmm.. so these are part of a greater type called Regex. I tried to inline everything inside Regex, and use as, but as seems to throw an error.

Ian McLerran (Feb 04 2025 at 16:51):

Seems like as doesn't work in this context.

Ian McLerran (Feb 04 2025 at 16:52):

I think I'm going to have to go back to the drawing board on how to implement this AST. :thinking::sweat_smile:

Brendan Hansknecht (Feb 04 2025 at 16:57):

I swear we have a way to name inline....thought it was wrapping in parens and using as.....hmmm

Ian McLerran (Feb 04 2025 at 18:32):

Hmmm.. yeah, I can't seem to find a way to get the as keyword to work inline.

Ian McLerran (Feb 04 2025 at 22:26):

Brendan Hansknecht said:

I don't think we ever fixed the one definition restriction

Does this imply it is a goal to permit recursion across multiple definitions? :fingers_crossed::smiley:

Brendan Hansknecht (Feb 04 2025 at 23:08):

I don't know what the new plan is/how it works. I think the new plan is only recursion through nominal types.

Brendan Hansknecht (Feb 04 2025 at 23:08):

But yeah, should be multiple definition

Richard Feldman (Feb 04 2025 at 23:09):

yeah that's the plan!

Richard Feldman (Feb 04 2025 at 23:10):

introduce nominal ("custom") tag unions, allow them to be recursive (including mutually recursive if desired) and disallow recursion in structural tag unions

Richard Feldman (Feb 04 2025 at 23:10):

I forget where we talked about why that change was necessary, but it was important :sweat_smile:

Ian McLerran (Feb 05 2025 at 15:23):

This sounds promising! Will be great to have more flexible recursion support.

Ian McLerran (Feb 05 2025 at 15:27):

Couple of questions - by definition, a nominal tag union would be a closed union, correct? And furthermore, since it is nominal, not structural, then even if NominalA was a subset of NominalB, NominalA could not be given to something which needed NominalB, correct?

Richard Feldman (Feb 05 2025 at 16:15):

they're closed and so can't be unioned together

Richard Feldman (Feb 05 2025 at 16:15):

they're exactly like algebraic data types in other languages (or enums in Rust)

Richard Feldman (Feb 05 2025 at 16:16):

just using the name "custom tag union" since that fits our terminology :big_smile:

Ian McLerran (Feb 05 2025 at 16:52):

Okay, that's what I figured.

Ian McLerran (Feb 05 2025 at 16:53):

This now tops the list of features I'm looking forward to in Roc!

Last updated: Jul 05 2025 at 12:14 UTC