Обобщённое программирование: стили и реализации

Введение

Стиль компьютерного программирования

Обобщённое программирование — это стиль компьютерного программирования, в котором алгоритмы записываются в терминах типов данных, которые будут определены позднее и затем инстанцируются при необходимости для конкретных типов, предоставляемых в качестве параметров. Этот подход, впервые реализованный в языке ML в 1973 году, позволяет создавать универсальные функции или типы, которые различаются только набором типов, над которыми они работают при использовании, тем самым уменьшая дублирование кода. Обобщённое программирование вошло в широкое употребление с языком Ada в 1977 году. С появлением шаблонов в C++ обобщённое программирование стало частью арсенала профессионального проектирования библиотек. Методы были усовершенствованы, а параметризованные типы были введены во влиятельной книге 1994 года «Design Patterns». Новые методы были представлены Андреем Александреску в его книге 2001 года «Современный дизайн C++: обобщённое программирование и шаблоны проектирования». Впоследствии язык D реализовал те же идеи. Такие программные сущности известны как дженерики в Ada, C#, Delphi, Eiffel, F#, Java, Nim, Python, Go, Rust, Swift, TypeScript и Visual Basic NET. Они известны как параметрический полиморфизм в ML, Scala, Julia и Haskell. (Терминология Haskell также использует термин «обобщённый» для связанного, но несколько отличного понятия.) Термин «обобщённое программирование» был первоначально предложен Дэвидом Муссером и Александром Степановым в более узком смысле, чем выше, для описания парадигмы программирования, в которой фундаментальные требования к типам данных абстрагируются из конкретных примеров алгоритмов и структур данных и формализуются в виде концепций, а обобщённые функции реализуются в терминах этих концепций, как правило, с использованием механизмов языковой обобщённости, как описано выше.

Поддержка языка программирования для обобщения

Механизмы обобщения существуют в языках высокого уровня, по крайней мере, с 1970-х годов, в таких языках, как ML, CLU и Ada, и впоследствии были приняты многими языками, основанными на объектной и объектно-ориентированной парадигмах, включая BETA, C++, D, Eiffel, Java и устаревшую Trellis Owl от DEC. Реализация и поддержка обобщения различаются в разных языках программирования; термин "обобщенный" также используется по-разному в различных контекстах программирования. Например, в Forth компилятор может выполнять код во время компиляции, и можно создавать новые ключевые слова компилятора и новые реализации для этих слов "на лету". В нем немного средств для раскрытия поведения компилятора, и поэтому он естественным образом предоставляет возможности обобщения, которые, однако, обычно не называют таковыми в большинстве текстов по Forth. Аналогично, динамически типизированные языки, особенно интерпретируемые, обычно предлагают обобщение по умолчанию, поскольку передача значений функциям и присваивание значений не зависят от типа, и такое поведение часто используется для абстракции или лаконичности кода, однако это обычно не квалифицируется как обобщение, поскольку является прямым следствием используемой в языке динамической системы типизации. Этот термин также использовался в функциональном программировании, в частности, в языках, подобных Haskell, которые используют структурную систему типов, где типы всегда параметрические, а код, работающий с этими типами, является обобщенным. Все эти подходы служат схожей цели – экономии кода и реализации абстракции. Массивы и структуры можно рассматривать как предопределенные обобщенные типы. Каждое использование типа массива или структуры создает новый конкретный тип или повторно использует ранее созданный экземпляр типа. Типы элементов массива и типы элементов структуры являются параметризованными типами, которые используются для создания экземпляра соответствующего обобщенного типа. Все это обычно встроено в компилятор, и синтаксис отличается от других обобщенных конструкций. Некоторые расширяемые языки программирования пытаются объединить встроенные и определяемые пользователем обобщенные типы. Далее следует широкий обзор механизмов обобщения в языках программирования. Для конкретного обзора, сравнивающего пригодность механизмов для обобщенного программирования, см.

Genericity facilities have existed in high level languages since at least the 1970s in languages such as ML, CLU and Ada, and were subsequently adopted by many object based and object oriented languages, including BETA, C++, D, Eiffel, Java, and DEC's now defunct Trellis Owl. Genericity is implemented and supported differently in various programming languages; the term "generic" has also been used differently in various programming contexts. For example, in Forth the compiler can execute code while compiling and one can create new compiler keywords and new implementations for those words on the fly. It has few words that expose the compiler behaviour and therefore naturally offers genericity capacities that, however, are not referred to as such in most Forth texts. Similarly, dynamically typed languages, especially interpreted ones, usually offer genericity by default as both passing values to functions and value assignment are type indifferent and such behavior is often used for abstraction or code terseness, however this is not typically labeled genericity as it's a direct consequence of the dynamic typing system employed by the language. The term has been used in functional programming, specifically in Haskell like languages, which use a structural type system where types are always parametric and the actual code on those types is generic. These uses still serve a similar purpose of code saving and rendering an abstraction. Arrays and structs can be viewed as predefined generic types. Every usage of an array or struct type instantiates a new concrete type, or reuses a previous instantiated type. Array element types and struct element types are parameterized types, which are used to instantiate the corresponding generic type. All this is usually built in in the compiler and the syntax differs from other generic constructs. Some extensible programming languages try to unify built in and user defined generic types. A broad survey of genericity mechanisms in programming languages follows. For a specific survey comparing suitability of mechanisms for generic programming, see.

Дженерики в Ада

Ada поддерживала обобщённое программирование с момента её разработки в 1977–1980 годах. Стандартная библиотека использует обобщённые типы для предоставления множества возможностей. Ada 2005 добавляет в стандартную библиотеку комплексную библиотеку обобщённых контейнеров, вдохновлённую стандартной библиотекой шаблонов C++. Обобщённый модуль – это пакет или подпрограмма, принимающая один или несколько обобщённых формальных параметров. Обобщённый формальный параметр может быть значением, переменной, константой, типом, подпрограммой или даже экземпляром другого, указанного, обобщённого модуля. Для обобщённых формальных типов синтаксис различает дискретные, с плавающей точкой, с фиксированной точкой, типы доступа (указатели) и другие. Некоторые формальные параметры могут иметь значения по умолчанию. Для создания экземпляра обобщённого модуля программист передаёт фактические параметры для каждого формального параметра. Полученный обобщённый экземпляр ведёт себя как любой другой модуль. Возможно создание экземпляров обобщённых модулей во время выполнения, например, внутри цикла.

Шаблоны на C++

C++ использует шаблоны для реализации техник обобщенного программирования. Стандартная библиотека C++ включает в себя Стандартную библиотеку шаблонов (STL), предоставляющую основу из шаблонов для распространенных структур данных и алгоритмов. Шаблоны в C++ также могут применяться для метапрограммирования шаблонов, представляющего собой способ предварительной оценки части кода на этапе компиляции, а не во время выполнения. Благодаря специализации шаблонов, шаблоны C++ являются Тьюринг-полными.

Специализация шаблонов

Мощная особенность шаблонов C++ — специализация шаблонов. Она позволяет предоставлять альтернативные реализации в зависимости от определенных характеристик параметризованного типа, для которого производится инстанцирование. Специализация шаблонов преследует две цели: обеспечение определенных видов оптимизации и уменьшение раздувания кода. Например, рассмотрим шаблонную функцию сортировки. Одной из основных задач такой функции является обмен значениями в двух позициях контейнера. Если значения велики (с точки зрения объема памяти, необходимого для хранения каждого из них), то часто быстрее сначала создать отдельный список указателей на объекты, отсортировать эти указатели, а затем построить окончательную отсортированную последовательность. Однако, если значения достаточно малы, обычно быстрее всего просто обменивать значения непосредственно по мере необходимости. Более того, если параметризованный тип уже является типом указателя, то нет необходимости создавать отдельный массив указателей. Специализация шаблонов позволяет автору шаблона создавать различные реализации и указывать характеристики, которым должен соответствовать параметризованный тип (или типы) для использования каждой реализации. В отличие от шаблонов функций, шаблоны классов могут быть частично специализированы. Это означает, что альтернативная версия кода шаблона класса может быть предоставлена, когда некоторые параметры шаблона известны, а остальные параметры остаются обобщенными. Это можно использовать, например, для создания реализации по умолчанию (основной специализации), которая предполагает, что копирование параметризующего типа является дорогостоящей операцией, а затем создать частичные специализации для типов, копирование которых дешево, тем самым повышая общую эффективность. Клиенты такого шаблона класса просто используют его специализации, не зная, использовал ли компилятор основную специализацию или какую-либо частичную специализацию в каждом конкретном случае. Шаблоны классов также могут быть полностью специализированы, что означает, что альтернативная реализация может быть предоставлена, когда известны все типы параметризации.

A powerful feature of C++'s templates is template specialization. This allows alternative implementations to be provided based on certain characteristics of the parameterized type that is being instantiated. Template specialization has two purposes: to allow certain forms of optimization, and to reduce code bloat. For example, consider a sort template function. One of the primary activities that such a function does is to swap or exchange the values in two of the container's positions. If the values are large (in terms of the number of bytes it takes to store each of them), then it is often quicker to first build a separate list of pointers to the objects, sort those pointers, and then build the final sorted sequence. If the values are quite small however it is usually fastest to just swap the values in place as needed. Furthermore, if the parameterized type is already of some pointer type, then there is no need to build a separate pointer array. Template specialization allows the template creator to write different implementations and to specify the characteristics that the parameterized type(s) must have for each implementation to be used. Unlike function templates, class templates can be partially specialized. That means that an alternate version of the class template code can be provided when some of the template parameters are known, while leaving other template parameters generic. This can be used, for example, to create a default implementation (the primary specialization) that assumes that copying a parameterizing type is expensive and then create partial specializations for types that are cheap to copy, thus increasing overall efficiency. Clients of such a class template just use specializations of it without needing to know whether the compiler used the primary specialization or some partial specialization in each case. Class templates can also be fully specialized, which means that an alternate implementation can be provided when all of the parameterizing types are known.

Общественность в Эйфеле

Общие классы были частью Eiffel с момента первоначальной разработки метода и языка. В основополагающих публикациях по Eiffel используется термин "генеричность" для описания создания и использования общих классов.

Генерики на Яве

Поддержка генериков, или "контейнеров типа T", была добавлена в язык программирования Java в 2004 году в составе J2SE 5.0. В Java генерики проверяются на корректность типов только во время компиляции. Затем информация о генерическом типе удаляется посредством процесса, называемого стиранием типов, для обеспечения совместимости со старыми реализациями JVM, что делает её недоступной во время выполнения. Например, List<String> преобразуется к исходному типу List. Компилятор добавляет приведения типов для преобразования элементов к типу String при их извлечении из списка, что снижает производительность по сравнению с другими реализациями, такими как шаблоны C++.