Теория языков программирования

Дженерики и параметрический полиморфизм

До Java 5 каждый контейнер работал через `Object`: `list.get(0)` возвращал `Object`, и разработчик вручную кастил к нужному типу. Пропустить cast - ClassCastException в рантайме. Дженерики перенесли эту проверку в компилятор. В Rust monomorphization делает дженерики буквально бесплатными - zero overhead по сравнению с ручным кодом.

**Java Collections** - `List<String>`, `Map<K,V>` избавили от бесчисленных `(String) list.get(0)` и ClassCastException
**Rust Vec<T>, HashMap<K,V>** - monomorphization даёт производительность, неотличимую от написанного вручную специализированного кода
**TypeScript generics** - `Promise<T>`, `Array<T>`, React `useState<T>` - весь современный TS API строится на дженериках

Параметрический полиморфизм: одна реализация для всех типов

Функция `identity` принимает значение и возвращает его обратно. На Java 1.4 это писали отдельно для `int`, `String`, `User`. С дженериками - один раз: `id: ∀T. T → T`. Компилятор проверяет корректность для **любого** T без знания конкретного типа.

**Parametricity:** чем более параметрический тип, тем меньше возможных реализаций. Функция `∀T. [T] → [T]` может только переставлять/отфильтровывать элементы - она не может создать новый T из ниоткуда или заглянуть внутрь. Тип - это спецификация.

Функция имеет тип `<T>(items: T[], index: number) => T`. Что гарантирует её сигнатура?

Ограниченные type parameters: только типы с нужными операциями

Чисто параметрический `T` не позволяет ничего сделать со значением - нельзя сложить, сравнить, распечатать. **Ограничения (bounds)** говорят: «T - любой тип, но только если у него есть нужные операции». Разные языки выражают это по-разному.

Язык	Механизм bounds	Пример
Java	extends / implements	<T extends Comparable<T>>
TypeScript	extends (структурный)	<T extends { length: number }>
Rust	Trait bounds	<T: Display + Clone>
Haskell	Typeclass constraints	(Ord a, Show a) => a -> a
C++	Concepts (C++20)	template<std::sortable T>

Зачем нужны bounded type parameters в сравнении с чисто параметрическими `T`?

Вариантность: когда List<Cat> является List<Animal>?

Интуиция подсказывает: `List<Cat>` должен быть `List<Animal>` (ведь кот - животное). Но это ловушка. Если разрешить присвоить `List<Cat>` переменной типа `List<Animal>`, то через эту переменную можно добавить `Dog` в список котов - нарушение типобезопасности. Это проблема **вариантности**.

**Мнемоника PECS (Producer Extends, Consumer Super):** если используешь F как producer (только читаешь) - используй `extends` (ковариантность). Если как consumer (только пишешь) - `super` (контравариантность). Если и то, и другое - инвариантность.

Функция `printAll(List<? extends Animal> list)` принимает `List<Cat>`. Что НЕЛЬЗЯ делать внутри функции?

Type Erasure vs Reification vs Monomorphization

Дженерики можно реализовать тремя способами. Каждый - с разными trade-offs по скорости, размеру бинарника и возможностям рантайма.

Подход	Язык	Суть	Последствие
Type Erasure	Java, Kotlin (JVM)	Типовые параметры удаляются при компиляции; в байткоде только Object	нельзя `instanceof List<String>`, нельзя `new T()`, один `.class`-файл
Reification	C# (.NET)	Типы сохраняются в рантайме; CLR знает `List<int>` vs `List<string>`	можно `typeof(T)`, reflection работает с type args, отдельный JIT per specialization
Monomorphization	Rust, C++ templates	Компилятор генерирует отдельный код для каждого конкретного T	быстрейший рантайм (нет boxing), большой бинарник (code bloat)

Дженерики Java и Rust работают одинаково - просто синтаксический сахар над Object.

Java использует type erasure (один класс для всех T), Rust - monomorphization (отдельный машинный код per T). Это принципиально разные реализации с разными возможностями и trade-offs по производительности.

Java generics добавили в версии 5 с сохранением совместимости со старым байткодом - поэтому erasure. Rust был спроектирован с нуля без этого ограничения, monomorphization даёт zero-cost abstractions.

В Java нельзя написать `new T()` в generic-методе. Почему?