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: Предикаты компиляции и унифицированная статическая верификация	Проверка завершения	Спецификации decreases и гарантии безопасности вычислений на этапе компиляции

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

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

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

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

yaoxiang

# Традиционные обобщения: параметры типов
List: (T: Type) -> Type

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

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

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

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

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

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

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

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

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

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

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

Концепция типовой вселенной 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, размер вектора определяется на этапе компиляции
vec: Vec(factorial(3)) = Vec(6)()

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

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

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

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

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 (известно на этапе компиляции)

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

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(1, 2, 3)
doubled = map(numbers, (x) => x * 2)  # Выводится как map[Int, Int]

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

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

Механизм проверки завершения (интеграция с RFC-022)

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

Спецификация завершения для рекурсивных функций

yaoxiang

# Факториал на этапе компиляции: необходимо доказать завершение
factorial: (n: Int) -> Int = {
    //! requires: n >= 0
    //! ensures: result == n!
    //! decreases: n    # При каждой рекурсии n строго убывает
    if n <= 1 { return 1 }
    return n * factorial(n - 1)
}

# Использование: вызов в позиции типа
vec: Vec(factorial(5)) = Vec(120)()  # Вычисление factorial(5) = 120 на этапе компиляции

Спецификация завершения для циклов

yaoxiang

sum: (arr: Array(Int, n)) -> Int = {
    s = 0; i = 0
    while i < n {
        /*! invariant: s == sum(arr[0..i]) && 0 <= i <= n !*/
        /*! decreases: n - i !*/
        s += arr[i]; i += 1
    }
    return s
}

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

┌─────────────────────────────────────────────────────────────┐
│  Фаза проверки типов                                        │
│  Встречен вызов функции в позиции типа (например, Vec(factorial(5))) │
└─────────────────────────┬───────────────────────────────────┘
                          ▼
┌─────────────────────────────────────────────────────────────┐
│  1. Проверка спецификации decreases                         │
│     - Есть decreases: проверка убывания на всех путях рекурсии │
│     - Нет decreases, но очевидно завершается: прямое вычисление │
│     - Нет decreases и возможно не завершается: ошибка компиляции │
└─────────────────────────┬───────────────────────────────────┘
                          ▼
┌─────────────────────────────────────────────────────────────┐
│  2. Вычисления на этапе компиляции (выполняются встроенным интерпретатором) │
│     - Чистые функции: прямое вычисление                      │
│     - Побочные эффекты: ошибка компиляции (в позиции типа побочных эффектов быть не может) │
└─────────────────────────┬───────────────────────────────────┘
                          ▼
┌─────────────────────────────────────────────────────────────┐
│  3. Встраивание результата в тип                             │
│     - Vec(factorial(5)) → Vec(120)                          │
│     - Matrix(Float, 3, 3) → конкретный тип                  │
└─────────────────────────────────────────────────────────────┘

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

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

Мотивация

Зачем нужна мощная система обобщений?

Обобщения в текущих основных языках имеют ограничения:

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

Основное противоречие

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

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

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

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

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: Array(Int), f: Fn(Int) -> Int) -> Array(Int) = ...
map_string_array: (array: Array(String), f: Fn(String) -> String) -> Array(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 — интеллектуальные подсказки, понятные сообщения об ошибках
Типы, зависящие от значений — типы могут зависеть от значений, поддержка проверки размерностей на этапе компиляции
Безопасность вычислений на этапе компиляции — гарантия завершения вычислений на этапе компиляции через спецификацию decreases

Принципы проектирования

Определённость на этапе компиляции: параметры обобщений определяются на этапе компиляции
Приоритет мономорфизации: генерация конкретного кода, избегание виртуальных вызовов
Ограничения управляют инстанцированием: ограничения типов направляют инстанцирование
Оптимизация под платформу: специализация поддерживает оптимизацию под конкретную платформу
Единообразие типовой вселенной: функции/конструкторы типов/типы, зависящие от значений, унифицированы на уровне 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: Array(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)  # ❌ Ошибка: Не удаётся вывести 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: Array(T), f: R) -> Array(R) = {
    result: Array(R) = Array()
    for item in array {
        result.push(f(item))
    }
    return result
}

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

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

# Iterator trait (использование синтаксиса (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 для Array
# Использование синтаксического сахара для методов: Array.Item, Array.next, Array.has_next
Array.has_next: (T: Type)(self: Array(T)) -> Bool = {
    return self.index < self.length
}

Array.next: (T: Type)(self: Array(T)) -> Option(T) = {
    if has_next(self) {
        item = self.data[self.index]
        self.index = self.index + 1
        return Option.some(item)
    } else {
        return Option.none()
    }
}

Array.Item: (T: Type)(arr: Array(T)) -> T = {
    return arr.data[0]
}

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, по умолчанию определяются на этапе компиляции в обобщённом контексте. Ключевое слово const не требуется.

yaoxiang

# ════════════════════════════════════════════════════════
# Параметры-константы этапа компиляции: Int в обобщениях по умолчанию определяется на этапе компиляции
# ════════════════════════════════════════════════════════

# Факториал на этапе компиляции: N должен быть известной на этапе компиляции константой
factorial: (N: Int) -> (n: N) -> Int = {
    return match n {
        0 => 1,
        _ => n * factorial(n - 1)
    }
}

# Сложение на этапе компиляции
add: (a: Int, b: Int) -> (a: a, b: b) -> Int = a + b

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

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

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 по умолчанию), носитель истинного высказывания «всегда истинно». Void — единица нуль-полевого произведения типов, Never — единица нуль-вариантного суммарного типа — они двойственны. x: Void = <по умолчанию> допустимо, x: Never = ... не имеет правой части для записи.

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

yaoxiang

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

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

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

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

# Способ использования 2: в выражении
IntArray: (N: Int) -> Type = StaticArray(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 соответствует высказыванию с двумя возможными значениями (True/False), If выбирает различные результаты в зависимости от истинности этого высказывания — это именно дизъюнктивный case в логике. match C { True => T, False => E } фактически выражает: «когда известно, что высказывание C истинно, заключение — T; когда C ложно, заключение — 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 Семейства типов

Изоморфизм Карри — Ховарда: Семейства типов — наиболее прямое воплощение «высказывания — это типы». Add: (A: Type, B: Type) -> Type — это не «написанная на уровне типов функция сложения», а конструкция высказывания о сложении натуральных чисел. (Zero, B) => B означает «высказывание 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,
}

# Сложение на уровне типов (Curry-Howard: 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: Array(Int)) -> Int = {
    # Компилируется в более эффективный код
    return native_sum_int(arr.data, arr.length)
}

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

# Универсальная реализация
sum: (T: Type) -> ((arr: Array(T)) -> T) = {
    result = Zero::zero()
    for item in arr {
        result = result + item
    }
    return result
}

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

yaoxiang

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

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

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

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

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

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

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

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

yaoxiang

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

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

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

# Использование
int_arr = Array(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: (Array(Int)) -> Int
sum(float_arr)    # Автоматически выбирается sum: (Array(Float)) -> Float
sum(custom_arr)  # Автоматически выбирается sum: (T: Type) -> ((arr: Array(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(1, 2, 3)
doubled = map(int_list, (x) => x * 2)  # Требуется map[Int, Int]

# Точка использования 2: инстанцирование map(String, String)
string_list = List("a", "b", "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 Устранение мёртвого кода для обобщений этапа компиляции

yaoxiang

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

# Фактическое использование
arr_10_int = Array(Int, 10)(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
arr_100_int = Array(Int, 100)(...)

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

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

7.4 Кросс-модульное устранение мёртвого кода

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(1, 2, 3)
doubled = map(int_list, (x) => x * 2)  # Инстанцирование map(Int, Int)

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

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

7.5 Устранение мёртвого кода на уровне 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

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: Array(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 = Array(T)(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 если a < b, 0 если a == b, 1 если a > b
}

# Обобщённый quicksort
quicksort: (T: Clone) -> ((array: Array(T), cmp: Comparator(T)) -> Array(T)) = {
    if array.length <= 1 {
        return array.clone()
    }

    pivot = array[array.length / 2]
    left = Array(T)()
    right = Array(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 = Array(Int)(3, 1, 4, 1, 5, 9, 2, 6)
sorted = quicksort(numbers, Comparator(Int)())

# Сортировка массива String (нужен StringComparator)
strings = Array(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)
# Единичная матрица 3x3
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-022) ​

Спецификация завершения для рекурсивных функций ​

Спецификация завершения для циклов ​

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

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

Мотивация ​

Зачем нужна мощная система обобщений? ​

Основное противоречие ​

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

Ценность системы обобщений ​

Цели проектирования ​

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

Принципы проектирования ​

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

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. Механизм устранения мёртвого кода ​

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

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

7.3 Устранение мёртвого кода для обобщений этапа компиляции ​

7.4 Кросс-модульное устранение мёртвого кода ​

7.5 Устранение мёртвого кода на уровне LLVM ​

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

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

8.2 Замена DSL ​

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

9. Примеры ​

9.1 Полный пример обобщённого контейнера ​

9.2 Пример обобщённого алгоритма ​

9.3 Пример обобщений этапа компиляции ​

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

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

Недостатки ​

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

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

Риски ​

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

Вопросы, требующие решения ​

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

Приложение ​

БНФ-грамматика синтаксиса ​

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

RFC-011: Проектирование системы обобщений — Абстракции с нулевой стоимостью и замена макросов

Аннотация

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

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

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

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

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

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

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

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

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

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

Обобщённые функции

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

Механизм проверки завершения (интеграция с RFC-022)

Спецификация завершения для рекурсивных функций

Спецификация завершения для циклов

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

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

Мотивация

Зачем нужна мощная система обобщений?

Основное противоречие

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

Ценность системы обобщений

Цели проектирования

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

Принципы проектирования

Предложение

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. Механизм устранения мёртвого кода

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

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

7.3 Устранение мёртвого кода для обобщений этапа компиляции

7.4 Кросс-модульное устранение мёртвого кода

7.5 Устранение мёртвого кода на уровне LLVM

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

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

8.2 Замена DSL

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

9. Примеры

9.1 Полный пример обобщённого контейнера

9.2 Пример обобщённого алгоритма

9.3 Пример обобщений этапа компиляции

Компромиссы

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

Недостатки

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

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

Риски

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

Вопросы, требующие решения

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

Приложение

БНФ-грамматика синтаксиса

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