Generics details 2: adapters, associated types, parameterized interfaces

Problem

We want to Carbon to have a high quality generics feature that achieves the goals set out in #24. This is too big to land in a single proposal. This proposal continues #553 defining the details of:

adapters
associated types and other constants
parameterized interfaces

Background

This is a follow on to these previous generics proposals:

The content for this proposal was extracted from a larger Generics combined draft proposal.

Proposal

This is a proposal to add multiple sections to this design document on generics details.

Rationale based on Carbon’s goals

Much of this rationale was captured in the Generics goals proposal.

Alternatives considered

`adaptor` instead of `adapter`

We considered replacing the adapter keyword with the alternate spelling of “adaptor”. Both spellings can be used for the intended meaning, but the “-er” spelling is more common in English text and in code. The final deciding factor was that the GoF Design Patterns book spells the “adapter pattern” with the “-er” spelling.

Syntax for associated constants

Issue #739: Associated type syntax decided that the syntax for assigning a value to an associated constant, such as an associated type.

The decision was to use let with :! to express that these are compile-time values, matching the use in classes described in proposal #772.

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

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

One advantage was this opened the door for a type to satisfy the associated types of two interfaces with the same name with a single let declaration using constraints satisfying the requirements of both interfaces.

This type can be replaced with auto, to have it determined automatically.

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

This would avoid needing to change the impl when the constraints in the interface changed as long as the value to the right of the = satisfied the new constraints. Otherwise if the constraints are being weakened, first functions relying on the capabilities being removed would have to change, then they would be changed in the interface, and finally the implementations for types. If the constraints are being strengthened, the implementations for types would have to change first followed by the interface.

Omitting types

We also considered omitting the type in the impl, always using the type declared in the interface.

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

This would provide the advantage of reducing the number of changes when changing the constraint specified in the interface. If the constraints were being weakened, then functions that used the capability that was being removed would break or need to be modified. If the constraints were being strengthened, then only type implementations that didn’t satisfy the new constraints would break or need to be modified.

The biggest difference from the selected option is when adding a constraint. In that case the selected option would have more churn, because all implementations would be updated even if they already satisfied the new constraint. This comes with the advantage of making it easier incrementally enforce greater constraints.

On the whole, it seems like both could be made to work. You could explicitly specify constraints with this option by using an alias to a normal let ..:! TypeOfType declaration that has extra constraints. Conversely, you can specify auto as the constraints in the selected option.

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.

Inferring associated types from method signatures

The last option considered is used by Swift. Swift allows the value of an associated type to be omitted when it can be determined from the method signatures in the implementation. For the above example, this would mean figuring out ElementType == T from context:

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

One benefit is that it allows an interface to evolve by adding an associated type, without having to then modify all implementations of that interface.

One concern is this might be a little more complicated in the presence of method overloads with default implementations, since it might not be clear how they should match up, as in this example:

interface Has2OverloadsWithDefaults {
  let T:! StackAssociatedType;
  fn F[me: Self](x: DynamicArray(T), y: T) { ... }
  fn F[me: Self](x: T, y: T.ElementType) { ... }
}

class S {
  impl as Has2OverloadsWithDefaults {
     // Unclear if T == DynamicArray(Int) or
     // T == DynamicArray(DynamicArray(Int)).
     fn F[me: Self](
         x: DynamicArray(DynamicArray(Int)),
         y: DynamicArray(Int)) { ... }
  }
}

Not to say this can’t be resolved, but it does add complexity. Swift considered removing this feature because it was the one thing in Swift that required global type inference, which they otherwise avoided. They ultimately decided to keep the feature.

This option was only very briefly discussed and not preferred because:

It came with complexity of inference.
It seemed unnecessary.

Value patterns

We considered an alternative to the type_of approach from the parameterized interfaces section for binding T to a type mentioned later in the parameter list. We could instead allow functions to have value patterns without a :, as in:

fn PeekAtTopOfStackParameterized
    [T:! Type, StackType:! StackParameterized(T)]
    (s: StackType*, T) -> T { ... }

However, we don’t want to allow value patterns more generally so we can reject declarations like fn F(Int) when users almost certainly meant fn F(i: Int).

Deduced interface parameters

The Carbon team considered and then rejected the idea that we would have two kinds of interface parameters. “Multi” parameters would work as described in the detailed design document. “Deducible” type parameters would only allow one implementation of an interface, not one per interface & type parameter combination. These deducible type parameters could be inferred like associated types are. For example, we could make a Stack interface that took a deducible ElementType parameter. You would only be able to implement that interface once for a type, which would allow you to infer the ElementType parameter like so:

fn PeekAtTopOfStack[ElementType:! Type, StackType:! Stack(ElementType)]
    (s: StackType*) -> ElementType { ... }

This can result in more concise code for interfaces where you generally need to talk about some parameter anytime you use that interface. For example, NTuple(N, type) is much shorter without having to specify names with the arguments.

Rationale for the rejection

Having only one type of parameter simplifies the language.
Multi parameters express something we need, while deducible parameters can always be changed to associated types.
One implementation per interface & type parameter combination is more consistent with other parameterized constructs in Carbon. For example, parameterized types Foo(A) and Foo(B) are distinct, unconnected types.
It would be hard to give clear guidance on when to use associated types versus deducible type parameters, since which is best for a particular use is more of a subtle judgement call.
Deducible parameters in structural interfaces require additional rules to ensure they can be deduced unambiguously.

In addition, deducible interface parameters would complicate the lookup rules for impls.

Impl lookup rules with deducible interface parameters

Interface implementation is Carbon’s only language construct that allows open extension, and this sort of open extension is needed to address the “expression problem” in programming language design. However, we need to limit which libraries can implement an interface for a type so we can be guaranteed to see the implementation when we try and use it.

So the question becomes: can we allow an implementation of a parameterized interface I(T) for a type A to be in the same library as T, or can it only be provided with I or A? The answer is “yes” if T is “multi” and “no” if T is deducible.

The problem with defining the implementation with a deducible T is that it would allow users to violate coherence. Consider this collection of libraries, where there are implementations for an interface I(T) for a type A, and those implementations are in the libraries defining the type parameter:

package X library "I and A" api;

interface I(Type:$ T) { ... }

struct A { ... }

package Y library "T1" api;

import X library "I and A";

struct T1 { ... }

// Type `X.A` has an implementation for `X.I(T)` for `T == Y.T1`.
impl X.I(T1) for X.A { ... }

package Z library "T2" api;

import X library "I and A";

struct T2 { ... }

// Type `X.A` has an implementation for `X.I(T)` for `T == Z.T2`.
impl X.I(T2) for X.A { ... }

package Main api;

import X library "I and A";
// Consider what happens if we include different combinations
// of the following two statements:
// import Y library "T1";
// import Z library "T2";

// Function `F` is called with value `a` with type `U`,
// where `U` implements interface `X.I(T)` for some type `T`.
fn F[Type:$ T, X.I(T):$ U](U:$ a) { ... }

fn Main() {
  var X.A: a = X.A.Init();
  F(a);
}

(In the example, each library is in a different package, but the packages are not the important part here.)

The F(a) call triggers a lookup for implementations of the interface X.I(T) for some T. There exists such implementations in both libraries Y.T1 and Z.T2 for different values of T. This has a number of sad consequences:

“Import what you use” is hard to measure: libraries Y.T1 and Z.T2 are important and used even though Y and Z are not mentioned outside the import statement.
The call F(a) has different interpretations depending on what libraries are imported:
- If neither is imported, it is an error.
- If both are imported, it is ambiguous.
- If only one is imported, you get totally different code executed depending on which it is.
We have no way of enforcing a “one implementation per interface” rule that would prevent the call to F from being ambiguous.

Basically, there is nothing guaranteeing that we import libraries defining the types that are used as interface parameters if we allow the interface parameters to be deduced.

Only associated types, no interface parameters

This is what Swift does, but doesn’t allow us to use interfaces to express operator overloads. For example, a vector should be able to be added to either a vector or a point. So we follow Rust, which has trait parameters in addition to associated types and uses them to define the behavior of operators.

Others

Other alternatives considered will be in a future proposal. Some of them can be seen in a rough form in #36.