Hacker News Reader

Comment by zinclozenge | Hacker News Reader

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?

View on HN

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.

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.

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/des...

It's not chaining of comparisons, but rather a multi-valued expression - note the comma.

It does not, so the argument is very much valid.

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.

Which argument is valid?

That using angle brackets for generics would unduly complicate Go parsing.

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)

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.

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.

> 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

`|` is bitwise-or in many C-style languages.

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)

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.

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.

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/des...

Was that what you were referring to?

Yep

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.

Reply on news.ycombinator.com