# Generics details 2: adapters, associated types, parameterized interfaces

<!--
Part of the Carbon Language project, under the Apache License v2.0 with LLVM
Exceptions. See /LICENSE for license information.
SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-->

[Pull request](https://github.com/carbon-language/carbon-lang/pull/731)

<!-- toc -->

## Table of contents

-   [Problem](#problem)
-   [Background](#background)
-   [Proposal](#proposal)
-   [Rationale based on Carbon's goals](#rationale-based-on-carbons-goals)
-   [Alternatives considered](#alternatives-considered)
    -   [`adaptor` instead of `adapter`](#adaptor-instead-of-adapter)
    -   [Syntax for associated constants](#syntax-for-associated-constants)
        -   [Omitting types](#omitting-types)
        -   [Inferring associated types from method signatures](#inferring-associated-types-from-method-signatures)
    -   [Value patterns](#value-patterns)
    -   [Deduced interface parameters](#deduced-interface-parameters)
        -   [Rationale for the rejection](#rationale-for-the-rejection)
            -   [Impl lookup rules with deducible interface parameters](#impl-lookup-rules-with-deducible-interface-parameters)
    -   [Only associated types, no interface parameters](#only-associated-types-no-interface-parameters)
    -   [Others](#others)

<!-- tocstop -->

## Problem

We want to Carbon to have a high quality generics feature that achieves the
goals set out in [#24](https://github.com/carbon-language/carbon-lang/pull/24).
This is too big to land in a single proposal. This proposal continues
[#553](https://github.com/carbon-language/carbon-lang/pull/553) defining the
details of:

-   adapters
-   associated types and other constants
-   parameterized interfaces

## Background

This is a follow on to these previous generics proposals:

-   [#24: Generics goals](https://github.com/carbon-language/carbon-lang/pull/24)
-   [#447: Generics terminology](https://github.com/carbon-language/carbon-lang/pull/447)
-   [#524: Generics overview](https://github.com/carbon-language/carbon-lang/pull/524)
-   [#553: Generics details part 1](https://github.com/carbon-language/carbon-lang/pull/553)

The content for this proposal was extracted from a larger
[Generics combined draft proposal](https://github.com/carbon-language/carbon-lang/pull/36).

## Proposal

This is a proposal to add multiple sections to
[this design document on generics details](/docs/design/generics/details.md).

## Rationale based on Carbon's goals

Much of this rationale was captured in the
[Generics goals proposal](https://github.com/carbon-language/carbon-lang/pull/24).

## 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](https://en.wikipedia.org/wiki/Design_Patterns) spells
the ["adapter pattern"](https://en.wikipedia.org/wiki/Adapter_pattern) with the
["-er" spelling](https://springframework.guru/gang-of-four-design-patterns/adapter-pattern/).

### Syntax for associated constants

Issue
[#739: Associated type syntax](https://github.com/carbon-language/carbon-lang/issues/739)
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](p0722.md#let-constants).

```
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](https://docs.swift.org/swift-book/LanguageGuide/Generics.html#ID190).
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](/docs/design/generics/details.md#interface-defaults),
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](https://github.com/apple/swift/blob/main/docs/GenericsManifesto.md#associated-type-inference)
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](https://github.com/apple/swift-evolution/blob/main/proposals/0108-remove-assoctype-inference.md).

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](/docs/design/generics/details.md#parameterized-interfaces)
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](/docs/design/generics/details.md#parameterized-interfaces).
"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](/docs/design/generics/details.md#associated-facets) 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](/docs/design/generics/goals.md#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](https://github.com/carbon-language/carbon-lang/pull/36).
