Универсальное программирование — это стиль компьютерного программирования , в котором алгоритмы записываются с использованием типов данных, которые должны быть указаны позже, а затем при необходимости создаются экземпляры для конкретных типов, представленных в качестве параметров . Этот подход, впервые использованный в языке программирования ML в 1973 году [1] [2], позволяет писать общие функции или типы , которые отличаются только набором типов, с которыми они работают при использовании, тем самым уменьшая дублирование кода .
Универсальное программирование стало широко распространенным вместе с Ada в 1977 году. С появлением шаблонов на C++ универсальное программирование стало частью репертуара профессионального проектирования библиотек. Техники были усовершенствованы, и параметризованные типы были представлены во влиятельной книге Design Patterns 1994 года . [3]
Новые методы были представлены Андреем Александреску в его книге 2001 года « Современный дизайн на C++: общее программирование и применение шаблонов проектирования» . Впоследствии D реализовал те же идеи.
Такие программные объекты известны как дженерики в Ada , C# , Delphi , Eiffel , F# , Java , Nim , Python , Go , Rust , Swift , TypeScript и Visual Basic .NET . Они известны как параметрический полиморфизм в ML , Scala , Julia и Haskell . (В терминологии Haskell также используется термин «общий» для обозначения родственной, но несколько иной концепции.)
Термин «обобщенное программирование» был первоначально введен Дэвидом Массером и Александром Степановым [4] в более конкретном смысле, чем приведенный выше, для описания парадигмы программирования, в которой фундаментальные требования к типам данных абстрагируются от конкретных примеров алгоритмов и структур данных и формализуются. как концепции , с общими функциями , реализованными в терминах этих концепций, обычно с использованием языковых механизмов универсальности, как описано выше.
Общее программирование определяется в Musser & Stepanov (1989) следующим образом:
Универсальное программирование основано на идее абстрагирования от конкретных эффективных алгоритмов для получения универсальных алгоритмов, которые можно комбинировать с различными представлениями данных для создания широкого спектра полезного программного обеспечения.
- Массер, Дэвид Р.; Степанов, Александр А., Общее программирование [5]
Парадигма «общего программирования» — это подход к декомпозиции программного обеспечения, при котором фундаментальные требования к типам абстрагируются от конкретных примеров алгоритмов и структур данных и формализуются в виде концепций , аналогично абстракции алгебраических теорий в абстрактной алгебре . [6] Ранние примеры этого подхода к программированию были реализованы в Scheme и Ada, [7] хотя наиболее известным примером является Стандартная библиотека шаблонов (STL), [8] [9] которая разработала теорию итераторов , которая используется для разделения Структуры данных последовательности и алгоритмы, работающие с ними.
Например, при наличии N структур данных последовательности, например, односвязного списка, вектора и т. д., и M алгоритмов для работы с ними, например find
и sort
т. д., прямой подход будет реализовывать каждый алгоритм специально для каждой структуры данных, предоставляя N × M комбинаций для осуществлять. Однако в универсальном подходе к программированию каждая структура данных возвращает модель концепции итератора (простой тип значения, который можно разыменовать для получения текущего значения или изменить, чтобы он указывал на другое значение в последовательности), и вместо этого каждый алгоритм записывается в общем случае с аргументами таких итераторов, например, пары итераторов, указывающих на начало и конец подпоследовательности или диапазона для обработки. Таким образом, необходимо реализовать только N + M комбинаций структуры данных и алгоритма. В STL указано несколько концепций итераторов, каждая из которых является усовершенствованием более ограничительных концепций, например, итераторы прямого доступа обеспечивают только переход к следующему значению в последовательности (например, подходят для односвязного списка или потока входных данных), тогда как итераторы с произвольным доступом итератор также обеспечивает прямой доступ с постоянным временем к любому элементу последовательности (например, подходящему для вектора). Важным моментом является то, что структура данных будет возвращать модель самой общей концепции, которую можно эффективно реализовать — требования к вычислительной сложности явно являются частью определения концепции. Это ограничивает структуры данных, к которым может применяться данный алгоритм, и такие требования к сложности являются основным фактором, определяющим выбор структуры данных. Общее программирование аналогичным образом применялось и в других областях, например, в графовых алгоритмах. [10]
Хотя этот подход часто использует языковые особенности универсальности и шаблонов во время компиляции , он не зависит от конкретных технических деталей языка. Пионер универсального программирования Александр Степанов писал:
Общее программирование — это абстрагирование и классификация алгоритмов и структур данных. Он черпает вдохновение у Кнута , а не из теории типов. Его цель — постепенное построение систематических каталогов полезных, эффективных и абстрактных алгоритмов и структур данных. Такое предприятие пока остается мечтой.
- Александр Степанов, Краткая история STL [11] [12]
Я считаю, что теории итераторов так же важны для информатики, как теории колец или банаховых пространств являются центральными для математики.
— Александр Степанов, Интервью с А. Степановым [13]
Бьёрн Страуструп отметил:
Следуя Степанову, мы можем определить общее программирование, не упоминая особенностей языка: Поднимите алгоритмы и структуры данных от конкретных примеров до их наиболее общей и абстрактной формы.
- Бьерн Страуструп, Развитие языка в реальном мире и для него: C++ 1991-2006 [12]
Другие парадигмы программирования, которые были описаны как универсальное программирование, включают универсальное программирование типов данных , как описано в «Общее программирование – введение». [14] Подход «Отбросьте свой шаблон» — это облегченный универсальный подход к программированию для Haskell. [15]
В этой статье мы отличаем парадигмы обобщенного программирования высокого уровня , описанные выше, от механизмов универсальности языка программирования нижнего уровня, используемых для их реализации (см. Поддержка универсальности в языках программирования). Дальнейшее обсуждение и сравнение общих парадигм программирования см. [16]
Средства обобщения существовали в языках высокого уровня, по крайней мере, с 1970-х годов в таких языках, как ML , CLU и Ada , и впоследствии были приняты многими объектно-ориентированными и объектно-ориентированными языками, включая BETA , C++ , D , Eiffel , Java , и ныне несуществующая компания DEC Trellis-Owl .
Универсальность реализуется и поддерживается по-разному в разных языках программирования; термин «общий» также использовался по-разному в различных контекстах программирования. Например, в Форте компилятор может выполнять код во время компиляции, и можно на лету создавать новые ключевые слова компилятора и новые реализации для этих слов. В нем мало слов , раскрывающих поведение компилятора, и поэтому он, естественно, предлагает возможности универсальности , которые, однако, не упоминаются как таковые в большинстве текстов на Форте. Аналогичным образом, динамически типизированные языки, особенно интерпретируемые, обычно предлагают универсальность по умолчанию, поскольку как передача значений в функции, так и присвоение значений не зависят от типа, и такое поведение часто используется для абстракции или краткости кода, однако это обычно не обозначается как универсальность , поскольку это прямое следствие системы динамической типизации, используемой в языке. [ нужна цитация ] Этот термин использовался в функциональном программировании , особенно в Haskell- подобных языках, которые используют систему структурных типов , где типы всегда являются параметрическими, а фактический код для этих типов является универсальным. Эти варианты использования по-прежнему служат той же цели: сохранения кода и визуализации абстракции.
Массивы и структуры можно рассматривать как предопределенные универсальные типы. Каждое использование типа массива или структуры создает экземпляр нового конкретного типа или повторно использует предыдущий созданный тип. Типы элементов массива и типы элементов структуры — это параметризованные типы, которые используются для создания экземпляра соответствующего универсального типа. Все это обычно встроено в компилятор и синтаксис отличается от других универсальных конструкций. Некоторые расширяемые языки программирования пытаются унифицировать встроенные и определяемые пользователем универсальные типы.
Далее следует широкий обзор механизмов универсальности в языках программирования. Конкретный обзор, сравнивающий пригодность механизмов для общего программирования, см. [17]
При создании классов-контейнеров в статически типизированных языках неудобно писать конкретные реализации для каждого содержащегося типа данных, особенно если код для каждого типа данных практически идентичен. Например, в C++ это дублирование кода можно обойти, определив шаблон класса:
template < typename T > class List { // Содержимое класса. }; List < Животное > list_of_animals ; List < Автомобиль > list_of_cars ;
Выше — T
заполнитель для любого типа, указанного при создании списка. Эти «контейнеры типа T», обычно называемые шаблонами , позволяют повторно использовать класс с разными типами данных при условии сохранения определенных контрактов, таких как подтипы и подпись . Этот механизм универсальности не следует путать с полиморфизмом включения , который представляет собой алгоритмическое использование заменяемых подклассов: например, список объектов типа Moving_Object
, содержащий объекты типа Animal
и Car
. Шаблоны также можно использовать для независимых от типа функций, как показано в Swap
примере ниже:
// "&" обозначает шаблон ссылки < имя типа T > void Swap ( T & a , T & b ) { // Аналогичная, но более безопасная и потенциально более быстрая функция // определена в заголовке стандартной библиотеки <utility> T temp = б ; б = а ; а = температура ; } std :: string world = "Мир!" ; std :: string hello = "Привет," ; Обмен ( мир , привет ); std :: cout << world << hello << '\ n ' ; // Вывод: «Привет, мир!».
Использованная выше конструкция C++ template
широко упоминается [ нужна ссылка ] как конструкция универсальности, которая популяризировала это понятие среди программистов и разработчиков языков и поддерживает множество общих идиом программирования. Язык программирования D также предлагает полностью универсальные шаблоны, основанные на прецеденте C++, но с упрощенным синтаксисом. Язык программирования Java предоставляет возможности обобщения, синтаксически основанные на C++, с момента появления платформы Java Standard Edition (J2SE) 5.0.
В C# 2.0, Oxygene 1.5 (ранее Chrome) и Visual Basic .NET 2005 есть конструкции, использующие поддержку универсальных шаблонов, присутствующих в Microsoft .NET Framework, начиная с версии 2.0.
Обобщенные коды Ada существуют с момента их первой разработки в 1977–1980 годах. Стандартная библиотека использует дженерики для предоставления множества сервисов. Ada 2005 добавляет к стандартной библиотеке комплексную библиотеку универсальных контейнеров, вдохновленную стандартной библиотекой шаблонов C++ .
Общий модуль — это пакет или подпрограмма, принимающая один или несколько общих формальных параметров .
Общий формальный параметр — это значение, переменная, константа, тип, подпрограмма или даже экземпляр другой назначенной универсальной единицы. Для общих формальных типов синтаксис различает дискретные типы, типы с плавающей запятой, фиксированной запятой, типы доступа (указатели) и т. д. Некоторые формальные параметры могут иметь значения по умолчанию.
Чтобы создать экземпляр универсального модуля, программист передает фактические параметры для каждого формального элемента. В этом случае универсальный экземпляр ведет себя так же, как и любой другой модуль. Можно создавать экземпляры универсальных модулей во время выполнения , например, внутри цикла.
Спецификация универсального пакета:
общий Max_Size : Natural ; -- общий тип формального значения Element_Type является частным ; -- общий формальный тип; принимает любой пакет неограниченного типа. Стеки имеют тип Size_Type — диапазон 0 .. Max_Size ; тип стека ограничен частным ; процедура Create ( S : out Stack ; Initial_Size : in Size_Type := Max_Size ); процедура Push ( Into : in out Stack ; Element : in Element_Type ); процедура Pop ( From : in out Stack ; Element : out Element_Type ); Переполнение : исключение ; Недополнение : исключение ; частный подтип Index_Type — это диапазон Size_Type 1 .. Max_Size ; type Vector — это массив ( диапазон Index_Type <>) из Element_Type ; тип Stack ( Allocated_Size : Size_Type := 0 ) — это запись Top : Index_Type ; Хранилище : векторное ( 1 .. Allocated_Size ); завершить запись ; конец стеков ;
Создание экземпляра общего пакета:
тип Bookmark_Type новый Natural ; -- записывает местоположение в текстовом документе, который мы редактируем пакет Bookmark_Stacks — это новые стеки ( Max_Size => 20 , Element_Type => Bookmark_Type ); -- Позволяет пользователю переключаться между записанными местами в документе.
Использование экземпляра универсального пакета:
type Document_Type — это запись. Содержание : Ada . Струны . Неограниченный . Неограниченная_Строка ; Закладки : Bookmark_Stacks . Куча ; завершить запись ; процедура Edit ( Document_Name : in String ) — Document : Document_Type ; начало — Инициализировать стек закладок: Bookmark_Stacks . Создать ( S => Document . Bookmarks , Initial_Size => 10 ); -- Теперь откройте файл Document_Name и прочитайте его... end Edit ;
Синтаксис языка позволяет точно указать ограничения на общие формальные параметры. Например, можно указать, что универсальный формальный тип будет принимать в качестве фактического только модульный тип. Также возможно выразить ограничения между общими формальными параметрами; например:
универсальный тип Index_Type равен (<>); -- должен быть дискретным типом. Тип Element_Type является частным ; -- может быть любым неограниченным типом. Array_Type — это массив ( диапазон Index_Type <>) из Element_Type ;
В этом примере Array_Type ограничен как Index_Type, так и Element_Type. При создании экземпляра модуля программист должен передать фактический тип массива, удовлетворяющий этим ограничениям.
Недостатком этого детального управления является сложный синтаксис, но, поскольку все формальные параметры обобщения полностью определены в спецификации, компилятор может создавать экземпляры обобщений, не просматривая тело обобщения.
В отличие от C++, Ada не допускает создания специализированных обобщенных экземпляров и требует, чтобы все обобщенные экземпляры создавались явно. Эти правила имеют несколько последствий:
C++ использует шаблоны для реализации общих методов программирования. Стандартная библиотека C++ включает в себя стандартную библиотеку шаблонов или STL, которая предоставляет структуру шаблонов для общих структур данных и алгоритмов. Шаблоны в C++ также могут использоваться для метапрограммирования шаблонов , что представляет собой способ предварительной оценки части кода во время компиляции, а не во время выполнения . Благодаря специализации шаблонов шаблоны C++ являются полными по Тьюрингу .
Существует множество типов шаблонов, наиболее распространенными из которых являются шаблоны функций и шаблоны классов. Шаблон функции — это шаблон для создания обычных функций на основе типов параметризации, предоставляемых при создании экземпляра. Например, стандартная библиотека шаблонов C++ содержит шаблон функции max(x, y)
, который создает функции, возвращающие либо x , либо y, в зависимости от того, какое значение больше. max()
можно определить так:
шаблон < имя типа T > T max ( T x , T y ) { return x < y ? у : х ; }
Специализации этого шаблона функции, экземпляры определенных типов, можно вызывать так же, как обычную функцию:
std :: cout << max ( 3 , 7 ); // Выходы 7.
Компилятор проверяет аргументы, используемые для вызова, max
и определяет, что это вызов max(int, int)
. Затем он создает экземпляр версии функции, где тип параметризации T
равен int
, что делает эквивалент следующей функции:
int max ( int x , int y ) { return x < y ? у : х ; }
Это работает независимо от того, являются ли аргументы x
и y
целыми числами, строками или любым другим типом, для которого выражение x < y
является разумным, или, более конкретно, для любого типа, для которого operator<
определено. Общее наследование не требуется для набора типов, которые можно использовать, поэтому оно очень похоже на утиную типизацию . Программа, определяющая пользовательский тип данных, может использовать перегрузку операторов , чтобы определить значение <
этого типа, что позволяет использовать его с max()
шаблоном функции. Хотя в этом изолированном примере это может показаться незначительным преимуществом, в контексте такой комплексной библиотеки, как STL, это позволяет программисту получить обширную функциональность для нового типа данных, просто определив для него несколько операторов. Простое определение <
позволяет использовать тип со стандартными алгоритмами sort()
, stable_sort()
и binary_search()
или помещать его внутри структур данных, таких как set
s, кучи и ассоциативные массивы .
Шаблоны C++ полностью типобезопасны во время компиляции. В качестве демонстрации стандартный тип complex
не определяет <
оператор, поскольку не существует строгого порядка для комплексных чисел . Следовательно, max(x, y)
компиляция завершится ошибкой, если x и y являются complex
значениями. Аналогично, другие шаблоны, на которые полагаются, <
не могут быть применены к complex
данным, если не предоставлено сравнение (в форме функтора или функции). Например: A complex
не может использоваться в качестве ключа для a map
, если не предоставлено сравнение. К сожалению, исторически компиляторы генерируют несколько эзотерические, длинные и бесполезные сообщения об ошибках такого рода. Обеспечение соответствия определенного объекта протоколу метода может решить эту проблему. Языки, которые используют compare
вместо, <
также могут использовать complex
значения в качестве ключей.
Другой тип шаблона — шаблон класса — распространяет ту же концепцию на классы. Специализация шаблона класса — это класс. Шаблоны классов часто используются для создания универсальных контейнеров. Например, в STL есть контейнер связанного списка . Чтобы создать связанный список целых чисел, пишут list<int>
. Обозначается список строк list<string>
. A list
имеет набор связанных с ним стандартных функций, которые работают для любых совместимых типов параметризации.
Мощной особенностью шаблонов C++ является специализация шаблонов . Это позволяет предоставлять альтернативные реализации на основе определенных характеристик параметризованного типа, экземпляр которого создается. Специализация шаблонов преследует две цели: обеспечить определенные формы оптимизации и уменьшить раздувание кода.
Например, рассмотрим sort()
функцию шаблона. Одним из основных действий, выполняемых такой функцией, является замена значений в двух позициях контейнера. Если значения большие (с точки зрения количества байтов, необходимых для хранения каждого из них), то часто бывает быстрее сначала создать отдельный список указателей на объекты, отсортировать эти указатели, а затем построить окончательную отсортированную последовательность. . Однако если значения довольно малы, обычно быстрее всего просто поменять местами значения по мере необходимости. Более того, если параметризованный тип уже относится к некоторому типу указателя, нет необходимости создавать отдельный массив указателей. Специализация шаблона позволяет создателю шаблона писать различные реализации и указывать характеристики, которые параметризованный тип(ы) должен иметь для каждой используемой реализации.
В отличие от шаблонов функций, шаблоны классов могут быть частично специализированными . Это означает, что альтернативная версия кода шаблона класса может быть предоставлена, когда некоторые параметры шаблона известны, оставляя при этом другие параметры шаблона общими. Это можно использовать, например, для создания реализации по умолчанию (основная специализация ), которая предполагает, что копирование параметризуемого типа является дорогостоящим, а затем создать частичные специализации для типов, копировать которые дешево, тем самым увеличивая общую эффективность. Клиенты такого шаблона класса просто используют его специализации, не зная, использовал ли компилятор в каждом случае первичную специализацию или некоторую частичную специализацию. Шаблоны классов также могут быть полностью специализированными, а это означает, что альтернативная реализация может быть предоставлена, когда известны все типы параметризации.
Некоторые варианты использования шаблонов, такие как max()
функции, ранее заполнялись макросами препроцессора , похожими на функции (наследие языка C ). Например, вот возможная реализация такого макроса:
#define max(a,b) ((a) < (b) ? (b) : (a))
Макросы расширяются (копируются) препроцессором перед правильной компиляцией; шаблоны — это настоящие реальные функции. Макросы всегда раскрываются в строке; шаблоны также могут быть встроенными функциями , если компилятор сочтет это целесообразным.
Однако для этих целей шаблоны обычно считаются улучшением по сравнению с макросами. Шаблоны типобезопасны. Шаблоны позволяют избежать некоторых распространенных ошибок, встречающихся в коде, в котором интенсивно используются макросы, подобные функциям, например, двойная оценка параметров с побочными эффектами. Возможно, самое главное, шаблоны были разработаны для решения гораздо более серьезных задач, чем макросы.
Есть четыре основных недостатка использования шаблонов: поддерживаемые функции, поддержка компилятора, плохие сообщения об ошибках (обычно с SFINAE до C++20 ) и раздувание кода :
Итак, можно ли использовать деривацию для уменьшения проблемы репликации кода из-за использования шаблонов? Это потребует получения шаблона от обычного класса. Этот метод оказался успешным в борьбе с раздуванием кода в реальном использовании. Люди, которые не используют подобную технику, обнаружили, что реплицируемый код может занимать мегабайты кодового пространства даже в программах среднего размера.
- Бьерн Страуструп , Проектирование и эволюция C++, 1994 г. [19]
Дополнительные экземпляры, генерируемые шаблонами, также могут привести к тому, что некоторые отладчики будут испытывать трудности с корректной работой с шаблонами. Например, при установке точки останова отладки в шаблоне из исходного файла может либо не быть установлена точка останова в желаемом фактическом создании экземпляра, либо может быть установлена точка останова в каждом месте, где создается экземпляр шаблона.
Кроме того, исходный код реализации шаблона должен быть полностью доступен (например, включен в заголовок) для использующей его единицы перевода (исходного файла). Шаблоны, включая большую часть стандартной библиотеки, если они не включены в файлы заголовков, не могут быть скомпилированы. (В отличие от нешаблонного кода, который может быть скомпилирован в двоичный формат, предоставляя только файл заголовка объявлений для кода, использующего его.) Это может быть недостатком, поскольку раскрывается код реализации, который удаляет некоторые абстракции и может ограничить его. использование в проектах с закрытым исходным кодом. [ нужна цитата ]
Язык D поддерживает шаблоны, основанные на C++. Большинство идиом шаблонов C++ работают в D без изменений, но D добавляет некоторые функциональные возможности:
static if
оператор предоставляют альтернативу концепциям C ++ и if constexpr
.is(...)
позволяет спекулятивное создание экземпляров для проверки свойств объекта во время компиляции.auto
слово и typeof
выражение позволяют выводить тип для объявлений переменных и возвращаемых значений функции, что, в свою очередь, позволяет использовать «типы Волдеморта» (типы, не имеющие глобального имени). [20]Шаблоны в D используют другой синтаксис, чем в C++: тогда как в C++ параметры шаблона заключаются в угловые скобки ( Template<param1, param2>
), D использует восклицательный знак и круглые скобки: Template!(param1, param2)
. Это позволяет избежать трудностей синтаксического анализа C++ из-за неоднозначности операторов сравнения. Если параметр только один, круглые скобки можно опустить.
Традиционно D объединяет вышеперечисленные функции для обеспечения полиморфизма во время компиляции с использованием универсального программирования на основе признаков. Например, входной диапазон определяется как любой тип, который удовлетворяет проверкам, выполняемым isInputRange
, что определяется следующим образом:
template isInputRange ( R ) { enum bool isInputRange = is ( typeof ( ( inout int = 0 ) { R r = R . init ; // можно определить объект диапазона if ( r . пустой ) {} // можно проверить пустой r .popFront (); // можно вызвать popFront () auto h = r .front ; // можно получить начало диапазона })) ; }
Функция, которая принимает только входные диапазоны, может затем использовать приведенный выше шаблон в ограничении шаблона:
auto fun ( Диапазон )( Диапазон диапазона ) if ( isInputRange ! Диапазон ) { // ... }
В дополнение к метапрограммированию шаблонов, D также предоставляет несколько функций, позволяющих генерировать код во время компиляции:
import
позволяет читать файл с диска и использовать его содержимое в виде строкового выражения.Объединение вышеизложенного позволяет генерировать код на основе существующих объявлений. Например, платформы сериализации D могут перечислять члены типа и создавать специализированные функции для каждого сериализованного типа для выполнения сериализации и десериализации. Определенные пользователем атрибуты могут дополнительно указывать правила сериализации.
Выполнение выражений import
и функций во время компиляции также позволяет эффективно реализовывать языки, специфичные для предметной области . Например, если есть функция, которая принимает строку, содержащую шаблон HTML, и возвращает эквивалентный исходный код D, ее можно использовать следующим образом:
// Импортируем содержимое example.htt как константу строкового манифеста. enum htmlTemplate = import ( «example.htt» ); // Транспилируем HTML-шаблон в D-код. перечисление htmlDCode = htmlTemplateToD ( htmlTemplate ); // Вставляем содержимое htmlDCode как D-код. миксин ( htmlDCode );
Универсальные классы были частью Eiffel с момента создания оригинального метода и языка. В фундаментальных публикациях Эйфеля [21] [22] используется термин универсальность для описания создания и использования обобщенных классов.
Универсальные классы объявляются с указанием имени класса и списка одного или нескольких формальных универсальных параметров . В следующем коде класс LIST
имеет один формальный универсальный параметр.G
class LIST [ G ] ... Feature — Доступ к элементу : G — Элемент, на который в данный момент указывает курсор ... Feature — Изменение элемента put ( new_item : G ) — Добавить `new_item' в конец списка ...
Формальные универсальные параметры — это заполнители для произвольных имен классов, которые будут предоставлены при объявлении универсального класса, как показано в двух универсальных производных вариантах ниже, где ACCOUNT
и DEPOSIT
— другие имена классов. ACCOUNT
и DEPOSIT
считаются фактическими универсальными параметрами, поскольку они предоставляют реальные имена классов, которые можно заменить G
при фактическом использовании.
list_of_accounts : LIST [ АККАУНТ ] — Список аккаунтов list_of_deposits : LIST [ ДЕПОЗИТ ] -- Список депозитов
В системе типов Эйфеля класс, хотя и LIST [G]
считается классом, не считается типом. Однако родовое происхождение LIST [G]
такого типа LIST [ACCOUNT]
считается типом.
Для класса списка, показанного выше, фактический универсальный параметр, заменяющий, G
может быть любым другим доступным классом. Чтобы ограничить набор классов, из которых можно выбрать действительные фактические универсальные параметры, можно указать универсальное ограничение . В объявлении класса SORTED_LIST
ниже универсальное ограничение требует, чтобы любой действительный фактический универсальный параметр был классом, наследуемым от class COMPARABLE
. Общее ограничение гарантирует, что элементы a SORTED_LIST
действительно могут быть отсортированы.
класс SORTED_LIST [ G -> СРАВНЕННЫЙ ]
Поддержка дженериков или «контейнеров типа T» была добавлена в язык программирования Java в 2004 году как часть J2SE 5.0. В Java дженерики проверяются только во время компиляции на правильность типа. Информация об общем типе затем удаляется с помощью процесса, называемого стиранием типа , для обеспечения совместимости со старыми реализациями JVM , что делает ее недоступной во время выполнения. [23] Например, a List<String>
преобразуется в необработанный тип List
. Компилятор вставляет приведение типов для преобразования элементов в String
тип при их извлечении из списка, что снижает производительность по сравнению с другими реализациями, такими как шаблоны C++.
Обобщенные шаблоны были добавлены как часть .NET Framework 2.0 в ноябре 2005 года на основе исследовательского прототипа, проведенного Microsoft Research, начатого в 1999 году . –209 , но реализуйте дженерики как первоклассный механизм во время выполнения, используя реификацию . Этот выбор дизайна обеспечивает дополнительные функциональные возможности, такие как возможность отражения с сохранением универсальных типов и смягчение некоторых ограничений стирания (например, невозможность создания универсальных массивов). [26] [27] Это также означает, что приведение типов во время выполнения и обычно дорогостоящие преобразования упаковки не влияют на производительность . Когда примитивные типы и типы значений используются в качестве универсальных аргументов, они получают специализированные реализации, позволяющие создавать эффективные универсальные коллекции и методы. Как и в C++ и Java, вложенные универсальные типы, такие как Dictionary<string, List<int>>, являются допустимыми типами, однако их не рекомендуется использовать для подписей членов в правилах проектирования анализа кода. [28]
.NET допускает шесть разновидностей ограничений универсального типа с использованием where
ключевого слова, включая ограничение универсальных типов быть типами значений, классами, иметь конструкторы и реализовывать интерфейсы. [29] Ниже приведен пример с ограничением интерфейса:
используя систему ; образец класса { статическая пустота Main () { int [] массив = { 0 , 1 , 2 , 3 }; MakeAtLeast <int> ( массив , 2 ) ; // Изменяем массив на { 2, 2, 2, 3 } foreach ( int i в массиве ) Консоль . WriteLine ( я ); // Распечатываем результаты. Консоль . ReadKey ( истина ); } static void MakeAtLeast <T> ( список T [ ] , T самый низкий ) , где T : IComparable <T> { for ( int я = 0 ; я < список . Длина ; я ++ ) если ( список [ i ]. CompareTo ( самый низкий ) < 0 ) список [ я ] = самый низкий ; }}
Метод MakeAtLeast()
позволяет работать с массивами с элементами универсального типа T
. Ограничение типа метода указывает, что метод применим к любому типу T
, реализующему универсальный IComparable<T>
интерфейс. Это гарантирует ошибку времени компиляции , если метод вызывается, если тип не поддерживает сравнение. Интерфейс предоставляет общий метод CompareTo(T)
.
Вышеупомянутый метод также можно написать без универсальных типов, просто используя необобщенный Array
тип. Однако, поскольку массивы являются контравариантными , приведение не будет типобезопасным , и компилятор не сможет обнаружить определенные возможные ошибки, которые в противном случае были бы обнаружены при использовании универсальных типов. Кроме того, вместо этого методу потребуется доступ к элементам массива как object
s и потребуется приведение типов для сравнения двух элементов. (Для таких типов значений, как int
этот, требуется преобразование упаковки , хотя это можно обойти с помощью Comparer<T>
класса, как это делается в стандартных классах коллекций.)
Примечательным поведением статических членов в универсальном классе .NET является создание экземпляра статического члена для каждого типа времени выполнения (см. пример ниже).
//Общий класс public class GenTest < T > { //Статическая переменная - будет создана для каждого типа при отражении static CountedInstances OnePerType = new CountedInstances (); //член данных Private T mT ; //простой конструктор public GenTest ( T pT ) { mT = pT ; } } //класс public class CountedInstances { //Статическая переменная — она будет увеличиваться один раз для каждого экземпляра public static int Counter ; //простой конструктор public CountedInstances () { //увеличиваем счетчик на единицу во время создания экземпляра объекта CountedInstances . Счетчик ++ ; } } // точка входа в основной код // в конце выполнения CountedInstances.Counter = 2 GenTest < int > g1 = new GenTest < int > ( 1 ); GenTest <int> g11 = новый GenTest <int> ( 11 ) ; GenTest <int> g111 = новый GenTest <int> ( 111 ) ; GenTest <double> g2 = новый GenTest <double> ( 1.0 ) ;
Диалект Delphi Object Pascal приобрел дженерики в выпуске Delphi 2007, первоначально только с компилятором .NET (сейчас прекращено), а затем был добавлен в собственный код в выпуске Delphi 2009. Семантика и возможности дженериков Delphi во многом смоделированы на основе дженериков в .NET 2.0, хотя реализация по необходимости совершенно другая. Вот более или менее прямой перевод первого примера C#, показанного выше:
Образец программы ; {$APPTYPE КОНСОЛЬ}использует дженерики . По умолчанию ; //для IComparer<> тип TUtils = класс класс процедура MakeAtLeast <T> ( Arr : TArray <T> ; const Lowest : T ; Comparer : IComparer <T> ) ; перегрузка ; процедура класса MakeAtLeast <T> ( Arr : TArray <T> ; const Lowest : T ) ; перегрузка ; конец ; процедура класса TUtils . MakeAtLeast <T> ( Arr : TArray <T> ; const Lowest : T ; Comparer : IComparer <T> ) ; вар I : Целое число ; начать , если Comparer = nil, тогда Comparer := TComparer < T >. По умолчанию ; for I := Low ( Arr ) to High ( Arr ) делайте if Comparer . Сравните ( Arr [ I ] , Самый низкий ) < 0 , тогда Arr [ I ] := Самый низкий ; конец ; процедура класса TUtils . MakeAtLeast <T> ( Arr : TArray <T> ; const Lowest : T ) ; начать MakeAtLeast <T> ( Arr , Самый низкий , ноль ) ; конец ; var Ints : TArray < Целое число >; Значение : Целое число ; начало Ints := TArray < Целое число >. Создать ( 0 , 1 , 2 , 3 ) ; TUtils . MakeAtLeast <Integer> ( Ints , 2 ) ; для значения в Ints do WriteLn ( Value ) ; ЧитатьЛн ; конец .
Как и в C#, методы и целые типы могут иметь один или несколько параметров типа. В этом примере TArray — это универсальный тип (определяемый языком), а MakeAtLeast — универсальный метод. Доступные ограничения очень похожи на доступные ограничения в C#: любой тип значения, любой класс, конкретный класс или интерфейс и класс с конструктором без параметров. Множественные ограничения действуют как аддитивный союз.
В Free Pascal дженерики были реализованы до Delphi, с другим синтаксисом и семантикой. Однако, начиная с версии FPC 2.6.0, синтаксис в стиле Delphi доступен при использовании языкового режима {$mode Delphi}. Таким образом, код Free Pascal поддерживает дженерики в любом стиле.
Пример Delphi и Free Pascal:
// модуль стиля Delphi A ; {$ifdef fpc} {$mode delphi} {$endif} интерфейстип TGenericClass <T> = функция класса Foo ( const AValue : T ) : T ; конец ; выполнениефункция TGenericClass <T> . Foo ( const AValue : T ) : T ; начало результата := AValue + AValue ; конец ; конец .// Стиль ObjFPC Free Pascal unit B ; {$ifdef fpc} {$mode objfpc} {$endif} интерфейстип generic TGenericClass <T> = функция класса Foo ( const AValue : T ) : T ; конец ; выполнениефункция TGenericClass . Foo ( const AValue : T ) : T ; начало результата := AValue + AValue ; конец ; конец .// пример использования, программа в стиле Delphi TestGenDelphi ; {$ifdef fpc} {$mode delphi} {$endif} использует A , B ; вар GC1 : A. TGenericClass < Целое число >; ГК2 : Б. TGenericClass < строка >; начать GC1 := A . TGenericClass < Целое число >. Создавать ; GC2 := B . TGenericClass < строка >. Создавать ; WriteLn ( GC1.Foo ( 100 ) ) ; // 200 WriteLn ( GC2.Foo ( ' привет' ) ) ; // привет, привет GC1 . Бесплатно ; ГК2 . Бесплатно ; конец . // пример использования, программа в стиле ObjFPC TestGenDelphi ; {$ifdef fpc} {$mode objfpc} {$endif} использует A , B ; // требуется в типе ObjFPC TAGenericClassInt = specialize A. TGenericClass < Целое число >; TBGenericClassString = специализировать B . TGenericClass < Строка >; вар GC1 : TAGenericClassInt ; GC2 : TBGenericClassString ; начать GC1 := TAGenericClassInt . Создавать ; GC2 := TBGenericClassString . Создавать ; WriteLn ( GC1.Foo ( 100 ) ) ; // 200 WriteLn ( GC2.Foo ( ' привет' ) ) ; // привет, привет GC1 . Бесплатно ; ГК2 . Бесплатно ; конец .
Механизм классов типов Haskell поддерживает обобщенное программирование. Шесть предопределенных классов типов в Haskell (включая Eq
типы, которые можно сравнивать на равенство, и Show
типы, значения которых могут отображаться как строки) обладают специальным свойством поддержки производных экземпляров. Это означает, что программист, определяющий новый тип, может заявить, что этот тип должен быть экземпляром одного из этих специальных классов типов, не предоставляя реализации методов класса, как это обычно необходимо при объявлении экземпляров класса. Все необходимые методы будут «производными», то есть построенными автоматически, на основе структуры типа. Например, следующее объявление типа двоичных деревьев утверждает, что он должен быть экземпляром классов Eq
и Show
:
данные BinTree a = Лист a | Узел ( BinTree a ) a ( BinTree a ) вывод ( Eq , Show )
В результате функция равенства ( ==
) и функция представления строк ( show
) автоматически определяются для любого типа формы, BinTree T
при условии, что T
она сама поддерживает эти операции.
Поддержка производных экземпляров Eq
и Show
делает их методы ==
и show
универсальные качественно отличными от параметрически полиморфных функций: эти «функции» (точнее, семейства функций с индексированным типом) могут применяться к значениям различных типов, и хотя они ведут себя по-разному для каждого типа аргумента, требуется небольшая работа, чтобы добавить поддержку нового типа. Ральф Хинце (2004) показал, что аналогичный эффект может быть достигнут для классов типов, определяемых пользователем, с помощью определенных методов программирования. Другие исследователи предложили подходы к этому и другим видам универсальности в контексте Haskell и расширений Haskell (обсуждаемых ниже).
PolyP был первым универсальным расширением языка программирования для Haskell . В PolyP общие функции называются политипическими . В языке представлена специальная конструкция, в которой такие политипические функции могут быть определены посредством структурной индукции по структуре функтора шаблона регулярного типа данных. Обычные типы данных в PolyP являются подмножеством типов данных Haskell. Обычный тип данных t должен иметь вид * → * , и если a является аргументом формального типа в определении, то все рекурсивные вызовы t должны иметь форму ta . Эти ограничения исключают типы данных более высокого порядка и вложенные типы данных, где рекурсивные вызовы имеют другую форму. Функция Flatten в PolyP представлена в качестве примера:
Flatten :: Regular d => d a -> [ a ] Flatten = cata fl политипический fl :: f a [ a ] -> [ a ] случай f of g + h -> либо fl fl g * h -> \ ( x , y ) -> fl x ++ fl y () -> \ x -> [] Par -> \ x -> [ x ] Rec -> \ x -> x d @ g -> concat . сгладить . pmap fl Con t -> \ x -> [] cata :: Regular d => ( FunctorOf d a b -> b ) -> d a -> b
Generic Haskell — еще одно расширение Haskell , разработанное в Утрехтском университете в Нидерландах . Расширения, которые он предоставляет:
Результирующее значение с индексом типа может быть специализировано для любого типа.
В качестве примера функция равенства в Generic Haskell: [30]
тип Eq {[ * ]} t1 t2 = t1 -> t2 -> Bool тип Eq {[ k -> l ]} t1 t2 = forall u1 u2 . Eq {[ k ]} u1 u2 -> Eq {[ l ]} ( t1 u1 ) ( t2 u2 ) экв { | т :: к | } :: Eq {[ k ]} t t eq { | Единица | } _ _ = Истинное уравнение { | :+: | } eqA eqB ( Inl a1 ) ( Inl a2 ) знак равно eqA a1 a2 eq { | :+: | } eqA eqB ( Inr b1 ) ( Inr b2 ) знак равно eqB b1 b2 eq { | :+: | } eqA eqB _ _ = Ложное eq { | :*: | } eqA eqB ( a1 :*: b1 ) ( a2 :*: b2 ) = eqA a1 a2 && eqB b1 b2 eq { | Интер | } = ( == ) экв { | Чар | } = ( == ) экв { | Бул | } = ( == )
Clean предлагает универсальное программирование на основе PolyP и Generic Haskell, поддерживаемое GHC ≥ 6.0. Он параметризуется по типу, но предлагает перегрузку.
Языки семейства ML поддерживают универсальное программирование посредством параметрического полиморфизма и универсальных модулей, называемых функторами. И Standard ML, и OCaml предоставляют функторы, похожие на шаблоны классов и универсальные пакеты Ada. Синтаксические абстракции схем также связаны с универсальностью — на самом деле они являются расширенным набором шаблонов C++.
Модуль Verilog может принимать один или несколько параметров, которым при создании экземпляра модуля присваиваются их фактические значения. Одним из примеров является универсальный массив регистров , где ширина массива задается через параметр. Такой массив в сочетании с общим проводным вектором может создать универсальный буфер или модуль памяти с произвольной разрядностью из реализации одного модуля. [31]
VHDL , являющийся производным от Ada, также имеет общие возможности. [32]
C поддерживает «обобщенные выражения типов» с использованием _Generic
ключевого слова: [33]
#define cbrt(x) _Generic((x), long double: cbrtl, \ default: cbrt, \ float: cbrtf)(x)