Универсальное программирование — это стиль компьютерного программирования, в котором алгоритмы записываются в терминах типов , которые должны быть определены позже , а затем при необходимости создаются экземпляры для конкретных типов, предоставляемых в качестве параметров . Этот подход, впервые примененный в языке программирования ML в 1973 году [1] [2] , позволяет писать общие функции или типы , которые отличаются только набором типов, с которыми они работают при использовании, тем самым уменьшая дублирование . Такие программные объекты известны как дженерики в Ada , C#., Delphi , Eiffel , F# , Java , Nim , Python , Rust , Swift , TypeScript и Visual Basic .NET . Они известны как параметрический полиморфизм в ML , Scala , Julia и Haskell (сообщество Haskell также использует термин «общий» для родственной, но несколько иной концепции); шаблоны на C++ и D ; и параметризованные типы во влиятельной книге 1994 годаШаблоны дизайна . [3]
Термин «универсальное программирование» был первоначально придуман Дэвидом Мюссером и Александром Степановым [4] в более конкретном смысле, чем указанный выше, для описания парадигмы программирования, в которой фундаментальные требования к типам абстрагируются от конкретных примеров алгоритмов и структур данных и формализуются. как концепции с универсальными функциями , реализованными в терминах этих понятий, обычно с использованием языковых механизмов универсальности, как описано выше.
Общее программирование основано на идее абстрагирования от конкретных эффективных алгоритмов для получения общих алгоритмов, которые можно комбинировать с различными представлениями данных для создания широкого спектра полезного программного обеспечения.
Парадигма «общего программирования» — это подход к декомпозиции программного обеспечения, при котором основные требования к типам абстрагируются от конкретных примеров алгоритмов и структур данных и формализуются в виде понятий , аналогично абстракции алгебраических теорий в абстрактной алгебре . [6] Ранние примеры этого подхода к программированию были реализованы в Scheme и Ada, [7] хотя наиболее известным примером является Стандартная библиотека шаблонов (STL), [8] [9] , которая разработала теорию итераторов , которая используется для разделения структуры данных последовательности и алгоритмы, работающие с ними.
Например, при наличии N структур данных последовательности, например односвязного списка, вектора и т. д., и M алгоритмов для работы с ними, например find, sortи т. д., прямой подход реализовывал бы каждый алгоритм специально для каждой структуры данных, давая N × M комбинаций для воплощать в жизнь. Однако в общем подходе к программированию каждая структура данных возвращает модель концепции итератора (простой тип значения, который может быть разыменован для извлечения текущего значения или изменен для указания на другое значение в последовательности), и вместо этого каждый алгоритм записывается обычно с аргументами таких итераторов, например, пара итераторов, указывающих на начало и конец подпоследовательности или диапазонаобрабатывать. Таким образом, необходимо реализовать только N + M комбинаций структуры данных и алгоритма. В STL определено несколько концепций итераторов, каждая из которых является уточнением более ограничительных концепций, например, прямые итераторы обеспечивают перемещение только к следующему значению в последовательности (например, подходят для односвязного списка или потока входных данных), тогда как произвольный доступ итератор также обеспечивает прямой доступ в постоянное время к любому элементу последовательности (например, подходит для вектора). Важным моментом является то, что структура данных вернет модель самой общей концепции, которую можно эффективно реализовать — вычислительная сложность .требования явно являются частью определения понятия. Это ограничивает структуры данных, к которым может применяться данный алгоритм, и такие требования к сложности являются основным фактором, определяющим выбор структуры данных. Аналогичным образом универсальное программирование применялось и в других областях, например, в графовых алгоритмах. [10]
Обратите внимание, что, хотя этот подход часто использует языковые функции универсальности/шаблонов времени компиляции , на самом деле он не зависит от конкретных технических деталей языка. Пионер универсального программирования Александр Степанов писал: