The Why and the How (Part 1) (original) (raw)

Definition Checked Generics

Chandler Carruth

Josh Levenberg
Richard Smith

CppNow 2023

The why of checked generics

What are checked generics?

• Fully type-checking the generic definition

or

• A finite set of constraints on the generic parameters that are both necessary_and sufficient_ to guarantee successful instantiation.

Let’s start with C++20 constrained templates

C++20 constrained templates use concepts

• Fundamentally based around assertions of expression validity
  • The expressions, as given, must be valid
• Doesn’t specify their semantics when valid
• Still rely on instantiation for semantics
  • That’s when we can fully type check

Let’s try to definition check with these

template<typename D>
concept Display = requires(D &d, std::string_view sv) {
  `<1>d.Show(sv)`;
};

template<Display D> void hello(D &d) {
  `<2>d.Show("Hello, world!"sv)`;
}

template<typename D>
concept Display = requires(D &d, std::string_view sv) {
  d.Show(sv);
};

template<Display D> void hello(D &d, std::string name = "world") {
  d.Show("Hello, " + name + "!");
}

struct FormattedText {
  FormattedText(std::string_view);
};
struct MyDisplay {
  void Show(FormattedText text);
};
void test(MyDisplay &d, std::string_view sv) {
  // ✅: This is fine, so concept is satisfied!
  d.Show(sv);
  // ❌: This doesn't work though!
  hello(d);
}

template<typename T> struct ConvertsTo {
  operator T();
};
template<typename D>
concept Display = requires(D &d, std::string_view sv1,
                           ConvertsTo<std::string_view> sv2) {
  `<1>d.Show(sv1)`;
  `<0>d.Show(sv2)`;
};

template<typename T> struct ConvertsTo {
  operator T();
};
template<typename D>
concept Display = requires(D &d, std::string_view sv1,
                           ConvertsTo<std::string_view> sv2,
                           `<2>const std::string_view sv3`) {
  d.Show(sv1);
  d.Show(sv2);
  `<1>d.Show(std::move(sv1))`;
  `<2>d.Show(sv3)`;
  `<3>d.Show(std::move(sv3))`;
};

`<4>int` `<3>ScaleTime`(int time);
double ScaleTime(float time);
double ScaleTime(double time);
void RecordTime(`<5>double &time`);


template<Display D> void hello(D &d, std::string name = "world") {
  `<4>auto` time = `<3>ScaleTime`(d.Show("Hello, " + name + "!"));
  RecordTime(`<5>time`);
}

struct BadDisplay {
  `<2>double` Show(std::string_view);

  // Custom version.
  `<2>int` Show(`<1>std::string`);
};

Definition checking C++20 concepts is infeasible, not impossible

• Requires building up a set of expression validity tests that fully subsume every step of type checking the definition
• Essentially, an observational record of the result of type checking
• In essence, builds a new type system in the constraint
  • But rather than expressed directly, expressed through indirect assertions that must cover every case

😞

Why is type checking generic definitions useful?

Better error messages?

Better error messages?

Example from the original Concepts Lite paper:

list<int> lst = ...;
sort(lst); // Error

error: no matching function for call to ‘sort(list<int>&)’
   sort(l);
         ^
note: candidate is:
note: template<Sortable T> void sort(T)
   void sort(T t) { }
        ^
note: template constraints not satisfied because
note:   ‘T’ is not a/an ‘Sortable’ type [with T = list<int>] since
note:     ‘declval<T>()[n]’ is not valid syntax

Better error messages?

Mostly covered by C++20 concepts

• Concrete outline of how to use concepts: https://wg21.link/p2429
• Important benefit is diagnosing a failed constraint, which works
• Many other aspects of error messages important to improve

Lots more to do on error messages,

but definition checking isn’t crucial there

Definition checking helps you get the errors

Changes how to develop generic code

• Zero gaps – if the definition type checks, it’s right
  • No action-at-a-distance or surprise breakage for users of a template
  • Enables substantially more aggressive evolution of generic code
• No futile attempt to cover every instantiation in unit tests
  • Or updating the endless tests when you change something

Is static typing useful?

IMO, yes: shifting-left & large-scale refactoring

Checked generics give static typing benefits

for large-scale generic software.

Complete definition checking unlocks type erasure

Type erasure is a powerful missing abstractions

• C++ dynamic dispatch tools don’t address the needs:
  • Inheritance is a closed extension space, not open
  • Inheritance creates composition problems with diamond dependencies
• Templates can compose and are an open extension space
  • But they don’t form a meaningful abstraction boundary

Type-checked definitions also improve implementation options

• Avoid repeated type checking during instantiation
• Avoid silently generating ODR-violations
• Reduce (but not eliminate) the generation duplicated code

Checked generics can also improve the foundations of the language

What do checked generics look like in practice?

Generic means “parameterized”

• Includes template generics and checked generics
• Generic parameters are supplied at compile time
• Often the parameters are types, or can only be types

For comparison, what do template generics with C++20 concepts look like?

C++ example: defining a concept

#include <concepts>

template<typename T>
concept `RNGConcept` = requires(T a) {
    { `a.random()` } -> std::same_as<typename `T::result_t`>;
};

class BaseRNGClass { ... };

class FancyRNG : public BaseRNGClass {
 public:
  typedef double result_t;
  auto random() -> double { ... }
};

template<RNGConcept T>
auto GenericFunction(T r) -> T::result_t {
  return r.random();
}

auto CallsGeneric(FancyRNG r) -> double {
  return GenericFunction(r);
}

C++ example: a type implementing the concept

#include <concepts>

template<typename T>
concept RNGConcept = requires(T a) {
    { a.random() } -> std::same_as<typename T::result_t>;
};

class BaseRNGClass { ... };

class FancyRNG : public BaseRNGClass {
 public:
  `<1>typedef double result_t`;
  auto `<0>random() -> double` { ... }
};

template<RNGConcept T>
auto GenericFunction(T r) -> T::result_t {
  return r.random();
}

auto CallsGeneric(FancyRNG r) -> double {
  return GenericFunction(r);
}

C++ example: a generic function

#include <concepts>

template<typename T>
concept RNGConcept = requires(T a) {
    { a.random() } -> std::same_as<typename T::result_t>;
};

class BaseRNGClass { ... };

class FancyRNG : public BaseRNGClass {
 public:
  typedef double result_t;
  auto random() -> double { ... }
};

template<`<1>RNGConcept` T>
auto `<0>GenericFunction(T r)` -> T::result_t {
  return r.random();
}

auto CallsGeneric(FancyRNG r) -> double {
  return GenericFunction(r);
}

C++ example: calling a generic function

#include <concepts>

template<typename T>
concept RNGConcept = requires(T a) {
    { a.random() } -> std::same_as<typename T::result_t>;
};

class BaseRNGClass { ... };

class FancyRNG : public BaseRNGClass {
 public:
  typedef double result_t;
  auto random() -> double { ... }
};

template<RNGConcept T>
auto GenericFunction(T r) -> T::result_t {
  return r.random();
}

auto CallsGeneric(FancyRNG r) -> double {
  return GenericFunction(r);
}

Languages with checked generics are going to have similar facilities

Generic functions

• Generic parameters are used in the signature

template<RNGConcept `<0>T`>
auto GenericFunction(`<0>T` r) -> `<0>T`::result_t {
  return r.random();
}

Generic types

• Often the generic parameters are listed explicitly when naming the type (vector<int>)
  • Can be deduced, as in the case of C++’sclass template argument deduction (CTAD)
• The generic parameters are used in the method signatures and field types

Checked generic means the parameters are constrained

template<`RNGConcept` T>
auto GenericFunction(T r) -> T::result_t {
  return r.random();
}

• Can have constraints without fully typechecking
  • C++20 concepts
  • The constraints define the minimum provided by the caller
• But can’t have typechecking without the constraints
  • The constraints define the maximum the callee can rely on
  • Using anything else is a type error in the definition

Interfaces

The building blocks of constraints

template<typename T>
concept RNGConcept = requires(T a) {
    { a.random() } -> std::same_as<typename T::result_t>;
};

• Two approaches: structural and nominal

Structural interfaces

If you have these methods, with these signatures, then you satisfy this interface

• C++ concepts are an extreme version of structural
  • specified code has to somehow be valid

Nominal interfaces

There is an explicit statement – by name – that a type satisfies a requirement

• In C++, inheriting from a base class works nominally. A class having the methods of another class is not enough to cast a pointer between the two types.
• In some languages, the implementation of an interface for a type is a separate definition.

Associated types

#include <concepts>

template<typename T>
concept RNGConcept = requires(T a) {
    { a.random() } -> std::same_as<typename `<0>T::result_t`>;
};

class BaseRNGClass { ... };

class FancyRNG : public BaseRNGClass {
 public:
  typedef double `<0>result_t`;
  auto random() -> double { ... }
};

Associated types

• Associated types are types that an interface implementation must define

  • for example: value_type and iterator of C++ containers
  • allow the signature of methods in the interface to vary

• Associated types have their own constraints

  • If the iterator associated type has constraint ForwardIterator, then a generic function using an iterator can only use the methods ofForwardIterator
  • A generic function might only accept containers if the associated typevalue_type is String, or if it implements Printable

Generic interfaces

Some languages allow interfaces to be parameterized as well

template<typename T, `typename U`>
concept Pow = requires(T a, U b) {
    { a.pow(b) } -> std::same_as<typename T::result_t>;
};

template<Pow`<int>` T>
auto GenericFunction(T r) -> T::result_t {
  return r.pow(2);
}

Generic interfaces

• Some languages allow interfaces to be parameterized as well
  • Pow<T>: type can be raised to a power of type T
  • very useful for representing operator overloading
• Allows a type to implement an interface multiple times
  • Pow<unsigned> and Pow<float> are different
• Interface parameters are inputs
  • they have to be specified when naming an interface
• Associated types are outputs
  • they are determined by the implementation selected

Hold on, there were two inputs

template<`<0>typename T`, typename U>
concept Pow = requires(`<0>T a`, U b) {
    { a.pow(b) } -> std::same_as<typename T::result_t>;
};

• The first input type parameter is often called the Self type, and is often implicit
• Gives expressivity beyond pure inheritance

Generic implementations

• This family of types implements this interface
• Or this interface with a range of arguments
• Can express language mechanisms that are often hard-coded in languages without generics
  • Simpler, more uniform
• Some languages, such as C++ support specialization
  • When two implementations apply, use the more specific one
  • More about specialization in part 2

What do checked generics look like?

• in Swift
• in Rust
• in Carbon

Reminder: C++20 concepts

C++20 concepts are only constraints on the caller

• So templated function bodies are not “checked” until they are called
• Can be used to select between overloads

C++20 concepts are generally structural

• Types “satisfy” a concept if
  • certain expressions are valid, or
  • valid and have a specified type
• A fit for there being multiple ways to make something valid
  • Example: operators (or begin/end) can be overloaded with methods or free functions
• Support for specialization
  • “Ad hoc”: nothing enforces that a specialization has the same API

However subsumption is nominal

• Can only say this concept implies another concept if there is a direct, named dependency
• It is too hard to say whether “this expression is valid” implies “that expression is valid”

C++ example: defining a concept

#include <concepts>

template<typename T>
concept RNGConcept = requires(T a) {
    { a.random() } -> std::same_as<typename T::result_t>;
};

class BaseRNGClass { ... };

class FancyRNG : public BaseRNGClass {
 public:
  typedef double result_t;
  auto random() -> double { ... }
};

template<RNGConcept T>
auto GenericFunction(T r) -> T::result_t {
  return r.random();
}

C++ example: a type implementing the concept

#include <concepts>

template<typename T>
concept RNGConcept = requires(T a) {
    { a.random() } -> std::same_as<typename T::result_t>;
};

class BaseRNGClass { ... };

class FancyRNG `<1>: public BaseRNGClass` {
 public:
  typedef double result_t;
  `<0>auto random() -> double` { ... }
};

template<RNGConcept T>
auto GenericFunction(T r) -> T::result_t {
  return r.random();
}

C++ example: a generic function

#include <concepts>

template<typename T>
concept RNGConcept = requires(T a) {
    { a.random() } -> std::same_as<typename T::result_t>;
};

class BaseRNGClass { ... };

class FancyRNG : public BaseRNGClass {
 public:
  typedef double result_t;
  auto random() -> double { ... }
};

template<`RNGConcept` `T`>
auto GenericFunction(`T r`) -> T::result_t {
  return r.random();
}

Swift

Swift example: defining a protocol

protocol RNGProtocol {
  `associatedtype Result`
  `mutating func random() -> Result`
}

class BaseRNGClass { ... }

class FancyRNG: BaseRNGClass, RNGProtocol {
  func random() -> Double { ... }
}

func GenericFunction<T: RNGProtocol>(_ r: inout T) -> T.Result {
  return r.random()
}

Swift example: a type conforming to a protocol

protocol `<0>RNGProtocol` {
  associatedtype Result
  mutating func `<2>random`() -> `<3>Result`
}

class `<1>BaseRNGClass` { ... }

class FancyRNG: `<1>BaseRNGClass`, `<0>RNGProtocol` {
  func `<2>random`() -> `<3>Double` { ... }
}

func GenericFunction<T: RNGProtocol>(_ r: inout T) -> T.Result {
  return r.random()
}

Swift example: a generic function

protocol RNGProtocol {
  associatedtype Result
  mutating func random() -> Result
}

class BaseRNGClass { ... }

class FancyRNG: BaseRNGClass, RNGProtocol {
  func random() -> Double { ... }
}

func GenericFunction<`T`: `RNGProtocol`>(_ r: inout T) -> `T.Result` {
  return r.random()
}

Some things Swift does not (yet) do

• Checked generic variadics are a work in progress
• No specialization
• No parameterization of protocols
• No overlapping conformances
• No non-type generic parameters

Rust

Rust example: defining a trait

pub trait RNGTrait {
  `type Result;`
  `fn random(&mut self) -> Self::Result;`
}

pub struct BaseRNG { ... }

pub struct FancyRNG {
  base: BaseRNG,  // no inheritance
}
impl RNGTrait for FancyRNG {
  type Result = f64;
  fn random(&mut self) -> f64 { ... }
}

fn generic_function<T: RNGTrait>(r: &mut T) -> T::Result {
  return r.random();
}

Rust example: a type implementing to a trait

pub trait RNGTrait {
  type Result;
  fn random(&mut self) -> Self::Result;
}

pub struct BaseRNG { ... }

pub struct FancyRNG {
  base: BaseRNG,  // no inheritance
}
`impl RNGTrait for FancyRNG` {
  type Result = f64;
  `fn random(&mut self) -> f64` { ... }
}

fn generic_function<T: RNGTrait>(r: &mut T) -> T::Result {
  return r.random();
}

Rust example: a generic function

pub trait RNGTrait {
  type Result;
  fn random(&mut self) -> Self::Result;
}

pub struct BaseRNG { ... }

pub struct FancyRNG {
  base: BaseRNG,  // no inheritance
}
impl RNGTrait for FancyRNG {
  type Result = f64;
  fn random(&mut self) -> f64 { ... }
}

fn generic_function<`T: RNGTrait`>(r: &mut T) -> `T::Result` {
  return r.random();
}

Rust has been adding some advanced features

Recent releases have added support for:

• generic associated types
• non-type parameters
  • called “const generics” in Rust

Some things Rust does not do

• Variadics only through macros
  • Draft RFC: variadic generics #376, last comment Apr 30, 2021:

    There’s been several attempts over the years and it doesn’t seem like it’s going to happen again any time soon, sorry.

• Specialization desired, but hard to land due to legacy

Carbon

Carbon example: defining an interface

interface RNGInterface {
  `let Result: type;`
  `fn Random[addr self: Self*]() -> Result;`
}

class BaseRNGClass { ... }

class FancyRNG {
  extend base: BaseRNGClass;
  extend impl as RNGInterface where .Result = f64 {
    fn Random[addr self: Self*]() -> f64 { ... }
  }
}

fn GenericFunction[T:! RNGInterface](r: T*) -> T.Result {
  return r->Random();
}

Carbon example: implementing an interface

interface RNGInterface {
  let Result: type;
  fn Random[addr self: Self*]() -> Result;
}

class BaseRNGClass { ... }

class FancyRNG {
  `<1>extend` `<2>base: BaseRNGClass`;
  `<1>extend` `<0>impl as RNGInterface` where .Result = f64 {
    `<3>fn Random[addr self: Self*]() -> f64` { ... }
  }
}

fn GenericFunction[T:! RNGInterface](r: T*) -> T.Result {
  return r->Random();
}

Carbon example: generic function

interface RNGInterface {
  let Result: type;
  fn Random[addr self: Self*]() -> Result;
}

class BaseRNGClass { ... }

class FancyRNG {
  extend base: BaseRNGClass;
  extend impl as RNGInterface where .Result = f64 {
    fn Random[addr self: Self*]() -> f64 { ... }
  }
}

fn GenericFunction`[T:! RNGInterface]``(r: T*)` -> T.Result {
  return r->Random();
}

Carbon example: generic function

interface RNGInterface {
  let Result: type;
  fn Random[addr self: Self*]() -> Result;
}

class BaseRNGClass { ... }

class FancyRNG {
  extend base: BaseRNGClass;
  extend impl as RNGInterface where .Result = f64 {
    fn Random[addr self: Self*]() -> f64 { ... }
  }
}

fn GenericFunction[T`:!` RNGInterface](r: T*) -> `T.Result` {
  return r->Random();
}

Carbon

• Supports checked and template generics

  • Checked generics use nominal “interfaces”
  • Template generics work like C++ templates
  • Template generics may be constrained
  • They can call each other

• Supports interface implementation specialization from the start

• Supports checked-generic variadics

• Is new! Everything is a work in progress

  • benefiting from the experience of other languages

Better language foundations with checked generics

Unified and powerful customization points

What are customization points?

class MyComplex { ... };

MyComplex `operator+`(MyComplex, MyComplex) { ... }
void `swap`(MyComplex, MyComplex) { ... }

void f(std::vector<MyComplex> vec) {
  // Uses ``operator+`` customization point.
  MyComplex avg = `std::accumulate`(vec.begin(), vec.end(),
                                  MyComplex{})
                  / vec.size();

  // Uses ``swap`` customization point.
  `std::partial_sort`(vec.begin(), vec.end(),
                    [&](MyComplex c) {
                      return c.real() < avg.real();
                    });
}

Long, complex history trying to get this right

• ADL (Argument Dependent Lookup) of operators
• Class template specialization
• ADL-found functions with the weird using trick
• Customization Point Objects
• tag_invoke
• …

Many WG21 papers here, but can start with: http://wg21.link/p2279

Checked generics solve these problems

Operator overloading

interface `MulWith`(`U:! type`) {
  `let Result:! type` `= Self`;
  fn `Op`[self: Self](rhs: U) -> Result;
}

class Point {
  var x: f64;
  var y: f64;

  impl as MulWith(f64) where .Result = Point {
    fn Op[self: Self](scale: f64) -> Point {
      return {.x = self.x * scale, .y = self.y * scale};
    }
  }
}

fn Double(p: Point) -> auto {
  let scale: f64 = 2.0;
  return p * scale;
  // => p.(MulWith(typeof(scale)).Op)(scale)
  // => p.(MulWith(f64).Op)(scale)
}

Operator overloading

interface MulWith(U:! type) {
  let Result:! type = Self;
  fn Op[self: Self](rhs: U) -> Result;
}

class `Point` {
  var x: f64;
  var y: f64;

  `impl as MulWith(f64)` where .Result = Point {
    fn Op[self: Self](scale: f64) -> Point {
      return {.x = self.x * scale, .y = self.y * scale};
    }
  }
}

fn Double(p: Point) -> auto {
  let scale: f64 = 2.0;
  return p * scale;
  // => p.(MulWith(typeof(scale)).Op)(scale)
  // => p.(MulWith(f64).Op)(scale)
}

Operator overloading

interface MulWith(U:! type) {
  let Result:! type = Self;
  fn Op[self: Self](rhs: U) -> Result;
}

class Point {
  var x: f64;
  var y: f64;

  impl as MulWith(f64) `where .Result = Point` {
    fn Op[self: Self](scale: f64) -> Point {
      `return {.x = self.x * scale, .y = self.y * scale};`
    }
  }
}

fn Double(p: Point) -> auto {
  let scale: f64 = 2.0;
  return p * scale;
  // => p.(MulWith(typeof(scale)).Op)(scale)
  // => p.(MulWith(f64).Op)(scale)
}

Operator overloading

interface MulWith(U:! type) {
  let Result:! type = Self;
  fn Op[self: Self](rhs: U) -> Result;
}

class Point {
  var x: f64;
  var y: f64;

  impl as MulWith(f64) where .Result = Point {
    fn Op[self: Self](scale: f64) -> Point {
      return {.x = self.x * scale, .y = self.y * scale};
    }
  }
}

fn Double(p: Point) -> auto {
  let scale: f64 = 2.0;
  return `p * scale`;
  // => `p.(MulWith(typeof(scale)).Op)(scale)`
  // => p.(MulWith(f64).Op)(scale)
}

Operator overloading

interface MulWith(U:! type) {
  let Result:! type = Self;
  fn Op[self: Self](rhs: U) -> Result;
}

class Point {
  var x: f64;
  var y: f64;

  impl as MulWith(f64) where .Result = `<5>Point` {
    fn `<2>Op`[self: Self](scale: f64) -> Point {
      return {.x = self.x * scale, .y = self.y * scale};
    }
  }
}

fn Double(p: Point) -> `<5>auto` {
  let scale: f64 = 2.0;
  return p * `<1>scale`;
  // => p.(MulWith(`<1>typeof(scale)`).Op)(scale)
  // => `<3>p`.(`<2>MulWith(f64).Op`)(`<4>scale`)
}

Customizations with higher-level semantics

choice Ordering {
  Less,
  Equivalent,
  Greater,
  Incomparable
}

interface OrderedWith(U:! type) {
  fn Compare[self: Self](u: U) -> Ordering;
}

fn StringLess(s1: String, s2: String) -> bool {
  return s1 < s2;
  // => s1.(OrderedWith(String).Compare)(s2) == Less
}

fn StringGreater(s1: String, s2: String) -> bool {
  return s1 > s2;
  // => s1.(OrderedWith(String).Compare)(s2) == Greater
}

Customizations with higher-level semantics

choice Ordering {
  Less,
  Equivalent,
  Greater,
  Incomparable
}

interface OrderedWith(U:! type) {
  fn Compare[self: Self](u: U) -> Ordering;
}

fn StringLess(s1: String, s2: String) -> bool {
  return s1 `<2><` s2;
  // => `<1>s1.(OrderedWith(String).Compare)(s2)` `<2>== Less`
}

fn StringGreater(s1: String, s2: String) -> bool {
  return s1 `<3>>` s2;
  // => `<1>s1.(OrderedWith(String).Compare)(s2)` `<3>== Greater`
}

Note: Carbon actually supports deeper customization, motivated by C++ interop

Incrementally extending & specializing customization points

interface OrderedWith(U:! type) {
  fn Compare[self: Self](u: U) -> Ordering;

  default fn Less[self: Self](u: U) -> bool {
    return self.Compare(u) == Ordering.Less;
  }
  default fn LessOrEquivalent[self: Self](u: U) -> bool {
    let c: Ordering = self.Compare(u);
    return c == Ordering.Less or c == Ordering.Equivalent;
  }

  default fn Greater[self: Self](u: U) -> bool {
    return self.Compare(u) == Ordering.Greater;
  }
  default fn GreaterOrEquivalent[self: Self](u: U) -> bool {
    let c: Ordering = self.Compare(u);
    return c == Ordering.Greater or c == Ordering.Equivalent;
  }
}

Incrementally extending & specializing customization points

interface OrderedWith(U:! type) {
  fn Compare[self: Self](u: U) -> Ordering;

  `<2>default` fn `<1>Less`[self: Self](u: U) -> bool {
    `<3>return self.Compare(u) == Ordering.Less;`
  }
  default fn LessOrEquivalent[self: Self](u: U) -> bool {
    let c: Ordering = self.Compare(u);
    return c == Ordering.Less or c == Ordering.Equivalent;
  }

  default fn Greater[self: Self](u: U) -> bool {
    return self.Compare(u) == Ordering.Greater;
  }
  default fn GreaterOrEquivalent[self: Self](u: U) -> bool {
    let c: Ordering = self.Compare(u);
    return c == Ordering.Greater or c == Ordering.Equivalent;
  }
}

Conditional, generic customization points

interface `Printable` {
  fn `Print`[self: Self]();
}

class `Vector(template T:! type)` { ... }

impl `forall` [`T`:! `Printable`] `Vector(T)` as Printable {
  fn Print[self: Self]() {
    var first: bool = true;
    for (elem: `T` in self) {
      if (not first) { ", ".Print(); }
      `elem.Print()`;
      first = false;
    }
  }
}

Implicit conversions with customization points

Explicit conversion customization point

interface `As`(`Dest:! type`) {
  fn `Convert`[self: Self]() -> `Dest`;
}

`impl String as As`(`Path`) {
  fn Convert[self: String]() -> Path {
    return `Path.FromString`(self);
  }
}

let config_file: Path = `"/etc/myutil.cfg" as Path`;
//                      => ("/etc/myutil.cfg").(`As(Path)`.`Convert`)()

Implicit conversion customization point

interface `ImplicitAs`(Dest:! type) {
  `extends As(Dest)`;
  // Inherited from As(Dest):
  // fn `Convert`[self: Self]() -> Dest;
}

impl `String as ImplicitAs(StringView)` {
  fn Convert[self: String]() -> StringView {
    return StringView::Make(self.Data(), self.Data() + self.Size());
  }
}

fn Greet(s: StringView) { Print("Hello, {0}", s); }

fn Main() -> i32 {
  `Greet`(`"audience"`);
  // => Greet(("audience").(`ImplicitAs(StringView)`.`Convert`)()
  return 0;
}

Implicit conversion conditional defaults

impl `forall` [`U:! type`, `T:! As(U)`]
     `Optional(T)` as `As(Optional(U))`;

impl forall [U:! type, T:! `ImplicitAs(U)`]
     Optional(T) as ImplicitAs(Optional(U));

impl forall [T:! type]
     `NullOpt` as `ImplicitAs(Optional(T))`;

Fundamentally more expressive customization

This works! ✅

class `Base` {};
class `Derived` : public Base {};

void Test(`Base *b`);

void Example(bool condition) {
  `Base b`;
  `Derived d`;


  // ✅
  Test(`condition ? &b : &d`);


  //...
}

This works in either direction! ✅

class Base {};
class Derived : public Base {};

void Test(Base *b);

void Example(bool condition) {
  Base b;
  Derived d;


  // ✅✅
  Test(condition ? &b : &d);
  Test(`condition ? &d : &b`);


  //...
}

But does this? 😞

class Base {};
class `DerivedA` : public Base {};
class `DerivedB` : public Base {};
void Test(Base *b);

void Example(bool condition) {
  Base b;
  `DerivedA da`;
  `DerivedB db`;

  // ✅✅
  Test(condition ? &b : &db);
  Test(condition ? &da : &b);

  // ???
  Test(`condition ? &da : &db`);

  //...
}

❌ error: incompatible operand types (DerivedA * and DerivedB *)

We can make this easy in Carbon

interface `CommonTypeWith`(`U:! type`) {
  `let Result:! type`
    `where` `Self impls ImplicitAs`(`.Self`) and
          `U impls ImplicitAs`(`.Self`);
}

class `InternedString` { ... }
impl `InternedString` as `CommonTypeWith(String)`
  where `.Result = StringView` {}

fn SelectString(condition: bool, s: String, i: InternedString) -> StringView {
  // Carbon version of ``... ? ... : ...`` in C++:
  return `if condition then s else i`;
}

Customizable CommonType opens even more doors

fn SelectLongString(s: String, i: InternedString, v: StringView) -> `auto` {
  if (s.Size() > 20) {
    `return s`;
  } else if (i.Size() > 20) {
    `return i`;
  } else {
    `return v`;
  }
}

Checked generics build better language foundations

These better foundations make generics better!

Foundations built with checked generics

become available within checked generics

Operator overloads in checked generic code

interface MulWith(U:! type) {
  let Result:! type = Self;
  fn Op[self: Self](rhs: U) -> Result;
}

class Point {
  var x: f64;
  var y: f64;
  impl as MulWith(f64) where .Result = Point {
    fn Op[self: Self](scale: f64) -> Point;
  }
}

fn Double(p: Point) -> auto {
  let scale: f64 = 2.0;
  return p * scale;
  // => p.(MulWith(f64).Op)(scale)
}

fn GenericDouble[T:! MulWith(f64)](x: T) -> auto {
  let scale: f64 = 2.0;
  return x * scale;
  // => p.(MulWith(f64).Op)(scale)
}

Operator overloads in checked generic code

interface MulWith(U:! type) {
  let Result:! type = Self;
  fn Op[self: Self](rhs: U) -> Result;
}

class Point {
  var x: f64;
  var y: f64;
  impl as MulWith(f64) where .Result = Point {
    fn Op[self: Self](scale: f64) -> Point;
  }
}

fn Double(p: Point) -> auto {
  let scale: f64 = 2.0;
  return p * scale;
  // => p.(MulWith(f64).Op)(scale)
}

fn GenericDouble[`T:! MulWith(f64)`](`x: T`) -> auto {
  let scale: f64 = 2.0;
  return `x * scale`;
  // => p.(MulWith(f64).Op)(scale)
}

Operator overloads in checked generic code

interface MulWith(U:! type) {
  let `<5>Result`:! type = Self;
  fn Op[self: Self](rhs: U) -> `<4>Result`;
}

class Point {
  var x: f64;
  var y: f64;
  impl as MulWith(f64) where .Result = Point {
    fn Op[self: Self](scale: f64) -> Point;
  }
}

fn Double(p: Point) -> auto {
  let scale: f64 = 2.0;
  return p * scale;
  // => p.(MulWith(f64).Op)(scale)
}

fn GenericDouble[T:! `<2>MulWith(f64)`](x: T) -> `<3>auto` {
  let scale: f64 = 2.0;
  return x * scale;
  // => p.(`<1>MulWith(f64)`.Op)(scale)
}

Same pattern provides generic implicit conversions, common types, etc.

Systematically generic language foundations ensure that generic code is just code

Conclusion

Generic programming is better with checking

• Better ergonomics
• More reliably better ergonomics
• Powerful abstraction tool when desired
• Efficient implementation strategies

Entire language is better with foundations built on checked generics

• Better customization mechanics throughout the language
• Language constructs can be more easily customized
• Enables clean interface composition
• Generic programming becomes simpler as the language foundations are integrated
  • Increasingly erases the difference between non-generic and generic code.

Carbon is developing and exploring this area

• What it looks like to build a checked generics system that interoperates with C++?
  • How do we support template generic code?
  • How do we model specialization?
  • How can we more pervasively integrate it into the foundations of the language?
• Hope to share what we learn and our experience
• Also would love to work with anyone interested in contributing to this space

Next up, a break and then part 2:

The how of checked generics

Thank you!