Программирование на C++ в функциональном стиле

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

Под программированием в функциональном стиле я не имею в виду, что оно является строго функциональным, а лишь то, что в C++ легко использовать многие из функциональных строительных блоков. В данной статье основное внимание уделяется одной из важнейших конструкций функционального программирования: работе со значениями (values) в противоположность идентификациям (identities). Я рассмотрю мощную поддержку, которая всегда была в C++ для работы со значениями, потом покажу, как в новом стандарте C++ 11 эта поддержка расширена с помощью лямбд. Наконец, я дам введение по методу работы с неизменяемыми (immutable) структурами данных, который обеспечивает не только свойственное C++ быстродействие, но и защиту, уже достаточно давно реализованную в функциональных языках.

Значения в сравнении с идентификациями

Сначала позвольте мне пояснить, что я имею в виду под работой со значениями по сравнению с идентификациями. Простые значения вроде 1, 2 и 3 легко идентифицировать. Я мог бы также сказать, что 1, 2 и 3 являются константными целочисленными значениями. Однако это было бы избыточно, так как все значения — на самом деле константы, и сами значения никогда не изменяются (т. е. 1 — всегда 1, и 1 никогда не превратится в 2). С другой стороны, значение, сопоставленное с идентификацией, измениться может (x может быть сейчас равно 1, но позднее стать равным 2).

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

Код на рис. 1 демонстрирует простое использование значимого типа.

Рис. 1. Использование значимого типа

void Foo()
{
  for (int x = 0; x < 10; ++x)
  {
    // Вызываем Bar, передавая значение x, а не идентификацию
    Bar(x);
  }
}
void Bar(int y)
{
  // отображаем значение y
  cout << y << " ";
  // Изменяем значение, на которое ссылается идентификация y.
  // Примечание: это не повлияет на значение,
  // на которое ссылается переменная x.
  y = y + 1;
}
// Вывод:
// 0 1 2 3 4 5 6 7 8 9

Небольшое изменение, и переменная y может стать ссылочным типом (reference type), что кардинально меняет взаимосвязь между x и y, как показано на рис. 2.

Рис. 2. Использование ссылочного типа

void Foo()
{
  for (int x = 0; x < 10; ++x)
  {
    // Вызываем Bar, передавая идентификацию x
    Bar(x);
  }
}
void Bar(int& y)
{
  // Отображаем значение y
  cout << y << " ";
  // Изменяем значение, на которое ссылается идентификация y.
  // Примечание: это повлияет на значение переменной x.
  y = y + 1;
}
// Вывод:
// 0 2 4 6 8

Как видно на рис. 3, C++ также поддерживает модификатор const, который не дает программисту вносить изменения в переменную и тем самым еще больше защищает концепцию значения. (Однако, как и в большинстве других случаев, в C++ есть минимум один способ разрушить эту защиту. Подробнее на эту тему ищите описание const_cast, предназначенной для работы с более старым кодом, который не является «const-корректным».)

Рис. 3. Модификатор const

void Foo()
{
  for (int x = 0; x < 10; ++x)
  {
    // Вызываем Bar, передавая идентификацию x,
    // однако значение x будет защищено const
    Bar(x);
  }
}
void Bar(const int& y)
{
  // Используем значение y
  cout << y << " ";
  // Попытка изменить значение того,
  // на что ссылается идентификация y
  y = y + 1; // эта строка не компилируется, y - константа!
}

Заметьте, хотя на рис. 3 переменная y передается по ссылке, значение y защищено на этапе компиляции модификатором const. Это дает программистам на C++ эффективный способ передачи больших объектов и в то же время позволяет работать с их значениями, а не идентификациями.

Благодаря модификатору const в C++ есть неизменяемые типы данных, напоминающие таковые в большинстве языков функциональность программирования. Однако иметь дело с этими типами данных трудно. Более того, создавать детальные (deep) (полные) копии больших объектов при каждом незначительном изменении неэффективно. Тем не менее, должно быть ясно, что в стандартном C++ всегда была концепция работы со значениями (даже если ее чистота выдерживалась не полностью).

Заметьте, что поддержка значимых типов расширяется до охвата пользовательских типов через конструкторы копий и операторы присваивания. Конструкторы копий и операторы присваивания в C++ позволяют создавать детальную копию экземпляра пользовательского типа. Учитывайте, что хотя в C++ можно реализовать конструкторы копий для создания поверхностной копии (shallow copy), вы должны заботиться о сохранении семантики значений.

Поддержка программирования в функциональном стиле в C++ 11

В C++ 11 появилось целый ряд новых средств для программирования в функциональном стиле. Возможно, самое важное, что C++ теперь поддерживает лямбды (также называемые замыканиями [closures] и анонимными функциями). Лямбды позволяют структурировать код такими способами, которые ранее были бы непрактичными. Эта функциональность и раньше была доступна через функторы — мощные, но не столь удобные в использовании средства. (На самом деле «за кулисами» лямбды C++ записывают анонимные функторы.) На рис. 4 показано, как лямбды позволили улучшить наш код на простом примере, использующем STL-библиотеку (C++ standard library).

Рис. 4. Использование лямбд

void Foo()
{
  vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  for_each(begin(v), end(v), [](int i) {
    cout << i << " ";
  });
}
// Вывод:
// 1 2 3

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

Хотя C++ — лишь один из многих императивных языков, в которых теперь появились лямбды, изюминка лямбд в C++ в том, что (по аналогии с лямбдами в языках функционального программирования) они позволяют защищать концепцию работы со значениями в противоположность идентификациям. Тогда как языки функционального программирования достигают этой цели за счет неизменяемости переменных, C++ делает это, предоставляя контроль над захватом (capture). Рассмотрим код на рис. 5.

Рис. 5. Захват по ссылке

void Foo()
{
  int a[3] = { 11, 12, 13 };
  vector<function<void(void)>> vf;
  // Сохраняем лямбды для вывода каждого элемента массива
  int ctr;
  for (ctr = 0; ctr < 3; ++ctr) {
    vf.push_back([&]() {
      cout << "a[" << ctr << "] = " << a[ctr] << endl;
    });   
  }
  // Выполняем каждую лямбду
  for_each(begin(vf), end(vf), [](function<void(void)> f) {
    f();
  });
}
// Вывод:
// a[3] = -858993460
// a[3] = -858993460
// a[3] = -858993460

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

a[0] = 11
a[1] = 12
a[2] = 13

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

Также заметьте: чтобы сохранить переменную ctr «живой» для использования лямбдой вне цикла for, объявление переменной ctr следует вынести из цикла for и поместить перед ним. Хотя ненкоторые языки исключают необходимость в выносе переменных значимого типа в соответствующую область видимости, это на самом деле не решает проблему, которая заключается в том, что лямбде нужно использовать значение ctr в противоположность идентификации этой переменной. (В других языках есть обходные пути, в том числе создание явной копии и ее запись во временную переменную. Однако это немного затуманивает то, что происходит в коде, и повышает риск ошибок, так как исходная переменная тоже захватывается т из-за этого по-прежнему доступна для использования.)

Как показано в табл. 1, C++ предоставляет простой синтаксис, позволяющий легко управлять захватом лямбды, и тем самым способствует укреплению концепции работы со значениями.

Табл. 1. Синтаксис C++ для управления захватом лямбды

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

Неизменяемые типы данных

Чего не хватает, так это эффективных неизменяемых структур данных, имеющихся в некоторых языках функционального программирования. В этих языках неизменяемые структуры данных эффективны, даже когда они очень большие, потому что используют общие данные. Создание в C++ структур данных, совместно использующих данных, — дело тривиальное: вы просто динамически выделяете память под данные, и у каждой структуры есть указатели на эти данные. Увы, управлять жизненным циклом общих переменных труднее (именно поэтому, кстати, сборщики мусора стали такими популярными). К счастью, C++ 11 предоставляет элегантное решение для работы с общими переменными через класс шаблона std::shared_ptr, как показано на рис. 6.

Рис. 6. Общие переменные

void Foo()
{
  // Создаем общий int (динамически создаем целочисленное
  // значение и обеспечиваем автоматический учет ссылок)
  auto sharedInt = make_shared<int>(123);
  // Разделяем это значение с secondShare
  // (счетчик ссылок увеличивается на 1)
  shared_ptr<int> secondShare(sharedInt);
  // Освобождаем указатель на первую переменную
  // (счетчик ссылок уменьшается на 1)
  sharedInt = nullptr;
  // Проверяем, существует ли еще общий int
  cout << "secondShare = " << *secondShare << endl;
  // Общий int автоматически удаляется, когда secondShare
  // выходит за область видимости и счетчик ссылок обнуляется
}
// Вывод:
// secondShare = 123

Код на рис. 6 иллюстрирует простое использование std::shared_ptr и его вспомогательной функции std::make_shared. С помощью std::shared_ptr можно легко разделять данные между структурами, не боясь утечки памяти (при условии, что вы избегаете круговых ссылок). Заметьте, что std::shared_ptr предоставляет базовые гарантии безопасности в многопоточной среде (thread-safety) и выполняется быстро, так как использует архитектуру без блокировок. Однако учитывайте, что эти базовые гарантии не распространяются автоматически на объект, на который указывает std::shared_ptr. Тем не менее, std::shared_ptr гарантирует, что он не уменьшит степень безопасности этого объекта в многопоточной среде. Неизменяемые объекты по своей сути обеспечивают серьезные гарантии безопасности в многопоточной среде, поскольку они никогда не изменяются после создания. Так что, когда вы используете std::shared_ptr с неизменяемым объектом, эта комбинация сохраняет все гарантии безопасности неизменяемого объекта в многопоточной среде.

Теперь я могу легко создать неизменяемый класс, потенциально способный разделять данные (рис. 7).

Рис. 7. Неизменяемый класс для разделения данных

class Immutable
{
private:
  // Используем обычную переменную типа double,
  // так как ее копирование почти не влечет издержек
  double d_;
  // Используем общую строку,
  // так как строки могут быть очень большими
  std::shared_ptr<std::string const> s_;
public:
  // Конструктор по умолчанию
  Immutable()
    : d_(0.0),
      s_(std::make_shared<std::string const>(""))
  {}
  // Конструктор, принимающий строку
  Immutable(const double d, const string& s)
    : d_(d),
    s_(std::make_shared<std::string const>(s))
  {}
  // Конструктор перемещения
  Immutable(Immutable&& other)
    : s_()
  {
    using std::swap;
    swap(d_, other.d_);
    swap(s_, other.s_);
  }
  // Оператор присваивания с перемещением
  // (move assignment operator)
  Immutable& operator=(Immutable&& other)
  {
    swap(d_, other.d_);
    swap(s_, other.s_);
    return *this;
  }
// Используем конструктор копии по умолчанию
  // и оператор присваивания
  // Функции-получатели (Getter Functions)
  double GetD() const
  {
    // Возвращаем копию, поскольку double имеет
    // малый размер (8 байтов)
    return d_;
  }
  const std::string& GetS() const
  {
    // Возвращаем постоянную ссылку,
    // так как строка может быть очень большой
    return *s_;
  }
  // Функции задания (всегда возвращают новый объект)
  Immutable SetD(double d) const
  {
    Immutable newObject(*this);
    newObject.d_ = d;
    return newObject;
  }
  Immutable SetS(const std::string& s) const
  {
    Immutable newObject(*this);
    newObject.s_ = std::make_shared<std::string const>(s);
    return newObject;
  }
};

Код на рис. 7 довольно длинный, но большая его часть для конструкторов и операторов присваивания стереотипна. Последние две функции являются ключевыми для того, чтобы сделать объект неизменяемым. Заметьте, что методы SetS и SetD возвращают новый объект, что оставляет исходный объект неизменным. (Хотя включение методов SetS и SetD в виде членов класса удобно, это немного вводит в заблуждение, поскольку на самом деле они не изменяют исходный объект. Более четкое решение см. в ImmutableVector рис. 8 и 9.) Класс Immutable в действии показан на рис. 10.

Рис. 8. Использование «интеллектуального» класса шаблона ImmutableVector

template <class ImmutableVector>
void DisplayImmutableVector(const char* name, const ImmutableVector& v)
{
  using namespace std;
  cout << name << ".Size() = " << v.Size()
     << ", " << name << "[] = { ";
  for (size_t ctr = 0; ctr < v.Size(); ++ctr) {
    cout << v[ctr] << " ";
  }
  cout << "}" << endl;
}
void ImmutableVectorTest1()
{
  // Создаем ImmutableVector с размером, равным 4
  ImmutableVector<int, 4> v;
  // Другой ImmutableVector (мы возьмем копию v в элементе 6)
  ImmutableVector<int, 4> aCopyOfV;
  // Записываем в вектор 16 значений (это приводит к созданию
  // двухуровневого дерева). Заметьте, что вектор присваивается
  // сам себе. Конструктор перемещения гарантирует, что эта
  // операция не будет особо дорогостоящей. Копия, создаваемая
  // в любой момент, останется неизменной, но продолжит делить
  // доступные данные с текущей версией.
  for (int ctr = 0; ctr < 10; ++ctr) {
    v = AppendValue(v, ctr);
    if (ctr == 6) aCopyOfV = v;
  }
  // Отображаем содержимое векторов
  DisplayImmutableVector("v", v);
  DisplayImmutableVector("aCopyOfV", aCopyOfV);
}
// Вывод:
// v.Size() = 10, v[] = { 0 1 2 3 4 5 6 7 8 9 }
// aCopyOfV.Size() = 7, aCopyOfV[] = { 0 1 2 3 4 5 6 }

Рис. 9. Методы для операций с ImmutableVector

void ImmutableVectorTest2()
{
  ImmutableVector<int, 4> v;
  v = AppendValue(v, 1);
  v = AppendValue(v, 2);
  v = AppendValue(v, 3);
  int oldValue = v.Back();
  auto v1 = TruncateValue(v);
  auto v2 = SubstituteValueAtIndex(v, 0, 3);
  auto v3 = GenerateFrom(v, [](ImmutableVector<int, 4>::MutableVector& v) {
    v[0] = 4;
    v[1] = 5;
    v[2] = 6;
    v.PushBack(7);
    v.PushBack(8);
  });
  auto v4 = GenerateFrom(v3, [](ImmutableVector<int, 4>::MutableVector& v4) {
    using namespace std;
    cout << "Change v4 by calling PopBack:" << endl;
    cout << "x = v4.PopBack()" << endl;
    int x = v4.PopBack();
    cout << "x == " << x << endl;
    cout << endl;
  });
  // Отображаем содержимое векторов
  DisplayImmutableVector("v", v);
  DisplayImmutableVector("v1", v1);
  DisplayImmutableVector("v2", v2);
  DisplayImmutableVector("v3", v3);
  DisplayImmutableVector("v4", v4);
}
// Вывод:
//    Change v4 by calling PopBack:
//    x = v4.PopBack()
//    x == 8
//   
//    Resulting ImmutableVectors:
//    v.Size() = 3, v[] = { 1 2 3 }
//    v1.Size() = 2, v1[] = { 1 2 }
//    v2.Size() = 3, v2[] = { 3 2 1 }
//    v3.Size() = 5, v3[] = { 4 5 6 7 8 }
//    v4.Size() = 4, v4[] = { 4 5 6 7 }

Рис. 10. Класс Immutable в действии

using namespace std;
void Foo()
{
  // Создаем неизменяемый объект
  double d1 = 1.1;
  string s1 = "Hello World";
  Immutable a(d1, s1);
  // Создаем копию неизменяемого объекта, делаем данные общими
  Immutable b(a);
  // Создаем новый неизменяемый объект,
  // изменяя существующий неизменяемый объект
  // (возвращается новый объект)
  string s2 = "Hello Other";
  Immutable c = a.SetS(s2);
  // Отображаем содержимое каждого объекта
  cout << "a.GetD() = " << a.GetD() << ", "
    << "a.GetS() = " << a.GetS()
    << " [address = " << &(a.GetS()) << "]" << endl;
  cout << "b.GetD() = " << b.GetD() << ", "
    << "b.GetS() = " << b.GetS()
    << " [address = " << &(b.GetS()) << "]" << endl;
  cout << "c.GetD() = " << c.GetD() << ", "
    << "c.GetS() = " << c.GetS()
    << " [address = " << &(c.GetS()) << "]" << endl;
}
// Вывод:
// a.GetD() = 1.1, a.GetS() = Hello World [address = 008354BC]
// b.GetD() = 1.1, b.GetS() = Hello World [address = 008354BC]
// c.GetD() = 1.1, c.GetS() = Hello Other [address = 008355B4]

Заметьте, что объект b использует ту же строку, что и объект a (обе строки находятся по одинаковому адресу). Включение дополнительных полей с сопоставленными get- и set-аксессорами осуществляется тривиальным образом. Хотя этот код вполне хорош, его масштабирование до контейнеров немного затруднительно. Например, «наивная» реализация ImmutableVector могла бы поддерживать список общих указателей, представляющих каждый элемент массива. Если «наивный» ImmutableVector изменяется, вам придется продублировать весь массив общих указателей, что повлечет за собой дополнительные издержки, так как каждый элемент shared_ptr массива потребует увеличения своего счетчика ссылок.

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

Рис. 11. Сравнение «наивной» и «интеллектуальной» реализаций ImmutableVector

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

Я разработал «интеллектуальный» класс шаблона ImmutableVector, который можно скачать по ссылке archive.msdn.microsoft.com/mag201208CPP. На рис. 8 показано, как использовать мой класс ImmutableVector. (Как уже отмечалось, чтобы сделать неизменяемую природу ImmutableVector более понятной пользователям, в ImmutableVector применяются статические функции-члены для всех операций, вызов которых приводит к генерации новых версий.)

В случае операций только для чтения этот вектор можно использовать во многом как обычный. (Заметьте, что в этом примере я не реализовал итераторы, но сделать это несложно.) При операциях записи статические методы AppendValue и TruncateValue возвращают новый ImmutableVector, тем самым защищая исходный объект. К сожалению, это неприемлемо для оператора нижнего индекса массива (array subscript operator), поэтому я сделал его только для чтения (т. е. он возвращает постоянную ссылку) и предоставил статический метод SubstituteValueAtIndex. Однако было бы неплохо иметь возможность вносить большое количество модификаций, используя оператор нижнего индекса массива в одном блоке кода. Чтобы поспособствовать этому, ImmutableVector предоставляет статический метод GenerateFrom, принимающий лямбду (или любой другой функтор). Лямбда в свою очередь принимает ссылку на MutableVector в качестве параметра, что позволяет лямбде работать с временным MutableVector, который можно свободно изменять, как обычный std::vector. В примере на рис. 9 показаны различные методы для операций с ImmutableVector.

Изящество статического метода GenerateFrom заключается в том, что код внутри него можно писать как императивный, в то же время получая неизменяемый объект, который можно безопасно использовать как общий. Заметьте, что этот метод предотвращает неавторизованный доступ к нижележащему ImmutableVector, отключая переданный им в лямбду MutableVector, как только происходит выход из этой лямбды. Также заметьте, что, если ImmutableVector дает прочные гарантии безопасности в многопоточной среде, то его вспомогательный класс MutableVector — нет (и предназначен только для локального использования внутри лямбды, а не для передачи в другие потоки). Кроме того, моя реализация оптимизирована для нескольких изменений в рамках метода Change, чтобы добиться минимальных издержек реструктуризации временного дерева, а это дает приличную прибавку в производительности.

Заключение

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