RFC-011: Дизайн системы дженериков - абстракции с нулевой стоимостью и замена макросов

Резюме

Данный документ определяет дизайн системы дженериков языка YaoXiang, реализующий абстракции с нулевой стоимостью посредством мощных возможностей дженериков, уменьшающий зависимость от макросов за счёт оптимизаций времени компиляции и предоставляющий механизм удаления мёртвого кода.

Ключевые решения в дизайне:

Унифицированный синтаксис сигнатур: (T: Type, R: Type) -> ... — параметры дженериков и обычные параметры унифицированы
Механизм самоописания Type: Type — сущность уровня языка, позиция Type в сигнатуре автоматически выводится и заполняется
Ограничения типов: T: Dup + Add — множественные ограничения, ограничения на типы функций
Ассоциированные типы: Iterator: (Item: Type) -> Type = { next: () -> Option(Item), has_next: () -> Bool }
Дженерики времени компиляции: значения-параметры дженериков N: Int, инстанцирование константами времени компиляции
Условные типы: If: (C: Bool, T: Type, E: Type) -> Type — вычисления на уровне типов, семейства типов

Ценность:

Абстракции с нулевой стоимостью: мономорфизация на этапе компиляции, без накладных расходов во время выполнения
Удаление мёртвого кода: анализ графа инстанцирования + оптимизации LLVM
Замена макросов: дженерики заменяют 90% сценариев использования макросов
Безопасность типов: проверка на этапе компиляции, IDE-дружественность
Явное лучше неявного: самоописание Type, автоматический вывод компилятора

Справочные документы

Дизайн данного документа основан на следующих документах:

Документ	Связь	Описание
RFC-010: Унифицированный синтаксис типов	Синтаксис	Синтаксис дженериков интегрирован с унифицированной моделью `name: type = value`
RFC-010: Унифицированный синтаксис типов	Вызовы	Раздел 6: синтаксис вызовов дженериков — унифицированное применение `()`, `[]` удалены
RFC-009: Модель владения	Система типов	Естественное сочетание семантики Move и дженериков
RFC-024: Семантика рантайма конкурентности на основе spawn	Модель исполнения	Анализ DAG и проверка типов дженериков
RFC-008: Модель рантайма	Архитектура компилятора	Стратегии мономорфизации дженериков и оптимизаций времени компиляции
Идея вселенной типов	Теоретическое ядро	Иерархическая модель вселенных типов и дизайн типов, зависящих от значений
RFC-027: Предикаты времени компиляции и унифицированная статическая верификация	Проверка завершимости	Автоматический синтез мер и гарантии вычислений времени компиляции

Идея вселенной типов и типы, зависящие от значений

Система дженериков YaoXiang построена на идее вселенной типов — ментальной модели, которая унифицирует все концепции языка в многоуровневую структуру, ключевая инновация — возведение типов, зависящих от значений, в полноправные граждане уровня Type2.

Что такое типы, зависящие от значений?

Тип, зависящий от значений — это тип, который зависит от одного или нескольких значений (а не только от других типов). Эти значения могут быть вычислены на этапе компиляции, тем самым предоставляя гарантии безопасности типов уже на стадии компиляции.

yaoxiang

# Традиционные дженерики: параметры-типы
List: (T: Type) -> Type

# Тип, зависящий от значений: параметры-значения
Array: (T: Type, N: Int) -> Type  # Тип массива зависит от значения длины N
Matrix: (T: Type, Rows: Int, Cols: Int) -> Type  # Тип матрицы зависит от количества строк и столбцов

Именование контейнеров по уровням

На уровне языка существует три концепции контейнеров; местонахождение информации о длине — их фундаментальное отличие:

Тип	Длина	Семантика	Базовая реализация
`Array(T, N)`	Тип	Фиксированной длины, N зашит в тип	Базовый примитив (стек/inline в приоритете)
`Vec(T)`	Значение рантайма	Буфер сырых данных с длиной в рантайме, может расти	Базовый примитив (непрерывный буфер в куче)
`List(T)`	Значение рантайма	Тип стандартной библиотеки	Библиотека: `{ data: Vec(T), length: Int }`

Принцип разделения:

Array(T, N) — единственная форма, вносящая длину в тип — длина является константой времени компиляции, поэтому возможен отказ на этапе компиляции при ошибках границ (a[5] при a: Array(Int, 3) сразу даёт ошибку компиляции, см. раздел «Проверка измерений времени компиляции» ниже).
Vec(T) — минимальный фундамент с длиной в рантайме — предоставляет только четыре вещи: «уметь выделить, получить длину, читать/писать, расширять». Никакой политики ёмкости, фактора роста, сжатия — ничего этого. Это сырьё для построения других контейнеров.
List(T) — тип библиотеки, а не примитив — определяется в самом YaoXiang в std.list ({ data: Vec(T), length: Int }), наравне с пользовательскими дженерик-записями. Вся политика расширяемой семантики (когда расширять, на сколько, можно ли разделять) — в библиотеке, компилятор не участвует.

Форма конструктора Vec(T) (два уровня: сначала параметры типов, затем параметры конструктора):

yaoxiang

# Пустая конструкция — длина 0, элементы добавляются позже
v = Vec(Int)()

# Конструкция с элементами — длина определяется количеством элементов
w = Vec(Int)(1, 2, 3)          # длина 3

# Выделение слотов — выделяет n нулевых слотов
buf = Vec(Int)(len=64)         # длина 64, все элементы — нулевые значения

Выделение слотов использует именованный синтаксис (len=), а не позиционный: позиционная запись с одним целым неоднозначна с «вектором с одним элементом» (Vec(Int)(64) невозможно отличить «длина 64» от «содержит один элемент 64»). Это согласуется с унифицированными правилами конструкторов дженериков: именованные аргументы связываются по имени и не зависят от позиционного вывода.
Это единственный примитив, необходимый List для расширения — List при необходимости выделяет новые слоты и перемещает элементы:
yaoxiang
new_data = Vec(T)(len=self.data.length * 2)
Когда расширять, на сколько, нужно ли сжимать — решает List. Vec не занимается политикой ёмкости.

Снизу вверх производительность уменьшается, гибкость растёт: Array > Vec > List.

Обоснование имён: Vec/vector в основных языках (Rust/C++) обозначают расширяемые последовательности с длиной в рантайме; Array — фиксированной длины.

Ключевые преимущества типов, зависящих от значений

По сравнению с традиционными дженериками, типы YaoXiang, зависящие от значений, обладают следующими ключевыми преимуществами:

Характеристика	Традиционные дженерики (C++/Rust)	Типы YaoXiang, зависящие от значений
Значения, от которых зависят типы	Только параметры-типы	Любые значения, включая результаты вызовов функций
Вычисления времени компиляции	C++ — ручная спецификация шаблонов, Rust — нет	Автоматическое вычисление, гарантия завершимости
Вычисления на уровне типов	Метапрограммирование шаблонов (сложно/опасно)	Унифицированный движок вычислений на уровне типов
Безопасность типов	C++ — нет, Rust — ограниченная	Полная безопасность, проверка на этапе компиляции
Проверка измерений	Проверка в рантайме или ручная спецификация	Автоматическая проверка на этапе компиляции, без накладных расходов

Иерархия вселенных типов и типы, зависящие от значений

Идея вселенной типов разделяет концепции языка по семантическим ролям на различные уровни, типы, зависящие от значений, расположены на уровне Type2:

Уровень	Роль	Примеры
Type-1	Значения	`42`, `factorial(5)`, сама функция
Type0	Ключевое слово метатипа	`Type`
Type1	Конкретные типы	`Int`, `String`, `Array(Int, 3)`
Type2	Функции/конструкторы типов/типы, зависящие от значений	`add: (Int, Int) -> Int`, `Array: (T: Type, N: Int) -> Type`, `Matrix: (T: Type, Rows: Int, Cols: Int) -> Type`

Ключевое решение: функции, конструкторы типов и типы, зависящие от значений, на уровне Type2 имеют унифицированный синтаксис — форму (params) -> result:

Обычная функция: (Int, Int) -> Int → результат — значение
Конструктор типа: (T: Type) -> Type → результат — тип
Тип, зависящий от значений: (T: Type, N: Int) -> Type → результат — тип, зависящий от значения N

Изоморфизм Карри-Говарда: это единство — не совпадение. Изоморфизм Карри-Говарда утверждает «типы суть propositions, программы суть доказательства» — тип функции A → B соответствует логической импликации «если A, то B», дженерик (T: Type) -> Type соответствует квантору всеобщности «для всех типов T», тип, зависящий от значений (n: Int) -> Type соответствует «для каждого целого n существует тип». YaoXiang объединяет функции, конструкторы типов и типы, зависящие от значений, на уровне Type2, по существу объединяя «доказательство» и «вычисление» в одну концепцию — конструктивное доказательство. Это прямое воплощение изоморфизма Карри-Говарда в дизайне языка: одна форма ((params) -> result) несёт и логические propositions, и процесс вычисления.

Гарантия детерминированности времени компиляции

Идея вселенной типов YaoXiang требует: всё на уровне Type определяется на этапе компиляции.

yaoxiang

# Пример проверки измерений времени компиляции
Matrix: (T: Type, Rows: Int, Cols: Int) -> Type = {
    data: Array(Array(T, Cols), Rows),
    # Проверка времени компиляции: измерения должны быть положительными
    _assert: Assert(Rows > 0),
    _assert: Assert(Cols > 0),
}

# Создание единичной матрицы 3x3 — завершается на этапе компиляции
identity: (T: Add + Zero + One, N: Int) -> ((size: N) -> Matrix(T, N, N)) = {
    matrix = Matrix(T, N, N)()
    # ...
}

# Вычисление времени компиляции: factorial(3) = 6, размер массива определяется на этапе компиляции
arr: Array(Int, factorial(3)) = Array(Int, 6)()

Компилятор автоматически:

Обнаруживает вызовы функций в позициях типов
Выполняет проверку завершимости на этапе компиляции (см. механизм проверки завершимости ниже)
Выполняет вычисление на этапе компиляции
Встраивает результат в генерируемый тип

Сценарии применения типов, зависящих от значений

Проверка измерений времени компиляции

yaoxiang

# Умножение матриц: проверка соответствия измерений на этапе компиляции
multiply: (T: Add + Multiply + Zero,
           Rows: Int, Cols: Int, M: Int) -> ((
    a: Matrix(T, Rows, Cols),
    b: Matrix(T, Cols, M)
) -> Matrix(T, Rows, M)) = {
    # Проверка времени компиляции: a.Cols == b.Rows, иначе ошибка компиляции
    result = Matrix(T, Rows, M)()
    # ...
}

# Ошибка перехватывается на этапе компиляции:
# multiply(matrix_2x3, matrix_4x2)  # Ошибка компиляции: 2 != 4

Типобезопасный размер массива

yaoxiang

# Размер массива — константа времени компиляции
Array: (T: Type, N: Int) -> Type = {
    data: Array(T, N),
    length: N,
}

# N — константа времени компиляции, может использоваться для вычислений на уровне типов
first_three: Array(Int, 3) = Array(Int, 3)(1, 2, 3)
# first_three.length == 3 (известно на этапе компиляции)

Цель покрытия ошибок границ на этапе компиляции

Пояснение о состоянии реализации: типы контейнеров деспециализированы — Array(T, N) является конструктором const-дженериков, контекст литералов и предикат членства in уже реализованы. N в точке привязки литерала Array(T, N) и тип элемента принудительно проверяются на этапе компиляции (E1002), N достоверен — механизмы данного раздела могут строиться на утверждении «аннотация N == длина в рантайме». В текущем состоянии ошибки выхода за границы [] (E6003) и отсутствующего ключа Dict (E6008) являются переходным состоянием с ошибками в рантайме; типы, зависящие от значений, в данном разделе — это целевой механизм переноса этих ошибок границ на этап компиляции:
const-индексация: a[5] (5 — константа времени компиляции) при a: Array(Int, 3) сразу отвергается на этапе компиляции;
индексация значением: a[i] требует предусловия i < len(a), доказываемого контрактом типа, зависящего от значений;
предикат in — основа предусловий логики Хоара: n in 1..10, x in some_set — доказуемые propositions на этапе компиляции.
Полный дизайн refinement-типов будет дополнен данным разделом при реализации.

Условные типы

yaoxiang

# If на уровне типов
If: (C: Bool, T: Type, E: Type) -> Type = match C {
    True => T,
    False => E,
}

# Семейство типов
AsString: (T: Type) -> Type = match T {
    Int => String,
    Float => String,
    Bool => String,
    _ => String,
}

Дженерик-функции

yaoxiang

# map: дженерик-функция, параметры типов T, R определяются на этапе компиляции
map: (T: Type, R: Type) -> (
    (list: List(T), f: (x: T) -> R) -> List(R)
) = (list, f) => {
    result = List(R)()
    for x in list {
        result.push(f(x))
    }
    return result
}

# Использование полностью прозрачно, типы выводятся автоматически
numbers = List(Int)()   # Двухуровневая форма конструкции значения (см. §9.1); элементы заполняются через push
numbers.push(1)
numbers.push(2)
numbers.push(3)
doubled = map(numbers, (x) => x * 2)  # Выводится как map[Int, Int]

Сравнение с другими языками

Характеристика	Шаблоны C++	Дженерики Rust	GADT в Haskell	YaoXiang
Параметры-типы	✅	✅	✅	✅
Типы, зависящие от значений	❌	❌	✅	✅
Вычисления времени компиляции	Инстанцирование шаблонов	❌	✅	✅
Гарантия завершимости	❌	❌	❌ (опасно)	✅ (автоматический поиск мер + явные меры, RFC-027)
Безопасность типов	❌ (раскрытие макросов)	✅	✅	✅
Унифицированный синтаксис	❌	❌	❌	✅
Проверка измерений времени компиляции	Ручная спецификация	Проверка в рантайме	Семейства типов	Автоматическая проверка на этапе компиляции
Полуавтоматические аннотации завершимости (decreases/invariant)	❌	❌	❌	❌ (нет синтаксиса аннотаций; явные меры записываются в позиции типов)

Механизм проверки завершимости (унифицирован с RFC-027)

Вычисление типов, зависящих от значений, на этапе компиляции должно гарантировать завершимость, иначе система типов попадёт в бесконечный цикл. Проверка завершимости выполняется конвейером доказательств RFC-027 в режиме полной автоматики в первую очередь — компилятор сначала автоматически ищет меры; рекурсии/циклы, для которых меры найдены, проходят; если мера не найдена и явная мера не задана — выдаётся ошибка компиляции (RFC-027 §6.9 задаёт явную меру в позиции типа как запасной вариант). Синтаксису аннотаций не оставлено лазеек: //! decreases, /*! invariant !*/ из RFC-022 устарели вместе с RFC-022, спецификация — это сама аннотация типа.

Критерий запуска (RFC-027 §7): обязательство завершимости срабатывает от refinement-типов — как только тип подвергается refinement, включается режим верификации. Не подвергнутые refinement обычные типы не входят в режим верификации и не порождают обязательств завершимости.

Проверка завершимости рекурсивных функций

Для рекурсивных функций с refinement-сигнатурой компилятор проверяет, что аргументы рекурсивного вызова строго убывают на каждом пути рекурсии (RFC-027 §6.7). Никаких спецификационных комментариев не требуется:

yaoxiang

# Рекурсия с refinement-сигнатурой: без //! requires/ensures/decreases, компилятор автоматически ищет убывание
factorial: (n: NonNegative(n)) -> Int = {
    if n <= 1 { return 1 }
    return n * factorial(n - 1)  # Поиск компилятора: n-1 < n → убывает → завершается
}

Сценарий	Поведение
Компилятор находит убывание (например, `n-1`)	Проходит
Убывание не найдено, но мера задана в позиции типа (§6.9)	SMT решает, если выполняется — проходит
Убывание не найдено, явная мера отсутствует / мера опровергнута SMT	Ошибка компиляции
Сигнатура без refinement (не входит в режим верификации)	Обязательство завершимости не генерируется

Проверка завершимости циклов

Циклам не нужны аннотации : Invariant(...) или : decreases(...). Аннотации refinement-типов на переменных (например, UpTo(n)) одновременно задают инвариант цикла и границу меры; компилятор перебирает четыре стратегии поиска меры по приоритету и останавливается на первой найденной (RFC-027 §6.1–6.5):

Автоматический синтез линейной ранговой функции — извлечение границ переменных из аннотаций типов, перебор линейных комбинаций, верификация SMT m ≥ 0 и m' < m на всех путях
Подсчёт нарушений предиката (экспериментально) — извлечение violation_count из определения целевого типа (например, Sorted), покрытие соседних обменов/перемещений
Паттерны ограниченного инкремента/декремента — v += const → мера upper - v (вырождение стратегии 1, самый быстрый путь)
Шаблон мультипликативной меры — v *= const (const > 1) → мера ceil(log_const(upper / v))

yaoxiang

sum: (arr: Array(Int, n)) -> Int = {
    mut i: UpTo(arr.len) = 0   # Аннотация типа задаёт верхнюю границу arr.len и нижнюю 0 → вход в режим верификации
    while i < arr.len {
        # Автоматический поиск компилятора: мера arr.len - i, на каждой итерации строго убывает на 1 → завершимость доказана
        s += arr[i]; i += 1
    }
    return s
}

Если поиск не дал результата, циклу можно дать имя и задать меру в позиции типа (RFC-027 §6.9):

yaoxiang

loop: (n: Int) -> Int = {
    mut i = 0
    acc: Terminates(n - i) = while i < n { i = i + 1 }
    return acc
}

Рабочий процесс проверки завершимости

┌─────────────────────────────────────────────────────────────┐
│  Этап проверки типов                                         │
│  Встречается позиция с refinement-типом (уточнение параметра,│
│  возврата, переменной)                                       │
└─────────────────────────┬───────────────────────────────────┘
                          ▼
┌─────────────────────────────────────────────────────────────┐
│  1. Проверка завершимости (конвейер доказательств RFC-027,  │
│     в первую очередь полная автоматика)                      │
│     - Рекурсивные функции: проверка строгого убывания        │
│       аргументов на каждом пути рекурсии                     │
│     - Циклы: четыре стратегии поиска меры (линейный ранг/   │
│       подсчёт нарушений/ограниченные паттерны/                │
│       мультипликативные), верификация SMT убывания           │
│     - Мера не найдена → программист может задать меру в      │
│       позиции типа (Terminates)                              │
│     - Нет меры / мера опровергнута SMT → ошибка компиляции   │
│       (жёсткая граница)                                      │
└─────────────────────────┬───────────────────────────────────┘
                          ▼
┌─────────────────────────────────────────────────────────────┐
│  2. Вычисление времени компиляции (выполняется встроенным    │
│     интерпретатором)                                         │
│     - Чистые функции: прямое вычисление                      │
│     - Побочные эффекты: ошибка компиляции (позиция типа     │
│       не должна иметь побочных эффектов)                     │
└─────────────────────────┬───────────────────────────────────┘
                          ▼
┌─────────────────────────────────────────────────────────────┐
│  3. Встраивание результата в тип                             │
│     - Array(Int, factorial(5)) → Array(Int, 120)             │
│     - Matrix(Float, 3, 3) → конкретный тип                   │
└─────────────────────────────────────────────────────────────┘

Преимущества

Безопасность: гарантируется неизбежная завершимость вычислений времени компиляции, предотвращается попадание системы типов в бесконечный цикл
Унификация: проверка завершимости и верификация корректности (генерация VC) разделяют один конвейер доказательств времени компиляции (RFC-027), нет отдельного синтаксиса спецификаций
Полная автоматика в первую очередь: компилятор автоматически ищет меры по аннотациям типов, доказуемое проходит; если не найдено — можно задать меру в позиции типа (Terminates), всё равно SMT решает — не зависит от ручного decreases от программиста

Мотивация

Зачем нужна сильная система дженериков?

Существующие системы дженериков в主流ных языках имеют ограничения:

Язык	Возможности дженериков	Проблема
Java	Ограниченные типы	Мономорфизация времени компиляции, без специализации
C#	Ограничения типов	Проверка типов в рантайме, накладные расходы
Rust	Дженерики + Trait	Сложная система Trait, крутая кривая обучения
C++	Шаблоны	Сложная специализация шаблонов, плохие сообщения об ошибках
YaoXiang	Типы, зависящие от значений	Типы могут зависеть от значений, проверка измерений времени компиляции, гарантия завершимости

Ключевые противоречия

Производительность vs гибкость: гибкость рантайма vs оптимизации времени компиляции
Сложность vs простота: мощная система типов vs удобство использования
Макросы vs дженерики: кодогенерация макросами vs типобезопасность дженериков
Зависимость от значений vs безопасность типов: традиционные дженерики не могут проверять измерения на этапе компиляции

Ключевые преимущества типов, зависящих от значений

Типы, зависящие от значений YaoXiang — ключевое преимущество по сравнению с традиционными дженериками:

Преимущество	Описание
Тип зависит от значения	`Array: (T: Type, N: Int) -> Type` — тип зависит от конкретного значения
Вычисления времени компиляции	Вызовы функций в позициях типов вычисляются на этапе компиляции, результат встраивается в тип
Проверка измерений	`Matrix(Float, 3, 3)` — измерения матрицы проверяются на этапе компиляции
Вычисления на уровне типов	Условные типы `If`, `Match` поддерживают вычисления на уровне типов
Гарантия завершимости	Проверка завершимости времени компиляции (автоматический синтез мер RFC-027) гарантирует завершимость вычислений

yaoxiang

# Проверки на этапе компиляции, невозможные в C++/Rust
matrix: Matrix(Float, factorial(3), factorial(2)) = ...
# Вычисление времени компиляции: factorial(3) = 6, factorial(2) = 2
# Тип: Matrix(Float, 6, 2)

# Несоответствие измерений перехватывается на этапе компиляции
identity: Matrix(Float, 3, 3) = ...
# multiply(matrix_2x3, identity_3x3)  # Ошибка компиляции: 2 != 3

Ценность системы дженериков

yaoxiang

# Пример: унифицированный дизайн API
# операция map для разных контейнерных типов

# Традиционный подход: отдельная реализация для каждого типа
map_int_array: (array: Vec(Int), f: Fn(Int) -> Int) -> Vec(Int) = ...
map_string_array: (array: Vec(String), f: Fn(String) -> String) -> Vec(String) = ...
map_int_list: (list: List(Int), f: Fn(Int) -> Int) -> List(Int) = ...
map_string_list: (list: List(String), f: Fn(String) -> String) -> List(String) = ...

# Подход с дженериками: одна дженерик-функция покрывает все типы
map: (T: Type, R: Type)(container: Container(T), f: Fn(T) -> R) -> Container(R) = {
    for item in container {
        result.push(f(item))
    }
    result
}

Цели дизайна

Основные цели

Абстракции с нулевой стоимостью — вызов дженерика эквивалентен вызову с конкретным типом
Удаление мёртвого кода — анализ на этапе компиляции, инстанцирование только используемых дженериков
Замена макросов — дженерики заменяют 90% сценариев использования макросов
Безопасность типов — проверка на этапе компиляции, без накладных расходов типов в рантайме
IDE-дружественность — интеллектуальные подсказки, понятные сообщения об ошибках
Типы, зависящие от значений — типы могут зависеть от значений, поддержка проверки измерений на этапе компиляции
Безопасность вычислений времени компиляции — гарантия завершимости вычислений через проверку завершимости (автоматический синтез мер RFC-027)

Принципы дизайна

Детерминированность времени компиляции: параметры дженериков определяются на этапе компиляции
Приоритет мономорфизации: генерация конкретного кода, без вызовов виртуальных функций
Управление через ограничения: ограничения типов управляют инстанцированием
Платформенные оптимизации: специализация для платформенно-специфических оптимизаций
Унификация вселенных типов: функции/конструкторы типов/типы, зависящие от значений, унифицированы на уровне Type2
Гарантия завершимости: вызовы функций в позициях типов должны доказывать завершимость

Предложение

1. Базовые дженерики

1.1 Параметры типов дженериков

Ключевое правило: определения типов дженериков должны явно аннотироваться : Type, иначе HM выведет их как функции.
Запись Значение
List: (T: Type) -> Type = {...} ✅ Конструктор типа
List = {...} ❌ HM выводит как функцию, не тип

Запись	Значение
`List: (T: Type) -> Type = {...}`	✅ Конструктор типа
`List = {...}`	❌ HM выводит как функцию, не тип

yaoxiang

# Определение дженерик-типа (должно иметь : Type)
Option: (T: Type) -> Type = {
    some: (T) -> Self,
    none: () -> Self
}

Result: (T: Type, E: Type) -> Type = {
    ok: (T) -> Self,
    err: (E) -> Self
}

List: (T: Type) -> Type = {
    data: Vec(T),
    length: Int,
    push: (self: List(T), item: T) -> Void,   # self — просто имя по соглашению, не ключевое слово
    get: (self: List(T), index: Int) -> Option(T),
}

# Дженерик-функция (без : Type, HM выводит как функцию)
map: (T: Type, R: Type) -> ((opt: Option(T), f: Fn(T) -> R) -> Option(R)) = {
    return match opt {
        some => Option.some(f(some)),
        none => Option.none(),
    }
}

# Ограничение дженерика (прямое выражение, в одной строке можно опустить return)
clone: (T: Clone)(value: T) -> T = value.clone()

# Несколько параметров типов
combine: (T: Type, U: Type) -> ((a: T, b: U) -> (T, U)) = (a, b)

Синтаксис вызова дженерик-функций

1.1 Унифицированный синтаксис сигнатур

yaoxiang

# Дженерик-функции используют унифицированный синтаксис сигнатур (T: Type, R: Type)
map: (T: Type, R: Type) -> ((list: List(T), f: (x: T) -> R) -> List(R)) = ...

# Несколько параметров типов
combine: (T: Type, U: Type) -> ((a: T, b: U) -> (T, U)) = (a, b)

1.2 Механизм самоописания Type

Type — сущность уровня языка; компилятор от природы распознаёт позиции Type в сигнатурах и автоматически выводит их заполнение из типов фактических аргументов.

yaoxiang

# Компилятор автоматически выводит параметры дженериков
numbers: List(Int) = List(Int)()
#         ^^^^^^^^   ^^^^^^^^
#         объявление типа   вызов конструктора: Int заполняет T, () — конструкция значения

# Вывод при вызове функции
numbers: List(Int) = List(Int)()
f: (x: Int) -> String = (x) => x.to_string()
strings: List(String) = map(numbers, f)
# Вывод компилятора: T=Int, R=String

1.3 Мономорфизация

yaoxiang

# Исходный код
map: (T: Type, R: Type) -> ((list: List(T), f: (x: T) -> R) -> List(R)) = {
    result: List(R) = List(R)()
    for x in list {
        result.push(f(x))
    }
    return result
}

# Точки использования
int_list: List(Int) = List(Int)()
doubled: List(Int) = map(int_list, (x: Int) => x * 2)  # Инстанцирование map[Int, Int]

string_list: List(String) = List(String)()
uppercased: List(String) = map(string_list, (s: String) => s.to_uppercase())  # Инстанцирование map[String, String]

# После компиляции (эквивалентный код)
map_Int_Int: (list: List(Int), f: (Int) -> Int) -> List(Int) = {
    result: List(Int) = List(Int)()
    for x in list {
        result.push(f(x))
    }
    return result
}

map_String_String: (list: List(String), f: (String) -> String) -> List(String) = {
    result: List(String) = List(String)
    for s in list {
        result.push(f(s))
    }
    return result
}

1.4 Явное заполнение (когда вывод не удаётся)

yaoxiang

# Когда возможен вывод, параметры Type можно опустить
numbers: List(Int) = List(Int)()
strings: List(String) = map(numbers, (x: Int) => x.to_string())

# Когда вывод невозможен, необходимо явное заполнение
# map(numbers, (x) => x)  # ❌ Error: Cannot infer R

### 2. Система ограничений типов

#### 2.1 Одиночное ограничение

```yaoxiang
# Базовые определения trait (типы интерфейсов)
Clone: Type = {
    clone: (Self) -> Self,
}

Display: Type = {
    fmt: (Self, Formatter) -> Result,
}

Debug: Type = {
    fmt: (Self, Formatter) -> Result,
}

# Использование ограничений: объявление ограничений типов прямо в сигнатуре
clone: (T: Clone) -> (value: T) -> T = value.clone()

debug_print: (T: Debug)(value: T) -> Void = {
    formatter = Formatter.new()
    value.fmt(formatter)
    print(formatter.to_string())
}

2.2 Множественные ограничения

yaoxiang

# Синтаксис множественных ограничений
combine: (T: Clone + Add)(a: T, b: T) -> T = {
    a.clone() + b
}

# Сортировка дженерик-контейнера
sort: (T: Clone + PartialOrd)(list: List(T)) -> List(T) = {
    # Реализация алгоритма сортировки
    result: List(T) = list.clone()
    quicksort(&mut result)
    return result
}

# Ограничение на тип функции
map: (T: Type, R: FnMut(T))(array: Vec(T), f: R) -> Vec(R) = {
    result: Vec(R) = Vec()
    for item in array {
        result.push(f(item))
    }
    return result
}

# Использование
doubled: Vec(Int) = map(Vec(1, 2, 3), (x: Int) => x * 2)  # Вывод компилятора

Источник имён ограничений (примечание от 2026-09-22): Add / Subtract / Multiply / Divide / Modulo и другие ограничения операторов определяются и реализуются в RFC-011b: Перегрузка операторов и операторы на основе интерфейсов — T: Add ≜ зарегистрированное инстанцирование интерфейса Add(T, T, T) (три параметра типа, тип результата O явный). Zero / One / PartialOrd / Fn / FnMut в настоящее время не имеют определённого источника и являются висячими именами ограничений, ожидающими своих RFC; до этого примеры с этими именами — бумажные иллюстрации.

2.3 Ограничения на типы функций

yaoxiang

# Ограничения на функции высшего порядка
call_twice: (T: Type, F: Fn() -> T)(f: F) -> (T, T) = (f(), f())

call_with_arg: (T: Type, U: Type, F: Fn(T) -> U)(arg: T, f: F) -> U = f(arg)

compose: (A: Type, B: Type, C: Type, F: Fn(A) -> B, G: Fn(B) -> C)(a: A, f: F, g: G) -> C = g(f(a))

# Примеры использования
result: Int = call_with_arg(42, (x: Int) => x * 2)  # result = 84
composed: String = compose(
    "hello",
    (s: String) => s.to_uppercase(),
    (s: String) => s + " WORLD"
)  # composed = "HELLO WORLD"

2.4 Встроенные marker trait: Dup и Clone

Три вида семантики копирования:

Тип	Значение	Способ запуска	Сценарий применения
Копирование примитива	Автоматическое копирование значения при присваивании, два значения полностью независимы	Автоматически при присваивании/передаче	Int, Float, Bool, Char
Dup	Поверхностное копирование: копирование дескриптора/токена, базовые данные разделяются	Автоматически при присваивании/передаче	Токены `&T`, `ref T`, String/Bytes
Clone	Глубокое копирование: создание полной независимой копии	`value.clone()`	Любой тип, реализующий Clone

Семантика Dup: типы, реализующие Dup, при присваивании/передаче не передают владение — компилятор копирует дескриптор/токен, несколько владельцев указывают на одни и те же базовые данные. Это дополняет семантику Move по умолчанию из модели владения RFC-009.

Dup и Clone — ортогональные концепции:

Dup = копирование дескриптора, общие данные (изменения влияют друг на друга)
Clone = копирование данных, копия независима (изменения не влияют друг на друга)

Правила:

1. Примитивные типы значений (Int, Float, Bool, Char) — встроенное в компилятор копирование значений, не Dup
2. Dup — только для типов ссылок/токенов и типов с внутренним подсчётом ссылок
3. Clone — явное глубокое копирование, может реализовать любой тип
4. Move по умолчанию — остальные типы сохраняют семантику Move по умолчанию

Какие типы являются Dup:

Тип	Dup	Причина
`&T` (токен заимствования)	✅	Токен нулевого размера, копирование токена = несколько представлений на одни данные
`ref T`	✅	Копирование Rc/Arc = счётчик ссылок +1, общие данные в куче
String, Bytes	✅	Внутренний подсчёт ссылок, копирование дескриптора разделяет базовый буфер
`&mut T` (токен изменяемого заимствования)	❌	Линейная эксклюзивность, нельзя копировать
struct	Производное	Все поля Dup → struct Dup
enum	Производное	Все поля всех вариантов Dup → enum Dup
tuple	Производное	Все элементы Dup → tuple Dup
Fn (замыкание)	❌	Захваченное окружение может быть не Dup
`*T` (сырой указатель)	❌	unsafe, не участвует в системе владения

Int/Float/Bool/Char не являются Dup — это типы значений, при присваивании компилятор автоматически копирует значение (два значения полностью независимы). Это не «поверхностное копирование», а встроенная в компилятор обработка примитивов; её не нужно и не следует выражать через атрибут типа Dup.

yaoxiang

# Примитивные типы значений: компилятор автоматически копирует значение (не Dup)
x: Int = 42
y = x          # Копирование значения, x и y полностью независимы
print(x)       # ✅

# Dup: поверхностное копирование, копирование дескриптора разделяет данные
view: &Point = &point
view2 = view    # ✅ Dup: копирование токена, оба указывают на один и тот же point
print(view.x)   # ✅

# Clone: явное глубокое копирование, создание независимой копии
backup = big_struct.clone()  # Явный вызов

# Ограничения дженериков
dup_use: (T: Dup) -> T = x         # T: Dup → можно поверхностно копировать
clone_use: (T: Clone) -> T = x.clone()  # T: Clone → можно глубоко копировать

Замечание: Send/Sync не являются видимыми пользователю trait. Гарантии безопасности между задачами обрабатываются ключевым словом ref и полностью автоматически компилятором — ref автоматически выбирает Rc или Arc, пользователю не нужно понимать Send/Sync.

3. Ассоциированные типы

3.1 Определение ассоциированных типов

yaoxiang

# trait Iterator (использует синтаксис (Item: Type) -> Type)
Iterator: (Item: Type) -> Type = {
    next: (Self) -> Option(Item),
    has_next: (Self) -> Bool,
    collect: (T: Type)(Self) -> List(T),
}

# Использование
collect_all: (T: Type, I: Iterator(T))(iter: I) -> List(T) = {
    result: List(T) = List(T)
    while iter.has_next() {
        if let Some(item) = iter.next() {
            result.push(item)
        }
    }
    return result
}

# Реализация Iterator для Vec
# Используется синтаксический сахар методов: Vec.Item, Vec.next, Vec.has_next
# Позиция итерации переносится в записи-обёртке (Vec сам по себе — сырой буфер, без поля index)
VecIter: (T: Type) -> Type = {
    data: &Vec(T),
    index: Int,
}

VecIter.has_next: (T: Type)(self: &VecIter(T)) -> Bool = {
    return self.index < self.data.length
}

VecIter.next: (T: Type)(self: &mut VecIter(T)) -> Option(T) = {
    if self.index < self.data.length {
        item = self.data[self.index]
        self.index = self.index + 1
        return Option.some(item)
    } else {
        return Option.none()
    }
}

VecIter.Item: (T: Type)(arr: &VecIter(T)) -> T = {
    return arr.data[arr.index]
}

3.2 Дженерик-ассоциированные типы (GAT)

yaoxiang

# Более сложные ассоциированные типы
Producer: (Item: Type) -> Type = {
    Item: T,
    produce: (Self) -> Option(Item),
}

# Ассоциированный тип может быть дженериком
Container: (Item: Type) -> Type = {
    Item: T,
    IteratorType: Iterator(Item),  # Ассоциированный тип тоже дженерик
    iter: (Self) -> IteratorType,
}

# Использование
process_container: (T: Type, C: Container(T))(container: C) -> List(T) = {
    container.iter().collect()
}

4. Дженерики времени компиляции

4.1 Параметры-значения времени компиляции

Ключевое решение: в сигнатурах дженериков Type помечает параметры-типы; параметры, аннотированные конкретными типами (Int/Bool/Float и т.д.), являются кандидатами в параметры-значения времени компиляции; становятся ли они параметрами-значениями времени компиляции, зависит от того, упоминается ли их значение в позиции типа (зависимость от значения). Ключевое слово const не требуется.

Критерий — упоминание в позиции типа, а не «аннотация конкретным типом»: в add: (a: Int, b: Int) -> Int = a + b a/b — параметры-значения рантайма, поскольку оба не появляются ни в одной позиции типа.

Правило определения (в два шага):

Грубая фильтрация по форме: параметр аннотирован конкретным типом, отличным от Type (например, Int) → становится кандидатом.
Точная фильтрация по использованию: имя кандидата появляется в позиции типа (тип поля тела типа, тип параметра внутренней Fn, предикат Assert, позиция аргумента конструктора типа вроде Array(T, N)) → подтверждается как параметр-значение времени компиляции; иначе рассматривается как параметр-значение рантайма.

Запись	Определение	Причина
`add: (a: Int, b: Int) -> Int = a + b`	a/b — параметры-значения рантайма	Появляются только в позициях значений, не участвуют в конструкции типов
`Array: (T: Type, N: Int) -> Type = { data: Array(T, N) }`	N — параметр-значение времени компиляции	N появляется в позиции аргумента конструктора типа `Array(T, N)`
`factorial: (N: Int) -> (k: N) -> Int`	N — параметр-значение времени компиляции	N служит типом внутреннего параметра `k`
`Foo: (T: Type, N: Int) -> Type = { x: T }`	N проваливается (см. ниже)	N не упомянут в теле типа, вырождается в параметр-значение рантайма

Суть зависимости от значений: параметр-значение времени компиляции — это тип, зависящий от значения, — только когда значение используется для конструирования типа, оно должно быть определено на этапе компиляции. Форма (: Int) определяет лишь кандидатуру, использование (появление в позиции типа) определяет, является ли он параметром-значением времени компиляции. Это тот же критерий, что и в разделе «Гарантия детерминированности времени компиляции» — «вызовы функций в позициях типов вычисляются на этапе компиляции».

yaoxiang

# ════════════════════════════════════════════════════════
# Параметр-значение времени компиляции: N упомянут в позиции типа (слот длины Measure)
# ════════════════════════════════════════════════════════
Measure: (T: Type, N: Int) -> Type = {
    data: Array(T, N),  # N появляется в позиции аргумента конструктора типа → параметр-значение времени компиляции
    length: N,
}

# Способ использования: factorial(5) вычисляется в позиции типа (время компиляции), результат 120 встраивается в тип
m: Measure(Int, factorial(5))  # Measure(Int, 120)

# ════════════════════════════════════════════════════════
# Зависимость от значения: N служит типом внутреннего параметра k
# ════════════════════════════════════════════════════════
# N — параметр-значение времени компиляции (появляется в позиции типа (k: N));
# k — параметр-значение рантайма, его тип — литеральный тип N (тип с одним значением).
factorial: (N: Int) -> (k: N) -> Int = {
    return match k {
        0 => 1,
        _ => k * factorial(k - 1)
    }
}

Обработка провалившихся кандидатов: кандидаты, аннотированные конкретным типом, но не упомянутые в позиции типа (например, N в Foo выше), вырождаются в параметры-значения рантайма (уровень функции). Провалившиеся кандидаты на пути конструктора типов не могут занять слот рантайма (конструктор типа вычисляется на этапе компиляции), сторона объявления напрямую выдаёт ошибку [E1094]: «N объявлен как параметр-значение времени компиляции, но не упомянут в теле типа» — ранее тихое отбрасывание приводило к несогласованности arity инстанцирования.

4.2 Вычисления времени компиляции

yaoxiang

# ════════════════════════════════════════════════════════
# Примеры вычислений времени компиляции
# ════════════════════════════════════════════════════════

# Компилятор вычисляет вызовы функций литеральных типов на этапе компиляции
SIZE: Int = factorial(5)  # На этапе компиляции: 120

# Использование типа матрицы
Matrix: (T: Type, Rows: Int, Cols: Int) -> Type = {
    data: Array(Array(T, Cols), Rows),
}

# Проверка измерений времени компиляции
identity_matrix: (T: Add + Zero + One, N: Int)(size: N) -> Matrix(T, N, N) = {
    matrix: Matrix(T, N, N) = Matrix(T, N, N)()
    for i in 0..size {
        for j in 0..size {
            if i == j {
                matrix.data[i][j] = One::one()
            } else {
                matrix.data[i][j] = Zero::zero()
            }
        }
    }
    matrix
}

# Использование: вычисление на этапе компиляции, генерируется Matrix(Float, 3, 3)
identity_3x3: Matrix(Float, 3, 3) = identity_matrix(Float, 3)(3)

Never и Void: ⊥ и ⊤ в системе типов

Система типов YaoXiang в изоморфизме Карри-Говарда одновременно обладает ⊥ (ложь/пустой тип) и ⊤ (истина/Unit), представленными двумя встроенными именами типов: Never и Void.

Never (⊥) — три не подлежащих обсуждению ключевых свойства:

Нулевые конструкторы: ни один литерал или выражение не может породить значение типа Never. Это метауровневое свойство, должно быть встроено.
Принцип взрыва: Never <: T выполняется для любого типа T. Значение Never может использоваться как значение любого типа — именно поэтому код после assert(false) всё ещё проходит проверку типов (хотя никогда не выполнится).
Маркер расходимости: f: (...) -> Never означает, что f гарантированно не возвращается. Компилятор использует это для анализа мёртвого кода.

Never — встроенное имя типа, а не ключевое слово, парсер его не выделяет. Синтаксис пустых и литеральных типов не открывается.

Void (⊤, т.е. Unit) — ровно один обитатель (значение void по умолчанию), носитель истинного propositions «всегда истинно». Void — единичный элемент для нулевых типов произведения, Never — единичный элемент для нулевых типов суммы — они двойственны. x: Void = <по умолчанию> допустимо, x: Never = ... — нет правой части, которую можно было бы записать.

4.3 Проверки времени компиляции (реализация стандартной библиотеки)

yaoxiang

# ════════════════════════════════════════════════════════
# Реализация стандартной библиотеки: использование условных типов
# ════════════════════════════════════════════════════════

# Определения стандартной библиотеки
# IsTrue: мост от вселенной значений к вселенной типов — истинное значение Bool отображается в тип
IsTrue: (b: Bool) -> Type = match b {
    true => Void,      # ⊤, имеет значение, программа продолжается
    false => Never,    # ⊥, нет значения, расходимость
}

# Assert: примитив refinement-типа времени компиляции — типуровневое выражение propositions Bool
Assert: (cond: Bool) -> Type = IsTrue(cond)
#
# cond == true  → Assert(true)  = Void    (всегда истинно, стирается)
# cond == false → Assert(false) = Never   (всегда ложно, ошибка компиляции/расходимость)
# cond не решаемо → конвейер доказательств решает по режиму dispatch:
#                   CompileTime → Unknown, требует prove
#                   Runtime     → вставка check, инъекция предположения Γ

# Способ использования 1: как ограничение в определении типа
Bounded: (T: Type, N: Int) -> Type = {
    data: Array(T, N),
    # Проверка времени компиляции: N должно быть больше 0 (Assert в позиции типа)
    length: Assert(N > 0),
}

# Способ использования 2: использование в выражениях
IntArray: (N: Int) -> Type = Array(Int, N)
# Верификация: размер IntArray(10) равен sizeof(Int) * 10
Assert(size_of(IntArray(10)) == sizeof(Int) * 10)

4.4 Специализация дженериков времени компиляции

yaoxiang

# Оптимизация малых массивов: использование перегрузки функций для специализации дженериков времени компиляции

# Общая реализация
sum: (T: Type, N: Int) -> ((arr: Array(T, N)) -> T) = {
    result = Zero::zero()
    for item in arr.data {
        result = result + item
    }
    return result
}

# Специализация N=1
sum: (T: Type) -> ((arr: Array(T, 1)) -> T) = arr.data[0]

# Специализация N=2
sum: (T: Type) -> ((arr: Array(T, 2)) -> T) = arr.data[0] + arr.data[1]

# Развёртка цикла для малых массивов (N <= 4)
sum: (T: Type, N: Int) -> ((arr: Array(T, N)) -> T) = {
    # Оптимизация компилятора: развёртка цикла
    return arr.data[0] + arr.data[1] + arr.data[2] + arr.data[3]
}

5. Условные типы

Изоморфизм Карри-Говарда: условные типы с точки зрения Карри-Говарда — это case-анализ в логике. Тип Bool соответствует propositions с двумя возможными значениями (True/False), If выбирает разные результаты в зависимости от истинности этого propositions — это и есть логический case-дизъюнкт. match C { True => T, False => E } фактически выражает: «при известном истинном propositions C результат T, при ложном — E».

5.1 Условный тип If

yaoxiang

# If на уровне типов
If: (C: Bool, T: Type, E: Type) -> Type = match C {
    True => T,
    False => E,
}

# Пример: ветвление времени компиляции
NonEmpty: (T: Type) -> Type = If(T != Void, T, Never)

Optional: (T: Type) -> Type = If(T != Void, T, Void)

# Проверка времени компиляции (унифицирована с определением Assert из §4.3)
# Assert: (cond: Bool) -> Type = IsTrue(cond)

# Использование
# Вычисление типа: If(True, Int, String) => Int
# Вычисление типа: If(False, Int, String) => String

5.2 Семейства типов

Изоморфизм Карри-Говарда: семейства типов — самое прямое воплощение «propositions суть типы». Add: (A: Type, B: Type) -> Type — это не «функция сложения на уровне типов», а конструирование propositions о сложении натуральных чисел. (Zero, B) => B означает «propositions Add(Zero, B) эквивалентно B», (Succ(A'), B) => Succ(Add(A', B)) означает «если Add(A', B) выполняется, то и Add(Succ(A'), B) выполняется». Это и есть определение сложения в аксиомах Пеано. Проверка типов подтверждает, что это выражение match проходит — эквивалентно проверке логической согласованности этого определения.

yaoxiang

# Преобразование типа времени компиляции
AsString: (T: Type) -> Type = match T {
    Int => String,
    Float => String,
    Bool => String,
    _ => String,  # по умолчанию
}

# Вычисления на уровне типов
Length: (T: Type) -> Type = match T.length {
    0 => Zero,
    1 => Succ(Zero),
    2 => Succ(Succ(Zero)),
    _ => TooLong,
}

# Сложение на уровне типов (Карри-Говард: case analysis + рекурсивный вызов, требует проверки завершимости для полной индукции)
Add: (A: Type, B: Type) -> Type = match (A, B) {
    (Zero, B) => B,
    (Succ(A'), B) => Succ(Add(A', B)),
}

# Пример: вычисление 2 + 3 на этапе компиляции
Two: Type = Succ(Succ(Zero))
Three: Type = Succ(Succ(Succ(Zero)))
Five: Type = Add[Two, Three]  # Succ(Succ(Succ(Succ(Succ(Zero)))))

6. Специализация через перегрузку функций

6.1 Базовая специализация

yaoxiang

# Базовая специализация: использование перегрузки функций (компилятор выбирает автоматически)
sum: (arr: Vec(Int)) -> Int = {
    # Компилируется в более эффективный код
    return native_sum_int(arr.data, arr.length)
}

sum: (arr: Vec(Float)) -> Float = {
    # Использует SIMD-инструкции
    return simd_sum_float(arr.data, arr.length)
}

# Общая реализация
sum: (T: Type) -> ((arr: Vec(T)) -> T) = {
    result = Zero::zero()
    for item in arr {
        result = result + item
    }
    return result
}

6.2 Условная специализация

yaoxiang

# Полностью соответствующий RFC-010 способ специализации: перегрузка функций

# Специализация для конкретных типов
sum: (arr: Vec(Int)) -> Int = {
    return native_sum_int(arr.data, arr.length)
}

sum: (arr: Vec(Float)) -> Float = {
    return simd_sum_float(arr.data, arr.length)
}

# Дженерик-реализация (компилятор автоматически выбирает оптимальную)
sum: (T: Type) -> ((arr: Vec(T)) -> T) = {
    result = Zero::zero()
    for item in arr {
        result = result + item
    }
    return result
}

# Использование полностью прозрачно
int_arr = Vec(Int)(1, 2, 3)
float_arr = Vec(Float)(1.0, 2.0, 3.0)

# Компилятор автоматически выбирает оптимальную специализацию
sum(int_arr)     # Выбирает sum: (Vec(Int)) -> Int
sum(float_arr)    # Выбирает sum: (Vec(Float)) -> Float

6.3 Идеальное сочетание перегрузки функций и инлайнинга

Ключевая особенность: перегрузка функций и оптимизация инлайнинга естественно сочетаются, обеспечивая абстракции с нулевой стоимостью.

yaoxiang

# ======== Исходный код ========
sum: (arr: Vec(Int)) -> Int = {
    return native_sum_int(arr.data, arr.length)
}

sum: (arr: Vec(Float)) -> Float = {
    return simd_sum_float(arr.data, arr.length)
}

sum: (T: Type) -> ((arr: Vec(T)) -> T) = {
    result = Zero::zero()
    for item in arr {
        result = result + item
    }
    return result
}

# Использование
int_arr = Vec(Int)(1, 2, 3, 4, 5)
result = sum(int_arr)

# ======== После компиляции (эквивалентный код) ========
# Компилятор автоматически выбирает оптимальную специализацию, затем инлайнит
result = native_sum_int(int_arr.data, int_arr.length)

# Полностью эквивалентно вручную написанному оптимизированному коду, без накладных расходов на вызов функции!

Ключевые преимущества:

Интеллектуальный выбор компилятора

yaoxiang

sum(int_arr)      # Автоматически выбирает sum: (Vec(Int)) -> Int
sum(float_arr)    # Автоматически выбирает sum: (Vec(Float)) -> Float
sum(custom_arr)  # Автоматически выбирает sum: (T: Type) -> ((arr: Vec(T)) -> T)

Оптимизация инлайнинга
- Малые функции автоматически инлайнятся в точку вызова
- Нулевые накладные расходы на вызов функции
- Полностью эквивалентно вручную написанному оптимизированному коду
Безопасность типов
- Проверка типов на этапе компиляции
- Нулевые накладные расходы в рантайме
- Нет необходимости в таблицах виртуальных функций

Идеально соответствует RFC-010

yaoxiang

# Полностью использует унифицированный синтаксис
name: type = value
# Без новых ключевых слов impl, where и т.д.

Пример из практики:

yaoxiang

# Чувствительные к производительности численные вычисления
fibonacci: (n: Int) -> Int = {
    if n <= 1 { return n }
    return fibonacci(n - 1) + fibonacci(n - 2)
}

fibonacci: (n: Float) -> Float = {
    # Использует формулу Бине
    phi = (1.0 + 5.0.sqrt()) / 2.0
    return (phi.pow(n) - (-phi).pow(-n)) / 5.0.sqrt()
}

# Компилятор автоматически выбирает и инлайнит
fibonacci(10)      # Выбирает версию для Int, полностью инлайнится
fibonacci(10.5)    # Выбирает версию для Float, использует формулу Бине

Что это означает?

✅ Специализация дженериков → перегрузка функций решает естественно
✅ Оптимизация производительности → инлайнинг выполняется автоматически
✅ Повторное использование кода → одно имя функции, несколько реализаций
✅ Абстракции с нулевой стоимостью → полиморфизм на этапе компиляции, нулевые накладные расходы в рантайме
✅ Без новых ключевых слов → идеально соответствует унифицированному синтаксису RFC-010


### 7. Механизм удаления мёртвого кода

#### 7.1 Анализ графа инстанцирования

```rust
// Внутри компилятора: построение графа зависимостей инстанцирования дженериков
struct InstantiationGraph {
    // Узлы: инстанцирования дженериков
    nodes: HashMap<InstanceKey, InstanceNode>,

    // Рёбра: отношения использования
    edges: HashMap<InstanceKey, Vec<InstanceKey>>,
}

struct InstanceKey {
    generic: FunctionId,  // ID дженерик-функции
    type_args: Vec<TypeId>,  // Параметры типов
    const_args: Vec<ConstId>,  // Параметры Const
}

// Алгоритм: анализ достижимости
fn eliminate_dead_instantiations(graph: &InstantiationGraph) {
    let mut reachable = HashSet::new();

    // Начинаем с точек входа (main, экспортируемые функции и т.д.)
    let entry_points = find_entry_points();
    for entry in entry_points {
        dfs_visit(entry, &graph, &mut reachable);
    }

    // Не посещённые инстанцирования — мёртвый код
    for node in &graph.nodes {
        if !reachable.contains(node.key) {
            eliminate(node);
        }
    }
}

7.2 Анализ точек использования

yaoxiang

# Анализ исходного кода
map: (T: Type, R: Type)(list: List(T), f: Fn(T) -> R) -> List(R) = ...

# Точка использования 1: инстанцирование map(Int, Int)
int_list = List(Int)()
int_list.push(1)
int_list.push(2)
int_list.push(3)
doubled = map(int_list, (x) => x * 2)  # Требуется map[Int, Int]

# Точка использования 2: инстанцирование map(String, String)
string_list = List(String)()
string_list.push("a")
string_list.push("b")
string_list.push("c")
uppercased = map(string_list, (s) => s.to_uppercase())  # Требуется map[String, String]

# Не используется: map[Float, Float] и т.д.
# Эти инстанцирования дженериков не будут сгенерированы

# После компиляции содержатся только используемые инстанцирования
map_Int_Int: (list: List(Int), f: Fn(Int) -> Int) -> List(Int) = ...
map_String_String: (list: List(String), f: Fn(String) -> String) -> List(String) = ...

7.3 DCE для дженериков времени компиляции

yaoxiang

# Анализ времени компиляции: использование дженериков времени компиляции
Array: (T: Type, N: Int) -> Type = {
    data: Array(T, N),
}

# Фактическое использование
arr_10_int = Array(Int, 10)(data=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10])  # Два уровня: параметры типов + параметры конструктора
arr_100_int = Array(Int, 100)()   # Пустая конструкция, данные присваиваются позже

# После компиляции генерируются только используемые Size
Array_Int_10: (Array(Int, 10)) = ...
Array_Int_100: (Array(Int, 100)) = ...

# Неиспользуемые Size не генерируются
# Array(Int, 50) не будет сгенерирован

7.4 Кросс-модульный DCE

yaoxiang

# Модуль A
# A.yx
pub map: (T: Type, R: Type)(list: List(T), f: Fn(T) -> R) -> List(R) = ...

# Модуль B
# B.yx
use A.{map}
int_list = List(Int)()
int_list.push(1)
int_list.push(2)
int_list.push(3)
doubled = map(int_list, (x) => x * 2)  # Инстанцирование map(Int, Int)

# Модуль C
# C.yx
use A.{map}
string_list = List(String)()
string_list.push("a")
string_list.push("b")
string_list.push("c")
uppercased = map(string_list, (s) => s.to_uppercase())  # Инстанцирование map(String, String)

# Анализ компиляции:
# - Модуль B использует map[Int, Int]
# - Модуль C использует map[String, String]
# - Скомпилированный бинарник содержит только эти два инстанцирования

7.5 DCE на уровне LLVM

rust

// Конвейер компиляции
fn optimize_ir(ir: &mut IR) {
    // 1. Мономорфизация (компилятор YaoXiang)
    ir.monomorphize();

    // 2. Оптимизация инлайнинга
    ir.inline_small_functions();

    // 3. Распространение констант
    ir.constant_propagation();

    // 4. Генерация LLVM IR
    let llvm_ir = ir.to_llvm();

    // 5. Проходы оптимизации LLVM
    llvm_ir.add_pass(Passes::DEAD_CODE_ELIMINATION);
    llvm_ir.add_pass(Passes::INLINE_FUNCTION);
    llvm_ir.add_pass(Passes::GLOBAL_DCE);
    llvm_ir.add_pass(Passes::MERGE_FUNC);

    // 6. Запуск проходов оптимизации
    llvm_ir.run_optimization_passes();
}

8. Стратегия замены макросов

8.1 Замена кодогенерации

yaoxiang

# ❌ Подход с макросами: кодогенерация
macro_rules! impl_debug {
    ($($t:ty),*) => {
        $(impl Debug for $t {
            fn fmt(&self, f: &mut Formatter) -> Result {
                write!(f, "{:?}", self)
            }
        })*
    };
}

# ✅ Подход с дженериками: автоматическое выведение
# Использование перегрузки функций для автоматического выведения
debug_fmt: (T: fields...) -> ((self: Point(T)) -> String) = {
    return "Point { x: " + self.x.to_string() + ", y: " + self.y.to_string() + " }"
}

# Использование
p = Point { x: 1, y: 2 }
p.debug_fmt(&formatter)  # Вызов генерируется автоматически

8.2 Замена DSL

yaoxiang

# ❌ Подход с макросами: HTML DSL
html! {
    <div class="container">
        <h1> { title } </h1>
        <ul>
            { for item in items {
                <li> { item } </li>
            }}
        </ul>
    </div>
}

# ✅ Подход с дженериками: типобезопасный построитель
Element: Type = {
    tag: String,
    attrs: HashMap(String, String),
    children: List(Element),
    text: Option(String),
}

create_element: (tag: String) -> Element = {
    return Element(tag, HashMap::new(), List::new(), None)
}

with_class: [E: Element](elem: E, class: String) -> E = {
    elem.attrs.insert("class", class)
    return elem
}

with_text: [E: Element](elem: E, text: String) -> E = {
    return E { text: Some(text), ..elem }
}

# Построение DOM
container = create_element("div")
    |> with_class("container")
    |> with_children(List::new())

title_elem = create_element("h1") |> with_text(title)
items_li = items.map((item) =>
    create_element("li") |> with_text(item)
)
root = container |> with_children(List::new() + [title_elem, ul_elem])

8.3 Замена программирования на уровне типов

yaoxiang

# ❌ Подход с макросами: вычисления на уровне типов
macro_rules! add_types {
    ($a:ty, $b:ty) => {
        ($a, $b)
    };
}

# ✅ Подход с дженериками: условные типы
Add: (A: Type, B: Type) -> Type = match (A, B) {
    (Int, Int) => Int,
    (Float, Float) => Float,
    (Int, Float) => Float,
    (Float, Int) => Float,
    _ => TypeError,
}

# Проверка времени компиляции
AssertAddable: (A: Type, B: Type) -> Type = If(Add(A, B) != TypeError, (A, B), compile_error("Cannot add"))

# Использование
result_type = Add[Int, Float]  # Выводится как Float

Связь с RFC-011b (примечание от 2026-09-22): семейство типов Add(A, B) в данном разделе — это взгляд реестра интерфейсов операторов из RFC-011b на уровне типов — базовая запись Add(Int, Float, Float) и (Int, Float) => Float в данной таблице — одно и то же правило, каждое инстанцирование интерфейса пользователем — добавление строки в эту таблицу. Пеано-уровневое Add из §5.2 — это чисто вычисление на уровне типов (однофамилец, но другой объект), не пересекается с value-уровневыми интерфейсами операторов — запросы операторов идут в реестр, а не через разрешение имён.

9. Примеры

9.1 Полный пример дженерик-контейнера

yaoxiang

# ======== 1. Определение дженерик-контейнера ========
# Использование синтаксиса (T: Type) -> Type
Result: (T: Type, E: Type) -> Type = {
    ok: (T) -> Self,
    err: (E) -> Self,
}

Option: (T: Type) -> Type = {
    some: (T) -> Self,
    none: () -> Self,
}

List: (T: Type) -> Type = {
    data: Vec(T),
    length: Int,

    # Дженерик-методы (T автоматически вводится в область видимости внешним List(T))
    push: (self: List(T), item: T) -> Void,
    pop: (self: List(T)) -> Option(T),
    map: (R: Type) -> ((self: List(T), f: (T) -> R) -> List(R)),
    filter: (self: List(T), predicate: (T) -> Bool) -> List(T),
    fold: (U: Type) -> ((self: List(T), initial: U, f: (U, T) -> U) -> U),
}

# ======== 2. Реализация дженерик-методов ========
# Определения функций находятся в пространстве имён List (префикс List. = принадлежность пространству имён)
# Чтобы вызовы через . (например, list.push(item)) работали, требуется явная привязка: List.push = push[0]
# self — просто имя параметра по соглашению, компилятор смотрит на тип, а не на имя

List.push: (T: Type) -> ((self: List(T), item: T) -> Void) = {
    if self.length >= self.data.length {
        # Расширение
        new_data = Vec(T)(len=self.data.length * 2)
        for i in 0..self.length {
            new_data[i] = self.data[i]
        }
        self.data = new_data
    }
    self.data[self.length] = item
    self.length = self.length + 1
}

List.pop: (T: Type) -> ((self: List(T)) -> Option(T)) = {
    if self.length > 0 {
        self.length = self.length - 1
        return Option.some(self.data[self.length])
    } else {
        return Option.none()
    }
}

List.map: (T: Type, R: Type) -> ((self: List(T), f: (T) -> R) -> List(R)) = {
    result = List(R)()
    for i in 0..self.length {
        result.push(f(self.data[i]))
    }
    return result
}

List.filter: (T: Type) -> ((self: List(T), predicate: (T) -> Bool) -> List(T)) = {
    result = List(T)()
    for i in 0..self.length {
        if predicate(self.data[i]) {
            result.push(self.data[i])
        }
    }
    return result
}

List.fold: (T: Type, U: Type) -> ((self: List(T), initial: U, f: (U, T) -> U) -> U) = {
    result = initial
    for i in 0..self.length {
        result = f(result, self.data[i])
    }
    return result
}

# ======== 3. Использование ограничений типов ========
# Реализация Clone для List
List.clone: (T: Clone) -> ((self: List(T)) -> List(T)) = {
    result = List(T)()
    for i in 0..self.length {
        result.push(self.data[i].clone())
    }
    return result
}

# ======== 4. Примеры использования ========
# Создание дженерик-List
numbers = List(Int)()
numbers.push(1)
numbers.push(2)
numbers.push(3)

# Использование дженерик-методов
doubled = numbers.map((x) => x * 2)
evens = numbers.filter((x) => x % 2 == 0)

# Использование fold для вычисления
sum = numbers.fold(0, (acc, x) => acc + x)  # sum = 6

# Композиция дженериков
sum_of_evens = numbers
    .filter((x) => x % 2 == 0)
    .map((x) => x * 2)
    .fold(0, (acc, x) => acc + x)  # sum_of_evens = 8

9.2 Пример дженерик-алгоритма

yaoxiang

# ======== 1. Дженерик-алгоритм сортировки ========
Comparator: (T: Type) -> Type = {
    compare: (T, T) -> Int,  # -1 if a < b, 0 if a == b, 1 if a > b
}

# Дженерик quicksort
quicksort: (T: Clone) -> ((array: Vec(T), cmp: Comparator(T)) -> Vec(T)) = {
    if array.length <= 1 {
        return array.clone()
    }

    pivot = array[array.length / 2]
    left = Vec(T)()
    right = Vec(T)()

    for i in 0..array.length {
        if i == array.length / 2 {
            continue
        }
        item = array[i]
        comparison = cmp.compare(item, pivot)
        if comparison < 0 {
            left.push(item)
        } else {
            right.push(item)
        }
    }

    sorted_left = quicksort(left, cmp)
    sorted_right = quicksort(right, cmp)

    result = sorted_left.clone()
    result.push(pivot)
    result.extend(sorted_right)
    return result
}

# ======== 2. Реализация IntComparator ========
# Использование перегрузки функций
compare: (a: Int, b: Int) -> Int = {
    if a < b {
        return -1
    } else if a > b {
        return 1
    } else {
        return 0
    }
}

# ======== 3. Примеры использования ========
# Сортировка массива Int
numbers = Vec(Int)(3, 1, 4, 1, 5, 9, 2, 6)
sorted = quicksort(numbers, Comparator(Int)())

# Сортировка массива String (требуется StringComparator)
strings = Vec(String)("hello", "world", "foo", "bar")
sorted_strings = quicksort(strings, Comparator(String)())

9.3 Пример дженерика времени компиляции

yaoxiang

# ======== 1. Тип матрицы времени компиляции ========
Matrix: (T: Type, Rows: Int, Cols: Int) -> Type = {
    data: Array(Array(T, Cols), Rows),

    # Проверка измерений времени компиляции: с использованием типа Assert стандартной библиотеки
    _assert: Assert(Rows > 0),  # Rows > 0, иначе ошибка компиляции
    _assert: Assert(Cols > 0),  # Cols > 0, иначе ошибка компиляции

    # Операции над матрицами
    multiply: (M: Int) -> ((self: Matrix(T, Rows, Cols), other: Matrix(T, Cols, M)) -> Matrix(T, Rows, M)) = {
        result = Matrix(T, Rows, M)()
        for i in 0..Rows {
            for j in 0..M {
                sum = Zero::zero()
                for k in 0..Cols {
                    sum = sum + self.data[i][k] * other.data[k][j]
                }
                result.data[i][j] = sum
            }
        }
        return result
    }
}

# ======== 2. Создание матрицы времени компиляции ========
identity: (T: Add + Multiply + One, N: Int) -> ((size: N) -> Matrix(T, N, N)) = {
    matrix = Matrix(T, N, N)()
    for i in 0..N {
        for j in 0..N {
            if i == j {
                matrix.data[i][j] = One::one()
            } else {
                matrix.data[i][j] = Zero::zero()
            }
        }
    }
    return matrix
}

# ======== 3. Примеры использования ========
# Создание матрицы с размером, известным на этапе компиляции
# Матрица 2x3
matrix_2x3 = Matrix(Float, 2, 3)()
matrix_2x3.data[0][0] = 1.0
matrix_2x3.data[0][1] = 2.0
matrix_2x3.data[0][2] = 3.0
matrix_2x3.data[1][0] = 4.0
matrix_2x3.data[1][1] = 5.0
matrix_2x3.data[1][2] = 6.0

# Матрица 3x2
matrix_3x2 = Matrix(Float, 3, 2)()
matrix_3x2.data[0][0] = 7.0
matrix_3x2.data[0][1] = 8.0
matrix_3x2.data[1][0] = 9.0
matrix_3x2.data[1][1] = 10.0
matrix_3x2.data[2][0] = 11.0
matrix_3x2.data[2][1] = 12.0

# Умножение матриц: 2x3 * 3x2 = 2x2
result = matrix_2x3.multiply(matrix_3x2)

# Проверка времени компиляции: тип result — Matrix(Float, 2, 2)
# Единичная матрица 2x2
identity_3x3 = identity(Float, 3)()

# Несоответствие измерений: ошибка компиляции
# bad_multiply = matrix_2x3.multiply(identity_3x3)  # Ошибка компиляции: 3x3 != 2x3

Компромиссы

Преимущества

Абстракции с нулевой стоимостью
- Мономорфизация на этапе компиляции, без накладных расходов в рантайме
- Без виртуальных функций, без RTTI
Удаление мёртвого кода
- Анализ на этапе компиляции, инстанцирование только используемых дженериков
- Раздувание кода контролируемо
Замена макросов
- Типобезопасная кодогенерация
- IDE-дружественность, понятные сообщения об ошибках
Вычисления времени компиляции
- Дженерики времени компиляции поддерживают вычисления на этапе компиляции
- Характеристики вроде проверки измерений
- Без ключевого слова const, чистые ограничения типов

Недостатки

Время компиляции
- Инстанцирование дженериков увеличивает время компиляции
- Решение ограничений может быть медленным
Потребление памяти
- Увеличивается потребление памяти компилятором
- Механизмам кэширования нужна память
Сложность реализации
- Решатель ограничений сложен
- Движок вычислений на уровне типов сложен
Диагностика ошибок
- Ошибки дженериков могут быть сложными
- Нужны понятные подсказки об ошибках

Меры по смягчению

Стратегия кэширования
- Кэширование результатов инстанцирования
- LRU-кэш для ограничения памяти
Инкрементальная компиляция
- Кэширование результатов компиляции
- Инкрементальное инстанцирование
Сообщения об ошибках
- Понятные сообщения об ошибках
- Подсказки для вывода параметров дженериков
Параллельная компиляция
- Параллельное инстанцирование дженериков
- Многопоточное решение ограничений

Альтернативы

Альтернатива	Почему не выбрана
Только базовые дженерики	Не может заменить сложные макросы
Чистая система макросов	Нет безопасности типов, плохие сообщения об ошибках
Только ограничения-зависимости	Недостаточная гибкость
Рантайм-дженерики	Накладные расходы производительности

Риски

Риск	Влияние	Меры по смягчению
Сложность решения ограничений	Слишком долгая компиляция	Инкрементальное решение + кэширование
Раздувание кода	Слишком большой бинарник	DCE + пороговое управление
Сложность реализации	Удлинение цикла разработки	Поэтапная реализация
Диагностика ошибок	Плохой пользовательский опыт	Подробные сообщения об ошибках

Открытые вопросы

Вопросы, ожидающие решения

Вопрос	Описание	Статус
Стратегия инстанцирования	Eager vs Lazy vs Threshold	К обсуждению
Размер кэша	Настройка объёма LRU-кэша	К обсуждению
Диагностика ошибок	Степень детализации сообщений об ошибках дженериков	К обсуждению

Последующие оптимизации

Оптимизация	Ценность	Сложность реализации
Анализ графа инстанцирования	Высокая	Средняя
DSL программирования на уровне типов	Средняя	Высокая
Бенчмарки производительности дженериков	Средняя	Низкая

Приложение

БНФ синтаксиса

bnf

# Параметры дженериков используют унифицированный синтаксис () как часть типа функции
# Например, map: (T: Type, R: Type) -> ((list: List(T), f: (T) -> R) -> List(R))

# Ограничение типа (в параметрах дженерика)
type_bound ::= identifier
             | identifier '+' identifier ('+' identifier)*

# Объявление параметра (тип + имя)
parameter ::= identifier ':' type

parameters ::= parameter (',' parameter)*

# Объявление функции: name: type = expression
# Параметры дженерика — первая группа параметров в типе функции: (T: Type) -> ((params) -> return)
function ::= identifier ':' type '=' (expression | block)

# Объявление метода: Type.method: type = expression
method ::= identifier '.' identifier ':' type '=' (expression | block)

# Определение типа (унифицированный синтаксис Binding)
# Дженерик-тип, такой как List: (T: Type) -> Type = { ... }
generic_type ::= identifier ':' type '=' type_expression

# Type в параметрах дженерика автоматически заполняется компилятором из типов фактических аргументов
# Например, map(numbers, f), T извлекается из numbers: List(Int), R — из f: (Int) -> String

Жизненный цикл и судьба

┌─────────────┐
│   Черновик  │  ← Текущее состояние
└──────┬──────┘
       │
       ▼
┌─────────────┐
│  На проверке│  ← Открытое общественное обсуждение и обратная связь
└──────┬──────┘
       │
       ├──────────────────┐
       ▼                  ▼
┌─────────────┐    ┌─────────────┐
│  Принят     │    │  Отклонён   │
└──────┬──────┘    └──────┬──────┘
       │                  │
       ▼                  ▼
┌─────────────┐    ┌─────────────┐
│   accepted/ │    │    rfc/     │
│ (официальный дизайн) │  (остаётся на месте)  │
└─────────────┘    └─────────────┘

RFC-011: Дизайн системы дженериков - абстракции с нулевой стоимостью и замена макросов ​

Резюме ​

Справочные документы ​

Идея вселенной типов и типы, зависящие от значений ​

Что такое типы, зависящие от значений? ​

Именование контейнеров по уровням ​

Ключевые преимущества типов, зависящих от значений ​

Иерархия вселенных типов и типы, зависящие от значений ​

Гарантия детерминированности времени компиляции ​

Сценарии применения типов, зависящих от значений ​

Проверка измерений времени компиляции ​

Типобезопасный размер массива ​

Цель покрытия ошибок границ на этапе компиляции ​

Условные типы ​

Дженерик-функции ​

Сравнение с другими языками ​

Механизм проверки завершимости (унифицирован с RFC-027) ​

Проверка завершимости рекурсивных функций ​

Проверка завершимости циклов ​

Рабочий процесс проверки завершимости ​

Преимущества ​

Мотивация ​

Зачем нужна сильная система дженериков? ​

Ключевые противоречия ​

Ключевые преимущества типов, зависящих от значений ​

Ценность системы дженериков ​

Цели дизайна ​

Основные цели ​

Принципы дизайна ​

Предложение ​

1. Базовые дженерики ​

1.1 Параметры типов дженериков ​

Синтаксис вызова дженерик-функций ​

1.1 Унифицированный синтаксис сигнатур ​

1.2 Механизм самоописания Type ​

1.3 Мономорфизация ​

1.4 Явное заполнение (когда вывод не удаётся) ​

2.2 Множественные ограничения ​

2.3 Ограничения на типы функций ​

2.4 Встроенные marker trait: Dup и Clone ​

3. Ассоциированные типы ​

3.1 Определение ассоциированных типов ​

3.2 Дженерик-ассоциированные типы (GAT) ​

4. Дженерики времени компиляции ​

4.1 Параметры-значения времени компиляции ​

4.2 Вычисления времени компиляции ​

Never и Void: ⊥ и ⊤ в системе типов ​

4.3 Проверки времени компиляции (реализация стандартной библиотеки) ​

4.4 Специализация дженериков времени компиляции ​

5. Условные типы ​

5.1 Условный тип If ​

5.2 Семейства типов ​

6. Специализация через перегрузку функций ​

6.1 Базовая специализация ​

6.2 Условная специализация ​

6.3 Идеальное сочетание перегрузки функций и инлайнинга ​

7.2 Анализ точек использования ​

7.3 DCE для дженериков времени компиляции ​

7.4 Кросс-модульный DCE ​

7.5 DCE на уровне LLVM ​

8. Стратегия замены макросов ​

8.1 Замена кодогенерации ​

8.2 Замена DSL ​

8.3 Замена программирования на уровне типов ​

9. Примеры ​

9.1 Полный пример дженерик-контейнера ​

9.2 Пример дженерик-алгоритма ​

9.3 Пример дженерика времени компиляции ​

Компромиссы ​

Преимущества ​

Недостатки ​

Меры по смягчению ​

Альтернативы ​

Риски ​

Открытые вопросы ​

Вопросы, ожидающие решения ​

Последующие оптимизации ​

Приложение ​

БНФ синтаксиса ​

Жизненный цикл и судьба ​

RFC-011: Дизайн системы дженериков - абстракции с нулевой стоимостью и замена макросов

Резюме

Справочные документы

Идея вселенной типов и типы, зависящие от значений

Что такое типы, зависящие от значений?

Именование контейнеров по уровням

Ключевые преимущества типов, зависящих от значений

Иерархия вселенных типов и типы, зависящие от значений

Гарантия детерминированности времени компиляции

Сценарии применения типов, зависящих от значений

Проверка измерений времени компиляции

Типобезопасный размер массива

Цель покрытия ошибок границ на этапе компиляции

Условные типы

Дженерик-функции

Сравнение с другими языками

Механизм проверки завершимости (унифицирован с RFC-027)

Проверка завершимости рекурсивных функций

Проверка завершимости циклов

Рабочий процесс проверки завершимости

Преимущества

Мотивация

Зачем нужна сильная система дженериков?

Ключевые противоречия

Ключевые преимущества типов, зависящих от значений

Ценность системы дженериков

Цели дизайна

Основные цели

Принципы дизайна

Предложение

1. Базовые дженерики

1.1 Параметры типов дженериков

Синтаксис вызова дженерик-функций

1.1 Унифицированный синтаксис сигнатур

1.2 Механизм самоописания Type

1.3 Мономорфизация

1.4 Явное заполнение (когда вывод не удаётся)

2.2 Множественные ограничения

2.3 Ограничения на типы функций

2.4 Встроенные marker trait: Dup и Clone

3. Ассоциированные типы

3.1 Определение ассоциированных типов

3.2 Дженерик-ассоциированные типы (GAT)

4. Дженерики времени компиляции

4.1 Параметры-значения времени компиляции

4.2 Вычисления времени компиляции

Never и Void: ⊥ и ⊤ в системе типов

4.3 Проверки времени компиляции (реализация стандартной библиотеки)

4.4 Специализация дженериков времени компиляции

5. Условные типы

5.1 Условный тип If

5.2 Семейства типов

6. Специализация через перегрузку функций

6.1 Базовая специализация

6.2 Условная специализация

6.3 Идеальное сочетание перегрузки функций и инлайнинга

7.2 Анализ точек использования

7.3 DCE для дженериков времени компиляции

7.4 Кросс-модульный DCE

7.5 DCE на уровне LLVM

8. Стратегия замены макросов

8.1 Замена кодогенерации

8.2 Замена DSL

8.3 Замена программирования на уровне типов

9. Примеры

9.1 Полный пример дженерик-контейнера

9.2 Пример дженерик-алгоритма

9.3 Пример дженерика времени компиляции

Компромиссы

Преимущества

Недостатки

Меры по смягчению

Альтернативы

Риски

Открытые вопросы

Вопросы, ожидающие решения

Последующие оптимизации

Приложение

БНФ синтаксиса

Жизненный цикл и судьба