# Template generics [Pull request](https://github.com/carbon-language/carbon-lang/pull/2200) ## Table of contents - [Abstract](#abstract) - [Problem](#problem) - [Background](#background) - [Terminology](#terminology) - [Proposal](#proposal) - [Details](#details) - [Syntax](#syntax) - [Branching on type identity](#branching-on-type-identity) - [Value phases](#value-phases) - [`auto`](#auto) - [Template constraints](#template-constraints) - [Name lookup](#name-lookup) - [Transition from C++ templates to Carbon checked generics](#transition-from-c-templates-to-carbon-checked-generics) - [To template Carbon with structural constraints](#to-template-carbon-with-structural-constraints) - [To interface constraints](#to-interface-constraints) - [To checked generic](#to-checked-generic) - [Validity can depend on value](#validity-can-depend-on-value) - [Template dependent](#template-dependent) - [Simple member access](#simple-member-access) - [Compound member access](#compound-member-access) - [Impl lookup](#impl-lookup) - [Use of dependent value is dependent](#use-of-dependent-value-is-dependent) - [Rationale](#rationale) - [Alternatives considered](#alternatives-considered) - [Only checked generics](#only-checked-generics) - [SFINAE](#sfinae) - [Ad hoc API specialization](#ad-hoc-api-specialization) - [Value phase of bindings determined by initializer](#value-phase-of-bindings-determined-by-initializer) - [Simpler template dependent rules that delayed more checking](#simpler-template-dependent-rules-that-delayed-more-checking) - [Future work](#future-work) - [Expanded template constraints](#expanded-template-constraints) - [Predicates: constraints on values](#predicates-constraints-on-values) - [Checked generics calling templates](#checked-generics-calling-templates) - [Which expressions will be evaluated at compile time](#which-expressions-will-be-evaluated-at-compile-time) ## Abstract Add template generics, with optional constraints but no [SFINAE](https://en.cppreference.com/w/cpp/language/sfinae), to Carbon. Template generics allows the compiler to postpone type checking of expressions dependent on a template parameter until the function is called and the value of that parameter is known. Example usage: ```carbon fn Identity[template T:! Type](x: T) -> T { return x; } ``` ## Problem Starting with [#24: Generics goals](https://github.com/carbon-language/carbon-lang/pull/24), we have assumed templates (also known as "template generics" in Carbon) will be a feature of Carbon, but it has not been an accepted part of the design. We now understand enough about how they should fit into the language to decide that we are including the feature in the language, and what form they should take. Template generics will address these use cases: - They provide a step in the transition from C++ templates to Carbon checked generics. - They provide a generics programming model familiar to C++ developers. - They allow Carbon to separate features that we don't want to expose by default in checked generics. These are features that pierce abstraction boundaries that we want to discourage for software engineering reasons or at least mark when they are in use. Examples in this category include: - Compile-time duck typing features that use the structural properties of types, like having a method with a particular name, rather than semantic properties like implementing an interface. - Branching in code based on type identity. Out of scope for this proposal are any questions about passing a checked generic argument value to a template parameter. See question-for-leads issue [#2153: Generics calling templates](https://github.com/carbon-language/carbon-lang/issues/2153). ## Background Templates are the mechanism for performing [generic programming](https://en.wikipedia.org/wiki/Generic_programming) in C++, see [cppreference.com](https://en.cppreference.com/w/cpp/language/templates). There have been a number of prior proposals and questions-for-leads issues on template generics on which this proposal builds: - Proposal [#24: Generics goals](https://github.com/carbon-language/carbon-lang/pull/24) talked about the reasons for templates, without committing Carbon to including them. These reasons include making it easier to transition C++ template code to Carbon and providing functionality outside of what we want to support with checked generics. - Proposal [#447: Generics terminology](https://github.com/carbon-language/carbon-lang/pull/447) defined terminology. This included some of the differences between checked and template generics, and definitions for terms like _instantiation_. - Proposal [#553: Generic details part 1](https://github.com/carbon-language/carbon-lang/pull/553) defined `auto` as a template construct, and described how templates do not require constraints to find member names. - Question-for-leads issue [#565: Generic syntax to replace provisional `$`s](https://github.com/carbon-language/carbon-lang/issues/565) implemented in proposal [#676: `:!` generic syntax](https://github.com/carbon-language/carbon-lang/pull/676) defined the syntax for template bindings. - Proposal [#731: Generics details 2: adapters, associated types, parameterized interfaces](https://github.com/carbon-language/carbon-lang/pull/731) included that template values may be passed to generic parameters. - Proposal [#818: Constraints for generics](https://github.com/carbon-language/carbon-lang/pull/818) included `template constraint` to defined named constraints with fewer restrictions for use with template parameters. - Proposal [#875: Principle: information accumulation](https://github.com/carbon-language/carbon-lang/pull/875) considered how the principle benefited and was impacted by templates. - Question-for-leads issue [#949: Constrained template name lookup](https://github.com/carbon-language/carbon-lang/issues/949) implemented in proposal [#989: Member access expressions](https://github.com/carbon-language/carbon-lang/pull/989) defined how name lookup works for template parameters. It provided a path to incrementally adopt constraints on template parameters, a stepping stone to transitioning to checked generics. - Proposal [#950: Generics details 6: remove facets](https://github.com/carbon-language/carbon-lang/pull/950) included the impact on the semantics of templates in its rationale. - Proposal [#1146: Generic details 12: parameterized types](https://github.com/carbon-language/carbon-lang/pull/1146) allowed template type parameters. - Proposal [#1270: Update and expand README content and motivation for Carbon](https://github.com/carbon-language/carbon-lang/pull/1270) advertised that Carbon would support templates for "seamless C++ interop." - Terminology was updated in proposal [#2138: Checked and template generic terminology](https://github.com/carbon-language/carbon-lang/pull/2138). TODO: Update if proposal [#2188: Pattern matching syntax and semantics](https://github.com/carbon-language/carbon-lang/pull/2188) is accepted first. ## Terminology - A _template dependent_ name or expression is one whose meaning depends on, that is varies with, some template generic parameter. Specifically this refers to an expression that can not be fully checked until the value of the parameter is known. This is consistent with the meaning of this term in [C++](https://en.cppreference.com/w/cpp/language/dependent_name), but is different from ["dependent types"](https://en.wikipedia.org/wiki/Dependent_type). The specifics of how this works in Carbon are being proposed in [a later section](#template-dependent). - [_Instantiation_](/docs/design/generics/terminology.md#instantiation), _substitution_, or [_monomorphizaton_](https://en.wikipedia.org/wiki/Monomorphization) is the process of duplicating the implementation of a function and then substituting in the values of any (checked or template) generic arguments. - Errors that are only detected once the argument value from the call site is known are called _monomorphization errors_. These mostly occur in expressions dependent on some template parameter, but can also occur for other reasons like hitting an implementation limit. - _SFINAE_ stands for "Substitution failure is not an error", which is the policy in C++, see [cppreference](https://en.cppreference.com/w/cpp/language/sfinae), [wikipedia](https://en.wikipedia.org/wiki/Substitution_failure_is_not_an_error). It means that functions from an overload set with monorphization errors, or "substitution failure," within their signatures are simply ignored instead of causing compilation to fail. ## Proposal We propose that template generics are included as an official feature of Carbon. In many ways, template generic parameters work like checked generic parameters. The following are true for any kind of generic parameter: - The value passed to a generic parameter must be able to be evaluated at compile time. - Generic parameters may have constraints that will be enforced by the compiler on the value supplied by the caller. - The compiler may choose to generate multiple copies of a generic function for different values of the generic parameters. The main differences between checked and templated generics are: - Member lookup into a templated type looks in the actual type value provided by the caller in addition to in any constraints on that type; see [proposal #989](https://github.com/carbon-language/carbon-lang/pull/989). - A templated parameter may be used in ways where the validity of the result depends on the value of the parameter, not just its type. - Impl lookup is delayed until all templated types, interfaces, and parameters are known. As a consequence of these differences, type checking of any expression dependent on a templated parameter may not be completed until its value is known. In addition, templated generics support branching on the value of a templated type. In contrast with C++ templates, with Carbon template generics: - Substitution failure is an error. In C++, [the SFINAE rule](#terminology) will skip functions in overload resolution that fail to instantiate. Instead, Carbon template parameters use constraints to control when the function is available. - Carbon template specialization does not allow ad hoc changes to the API of the function or type being specialized, only its implementation. This is in contrast to C++, where [C++'s `std::vector`](https://en.cppreference.com/w/cpp/container/vector_bool) has different return types for certain methods. Anything that can vary in an API must be explicitly marked using associated types of an interface, as is described in the ["parameterized type specialization" design](/docs/design/generics/details.md#specialization). - Constraints on a Carbon template type affect how lookup is done into that type, as described in [proposal #989](https://github.com/carbon-language/carbon-lang/pull/989). ## Details ### Syntax Template generic bindings are declared using the `template` keyword in addition to the `:!` of all generic bindings. This includes `let` declarations, as in: ```carbon // `N` is a constant that may be used in types. let template N:! i64 = 4; var my_array: [u8; N] = (255, 128, 64, 255); ``` Function parameters also default to a `let` context and may use `template`: ```carbon // `U` is a templated type parameter that must be specified // explicitly by the caller. fn Cast[template T:! Type](x: T, template U:! Type) -> U { // OK, check for `T is As(U)` delayed until values of `T` and `U` are known. return x as U; } let x: i32 = 7; // Calls `Cast` with `T` set to `i32` and `U` set to `i64`. let y: auto = Cast(x, i64); // Type of `y` is `i64`. ``` Note that generic bindings, checked or template, can only be used in `let` context to produce r-values, not in a `var` context to produce l-values. ```carbon // ❌ Error: Can't use `:!` with `var`. Can't be both a // compile-time constant and a variable. var N:! i64 = 4; // ❌ Error: Can't use `template :!` with `var` for the // same reason. var template M:! i64 = 5; ``` #### Branching on type identity Branching on the value of a templated type will be done using a `match` statement, but is outside the scope of this proposal. See instead pending proposal [#2188: Pattern matching syntax and semantics](https://github.com/carbon-language/carbon-lang/pull/2188). ### Value phases R-values are divided into three different _value phases_: - A _constant_ has a value known at compile time, and that value is available during type checking, for example to use as the size of an array. These include literals (integer, floating-point, string), concrete type values (like `f64` or `Optional(i32*)`), expressions in terms of constants, and values of `template` parameters. - A _symbolic value_ has a value that will be known at the code generation stage of compilation when monomorphization happens, but is not known during type checking. This includes checked-generic parameters, and type expressions with checked-generic arguments, like `Optional(T*)`. - A _runtime value_ has a dynamic value only known at runtime. So: - A `let template T:! ...` or `fn F(template T:! ...)` declaration binds `T` with constant value phase, - A `let T:! ...` or `fn F(T:! ...)` declaration binds `T` with symbolic value phase, - A `let x: ...` or `fn F(x: ...)` declaration binds `x` with runtime value phase. **Note:** The naming of value phases is the subject of open question-for-leads issue [#1391: New name for "constant" value phase](https://github.com/carbon-language/carbon-lang/issues/1391). This terminology comes from [a discussion in #typesystem on Discord](https://discord.com/channels/655572317891461132/708431657849585705/992817321074774098), in particular [this message](https://discord.com/channels/655572317891461132/708431657849585705/994396535561408623). **Note:** This reflects the resolution of question-for-leads issue [#1371: Is `let` referentially transparent?](https://github.com/carbon-language/carbon-lang/issues/1371) that the value phase of a binding is determined by the kind of binding, and not anything about the initializer. **Note:** The situations in which a value with one phase can be used to initialize a binding with a different value phase is future work, partially considered in question-for-leads issue [#2153: Generics calling templates](https://github.com/carbon-language/carbon-lang/issues/2153) in addition to [#1371: Is `let` referentially transparent?](https://github.com/carbon-language/carbon-lang/issues/1371). **Note:** Exactly which expressions in terms of constants result in constants is an open question that is not resolved by this proposal. In particular, which function calls will be evaluated at compile time is not yet specified. See [future work](#which-expressions-will-be-evaluated-at-compile-time). ### `auto` The `auto` keyword is a shortcut for an unnamed templated type, as in: ```carbon // Type of `x` is the same as the return type of function `F`. let x: auto = F(); ``` This was first added to Carbon in proposal [#553: Generic details part 1](https://github.com/carbon-language/carbon-lang/pull/553) and further specified by open proposal [#2188: Pattern matching syntax and semantics](https://github.com/carbon-language/carbon-lang/pull/2188). The `auto` keyword may also be used to omit the return type, as specified in [#826: Function return type inference](https://github.com/carbon-language/carbon-lang/pull/826). The semantics of `let x:! auto = ...` is the subject of open question-for-leads issue [#996: Generic `let` with `auto`?](https://github.com/carbon-language/carbon-lang/issues/996). ### Template constraints Template constraints have already been introduced in proposal [#818: Constraints for generics](https://github.com/carbon-language/carbon-lang/pull/818). In brief, a `template constraint` declaration is like a `constraint` declaration, except that it may also contain function and field declarations, called _structural constraints_. Only types with matching declarations will satisfy the template constraint. Note that the declarations matching the structural constraints must be found by member lookups in the type. It is not sufficient for them to be declared only in an external impl. ```carbon interface A { fn F[me: Self](); } interface B { fn F[me: Self](); } class C { } external impl C as A; external impl C as B; template constraint HasF { fn F[me: Self](); } fn G[template T:! HasF](x: T); var y: C = {}; // Can't call `G` with with `y` since it doesn't have any internal // implementation of a method `F` satisfying `HasF`, even though `C` // externally implements both `A` and `B` with such an `F`. May // define an adapter for `C` to get a type that implements `HasF`, // with `A.F`, `B.F`, or some other definition. ``` This was discussed in [#generics-and-templates on 2022-09-20](https://discord.com/channels/655572317891461132/941071822756143115/1021903925613449316). Structural constraints do not affect [name lookup](#name-lookup) into template type parameters. They guarantee that a name will be available in the type, but don't change the outcome. ```carbon template constraint HasF { fn F[me: Self](); } class C { fn F[me: Self](); } fn G[template T:! HasF](x: T) { x.F(); } var y: C = {}; // Call to `F` inside `G` is not ambiguous since // `C.F` and `HasF.F` refer to the same function. G(y); class D extends C { alias F = C.(A.F); } // OK, `z.(HasF.F)` will resolve to `z.(C.(A.F))`. fn Run(z: D) { G(z); } ``` Whether template constraints may be used as constraints on checked-generic parameters is being considered in question-for-leads issue [#2153: Generics calling templates](https://github.com/carbon-language/carbon-lang/issues/2153). Even if we allow a checked-generic parameter to use a template constraint, we want to focus checked generics on semantic properties encapsulated in interfaces, not structural properties tested by template constraints. So we would not allow lookup into a checked-generic type to find type members outside of an interface: ```carbon template constraint HasF { fn F[me: Self](); } // ❓ If we allow a checked generic to use a template // constraint, as in: fn H[T:! HasF](x: T) { // We still will not support calling `F` on `x`: // ❌ x.F(); } ``` These members would only be found using a template type parameter. [Expanding the kinds of template constraints](#expanded-template-constraints) and [defining a way to put constraints on values](#predicates-constraints-on-values) are both [future work](#future-work). ### Name lookup Name lookup for templates has already been decided in question-for-leads issue [#949: Constrained template name lookup](https://github.com/carbon-language/carbon-lang/issues/949) and proposal [#989: Member access expressions](https://github.com/carbon-language/carbon-lang/pull/989). Briefly, name lookup is done both in the actual type value supplied at the call site and the interface constraints on the parameter. If the name is found in both, it is an error if they resolve to different entities. Look up into the calling type gives _compile-time duck typing_ behavior, much like C++ templates, as in: ```carbon fn F[template T:! Type](x: T) { // Calls whatever `M` is declared in `T`, and will // fail if `T` does not have a matching member `M`. x.M(); } class C1 { fn M[me: Self](); } var x1: C1 = {}; // Calls `F` with `T` equal to `C1`, which succeeds. F(x1); class C2 { fn M[addr me: Self*](); } var x2: C2 = {}; // Calls `F` with `T` equal to `C2`, which fails, // since `x` is an r-value in `F` and `C2.M` requires // an l-value. F(x2); class C3 { fn M[me: Self](p: i32); } var x3: C3 = {}; // Calls `F` with `T` equal to `C3`, which fails, // since `C3.M` must be passed an argument value. F(x3); class C4 { fn M[me: Self](p: i32 = 4); } var x4: C4 = {}; // Calls `F` with `T` equal to `C4`, which succeeds, // using the default value of `4` for `p` when // calling `C4.M`. F(x4); class C5 { var v: i32; } var x5: C5 = {.v = 5}; // Calls `F` with `T` equal to `C5`, which fails, // since `T` has no member `M`. F(x5); ``` Note that in some cases of looking up a qualified name, lookup will not depend on the value of the template parameter and can be checked before instantiation, as in: ```carbon interface A { fn F[me: Self](); } fn G[template T:! A](x: T) { // No question what this resolves to, can be checked // when `G` is defined: x.(A.F)(); // Will generate a monomorphization error if // `T.F` means something different than `T.(A.F)`, // can only be checked when `G` is called: x.F(); } ``` ### Transition from C++ templates to Carbon checked generics We have a specific [goal for generics](/docs/design/generics/goals.md#upgrade-path-from-templates) that we have a smooth story for transitioning from C++ templates to Carbon checked generics. Adding template generics to Carbon allows this to be done in steps. These steps serve two purposes. One is to allow any updates needed for callers and types used as parameters to be done incrementally. The second is to avoid any silent changes in semantics that would occur from jumping directly to Carbon checked generics. Each step will either preserve the meaning of the code or result in compile failures. #### To template Carbon with structural constraints The first step is to convert the C++ function with one or more template parameters to a Carbon function with template generic parameters. Any [non-type template parameters](https://en.cppreference.com/w/cpp/language/template_parameters#Non-type_template_parameter) can be converted to template generic parameters with the equivalent type, as in: ``` // This C++ function: void F_CPlusPlus(); // gets converted to Carbon: fn F_Carbon(template N:! i32); ``` Other template parameters can either be declared without constraints, using `template T:! Type`, or using [structural constraints](#template-constraints). To see if this transition can cause silent changes in meaning, consider how this new Carbon function will be different from the old C++ one: - The conversion of the body of the code in the function could introduce differences, but only template concerns are in scope for this proposal. - The C++ code could use ad hoc API specialization. The only way to translate that to Carbon is through [explicit parameterization of the API](/docs/design/generics/details.md#specialization), which is not expected to introduce silent changes in meaning. - The C++ code could rely on [SFINAE](#terminology). C++ uses of `std::enable_if` should be translated to equivalent [template constraints](#template-constraints). Generally making substitution failure an error is expected to make less code compile, not introduce silent changes in meaning. - As long as the constraints on template type parameters are [structural](#template-constraints) and not interface constraints, the name lookup rules into those type parameters will consistently look in the type for both C++ and Carbon. #### To interface constraints The next step is to switch from structural constraints to interface constraints. The interfaces that are providing the functionality that the function relies on must be identified or created. In some cases this could be done automatically when names are resolved consistently to interface methods in the types currently being used to instantiate the function. Once that is done, there are two approaches: - Implement the interface for every instantiating type. Once that is done, the function's constraint can be updated. - Alternatively, a blanket implementation of the interface could be defined for any type implementing the structural constraints so that the function's constraint can be updated first. After that, the interface can be implemented for types individually, overriding the blanket implementation until the blanket implementation is no longer needed. This second choice requires changes to the library defining the interface, and is most appropriate when it is a new interface specifically created for this function. In either case, the compiler will give an error if the interface is not implemented for some types before the step is finished. An example of the second approach, starting with a templated function with a structural constraint: ```carbon template constraint HasF { fn F[me: Self](); } fn G[template T:! HasF](x: T) { x.F(); } class C { fn F[me: Self](); } var y: C = {}; G(y); ``` First, a new interface is created with a blanket implementation and the function's constraints are updated to use it instead. Calls in the function body should be qualified to avoid ambiguity errors. ```carbon template constraint HasF { fn F[me: Self](); } // New interface interface NewF { fn DoF[me: Self](); } // Blanket implementation external impl forall [template T:! HasF] T as NewF { // If the functions are identical, can instead do: // alias DoF = T.F; fn DoF[me: Self]() { me.F(); // Or: me.(T.F)(); } } // Changed constraint fn G[template T:! NewF](x: T) { // Call function from interface x.(NewF.DoF)(); // Could use `x.DoF();` instead, but that will // give a compile error if `T` has a definition // for `DoF` in addition to the one in `NewF`. } class C { fn F[me: Self](); } var y: C = {}; // Still works since `C` implements `NewF` // from blanket implementation. G(y); ``` Then the interface is implemented for types used as parameters: ```carbon // ... class C { impl as NewF { // `NewF.DoF` will be called by `G`, not `C.F`. fn DoF[me: Self](); } // No longer needed: fn F[me: Self](); } // ... ``` Once all types have implemented the new interface, the blanket implementation can be removed: ```carbon // Template constraint `HasF` no longer needed. // New interface interface NewF { fn DoF[me: Self](); } // Blanket implementation no longer needed. fn G[template T:! NewF](x: T) { x.(NewF.DoF)(); } class C { impl as NewF { fn DoF[me: Self](); } } var y: C = {}; // `C` implements `NewF` directly. G(y); ``` The [name lookup rules](#name-lookup) ensure that unqualified names will only have one possible meaning, or the compiler will report an error. This error may be resolved by adding qualifications, which is done with the context of an ambiguity for a specific type. This avoids silent changes in the meaning of the code. Once the disambiguating qualifications have been added, the transition to checked generic becomes safe. #### To checked generic Once all needed qualifications are in place, the `template` keyword can be removed. After this, names will only be looked up in the interface constraints, not the type. If this does not cover the names used by the function, the compiler will report an error and this step can be rolled back and the previous step can be repeated to cover what was missed. Qualifications in the body of the function can be removed at this point, if desired, since the compiler will complain if this introduces an ambiguity from two different interfaces using that name. It would be reasonable to leave the qualifications in if the type parameter has multiple interface constraints, both as documentation for readers and to protect against future name collisions if the interfaces are changed. ### Validity can depend on value A templated parameter may be used in ways where the validity of the result depends on the value of the parameter, not just its type. As an example, whether two array types are compatible depends on whether they have the same size. With a symbolic constant sizes, they will only be considered equal if the compiler can show that the two sizes are always equal symbolically. If the size is a template parameter, the checking will be delayed until the value of the template parameter is known. ### Template dependent Expressions fall under three categories: - Expressions that are valid and have meaning determined without knowing the value of any template parameter are _not template dependent_. - Expressions whose meaning and validity requires knowing the value of a template parameter are _template dependent_. Template dependent expressions are not fully type checked until the template is instantiated, which can result in monomorphization errors. Further, template dependent subexpressions commonly cause a containing expression to also be dependent, as described in the ["use of dependent value is dependent" section](#use-of-dependent-value-is-dependent). - Expressions that have a meaning without knowing the value of any template parameter, assuming it is valid, but whose validity requires knowing the value of a template parameter are _template validity dependent_. These expressions can trigger a monomorphization error, but are not considered template dependent for purposes of a containing expression. The compiler will type check expressions that are not template dependent when the function is defined, and they won't trigger monomorphization errors. Note that an expression may not be template dependent even though it has a template-dependent sub-expression. For example, a function may have a value that is function dependent, but calling that function only needs the type of the function (meaning the function's signature) to not be template dependent. #### Simple member access There are three cases when performing unqualified member-name lookup into a templated type: ```carbon fn F[template T:! I](x: T) { x.G(); } ``` - If generic name lookup would succeed, in this example it would be because `G` is a member of `I`, then the result of name lookup is template validity dependent. This means that template instantiation may fail if `T` has a member `G` different than `T.(I.G)`. Assuming it succeeds, though, it will definitely have meaning determined by `I.G`. There may still be ambiguity making the result dependent if it is not known whether `x` is a type and `I.G` is a method and so has an implicit `me` parameter. - If the member name is not found in the constraint, lookup may still succeed once the type is known, so the result is template dependent. - If the lookup is ambiguous prior to knowing the value of the type, for example if `G` has two distinct meanings in `I`, then the code is invalid. The value of the expression will be dependent. For example, if `U` is an associated type of `I`, then `T.U` as an expression is template validity dependent, but the value of that expression is dependent. The value is not always needed to perform checking, for example `x.G()` can be checked without ever determining the value of `x.G` as long as its signature can be determined, if it is valid. #### Compound member access Adding qualifier to the member name, as in `x.(U.V)`, can make the lookup less dependent on the template parameter: - If `x` is dependent, and `U` is an interface, the value of the expression is dependent, but the type of the expression is not dependent unless the type of `U.V` involves `Self`. The lookup itself follows proposal [#2360](https://github.com/carbon-language/carbon-lang/pull/2360): - If `U.V` is an _instance_ member, and the type of `x` is known to implement `U`, then the lookup is not dependent. For example, there could be a requirement on `x` or a sufficiently general implementation of `U` that includes all possible types of `x`. The resulting value is dependent unless the implementation of `U` is `final`, see [the impl lookup section](#impl-lookup). - Otherwise, the lookup is template validity dependent. ```carbon interface Serializable { fn Serialize[me: Self](); } interface Printable { fn Print[me: Self](); } interface Hashable { let HashType:! Type; fn Hash[me: Self]() -> HashType; } external impl forall [T:! Serializable] T as Hashable; fn F[template T:! Serializable](x: T) { // `T` is required to implement `Serializable` and // `Serialize` is an instance member, so this is not // dependent. x.(Serializable.Serialize)(); // Any `T` implementing `Serializable` also implements // `Hashable`, since there is a blanket implementation, // so this is not dependent. Note: there may be a // specialization of this impl, so we can't rely on // knowing how `T` implements `Hashable`. x.(Hashable.Hash)(); // Unclear whether `T` implements `Printable`, but if // does, clear what this means, so this is template // validity dependent x.(Printable.Print)(); match (x.(Hashable.Hash)()) { // Uses the value of the associated type // `Hashable.HashType` that is template dependent. case _: u64 => { ... } default => { ... } } } ``` - If `U.V` is dependent, then the entire expression is dependent. #### Impl lookup If the validity of an expression requires that an impl exist for a type, and that can't be determined until the value of a template parameter is known, then the expression is template validity dependent. For example, in the example from the previous section, `x.(Printable.Print)()` is valid if `T` implements `Printable`. This can also occur without a qualified lookup, for example: ```carbon fn F[T:! Printable](x: T); fn G[template T:! Type](x: T) { // Valid if `T` implements `Printable`, so this // expression is template validity dependent. F(x); } ``` The values of members of an impl for a template-dependent type are template dependent, unless they can be resolved to a not template-dependent expression using checked-generic impl resolution. ``` final external impl [T:! Type] T* as D where .Result = T and .Index = i32; fn F[T:! Type](p: T*) { // `(T*).(D.Index)` uses the final impl of `D` for `T*`, // and so equals `i32`, which is not dependent. // `(T*).(D.Result)` is recognized as equal to `T`, which // is template dependent. } ``` #### Use of dependent value is dependent To match the expectations of C++ templates, uses of dependent values are also template dependent, propagating dependence from subexpressions to enclosing expressions. For example, if `expr` is a dependent expression, each of these is dependent: - `(expr)` - `F(expr)` - `expr + 1` - `if a then expr else b` - `a as expr` In some cases, an expression's type and value category can be determined even when a subexpression is dependent. This makes the expression template validity dependent, rather than dependent. For example, the types of these expressions are not dependent, even when `expr` is a dependent subexpression: - `if expr then a else b` - `expr as T` For `match`, which `case` body is executed may be dependent on the type of the match expression. For example: ``` fn TypeName[template T:! Type](x: T) -> String { match (x) { // Each entire case body is dependent case _: i32 => { return "int"; } case _: bool => { return "bool"; } case _: auto* => { return "pointer"; } // Allowed even though body of case is invalid for // `T != Vector(String)` case _: Vector(String) => { return x.front(); } default => { return "unknown"; } } } ``` ## Rationale This proposal advances these Carbon goals: - [Performance-critical software](/docs/project/goals.md#performance-critical-software), by providing an alternative to checked generics that has greater access to the specific value of the parameter. - [Code that is easy to read, understand, and write](/docs/project/goals.md#code-that-is-easy-to-read-understand-and-write) by specifically marking code that is using features that should receive greater scruitiny. - [Interoperability with and migration from existing C++ code](/docs/project/goals.md#interoperability-with-and-migration-from-existing-c-code), specifically migrating C++ code using templates, as detailed in the ["transition from C++ templates to Carbon checked generics" section](#transition-from-c-templates-to-carbon-checked-generics). ## Alternatives considered ### Only checked generics Like Rust, Carbon could use only checked generics and not support templates. The reasons for this approach are detailed in the ["problem" section](#problem). ### SFINAE We could use the [SFINAE rule](#terminology), to match C++. While familiar, it prevents the compiler from being able to distinguish between "this code is not meant for this case" from "this code has an error." The goal of eliminating SFINAE is to get away from the verbose and unclear errors that templates are infamous for. C++ itself, with [concepts](https://en.cppreference.com/w/cpp/language/constraints), is moving toward stating requirements up front to improve the quality of error diagnostics. ### Ad hoc API specialization Consider a type with a template type parameter: ```carbon class Vector(template T:! Type) { fn GetPointer[addr me: Self*](index: i32) -> T*; // ... } ``` To be able to type check a checked generic function using that type: ```carbon fn SetFirst[T:! Type](vec: Vector(T)*, val: T) { let p: T* = vec->GetPointer(0); *p = val; } ``` we need a guarantee that the function signature used to type check the function is correct. This won't in general be true if ad hoc specialization is allowed: ```carbon // ❌ Not legal Carbon, no ad hoc specialization class Vector(bool) { // `let p: T* = vec->GetPointer(0)` won't type check // in `SetFirst` with `T == bool`. fn GetPointer[addr me: Self*](index: i32) -> BitProxy; // ... } ``` Specialization is still important for performance, but Carbon's [existing approach to specialization of parameterized types](/docs/design/generics/details.md#specialization) makes it clear what parts of the signature can vary, and what properties all specializations will have. In this example, `Vector` would have to be declared alongside an interface, and implementations of that interface, as in: ```carbon class Vector(template T:! Type); interface VectorSpecialization { let PointerType: Deref(Self); fn GetPointer(p: Vector(Self)*, index: i32) -> PointerType; } // Blanket implementation provides default when there is // no specialization. impl forall [T:! Type] T as VectorSpecialization where .PointerType = T* { ... } // Specialization for `bool`. impl bool as VectorSpecialization where .PointerType = BitProxy { ... } class Vector(template T:! Type) { // Return type of `GetPointer` varies with `T`, but must // implement `Deref(T)`. fn GetPointer[addr me: Self*](index: i32) -> T.(VectorSpecialization.PointerType) { return T.(VectorSpecialization.GetPointer)(me, index); } // ... } ``` ### Value phase of bindings determined by initializer We considered allowing a `let` binding to result in a name with [constant value phase](#value-phases) if the initializer was a constant, even if it was not declared using the `template` keyword. That would mean that `let x: i32 = 5;` would declare `x` as constant, rather than a runtime value. For non-type values, this would be a strict improvement in usability. With the proposal, there is a choice between writing the concise form `let x: i32 = 5;` and `let template x:! i32 = 5;` that lets the compiler use the value of `x` directly. The `let template` form is both longer and uses `template` which in other contexts might merit closer scrutiny, but is generally either desirable or harmless in this context. The problem is that for type values, changing from a symbolic value to a constant results in a change to the [name lookup](#name-lookup) rules, which is not going to always be desired. This decision was the result of a discussion in open discussions on [2022-09-09](https://docs.google.com/document/d/1tEt4iM6vfcY0O0DG0uOEMIbaXcZXlNREc2ChNiEtn_w/edit#heading=h.g1xcokypbstm). ### Simpler template dependent rules that delayed more checking We considered simpler rules for which expressions were considered [template dependent](#template-dependent), like that any expression involving a template parameter was template dependent. This had the downside that it would have delayed checking of more expressions, and would have resulted in greater differences between template and checked generic semantics. Ultimately we thought that the developer experience would be better if errors were delivered earlier. This was discussed in [open discussion on 2022-10-10](https://discord.com/channels/655572317891461132/941071822756143115/1029411854277165137) and on [Discord #generics-and-templates starting 2022-10-11](https://discord.com/channels/655572317891461132/941071822756143115/1029411854277165137). ## Future work ### Expanded template constraints [Template constraints](#template-constraints) will need to support other kinds of structural constraints. In particular, the kinds of constraints that can be expressed in C++20 Concepts: - [Constraints and concepts (since C++20)](https://en.cppreference.com/w/cpp/language/constraints) - [Requires expression (since C++20)](https://en.cppreference.com/w/cpp/language/requires) This is both to allow the constraints of existing C++ code to be migrated, and because we expect constraints that were found to be useful in C++ will also be useful for Carbon. ### Predicates: constraints on values We will need some mechanism to express that the value of a non-type template parameter meets some criteria. For example, the size parameter of an array must not be less than 0. We are considering a construct called _predicates_ to represent these kinds of constraints, see the question-for-leads issue [#2153: Generics calling templates](https://github.com/carbon-language/carbon-lang/issues/2153). ### Checked generics calling templates For checked generics interoperation with existing templates, and to allow templates to be migrated to checked generics in any order, we want Carbon to support supplying a symbolic constant argument value, such as from a checked generic function, to a function taking a template parameter. One approach that already works is using a template implementation of an interface, as in this example: ```carbon fn TemplateFunction[template T:! Type](x: T) -> T; // `Wrapper` is an interface wrapper around // `TemplateFunction`. interface Wrapper { fn F[me: Self]() -> Self; } external impl forall [template T:! Type] T as Wrapper { fn F[me: Self]() -> Self { TemplateFunction(me); } } // ✅ Allowed: fn CheckedGeneric[T:! Wrapper](z: T) -> T { return z.(Wrapper.F)(); } // ⚠️ Future work, see #2153: fn CheckedGenericDirect[T:! Type](z: T) -> T { return TemplateFunction(z); } ``` More direct interoperation is being considered in question-for-leads issue [#2153: Generics calling templates](https://github.com/carbon-language/carbon-lang/issues/2153). ### Which expressions will be evaluated at compile time The section on [value phases](#value-phases) and the ["value phase of bindings determined by initializer" alternative](#value-phase-of-bindings-determined-by-initializer) still leave open some questions about how value phases interact, and what gets evaluated at compile time. For example, what happens when there is a function call in the initializer of a `let template`, as in: ```carbon let x: i32 = 5; let template Y:! i32 = F(x); ``` Is the function call evaluated at compile time in order to determine a value for `Y`, or is this an error? Does it depend on something about `F`, such as its definition being visible to the caller and being free of side effects? Is this only allowed since the value of `x` can be determined at compile time, even though it is a runtime value, or would the declaration of `x` have to change? If we allow this construction, observe that the parameter to `F` has different value phases when called at compile time compared to run time, which might affect the interpretation of the body of `F`.