Обобщенное программирование в c

Универсальное программирование-это стиль компьютерного программирования, в котором алгоритмы записываются в терминах типов , которые будут определены позже, а затем создаются при необходимости для конкретных типов. Предоставленных в качестве параметров. Этот подход. Впервые предложенный языком программирования ML в 1973 году,[1][2] позволяет писать общие функции или типы, которые отличаются только набором типов. На которых они работают при использовании. Тем самым уменьшая дублирование. Такие программные сущности известны как дженерики в Ada, C#, Delphi, Eiffel, F#, Java, Nim, Python, Rust, Swift, TypeScript и Visual Basic .НЕТТО. Они известны как параметрический полиморфизм в ML, Scala, Juliaи Haskell (сообщество Haskell также использует термин «generic» для родственной . Но несколько иной концепции); шаблоны в C++ и D; и параметризованные типы в влиятельных шаблонах дизайна книг 1994года.]

Термин Дэвид Массер и Александр Степанов в более узком смысле, чем выше. Для описания парадигмы программирования. Согласно основополагающим требованиям о видах абстрагированы от конкретных примерах алгоритмов и структур данных и формализованных нами в качестве

понятийс родовыми функций , реализованных в рамках этих концепций. Как правило. С использованием языковой общности положения механизмов. Как описано выше.

Степанов–Мюссер и другие общие парадигмы программирования

Общее программирование определяется в Musser & Stepanov (1989) следующим образом,

Универсальное программирование сосредоточено вокруг идеи абстрагирования от конкретных. Эффективных алгоритмов для получения универсальных алгоритмов. Которые могут быть объединены с различными представлениями данных для создания широкого спектра полезного программного обеспечения.

Musser, David R.; Stepanov, Alexander A.. Generic Programming

[5]

В понятия, по аналогии с абстракцией алгебраических теорий в абстрактной алгебры.[6] ранние примеры такого программирования подход был реализован в схеме. И Ада,[7] хотя самым известным примером является стандартной библиотеки шаблонов (STL файл),[8][9] , который разработал теорию итераторы , который используется. Чтобы отделить последовательность структур данных и алгоритмов. Работающих на них.

Например, учитывая N последовательных структур данных, например. Односвязный список. Вектор и т. Д., И M алгоритмов для работы с ними. Например find, sortи т. Д., Прямой подход будет реализовывать каждый алгоритм специально для каждой структуры данных. Давая N × M комбинации для реализации. Однако, в типовом программном подходе. Каждая структура данных возвращается модели понятие итератора (простой тип значения. Который может быть разыменован для получения текущего значения. Или изменяется на следующее значение в последовательности) и каждый алгоритм. А не записаны в общем с доводами такие итераторы, например. Парой итераторов. Указывающих на начало и конец подпоследовательности, или

диапазон для процесса. Таким образом. Только N + M необходимо реализовать комбинации структура-алгоритм данных.

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

вычислительной сложности требования являются явной частью определения понятия. Это ограничивает количество структур данных. К которым может быть применен данный алгоритм. И такие требования к сложности являются основным фактором. Определяющим выбор структуры данных. Универсальное программирование аналогичным образом было применено и в других областях. Например в графовых алгоритмах[10].]

Обратите внимание. Что хотя этот подход часто использует языковые особенности обобщенности/шаблонов времени компиляции. Он фактически не зависит от конкретных языковых технических деталей.

Пионер универсального программирования Александр Степанов писал,

Универсальное программирование-это абстрагирование и классификация алгоритмов и структур данных. Она черпает свое вдохновение из Кнута. А не из теории типов. Его цель-постепенное построение систематических каталогов полезных. Эффективных и абстрактных алгоритмов и структур данных. Такое предприятие-все еще мечта.

Александр Степанов. Краткая история СТЛ [11][12]

Я считаю, что теории итераторов так же важны для информатики. Как теории колец или банаховых пространств-для математики.

Александр Степанов. Интервью с А. Степановым

[13]

Бьярне Страуструп отметил,

Вслед за Степановым мы можем определить общее программирование без упоминания особенностей языка: поднять алгоритмы и структуры данных из конкретных примеров в их наиболее общую и абстрактную форму.

Бьярне Страуструп. Эволюция языка в реальном мире и для него: C++ 1991-2006[12]

Другие парадигмы программирования. Которые были описаны как универсальное программирование. Включают универсальное программирование типа данных. Описанное в разделе [14] Шаблонный подход Scrap your boilerplate — это легкий универсальный подход программирования для Haskell.

]

В этой статье мы отличаем парадигмы программирования высокого уровня общего программирования, описанные выше, от механизмов универсальности языка программирования более низкого уровня, используемых для их реализации (см. Для дальнейшего обсуждения и сравнения общих парадигм программирования см.[16]

Поддержка языка программирования для универсальности

Генерики объекты существовали в языках высокого уровня. По крайней мере с 1970-х годов в таких языках. Как мл, Клу и Ада, и впоследствии были приняты многими объектно-ориентированные и объектно-ориентированные языки. В том числе бета, C++, С, Д, Эйфелева, Ява, и декабряс ныне несуществующей решетки-Сова языка.

Универсальность реализуется и поддерживается по-разному в различных языках программирования; термин Например, в Forth компилятор может выполнять код во время компиляции. И можно создавать новые ключевые слова компилятора и новые реализации для этих слов на лету. В нем мало слов, раскрывающих поведение компилятора. И поэтому он. Естественно, предлагает возможности обобщения. Которые, однако. Не упоминаются как таковые в большинстве текстов Forth. Точно так же динамически типизированные языки. Особенно интерпретируемые. Обычно предлагают универсальность по умолчанию. Поскольку и передача значений функциям. И присвоение значений индифферентны к типу. И такое поведение часто используется для абстракции или краткости кода. Однако обычно это не называется обобщенностью, поскольку это прямое следствие системы динамической типизации. Используемой языком.[необходимая цитата] Этот термин использовался в функциональном программировании, в частности в хаскеллоподобных языках. Которые используют систему структурных типов где типы всегда параметрические и фактический код на этих типах является общим. Эти обычаи по-прежнему служат аналогичной цели сохранения кода и визуализации абстракции.

Массивы и структуры можно рассматривать как предопределенные универсальные типы. Каждое использование типа массива или структуры создает экземпляр нового конкретного типа или повторно использует предыдущий экземпляр типа. Типы элементов массива и типы элементов структуры являются параметризованными типами. Которые используются для создания экземпляра соответствующего универсального типа. Все это обычно встроено в компилятор, и синтаксис отличается от других универсальных конструкций. Некоторые расширяемые языки программирования пытаются унифицировать встроенные и определяемые пользователем универсальные типы.

Далее следует широкий обзор механизмов обобщенности в языках программирования. Конкретный обзор. Сравнивающий пригодность механизмов для общего программирования, см.[17]

В объектно-ориентированных языках

При создании контейнерных классов в статически типизированных языках неудобно писать конкретные реализации для каждого содержащегося типа данных. Особенно если код для каждого типа данных практически идентичен. Например, в C++ это дублирование кода можно обойти. Определив шаблон класса:

шаблон typename T>>  Список классов { // Содержимое класса. }; ListAnimal> list_of_animals; ListCar> list_of_cars; 

Выше-Tэто заполнитель для любого типа. Указанного при создании списка. Эти шаблонами, позволяют повторно использовать класс с различными типами данных до тех пор. Пока сохраняются определенные контракты. Такие как подтипы и подпись. Этот механизм обобщенности не следует путать с полиморфизмом включения, который представляет собой алгоритмическое использование взаимозаменяемых подклассов: например. Список объектов типаMoving_Object, содержащий объекты типа Animalи.Car Шаблоны также можно использовать для независимых от типа функций. Как в Swapприведенном ниже примере:

//  шаблон typename и Т> недействительными подкачки(Т& А, Т& Б) { Т темп = б; б = а; а = темп; } станд::строка  = ; СТД::строка мире = ; своп(мир, привет); станд::соиь    мир  станд::епси; // выведет  

templateИспользуемая выше конструкция C++ широкоцитируется как конструкция универсальности. Которая популяризировала это понятие среди программистов и разработчиков языков и поддерживает множество универсальных идиом программирования. Язык программирования D также предлагает полностью универсальные шаблоны. Основанные на прецеденте C++. Но с упрощенным синтаксисом. Язык программирования Java предоставляет средства обобщения. Синтаксически основанные на C++. Начиная с появления J2SE 5.0.

C# 2.0, Oxygene 1.5 (также известный как Chrome) и Visual Basic .NET 2005 имеют конструкции. Которые используют преимущества поддержки универсальных приложений. Присутствующих в Microsoft .NET Framework с версии 2.0.

Дженерики в Ada

У Ada были дженерики с тех пор. Как она была впервые разработана в 1977-1980 годах. Стандартная библиотека использует дженерики для предоставления многих услуг. Ada 2005 добавляет полную универсальную библиотеку контейнеров к стандартной библиотеке. Которая была вдохновлена стандартной библиотекой шаблонов C++.

Универсальная единица-это пакет или подпрограмма. Которая принимает один или несколько универсальных формальных параметров.

Универсальный формальный параметр-это значение, переменная. Константа, тип. Подпрограмма или даже экземпляр другой. Обозначенной универсальной единицы. Для общих формальных типов синтаксис различает дискретные типы. Типы с плавающей точкой. Фиксированной точкой. Типы доступа (указателя) и т. Д. Некоторые формальные параметры могут иметь значения по умолчанию.

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

Пример

Спецификация универсального пакета:

 generic Max_Size : Natural; -- a generic formal value type Element_Type является частным; -- a generic formal type; принимает любой нелимитный тип пакетных стеков является типом Size_Type является диапазон 0 .. Аргумент max_size; тип стек имеет ограниченный частная; порядок создания (С : из стек; Initial_Size : в Size_Type := аргумент max_size); процедура принудительной (В : В из стек; элемент : в Element_Type); порядок поп (С : в из стек; элемент : из Element_Type); перелив : исключение; переполнение : исключение; отдельный подтип Index_Type является Size_Type ряд 1 .. Max_Size; type Vector - массив (Index_Type range   Element_Type; type Stack (Allocated_Size : Size_Type := 0) -  вершина записи : Index_Type; Storage : Vector (1 .. Allocated_Size); end record; end Stacks; 

Создание экземпляра универсального пакета:

 тип Bookmark_Type is new Natural; -- записывает местоположение в текстовом документе , который мы редактируем пакет Bookmark_Stacks is new Stacks (Max_Size =>> 20, Element_Type =>> Bookmark_Type); -- Позволяет пользователю переходить между записанными местоположениями в документе 

Использование экземпляра универсального пакета:

 тип Document_Type является рекордное содержание : Ада.Строк.Неограниченная.Unbounded_String; Закладки : Bookmark_Stacks.Стека; конец записи; процедура редактирования (Имя_документа : в строке) - это документ : Document_Type; начать -- инициализация стека закладок: Bookmark_Stacks.Создание (С  Документ.Закладки, Initial_Size  10); -- Теперь откройте файл Имя_документа и... конец редактирования; 
Преимущества и ограничения

Синтаксис языка позволяет точно определять ограничения на общие формальные параметры. Например, можно указать. Что общий формальный тип будет принимать только модульный тип в качестве фактического. Кроме того, можно выразить ограничения между общими формальными параметрами; например:

 generic type Index_Type is  -- must be a discrete type type Element_Type is private; -- can be any nonlimited type type Array_Type is array (Index_Type range  of Element_Type; 

В этом примере Array_Type ограничен как Index_Type. Так и Element_Type. При создании экземпляра модуля программист должен передать фактический тип массива. Удовлетворяющий этим ограничениям.

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

В отличие от C++. Ada не допускает специализированных универсальных экземпляров и требует. Чтобы все универсальные экземпляры создавались явно. Эти правила имеют несколько последствий:

  • компилятор может реализовать общие универсалии: объектный код для универсального блока может быть общим для всех экземпляров (если, конечно. Программист не запрашивает инлайнинг подпрограмм). Как дальнейшие последствия:
    • нет возможности раздувания кода (раздувание кода распространено в C++ и требует особого ухода. Как описано ниже).
    • можно создавать экземпляры генераторов во время выполнения. А также во время компиляции. Так как для нового экземпляра не требуется никакого нового объектного кода.
    • фактические объекты. Соответствующие общему формальному объекту. Всегда считаются нестатичными внутри общего; подробности и последствия см. в разделе Общие формальные объекты в Викибук.
  • все экземпляры универсума абсолютно одинаковы. Проще просматривать и понимать программы. Написанные другими; нет
  • все экземпляры являются явными. Нет никаких скрытых экземпляров. Которые могли бы затруднить понимание программы.
  • Ada не допускает

Шаблоны в C++

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

Технический обзор

Существует два вида шаблонов: шаблоны функций и шаблоны классов. Шаблон функции-это шаблон для создания обычных функций на основе типов параметризации. Предоставляемых при создании экземпляра. Например, стандартная библиотека шаблонов C++ содержит шаблон функцииmax(x, y), который создает функции. Возвращающие либо x, либо y, в зависимости от того. Что больше. max() можно было бы определить так:

template typename T> T max(T x, T y) { return x  y ? y : x; } 

Специализации этого шаблона функций. Экземпляры с определенными типами. Могут быть вызваны так же. Как и обычная функция:

std::cout  max(3, 7); // Выходы 7. 

Компилятор проверяет аргументы. Используемые для вызоваmax, и определяет. Что это вызов max(int, int). Затем он создает экземпляр версии функции . В которой находится параметризующий типTint, делая эквивалент следующей функции:

int max(int x, int y) { return x  y ? y : x; } 

Это работает независимо от того. Являются ли аргументы xи yцелыми числами. Строками или любым другим типом. Для которого выражение x является разумным, или. Более конкретно. Для любого типа. Для которого operatorоно определено. Общее наследование не требуется для набора типов. Которые могут быть использованы. И поэтому оно очень похоже на утиный тип. Программа, определяющая пользовательский тип данных. Может использовать перегрузку оператора для определения значения для этого типа. Что позволяет использовать его с max() шаблон функции. Хотя это может показаться незначительным преимуществом в данном изолированном примере. В контексте такой обширной библиотеки, как STL. Она позволяет программисту получить обширную функциональность для нового типа данных. Просто определив для него несколько операторов. Простое определение позволяет использовать тип со стандартными sort()алгоритмами , stable_sort(), и binary_search()или помещать его в структуры данных. Такие как sets , кучии ассоциативные массивы.

Шаблоны C++ полностью типобезопасны во время компиляции. В качестве демонстрации стандартный тип complexне определяет оператора. Потому что нет строгого порядка на комплексных числах. Поэтому max(x, y)произойдет сбой с ошибкой компиляции. Если x и y являются complexзначениями. Кроме того, другие шаблоны. На которые полагаются, не могут быть применены к complexданным. Если не предусмотрено сравнение (в виде функтора или функции). Например: A complexне может быть использован в качестве ключа для map если сравнение не предусмотрено. К сожалению. Компиляторы исторически генерируют несколько эзотерические. Длинные и бесполезные сообщения об ошибках такого рода. Обеспечение того. Чтобы определенный объект придерживался протокола метода, может облегчить эту проблему. Языки, которые используют compareвместо могут также использовать complexзначения в качестве ключей.

Второй тип шаблона. Шаблон класса, расширяет ту же концепцию на классы. Специализация шаблона класса-это класс. Шаблоны классов часто используются для создания универсальных контейнеров. Например, STL имеет контейнер связанного списка. Чтобы составить связанный список целых чисел. Нужно написать list. Список строк обозначается list. A listимеет набор стандартных функций. Связанных с ним. Которые работают для любых совместимых типов параметризации.

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

Мощной особенностью шаблонов C++является специализация шаблонов. Это позволяет обеспечить альтернативные реализации. Основанные на определенных характеристиках создаваемого экземпляра параметризованного типа. Специализация шаблонов преследует две цели: разрешить определенные формы оптимизации и уменьшить объем кода.

Например, рассмотрим sort()функцию шаблона. Одним из основных действий. Выполняемых такой функцией. Является замена или обмен значениями в двух позициях контейнера. Если значения большие (с точки зрения количества байтов. Необходимых для хранения каждого из них). То часто быстрее сначала построить отдельный список указателей на объекты. Отсортировать эти указатели. А затем построить окончательную отсортированную последовательность. Однако если значения довольно малы. То обычно быстрее всего просто поменять их местами по мере необходимости. Кроме того, если параметризованный тип уже имеет некоторый тип указателя. То нет необходимости создавать отдельный массив указателей. Специализация шаблонов позволяет создателю шаблонов писать различные реализации и указывать характеристики. Которые должны иметь параметризованные типы для каждой используемой реализации.

В отличие от шаблонов функций. Шаблоны классов могут быть частично специализированными. Это означает. Что альтернативная версия кода шаблона класса может быть предоставлена. Когда некоторые параметры шаблона известны. Оставляя другие параметры шаблона универсальными. Это может быть использовано, например. Для создания реализации по умолчанию (основная специализация) это предполагает. Что копирование типа параметризации является дорогостоящим. А затем создает частичные специализации для типов. Которые являются дешевыми для копирования. Что повышает общую эффективность. Клиенты такого шаблона класса просто используют его специализации без необходимости знать. Использовал ли компилятор первичную специализацию или некоторую частичную специализацию в каждом случае. Шаблоны классов также могут быть полностью специализированными, что означает. Что альтернативная реализация может быть предоставлена. Когда известны все типы параметризации.

Преимущества и недостатки

Некоторые виды использования шаблонов. Такие как max()функция. Ранее были заполнены функциональными макросами препроцессора (наследие языка программирования Си). Например, вот возможный max()макрос:

#define max(a,b) ((a) )) 

Макросы расширяются препроцессоромперед собственно компиляцией; шаблоны расширяются во время компиляции. Макросы всегда расширяются встроенно; шаблоны также могут быть расширены как встроенные функции, когда компилятор сочтет это целесообразным. Таким образом. Как функциональные макросы. Так и шаблоны функций не имеют накладных расходов во время выполнения.

Однако шаблоны обычно считаются улучшением по сравнению с макросами для этих целей. Шаблоны типобезопасны. Шаблоны позволяют избежать некоторых распространенных ошибок. Обнаруживаемых в коде. Который часто использует функциональные макросы. Такие как оценка параметров с побочными эффектами дважды. Возможно, самое главное. Что шаблоны были разработаны. Чтобы быть применимыми к гораздо большим проблемам. Чем макросы.

Есть четыре основных недостатка в использовании шаблонов: поддерживаемые функции. Поддержка компилятора. Плохие сообщения об ошибках и раздувание кода:

  1. Шаблоны в C++ лишены многих функций. Что делает их реализацию и использование простым способом часто невозможным. Вместо этого программистам приходится полагаться на сложные трюки. Которые приводят к раздутому. Трудному для понимания и трудно поддерживаемому коду. Современные разработки в стандартах C++ усугубляют эту проблему. Интенсивно используя эти приемы и создавая множество новых функций для шаблонов на их основе или с их учетом.
  2. Многие компиляторы исторически плохо поддерживают шаблоны. Поэтому использование шаблонов может сделать код несколько менее переносимым. Поддержка также может быть плохой. Когда компилятор C++ используется с компоновщиком, который не поддерживает C++. Или при попытке использовать шаблоны через границы общей библиотеки. Однако большинство современных компиляторов теперь имеют довольно надежную и стандартную поддержку шаблонов, и новый стандарт C++, C++11, дополнительно решает эти проблемы.
  3. Почти все компиляторы выдают запутанные. Длинные или иногда бесполезные сообщения об ошибках при обнаружении ошибок в коде. Использующем шаблоны.[18] Это может затруднить разработку шаблонов.
  4. Наконец, использование шаблонов требует. Чтобы компилятор генерировал отдельный экземпляр шаблонного класса или функции для каждой перестановки параметров типа. Используемых с ним. (Это необходимо. Потому что типы в C++ не все одинакового размера . И размеры полей данных важны для того. Как классы работают.) Поэтому беспорядочное использование шаблонов может привести к раздуванию кода, в результате чего чрезмерно большие исполняемые файлы. Однако разумное использование специализации и деривации шаблонов в некоторых случаях может значительно уменьшить такое раздувание кода:

Итак, можно ли использовать деривацию для уменьшения проблемы репликации кода. Поскольку используются шаблоны? Это будет включать в себя вывод шаблона из обычного класса. Этот метод оказался успешным в сдерживании вздутия кода в реальном использовании. Люди, которые не используют подобную технику, обнаружили. Что реплицированный код может стоить мегабайт кодового пространства даже в программах среднего размера.

Дополнительные экземпляры. Генерируемые шаблонами. Также могут привести к тому. Что отладчикам будет трудно корректно работать с шаблонами. Например, установка точки останова отладки в шаблоне из исходного файла может либо пропустить установку точки останова в желаемом фактическом экземпляре. Либо может установить точку останова в каждом месте создания экземпляра шаблона.

Кроме того, поскольку компилятор должен выполнять макроподобные расширения шаблонов и генерировать различные их экземпляры во время компиляции. Исходный код реализации для шаблонного класса или функции должен быть доступен (например. Включен в заголовок) для кода. Использующего его. Шаблонные классы или функции. Включая большую часть Стандартной библиотеки шаблонов (STL). Если они не включены в заголовочные файлы. Не могут быть скомпилированы. (Это в отличие от не шаблонного кода. Который может быть скомпилирован в двоичный код. Предоставляя только файл заголовка объявления для кода. Использующего его.) Это может быть недостатком. Предоставляя код реализации. Который удаляет некоторые абстракции и может ограничить его использование в проектах с закрытым исходным кодом.[требуется цитирование]

Шаблоны в D

Язык программирования D поддерживает шаблоны. Основанные в дизайне на C++. Большинство идиом шаблонов C++ переносятся на D без изменений. Но D добавляет некоторые дополнительные функции:

  • Параметры шаблона в D не ограничиваются только типами и примитивными значениями. Но также допускают произвольные значения времени компиляции (такие как строки и литералы структуры) и псевдонимы произвольных идентификаторов. Включая другие шаблоны или экземпляры шаблонов.
  • Ограничения шаблона и static ifоператор предоставляют альтернативу C++’s substitution failure is not an error (SFINAE) mechanism. Аналогичную концепциям C++.
  • is(...)Выражение позволяет спекулятивной инстанциации проверять признаки объекта во время компиляции.
  • autoКлючевое слово и typeofвыражение позволяют вывод типа для объявлений переменных и возвращаемых значений функций, что. В свою очередь. Позволяет [20]

Шаблоны в D используют другой синтаксис. Чем в C++: в то время как в C++ параметры шаблона заключены в угловые скобки (Template), D использует восклицательный знак и скобки: Template!(param1, param2). Это позволяет избежать трудностей синтаксического анализа C++ из-за неоднозначности операторов сравнения. Если есть только один параметр. Скобки могут быть опущены.

Обычно D объединяет вышеперечисленные функции для обеспечения полиморфизма во время компиляции с использованием универсального программирования на основе признаков. Например, входной диапазон определяется как любой тип . Удовлетворяющий выполняемым проверкамisInputRange, который определяется следующим образом:

шаблон isInputRange(Р) { перечислимого типа bool isInputRange = это(для вызова typeof( (inout в инт = 0) { р р = р.метод init; // определить объект Range ли (Р.пустой)  // проверка на пустое Р.popFront(); // может вызвать popFront() автоматического ч = р.стойка; // может получить переднюю часть ассортимента })); } 

Функция. Которая принимает только входные диапазоны. Может затем использовать указанный выше шаблон в ограничении шаблона:

auto fun(Range)(Диапазон диапазона) if (isInputRange!Диапазон) { // ... } 
Генерация кода

В дополнение к шаблонному метапрограммированию D также предоставляет несколько функций для генерации кода во время компиляции:

  • Это importвыражение позволяет считывать файл с диска и использовать его содержимое в качестве строкового выражения.
  • Отражение во время компиляции позволяет перечислять и проверять объявления и их члены во время компиляции.
  • Определяемые пользователем атрибуты позволяют пользователям присоединять произвольные идентификаторы к объявлениям. Которые затем могут быть перечислены с помощью отражения во время компиляции.
  • Выполнение функции времени компиляции (CTFE) позволяет интерпретировать подмножество D (ограниченное безопасными операциями) во время компиляции.
  • Строковые миксины позволяют оценивать и компилировать содержимое строкового выражения в виде кода D. Который становится частью программы.

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

importВыражение и выполнение функций во время компиляции также позволяют эффективно реализовывать доменные языки. Например, учитывая функцию. Которая принимает строку. Содержащую HTML-шаблон. И возвращает эквивалентный исходный код D. Ее можно использовать следующим образом:

// Импортируйте содержимое example.htt в виде строковой манифестной константы. enum htmlTemplate = import(); // Транспилируйте HTML-шаблон в D-код. enum htmlDCode = htmlTemplateToD(htmlTemplate); // Вставить содержимое htmlDCode в виде D-кода. mixin(htmlDCode); 

Универсальность в Эйфеле

Универсальные классы были частью Eiffel со времен оригинального метода и языкового дизайна. Фундаментальные публикации Эйфеля[21][22] используют термин

Основная/безусловной общности положения

Универсальные классы объявляются с их именем класса и списком одного или нескольких формальных универсальных параметров. В следующем коде класс LISTимеет один формальный универсальный параметр G

class LIST [G] ... feature -- Access item: G -- Элемент. На который в данный момент указывает курсор ... feature -- Element change put (new_item: G) -- Add `new_item' в конце списка ... 

Формальные универсальные параметры являются заполнителями для произвольных имен классов. Которые будут предоставлены при объявлении универсального класса. Как показано в двух общих производных ниже. Где ACCOUNTи DEPOSITявляются другими именами классов. ACCOUNT и DEPOSITсчитаются фактическими универсальными параметрами, поскольку они предоставляют реальные имена классов для замены Gв фактическом использовании.

 list_of_accounts: LIST [ACCOUNT] -- Account list list_of_deposits: LIST [DEPOSIT] -- Deposit list 

В системе типов Eiffel. Хотя класс LIST [G]считается классом. Он не считается типом. Тем не менее. Родовое происхождение LIST [G]таких. Как LIST [ACCOUNT]считается типом.

Ограниченная

Для класса списка. Показанного выше. Фактическим универсальным параметром. Заменяющим Gего, может быть любой другой доступный класс. Чтобы ограничить набор классов. Из которых могут быть выбраны действительные фактические универсальные параметры, может быть задано универсальное ограничение. В приведенном ниже объявлении класса SORTED_LISTуниверсальное ограничение диктует. Что любой допустимый фактический универсальный параметр будет классом. Который наследуется от класса COMPARABLE. Универсальное ограничение гарантирует. Что элементы a SORTED_LISTдействительно могут быть отсортированы.

класс SORTED_LIST [G  СОПОСТАВИМЫЙ] 

Дженерики в Java

Поддержка дженериков, или язык программирования Java в 2004 году в составе J2SE 5.0. В Java дженерики проверяются только во время компиляции на правильность типа. Затем сведения об универсальных типах удаляются с помощью процесса . Называемого стиранием типов, для поддержания совместимости со старыми реализациями JVM. Делая их недоступными во время выполнения. Например, a Listпреобразуется в тип raw List. Компилятор вставляет приведения типа для преобразования элементов в StringМетод позволяет работать с массивами. С элементами универсального типа T. Ограничение типа метода указывает. Что метод применим к любому типуT, реализующему универсальный IComparableинтерфейс. Это гарантирует ошибку времени компиляции. Если метод вызывается. Если тип не поддерживает сравнение. Интерфейс предоставляет универсальный метод CompareTo(T).

Описанный выше метод также может быть написан без универсальных типов. Просто используя не-универсальный Arrayтип. Однако, поскольку массивы контравариантны, приведение не будет типобезопасным, и компилятор не сможет найти определенные возможные ошибки. Которые в противном случае были бы обнаружены при использовании универсальных типов. Кроме того, метод должен был бы получить доступ к элементам массива как objects вместо этого и потребовал бы приведения для сравнения двух элементов. (Для типов значений. Подобных intэтим типам. Требуется боксовое преобразование. Хотя это можно обойти с помощью Comparerкласса. Как это делается в стандартных классах коллекций.)

Заметное поведение статических членов в универсуме .NET class-это статический экземпляр элемента для каждого типа времени выполнения (см. Пример ниже).

 //Универсальный класс общественного класса ГентестТ> { //статическая переменная - будет создан для каждого типа на отражение статического CountedInstances OnePerType = новый CountedInstances(); //элемент данных, индивидуальный Т МТ; //простой конструктор публичных Гентест(Т, пт) { т = пт; } } //класс общественного класса CountedInstances { //статическая переменная - это значение будет увеличиваться после каждого экземпляра общественный статический инт счетчик; //простой конструктор публичных CountedInstances() { //увеличить счетчик на единицу при создании экземпляра объекта CountedInstances.Счетчик++; } } //основной код точка входа //в конце выполнения. CountedInstances.Counter = 2 GenTestint> g1 = new GenTestint>(1); GenTestint> g11 = new GenTestint>(11); GenTestint> g111 = new GenTestint>(111); GenTestdouble> g2 = new GenTestdouble>(1.0); 

Универсальность в Delphi

Объектный диалект Delphi Pascal приобрел дженерики в выпуске Delphi 2007, первоначально только с помощью (ныне прекращенного) компилятора .NET, а затем был добавлен в машинный код в выпуске Delphi 2009. Семантика и возможности дженериков Delphi в значительной степени смоделированы по образцу тех. Что были у дженериков в .NET 2.0, хотя реализация по необходимости совершенно иная. Вот более или менее прямой перевод первого примера C#. Показанного выше:

программа образца;  использует дженерики.По умолчанию;  тип TUtils = класс класс процессуального MakeAtLeastТ>(Модуль arr: TArrayТ>; константный низкой: Т; компаратор: метод icomparerТ>); перегрузки; класс процессуального MakeAtLeastТ>(Модуль arr: TArrayТ>; константный низкой: Т); перегрузки; конец; класс процессуального TUtils.MakeAtLeastТ>(Модуль arr: TArrayТ>; константный низкой: Т; компаратор: метод icomparerТ>); ВАР я: целое число; начать если компаратор = нулю, то компаратор := TComparerТ>.По умолчанию; для меня := низкая(округ) до высокого(округ) делать , если компаратор.Сравнить(ОБР[я], низкой)  0 тогда ОБР[я] := низкой; конец; класс процессуального TUtils.MakeAtLeastТ>(Модуль arr: TArrayТ>; константный низкой: Т); начать MakeAtLeastТ>(аранж, низкой, Нил); конец; ВАР ИНЦ: TArrayInteger>; Value: Integer; begin Ints := TArrayInteger>.Create(0, 1, 2, 3); TUtils.MakeAtLeastInteger>(Ints, 2); for Value in Ints do WriteLn(Value); ReadLn; end. 

Как и в случае с C#, методы. А также целые типы могут иметь один или несколько параметров типа. В приведенном примере TArray-это универсальный тип (определяемый языком). А MakeAtLeast-универсальный метод. Доступные ограничения очень похожи на доступные ограничения в C#: любой тип значения. Любой класс. Определенный класс или интерфейс и класс с конструктором без параметров. Множественные ограничения действуют как аддитивное объединение.

Обобщенность в свободном Паскале

Free Pascal реализовал генераторы до Delphi. Причем с разным синтаксисом и семантикой. Таким образом. Свободные программисты Pascal могут использовать универсальные шаблоны в любом стиле. Который они предпочитают.

Пример Delphi и Free Pascal:

// Делфи стиле блок а;    интерфейс тип TGenericClassТ> = класс функции Фу(константные значения: Т): Т; конец; реализация функции TGenericClassТ>.Фу(константные значения: Т): Т; начать результат := значение + значение; конец; конец. // Бесплатная Паскаля ObjFPC стиле блок Б;    интерфейс тип универсальный TGenericClassТ> = класс функции Фу(константные значения: Т): Т; конец; реализация функции TGenericClass.Фу(константные значения: Т): Т; начать результат := значение + значение; конец; конец. // пример использования. Дельфы тип программы TestGenDelphi;    использует А,Б; ВАР GC1: есть.TGenericClassцелое число>; С2: Б.TGenericClassСтрока>; начать GC1 := а.TGenericClassЦелое Число>.Создать; С2 := Б.TGenericClassСтрока>.Создать; WriteLn(GC1.Фу(100)); // 200 WriteLn(С2.Фу('привет')); // сайту hellohello GC1.Бесплатно; С2.Бесплатно; конец. // пример использования. ObjFPC тип программы TestGenDelphi;    использует А,Б; // требуется в ObjFPC тип TAGenericClassInt = специализируется на.TGenericClassцелое число>; TBGenericClassString = специализируется Б.TGenericClassстрока>; ВАР GC1: TAGenericClassInt; С2: TBGenericClassString; начать GC1 := TAGenericClassInt.Создать; С2 := TBGenericClassString.Создать; WriteLn(GC1.Фу(100)); // 200 WriteLn(С2.Фу('привет')); // сайту hellohello 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 являются подмножеством типов данных Haskell. Обычный тип данных t должен иметь вид * → *, и если a является формальным аргументом типа в определении. То все рекурсивные вызовы t должны иметь вид t a. Эти ограничения исключают более высокие типы данных. А также вложенные типы данных. Где рекурсивные вызовы имеют другую форму. Функция сплющивания в PolyP здесь приведена в качестве примера:

 плющить :: регулярный д  д А  [а] сплющить = ц ФЛ разнотипные ФЛ :: Ф А [А]  [а] дело ж в г+н  либо Флорида Флорида г*ч  \(х,г)  ФЛ х ++ ФЛ г ()  \х  [] равенство  \х  [х] отдых  \х  х Д@Г  функция concat . разровнять . pmap ФЛ Кон - т  \х  [] ката :: регулярные д'  (FunctorOf д А Б  б)  д А  Б 
Generic Haskell

Generic Haskell-это еще одно расширение Haskell, разработанное в Утрехтском университете в Нидерландах. Расширения. Которые он предоставляет:

  • Индексируемые по типу значения определяются как значения. Индексируемые по различным конструкторам типов Haskell (unit. Примитивные типы, суммы. Произведения и пользовательские конструкторы типов). Кроме того, мы также можем указать поведение индексированных по типу значений для конкретного конструктора . Используя случаи конструктора, и повторно использовать одно общее определение в другом. Используя случаи по умолчанию.

Результирующее индексированное по типу значение может быть специализировано на любом типе.

  • Индексированные по виду типы-это типы. Индексированные по видам. Определяемые приведением случая как для*, так и для k → k’. Экземпляры получаются путем применения индексированного по виду типа к виду.
  • Общие определения можно использовать. Применяя их к типу или виду. Это называется универсальным приложением. Результатом является тип или значение. В зависимости от того. Какой тип общего определения применяется.
  • Общая абстракция позволяет определять общие определения путем абстрагирования параметра типа (заданного типа).
  • Индексированные типы-это типы. Которые индексируются над конструкторами типов. Они могут быть использованы для придания типов более вовлеченным общим значениям. Полученные индексированные по типу типы могут быть специализированы на любом типе.

В качестве примера можно привести функцию равенства в универсальном языке Haskell:[28]

 тип эквалайзера {[ *  Т1 Т2 = Т1  Т2  bool и тип эквалайзера {[ к  я  Т1 Т2 = форалл У1 У2. Эквалайзер {[ к.  У1 У2  эквалайзер {[ л.  (Т1, У1) (Т2, У2) эквалайзер {| т :: к |} :: - эквалайзер {[ к.  т т экв {| единица |} _ _ = Правда эквалайзер {| :+: |} вок eqB (Мнз А1) (Мнз А2) = вок А1 А2 эквалайзер {| :+: |} вок eqB (индийских рупий В1) (индийских рупий В2) = eqB В1 В2 эквалайзер {| :+: |} вок eqB _ _ = ложь эквалайзер {| :*: |} вок eqB (А1 :*: В1) (А2 :*: В2) = вок А1 А2 && eqB В1 В2 эквалайзер {| Инт |} = (==) эквалайзер {| чар |} = (==) эквалайзер {| Боол |} = (==) 

Чистый

CleanОн параметризует по виду, как те. Но предлагает перегрузку.

Другие языки

Семейство языков программирования ML поддерживает универсальное программирование с помощью параметрического полиморфизма и универсальных модулей. Называемых функторами. Схематические синтаксические абстракции также имеют связь с универсальностью – на самом деле это надмножество шаблонов а-ля С++.

Модуль Verilog может принимать один или несколько параметров. Которым назначаются их фактические значения при создании экземпляра модуля. Одним из примеров является универсальный регистровый массив. Где ширина массива задается с помощью параметра. Такой массив в сочетании с универсальным проводным вектором может создать универсальный буфер или модуль памяти с произвольной битовой шириной из одной реализации модуля.[29]

VHDL, будучи производным от Ada. Также имеет общие возможности.

  1. ^
  2. ^ Milner, R.; Morris, L.; Newey, M. (1975). Материалы конференции по обоснованию и совершенствованию программ.
  3. ^ Gamma, Erich; Helm, Richard; Johnson, Ralph; Vlissides, John (1994). Шаблоны дизайна. Эддисон-Уэсли. ISBN 0-201-63361-2.
  4. ^ Муссер, Дэвид Р.; Степанов, Александр А. Общее программирование (PDF).
  5. ^ Александр Степанов; Пол Макджонес (19 июня 2009). Элементы программирования. Эддисон-Уэсли Профессионал. ISBN 978-0-321-63537-2.
  6. ^ Муссер, Дэвид Р.; Степанов, Александр А. (1987). Материалы ежегодной Международной конференции ACM SIGAda 1987 года по Ada: 216-225. CiteSeerX 10.1.1.588.7431. doi:10.1145/317500.317529. ISBN 0897912438. S2CID 795406.
  7. ^ Александр Степанов и Мэн Ли: Стандартная библиотека шаблонов. Технический отчет HP Laboratories 95-11(R. 1), 14 ноября 1995 г.
  8. Мэтью Х. Остерн: Универсальное программирование и STL: использование и расширение стандартной библиотеки шаблонов C++. Addison-Wesley Longman Publishing Co., Inc. Бостон, Массачусетс, США 1998
  9. ^ Jeremy G. Siek. Lie-Quan Lee. Andrew Lumsdaine: The Boost Graph Library: Руководство пользователя и справочное руководство. Аддисон-Уэсли 2001
  10. ^ Степанов, Александр. Краткая история STL (PDF).
  11. ^ b Страуструп. Бьярне. Разработка языка в реальном мире и для него: C++ 1991-2006 (PDF). doi:10.1145/1238844.1238848. S2CID 7518369.
  12. ^ Lo Russo, Graziano. .
  13. ^ Роланд Бэкхаус; Патрик Янссон; Юхан Йоринг; Ламберт Мертенс (1999). Общее программирование – Введение (PDF).
  14. ^ Lämmel, Ralf; Peyton Jones. Simon. (PDF). Проверено 16 октября 2016года .
  15. ^ Gabriel Dos Reis; Jaakko Ja ̈rvi (2005). (препринт LCSD’05) (PDF). Архивирован из оригинала (PDF) 25 декабря 2005 года.
  16. ^ R. Garcia; J. Ja rvi; A. Lumsdaine; J. Siek; J. Willcock (2005). CiteSeerX 10.1.1.110.122.
  17. ^ Stroustrup. Dos Reis (2003): Concepts — Design choices for template argument checking
  18. ^ Страуструп. Бьярне (1994). Дизайн и эволюция языка С++. Рединг, Массачусетс: Аддисон-Уэсли, стр. Bibcode:1994dec..book…. S. ISBN 978-81-317-1608-3.
  19. ^ Умница, Уолтер. . Доктор Доббс. Извлечено 3 июня 2015года .
  20. ^ Объектно-ориентированное построение программного обеспечения, Prentice Hall, 1988, и Объектно-ориентированное построение программного обеспечения. Второе издание, Prentice Hall, 1997.
  21. Эйфель: Язык, Прентис-Холл, 1991.
  22. ^ История Дженериков .NET/C#: Некоторые Фотографии С Февраля 1999 Года
  23. ^ C#: Вчера, Сегодня и завтра: Интервью с Андерсом Хейльсбергом
  24. ^ Дженерики в C#, Java и C++
  25. ^ Анализ кода CA1006: Не вкладывайте универсальные типы в сигнатуры членов
  26. ^ Ограничения на параметры типа (Руководство по программированию на C# )
  27. ^ Общее руководство пользователя Haskell
  28. ^ Verilog на примере. Раздел Остальное для справки. Блейн К. Ридлер. Full Arc Press, 2011. ISBN 978-0-9834973-0-1

Дальнейшее чтение

Внешние ссылки

C++/D
C#/.NET
Delphi/Object Pascal
Эйфелева башня
Хаскелл
Ява