[kast-ast] [feature] Quantifiers in AST parser

[bhavyakukkar]

Adding the concept of quantifiers to the AST parser will enable more of the expected syntax to be ready after the parsing stage instead of requiring another round of validation.

For example, the syntax for macro_struct_def can be redefined as:

-  syntax @"builtin macro struct_def" <- 500 = "struct" "{" body "}";
+  syntax @"builtin macro struct_def" <- 500 = "struct" "{" field[ key ":" value ]* "}";

which would parse source code as:

Ast::Complex {
  values: Tuple {
    named: BTreeMap{{
      "field": Quantifier::ZeroOrMore (
        Vec{[ Ast::Complex { ... }, Ast::Complex { ... }, ... ]}
      )
    })
  }
}

after the signature for Ast::Complex has been changed from values: Tuple<Self> to values: Tuple<Quantifier<Self>>

---

These quantifiers can also use the advantage of Tuple to be unnamed fields if no keyword is provided before the [ like field[ in the struct_def example.

Syntax for macro_list can then be reduced like this:

-  syntax @"builtin macro list" <- 100000 = "list" "[" values "]";
-  syntax @"builtin macro list" <- 100000 = "list" "[" "]";
+  syntax @"builtin macro list" <- 100000 = "list" "[" [ value ]* "]";

where the first unnamed field in the parsed tuple is Quantifier::ZeroOrMore(...)

---

I would like to try working on this, and start a discussion on whether there are any considerations before starting, including any feedback on these regex-style quantifiers, i.e:

• group[ key ]? parses 0 or 1 child expressions (Quantifier::ZeroOrOne( Option<Tuple> ))
• group[ key ]+ parses 1 or more child expressions (Quantifier::OneOrMore( Tuple, Vec<Tuple> ))
• group[ key ]* parses 0 or more child expressions (Quantifier::ZeroOrMore( Vec<Tuple> ))

This will also bring more iteration as opposed to recursion to the parsing stage which is nice.

[kuviman]

lets think about how it would work with user macros. right now tuple of asts is passed to them as argument.

I think there's not much reason to have Quantifier enum like you proposed, making macro handle the variants at runtime (of the macro, which is comptime 😄 ). It should instead be statically known through type system, with macro argument type matching the syntax definition.

So, when first ";" second is parsed it passes (.first :: ast, .second :: ast) to the macro.

If it was first rest[";" expr]+ instead it should pass (.first :: ast, .rest :: list[.expr :: ast]) instead. Also since the inner part of repetition contains just one binding maybe it should be just first [";" rest]+, and passed as (.first :: ast, .rest :: list[ast]). Naming groups is still nice for more complex expressions like field names tho. But maybe for simpler initial implementation only named groups should be allowed like you proposed.

Now, to support optionals I was planning for optional fields in tuples like (.a :: ast, .b? :: ast), but they are not implemented yet.

In order to construct the type we would need to convert the SyntaxDefinition, and the change here would be a new variant SyntaxDefinitionPart::Group with all the relevant information. This is where information about optionals and amount of repetition would be stored.

Now, at runtime, everything is just Value. More specifically, for macros, arguments are Tuple<Value> where each value is ast, which are constructed from Tuple<Ast> that kast-ast outputs. If we need to support lists, we just need to support lists in the output of kast-ast. Technically, we can mimic lists with tuples so maybe Ast::Complex would be exactly it, with definition being the group part of the original definition?. Which would mean no api change at all. So, for your example, it would be parsed into

Ast::Complex (with named tuple) {
  field: Ast::Complex (with unnamed tuple) {
    [0]: Ast::Complex (with named tuple) {
       key: <Ast of field 0 key>,
       value: <Ast of field 1 value>,
    },
    [1]: ...
  },
}

These are my initial thoughts, what do you think?

[bhavyakukkar]

If it was first rest[";" expr]+ instead it should pass (.first :: ast, .rest :: list[.expr :: ast]) instead. Also since the inner part of repetition contains just one binding maybe it should be just first [";" rest]+, and passed as (.first :: ast, .rest :: list[ast]). Naming groups is still nice for more complex expressions like field names tho. But maybe for simpler initial implementation only named groups should be allowed like you proposed.

Do you mean complexity from the implementation standpoint or for the macro author? Since unnamed group could just be add_unnamed into the tuple the same way as UnnamedBindings. But I see how it could be difficult to make macros for convoluted types with unnamed groups.

I'm at the stage where the the quantifier symbol (?, + or *) is inserted into the group that was specified just before it, and if we allow unnamed groups then a quantifier symbol could be used after any kind of SyntaxDefinitionPart, not just a group | value |, by popping it and converting it into an unnamed group with a singleton field and that respective quantifier.

[kuviman]

I meant implementation complexity.

Since unnamed group could just be add_unnamed into the tuple the same way as UnnamedBindings

In my example, first [";" rest]+ translates to (.first :: ast, .rest :: list[ast]). So, there is no unnamed field. With unnamed group becoming unnamed field it would be more like (.first :: ast, _unnamed :: list[(.rest :: ast)]). So what I proposed is a little bit more complex but makes it easier for macro author. But maybe this logic can be done when converting output of kast-ast to Value before passing it to the macro. Then you can just implement it as you say, I suppose. But here's another example: in syntax "fn" name "(" args ")" ["->" returns]? "{" body "}" the optional group specifying return type is unnamed, just returns being optional field in the result is much cleaner than unnamed optional field containing single named field. Also there could be multiple unnamed optional groups.

On one hand I like quantifiers applicable to not only groups, but what if user meant the * keyword instead of * quantifier. I think having them only applicable to groups which require parentheses is less error prone for those who write custom syntax. ","? is not much more complex than (",")? I suppose. I would make quantifier mandatory after a group too. But maybe having it as a configurable option would be cool

[bhavyakukkar]

In my example, first [";" rest]+ translates to (.first :: ast, .rest :: list[ast]). So, there is no unnamed field. With unnamed group becoming unnamed field it would be more like (.first :: ast, _unnamed :: list[(.rest :: ast)]). So what I proposed is a little bit more complex but makes it easier for macro author.

Yes I guess that is transposing the output, i.e., [ key ":" value ]* parsing it into Tuple { "key" => Tuple, "value" => Tuple } instead of Tuple { [0] => Tuple { "key" => ..., "field" => ... }, [1] => ... }. I will get started on implementing that soon.

On one hand I like quantifiers applicable to not only groups, but what if user meant the * keyword instead of * quantifier. I think having them only applicable to groups which require parentheses is less error prone for those who write custom syntax. ","? is not much more complex than (",")? I suppose. I would make quantifier mandatory after a group too. But maybe having it as a configurable option would be cool

Sounds good and I agree, for now I'll hide the quantifiers with non-group parts as well as groups with no succeeding quantifiers in the implementation.

Also, you mentioned (",")? but I am currently only using square-brackets, should I add round-brackets as a possible group boundary too?

[kuviman]

I don't think it matters currently, and can be changed later, but i think round parentheses make more sense to me for grouping. Although I also see an issue with distinguishing named[ ... ] vs unnamed groups. Since we want to be whitespace insensitive I think? So maybe we could use round brackets for unnamed ones.

[bhavyakukkar]

Oh that issue didn't occur to me initially. Alright, proceeding with named: group_name [ ... ]? and unnamed: something_else ( ... )?

[bhavyakukkar]

When you transpose the groups to be parsed as lists of each field (key :: list[ast], value :: list[ast]) you have to rely on the promise that the ast parser makes that "since key and value were in the same group they will have the same sizes", however if they are both inside a single list of a group (_unnamed :: list[(key :: ast, value :: ast)]) only the size of the list needs to be considered, to me it feels more "correct".

Let me know your thoughts on whether this even matters since its converted to a strict type tuple at the end of the day