# Language design

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

<!-- toc -->

## Table of contents

-   [Overview](#overview)
    -   [This document is provisional](#this-document-is-provisional)
-   [Hello, Carbon](#hello-carbon)
-   [Code and comments](#code-and-comments)
-   [Build modes](#build-modes)
-   [Types are values](#types-are-values)
-   [Primitive types](#primitive-types)
    -   [`bool`](#bool)
    -   [Integer types](#integer-types)
        -   [Integer literals](#integer-literals)
    -   [Floating-point types](#floating-point-types)
        -   [Floating-point literals](#floating-point-literals)
    -   [String types](#string-types)
        -   [String literals](#string-literals)
-   [Composite types](#composite-types)
    -   [Tuples](#tuples)
    -   [Struct types](#struct-types)
    -   [Pointer types](#pointer-types)
    -   [Arrays and slices](#arrays-and-slices)
-   [Expressions](#expressions)
-   [Declarations, Definitions, and Scopes](#declarations-definitions-and-scopes)
-   [Patterns](#patterns)
    -   [Binding patterns](#binding-patterns)
    -   [Destructuring patterns](#destructuring-patterns)
    -   [Refutable patterns](#refutable-patterns)
-   [Name-binding declarations](#name-binding-declarations)
    -   [Constant `let` declarations](#constant-let-declarations)
    -   [Variable `var` declarations](#variable-var-declarations)
    -   [`auto`](#auto)
-   [Functions](#functions)
    -   [`auto` return type](#auto-return-type)
    -   [Blocks and statements](#blocks-and-statements)
    -   [Assignment statements](#assignment-statements)
    -   [Control flow](#control-flow)
        -   [`if` and `else`](#if-and-else)
        -   [Loops](#loops)
            -   [`while`](#while)
            -   [`for`](#for)
            -   [`break`](#break)
            -   [`continue`](#continue)
        -   [`return`](#return)
            -   [`returned var`](#returned-var)
        -   [`match`](#match)
-   [User-defined types](#user-defined-types)
    -   [Classes](#classes)
        -   [Assignment](#assignment)
        -   [Class functions and factory functions](#class-functions-and-factory-functions)
        -   [Methods](#methods)
        -   [Inheritance](#inheritance)
        -   [Access control](#access-control)
        -   [Destructors](#destructors)
    -   [Choice types](#choice-types)
-   [Names](#names)
    -   [Packages, libraries, namespaces](#packages-libraries-namespaces)
    -   [Legal names](#legal-names)
    -   [Naming conventions](#naming-conventions)
    -   [Aliases](#aliases)
    -   [Name lookup](#name-lookup)
        -   [Name lookup for common types](#name-lookup-for-common-types)
    -   [Name visibility](#name-visibility)
-   [Generics](#generics)
    -   [Checked and template parameters](#checked-and-template-parameters)
    -   [Interfaces and implementations](#interfaces-and-implementations)
    -   [Combining constraints](#combining-constraints)
    -   [Associated types](#associated-types)
    -   [Generic entities](#generic-entities)
        -   [Generic Classes](#generic-classes)
        -   [Generic choice types](#generic-choice-types)
        -   [Generic interfaces](#generic-interfaces)
        -   [Generic implementations](#generic-implementations)
    -   [Other features](#other-features)
    -   [Generic type equality and `observe` declarations](#generic-type-equality-and-observe-declarations)
    -   [Operator overloading](#operator-overloading)
        -   [Common type](#common-type)
-   [Bidirectional interoperability with C/C++](#bidirectional-interoperability-with-cc)
-   [Unfinished tales](#unfinished-tales)
    -   [Safety](#safety)
    -   [Pattern matching as function overload resolution](#pattern-matching-as-function-overload-resolution)
    -   [Lifetime and move semantics](#lifetime-and-move-semantics)
    -   [Metaprogramming](#metaprogramming)
    -   [Execution abstractions](#execution-abstractions)
        -   [Abstract machine and execution model](#abstract-machine-and-execution-model)
        -   [Lambdas](#lambdas)
        -   [Co-routines](#co-routines)

<!-- tocstop -->

## Overview

This documentation describes the design of the Carbon language, and the
rationale for that design. This documentation is an overview of the Carbon
project in its current state, written for the builders of Carbon and for those
interested in learning more about Carbon.

This document is _not_ a complete programming manual, and, nor does it provide
detailed and comprehensive justification for design decisions. These
descriptions are found in linked dedicated designs.

### This document is provisional

This document includes much that is provisional or placeholder. This means that
the syntax used, language rules, standard library, and other aspects of the
design have things that have not been decided through the Carbon process. This
preliminary material fills in gaps until aspects of the design can be filled in.

## Hello, Carbon

Here is a simple function showing some Carbon code:

```carbon
import Console;

// Prints the Fibonacci numbers less than `limit`.
fn Fibonacci(limit: i64) {
  var (a: i64, b: i64) = (0, 1);
  while (a < limit) {
    Console.Print(a, " ");
    let next: i64 = a + b;
    a = b;
    b = next;
  }
  Console.Print("\n");
}
```

Carbon is a language that should feel familiar to C++ and C developers. This
example has familiar constructs like imports, function definitions, typed
arguments, and curly braces.

A few other features that are unlike C or C++ may stand out. First, declarations
start with introducer keywords. `fn` introduces a function declaration, and
`var` introduces a variable declaration. You can also see a _tuple_, a composite
type written as a comma-separated list inside parentheses. Unlike, say, Python,
these types are strongly-typed as well.

## Code and comments

All source code is UTF-8 encoded text. Comments, identifiers, and strings are
allowed to have non-ASCII characters.

```carbon
var résultat: String = "Succès";
```

Comments start with two slashes `//` and go to the end of the line. They are
required to be the only non-whitespace on the line.

```carbon
// Compute an approximation of π
```

> References:
>
> -   [Source files](code_and_name_organization/source_files.md)
> -   [lexical conventions](lexical_conventions)
> -   Proposal
>     [#142: Unicode source files](https://github.com/carbon-language/carbon-lang/pull/142)
> -   Proposal
>     [#198: Comments](https://github.com/carbon-language/carbon-lang/pull/198)

## Build modes

The behavior of the Carbon compiler depends on the _build mode_:

-   In a _development build_, the priority is diagnosing problems and fast build
    time.
-   In a _performance build_, the priority is fastest execution time and lowest
    memory usage.
-   In a _hardened build_, the first priority is safety and second is
    performance.

> References: [Safety strategy](/docs/project/principles/safety_strategy.md)

## Types are values

Expressions compute values in Carbon, and these values are always strongly typed
much like in C++. However, an important difference from C++ is that types are
themselves modeled as values; specifically, compile-time constant values. This
means that the grammar for writing a type is the [expression](#expressions)
grammar. Expressions written where a type is expected must be able to be
evaluated at compile-time and must evaluate to a type value.

## Primitive types

Primitive types fall into the following categories:

-   the boolean type `bool`,
-   signed and unsigned integer types,
-   IEEE-754 floating-point types, and
-   string types.

These are made available through the [prelude](#name-lookup-for-common-types).

> References: [Primitive types](primitive_types.md)

### `bool`

The type `bool` is a boolean type with two possible values: `true` and `false`.
[Comparison expressions](#expressions) produce `bool` values. The condition
arguments in [control-flow statements](#control-flow), like [`if`](#if-and-else)
and [`while`](#while), and
[`if`-`then`-`else` conditional expressions](#expressions) take `bool` values.

### Integer types

The signed-integer type with bit width `N` may be written `Carbon.Int(N)`. For
convenience and brevity, the common power-of-two sizes may be written with an
`i` followed by the size: `i8`, `i16`, `i32`, `i64`, `i128`, or `i256`.
Signed-integer
[overflow](expressions/arithmetic.md#overflow-and-other-error-conditions) is a
programming error:

-   In a development build, overflow will be caught immediately when it happens
    at runtime.
-   In a performance build, the optimizer can assume that such conditions don't
    occur. As a consequence, if they do, the behavior of the program is not
    defined.
-   In a hardened build, overflow does not result in undefined behavior.
    Instead, either the program will be aborted, or the arithmetic will evaluate
    to a mathematically incorrect result, such as a two's complement result or
    zero.

The unsigned-integer types are: `u8`, `u16`, `u32`, `u64`, `u128`, `u256`, and
`Carbon.UInt(N)`. Unsigned integer types wrap around on overflow, we strongly
advise that they are not used except when those semantics are desired. These
types are intended for bit manipulation or modular arithmetic as often found in
[hashing](https://en.wikipedia.org/wiki/Hash_function),
[cryptography](https://en.wikipedia.org/wiki/Cryptography), and
[PRNG](https://en.wikipedia.org/wiki/Pseudorandom_number_generator) use cases.
Values which can never be negative, like sizes, but for which wrapping does not
make sense
[should use signed integer types](/proposals/p1083.md#dont-let-unsigned-arithmetic-wrap).

> References:
>
> -   Question-for-leads issue
>     [#543: pick names for fixed-size integer types](https://github.com/carbon-language/carbon-lang/issues/543)
> -   Proposal
>     [#820: Implicit conversions](https://github.com/carbon-language/carbon-lang/pull/820)
> -   Proposal
>     [#1083: Arithmetic expressions](https://github.com/carbon-language/carbon-lang/pull/1083)

#### Integer literals

Integers may be written in decimal, hexadecimal, or binary:

-   `12345` (decimal)
-   `0x1FE` (hexadecimal)
-   `0b1010` (binary)

Underscores `_` may be used as digit separators, but for decimal and hexadecimal
literals, they can only appear in conventional locations. Numeric literals are
case-sensitive: `0x`, `0b` must be lowercase, whereas hexadecimal digits must be
uppercase. Integer literals never contain a `.`.

Unlike in C++, literals do not have a suffix to indicate their type. Instead,
numeric literals have a type derived from their value, and can be
[implicitly converted](expressions/implicit_conversions.md) to any type that can
represent that value.

> References:
>
> -   [Integer literals](lexical_conventions/numeric_literals.md#integer-literals)
> -   Proposal
>     [#143: Numeric literals](https://github.com/carbon-language/carbon-lang/pull/143)
> -   Proposal
>     [#144: Numeric literal semantics](https://github.com/carbon-language/carbon-lang/pull/144)
> -   Proposal
>     [#820: Implicit conversions](https://github.com/carbon-language/carbon-lang/pull/820)

### Floating-point types

Floating-point types in Carbon have IEEE 754 semantics, use the round-to-nearest
rounding mode, and do not set any floating-point exception state. They are named
with an `f` and the number of bits: `f16`, `f32`, `f64`, and `f128`.
[`BFloat16`](primitive_types.md#bfloat16) is also provided.

> References:
>
> -   Question-for-leads issue
>     [#543: pick names for fixed-size integer types](https://github.com/carbon-language/carbon-lang/issues/543)
> -   Proposal
>     [#820: Implicit conversions](https://github.com/carbon-language/carbon-lang/pull/820)
> -   Proposal
>     [#1083: Arithmetic expressions](https://github.com/carbon-language/carbon-lang/pull/1083)

#### Floating-point literals

Floating-point types along with [user-defined types](#user-defined-types) may
initialized from _real-number literals_. Decimal and hexadecimal real-number
literals are supported:

-   `123.456` (digits on both sides of the `.`)
-   `123.456e789` (optional `+` or `-` after the `e`)
-   `0x1.Ap123` (optional `+` or `-` after the `p`)

Real-number literals always have a period (`.`) and a digit on each side of the
period. When a real-number literal is interpreted as a value of a floating-point
type, its value is the representable real number closest to the value of the
literal. In the case of a tie, the nearest value whose mantissa is even is
selected.

> References:
>
> -   [Real-number literals](lexical_conventions/numeric_literals.md#real-number-literals)
> -   Proposal
>     [#143: Numeric literals](https://github.com/carbon-language/carbon-lang/pull/143)
> -   Proposal
>     [#144: Numeric literal semantics](https://github.com/carbon-language/carbon-lang/pull/144)
> -   Proposal
>     [#820: Implicit conversions](https://github.com/carbon-language/carbon-lang/pull/820)
> -   Proposal
>     [#866: Allow ties in floating literals](https://github.com/carbon-language/carbon-lang/pull/866)

### String types

There are two string types:

-   `String` - a byte sequence treated as containing UTF-8 encoded text.
-   `StringView` - a read-only reference to a byte sequence treated as
    containing UTF-8 encoded text.

#### String literals

String literals may be written on a single line using a double quotation mark
(`"`) at the beginning and end of the string, as in `"example"`.

Multi-line string literals, called _block string literals_, begin and end with
three double quotation marks (`"""`), and may have a file type indicator after
the first `"""`.

```carbon
// Block string literal:
var block: String = """
    The winds grow high; so do your stomachs, lords.
    How irksome is this music to my heart!
    When such strings jar, what hope of harmony?
    I pray, my lords, let me compound this strife.
        -- History of Henry VI, Part II, Act II, Scene 1, W. Shakespeare
    """;
```

The indentation of a block string literal's terminating line is removed from all
preceding lines.

Strings may contain
[escape sequences](lexical_conventions/string_literals.md#escape-sequences)
introduced with a backslash (`\`).
[Raw string literals](lexical_conventions/string_literals.md#raw-string-literals)
are available for representing strings with `\`s and `"`s.

> References:
>
> -   [String literals](lexical_conventions/string_literals.md)
> -   Proposal
>     [#199: String literals](https://github.com/carbon-language/carbon-lang/pull/199)

## Composite types

### Tuples

A tuple is a fixed-size collection of values that can have different types,
where each value is identified by its position in the tuple. An example use of
tuples is to return multiple values from a function:

```carbon
fn DoubleBoth(x: i32, y: i32) -> (i32, i32) {
  return (2 * x, 2 * y);
}
```

Breaking this example apart:

-   The return type is a tuple of two `i32` types.
-   The expression uses tuple syntax to build a tuple of two `i32` values.

Both of these are expressions using the tuple syntax
`(<expression>, <expression>)`. The only difference is the type of the tuple
expression: one is a tuple of types, the other a tuple of values. In other
words, a tuple type is a tuple _of_ types.

The components of a tuple are accessed positionally, so element access uses
subscript syntax, but the index must be a compile-time constant:

```carbon
fn DoubleTuple(x: (i32, i32)) -> (i32, i32) {
  return (2 * x[0], 2 * x[1]);
}
```

Tuple types are
[structural](https://en.wikipedia.org/wiki/Structural_type_system).

> References: [Tuples](tuples.md)

### Struct types

Carbon also has
[structural types](https://en.wikipedia.org/wiki/Structural_type_system) whose
members are identified by name instead of position. These are called _structural
data classes_, also known as a _struct types_ or _structs_.

Both struct types and values are written inside curly braces (`{`...`}`). In
both cases, they have a comma-separated list of members that start with a period
(`.`) followed by the field name.

-   In a struct type, the field name is followed by a colon (`:`) and the type,
    as in: `{.name: String, .count: i32}`.
-   In a struct value, called a _structural data class literal_ or a _struct
    literal_, the field name is followed by an equal sign (`=`) and the value,
    as in `{.key = "Joe", .count = 3}`.

> References:
>
> -   [Struct types](classes.md#struct-types)
> -   Proposal
>     [#561: Basic classes: use cases, struct literals, struct types, and future work](https://github.com/carbon-language/carbon-lang/pull/561)
> -   Proposal
>     [#981: Implicit conversions for aggregates](https://github.com/carbon-language/carbon-lang/pull/981)
> -   Proposal
>     [#710: Default comparison for data classes](https://github.com/carbon-language/carbon-lang/issues/710)

### Pointer types

The type of pointers-to-values-of-type-`T` is written `T*`. Carbon pointers do
not support
[pointer arithmetic](<https://en.wikipedia.org/wiki/Pointer_(computer_programming)>);
the only pointer [operations](#expressions) are:

-   Dereference: given a pointer `p`, `*p` gives the value `p` points to as an
    [l-value](<https://en.wikipedia.org/wiki/Value_(computer_science)#lrvalue>).
    `p->m` is syntactic sugar for `(*p).m`.
-   Address-of: given an
    [l-value](<https://en.wikipedia.org/wiki/Value_(computer_science)#lrvalue>)
    `x`, `&x` returns a pointer to `x`.

There are no [null pointers](https://en.wikipedia.org/wiki/Null_pointer) in
Carbon. To represent a pointer that may not refer to a valid object, use the
type `Optional(T*)`.

Pointers are the main Carbon mechanism for allowing a function to modify a
variable of the caller.

> References:
>
> -   Question-for-leads issue
>     [#520: should we use whitespace-sensitive operator fixity?](https://github.com/carbon-language/carbon-lang/issues/520)
> -   Question-for-leads issue
>     [#523: what syntax should we use for pointer types?](https://github.com/carbon-language/carbon-lang/issues/523)

### Arrays and slices

The type of an array of holding 4 `i32` values is written `[i32; 4]`. There is
an [implicit conversion](expressions/implicit_conversions.md) from tuples to
arrays of the same length as long as every component of the tuple may be
implicitly converted to the destination element type. In cases where the size of
the array may be deduced, it may be omitted, as in:

```carbon
var i: i32 = 1;
// `[i32;]` equivalent to `[i32; 3]` here.
var a: [i32;] = (i, i, i);
```

Elements of an array may be accessed using square brackets (`[`...`]`), as in
`a[i]`:

```carbon
a[i] = 2;
Console.Print(a[0]);
```

> **TODO:** Slices

## Expressions

Expressions describe some computed value. The simplest example would be a
literal number like `42`: an expression that computes the integer value 42.

Some common expressions in Carbon include:

-   Literals:

    -   [boolean](#bool): `true`, `false`
    -   [integer](#integer-literals): `42`, `-7`
    -   [real-number](#floating-point-literals): `3.1419`, `6.022e+23`
    -   [string](#string-literals): `"Hello World!"`
    -   [tuple](#tuples): `(1, 2, 3)`
    -   [struct](#struct-types): `{.word = "the", .count = 56}`

-   [Names](#names) and [member access](expressions/member_access.md)

-   [Operators](expressions#operators):

    -   [Arithmetic](expressions/arithmetic.md): `-x`, `1 + 2`, `3 - 4`,
        `2 * 5`, `6 / 3`, `5 % 3`
    -   [Bitwise](expressions/bitwise.md): `2 & 3`, `2 | 4`, `3 ^ 1`, `^7`
    -   [Bit shift](expressions/bitwise.md): `1 << 3`, `8 >> 1`
    -   [Comparison](expressions/comparison_operators.md): `2 == 2`, `3 != 4`,
        `5 < 6`, `7 > 6`, `8 <= 8`, `8 >= 8`
    -   [Conversion](expressions/as_expressions.md): `2 as i32`
    -   [Logical](expressions/logical_operators.md): `a and b`, `c or d`,
        `not e`
    -   [Indexing](#arrays-and-slices): `a[3]`
    -   [Function](#functions) call: `f(4)`
    -   [Pointer](#pointer-types): `*p`, `p->m`, `&x`

-   [Conditionals](expressions/if.md): `if c then t else f`
-   Parentheses: `(7 + 8) * (3 - 1)`

When an expression appears in a context in which an expression of a specific
type is expected, [implicit conversions](expressions/implicit_conversions.md)
are applied to convert the expression to the target type.

> References:
>
> -   [Expressions](expressions/)
> -   Proposal
>     [#162: Basic Syntax](https://github.com/carbon-language/carbon-lang/pull/162)
> -   Proposal
>     [#555: Operator precedence](https://github.com/carbon-language/carbon-lang/pull/555)
> -   Proposal
>     [#601: Operator tokens](https://github.com/carbon-language/carbon-lang/pull/601)
> -   Proposal
>     [#680: And, or, not](https://github.com/carbon-language/carbon-lang/pull/680)
> -   Proposal
>     [#702: Comparison operators](https://github.com/carbon-language/carbon-lang/pull/702)
> -   Proposal
>     [#845: as expressions](https://github.com/carbon-language/carbon-lang/pull/845)
> -   Proposal
>     [#911: Conditional expressions](https://github.com/carbon-language/carbon-lang/pull/911)
> -   Proposal
>     [#1083: Arithmetic expressions](https://github.com/carbon-language/carbon-lang/pull/1083)

## Declarations, Definitions, and Scopes

_Declarations_ introduce a new [name](#names) and say what that name represents.
For some kinds of entities, like [functions](#functions), there are two kinds of
declarations: _forward declarations_ and _definitions_. In this case, there
should be exactly one definition for the name, but there can be additional
forward declarations that introduce the name before it is defined. Forward
declarations allow cyclic references, and can be used to declare a name in an
[api file](#packages-libraries-namespaces) that is defined in an
[impl file](#packages-libraries-namespaces). A name that has been declared but
not defined is called _incomplete_, and in some cases there are limitations on
what can be done with an incomplete name.

A name is valid until the end of the innermost enclosing
[_scope_](<https://en.wikipedia.org/wiki/Scope_(computer_science)>). Except for
the outermost scope, scopes are enclosed in curly braces (`{`...`}`).

## Patterns

A _pattern_ says how to receive some data that is being matched against. There
are two kinds of patterns:

-   _Refutable_ patterns can fail to match based on the runtime value being
    matched.
-   _Irrefutable_ patterns are guaranteed to match, so long as the code
    type-checks.

Irrefutable patterns are used in [function parameters](#functions),
[variable `var` declarations](#variable-var-declarations), and
[constant `let` declarations](#constant-let-declarations).
[`match` statements](#match) can include both refutable patterns and irrefutable
patterns.

> References:
>
> -   [Pattern matching](pattern_matching.md)
> -   Proposal
>     [#162: Basic Syntax](https://github.com/carbon-language/carbon-lang/pull/162)

### Binding patterns

The most common irrefutable pattern is a _binding pattern_, consisting of a new
name, a colon (`:`), and a type. It binds the matched value of that type to that
name. It can only match values that may be
[implicitly converted](expressions/implicit_conversions.md) to that type. A
underscore (`_`) may be used instead of the name to match a value but without
binding any name to it.

Binding patterns default to _`let` bindings_ except inside a context where the
`var` keyword is used to make it a _`var` binding_:

-   The result of a `let` binding is the name is bound to an
    [non-l-value](<https://en.wikipedia.org/wiki/Value_(computer_science)#lrvalue>).
    This means the value can not be modified, and its address cannot be taken.
-   A `var` binding has dedicated storage, and so the name is an
    [l-value](<https://en.wikipedia.org/wiki/Value_(computer_science)#lrvalue>)
    which can be modified and has a stable address.

A [generic binding](#checked-and-template-parameters) uses `:!` instead of a
colon (`:`) and can only match compile-time values.

The keyword `auto` may be used in place of the type in a binding pattern, as
long as the type can be deduced from the type of a value in the same
declaration.

### Destructuring patterns

There are also irrefutable _destructuring patterns_, such as _tuple
destructuring_. A tuple destructuring pattern looks like a tuple of patterns. It
may only be used to match tuple values whose components match the component
patterns of the tuple. An example use is:

```carbon
// `Bar()` returns a tuple consisting of an
// `i32` value and 2-tuple of `f32` values.
fn Bar() -> (i32, (f32, f32));

fn Foo() -> i64 {
  // Pattern in `var` declaration:
  var (p: i64, _: auto) = Bar();
  return p;
}
```

The pattern used in the `var` declaration destructures the tuple value returned
by `Bar()`. The first component pattern, `p: i64`, corresponds to the first
component of the value returned by `Bar()`, which has type `i32`. This is
allowed since there is an implicit conversion from `i32` to `i64`. The result of
this conversion is assigned to the name `p`. The second component pattern,
`_: auto`, matches the second component of the value returned by `Bar()`, which
has type `(f32, f32)`.

### Refutable patterns

Additional kinds of patterns are allowed in [`match` statements](#match), that
may or may not match based on the runtime value of the `match` expression:

-   An _expression pattern_ is an expression, such as `42`, whose value must be
    equal to match.
-   A _choice pattern_ matches one case from a choice type, as described in
    [the choice types section](#choice-types).
-   A _dynamic cast pattern_ is tests the dynamic type, as described in
    [inheritance](#inheritance).

See [`match`](#match) for examples of refutable patterns.

> References:
>
> -   [Pattern matching](pattern_matching.md)
> -   Question-for-leads issue
>     [#1283: how should pattern matching and implicit conversion interact?](https://github.com/carbon-language/carbon-lang/issues/1283)

## Name-binding declarations

There are two kinds of name-binding declarations:

-   constant declarations, introduced with `let`, and
-   variable declarations, introduced with `var`.

There are no forward declarations of these; all name-binding declarations are
[definitions](#declarations-definitions-and-scopes).

### Constant `let` declarations

A `let` declaration matches an [irrefutable pattern](#patterns) to a value. In
this example, the name `x` is bound to the value `42` with type `i64`:

```carbon
let x: i64 = 42;
```

Here `x: i64` is the pattern, which is followed by an equal sign (`=`) and the
value to match, `42`. The names from [binding patterns](#binding-patterns) are
introduced into the enclosing [scope](#declarations-definitions-and-scopes).

### Variable `var` declarations

A `var` declaration is similar, except with `var` bindings, so `x` here is an
[l-value](<https://en.wikipedia.org/wiki/Value_(computer_science)#lrvalue>) with
storage and an address, and so may be modified:

```carbon
var x: i64 = 42;
x = 7;
```

Variables with a type that has
[an unformed state](https://github.com/carbon-language/carbon-lang/pull/257) do
not need to be initialized in the variable declaration, but do need to be
assigned before they are used.

> References:
>
> -   [Variables](variables.md)
> -   Proposal
>     [#162: Basic Syntax](https://github.com/carbon-language/carbon-lang/pull/162)
> -   Proposal
>     [#257: Initialization of memory and variables](https://github.com/carbon-language/carbon-lang/pull/257)
> -   Proposal
>     [#339: Add `var <type> <identifier> [ = <value> ];` syntax for variables](https://github.com/carbon-language/carbon-lang/pull/339)
> -   Proposal
>     [#618: var ordering](https://github.com/carbon-language/carbon-lang/pull/618)

### `auto`

If `auto` is used as the type in a `var` or `let` declaration, the type is the
static type of the initializer expression, which is required.

```
var x: i64 = 2;
// The type of `y` is inferred to be `i64`.
let y: auto = x + 3;
// The type of `z` is inferred to be `bool`.
var z: auto = (y > 1);
```

> References:
>
> -   [Type inference](type_inference.md)
> -   Proposal
>     [#851: auto keyword for vars](https://github.com/carbon-language/carbon-lang/pull/851)

## Functions

Functions are the core unit of behavior. For example, this is a
[forward declaration](#declarations-definitions-and-scopes) of a function that
adds two 64-bit integers:

```carbon
fn Add(a: i64, b: i64) -> i64;
```

Breaking this apart:

-   `fn` is the keyword used to introduce a function.
-   Its name is `Add`. This is the name added to the enclosing
    [scope](#declarations-definitions-and-scopes).
-   The parameter list in parentheses (`(`...`)`) is a comma-separated list of
    [irrefutable patterns](#patterns).
-   It returns an `i64` result. Functions that return nothing omit the `->` and
    return type.

You would call this function like `Add(1, 2)`.

A function definition is a function declaration that has a body
[block](#blocks-and-statements) instead of a semicolon:

```carbon
fn Add(a: i64, b: i64) -> i64 {
  return a + b;
}
```

The names of the parameters are in scope until the end of the definition or
declaration.

The bindings in the parameter list default to
[`let` bindings](#binding-patterns), and so the parameter names are treated as
[r-values](<https://en.wikipedia.org/wiki/Value_(computer_science)#lrvalue>). If
the `var` keyword is added before the binding, then the arguments will be copied
to new storage, and so can be mutated in the function body. The copy ensures
that any mutations will not be visible to the caller.

> References:
>
> -   [Functions](functions.md)
> -   Proposal
>     [#162: Basic Syntax](https://github.com/carbon-language/carbon-lang/pull/162)
> -   Proposal
>     [#438: Add statement syntax for function declarations](https://github.com/carbon-language/carbon-lang/pull/438)
> -   Question-for-leads issue
>     [#476: Optional argument names (unused arguments)](https://github.com/carbon-language/carbon-lang/issues/476)

### `auto` return type

If `auto` is used in place of the return type, the return type of the function
is inferred from the function body. It is set to [common type](#common-type) of
the static type of arguments to the [`return` statements](#return) in the
function. This is not allowed in a forward declaration.

```
// Return type is inferred to be `bool`, the type of `a > 0`.
fn Positive(a: i64) -> auto {
  return a > 0;
}
```

> References:
>
> -   [Type inference](type_inference.md)
> -   [Function return clause](functions.md#return-clause)
> -   Proposal
>     [#826: Function return type inference](https://github.com/carbon-language/carbon-lang/pull/826)

### Blocks and statements

A _block_ is a sequence of _statements_. A block defines a
[scope](#declarations-definitions-and-scopes) and, like other scopes, is
enclosed in curly braces (`{`...`}`). Each statement is terminated by a
semicolon or block. [Expressions](#expressions) and
[`var`](#variable-var-declarations) and [`let`](#constant-let-declarations) are
valid statements.

Statements within a block are normally executed in the order the appear in the
source code, except when modified by control-flow statements.

The body of a function is defined by a block, and some
[control-flow statements](#control-flow) have their own blocks of code. These
are nested within the enclosing scope. For example, here is a function
definition with a block of statements defining the body of the function, and a
nested block as part of a `while` statement:

```carbon
fn Foo() {
  Bar();
  while (Baz()) {
    Quux();
  }
}
```

> References:
>
> -   [Blocks and statements](blocks_and_statements.md)
> -   Proposal
>     [#162: Basic Syntax](https://github.com/carbon-language/carbon-lang/pull/162)

### Assignment statements

Assignment statements mutate the value of the
[l-value](<https://en.wikipedia.org/wiki/Value_(computer_science)#lrvalue>)
described on the left-hand side of the assignment.

-   Assignment: `x = y;`. `x` is assigned the value of `y`.
-   Increment and decrement: `++i;`, `--j;`. `i` is set to `i + 1`, `j` is set
    to `j - 1`.
-   Compound assignment: `x += y;`, `x -= y;`, `x *= y;`, `x /= y;`, `x &= y;`,
    `x |= y;`, `x ^= y;`, `x <<= y;`, `x >>= y;`. `x @= y;` is equivalent to
    `x = x @ y;` for each operator `@`.

Unlike C++, these assignments are statements, not expressions, and don't return
a value.

### Control flow

Blocks of statements are generally executed sequentially. Control-flow
statements give additional control over the flow of execution and which
statements are executed.

Some control-flow statements include [blocks](#blocks-and-statements). Those
blocks will always be within curly braces `{`...`}`.

```carbon
// Curly braces { ... } are required.
if (condition) {
  ExecutedWhenTrue();
} else {
  ExecutedWhenFalse();
}
```

This is unlike C++, which allows control-flow constructs to omit curly braces
around a single statement.

> References:
>
> -   [Control flow](control_flow/README.md)
> -   Proposal
>     [#162: Basic Syntax](https://github.com/carbon-language/carbon-lang/pull/162)
> -   Proposal
>     [#623: Require braces](https://github.com/carbon-language/carbon-lang/pull/623)

#### `if` and `else`

`if` and `else` provide conditional execution of statements. An `if` statement
consists of:

-   An `if` introducer followed by a condition in parentheses. If the condition
    evaluates to `true`, the block following the condition is executed,
    otherwise it is skipped.
-   This may be followed by zero or more `else if` clauses, whose conditions are
    evaluated if all prior conditions evaluate to `false`, with a block that is
    executed if that evaluation is to `true`.
-   A final optional `else` clause, with a block that is executed if all
    conditions evaluate to `false`.

For example:

```carbon
if (fruit.IsYellow()) {
  Console.Print("Banana!");
} else if (fruit.IsOrange()) {
  Console.Print("Orange!");
} else {
  Console.Print("Vegetable!");
}
```

This code will:

-   Print `Banana!` if `fruit.IsYellow()` is `true`.
-   Print `Orange!` if `fruit.IsYellow()` is `false` and `fruit.IsOrange()` is
    `true`.
-   Print `Vegetable!` if both of the above return `false`.

> References:
>
> -   [Control flow](control_flow/conditionals.md)
> -   Proposal
>     [#285: if/else](https://github.com/carbon-language/carbon-lang/pull/285)

#### Loops

> References: [Loops](control_flow/loops.md)

##### `while`

`while` statements loop for as long as the passed expression returns `true`. For
example, this prints `0`, `1`, `2`, then `Done!`:

```carbon
var x: i32 = 0;
while (x < 3) {
  Console.Print(x);
  ++x;
}
Console.Print("Done!");
```

> References:
>
> -   [`while` loops](control_flow/loops.md#while)
> -   Proposal
>     [#340: Add C++-like `while` loops](https://github.com/carbon-language/carbon-lang/pull/340)

##### `for`

`for` statements support range-based looping, typically over containers. For
example, this prints all names in `names`:

```carbon
for (var name: String in names) {
  Console.Print(name);
}
```

This prints each `String` value in `names`.

> References:
>
> -   [`for` loops](control_flow/loops.md#for)
> -   Proposal
>     [#353: Add C++-like `for` loops](https://github.com/carbon-language/carbon-lang/pull/353)

##### `break`

The `break` statement immediately ends a `while` or `for` loop. Execution will
continue starting from the end of the loop's scope. For example, this processes
steps until a manual step is hit (if no manual step is hit, all steps are
processed):

```carbon
for (var step: Step in steps) {
  if (step.IsManual()) {
    Console.Print("Reached manual step!");
    break;
  }
  step.Process();
}
```

> References: [`break`](control_flow/loops.md#break)

##### `continue`

The `continue` statement immediately goes to the next loop of a `while` or
`for`. In a `while`, execution continues with the `while` expression. For
example, this prints all non-empty lines of a file, using `continue` to skip
empty lines:

```carbon
var f: File = OpenFile(path);
while (!f.EOF()) {
  var line: String = f.ReadLine();
  if (line.IsEmpty()) {
    continue;
  }
  Console.Print(line);
}
```

> References: [`continue`](control_flow/loops.md#continue)

#### `return`

The `return` statement ends the flow of execution within a function, returning
execution to the caller.

```carbon
// Prints the integers 1 .. `n` and then
// returns to the caller.
fn PrintFirstN(n: i32) {
  var i: i32 = 0;
  while (true) {
    i += 1;
    if (i > n) {
      // None of the rest of the function is
      // executed after a `return`.
      return;
    }
    Console.Print(i);
  }
}
```

If the function returns a value to the caller, that value is provided by an
expression in the return statement. For example:

```carbon
fn Sign(i: i32) -> i32 {
  if (i > 0) {
    return 1;
  }
  if (i < 0) {
    return -1;
  }
  return 0;
}

Assert(Sign(-3) == -1);
```

> References:
>
> -   [`return`](control_flow/return.md)
> -   [`return` statements](functions.md#return-statements)
> -   Proposal
>     [#415: return](https://github.com/carbon-language/carbon-lang/pull/415)
> -   Proposal
>     [#538: return with no argument](https://github.com/carbon-language/carbon-lang/pull/538)

##### `returned var`

To avoid a copy when returning a variable, add a `returned` prefix to the
variable's declaration and use `return var` instead of returning an expression,
as in:

```carbon
fn MakeCircle(radius: i32) -> Circle {
  returned var c: Circle;
  c.radius = radius;
  // `return c` would be invalid because `returned` is in use.
  return var;
}
```

This is instead of
[the "named return value optimization" of C++](https://en.wikipedia.org/wiki/Copy_elision#Return_value_optimization).

> References:
>
> -   [`returned var`](control_flow/return.md#returned-var)
> -   Proposal
>     [#257: Initialization of memory and variables](https://github.com/carbon-language/carbon-lang/pull/257)

#### `match`

`match` is a control flow similar to `switch` of C/C++ and mirrors similar
constructs in other languages, such as Swift. The `match` keyword is followed by
an expression in parentheses, whose value is matched against the `case`
declarations, each of which contains a [refutable pattern](#refutable-patterns),
in order. The refutable pattern may optionally be followed by an `if`
expression, which may use the names from bindings in the pattern.

The code for the first matching `case` is executed. An optional `default` block
may be placed after the `case` declarations, it will be executed if none of the
`case` declarations match.

An example `match` is:

```carbon
fn Bar() -> (i32, (f32, f32));

fn Foo() -> f32 {
  match (Bar()) {
    case (42, (x: f32, y: f32)) => {
      return x - y;
    }
    case (p: i32, (x: f32, _: f32)) if (p < 13) => {
      return p * x;
    }
    case (p: i32, _: auto) if (p > 3) => {
      return p * Pi;
    }
    default => {
      return Pi;
    }
  }
}
```

> References:
>
> -   [Pattern matching](pattern_matching.md)
> -   Question-for-leads issue
>     [#1283: how should pattern matching and implicit conversion interact?](https://github.com/carbon-language/carbon-lang/issues/1283)

## User-defined types

> **TODO:** Maybe rename to "nominal types"?

### Classes

_Nominal classes_, or just
[_classes_](<https://en.wikipedia.org/wiki/Class_(computer_programming)>), are a
way for users to define their own
[data strutures](https://en.wikipedia.org/wiki/Data_structure) or
[record types](<https://en.wikipedia.org/wiki/Record_(computer_science)>).

This is an example of a class
[definition](#declarations-definitions-and-scopes):

```carbon
class Widget {
  var x: i32;
  var y: i32;
  var payload: String;
}
```

Breaking this apart:

-   This defines a class named `Widget`. `Widget` is the name added to the
    enclosing [scope](#declarations-definitions-and-scopes).
-   The name `Widget` is followed by curly braces (`{`...`}`) containing the
    class _body_, making this a
    [definition](#declarations-definitions-and-scopes). A
    [forward declaration](#declarations-definitions-and-scopes) would instead
    have a semicolon(`;`).
-   Those braces delimit the class'
    [scope](#declarations-definitions-and-scopes).
-   Fields, or
    [instances variables](https://en.wikipedia.org/wiki/Instance_variable), are
    defined using [`var` declarations](#variable-var-declarations). `Widget` has
    two `i32` fields (`x` and `y`), and one `String` field (`payload`).

The order of the field declarations determines the fields' memory-layout order.

Classes may have other kinds of members beyond fields declared in its scope:

-   [Class functions](#class-functions-and-factory-functions)
-   [Methods](#methods)
-   [`alias`](#aliases)
-   [`let`](#constant-let-declarations) to define class constants. **TODO:**
    Another syntax to define constants associated with the class like
    `class let` or `static let`?
-   `class`, to define a
    [_member class_ or _nested class_](https://en.wikipedia.org/wiki/Inner_class)

Within the scope of a class, the unqualified name `Self` can be used to refer to
the class itself.

Members of a class are [accessed](expressions/member_access.md) using the dot
(`.`) notation, so given an instance `dial` of type `Widget`, `dial.payload`
refers to its `payload` field.

Both [structural data classes](#struct-types) and nominal classes are considered
_class types_, but they are commonly referred to as "structs" and "classes"
respectively when that is not confusing. Like structs, classes refer to their
members by name. Unlike structs, classes are
[nominal types](https://en.wikipedia.org/wiki/Nominal_type_system#Nominal_typing).

> References:
>
> -   [Classes](classes.md#nominal-class-types)
> -   Proposal
>     [#722: Nominal classes and methods](https://github.com/carbon-language/carbon-lang/pull/722)
> -   Proposal
>     [#989: Member access expressions](https://github.com/carbon-language/carbon-lang/pull/989)

#### Assignment

There is an [implicit conversions](expressions/implicit_conversions.md) defined
between a [struct literal](#struct-types) and a class type with the same fields,
in any scope that has [access](#access-control) to all of the class' fields.
This may be used to assign or initialize a variable with a class type, as in:

```carbon
var sprocket: Widget = {.x = 3, .y = 4, .payload = "Sproing"};
sprocket = {.x = 2, .y = 1, .payload = "Bounce"};
```

> References:
>
> -   [Classes: Construction](classes.md#construction)
> -   Proposal
>     [#981: Implicit conversions for aggregates](https://github.com/carbon-language/carbon-lang/pull/981)

#### Class functions and factory functions

Classes may also contain _class functions_. These are functions that are
accessed as members of the type, like
[static member functions in C++](<https://en.wikipedia.org/wiki/Method_(computer_programming)#Static_methods>),
as opposed to [methods](#methods) that are members of instances. They are
commonly used to define a function that creates instances. Carbon does not have
separate
[constructors](<https://en.wikipedia.org/wiki/Constructor_(object-oriented_programming)>)
like C++ does.

```carbon
class Point {
  // Class function that instantiates `Point`.
  // `Self` in class scope means the class currently being defined.
  fn Origin() -> Self {
    return {.x = 0, .y = 0};
  }
  var x: i32;
  var y: i32;
}
```

Note that if the definition of a function is provided inside the class scope,
the body is treated as if it was defined immediately after the outermost class
definition. This means that members such as the fields will be considered
defined even if their definitions are later in the source than the class
function.

The [`returned var` feature](#returned-var) can be used if the address of the
instance being created is needed in a factory function, as in:

```carbon
class Registered {
  fn Create() -> Self {
    returned var result: Self = {...};
    StoreMyPointerSomewhere(&result);
    return var;
  }
}
```

This approach can also be used for types that can't be copied or moved.

#### Methods

Class type definitions can include methods:

```carbon
class Point {
  // Method defined inline
  fn Distance[me: Self](x2: i32, y2: i32) -> f32 {
    var dx: i32 = x2 - me.x;
    var dy: i32 = y2 - me.y;
    return Math.Sqrt(dx * dx - dy * dy);
  }
  // Mutating method
  fn Offset[addr me: Self*](dx: i32, dy: i32);

  var x: i32;
  var y: i32;
}

// Out-of-line definition of method declared inline.
fn Point.Offset[addr me: Self*](dx: i32, dy: i32) {
  me->x += dx;
  me->y += dy;
}

var origin: Point = {.x = 0, .y = 0};
Assert(Math.Abs(origin.Distance(3, 4) - 5.0) < 0.001);
origin.Offset(3, 4);
Assert(origin.Distance(3, 4) == 0.0);
```

This defines a `Point` class type with two integer data members `x` and `y` and
two methods `Distance` and `Offset`:

-   Methods are defined as class functions with a `me` parameter inside square
    brackets `[`...`]` before the regular explicit parameter list in parens
    `(`...`)`.
-   Methods are called using using the member syntax, `origin.Distance(`...`)`
    and `origin.Offset(`...`)`.
-   `Distance` computes and returns the distance to another point, without
    modifying the `Point`. This is signified using `[me: Self]` in the method
    declaration.
-   `origin.Offset(`...`)` does modify the value of `origin`. This is signified
    using `[addr me: Self*]` in the method declaration.
-   Methods may be declared lexically inline like `Distance`, or lexically out
    of line like `Offset`.

> References:
>
> -   [Methods](classes.md#methods)
> -   Proposal
>     [#722: Nominal classes and methods](https://github.com/carbon-language/carbon-lang/pull/722)

#### Inheritance

Classes by default are
[_final_](<https://en.wikipedia.org/wiki/Inheritance_(object-oriented_programming)#Non-subclassable_classes>),
which means they may not be extended. A class may be declared as allowing
extension using either the `base class` or `abstract class` introducer instead
of `class`. An `abstract class` is a base class that may not itself be
instantiated.

```carbon
base class MyBaseClass { ... }
```

Either kind of base class maybe _extended_ to get a _derived class_. Derived
classes are final unless they are themselved declared `base` or `abstract`.
Classes may only extend a single class. Carbon only supports single inheritance,
and will use mixins instead of multiple inheritance.

```carbon
base class MiddleDerived extends MyBaseClass { ... }
class FinalDerived extends MiddleDerived { ... }
// ❌ Forbidden: class Illegal extends FinalDerived { ... }
```

A base class may define
[virtual methods](https://en.wikipedia.org/wiki/Virtual_function). These are
methods whose implementation may be overridden in a derived class. By default
methods are _non-virtual_, the declaration of a virtual methods must be prefixed
by one of these three keywords:

-   A method marked `virtual` has a definition in this class but not in any
    base.
-   A method marked `abstract` does not have have a definition in this class,
    but must have a definition in any non-`abstract` derived class.
-   A method marked `impl` has a definition in this class, overriding any
    definition in a base class.

A pointer to a derived class may be cast to a pointer to one of its base
classes. Calling a virtual method through a pointer to a base class will use the
overridden definition provided in the derived class. Base classes with `virtual`
methods may use
[run-time type information](https://en.wikipedia.org/wiki/Run-time_type_information)
in a match statement to dynamically test whether the dynamic type of a value is
some derived class, as in:

```carbon
var base_ptr: MyBaseType* = ...;
match (base_ptr) {
  case dyn p: MiddleDerived* => { ... }
}
```

For purposes of construction, a derived class acts like its first field is
called `base` with the type of its immediate base class.

```carbon
class MyDerivedType extends MyBaseType {
  fn Create() -> MyDerivedType {
    return {.base = MyBaseType.Create(), .derived_field = 7};
  }
  var derived_field: i32;
}
```

Abstract classes can't be instantiated, so instead they should define class
functions returning `partial Self`. Those functions should be marked
[`protected`](#access-control) so they may only be used by derived classes.

```carbon
abstract class AbstractClass {
  protected fn Create() -> partial Self {
    return {.field_1 = 3, .field_2 = 9};
  }
  // ...
  var field_1: i32;
  var field_2: i32;
}
// ❌ Error: can't instantiate abstract class
var abc: AbstractClass = ...;

class DerivedFromAbstract extends AbstractClass {
  fn Create() -> Self {
    // AbstractClass.Create() returns a
    // `partial AbstractClass` that can be used as
    // the `.base` member when constructing a value
    // of a derived class.
    return {.base = AbstractClass.Create(),
            .derived_field = 42 };
  }

  var derived_field: i32;
}
```

> References:
>
> -   [Inheritance](classes.md#inheritance)
> -   Proposal
>     [#777: Inheritance](https://github.com/carbon-language/carbon-lang/pull/777)
> -   Proposal
>     [#820: Implicit conversions](https://github.com/carbon-language/carbon-lang/pull/820)

#### Access control

Class members are by default publicly accessible. The `private` keyword prefix
can be added to the member's declaration to restrict it to members of the class
or any friends. A `private virtual` or `private abstract` method may be
implemented in derived classes, even though it may not be called.

Friends may be declared using a `friend` declaration inside the class naming an
existing function or type. Unlike C++, `friend` declarations may only refer to
names resolvable by the compiler, and don't act like forward declarations.

`protected` is like `private`, but also gives access to derived classes.

> References:
>
> -   [Access control for class members](classes.md#access-control)
> -   Question-for-leads issue
>     [#665: `private` vs `public` _syntax_ strategy, as well as other visibility tools like `external`/`api`/etc.](https://github.com/carbon-language/carbon-lang/issues/665)
> -   Question-for-leads issue
>     [#971: Private interfaces in public API files](https://github.com/carbon-language/carbon-lang/issues/971)

#### Destructors

A destructor for a class is custom code executed when the lifetime of a value of
that type ends. They are defined with the `destructor` keyword followed by
either `[me: Self]` or `[addr me: Self*]` (as is done with [methods](#methods))
and the block of code in the class definition, as in:

```carbon
class MyClass {
  destructor [me: Self] { ... }
}
```

or:

```carbon
class MyClass {
  // Can modify `me` in the body.
  destructor [addr me: Self*] { ... }
}
```

The destructor for a class is run before the destructors of its data members.
The data members are destroyed in reverse order of declaration. Derived classes
are destroyed before their base classes.

A destructor in a abstract or base class may be declared `virtual` like with
[methods](#inheritance). Destructors in classes derived from one with a virtual
destructor must be declared with the `impl` keyword prefix. It is illegal to
delete an instance of a derived class through a pointer to a base class unless
the base class is declared `virtual` or `impl`. To delete a pointer to a
non-abstract base class when it is known not to point to a value with a derived
type, use `UnsafeDelete`.

> References:
>
> -   [Destructors](classes.md#destructors)
> -   Proposal
>     [#1154: Destructors](https://github.com/carbon-language/carbon-lang/pull/1154)

### Choice types

A _choice type_ is a [tagged union](https://en.wikipedia.org/wiki/Tagged_union),
that can store different types of data in a storage space that can hold the
largest. A choice type has a name, and a list of cases separated by commas
(`,`). Each case has a name and an optional parameter list.

```carbon
choice IntResult {
  Success(value: i32),
  Failure(error: String),
  Cancelled
}
```

The value of a choice type is one of the cases, plus the values of the
parameters to that case, if any. A value can be constructed by naming the case
and providing values for the parameters, if any:

```carbon
fn ParseAsInt(s: String) -> IntResult {
  var r: i32 = 0;
  for (c: i32 in s) {
    if (not IsDigit(c)) {
      // Equivalent to `IntResult.Failure(...)`
      return .Failure("Invalid character");
    }
    // ...
  }
  return .Success(r);
}
```

Choice type values may be consumed using a [`match` statement](#match):

```carbon
match (ParseAsInt(s)) {
  case .Success(value: i32) => {
    return value;
  }
  case .Failure(error: String) => {
    Display(error);
  }
  case .Cancelled => {
    Terminate();
  }
}
```

They can also represent an
[enumerated type](https://en.wikipedia.org/wiki/Enumerated_type), if no
additional data is associated with the choices, as in:

```carbon
choice LikeABoolean { False, True }
```

> References:
>
> -   Proposal
>     [#157: Design direction for sum types](https://github.com/carbon-language/carbon-lang/pull/157)
> -   Proposal
>     [#162: Basic Syntax](https://github.com/carbon-language/carbon-lang/pull/162)

## Names

### Packages, libraries, namespaces

-   **Files** are grouped into libraries, which are in turn grouped into
    packages.
-   **Libraries** are the granularity of code reuse through imports.
-   **Packages** are the unit of distribution.

Name paths in Carbon always start with the package name. Additional namespaces
may be specified as desired.

For example, this code declares a class `Geometry.Shapes.Flat.Circle` in a
library `Geometry/OneSide`:

```carbon
package Geometry library("OneSide") namespace Shapes;

namespace Flat;
class Flat.Circle { ... }
```

This type can be used from another package:

```carbon
package ExampleUser;

import Geometry library("OneSide");

fn Foo(Geometry.Shapes.Flat.Circle circle) { ... }
```

> References:
>
> -   [Code and name organization](code_and_name_organization)
> -   Proposal
>     [#107: Code and name organization](https://github.com/carbon-language/carbon-lang/pull/107)
> -   Proposal
>     [#752: api file default public](https://github.com/carbon-language/carbon-lang/pull/752)
> -   Question-for-leads issue
>     [#1136: what is the top-level scope in a source file, and what names are found there?](https://github.com/carbon-language/carbon-lang/issues/1136)

### Legal names

Various constructs introduce a named entity in Carbon. These can be functions,
types, variables, or other kinds of entities. A name in Carbon is formed from a
word, which is a sequence of letters, numbers, and underscores, and which starts
with a letter. We intend to follow Unicode's Annex 31 in selecting valid
identifier characters, but a concrete set of valid characters has not been
selected yet.

> References: [Lexical conventions](lexical_conventions)
>
> **TODO:** References need to be evolved.

### Naming conventions

Our naming conventions are:

-   For idiomatic Carbon code:
    -   `UpperCamelCase` will be used when the named entity cannot have a
        dynamically varying value. For example, functions, namespaces, or
        compile-time constant values.
    -   `lower_snake_case` will be used when the named entity's value won't be
        known until runtime, such as for variables.
-   For Carbon-provided features:
    -   Keywords and type literals will use `lower_snake_case`.
    -   Other code will use the conventions for idiomatic Carbon code.

> References:
>
> -   [Naming conventions](naming_conventions.md)
> -   Proposal
>     [#861: Naming conventions](https://github.com/carbon-language/carbon-lang/pull/861)

### Aliases

Carbon provides a facility to declare a new name as an alias for a value. This
is a fully general facility because everything is a value in Carbon, including
types.

For example:

```carbon
alias MyInt = i32;
```

This creates an alias called `MyInt` for whatever `i32` resolves to. Code
textually after this can refer to `MyInt`, and it will transparently refer to
`i32`.

> References:
>
> -   [Aliases](aliases.md)
> -   Question-for-leads issue
>     [#749: Alias syntax](https://github.com/carbon-language/carbon-lang/issues/749)

> **TODO:** References need to be evolved.

### Name lookup

Unqualified name lookup will always find a file-local result, including aliases,
or names that are defined as part of the prelude. There is no prioritization of
scopes. This means that all relevant scopes are searched, and if the name is
found multiple times referring to different entities, then it is an error. The
error may be resolved by adding qualification to disambiguate the lookup.

When defining a member of a class, like a [method](#methods), then the other
members of the class' scope are searched as part of name lookup, even when that
member is being defined out-of-line.

> References:
>
> -   [Name lookup](name_lookup.md)
> -   Proposal
>     [#989: Member access expressions](https://github.com/carbon-language/carbon-lang/pull/989)
>
> **TODO:** References need to be evolved.

#### Name lookup for common types

Common types that we expect to be used universally will be provided for every
file, including `i32` and `bool`. These will likely be defined in a special
"prelude" package.

> References:
>
> -   [Name lookup](name_lookup.md)
> -   Question-for-leads issue
>     [#750: Naming conventions for Carbon-provided features](https://github.com/carbon-language/carbon-lang/issues/750)
> -   Question-for-leads issue
>     [#1058: How should interfaces for core functionality be named?](https://github.com/carbon-language/carbon-lang/issues/1058)
>
> **TODO:** References need to be evolved.

### Name visibility

> **TODO:**

> References:
>
> -   [Exporting entities from an API file](code_and_name_organization/README.md#exporting-entities-from-an-api-file)
> -   Question-for-leads issue
>     [#665: `private` vs `public` _syntax_ strategy, as well as other visibility tools like `external`/`api`/etc.](https://github.com/carbon-language/carbon-lang/issues/665)
> -   Proposal
>     [#752: api file default public](https://github.com/carbon-language/carbon-lang/pull/752)
> -   Proposal
>     [#931: Generic impls access (details 4)](https://github.com/carbon-language/carbon-lang/pull/931)

## Generics

Generics allow Carbon constructs like [functions](#functions) and
[classes](#classes) to be written with compile-time parameters and apply
generically to different types using those parameters. For example, this `Min`
function has a type parameter `T` that can be any type that implements the
`Ordered` interface.

```carbon
fn Min[T:! Ordered](x: T, y: T) -> T {
  // Can compare `x` and `y` since they have
  // type `T` known to implement `Ordered`.
  return if x <= y then x else y;
}

var a: i32 = 1;
var b: i32 = 2;
// `T` is deduced to be `i32`
Assert(Min(a, b) == 1);
// `T` is deduced to be `String`
Assert(Min("abc", "xyz") == "abc");
```

Since the `T` type parameter is in the deduced parameter list in square brackets
(`[`...`]`) before the explicit parameter list in parentheses (`(`...`)`), the
value of `T` is determined from the types of the explicit arguments instead of
being passed as a separate explicit argument.

> References: **TODO:** Revisit
>
> -   [Generics: Overview](generics/overview.md)
> -   Proposal
>     [#524: Generics overview](https://github.com/carbon-language/carbon-lang/pull/524)
> -   Proposal
>     [#553: Generics details part 1](https://github.com/carbon-language/carbon-lang/pull/553)
> -   Proposal
>     [#950: Generic details 6: remove facets](https://github.com/carbon-language/carbon-lang/pull/950)

### Checked and template parameters

The `:!` indicates that `T` is a _checked_ parameter passed at compile time.
"Checked" here means that the body of `Min` is type checked when the function is
defined, independent of the specific type values `T` is instantiated with, and
name lookup is delegated to the constraint on `T` (`Ordered` in this case). This
type checking is equivalent to saying the function would pass type checking
given any type `T` that implements the `Ordered` interface. Then calls to `Min`
only need to check that the deduced type value of `T` implements `Ordered`.

The parameter could alternatively be declared to be a _template_ parameter by
prefixing with the `template` keyword, as in `template T:! Type`.

```carbon
fn Convert[template T:! Type](source: T, template U:! Type) -> U {
  var converted: U = source;
  return converted;
}

fn Foo(i: i32) -> f32 {
  // Instantiates with the `T` implicit argument set to `i32` and the `U`
  // explicit argument set to `f32`, then calls with the runtime value `i`.
  return Convert(i, f32);
}
```

Carbon templates follow the same fundamental paradigm as
[C++ templates](<https://en.wikipedia.org/wiki/Template_(C%2B%2B)>): they are
instantiated when called, resulting in late type checking, duck typing, and lazy
binding.

Member lookup into a template type parameter is done in the actual type value
provided by the caller, _in addition_ to any constraints. This means member name
lookup and type checking for anything
[dependent](generics/terminology.md#dependent-names) on the template parameter
can't be completed until the template is instantiated with a specific concrete
type. When the constraint is just `Type`, this gives semantics similar to C++
templates. Constraints can then be added incrementally, with the compiler
verifying that the semantics stay the same. Once all constraints have been
added, removing the word `template` to switch to a checked parameter is safe.

Although checked generics are generally preferred, templates enable translation
of code between C++ and Carbon, and address some cases where the type checking
rigor of generics are problematic.

> References:
>
> -   [Templates](templates.md)
> -   Proposal
>     [#553: Generics details part 1](https://github.com/carbon-language/carbon-lang/pull/553)
> -   Question-for-leads issue
>     [#949: Constrained template name lookup](https://github.com/carbon-language/carbon-lang/issues/949)
> -   Proposal
>     [#989: Member access expressions](https://github.com/carbon-language/carbon-lang/pull/989)

### Interfaces and implementations

_Interfaces_ specify a set of requirements that a types might satisfy.
Interfaces act both as constraints on types a caller might supply and
capabilities that may be assumed of types that satisfy that constraint.

```carbon
interface Printable {
  // Inside an interface definition `Self` means
  // "the type implementing this interface".
  fn Print[me: Self]();
}
```

In addition to function requirements, interfaces can contain:

-   [requirements that other interfaces be implemented](generics/details.md#interface-requiring-other-interfaces)
    or
    [interfaces that this interface extends](generics/details.md#interface-extension)
-   [associated types](generics/details.md#associated-types) and other
    [associated constants](generics/details.md#associated-constants)
-   [interface defaults](generics/details.md#interface-defaults)
-   [`final` interface members](generics/details.md#final-members)

Types only implement an interface if there is an explicit `impl` declaration
that they do. Simply having a `Print` function with the right signature is not
sufficient.

```carbon
class Circle {
  var radius: f32;

  impl as Printable {
    fn Print[me: Self]() {
      Console.WriteLine("Circle with radius: {0}", me.radius);
    }
  }
}
```

In this case, `Print` is a member of `Circle`. Interfaces may also be
implemented [externally](generics/details.md#external-impl), which means the
members of the interface are not direct members of the type. Those methods may
still be called using
[compound member access syntax](generics/details.md#qualified-member-names-and-compound-member-access)
to qualify the name of the member, as in `x.(Printable.Print)()`. External
implementations don't have to be in the same library as the type definition,
subject to the orphan rule ([1](generics/details.md#impl-lookup),
[2](generics/details.md#orphan-rule)) for
[coherence](generics/terminology.md#coherence).

Interfaces and implementations may be
[forward declared](generics/details.md#forward-declarations-and-cyclic-references)
by replacing the definition scope in curly braces (`{`...`}`) with a semicolon.

> References:
>
> -   [Generics: Interfaces](generics/details.md#interfaces)
> -   [Generics: Implementing interfaces](generics/details.md#implementing-interfaces)
> -   Proposal
>     [#553: Generics details part 1](https://github.com/carbon-language/carbon-lang/pull/553)
> -   Proposal
>     [#731: Generics details 2: adapters, associated types, parameterized interfaces](https://github.com/carbon-language/carbon-lang/pull/731)
> -   Proposal
>     [#624: Coherence: terminology, rationale, alternatives considered](https://github.com/carbon-language/carbon-lang/pull/624)
> -   Proposal
>     [#990: Generics details 8: interface default and final members](https://github.com/carbon-language/carbon-lang/pull/990)
> -   Proposal
>     [#1084: Generics details 9: forward declarations](https://github.com/carbon-language/carbon-lang/pull/1084)

### Combining constraints

A function can require calling types to implement multiple interfaces by
combining them using an ampersand (`&`):

```carbon
fn PrintMin[T:! Ordered & Printable](x: T, y: T) {
  // Can compare since type `T` implements `Ordered`.
  if (x <= y) {
    // Can call `Print` since type `T` implements `Printable`.
    x.Print();
  } else {
    y.Print();
  }
}
```

The body of the function may call functions that are in either interface, except
for names that are members of both. In that case, use the
[compound member access syntax](generics/details.md#qualified-member-names-and-compound-member-access)
to qualify the name of the member, as in:

```carbon
fn DrawTies[T:! Renderable & GameResult](x: T) {
  if (x.(GameResult.Draw)()) {
    x.(Renderable.Draw)();
  }
}
```

> References:
>
> -   [Combining interfaces by anding type-of-types](generics/details.md#combining-interfaces-by-anding-type-of-types)
> -   Question-for-leads issue
>     [#531: Combine interfaces with `+` or `&`](https://github.com/carbon-language/carbon-lang/issues/531)
> -   Proposal
>     [#553: Generics details part 1](https://github.com/carbon-language/carbon-lang/pull/553)

### Associated types

An associated type is a type member of an interface whose value is determined by
the implementation of that interface for a specific type. These values are set
to compile-time values in implementations, and so use the
[`:!` generic syntax](#checked-and-template-parameters) inside a
[`let` declaration](#constant-let-declarations) without an initializer. This
allows types in the signatures of functions in the interface to vary. For
example, an interface describing a
[stack](<https://en.wikipedia.org/wiki/Stack_(abstract_data_type)>) might use an
associated type to represent the type of elements stored in the stack.

```
interface StackInterface {
  let ElementType:! Movable;
  fn Push[addr me: Self*](value: ElementType);
  fn Pop[addr me: Self*]() -> ElementType;
  fn IsEmpty[addr me: Self*]() -> bool;
}
```

Then different types implementing `StackInterface` can specify different type
values for the `ElementType` member of the interface using a `where` clause:

```carbon
class IntStack {
  impl as StackInterface where .ElementType == i32 {
    fn Push[addr me: Self*](value: i32);
    // ...
  }
}

class FruitStack {
  impl as StackInterface where .ElementType == Fruit {
    fn Push[addr me: Self*](value: Fruit);
    // ...
  }
}
```

> References:
>
> -   [Generics: Associated types](generics/details.md#associated-types)
> -   Proposal
>     [#731: Generics details 2: adapters, associated types, parameterized interfaces](https://github.com/carbon-language/carbon-lang/pull/731)
> -   Proposal
>     [#1013: Generics: Set associated constants using `where` constraints](https://github.com/carbon-language/carbon-lang/pull/1013)

### Generic entities

Many Carbon entities, not just functions, may be made generic by adding
[checked or template parameters](#checked-and-template-parameters).

#### Generic Classes

Classes may be defined with an optional explicit parameter list. All parameters
to a class must be generic, and so defined with `:!`, either with or without the
`template` prefix. For example, to define a stack that can hold values of any
type `T`:

```carbon
class Stack(T:! Type) {
  fn Push[addr me: Self*](value: T);
  fn Pop[addr me: Self*]() -> T;

  var storage: Array(T);
}

var int_stack: Stack(i32);
```

In this example:

-   `Stack` is a type parameterized by a type `T`.
-   `T` may be used within the definition of `Stack` anywhere a normal type
    would be used.
-   `Array(T)` instantiates generic type `Array` with its parameter set to `T`.
-   `Stack(i32)` instantiates `Stack` with `T` set to `i32`.

The values of type parameters are part of a type's value, and so may be deduced
in a function call, as in this example:

```carbon
fn PeekTopOfStack[T:! Type](s: Stack(T)*) -> T {
  var top: T = s->Pop();
  s->Push(top);
  return top;
}

// `int_stack` has type `Stack(i32)`, so `T` is deduced to be `i32`.
PeekTopOfStack(&int_stack);
```

> References:
>
> -   [Generic or parameterized types](generics/details.md#parameterized-types)
> -   Proposal
>     [#1146: Generic details 12: parameterized types](https://github.com/carbon-language/carbon-lang/pull/1146)

#### Generic choice types

[Choice types](#choice-types) may be parameterized similarly to classes:

```carbon
choice Result(T:! Type, Error:! Type) {
  Success(value: T),
  Failure(error: Error)
}
```

#### Generic interfaces

Interfaces are always parameterized by a `Self` type, but in some cases they
will have additional parameters.

```carbon
interface AddWith(U:! Type);
```

Interfaces without parameters may only be implemented once for a given type, but
a type can have distinct implementations of `AddWith(i32)` and
`AddWith(BigInt)`.

Parameters to an interface _determine_ which implementation is selected for a
type, in contrast to [associated types](#associated-types) which are _determined
by_ the implementation of an interface for a type.

> References:
>
> -   [Generic or parameterized interfaces](generics/details.md#parameterized-interfaces)
> -   Proposal
>     [#731: Generics details 2: adapters, associated types, parameterized interfaces](https://github.com/carbon-language/carbon-lang/pull/731)

#### Generic implementations

An `impl` declaration may be parameterized by adding `forall [`_generic
parameter list_`]` after the `impl` keyword introducer, as in:

```carbon
external impl forall [T:! Printable] Vector(T) as Printable;
external impl forall [Key:! Hashable, Value:! Type]
    HashMap(Key, Value) as Has(Key);
external impl forall [T:! Ordered] T as PartiallyOrdered;
external impl forall [T:! ImplicitAs(i32)] BigInt as AddWith(T);
external impl forall [U:! Type, T:! As(U)]
    Optional(T) as As(Optional(U));
```

Generic implementations can create a situation where multiple `impl` definitions
apply to a given type and interface query. The
[specialization](generics/details.md#lookup-resolution-and-specialization) rules
pick which definition is selected. These rules ensure:

-   Implementations have [coherence](generics/terminology.md#coherence), so the
    same implementation is always selected for a given query.
-   Libraries will work together as long as they pass their separate checks.
-   A generic function can assume that some impl will be successfully selected
    if it can see an impl that applies, even though another more specific impl
    may be selected.

Implementations may be marked [`final`](generics/details.md#final-impls) to
indicate that they may not be specialized, subject to
[some restrictions](generics/details.md#libraries-that-can-contain-final-impls).

> References:
>
> -   [Generic or parameterized impls](generics/details.md#parameterized-impls)
> -   Proposal
>     [#624: Coherence: terminology, rationale, alternatives considered](https://github.com/carbon-language/carbon-lang/pull/624)
> -   Proposal
>     [#920: Generic parameterized impls (details 5)](https://github.com/carbon-language/carbon-lang/pull/920)
> -   Proposal
>     [#983: Generics details 7: final impls](https://github.com/carbon-language/carbon-lang/pull/983)

### Other features

Carbon generics have a number of other features, including:

-   [Named constraints](generics/details.md#named-constraints) may be used to
    disambiguate when combining two interfaces that have name conflicts. Named
    constraints may be implemented and otherwise used in place of an interface.
-   [Template constraints](generics/details.md#named-constraints) are a kind of
    named constraint that can contain structural requirements. For example, a
    template constraint could match any type that has a function with a specific
    name and signature without any explicit declaration that the type implements
    the constraint. Template constraints may only be used as requirements for
    template parameters.
-   An [adapter type](generics/details.md#adapting-types) is a type with the
    same data representation as an existing type, so you may cast between the
    two types, but can implement different interfaces or implement interfaces
    differently.
-   Additional requirements can be placed on the associated types of an
    interface using
    [`where` constraints](generics/details.md#where-constraints).
-   [Implied constraints](generics/details.md#implied-constraints) allows some
    constraints to be deduced and omitted from a function signature.
-   [Dynamic erased types](generics/details.md#runtime-type-fields) can hold any
    value with a type implementing an interface, and allows the functions in
    that interface to be called using
    [dynamic dispatch](https://en.wikipedia.org/wiki/Dynamic_dispatch), for some
    interfaces marked "`dyn`-safe".
-   [Variadics](generics/details.md#variadic-arguments) supports variable-length
    parameter lists.

> References:
>
> -   [Generics details](generics/details.md)
> -   Proposal
>     [#553: Generics details part 1](https://github.com/carbon-language/carbon-lang/pull/553)
> -   Proposal
>     [#731: Generics details 2: adapters, associated types, parameterized interfaces](https://github.com/carbon-language/carbon-lang/pull/731)

> -   Proposal
>     [#818: Constraints for generics (generics details 3)](https://github.com/carbon-language/carbon-lang/pull/818)

### Generic type equality and `observe` declarations

Determining whether two types must be equal in a generic context is in general
undecidable, as
[has been shown in Swift](https://forums.swift.org/t/swift-type-checking-is-undecidable/39024).

To make compilation fast, the Carbon compiler will limit its search to a depth
of 1, only identifying types as equal if there is an explicit declaration that
they are equal in the code, such as in a
[`where` constraint](generics/details.md#where-constraints). There will be
situations where two types must be equal as the result of combining these facts,
but the compiler will return a type error since it did not realize they are
equal due to the limit of the search. An
[`observe`...`==` declaration](generics/details.md#observe-declarations) may be
added to describe how two types are equal, allowing more code to pass type
checking.

An `observe` declaration showing types are equal can increase the set of
interfaces the compiler knows that a type implements. It is also possible that
knowing a type implements one interface implies that it implements another, from
an
[interface requirement](generics/details.md#interface-requiring-other-interfaces)
or [generic implementation](#generic-implementations). An `observe`...`is`
declaration may be used to
[observe that a type implements an interface](generics/details.md#observing-a-type-implements-an-interface).

> References:
>
> -   [Generics: `observe` declarations](generics/details.md#observe-declarations)
> -   [Generics: Observing a type implements an interface](generics/details.md#observing-a-type-implements-an-interface)
> -   Proposal
>     [#818: Constraints for generics (generics details 3)](https://github.com/carbon-language/carbon-lang/pull/818)
> -   Proposal
>     [#1088: Generic details 10: interface-implemented requirements](https://github.com/carbon-language/carbon-lang/pull/1088)

### Operator overloading

Uses of an operator in an [expression](#expressions) is translated into a call
to a method of an interface. For example, if `x` has type `T` and `y` has type
`U`, then `x + y` is translated into a call to `x.(AddWith(U).Op)(y)`. So
overloading of the `+` operator is accomplished by implementing interface
`AddWith(U)` for type `T`. In order to support
[implicit conversion](expressions/implicit_conversions.md) of the first operand
to type `T` and the second argument to type `U`, add the `like` keyword to both
types in the `impl` declaration, as in:

```carbon
external impl like T as AddWith(like U) where .Result == V {
  // `Self` is `T` here
  fn Op[me: Self](other: U) -> V { ... }
}
```

When the operand types and result type are all the same, this is equivalent to
implementing the `Add` interface:

```carbon
external impl T as Add {
  fn Op[me: Self](other: Self) -> Self { ... }
}
```

The interfaces that correspond to each operator are given by:

-   [Arithmetic](expressions/arithmetic.md#extensibility):
    -   `-x`: `Negate`
    -   `x + y`: `Add` or `AddWith(U)`
    -   `x - y`: `Sub` or `SubWith(U)`
    -   `x * y`: `Mul` or `MulWith(U)`
    -   `x / y`: `Div` or `DivWith(U)`
    -   `x % y`: `Mod` or `ModWith(U)`
-   [Bitwise and shift operators](expressions/bitwise.md#extensibility):
    -   `^x`: `BitComplement`
    -   `x & y`: `BitAnd` or `BitAndWith(U)`
    -   `x | y`: `BitOr` or `BitOrWith(U)`
    -   `x ^ y`: `BitXor` or `BitXorWith(U)`
    -   `x << y`: `LeftShift` or `LeftShiftWith(U)`
    -   `x >> y`: `RightShift` or `RightShiftWith(U)`
-   Comparison:
    -   `x == y`, `x != y` overloaded by implementing
        [`Eq` or `EqWith(U)`](expressions/comparison_operators.md#equality)
    -   `x < y`, `x > y`, `x <= y`, `x >= y` overloaded by implementing
        [`Ordered` or `OrderedWith(U)`](expressions/comparison_operators.md#ordering)
-   Conversion:
    -   `x as U` is rewritten to use the
        [`As(U)`](expressions/as_expressions.md#extensibility) interface
    -   Implicit conversions use
        [`ImplicitAs(U)`](expressions/implicit_conversions.md#extensibility)
-   **TODO:** Dereference: `*p`
-   **TODO:** Indexing: `a[3]`
-   **TODO:** Function call: `f(4)`

The
[logical operators can not be overloaded](expressions/logical_operators.md#overloading).

> References:
>
> -   [Operator overloading](generics/details.md#operator-overloading)
> -   Proposal
>     [#702: Comparison operators](https://github.com/carbon-language/carbon-lang/pull/702)
> -   Proposal
>     [#820: Implicit conversions](https://github.com/carbon-language/carbon-lang/pull/820)
> -   Proposal
>     [#845: as expressions](https://github.com/carbon-language/carbon-lang/pull/845)
> -   Question-for-leads issue
>     [#1058: How should interfaces for core functionality be named?](https://github.com/carbon-language/carbon-lang/issues/1058)
> -   Proposal
>     [#1083: Arithmetic expressions](https://github.com/carbon-language/carbon-lang/pull/1083)
> -   Proposal
>     [#1191: Bitwise operators](https://github.com/carbon-language/carbon-lang/pull/1191)
> -   Proposal
>     [#1178: Rework operator interfaces](https://github.com/carbon-language/carbon-lang/pull/1178)

#### Common type

There are some situations where the common type for two types is needed:

-   A [conditional expression like `if c then t else f`](expressions/if.md)
    returns a value with the common type of `t` and `f`.
-   If there are multiple parameters to a function with a type parameter, it
    will be set to the common type of the corresponding arguments, as in:

    ```carbon
    fn F[T:! Type](x: T, y: T);

    // Calls `F` with `T` set to the
    // common type of `G()` and `H()`:
    F(G(), H());
    ```

-   The inferred return type of a function with
    [`auto` return type](#auto-return-type) is the common type of its `return`
    statements.

The common type is specified by implementing the `CommonTypeWith` interface:

```carbon
// Common type of `A` and `B` is `C`.
impl A as CommonTypeWith(B) where .Result == C { }
```

The common type is required to be a type that both types have an
[implicit conversion](expressions/implicit_conversions.md) to.

> References:
>
> -   [`if` expressions](expressions/if.md#finding-a-common-type)
> -   Proposal
>     [#911: Conditional expressions](https://github.com/carbon-language/carbon-lang/pull/911)
> -   Question-for-leads issue
>     [#1077: find a way to permit impls of CommonTypeWith where the LHS and RHS type overlap](https://github.com/carbon-language/carbon-lang/issues/1077)

## Bidirectional interoperability with C/C++

> **TODO:** Needs a detailed design and a high level summary provided inline.

> References:
>
> -   [Bidirectional interoperability with C/C++](interoperability/README.md)
> -   Proposal
>     [#175: C++ interoperability goals](https://github.com/carbon-language/carbon-lang/pull/175)
>
> **TODO:** References need to be evolved.

## Unfinished tales

### Safety

Carbon's premise is that C++ users can't give up performance to get safety. Even
if some isolated users can make that tradeoff, they share code with
performance-sensitive users. Any path to safety must preserve performance of C++
today. This rules out garbage collection, and many other options. The only well
understood mechanism of achieving safety without giving up performance is
compile-time safety. The leading example of how to achieve this is Rust.

The difference between Rust's approach and Carbon's is that Rust starts with
safety and Carbons starts with migration. Rust supports interop with C, and
there is ongoing work to improve the C++-interop story and develop migration
tools. However, there is a large gap in programming models between the two
languages, generally requiring a revision to the architecture. So, thus far the
common pattern in the Rust community is to "rewrite it in Rust"
([1](https://deprogrammaticaipsum.com/the-great-rewriting-in-rust/),
[2](https://unhandledexpression.com/rust/2017/07/10/why-you-should-actually-rewrite-it-in-rust.html),
[3](https://transitiontech.ca/random/RIIR)). Carbon's approach is to focus on
migration from C++, including seamless interop, and then incrementally improve
safety.

The first impact on Carbon's design to support its safety strategy are the
necessary building blocks for this level of compile-time safety. We look at
existing languages like Rust and Swift to understand what fundamental
capabilities they ended up needing. The two components that stand out are:

-   Expanded type system that includes more semantic information.
-   More pervasive use of type system abstractions (typically generics).

For migrating C++ code, we also need the ability to add features and migrate
code to use those new features incrementally and over time. This requires
designing the language with evolution baked in on day one. This impacts a wide
range of features:

-   At the lowest level, a simple and extensible syntax and grammar.
-   Tools and support for adding and removing APIs.
-   Scalable migration strategies, including tooling support.

Rust shows the value of expanded semantic information in the type system such as
precise lifetimes. This is hard to do in C++ since it has too many kinds of
references and pointers, which increases the complexity in the type system
multiplicatively. Carbon is attempting to compress C++'s type variations into
just values and [pointers](#pointer-types).

Rust also shows the value of functions parameterized by lifetimes. Since
lifetimes are only used to establish safety properties of the code, there is no
reason to pay the cost of monomorphization for those parameters. So we need a
[generics system](#generics) that can reason about code before it is
instantiated, unlike C++ templates.

In conclusion, there are two patterns in how Carbon diverges from C++:

-   Simplify and removing things to create space for new safety features. This
    trivially requires breaking backwards compatibility.
-   Re-engineer foundations to model and enforce safety. This has complex and
    difficulty in C++ without first simplifying the language.

This leads to Carbon's incremental path to safety:

-   Keep your performance, your existing codebase, and your developers.
-   Adopt Carbon through a scalable, tool-assisted migration from C++.
-   Address initial, easy safety improvements starting day one.
-   Shift the Carbon code onto an incremental path towards memory safety over
    the next decade.

> References: [Safety strategy](/docs/project/principles/safety_strategy.md)

### Pattern matching as function overload resolution

> **TODO:** References need to be evolved. Needs a detailed design and a high
> level summary provided inline.

> References: [Pattern matching](pattern_matching.md)

### Lifetime and move semantics

> **TODO:**

### Metaprogramming

> **TODO:** References need to be evolved. Needs a detailed design and a high
> level summary provided inline.

Carbon provides metaprogramming facilities that look similar to regular Carbon
code. These are structured, and do not offer arbitrary inclusion or
preprocessing of source text such as C/C++ does.

> References: [Metaprogramming](metaprogramming.md)

### Execution abstractions

Carbon provides some higher-order abstractions of program execution, as well as
the critical underpinnings of such abstractions.

#### Abstract machine and execution model

> **TODO:**

#### Lambdas

> **TODO:**

#### Co-routines

> **TODO:**