Skip to content

Latest commit

 

History

History
1118 lines (918 loc) · 44.1 KB

p2200.md

File metadata and controls

1118 lines (918 loc) · 44.1 KB
Raw

Template generics

Pull request

Table of contents

Abstract

Add template generics, with optional constraints but no 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:

fn Identity[template T:! Type](x: T) -> T {
  return x;
}

Problem

Starting with #24: Generics goals, 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.

Background

Templates are the mechanism for performing generic programming in C++, see cppreference.com.

There have been a number of prior proposals and questions-for-leads issues on template generics on which this proposal builds:

TODO: Update if proposal #2188: Pattern matching syntax and semantics 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++, but is different from "dependent types". The specifics of how this works in Carbon are being proposed in a later section.
  • Instantiation, substitution, or monomorphizaton 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, wikipedia. 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.
  • 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 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<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.
  • Constraints on a Carbon template type affect how lookup is done into that type, as described in proposal #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:

// `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:

// `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.

// ❌ 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.

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. This terminology comes from a discussion in #typesystem on Discord, in particular this message.

Note: This reflects the resolution of question-for-leads issue #1371: Is let referentially transparent? 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 in addition to #1371: Is let referentially transparent?.

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.

auto

The auto keyword is a shortcut for an unnamed templated type, as in:

// 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 and further specified by open proposal #2188: Pattern matching syntax and semantics.

The auto keyword may also be used to omit the return type, as specified in #826: Function return type inference.

The semantics of let x:! auto = ... is the subject of open question-for-leads issue #996: Generic let with auto?.

Template constraints

Template constraints have already been introduced in proposal #818: Constraints for generics. 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.

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.

Structural constraints do not affect name lookup into template type parameters. They guarantee that a name will be available in the type, but don't change the outcome.

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. 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:

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 and defining a way to put constraints on values are both future work.

Name lookup

Name lookup for templates has already been decided in question-for-leads issue #949: Constrained template name lookup and proposal #989: Member access expressions. 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:

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:

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 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 can be converted to template generic parameters with the equivalent type, as in:

// This C++ function:
void F_CPlusPlus<int N>();

// 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.

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, which is not expected to introduce silent changes in meaning.
  • The C++ code could rely on SFINAE. C++ uses of std::enable_if should be translated to equivalent 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 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:

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.

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:

// ...
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:

// 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 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.
  • 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:

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:

    • 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.
    • Otherwise, the lookup is template validity dependent.
    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:

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:

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.

SFINAE

We could use the SFINAE rule, 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, 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:

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:

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:

// ❌ 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 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:

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 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 rules, which is not going to always be desired.

This decision was the result of a discussion in open discussions on 2022-09-09.

Simpler template dependent rules that delayed more checking

We considered simpler rules for which expressions were considered 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 and on Discord #generics-and-templates starting 2022-10-11.

Future work

Expanded 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:

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.

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:

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.

Which expressions will be evaluated at compile time

The section on value phases and the "value phase of bindings determined by initializer" alternative 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:

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.