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

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

Универсальное программирование — это стиль компьютерного программирования , в котором алгоритмы пишутся с использованием типов данных , которые должны быть указаны позже , а затем при необходимости создаются экземпляры для конкретных типов, представленных в качестве параметров . Этот подход, впервые использованный в языке программирования ML в 1973 году, позволяет писать общие функции или типы , которые отличаются только набором типов, с которыми они работают при использовании, тем самым уменьшая дублирование кода .

Универсальное программирование стало широко распространенным вместе с Ada в 1977 году. С появлением шаблонов на C++ универсальное программирование стало частью репертуара профессионального проектирования библиотек. Техники были усовершенствованы, и параметризованные типы были представлены во влиятельной книге Design Patterns 1994 года .

Новые методы были представлены Андреем Александреску в его книге 2001 года « Современный дизайн на C++: общее программирование и применение шаблонов проектирования» . Впоследствии D реализовал те же идеи.

Такие программные объекты известны как дженерики в Ada , C# , Delphi , Eiffel , F# , Java , Nim , Python , Go , Rust , Swift , TypeScript и Visual Basic .NET . Они известны как параметрический полиморфизм в ML , Scala , Julia и Haskell . (В терминологии Haskell также используется термин «общий» для обозначения родственной, но несколько иной концепции.)

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

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

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

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

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

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

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

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

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

—  Alexander Stepanov, Short History of STL

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

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

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

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

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

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

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

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

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

Универсальность реализуется и поддерживается по-разному в разных языках программирования; термин «общий» также использовался по-разному в различных контекстах программирования. Например, в Форте компилятор может выполнять код во время компиляции , и можно создавать новые ключевые слова компилятора на лету и новые реализации для этих слов. В нем мало слов , раскрывающих поведение компилятора, и поэтому он, естественно, предлагает возможности универсальности , которые, однако, не упоминаются как таковые в большинстве текстов на Форте. Точно так же динамически типизированные языки, особенно интерпретируемые, обычно предлагают универсальность по умолчанию, поскольку как передача значений в функции, так и присвоение значений не зависят от типа, и такое поведение часто используется для абстракции или краткости кода, однако это обычно не называется универсальностью , поскольку это прямое следствие системы динамической типизации, используемой в языке. Этот термин использовался в функциональном программировании , особенно в языках, подобных 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!".

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

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

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

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

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

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

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

Пример

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

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

Шаблоны на 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 данные, если не предусмотрено сравнение (в форме функтора или функции). Например: А complex не может быть использован в качестве ключа для map если не будет сравнения. К сожалению, исторически компиляторы генерируют несколько эзотерические, длинные и бесполезные сообщения об ошибках такого рода. Обеспечение соответствия определенного объекта протоколу метода может решить эту проблему. Языки, которые используют compare вместо < также можно использовать complex значения как ключи.

Другой тип шаблона — шаблон класса — распространяет ту же концепцию на классы. Специализация шаблона класса — это класс. Шаблоны классов часто используются для создания универсальных контейнеров. Например, в STL есть контейнер связанного списка . Чтобы создать связанный список целых чисел, пишут list<int>. Список строк обозначается list<string>. А 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 г.

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

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

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

Шаблоны в D

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

• Параметры шаблона в D не ограничиваются только типами и примитивными значениями (как это было в C++ до C++20), но также допускают произвольные значения времени компиляции (такие как строки и структурные литералы) и псевдонимы произвольных идентификаторов, включая другие шаблоны или экземпляры шаблонов.
• Ограничения шаблона и static if предоставляют альтернативу концепциям C++ C++ и if constexpr.
• The is(...) Выражение позволяет спекулятивное создание экземпляров для проверки свойств объекта во время компиляции.
• The 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 также предоставляет несколько функций, позволяющих генерировать код во время компиляции:

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

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

The 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 с момента создания оригинального метода и языка. Основополагающие публикации Эйфеля, используйте термин универсальность для описания создания и использования универсальных классов.

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

Универсальные классы объявляются с указанием имени класса и списка одного или нескольких формальных универсальных параметров . В следующем коде класс 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. Общее ограничение гарантирует, что элементы SORTED_LIST на самом деле можно отсортировать.

class
    SORTED_LIST [G -> COMPARABLE]

Дженерики в Java

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

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

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

Универсальные шаблоны были добавлены как часть .NET Framework 2.0 в ноябре 2005 года на основе исследовательского прототипа, проведенного Microsoft Research в 1999 году. Хотя дженерики .NET аналогичны дженерикам в Java, они не применяют стирание типов . но реализуйте дженерики как первоклассный механизм во время выполнения, используя реификацию . Этот выбор дизайна обеспечивает дополнительные функциональные возможности, такие как возможность отражения с сохранением универсальных типов и смягчение некоторых ограничений стирания (например, невозможность создания универсальных массивов). не влияют на производительность Это также означает, что приведение типов во время выполнения и обычно дорогостоящие преобразования упаковки . Когда примитивные типы и типы значений используются в качестве универсальных аргументов, они получают специализированные реализации, позволяющие создавать эффективные универсальные коллекции и методы. Как и в 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;
    }
}

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

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

Примечательным поведением статических членов в универсальном классе .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 _t;

        // simple constructor
        public GenTest(T t)
        {
            _t = t;
        }
    }

    // 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, с другим синтаксисом и семантикой. Однако, начиная с версии FPC 2.6.0, синтаксис в стиле 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 . Эти ограничения исключают типы данных более высокого порядка и вложенные типы данных, где рекурсивные вызовы имеют другую форму. Функция Flatten в 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

Общий Хаскелл

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 и Generic 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)

См. также

• Концепция (общее программирование)
• Частичная оценка
• Template metaprogramming
• Тип полиморфизма

Источники

• Альбахари, Джозеф (2022). C# 10 в двух словах (первое изд.). О'Рейли. ISBN  978-1-098-12195-2 .
• Блох, Джошуа (2018). «Эффективная Java: Руководство по языку программирования» (третье изд.). Аддисон-Уэсли. ISBN  978-0134685991 .
• Мюссер, Др. ; Степанов А.А. (1989). «Общее программирование». В П. Джанни (ред.). Символические и алгебраические вычисления: Международный симпозиум ISSAC 1988 . Конспекты лекций по информатике. Том. 358. стр. 13–25. дои : 10.1007/3-540-51084-2_2 . ISBN  978-3-540-51084-0 .
• Страуструп, Бьярн (2007). Развитие языка в реальном мире и для него: C++ 1991–2006 (PDF) . АСМ ХОПЛ 2007.
• Гамма, Эрих; Хелм, Ричард; Джонсон, Ральф; Влиссидес, Джон (1994). Шаблоны проектирования: элементы объектно-ориентированного программного обеспечения многократного использования . Аддисон-Уэсли. Бибкод : 1995dper.book.....G . ISBN  0-201-63361-2 .

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

• Габриэль Дос Рейс и Яакко Ярви, Что такое общее программирование? , LCSD 2005. Архивировано 28 августа 2019 года в Wayback Machine .
• Гиббонс, Джереми (2007). Бэкхаус, Р.; Гиббонс, Дж.; Хинце, Р.; Джуринг, Дж. (ред.). Общее программирование типов данных . Весенняя школа по программированию на основе типов данных, 2006 г. Конспекты лекций по информатике. Том. 4719. Гейдельберг: Шпрингер. стр. 1–71. CiteSeerX   10.1.1.159.1228 .
• Мейер, Бертран (1986). «Общность против наследственности». Материалы конференции «Объектно-ориентированные системы, языки и приложения программирования — OOPSLA '86» . стр. 391–405. дои : 10.1145/28697.28738 . ISBN  0897912047 . S2CID   285030 .

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

• generic-programming.org
• Александр А. Степанов, Сборник статей Александра А. Степанова (создателя СТЛ )

С++, Д

• Уолтер Брайт, «Возвращение к шаблонам» .
• Дэвид Вандевурде, Николай М. Джосуттис, Шаблоны C++: Полное руководство , 2003, Аддисон-Уэсли. ISBN   0-201-73484-2

C#, .NET

• Джейсон Кларк, « Введение универсальных шаблонов в Microsoft CLR », сентябрь 2003 г., журнал MSDN Magazine , Microsoft.
• Джейсон Кларк, « Подробнее об универсальных шаблонах в Microsoft CLR », октябрь 2003 г., журнал MSDN Magazine , Microsoft.
• М. Аамир Маниар, Generics.Net . Библиотека обобщений с открытым исходным кодом для C#.

Делфи, Объект Паскаль

• Ник Ходжес, « Руководство для рецензентов Delphi 2009 », октябрь 2008 г., Embarcadero Developer Network , Embarcadero.
• Крейг Станц, « Обобщенные шаблоны и ограничения типов Delphi 2009 », октябрь 2008 г.
• Доктор Боб, " Обобщенные шаблоны Delphi 2009 "
• Free Pascal : Справочное руководство по Free Pascal Глава 8: Обобщенные шаблоны , Майкл Ван Каннейт, 2007 г.
• Delphi для Win32: универсальные шаблоны с Delphi 2009 Win32 , Себастьен ДОЭРЕН, 2008 г.
• Delphi для .NET: Delphi Generics , Феликс КОЛИБРИ, 2008 г.

Эйфелева

• Спецификация Eiffel ISO/ECMA

Хаскелл

• Йохан Жеуринг, Шон Лезер, Хосе Петер Магальяйнс и Алексей Родригес Якушев. Библиотеки общего программирования в Haskell Утрехтский университет.
• Дэв Кларк, Йохан Йеринг и Андрес Лё, Руководство пользователя Generic Haskell
• Ральф Хинце, « Обобщенные шаблоны для масс », в материалах Международной конференции ACM SIGPLAN по функциональному программированию (ICFP), 2004 г.
• Саймон Пейтон Джонс , редактор журнала The Haskell 98 Language Report , пересмотренного в 2002 году.
• Ральф Лэммель и Саймон Пейтон Джонс , «Отбросьте свой шаблон: практический шаблон проектирования для общего программирования», в материалах международного семинара ACM SIGPLAN по типам в языковом проектировании и реализации (TLDI'03), 2003 г. (также см. веб-сайт, посвященный к этому исследованию )
• Андрес Лё, Исследование общего языка Haskell , докторская диссертация, Утрехтский университет , 2004 г. ISBN   90-393-3765-9
• Generic Haskell: язык общего программирования.

Ява

• Гилад Брача, «Обобщенные элементы языка программирования Java» , 2004 г.
• Морис Нафталин и Филип Уодлер, Java Generics и коллекции, 2006, O'Reilly Media, Inc. ISBN   0-596-52775-6
• Питер Сестофт, «Точно Java», второе издание, MIT Press, 2005 г. ISBN   0-262-69325-9
• Общее программирование на Java , 2004 г., Sun Microsystems, Inc.
• Анжелика Лангер, Часто задаваемые вопросы по Java Generics