# Generic blanket impls (details 5) [Pull request](https://github.com/carbon-language/carbon-lang/pull/920) ## Table of contents - [Problem](#problem) - [Background](#background) - [Proposal](#proposal) - [Rationale based on Carbon's goals](#rationale-based-on-carbons-goals) - [Alternatives considered](#alternatives-considered) - [Different syntax](#different-syntax) - [Inconsistent syntax](#inconsistent-syntax) - [Members defined out-of-line](#members-defined-out-of-line) - [Context sensitivity](#context-sensitivity) - [Orphan rule could consider interface requirements in blanket impls](#orphan-rule-could-consider-interface-requirements-in-blanket-impls) - [Child trumps parent rule](#child-trumps-parent-rule) - [Impls could limit specialization](#impls-could-limit-specialization) - [Libraries for orphan impls](#libraries-for-orphan-impls) - [Different traversal order for overlap rule](#different-traversal-order-for-overlap-rule) - [Intersection rule in addition to prioritization](#intersection-rule-in-addition-to-prioritization) - [Name lookup into conditional impls](#name-lookup-into-conditional-impls) - [Automatic implicit conversions](#automatic-implicit-conversions) ## Problem There are cases where an impl definition should apply to more than a single type and interface combination. The solution is to parameterize the impl definition, so it applies to a family of types, interfaces, or both. This includes: - Declaring an impl for a parameterized type, which may be external or declared out-of-line. - "Conditional conformance" where a parameterized type implements some interface if the parameter to the type satisfies some criteria, like implementing the same interface. - "Blanket" impls where an interface is implemented for all types that implement another interface, or some other criteria beyond being a specific type. - "Wildcard" impls where a family of interfaces are implemented for single type. In addition to a syntax for defining parameterized impls, we need rules for coherence: - Orphan rules ensure that an impl is imported in any code that might use it. - Overlap rules pick a specific impl when more than one impl declaration matches a specific query about whether a type implements an interface. ## Background Rust supports parameterized impls, but has not stabilized the specialization feature that resolves multiple impls applying. ## Proposal This is a proposal to add [a "parameterized impls" section to the generics design details](/docs/design/generics/details.md#parameterized-impl-declarations). ## Rationale based on Carbon's goals Much of this rationale for generics was captured in the [Generics goals proposal](https://github.com/carbon-language/carbon-lang/pull/24). This proposal is particularly concerned with achieving the goal of making generics [coherent](/docs/design/generics/goals.md#coherence). ## Alternatives considered ### Different syntax This conditional interface implementation syntax was decided in [issue #575](https://github.com/carbon-language/carbon-lang/issues/575), and clarified in [a Discord discussion in #syntax](https://discord.com/channels/655572317891461132/709488742942900284/903036676371259432). A large part of what was decided in that issue is the syntax used for non-parameterized impls, and incorporated into the Carbon generics design in [proposal #553: Generics details part 1](https://github.com/carbon-language/carbon-lang/pull/553). #### Inconsistent syntax Our primary concern with the syntax for parameterized impls was that it be consistent with non-parameterized impls, and consistent between lexically inline and out-of-line definitions. Consistency was the basis for rejecting a number of conditional conformance options: - The `extend` syntax inline in a class definition to establish a more specific `Self` type for conditional conformance choice was eliminated along with [the `extend` syntax for external impls](p0553.md#extend-blocks). - Consistency excluded using deduced arguments in square brackets after the `impl` keyword, and an `if` or `where` clause to add constraints: ``` class FixedArray(T:! Type, N:! Int) { impl as [U:! Printable] Printable if T == U { // Here `T` and `U` have the same value and so you can freely // cast between them. The difference is that you can call the // `Print` method on values of type `U`. } } class Pair(T:! Type, U:! Type) { impl as Foo(T) if T == U { // Can cast between `Pair(T, U)` and `Pair(T, T)` since `T == U`. } } ``` This was too different from how those same impls would be declared out-of-line. - Another approach that was too different between inline and out-of-line, is to use pattern matching instead of boolean conditions. This might look like: ``` class FixedArray(T:! Type, N:! Int) { @if let P:! Printable = T { impl as Printable { ... } } } interface Foo(T:! Type) { ... } class Pair(T:! Type, U:! Type) { @if let Pair(T, T) = Self { impl as Foo(T) { ... } } } ``` #### Members defined out-of-line We rejected options that declared unqualified member names outside of the scope defining the class. This would have allowed us to consistently use an out-of-line syntax, but starting with something other than `external` when it affected the names in the class. #### Context sensitivity We rejected options for conditional conformance where the meaning of names declared in the class scope would have a more specific meaning in an inner scope. This would be much like how a language with [flow-sensitive typing](https://en.wikipedia.org/wiki/Flow-sensitive_typing) might affect the types in an inner scope as part of control flow. For example, a `where` clause on an `impl` declaration might add constraints to a class parameter only inside the scope of the `impl` it was applied to: ``` class FixedArray(T:! Type, N:! Int) { impl as Printable where T is Printable { // Inside this scope, `T` has type `Printable` instead of `Type`. } } ``` These options were rejected based on the [low-context-sensitivity principle](/docs/project/principles/low_context_sensitivity.md). ### Orphan rule could consider interface requirements in blanket impls The orphan rule states that a rule like ``` impl [T:! Interface1] T as Interface2 { ... } ``` can only live in the library that defines `Interface2`, not the library that defines `Interface1`. To see that the alternative is not coherent, consider this example where we have three libraries, with one a common library imported by the other two: - Library `Common` ``` interface ICommon { ... } class S { ... } ``` - Library `A`: ``` import Common interface IA { ... } // Local interface only used as a constraint impl [T:! IA] T as ICommon { ... } // Fine: implementation of a local interface impl S as IA { ... } ``` - Library `B`: ``` import Common interface IB { ... } // Local interface only used as a constraint impl [T:! IB] T as ICommon { ... } // Fine: implementation of a local interface impl S as IB { ... } ``` Inside another library that imports the `Common` library: - Does `S` implement `ICommon`? If you just import `ICommon`, no implementations are visible - Does the answer change if you import libraries `A` or `B`? - Which implementation of `ICommon` should `S` use if you import both? We avoid these problems by requiring the use of a local type or interface **outside** of constraints. ### Child trumps parent rule [Rust has considered a "child trumps parent" rule](http://aturon.github.io/tech/2017/02/06/specialization-and-coherence/). This rule would say that a library `Child` importing library `Parent` is enough to prioritize `impl` definitions in `Child` over `Parent` when they would otherwise overlap without one matching a strict subset of the other. The goal would be to resolve overlaps in a way that is both easy to understand and more often matches what implementations users actually want prioritized. One caveat of this rule is that a simple interpretation is not transitive. If we define three impls in three different libraries, with these type structures: - `impl (A, ?, ?) as I` - `impl (?, B, ?) as I` - `impl (?, ?, C) as I` then the type structure rule would prioritize `A` over `B` over `C`. If the library with `C` had a dependency on the one with `A`, though, then `C` would have priority over `A`, and we would not be able to decide which impl to use for `(A, B, C)`. The fix is to change the rule to be "Child trumps parent on their intersection". With that rule, it would be as if there was another implementation defined on the intersection of `(A, ?, ?)` and `(?, ?, C)`, that is it would match `(A, ?, C)`, that had the highest priority and delegated to the `(?, ?, C)` impl for the definition of the body. Without some child trumps parent rule: If I define a new type, then all impl lookup for interfaces implemented by that type as `Self` will consider impl from my library first, at the time I define it until some other library adds an impl of that type as `Self`. However, adding the "child trumps parent on their intersection" rule removes this property. This is something we would consider in the future once we have more experience. Note that this rule has not yet been implemented in Rust, so we don't know how it works out in practice. ### Impls could limit specialization This would allow greater reasoning in generic functions, requiring less specification. For example, there may be a blanket implementation of `PartiallyOrdered` provided for types that implement `Ordered`. If that blanket implementation could not be specialized, a generic function could rely on the implementations of the two interfaces being consistent with each other. This feature has been left for a future proposal. Note this feature needs to be limited to those cases where the implementation that limits specialization will be guaranteed to be a dependency of all implementations that are prioritized as more specific. ### Libraries for orphan impls The [orphan rule](/docs/design/generics/details.md#orphan-rule) means that there may be no library that can define an impl with a particular type structure. Rust has encountered this problem already, see [Rust RFC #1856: "Orphan rules are stricter than we would like"](https://github.com/rust-lang/rfcs/issues/1856). Carbon does not currently address this problem, but we would consider future changes that do as long as coherence was maintained. For example, we'd consider a mechanism that allowed libraries to be defined that must be imported, either implicitly or explicitly, depending on whether specific other libraries are imported or linked into the project. ### Different traversal order for overlap rule The [overlap rule](/docs/design/generics/details.md#overlap-rule) uses a depth-first traversal of the type tree to identify the first difference between two different type structures. We could also do another order, such as breadth-first, but this order is both simple and reflects some experience from the Rust community that the `Self` type is particularly important to prioritize. ### Intersection rule in addition to prioritization Another approach for [selecting between impls with the same type structure](/docs/design/generics/details.md#prioritization-rule) is to require that there is an impl matching the intersection of any two impls with the same type structure, and then prioritize by containment. This approach is being considered for Rust, see [Baby Steps: "Intersection Impls"](http://smallcultfollowing.com/babysteps/blog/2016/09/24/intersection-impls/) and [Aaron Turon: "Specialization, coherence, and API evolution](http://aturon.github.io/tech/2017/02/06/specialization-and-coherence/). Instead of requiring that impls with the same type structure are always in the same prioritization block, that requirement could be only when the intersection isn't defined. The advantage of the prioritization block is that it can express everything that intersection impls can express, and generally can do so without having to write an exponential number of impl declarations. Prioritization blocks do require you to write all the impls together in a block, though, so we might want to support the option of allowing developers to explicitly write out intersections instead. This might be convenient in cases where the intersection is defined anyway, such as when there is already strict subset relationship between the impls. ### Name lookup into conditional impls We considered the possibility that name lookup would fail to find the members of that impl when a conditional impl's condition does not apply. This would allow ``` class X(T:! Type) { impl X(i32) as Foo { fn F[me: Self](); } impl X(i64) as Bar { fn F[me: Self](n: i64); } } ``` where `X(T).F` means different things for different `T`, which could be an unpleasant surprise. This seemed against the Carbon philosophy of making the code behave consistently and predictably, and didn't have a motivating use case. ### Automatic implicit conversions We considered adding two features to support operator overloading use cases, where the language would select the interface parameter using the type of the second argument without considering implicit conversions. The intent of these features was to, for example, make it convenient to support addition with anything that implicitly converted to `i32` by implementing addition with just `i32`. One feature was to support implementing an interface using a function with a different signature, as long as the compiler could automatically generate a wrapper that bridged the two signatures using implicit conversions. This raised concerns about accidentally implementing interfaces with functions that had the wrong signature, evolution problems when new overloads were introduced, and surprises and confusing errors from a single function considered to have two different signatures. The other feature was to allow a wildcard implementation as long as it could be implemented using functions that did not vary with the wildcard parameter, by implicitly converting to a common type. This introduced concerns about what to do with other members of the interface, particularly those with defaults. Perhaps we would allow functions as long as the interface parameters could be deduced from the types of the arguments? Perhaps we would require explicit qualification to call functions where the interface parameter couldn't be deduced? In particular we were worried about evolution, and allowing users to add functions to an interface as long as they had defaults. These problems were discussed in [2021-12-08 open discussion](https://docs.google.com/document/d/1YhwNKLxQsWf8NPVaRm9PvgPmSM3PIK_KlD1gpNuUfwY/edit#heading=h.njnqpdcjp5h0). We concluded that we will later find other mechanisms to support this use case.