5 ms·

I'm experimenting with a toy language and I wanted to introduce generic syntax with angle brackets. I recall the golang team saying that it could lead to unboun

I'm experimenting with a toy language and I wanted to introduce generic syntax with angle brackets. I recall the golang team saying that it could lead to unbounded lookahead. Is there a parsing approach that mitigates that?

earthboundkid 6y ago
Yeah, not using angle brackets. ^_^ If you allow a, b = f < t1, t2 > ( c ), it can only be parsed if you know whether f is generic (if it's not, then a and b are bools), which requires whole program parsing because f could be defined above, below, or in another file. Basically, if you want to have a sane grammar, don't use angle brackets for generics or pipes for lambdas. It looks good to humans but really screws up the computers.
- Joker_vD 6y ago
  Or you could use a simple trick and in cases where '<' can either open a generic, or be a compasrison, you require it to have a whitespace before it to be a comparison. So your example is an assignment. To make it a function call, you'd need "a, b = f< t1, generic_type < t2, generic_type < t3 >> > ( c )". Notice that when you're already inside of a generic's arguments, you can't use comparison, so whitespace there is allowed to be before "<". IIRC, Elm uses this approach to disambiguate '.' and unary minus in function applications. The major nuisance is that you need to somehow handle "<<" and ">>" properly: either by a "lexer hack"; or by lexing only single "<" and ">", and recombining them in the parser when appropriate; or by splitting "<<" and ">>" in the parser when appropriate; or by not having "<<" and ">>" in the first place.
- laddng 6y ago
  Doesn't golang not support `a < b < c` and chaining of comparisons? I don't see why they make that argument in their specification if it's not already legal Golang syntax specification: https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md#why-not-use-the-syntax-like-c_and-java https://go.googlesource.com/proposal/+/refs/heads/master/des...
  - dllthomas 6y ago
    It's not chaining of comparisons, but rather a multi-valued expression - note the comma.
  - yencabulator 6y ago
    It does not, so the argument is very much valid. https://play.golang.org/p/NQL1rVp-wVC https://play.golang.org/p/NQL1rVp-wVC -- it's trying to interpret that as (1<2)<3, and the types make no sense for that.
    - dllthomas 6y ago
      Which argument is valid?
      - yencabulator 6y ago
        That using angle brackets for generics would unduly complicate Go parsing.
        dllthomas 6y ago
        Then although I agree, I'm still not sure I follow. > It does not [support chained comparisons], so the argument is very much valid. Was your comment to the effect of "although Go does not support chained comparisons, it is syntactically valid for a comparison operator to be passed the result of a comparison so the issue can still arise"? That's valid, but I would have expected "but" in place of "so". (sorry if it seems I'm picking nits; I'm just trying to understand and explaining my attempts)
- UncleEntity 6y ago
  t1 and t2 should be (user defined?) types so I would imagine LR(1) should be able to disambiguate between a generic function and the less than operator. Not saying the grammar would be context-free though.
  - dllthomas 6y ago
    You could help the grammar by having some lexical distinction between types and other identifiers. Relying on that is going to prevent you from including numbers as things you can be generic over (without some additional syntax for that case). That may or may not be something you care about.
- setr 6y ago
  > pipes for lambdas Whats wrong with pipes? The only conflict I can think of is LOGICAL-OR || but afaik no language lets you shove shit between the pipes and still be an OR
  - kbr 6y ago
    `|` is bitwise-or in many C-style languages.
laddng 6y ago
I'd love to read more about the golang team's comments about generic syntax - the only thing I could find was this: https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md#why-not-use-the-syntax-like-c_and-java https://go.googlesource.com/proposal/+/refs/heads/master/des... Was that what you were referring to?
- zinclozenge 6y ago
  Yep
hardwaregeek 6y ago
I know Rust uses the turbofish (foo::<Type>()) to solve it in expressions. As long as you keep type definitions strictly separated from expressions, it should be fine. But also there's various common syntax patterns that cause unbounded lookahead (arrow functions for instance)
perlgeek 6y ago
Unbounded lookahead is a feature of the problem, not the parsing approach. Just ask yourself: if you wouldn't see what comes after it, could you decide unambiguously what kind of construct is being parsed? There are several possible solutions in language syntax (and it's possible you won't like any of them). One is to use whitespace to disambiguate. a < b is parsed as a comparison, a< b or a<b as an opening angle bracket. Another is to keep track of the type while parsing, and parse a < b as an angle bracket only if a is known to be callable. Yet another would be to require some fancy quotes instead, like f«a, b» for generics, sidestepping the problem completely.
patrec 6y ago
I'd contend that the obvious, dead simple and user-friendly way to deal with this is not treat `a<b>(c)` the same as `a < b > (c)`. Mandate whitespace on both sides of relational operators and forbid it where it would look wrong anyway in generic expressions. Ambiguity resolved at the lexing level.
tomp 6y ago
The waz I solve this in my parsers, is that I have a generic "node" syntax that isn't differentiated between types and expressions. So e.g. x[1] : array[int] would be parsed as cast(item(ident("x"), int("1")), item(ident("array"), ident("int"))) Then the semantic disambiguation (`x[1]` -> expression, `array[int]` -> type) would be done in the next stage.

earthboundkid 6y ago

Yeah, not using angle brackets. ^_^ If you allow a, b = f < t1, t2 > ( c ), it can only be parsed if you know whether f is generic (if it's not, then a and b are bools), which requires whole program parsing because f could be defined above, below, or in another file. Basically, if you want to have a sane grammar, don't use angle brackets for generics or pipes for lambdas. It looks good to humans but really screws up the computers.

Joker_vD 6y ago
Or you could use a simple trick and in cases where '<' can either open a generic, or be a compasrison, you require it to have a whitespace before it to be a comparison. So your example is an assignment. To make it a function call, you'd need "a, b = f< t1, generic_type < t2, generic_type < t3 >> > ( c )". Notice that when you're already inside of a generic's arguments, you can't use comparison, so whitespace there is allowed to be before "<". IIRC, Elm uses this approach to disambiguate '.' and unary minus in function applications. The major nuisance is that you need to somehow handle "<<" and ">>" properly: either by a "lexer hack"; or by lexing only single "<" and ">", and recombining them in the parser when appropriate; or by splitting "<<" and ">>" in the parser when appropriate; or by not having "<<" and ">>" in the first place.
laddng 6y ago
Doesn't golang not support `a < b < c` and chaining of comparisons? I don't see why they make that argument in their specification if it's not already legal Golang syntax specification: https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md#why-not-use-the-syntax-like-c_and-java https://go.googlesource.com/proposal/+/refs/heads/master/des...
- dllthomas 6y ago
  It's not chaining of comparisons, but rather a multi-valued expression - note the comma.
- yencabulator 6y ago
  It does not, so the argument is very much valid. https://play.golang.org/p/NQL1rVp-wVC https://play.golang.org/p/NQL1rVp-wVC -- it's trying to interpret that as (1<2)<3, and the types make no sense for that.
  - dllthomas 6y ago
    Which argument is valid?
    - yencabulator 6y ago
      That using angle brackets for generics would unduly complicate Go parsing.
      - dllthomas 6y ago
        Then although I agree, I'm still not sure I follow. > It does not [support chained comparisons], so the argument is very much valid. Was your comment to the effect of "although Go does not support chained comparisons, it is syntactically valid for a comparison operator to be passed the result of a comparison so the issue can still arise"? That's valid, but I would have expected "but" in place of "so". (sorry if it seems I'm picking nits; I'm just trying to understand and explaining my attempts)
UncleEntity 6y ago
t1 and t2 should be (user defined?) types so I would imagine LR(1) should be able to disambiguate between a generic function and the less than operator. Not saying the grammar would be context-free though.
- dllthomas 6y ago
  You could help the grammar by having some lexical distinction between types and other identifiers. Relying on that is going to prevent you from including numbers as things you can be generic over (without some additional syntax for that case). That may or may not be something you care about.
setr 6y ago
> pipes for lambdas Whats wrong with pipes? The only conflict I can think of is LOGICAL-OR || but afaik no language lets you shove shit between the pipes and still be an OR
- kbr 6y ago
  `|` is bitwise-or in many C-style languages.

laddng 6y ago

I'd love to read more about the golang team's comments about generic syntax - the only thing I could find was this: https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md#why-not-use-the-syntax-like-c_and-java https://go.googlesource.com/proposal/+/refs/heads/master/des... Was that what you were referring to?

zinclozenge 6y ago
Yep

hardwaregeek 6y ago

I know Rust uses the turbofish (foo::<Type>()) to solve it in expressions. As long as you keep type definitions strictly separated from expressions, it should be fine. But also there's various common syntax patterns that cause unbounded lookahead (arrow functions for instance)

perlgeek 6y ago

Unbounded lookahead is a feature of the problem, not the parsing approach. Just ask yourself: if you wouldn't see what comes after it, could you decide unambiguously what kind of construct is being parsed? There are several possible solutions in language syntax (and it's possible you won't like any of them). One is to use whitespace to disambiguate. a < b is parsed as a comparison, a< b or a<b as an opening angle bracket. Another is to keep track of the type while parsing, and parse a < b as an angle bracket only if a is known to be callable. Yet another would be to require some fancy quotes instead, like f«a, b» for generics, sidestepping the problem completely.

patrec 6y ago

I'd contend that the obvious, dead simple and user-friendly way to deal with this is not treat `a<b>(c)` the same as `a < b > (c)`. Mandate whitespace on both sides of relational operators and forbid it where it would look wrong anyway in generic expressions. Ambiguity resolved at the lexing level.

tomp 6y ago

The waz I solve this in my parsers, is that I have a generic "node" syntax that isn't differentiated between types and expressions. So e.g. x[1] : array[int] would be parsed as cast(item(ident("x"), int("1")), item(ident("array"), ident("int"))) Then the semantic disambiguation (`x[1]` -> expression, `array[int]` -> type) would be done in the next stage.