stringtranslate.com

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

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

Обобщенное программирование было введено в мейнстрим с Ada в 1977 году. С шаблонами в C++ обобщённое программирование стало частью репертуара профессионального дизайна библиотек. Методы были дополнительно улучшены, а параметризованные типы были представлены во влиятельной книге 1994 года Design Patterns . [3]

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

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

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

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

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

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

—  Массер, Дэвид Р.; Степанов, Александр А., Обобщенное программирование [5]

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

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

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

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

—  Александр Степанов, Краткая история STL [11] [12]

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

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

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

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

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

Другие парадигмы программирования, которые были описаны как обобщенное программирование, включают обобщенное программирование Datatype , описанное в "Обобщенное программирование – введение". [14] Подход Scrap your boilerplate представляет собой облегченный обобщенный подход программирования для Haskell. [15]

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

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

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

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

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

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

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

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

template < typename T > class List { // Содержимое класса. };    Список < Животное > список_животных ; Список < Автомобиль > список_автомобилей ;

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

// "&" обозначает ссылочный шаблон < typename T > void Swap ( T & a , T & b ) { // Похожая, но более безопасная и потенциально более быстрая функция // определена в заголовке стандартной библиотеки <utility> T temp = b ; b = a ; a = temp ; }                  std :: string world = "Мир!" ; std :: string hello = "Привет, " ; Swap ( world , hello ); std :: cout << world << hello << '\ n ' ; // Вывод: "Привет, мир!".

Конструкция C++, templateиспользованная выше, широко цитируется [ требуется ссылка ] как конструкция универсальности, которая популяризировала это понятие среди программистов и разработчиков языков и поддерживает множество универсальных идиом программирования. Язык программирования D также предлагает полностью универсальные шаблоны, основанные на прецеденте C++, но с упрощенным синтаксисом. Язык программирования Java предоставляет возможности универсальности, синтаксически основанные на C++, с момента появления Java Platform, 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++ .

Универсальный модуль — это пакет или подпрограмма, которая принимает один или несколько универсальных формальных параметров . [18]

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

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

Пример

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

 generic  Max_Size  :  Natural ;  -- универсальный формальный  тип значения  Element_Type  is  private ;  -- универсальный формальный тип; принимает любой неограниченный тип  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 ;  конец  стеков ;

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

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

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

 тип  Document_Type  -  запись  Содержимое  :  Ada.Strings.Unbounded.Unbounded_String ; Закладки : Bookmark_Stacks.Stack ; конец записи ;​​​​​​​     procedure  Edit  ( Document_Name  : in  String )  is  Document  :  Document_Type ;  begin  -- Инициализируем стек закладок:  Bookmark_Stacks . Create  ( S  =>  Document . Bookmarks ,  Initial_Size  =>  10 );  -- Теперь откроем файл Document_Name и прочитаем его в...  end  Edit ;
Преимущества и ограничения

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

 универсальный  тип  Index_Type  is  (<>);  -- должен быть дискретным типом  type  Element_Type  is  private ;  -- может быть любым неограниченным типом  type  Array_Type  is  array  ( Index_Type  range  <>)  of  Element_Type ;

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

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

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

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

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

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

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

шаблон < имя_типа T > T max ( T x , T y ) { return x < y ? y : x ; }

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

std :: cout << max ( 3 , 7 ); // Выводит 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, heaps и associative arrays .

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

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

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

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

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

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

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

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

#define max(a,b) ((a) < (b) ? (b) : (a))

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

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

Использование шаблонов имеет четыре основных недостатка: поддерживаемые функции, поддержка компилятора, плохие сообщения об ошибках (обычно в SFINAE до C++20 ) и раздувание кода :

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

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

    —  Бьярне Страуструп , «Проектирование и эволюция C++», 1994 [20]
  5. Шаблонные классы или функции могут потребовать явной специализации шаблонного класса, что потребует переписывания всего класса для конкретных используемых им параметров шаблона.

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

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

Шаблоны на языке D

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

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

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

template isInputRange ( R ) { enum bool isInputRange = is ( typeof ( ( inout int = 0 ) { R r = R.init ; // можно определить объект диапазона if ( r.empty ) {} // можно проверить на пустоту r.popFront ( ) ; // можно вызвать popFront ( ) auto h = r.front ; // можно получить начало диапазона } )) ; }

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

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

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

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

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

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

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

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

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

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

class LIST [ G ] ... feature -- Доступ к элементу : G -- Элемент, на который в данный момент указывает курсор ... feature -- Изменение элемента put ( new_item : G ) -- Добавить `new_item' в конец списка ...

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

 list_of_accounts : СПИСОК [ АККАУНТ ] -- Список аккаунтов    list_of_deposits : СПИСОК [ ДЕПОЗИТ ] — Список депозитов

В системе типов Eiffel, хотя класс LIST [G]считается классом, он не считается типом. Однако, общее происхождение LIST [G]такого типа LIST [ACCOUNT]считается типом.

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

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

класс SORTED_LIST [ G -> СРАВНИТЕЛЬНЫЙ ]

Дженерики в Java

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

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

Generics были добавлены как часть .NET Framework 2.0 в ноябре 2005 года на основе исследовательского прототипа от Microsoft Research, начатого в 1999 году . [25] Хотя generics .NET похожи на generics в Java, generics .NET не применяют стирание типов , [26] : 208–209  но реализуют generics как механизм первого класса во время выполнения с помощью reification . Этот выбор дизайна обеспечивает дополнительную функциональность, такую ​​как разрешение отражения с сохранением generic типов и смягчение некоторых ограничений стирания (например, невозможность создания generic массивов). [27] [28] Это также означает, что нет падения производительности от приведения во время выполнения и обычно дорогих преобразований упаковки . Когда примитивные и значимые типы используются в качестве generic аргументов, они получают специализированные реализации, что позволяет использовать эффективные generic коллекции и методы. Как и в C++ и Java, вложенные generic типы, такие как Dictionary<string, List<int>>, являются допустимыми типами, однако не рекомендуются для сигнатур членов в правилах проектирования анализа кода. [29]

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

с использованием Системы ; класс Образец { статическая пустота Main ()   { int [] массив = { 0 , 1 , 2 , 3 };         MakeAtLeast < int > ( array , 2 ); // Изменить массив на { 2, 2, 2, 3 }   foreach ( int i в массиве )     Console.WriteLine ( i ) ; // Вывести результаты .  Консоль.ReadKey ( истина ) ;​ } static void MakeAtLeast < T > ( T [] список , T самый низкий ) где T : IComparable < T >          { для ( int i = 0 ; i < список . Длина ; i ++ )         если ( список [ i ]. СравнитьС ( самым низким ) < 0 )    список [ i ] = самый низкий ;   }}

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

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

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

 // Универсальный класс public class GenTest < T > { // Статическая переменная — будет создана для каждого типа при отражении static CountedInstances OnePerType = new CountedInstances ();            // член данных private T _t ;    // простой конструктор public GenTest ( T t ) { _t = t ; } }          // класс public class CountedInstances { //Статическая переменная — она будет увеличиваться один раз для каждого экземпляра public static int Counter ;          //простой конструктор public CountedInstances () { //увеличиваем счетчик на единицу во время создания экземпляра объекта CountedInstances . Counter ++ ; } }       // основная точка входа в код // в конце выполнения, 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

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

Образец программы ; {$КОНСОЛЬ ТИПА ПРИЛОЖЕНИЯ}использует Generics . Defaults ; //для IComparer<>  тип TUtils = класс класс процедура MakeAtLeast < T > ( Arr : TArray < T >; const Lowest : T ; Comparer : IComparer < T > ) ; перегрузка ; класс процедура MakeAtLeast < T > ( Arr : TArray < T >; const Lowest : T ) ; перегрузка ; конец ;                      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.Compar ( 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 реализовал generics до Delphi и с другим синтаксисом и семантикой. Однако, начиная с версии FPC 2.6.0, синтаксис в стиле Delphi доступен при использовании языкового режима {$mode Delphi}. Таким образом, код Free Pascal поддерживает generics в любом стиле.

Пример Delphi и Free Pascal:

// Модуль в стиле Delphi A ; {$ifdef fpc} {$mode delphi} {$endif} интерфейстип TGenericClass < T > = class function Foo ( const AValue : T ) : T ; конец ;         выполнениефункция TGenericClass <T> .​ Foo ( const AValue : T ) : T ; начало результата := AValue + AValue ; конец ;         конец .// Модуль B в стиле ObjFPC Free Pascal ; {$ifdef fpc} {$mode objfpc} {$endif} интерфейстип generic TGenericClass < T > = class function Foo ( const AValue : T ) : T ; end ;          выполнениефункция TGenericClass . Foo ( const AValue : T ) : T ; начало результата := AValue + AValue ; конец ;         конец .// пример использования, программа в стиле Delphi TestGenDelphi ; {$ifdef fpc} {$mode delphi} {$endif} использует А , В ; 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 .                // пример использования, программа в стиле ObjFPC TestGenDelphi ; {$ifdef fpc} {$mode objfpc} {$endif} использует А , В ; // требуется в типе ObjFPC 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:

данные BinTree a = Лист a | Узел ( BinTree a ) a ( BinTree a ) выведение ( Eq , Показать )

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

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

Полип

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

 flatten :: Обычный d => d a -> [ a ] ​​flatten = cata fl             политипный fl :: f a [ a ] ​​-> [ a ] ​​случай f из g + h -> либо 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 , разработанное в Утрехтском университете в Нидерландах . Расширения, которые он предоставляет:

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

В качестве примера приведем функцию равенства в Generic Haskell: [31]

 тип Eq {[ * ]} t1 t2 = t1 -> t2 -> Bool тип Eq {[ k -> l ]} t1 t2 = forall u1 u2 . Eq {[ k ]} u1 u2 -> Eq {[ l ]} ( t1 u1 ) ( t2 u2 )                                         экв { | т :: к | } :: Eq {[ k ]} t t eq { | Единица | } _ _ = Истинное уравнение { | :+: | } eqA eqB ( Inl a1 ) ( Inl a2 ) знак равно eqA a1 a2 eq { | :+: | } eqA eqB ( Inr b1 ) ( Inr b2 ) знак равно eqB b1 b2 eq { | :+: | } eqA eqB _ _ = Ложное eq { | :*: | } eqA eqB ( a1 :*: b1 ) ( a2 :*: b2 ) = eqA a1 a2 && eqB b1 b2 eq { | Интер | } = ( == ) экв { | Чар | } = ( == ) экв { | Бул | } = ( == )

Чистый

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

Другие языки

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

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

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

C поддерживает «типо-обобщенные выражения» с помощью _Genericключевого слова: [34]

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

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

Ссылки

  1. ^ Ли, Кент Д. (15 декабря 2008 г.). Языки программирования: активный подход к обучению. Springer Science & Business Media. стр. 9–10. ISBN 978-0-387-79422-8.
  2. ^ Милнер, Р.; Моррис, Л.; Ньюи, М. (1975). «Логика для вычислимых функций с рефлексивными и полиморфными типами». Труды конференции по доказательству и улучшению программ .
  3. ^ Гамма, Эрих; Хельм, Ричард; Джонсон, Ральф; Влиссидес, Джон (1994). Шаблоны проектирования . Эддисон-Уэсли. ISBN 0-201-63361-2.
  4. ^ Массер и Степанов 1989.
  5. ^ Массер, Дэвид Р.; Степанов, Александр А. Универсальное программирование (PDF) .
  6. ^ Александр Степанов; Пол МакДжонс (19 июня 2009). Элементы программирования . Addison-Wesley Professional. ISBN 978-0-321-63537-2.
  7. ^ Массер, Дэвид Р.; Степанов, Александр А. (1987). "Библиотека обобщенных алгоритмов в Ада". Труды ежегодной международной конференции ACM SIGAda 1987 года по Ада - SIGAda '87 . С. 216–225. CiteSeerX 10.1.1.588.7431 . doi :10.1145/317500.317529. ISBN  0897912438. S2CID  795406.
  8. ^ Александр Степанов и Мэн Ли: Библиотека стандартных шаблонов. Технический отчет HP Laboratories 95-11(R.1), 14 ноября 1995 г.
  9. ^ Мэтью Х. Остерн: Обобщенное программирование и STL: использование и расширение библиотеки стандартных шаблонов C++. Addison-Wesley Longman Publishing Co., Inc. Бостон, Массачусетс, США 1998
  10. ^ Джереми Г. Сик, Ли-Куан Ли, Эндрю Ламсдейн: Библиотека Boost Graph: Руководство пользователя и справочное руководство. Addison-Wesley 2001
  11. ^ Степанов, Александр. Краткая история STL (PDF) .
  12. ^ ab Страуструп, Бьярне. Развитие языка в реальном мире и для реального мира: C++ 1991-2006 (PDF) . doi :10.1145/1238844.1238848. S2CID  7518369.
  13. ^ Ло Руссо, Грациано. «Интервью с А. Степановым».
  14. ^ Бэкхаус, Роланд; Янссон, Патрик; Журинг, Йохан; Меертенс, Ламберт (1999). Общее программирование – введение (PDF) .
  15. ^ Лэммель, Ральф; Пейтон Джонс, Саймон (январь 2003 г.). «Scrap Your Boilerplate: A Practical Design Pattern for Generic Programming» (PDF) . Microsoft . Получено 16 октября 2016 г. .
  16. ^ Дос Рейс, Габриэль; Ярви, Яакко (2005). "Что такое обобщенное программирование? (препринт LCSD'05)" (PDF) . Архивировано из оригинала (PDF) 25 декабря 2005 г.
  17. ^ R. Garcia; J. Järvi; A. Lumsdaine; J. Siek; J. Willcock (2005). «Расширенное сравнительное исследование языковой поддержки для обобщенного программирования (препринт)». CiteSeerX 10.1.1.110.122 . 
  18. ^ "Generic Units". www.adaic.org . Получено 25 апреля 2024 г. .
  19. ^ Страуструп, Дос Рейс (2003): Концепции — Выбор дизайна для проверки аргументов шаблона
  20. ^ Страуструп, Бьярне (1994). "15.5 Избегание репликации кода". Проектирование и эволюция C++ . Рединг, Массачусетс: Addison-Wesley. стр. 346–348. Bibcode :1994dec..book.....S. ISBN 978-81-317-1608-3.
  21. ^ Брайт, Уолтер. «Волдеморт печатает на букву D». Доктор Доббс . Получено 3 июня 2015 г.
  22. ^ Объектно-ориентированное построение программного обеспечения, Prentice Hall, 1988, и Объектно-ориентированное построение программного обеспечения, второе издание, Prentice Hall, 1997.
  23. ↑ Эйфель: Язык, Prentice Hall, 1991.
  24. ^ Блох 2018, стр. 126, §Пункт 28: Предпочитайте списки массивам.
  25. ^ История дженериков .NET/C#: несколько фотографий с февраля 1999 г.
  26. ^ Албахари 2022.
  27. ^ C#: вчера, сегодня и завтра: интервью с Андерсом Хейлсбергом
  28. ^ Универсальные типы в C#, Java и C++
  29. ^ Анализ кода CA1006: Не вкладывайте универсальные типы в сигнатуры членов
  30. ^ Ограничения на параметры типа (Руководство по программированию на C#)
  31. ^ Общее руководство пользователя Haskell
  32. ^ Verilog в примерах, раздел «Остальное для справки» . Блейн К. Ридлер, Full Arc Press, 2011. ISBN 978-0-9834973-0-1 
  33. ^ https://www.ics.uci.edu/~jmoorkan/vhdlref/generics.html Справочник VHDL
  34. ^ Проект комитета WG14 N1516 — 4 октября 2010 г.

Источники

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

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

С++, D
C#, .NET
Delphi, Объектный Паскаль
Эйфелева
Хаскелл
Ява