Общее программирование - Generic programming

Не путать с генетическим программированием .

Парадигмы программирования

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

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

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

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

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

-  Musser, David R .; Степанов Александр Александрович, Generic Programming

Парадигма «общего программирования» - это подход к декомпозиции программного обеспечения, при котором фундаментальные требования к типам абстрагируются от конкретных примеров алгоритмов и структур данных и формализуются как концепции , аналогично абстракции алгебраических теорий в абстрактной алгебре . Ранние примеры этого подхода к программированию были реализованы в Scheme и Ada, хотя наиболее известным примером является Стандартная библиотека шаблонов (STL), которая разработала теорию итераторов, которая используется для разделения структур данных последовательности и алгоритмов, работающих с ними.

Например, учитывая N структур данных последовательностей, например, односвязный список, вектор и т. Д., И M алгоритмов для работы с ними, например find, sortи т. Д., Прямой подход будет реализовывать каждый алгоритм специально для каждой структуры данных, давая N × M комбинаций для осуществлять. Однако в общем подходе к программированию каждая структура данных возвращает модель концепции итератора (простой тип значения, который можно разыменовать для получения текущего значения или изменить, чтобы указать на другое значение в последовательности), и вместо этого записывается каждый алгоритм обычно с аргументами таких итераторов, например парой итераторов, указывающих на начало и конец подпоследовательности или диапазона для обработки. Таким образом, необходимо реализовать только N + M комбинаций структура данных-алгоритм. В STL указано несколько концепций итераторов, каждая из которых представляет собой уточнение более ограничительных концепций, например, прямые итераторы обеспечивают перемещение только к следующему значению в последовательности (например, подходит для односвязного списка или потока входных данных), тогда как случайный доступ iterator также обеспечивает прямой постоянный доступ к любому элементу последовательности (например, подходящему для вектора). Важным моментом является то, что структура данных будет возвращать модель наиболее общей концепции, которая может быть эффективно реализована - требования вычислительной сложности явным образом являются частью определения концепции. Это ограничивает структуры данных, к которым может применяться данный алгоритм, и такие требования к сложности являются основным фактором, определяющим выбор структуры данных. Обобщенное программирование аналогично применялось и в других областях, например, в алгоритмах графов.

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

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

-  Александр Степанов, Краткая история STL

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

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

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

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

-  Бьярн Страуструп, Развитие языка в реальном мире и для него: C ++ 1991-2006 гг.

Другие парадигмы программирования, которые были описаны как универсальное программирование, включают универсальное программирование типа данных, как описано в разделе «Общее программирование - введение». Подход « Избавьтесь от шаблона» - это легкий общий подход к программированию для Haskell.

В этой статье мы отделяем вышеприведенные парадигмы универсального программирования высокого уровня от механизмов универсальности языка программирования нижнего уровня, используемых для их реализации (см. Раздел «Поддержка универсального языка программирования» ). Для дальнейшего обсуждения и сравнения общих парадигм программирования см.

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

Средства универсальности существовали в языках высокого уровня по крайней мере с 1970-х годов в таких языках, как ML , CLU и Ada , и впоследствии были приняты многими объектно-ориентированными и объектно-ориентированными языками, включая BETA , C ++ , D , Eiffel , Java , и ныне несуществующий язык DEC Trellis-Owl .

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

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

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

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

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

template<typename T>
class List {
  // Class contents.
};

List<Animal> list_of_animals;
List<Car> list_of_cars;

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

// "&" denotes a reference
template<typename T>
void Swap(T& a, T& b) { // A similar, but safer and potentially faster function 
                        // is defined in the standard library header <utility>
  T temp = b;
  b = a;
  a = temp;
}

std::string world = "World!";
std::string hello = "Hello, ";
Swap(world, hello);
std::cout << world << hello << ‘\n’;  // Output is "Hello, World!".

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

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

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

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

Общий блок представляет собой пакет или подпрограмма , которая принимает один или более общие формальные параметры .

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

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

Пример

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

 generic
    Max_Size : Natural; -- a generic formal value
    type Element_Type is private; -- a generic formal type; accepts any nonlimited type
 package Stacks is
    type Size_Type is range 0 .. Max_Size;
    type Stack is limited private;
    procedure Create (S : out Stack;
                      Initial_Size : in Size_Type := Max_Size);
    procedure Push (Into : in out Stack; Element : in Element_Type);
    procedure Pop (From : in out Stack; Element : out Element_Type);
    Overflow : exception;
    Underflow : exception;
 private
    subtype Index_Type is Size_Type range 1 .. Max_Size;
    type Vector is array (Index_Type range <>) of Element_Type;
    type Stack (Allocated_Size : Size_Type := 0) is record
       Top : Index_Type;
       Storage : Vector (1 .. Allocated_Size);
    end record;
 end Stacks;

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

 type Bookmark_Type is new Natural;
 -- records a location in the text document we are editing

 package Bookmark_Stacks is new Stacks (Max_Size => 20,
                                        Element_Type => Bookmark_Type);
 -- Allows the user to jump between recorded locations in a document

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

 type Document_Type is record
    Contents : Ada.Strings.Unbounded.Unbounded_String;
    Bookmarks : Bookmark_Stacks.Stack;
 end record;

 procedure Edit (Document_Name : in String) is
   Document : Document_Type;
 begin
   -- Initialise the stack of bookmarks:
   Bookmark_Stacks.Create (S => Document.Bookmarks, Initial_Size => 10);
   -- Now, open the file Document_Name and read it in...
 end Edit;
Преимущества и ограничения

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

 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 ++ и требует особой осторожности, как описано ниже).
    • можно создавать экземпляры дженериков во время выполнения, а также во время компиляции, поскольку для нового экземпляра не требуется новый объектный код.
    • фактические объекты, соответствующие универсальному формальному объекту, всегда считаются нестатическими внутри универсального; подробности и последствия см. в общих формальных объектах в Викиучебнике.
  • все экземпляры универсального кода абсолютно одинаковы, поэтому легче просматривать и понимать программы, написанные другими; нет никаких «особых случаев», которые нужно принимать во внимание.
  • все экземпляры являются явными, нет скрытых экземпляров, которые могли бы затруднить понимание программы.
  • Ада не допускает «метапрограммирования шаблонов», потому что не допускает специализаций.

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

Основная статья: Шаблон (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);  // Outputs 7.

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

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

Это работает независимо от того, являются ли аргументы xи yцелыми числами, строками или любым другим типом, для которого выражение x < yявляется разумным, или, более конкретно, для любого типа, для которого operator<определено. Общее наследование не требуется для набора типов, которые можно использовать, и поэтому оно очень похоже на утиную типизацию . Программа, определяющая пользовательский тип данных, может использовать перегрузку оператора для определения значения <этого типа, что позволяет использовать его с max()шаблоном функции. Хотя в этом изолированном примере это может показаться незначительным преимуществом, в контексте всеобъемлющей библиотеки, такой как STL, он позволяет программисту получить обширную функциональность для нового типа данных, просто определив для него несколько операторов. Простое определение <позволяет типу , которые будут использоваться со стандартом sort(), stable_sort()и binary_search()алгоритмы или быть помещены внутрь структур данных , такие как setS, отвалы и ассоциативные массивы .

Шаблоны 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) и раздувание кода :

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

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

-  Бьярн Страуструп , Дизайн и эволюция C ++, 1994.

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

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

Шаблоны в D

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

  • Параметры шаблона в D не ограничиваются только типами и примитивными значениями (как это было в C ++ до C ++ 20), но также допускают произвольные значения времени компиляции (такие как строки и структурные литералы) и псевдонимы для произвольных идентификаторов, включая другие шаблоны или экземпляры шаблонов.
  • Ограничения шаблона и static ifоператор предоставляют альтернативу концепциям C ++ и if constexpr.
  • is(...)Выражение позволяет спекулятивная конкретизации проверить черты объекта во время компиляции.
  • autoКлючевое слово и typeofвыражение позволяет вывод типа для объявления переменных и возвращаемых значений функций, которые , в свою очередь , позволяет «типы Волдеморт» (типы , которые не имеют глобальное имя).

Шаблоны в 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;     // can define a range object
        if (r.empty) {}   // can test for empty
        r.popFront();     // can invoke popFront()
        auto h = r.front; // can get the front of the range
    }));
}

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

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

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

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

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

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

// Import the contents of example.htt as a string manifest constant.
enum htmlTemplate = import("example.htt");

// Transpile the HTML template to D code.
enum htmlDCode = htmlTemplateToD(htmlTemplate);

// Paste the contents of htmlDCode as D code.
mixin(htmlDCode);

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

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

Базовая / неограниченная универсальность

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

class
    LIST [G]
            ...
feature   -- Access
    item: G
            -- The item currently pointed to by cursor
            ...
feature   -- Element change
    put (new_item: G)
            -- Add `new_item' at the end of the list
            ...

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

    list_of_accounts: LIST [ACCOUNT]
            -- Account list

    list_of_deposits: LIST [DEPOSIT]
            -- Deposit list

В системе типов Эйфеля, хотя класс LIST [G]считается классом, он не считается типом. Однако родовое происхождение LIST [G]таких как LIST [ACCOUNT]считается типом.

Ограниченная универсальность

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

class
    SORTED_LIST [G -> COMPARABLE]

Дженерики в Java

Основная статья: Дженерики в Java

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

Универсальность в .NET [C #, VB.NET]

Универсальные шаблоны были добавлены как часть .NET Framework 2.0 в ноябре 2005 года на основе исследовательского прототипа Microsoft Research, начатого в 1999 году. Несмотря на то, что универсальные шаблоны в Java похожи на универсальные шаблоны в Java, универсальные шаблоны .NET не применяют стирание типов , а реализуют универсальные шаблоны как первоклассный механизм. во время выполнения с использованием реификации . Этот вариант дизайна обеспечивает дополнительные функциональные возможности, такие как разрешение отражения с сохранением универсальных типов, а также устранение некоторых ограничений стирания (например, невозможности создания универсальных массивов). Это также означает, что приведения во время выполнения и обычно дорогостоящие преобразования боксов не снижают производительность . Когда примитивные типы и типы значений используются в качестве универсальных аргументов, они получают специализированные реализации, позволяющие создавать эффективные универсальные коллекции и методы. Как и в C ++ и Java, вложенные универсальные типы, такие как Dictionary <string, List <int>>, являются допустимыми типами, однако их не рекомендуется использовать для подписей членов в правилах разработки анализа кода.

.NET допускает шесть разновидностей ограничений универсального типа с использованием whereключевого слова, включая ограничение универсальных типов как типов значений, как классов, наличия конструкторов и реализации интерфейсов. Ниже приведен пример ограничения интерфейса: 

using System;

class Sample
{
    static void Main()
    {
        int[] array = { 0, 1, 2, 3 };
        MakeAtLeast<int>(array, 2); // Change array to { 2, 2, 2, 3 }
        foreach (int i in array)
            Console.WriteLine(i); // Print results.
        Console.ReadKey(true);
    }

    static void MakeAtLeast<T>(T[] list, T lowest) where T : IComparable<T>
    {
        for (int i = 0; i < list.Length; i++)
            if (list[i].CompareTo(lowest) < 0)
                list[i] = lowest;
    }
}

MakeAtLeast()Метод позволяет работать с массивами, с элементами универсального типа T. Ограничение типа метода указывает, что метод применим к любому типу T, реализующему универсальный IComparable<T>интерфейс. Это гарантирует ошибку времени компиляции , если метод вызывается, если тип не поддерживает сравнение. Интерфейс предоставляет общий метод CompareTo(T).

Вышеупомянутый метод также можно было бы написать без универсальных типов, просто используя неуниверсальный Arrayтип. Однако, поскольку массивы контравариантны , приведение типов не будет безопасным для типов , и компилятор не сможет найти определенные возможные ошибки, которые в противном случае были бы обнаружены при использовании универсальных типов. Кроме того, методу потребуется доступ к элементам массива как objects, а также потребуется приведение типов для сравнения двух элементов. (Для типов значений , например таких типов, как intэто требует бокс преобразования, хотя это можно обойти , используя Comparer<T>класс, как это делается в стандартных классах коллекции.)

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

    //A generic class
    public class GenTest<T>
    {
        //A static variable - will be created for each type on reflection
        static CountedInstances OnePerType = new CountedInstances();

        //a data member
        private T mT;

        //simple constructor
        public GenTest(T pT)
        {
            mT = pT;
        }
    }

    //a class
    public class CountedInstances
    {
        //Static variable - this will be incremented once per instance
        public static int Counter;

        //simple constructor
        public CountedInstances()
        {
            //increase counter by one during object instantiation
            CountedInstances.Counter++;
        }
    }

  //main code entry point
  //at the end of execution, CountedInstances.Counter = 2
  GenTest<int> g1 = new GenTest<int>(1);
  GenTest<int> g11 = new GenTest<int>(11);
  GenTest<int> g111 = new GenTest<int>(111);
  GenTest<double> g2 = new GenTest<double>(1.0);

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

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

program Sample;

{$APPTYPE CONSOLE}

uses
  Generics.Defaults; //for IComparer<>

type
  TUtils = class
    class procedure MakeAtLeast<T>(Arr: TArray<T>; const Lowest: T;
      Comparer: IComparer<T>); overload;
    class procedure MakeAtLeast<T>(Arr: TArray<T>; const Lowest: T); overload;
  end;

class procedure TUtils.MakeAtLeast<T>(Arr: TArray<T>; const Lowest: T;
  Comparer: IComparer<T>);
var
  I: Integer;
begin
  if Comparer = nil then Comparer := TComparer<T>.Default;
  for I := Low(Arr) to High(Arr) do
    if Comparer.Compare(Arr[I], Lowest) < 0 then
      Arr[I] := Lowest;
end;

class procedure TUtils.MakeAtLeast<T>(Arr: TArray<T>; const Lowest: T);
begin
  MakeAtLeast<T>(Arr, Lowest, nil);
end;

var
  Ints: TArray<Integer>;
  Value: Integer;
begin
  Ints := TArray<Integer>.Create(0, 1, 2, 3);
  TUtils.MakeAtLeast<Integer>(Ints, 2);
  for Value in Ints do
    WriteLn(Value);
  ReadLn;
end.

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

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

В Free Pascal до Delphi были реализованы дженерики с другим синтаксисом и семантикой. Однако, начиная с версии 2.6.0 FPC, синтаксис в стиле Delphi доступен при использовании языкового режима {$ mode Delphi}. Таким образом, программисты Free Pascal могут использовать дженерики в любом стиле, который они предпочитают.

Пример Delphi и Free Pascal: 

// Delphi style
unit A;

{$ifdef fpc}
  {$mode delphi}
{$endif}

interface

type
  TGenericClass<T> = class
    function Foo(const AValue: T): T;
  end;

implementation

function TGenericClass<T>.Foo(const AValue: T): T;
begin
  Result := AValue + AValue;
end;

end.

// Free Pascal's ObjFPC style
unit B;

{$ifdef fpc}
  {$mode objfpc}
{$endif}

interface

type
  generic TGenericClass<T> = class
    function Foo(const AValue: T): T;
  end;

implementation

function TGenericClass.Foo(const AValue: T): T;
begin
  Result := AValue + AValue;
end;

end.

// example usage, Delphi style
program TestGenDelphi;

{$ifdef fpc}
  {$mode delphi}
{$endif}

uses
  A,B;

var
  GC1: A.TGenericClass<Integer>;
  GC2: B.TGenericClass<String>;
begin
  GC1 := A.TGenericClass<Integer>.Create;
  GC2 := B.TGenericClass<String>.Create;
  WriteLn(GC1.Foo(100)); // 200
  WriteLn(GC2.Foo('hello')); // hellohello
  GC1.Free;
  GC2.Free;
end.

// example usage, ObjFPC style
program TestGenDelphi;

{$ifdef fpc}
  {$mode objfpc}
{$endif}

uses
  A,B;

// required in ObjFPC
type
  TAGenericClassInt = specialize A.TGenericClass<Integer>;
  TBGenericClassString = specialize B.TGenericClass<String>;
var
  GC1: TAGenericClassInt;
  GC2: TBGenericClassString;
begin
  GC1 := TAGenericClassInt.Create;
  GC2 := TBGenericClassString.Create;
  WriteLn(GC1.Foo(100)); // 200
  WriteLn(GC2.Foo('hello')); // hellohello
  GC1.Free;
  GC2.Free;
end.

Функциональные языки

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

Механизм классов типов в Haskell поддерживает универсальное программирование. Шесть из предопределенных классов типов в Haskell (включая Eqтипы, которые можно сравнивать на равенство, и Showтипы, значения которых могут быть отображены как строки) имеют специальное свойство поддержки производных экземпляров. Это означает, что программист, определяющий новый тип, может заявить, что этот тип должен быть экземпляром одного из этих специальных классов типов, без предоставления реализаций методов класса, которые обычно необходимы при объявлении экземпляров класса. Все необходимые методы будут «производными», то есть построенными автоматически, на основе структуры типа. Например, следующее объявление типа двоичных деревьев утверждает, что он должен быть экземпляром классов Eqи Show: 

data BinTree a = Leaf a | Node (BinTree a) a (BinTree a)
      deriving (Eq, Show)

Это приводит к тому, что функция равенства ( ==) и функция строкового представления ( show) автоматически определяются для любого типа формы BinTree Tпри условии, что она Tсама поддерживает эти операции.

Поддержка производных экземпляров Eqи Showделает их методы ==и showуниверсальными качественно отличными от параметрически полиморфных функций: эти «функции» (точнее, семейства функций с индексированием по типу) могут применяться к значениям различных типов, и хотя они ведут себя по-разному для каждого типа аргумента, требуется небольшая работа, чтобы добавить поддержку нового типа. Ральф Хинце (2004) показал, что подобный эффект может быть достигнут для классов типов, определяемых пользователем, с помощью определенных методов программирования. Другие исследователи предложили подходы к этому и другим видам универсальности в контексте Haskell и расширений Haskell (обсуждаемых ниже).

Полип

PolyP был первым расширением общего языка программирования для Haskell . В PolyP универсальные функции называются политипическими . В языке представлена ​​специальная конструкция, в которой такие разнотипные функции могут быть определены посредством структурной индукции по структуре функтора шаблона обычного типа данных. Обычные типы данных в PolyP - это подмножество типов данных Haskell. Обычный тип данных t должен иметь вид * → * , и если a является аргументом формального типа в определении, то все рекурсивные вызовы t должны иметь форму ta . Эти ограничения исключают типы данных более высокого порядка, а также вложенные типы данных, где рекурсивные вызовы имеют другую форму. Функция сглаживания в PolyP здесь представлена ​​в качестве примера: 

   flatten :: Regular d => d a -> [a]
   flatten = cata fl

   polytypic fl :: f a [a] -> [a]
     case f of
       g+h -> either fl fl
       g*h -> \(x,y) -> fl x ++ fl y
       () -> \x -> []
       Par -> \x -> [x]
       Rec -> \x -> x
       d@g -> concat . flatten . pmap fl
       Con t -> \x -> []

   cata :: Regular d => (FunctorOf d a b -> b) -> d a -> b
Общий Haskell

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

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

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

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

Например, функция равенства в Generic Haskell: 

   type Eq {[ * ]} t1 t2 = t1 -> t2 -> Bool
   type Eq {[ k -> l ]} t1 t2 = forall u1 u2. Eq {[ k ]} u1 u2 -> Eq {[ l ]} (t1 u1) (t2 u2)

   eq {| t :: k |} :: Eq {[ k ]} t t
   eq {| Unit |} _ _ = True
   eq {| :+: |} eqA eqB (Inl a1) (Inl a2) = eqA a1 a2
   eq {| :+: |} eqA eqB (Inr b1) (Inr b2) = eqB b1 b2
   eq {| :+: |} eqA eqB _ _ = False
   eq {| :*: |} eqA eqB (a1 :*: b1) (a2 :*: b2) = eqA a1 a2 && eqB b1 b2
   eq {| Int |} = (==)
   eq {| Char |} = (==)
   eq {| Bool |} = (==)

Чистый

Clean предлагает универсальное программирование на основе PolyP и универсальный Haskell, поддерживаемый GHC> = 6.0. Он параметризуется по виду как таковой, но предлагает перегрузку.

Другие языки

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

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

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

C поддерживает "типовые выражения" с использованием ключевого слова: _Generic

#define cbrt(x) _Generic((x), long double: cbrtl, \
                              default: cbrt, \
                              float: cbrtf)(x)

Смотрите также

использованная литература

Источники

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

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

C ++ / D
C # /. NET
Delphi / Object Pascal
Эйфель
Haskell
Джава