Parameterized impl syntax

[josh11b]

@jsiek observed in #executable-semantics on Discord (1, 2) that our current proposed array syntax creates an ambiguity in the grammar with the parameterized impl syntax:

Here's an example with square brackets for implicit parameters:

external impl [T:! Printable] Vector(T) as Printable { ... }

and here's an example with square brackets for an array type:

external impl [i32; 5] as Printable { ... }

@zygoloid listed some options for addressing this problem in the #syntax channel:

Summary of options for implicit parameters / arrays ambiguity discussed so far:

1. Just make it work as-is: impl [a; b] parses as an array type, impl [a, b] parses as an implicit parameter. Theoretically this is unambiguous given that a ; is required inside the [...] in the former and disallowed in the latter. Concerns: it's likely to be visually ambiguous.
2. Add mandatory parentheses: impl [T:! Type] (Vector(T) as Container). Concerns: it's hard to avoid requiring them in cases that don't start with a [ if we want an unambiguous grammar. Requiring them always would impose a small ergonomic hit.
3. Add an introducer keyword for implicit parameters: impl where [T:! Type] Vector(T) as Container. Unambiguous. Concerns: still some visual ambiguity due to reuse of [...], concern over whether we'd uniformly use this syntax (fn F where [T:! Type](x: T)) or have non-uniform syntax for implicit parameters.
4. Use a different syntax for array types in general: impl Array(T) as Container or impl Array[N] as Container. Concerns: may want a first-class syntax here, especially if (per @geoffromer 's variadics work, we want some special behavior for a deduced bound), and there's a strong convention to use [...] for this. The latter syntax is messy because of our types-as-expressions approach, but we could imagine providing a impl Type as Indexable where .Result = Type to construct array types. T[] might be a special case of some kind.
5. Use a different syntax for implicit parameters in general: impl<T:! Type> Vector(T) as Container. Concerns: we don't have many delimiter options unless we start using multi-character delimiters; (), [], and {} are all used for types, leaving <> as the only remaining bracket. Use of <> as brackets as a long history but not a good one.
   ...
6. Remove the implicit parameter list from impls and force them to be introduced where they're first used: impl Vector(T:! Type) as Container. Concerns: harms readability in some cases, eg impl Optional(T:! As(U:! Type)) as As(Optional(U)) versus impl [U:! Type, T:! As(U)] Optional(T) as As(Optional(U)).
7. Move the implicit parameter list before the impl keyword, perhaps with an introducer: generic [T:! Type] impl Vector(T) as Container. Concerns: increases verbosity; would be inconsistent if we put everything but me there, and surprising if we put me there. Also not clear what a good keyword is, given that the existence of deduced parameters isn't the same as an entity being generic.

@chandlerc proposed in #generics that we might change our terminology to make the keyword generic applicable even when some of the parameters were template.

[josh11b]

In discussions, we decided that we should also consider how we would name an impl declaration. This:

• would allow delegation between impls
• would allow out-of-line definition
• would allow you to call a method from a specific impl to implement an impl in terms of another without just delegating

For unnamed impl declarations, we decided to go with option 3 using the forall keyword:

impl forall [T:! Type] Vector(T) as Container;

For named impl declarations, we decided to instead start with the named keyword and put an equal sign = after the name and before the Self type:

impl named X = [i32; 5] as Printable;

And when the impl was parameterized, use round parens (...) after the name:

impl named P(T:! Type) = Vector(T) as Printable;

This allows us to name a specific method in the impl with bound values for parameters, so P(i32).Print is a function that prints a Vector(i32).

We decided to stop allowing bindings inside the "Type as Interface" part of the impl declaration, so they will always be after one of these new keywords. So impl Vector(T:! Type) as Printable is now invalid. This means we need to change how we match an impl declaration of a parameterized class out of line:

class Vector(T:! Type) {
  impl as Printable;
  impl forall [U:! Type where T is ImplicitAs(U)] as ImplicitAs(Vector(U));
}

// Previously: impl Vector(T:! Type) as Printable
impl forall [T:! Type] Vector(T) as Printable;
impl forall [T:! Type, U:! Type where T is ImplicitAs(U)] Vector(T) as Printable;

Alternatives considered:

• We talked about a number of variations of option 7, but ultimately we liked the regularity of all impl declarations being first introduced by the same keyword.
• We considered using the facet keyword instead of forall or named. However it was hard to distinguish how a facet was different from an impl. The main possibility we considered was that it represented the archetype used when type checking, but that did not help solve a problem with the impl declaration itself.
• We thought it was not worth introducing ambiguities in the grammar in order to make this feature more concise, such as leaving off the forall or named keyword or the = after named.

[chandlerc]

@zygoloid and I talked through this a bit, and wanted to share where I think we're landing on the syntax question.

We both are really happy with impl forall [T:! Type] Vector(T) as Container;.

We both had sometimes overlapping, sometimes different concerns about other parts of this. None seemed huge, but enough that it seemed a bit difficult to get very comfortable moving forward.

A concrete suggestion from me after the discussion:

• Decide on and allow impl forall [T:! Type] Vector(T) as Container;, use that for all parameterized impls.
• Stop allowing bindings inside the T as C part so there is only a single way to write these. We can easily add this back if desired at some point.
• Don't provide the named approach or out-of-line definitions yet. Instead, code would need to forward declare some function and alias it into the impl. Again, the goal would be to revisit the need for out-of-line method definitions for impls and named impls more generally after we get some experience with the minimal approach.

One big question is -- would delaying the named impl stuff be OK? I feel bad as I brought them back into the discussion (sorry about that), but I feel like they're actually making it harder to move forward because they open a door to a larger space than necessary and than I intended. While I'm actually pretty optimistic about us wanting named impls eventually and am interested in that larger space, it is unsurprisingly less well explored and I think a bit harder to get a clear consensus around.

If that is OK, are folks happy with this as the decision for now, and we'll leave named impls (and expanding the pattern spellings) to the future?

[chandlerc]

I didn't include any of the specific concerns that came up in our discussion, and it is relevant that there were concerns. But to be clear, I don't think any of these are insurmountable. They may even be good things in the long run. The issue was whether we should eagerly spend more time right now figuring out the answers to those questions and resolving the remaining concerns.

One concern comes down to what is P(T) in the named case? It feels like going down this direction causes it to be its own thing in some way, and at least at the moment, it was hard to pin down what the right mental model would be. This uncertainty actually manifested in not being particularly comfortable with any of the syntax options -- some of them only make sense in one interpretation or the other.

Here is a very rough summary of my memory of the discussion... I may have missed some key points though (sorry for that), hopefully we can correct/iterate on any to capture things better.

• The = seems awkward. The thing on the right is an impl that has a very distinct syntax that is introduced by the keyword on the left. Unlike, for example alias <id> = <name> where the <name> is an existing Carbon syntactic construct.
• We played around with a number of syntaxes that didn't really address this one way or another.
• One observation was that the = isn't critical here... While impl named P(T:! Type) Vector(T) as Container has awkward justoposition, that might not be much more (or less) awkward than the =. It is somewhat one holistic entity -- a named impl.
• That led to my observing that named impl P(T:! Type) Vector(T) as Container read more naturally to me.
• Which led to @zygoloid observing that this really made a named impl seem importantly different. It wasn't clear what that different thing was, or whether that was desirable. Understanding that seemed important to understanding the right syntax here.
• I then observed that we somewhat already need to understand that because the entire use case of out-of-line definitions will have us write fn P(T:! Type).Print(...) { ... } and we somewhat need to have a good mental model for what the thing is before the .. I think we have a good rough idea, but it seemed a bit hard to pin it down.
• Trying to pin this down for myself, I kept coming back to "named impl"s being a thing that is what enables the out-of-line definition of functions. But that in turn suggested the named impl P(T:! Type) syntax and raised more questions...
  • For example, is:

    named impl P(T:! Type) Vector(T) as Container { ... }
    

    Essentially a short-hand for first declaring a "named impl" thing called `P(T

    named impl P(T:! Type) Vector(T) as Container { ... }
    impl forall [T:! Type] using P(T);
    

  • This in turn raised a bunch of other questions:
    • Having the ability to declare a named impl that isn't found by normal impl-lookup is something that has been discussed as potentially desirable / useful in the past. So maybe we should allow these to be separate steps? Down side is that it is awfully verbose for what is very likely the common case.
    • This exposes a potentially interesting different expressivity surface -- the deduced pattern doesn't have to be the exact same as the named pattern. You could imagine things like impl forall [T:! Type] using P2(T, T) for example.

This is roughly where I think we stopped. Not because any of this was concerning, it actually seemed fairly exciting to me at least. But it did seem to expose that there is more we should flesh out to understand what the mental model and design for named impls actually is. We could do that, but it wasn't clear this was a priority, and so it seemed like maybe worth just unwinding a bit and addressing the unnamed parameterized impls now, where we seem to be increasingly converging, and come back to named stuff later when we have more time to work through the details.

Maybe this explains more the desire to narrow scope a bit?

[josh11b]

We said we needed the = because of the grammatical ambiguity between "parameterized named impl" and "unparameterized named impl of a tuple type".

[josh11b]

I'm fine splitting named impls out of this issue, since the original question for this issue was only about parameterized impls, as long as we copy the context.

[chandlerc]

Let's call this specific issue decided with the comment above: #1192 (comment)

And as @josh11b mentioned, keep recording any context or thoughts needed here so that when we pick up named impls again we don't have to rebuild that context.