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

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

Мне сразу вспоминается STL, стандартная библиотека шаблонов C++. Это, пожалуй, наиболее известный пример полиморфизма — наборы универсальных коллекций, работающих с любыми типами. Шаблоны C++ представляют собой пример т.н. мономорфизма. На самом деле, для каждого типа из шаблона компилируется свой класс, который работает только с этим типом. Например, если мы используем шаблонный класс vector<T> дважды, один раз для int, другой раз для long, то будет скомпилировано два класса — vector<int> и vector<long>. Какой из них будет использоваться, будет решено на стадии линковки, в зависимости от типа аргумента. Усматривается прямая аналогия с перегрузкой функций, и это правильно — явления мономорфизма и перегрузки функций относят к общему классу ad-hoc полиморфизмов.

Кстати, все шаблонные классы и функции в C++ должны быть вынесены в заголовочные файлы именно потому, что их приходится перекомпилировать при использовании с каждым новым типом. Если бы шаблонные функции были объявлены только в исходных файлах, предполагалось бы, что они должны компилироваться лишь единожды, что возможно только, если все возможные типы аргументов известны.

У мономорфизма есть еще один минус — при использовании шаблонного класса с множеством различных параметров для каждого сочетания типов приходится компилировать бинарный код, в итоге объем бинарника существенно разрастается. Об этом я  писал в предыдущей заметке.

Противоположность мономорфизма — параметрический полиморфизм, или абстракция типа. В этом случае код принимает типы данных как параметры. Это позволяет компилировать код лишь однажды, но требует дополнительных действий по преобразованию типов в рантайме.

Пример параметрического полиморфизма — generic’и в Java. Класс с generic’ом (обобщенным типом) компилируется только один раз. При этом в байт-код в нужных местах добавляются проверки и приведения типов. Это защищает разработчика от попытки добавить в List<Cat> объект типа Dog, но немного понижает скорость работы. К счастью, такие проверки обычно успешно оптимизируется виртуальной машиной.

У полиморфизма в Java  есть существенный минус — параметром типа может быть только объект, но не примитив. Корни этой слабости уходят глубоко в недра JVM, а вот последствия каждый Java-разработчик ощущает на себе — эффективно использовать generic-классы для примитивов не получается. Нельзя просто так запихнуть int в HashMap, его приходится сначала обернуть в объект типа Integer.

Один из способов обойти это ограничение — специализация. О других мы поговорим позже.

Дополнительное чтение: