Обобщённое программирование ( англ. generic programming ) — парадигма программирования , заключающаяся в таком описании данных и алгоритмов , которое можно применять к различным типам данных , не меняя само это описание. В том или ином виде поддерживается разными языками программирования . Возможности обобщённого программирования впервые появились в виде дженериков (обобщённых функций) в 1970-х годах в языках Клу и Ада , затем — в виде параметрического полиморфизма в ML и его потомках, а затем — во многих объектно-ориентированных языках, таких как C++ , Python , Java , Object Pascal , D , Eiffel , языках для платформы .NET и других.

Методология

Обобщённое программирование рассматривается как методология программирования , основанная на разделении структур данных и алгоритмов через использование абстрактных описаний требований . Абстрактные описания требований являются расширением понятия абстрактного типа данных . Вместо описания отдельного типа в обобщённом программировании применяется описание семейства типов, имеющих общий интерфейс и семантическое поведение ( англ. semantic behavior ). Набор требований, описывающий интерфейс и семантическое поведение, называется концепцией ( concept ). Таким образом, написанный в обобщённом стиле алгоритм может применяться для любых типов, удовлетворяющих его своими концепциями. Такая возможность называется полиморфизмом .

Говорят, что тип моделирует концепцию (является моделью концепции), если он удовлетворяет её требованиям. Концепция является уточнением другой концепции, если она дополняет последнюю. Требования к концепциям содержат следующую информацию:

• Допустимые выражения ( англ. valid expressions ) — выражения языка программирования, которые должны успешно компилироваться для типов, моделирующих концепцию.
• Ассоциированные типы ( associated types ) — вспомогательные типы, имеющие некоторое отношение к моделирующему концепцию типу.
• Инварианты ( invariants ) — такие характеристики типов, которые должны быть постоянно верны во время исполнения . Обычно выражаются в виде предусловий и постусловий . Невыполнение предусловия влечёт непредсказуемость соответствующей операции и может привести к ошибкам.
• Гарантии сложности ( complexity guarantees ) — максимальное время выполнения допустимого выражения или максимальные требования к различным ресурсам в ходе выполнения этого выражения.

В C++ объектно-ориентированное программирование (ООП) реализуется посредством виртуальных функций и наследования , а обобщённое программирование (ОП) — с помощью шаблонов классов и функций. Тем не менее, суть обеих методологий связана с конкретными технологиями реализации лишь косвенно. Говоря более формально, ООП основано на полиморфизме подтипов , а ОП — на параметрическом полиморфизме . В других языках то и другое может быть реализовано иначе. Например, мультиметоды в CLOS имеют сходную с параметрическим полиморфизмом семантику.

Массер и Степанов выделяют следующие этапы в решении задачи по методологии ОП:

1. Найти полезный и эффективный алгоритм.
2. Определить обобщённое представление (параметризовать алгоритм, минимизировав требования к обрабатываемым данным).
3. Описать набор (минимальных) требований, удовлетворяя которые всё ещё можно получить эффективные алгоритмы.
4. Создать каркас на основе классифицированных требований.

Минимизация и создание каркаса ставят целью создание такой структуры, при которой алгоритмы не зависят от конкретных типов данных. Этот подход отражён в структуре библиотеки STL .

Альтернативный подход к определению обобщённого программирования, который можно назвать обобщённым программированием типов данных ( англ. datatype generic programming ), был предложен Ричардом Бёрдом и Ламбертом Меертенсом . В нём структуры типов данных являются параметрами обобщённых программ. Для этого в язык программирования вводится новый уровень абстракции, а именно параметризация по отношению к классам алгебр с переменной сигнатурой . Хотя теории обоих подходов не зависят от языка программирования, подход Массера — Степанова, делающий упор на анализ концепций, сделал C++ своей основной платформой, тогда как обобщённое программирование типов данных используют почти исключительно Haskell и его варианты .

Общий механизм

Средства обобщённого программирования реализуются в языках программирования в виде тех или иных синтаксических средств, дающих возможность описывать данные (типы данных) и алгоритмы (процедуры, функции, методы), параметризуемые типами данных. У функции или типа данных явно описываются формальные параметры-типы . Это описание является обобщённым и в исходном виде непосредственно использовано быть не может.

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

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

Обобщённое программирование в языках

C++

В языке C++ обобщённое программирование основывается на понятии «шаблон», обозначаемом ключевым словом template . Широко применяется в стандартной библиотеке C++ (см. STL ), а также в сторонних библиотеках boost , Loki . Большой вклад в появление развитых средств обобщённого программирования в C++ внёс Александр Степанов .

В качестве примера приведём шаблон (обобщение) функции, возвращающей большее значение из двух.

// Описание шаблона функции
template <typename T> T max(T x, T y)
{
    if (x < y)
        return y;
    else
        return x;
}
...
// Применение функции, заданной шаблоном

int a = max(10,15);
...
double f = max(123.11, 123.12);
...

или шаблон (обобщение) класса связного списка:

template <class T>
 class List
 {
 /* ... */
 public:
   void Add( const T& Element );
   bool Find( const T& Element );
 /* ... */
 };

Haskell

Язык Haskell предоставляет обобщённое программирование типов данных. В следующем примере a — параметрическая переменная типа.

data List a = Nil | Cons a (List a)
length :: List a -> Int
length Nil = 0
length (Cons _ tl) = 1 + length tl

Пример вычислений:

length (Cons 1 (Cons 2 Nil)) == 2

Java

Java предоставляет средства обобщённого программирования, синтаксически основанные на C++, начиная с версии J2SE 5.0. В этом языке имеются generics или «контейнеры типа T» — подмножество обобщённого программирования.

.NET

На платформе .NET средства обобщённого программирования появились в версии 2.0.

 // Объявление обобщенного класса.
 public class GenericList<T>
 {
     void Add(T input) { }
 }
 class TestGenericList
 {
     private class ExampleClass { }
     static void Main()
     {
         GenericList<int> list1 = new GenericList<int>();
         GenericList<string> list2 = new GenericList<string>();
         GenericList<ExampleClass> list3 = new GenericList<ExampleClass>();
     }
 }

Пример на C#

interface IPerson 
{
  string GetFirstName();
  string GetLastName();
}

class Speaker 
{
  public void SpeakTo<T>(T person) where T : IPerson 
  {
    string name = person.GetFirstName();
    this.say("Hello, " + name);
  }
}

D

Пример рекурсивной генерации на основе шаблонов D :

// http://digitalmars.com/d/2.0/template.html
template Foo(T, R...) // T - тип, R - набор типов
{
    void Foo(T t, R r)
    {
	writeln(t);
	static if (r.length)	// if more arguments
	    Foo(r);		// do the rest of the arguments
    }
}

void main()
{
    Foo(1, 'a', 6.8);
}

/+++++++++++++++
 prints:
 1
 a
 6.8
 +++++++++++++++/

Object Pascal

Поддержка обобщённого программирования компилятором Free Pascal появилась начиная с версии 2.2 в 2007 году . В Delphi — с октября 2008 года. Основа поддержки обобщённых классов сначала появилась в Delphi 2007 .NET в 2006 году, но она затрагивала только .NET Framework . Более полная поддержка обобщённого программирования была добавлена в Delphi 2009 . Обобщённые классы также поддерживаются в Object Pascal в системе PascalABC.NET .

Nim

import typetraits

proc getType[T](x: T): string =
  return x.type.name

echo getType(21)       # напечатает int
echo getType(21.12)    # напечатает float64
echo getType("string") # напечатает string

Примечания

Ссылки

• (англ.)
• Gabriel Dos Reis and Jaakko Järvi,
• (рус.)

Литература

• Джереми Сик, Лай-Кван Ли, Эндрю Ламсдэйн. C++ Boost Graph Library. — Питер, 2006. — 304 с. — ISBN 5-469-00352-3 .
• Степанов Александр А., Роуз Дэниэл Э. От математики к обобщённому программированию. — ДМК Пресс, 2016. — 264 с. — ISBN 978-5-97060-379-6 .