Associated type syntax

[josh11b]

This is an open question in #731 , specifically see https://github.com/josh11b/carbon-lang/blob/details/docs/design/generics/details.md#associated-types

Problem

Given an interface with an associated type:

interface Stack {
  let ElementType:! Type;
  fn Push[addr me: Self*](value: ElementType);
  ...
}

how should an impl specify the value for that associated type?

Option 1: let :! =

class DynamicArray(T:! Type) {
  ...
  impl as Stack {
    let ElementType:! Type = T;
    fn Push[addr me: Self*](value: ElementType);
    ...
  }
}

This matches the syntax of other let declarations in the class.

Option 2: let =

class DynamicArray(T:! Type) {
  ...
  impl as Stack {
    let ElementType = T;
    fn Push[addr me: Self*](value: ElementType);
    ...
  }
}

This is more concise, and doesn't repeat what is already in the interface. This allows the constraints on the associated type expressed in the interface to change without having to change all implementations of that interface.

Option 3: let is optional

See https://github.com/josh11b/carbon-lang/blob/details/docs/design/generics/details.md#inferring-associated-types

class DynamicArray(T:! Type) {
  ...
  impl as Stack {
    fn Push[addr me: Self*](value: T);
    ...
  }
}

In this case, the value of ElementType is deduced from the signature of Push, which uses T in the ElementType position. This is the approach used by Swift.

Advantages:

• Can make more changes to the interface without modifying implementations, including adding entirely new associated types to generalize existing method signatures.
• A lot more concise and convenient

Disadvantages:

• Less explicit
• Requires inference, which could fail in the exotic case of more than one possible value for the associated type
• Possibly slower and more complex compiler implementation

[josh11b]

Open discussion is leaning toward option 1. The specified type in the impl should be equal to the associated type in the interface, or more restrictive. Or the type can be explicitly set to auto.

[chandlerc]

I think @zygoloid and I have consensus on option #1 for now. We can always revisit this, but lets called this decided.

[chandlerc]

@josh11b prompted me to write down at least my memory of the rationale from the discussion we had...

Why not option 3? This one I think was only very briefly discussed and not preferred because:

• It came with complexity of inference.
• It seemed unnecessary.

Why not option 2? This was a more complex discussion.

The big advantage and disadvantage of option 1 compared to option 2 is that it allows you to specify the constraints for a specific implementation. These must at least include those in the interface, but could include further constraints. That results in a tradeoff when evolving constraints on interfaces.

Let's look at the implications of different evolutionary changes to the constraint on the interface's associated type. There are two kinds of changes here: adding or removing a constraint.

Option 2 seems to help when adding a constraint that all implementations of the interface already satisfy. If any don't already satisfy the constraint, this would be a breaking change until those implementations are updated to satisfy it.

Option 1 is a tradeoff here: it requires updating the implementations even when they already satisfy the added constraint just to say that they do. But it also makes it easier incrementally enforce greater constraints. So in the scenario of adding a constraint, this seems like it would make it easier to incrementally roll out and enforce the change at the cost of higher churn when most things Just Work.

When removing a constraint, there is little difference if the implementations aren't using that constraint in some other way -- for example due to aliasing reusing the associated type in other contexts which need that constraint, or user code that directly uses it (even though it was unnecessary). So when removing a constraint isn't a fundamentally breaking change, the options seem similar. If removing the constraint from the implementation would be a breaking change, option 1 seems to make it easier to preserve the functionality.

On the whole, it seems like both could be made to work. You can alias a normal let ..:! TypeOfType declaration that has extra constraints rather than using the syntax in option 2, and you can use let ElementType:! auto = ... in option 1.

But on balance, it seemed better to try putting the explicit constraints into the implementations so that we have more tools to incrementally roll out changes to interface constraints even though those rollouts will as a consequence be more noisy in some cases. If experience shows that this is a really bad tradeoff, we should revisit it.

[zygoloid]

This decision was revised by #1013; we now use:

impl as Stack where .ElementType = T {
  // ...
}