stringtranslate.com

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

 общий  Max_Size  :  Natural ;  -- общий  тип формального значения  Element_Type  является  частным ;  -- общий формальный тип; принимает любой  пакет неограниченного типа.  Стеки  имеют  тип  Size_Type  —  диапазон  0  ..  Max_Size ;  тип  стека  ограничен  частным ;​  процедура Create ( S : out Stack ; Initial_Size : in Size_Type := Max_Size ); процедура Push ( Into : in out Stack ; Element : in Element_Type ); процедура Pop ( From : in out Stack ; Element : out Element_Type ); Переполнение : исключение ; Недополнение : исключение ; частный подтип Index_Type — это диапазон Size_Type 1 .. Max_Size ; type Vector — это массив ( диапазон Index_Type <>) из Element_Type ; тип Stack ( Allocated_Size : Size_Type := 0 ) — это запись Top : Index_Type ; Хранилище : векторное ( 1 .. Allocated_Size ); завершить запись ; конец стеков ;

Создание экземпляра общего пакета:

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

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

 type  Document_Type  — это  запись.  Содержание  :  Ada . Струны . Неограниченный . Неограниченная_Строка ;  Закладки  :  Bookmark_Stacks . Куча ;  завершить запись ; процедура  Edit  ( Document_Name  : in  String )  —  Document  :  Document_Type ;  начало  — Инициализировать стек закладок:  Bookmark_Stacks . Создать  ( S  =>  Document . Bookmarks ,  Initial_Size  =>  10 );  -- Теперь откройте файл Document_Name и прочитайте его...  end  Edit ;
Преимущества и ограничения

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

 универсальный  тип  Index_Type  равен  (<>);  -- должен быть дискретным типом.  Тип  Element_Type  является  частным ;  -- может быть любым неограниченным типом.  Array_Type  —  это  массив  ( диапазон Index_Type  <>) из Element_Type ;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    -  Бьерн Страуструп , Проектирование и эволюция C++, 1994 г. [19]
  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 . пустой ) {} // можно проверить пустой r .popFront (); // можно вызвать popFront () auto h = r .front ; // можно получить начало диапазона })) ; }

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

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

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

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

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

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

Генеричность в Эйфеле

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

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

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

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

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

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

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

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

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

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

Дженерики в Java

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

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

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

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

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

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

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

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

 //Общий класс public class GenTest < T > { //Статическая переменная - будет создана для каждого типа при отражении static CountedInstances OnePerType = new CountedInstances ();            //член данных Private T mT ;    //простой конструктор public GenTest ( T pT ) { mT = pT ; } }          //класс public class CountedInstances { //Статическая переменная — она будет увеличиваться один раз для каждого экземпляра public static int Counter ;          //простой конструктор public CountedInstances () { //увеличиваем счетчик на единицу во время создания экземпляра объекта CountedInstances . Счетчик ++ ; } }        // точка входа в основной код // в конце выполнения CountedInstances.Counter = 2 GenTest < int > g1 = new GenTest < int > ( 1 ); GenTest <int> g11 = новый GenTest <int> ( 11 ) ;​​​ GenTest <int> g111 = новый GenTest <int> ( 111 ) ;​​​ GenTest <double> g2 = новый GenTest <double> ( 1.0 ) ;​​​

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

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

Образец программы ; {$APPTYPE КОНСОЛЬ}использует дженерики . По умолчанию ; //для IComparer<>  тип TUtils = класс класс процедура MakeAtLeast <T> ( Arr : TArray <T> ; const Lowest : T ; Comparer : IComparer <T> ) ;​​​​​ перегрузка ; процедура класса MakeAtLeast <T> ( Arr : TArray <T> ; const Lowest : T ) ;​​​ перегрузка ; конец ;                      процедура класса TUtils . MakeAtLeast <T> ( Arr : TArray <T> ; const Lowest : T ; Comparer : IComparer <T> ) ;​​​​​ вар I : Целое число ; начать , если Comparer = nil, тогда Comparer := TComparer < T >. По умолчанию ; for I := Low ( Arr ) to High ( Arr ) делайте if Comparer . Сравните ( Arr [ I ] , Самый низкий ) < 0 , тогда Arr [ I ] := Самый низкий ; конец ;                                  процедура класса TUtils . MakeAtLeast <T> ( Arr : TArray <T> ; const Lowest : T ) ;​​​ начать MakeAtLeast <T> ( Arr , Самый низкий , ноль ) ;​ конец ;         var Ints : TArray < Целое число >; Значение : Целое число ; начало Ints := TArray < Целое число >. Создать ( 0 , 1 , 2 , 3 ) ; TUtils . MakeAtLeast <Integer> ( Ints , 2 ) ;​​ для значения в Ints do WriteLn ( Value ) ; ЧитатьЛн ; конец .

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

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

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

Пример Delphi и Free Pascal:

// модуль стиля Delphi A ; {$ifdef fpc} {$mode delphi} {$endif} интерфейстип TGenericClass <T> = функция класса Foo ( const AValue : T ) : T ;​​ конец ;         выполнениефункция TGenericClass <T> .​ Foo ( const AValue : T ) : T ; начало результата := AValue + AValue ; конец ;         конец .// Стиль ObjFPC Free Pascal unit B ; {$ifdef fpc} {$mode objfpc} {$endif} интерфейстип generic TGenericClass <T> = функция класса Foo ( const AValue : T ) : T ;​​ конец ;          выполнениефункция TGenericClass . Foo ( const AValue : T ) : T ; начало результата := AValue + AValue ; конец ;         конец .// пример использования, программа в стиле Delphi TestGenDelphi ; {$ifdef fpc} {$mode delphi} {$endif} использует A , B ; вар GC1 : A.​ TGenericClass < Целое число >; ГК2 : Б.​ TGenericClass < строка >; начать GC1 := A . TGenericClass < Целое число >. Создавать ; GC2 := B . TGenericClass < строка >. Создавать ; WriteLn ( GC1.Foo ( 100 ) ) ;​ // 200 WriteLn ( GC2.Foo ( ' привет' ) ) ; // привет, привет GC1 . Бесплатно ; ГК2 . Бесплатно ; конец .                // пример использования, программа в стиле ObjFPC TestGenDelphi ; {$ifdef fpc} {$mode objfpc} {$endif} использует A , B ; // требуется в типе ObjFPC TAGenericClassInt = specialize A. TGenericClass < Целое число >; TBGenericClassString = специализировать B . TGenericClass < Строка >; вар GC1 : TAGenericClassInt ; GC2 : TBGenericClassString ; начать GC1 := TAGenericClassInt . Создавать ; GC2 := TBGenericClassString . Создавать ; WriteLn ( GC1.Foo ( 100 ) ) ;​ // 200 WriteLn ( GC2.Foo ( ' привет' ) ) ; // привет, привет GC1 . Бесплатно ; ГК2 . Бесплатно ; конец .

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

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

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

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

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

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

Полип

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

 Flatten :: Regular d => d a -> [ a ] ​​Flatten = cata fl             политипический fl :: f a [ a ] ​​-> [ a ] ​​случай f of g + h -> либо fl fl g * h -> \ ( x , y ) -> fl x ++ fl y () -> \ x -> [] Par -> \ x -> [ x ] Rec -> \ x -> x d @ g -> concat . сгладить . pmap fl Con t -> \ x -> []                                                      cata :: Regular d => ( FunctorOf d a b -> b ) -> d a -> b
Общий Хаскелл

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

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

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

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

Чистый

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

Другие языки

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

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

VHDL , являющийся производным от Ada, также имеет общие возможности. [32]

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

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

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

Рекомендации

  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 г.). Элементы программирования . Аддисон-Уэсли Профессионал. ISBN 978-0-321-63537-2.
  7. ^ Массер, Дэвид Р.; Степанов, Александр А. (1987). «Библиотека универсальных алгоритмов в Ada». Материалы ежегодной международной конференции ACM SIGAda 1987 года по Ada-SIGAda '87 . стр. 216–225. CiteSeerX 10.1.1.588.7431 . дои : 10.1145/317500.317529. ISBN  0897912438. S2CID  795406.
  8. ^ Александр Степанов и Мэн Ли: Библиотека стандартных шаблонов. Технический отчет лабораторий HP 95-11(R.1), 14 ноября 1995 г.
  9. ^ Мэтью Х. Остерн: Общее программирование и STL: использование и расширение стандартной библиотеки шаблонов C++. Addison-Wesley Longman Publishing Co., Inc. Бостон, Массачусетс, США, 1998 г.
  10. ^ Джереми Г. Сик, Ли-Куан Ли, Эндрю Ламсдейн: Библиотека графиков повышения: Руководство пользователя и справочное руководство. Аддисон-Уэсли 2001 г.
  11. ^ Степанов, Александр. Краткая история STL (PDF) .
  12. ^ аб Страуструп, Бьярн. Развитие языка в реальном мире и для него: C++ 1991–2006 (PDF) . дои : 10.1145/1238844.1238848. S2CID  7518369.
  13. ^ Ло Руссо, Грациано. «Интервью с А. Степановым».
  14. ^ Бэкхаус, Роланд; Янссон, Патрик; Журинг, Йохан; Меертенс, Ламберт (1999). Общее программирование – введение (PDF) .
  15. ^ Ламмель, Ральф; Пейтон Джонс, Саймон (январь 2003 г.). «Откажитесь от шаблона: практический шаблон проектирования для общего программирования» (PDF) . Майкрософт . Проверено 16 октября 2016 г.
  16. ^ Дос Рейс, Габриэль; Джарви, Яакко (2005). «Что такое общее программирование? (препринт LCSD'05)» (PDF) . Архивировано из оригинала (PDF) 25 декабря 2005 года.
  17. ^ Р. Гарсия; Дж. Джарви; А. Ламсдейн; Дж. Сик; Дж. Уиллкок (2005). «Расширенное сравнительное исследование языковой поддержки универсального программирования (препринт)». CiteSeerX 10.1.1.110.122 . 
  18. ^ Страуструп, Дос Рейс (2003): Концепции - варианты дизайна для проверки аргументов шаблона
  19. ^ Страуструп, Бьярн (1994). «15.5 Как избежать репликации кода». Проектирование и эволюция C++ . Ридинг, Массачусетс: Аддисон-Уэсли. стр. 346–348. Бибкод : 1994декабрь..книга.....С. ISBN 978-81-317-1608-3.
  20. ^ Брайт, Уолтер. «Типы Волдеморта в D». Доктор Доббс . Проверено 3 июня 2015 г.
  21. ^ Создание объектно-ориентированного программного обеспечения, Prentice Hall, 1988, и объектно-ориентированное создание программного обеспечения, второе издание, Prentice Hall, 1997.
  22. ^ Эйфелева: Язык, Прентис Холл, 1991.
  23. ^ Блох 2018, с. 126, §Пункт 28: Предпочитайте списки массивам.
  24. ^ История обобщений .NET/C#: некоторые фотографии за февраль 1999 г.
  25. ^ Альбахари 2022.
  26. ^ C#: вчера, сегодня и завтра: интервью с Андерсом Хейлсбергом
  27. ^ Универсальные шаблоны в C#, Java и C++.
  28. ^ Анализ кода CA1006: не вкладывать универсальные типы в сигнатуры членов.
  29. ^ Ограничения на параметры типа (Руководство по программированию на C#)
  30. ^ Общее руководство пользователя Haskell.
  31. ^ Verilog на примере, раздел «Остальное для справки» . Блейн К. Ридлер, Full Arc Press, 2011. ISBN 978-0-9834973-0-1 
  32. ^ https://www.ics.uci.edu/~jmoorkan/vhdlref/generics.html Справочник VHDL
  33. ↑ Проект комитета WG14 N1516 — 4 октября 2010 г.

Источники

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

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

С++, Д
С#, .NET
Делфи, Объект Паскаль
Эйфелева
Хаскелл
Джава