Чистые функции в D

Andrei Alexandrescu, автор "Современного программирования на C++" опубликовал слайды о возможности интеграции функционального и императивного подходов в языке D: Grafting Functional Support on Top of an Imperative Language

Материал показался мне настолько важным, что я перевел большую часть текста на русский язык. Перевод довольно-таки вольный, хотя я постарался сохранить структуру в виде слайдов. Есть определенные терминологические трудности, например я не нашел эквивалента слову memory-safe, хорошо бы что-то вроде type-safe – типобезопасный, а impure function – нечистая функция? Прямо мистика какая-то:)

Краткий обзор D 2.0.:

• язык программирования системного уровня;
• модель памяти подобна языку C (основана на указателях);
• также удобен как скриптовый язык;
• имеет безопасный для памяти строгий проверяемый подъязык;
• мощная реализация обобщенного программирования;
• на сегодня предлагает чистый функциональный подъязык.

Основные преимущества функционального программирования (ФП):

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

Почему ФП сложно:

• нет изменяемых состояний;
• нет побочных эффектов;
• нет порядка выполнения команд.

Основные преимущества императивного программирования:

• наличие состояний облегчает разработку многих приложений: базы данных…;
• многие существующие алгоритмы сформулированы в терминах состояний;
• побочные эффекты могут быть полезны: ввод/вывод, файлы, сеть;
• я знаю, что ФП позволяет реализовать всё;
• только замечу, что Некоторые Нехорошие Люди заявляют, что изменяемые состояния проще и легче для некоторых задач.

Как должно быть реализовано объединение обоих подходов:

• идеальный язык должен позволить использовать ФП, где это удобно, и программировать императивно в остальных случаях;
• соотношение использования подходов должно контролироваться программистом;
• правила языка должны не позволять бессмысленного или опасного смешения подходов;
• в D 2.0. реализовано такое объединение.

Проблемы объединения подходов:

• что даст уверенность, что процедурная часть не изменяет данные в функциональной?
• полная изоляция не является решением, т.к. нам нужна возможность коммуникации между двумя сферами кода;
• копирование данных не решает всех проблем, т.к. существуют различные способы косвенного обращения к данным;
• что даст уверенность, что ФП-функция никогда не вызовет не !ФП-функция, которая может иметь побочные эффекты?
• что даст уверенность, что !ФП-поток не изменит состояния ФП-функции?
• как проверять типы в ФП-функциях? где минимальные ограничения?

Неизменяемы данные
Было бы неплохой идеей использовать C++-подобные const:

• использовать const для всех ФП-данных;
• избирательно использовать не-const данные в остальных случаях;
• модификатор const считать частью типа, что не даст его забыть;
• не позволять изменять const-данные.

Но это не будет работать, поскольку:

• const ограничен:

struct Node { int value; Node* next; ... }

 const Node* n1 = new Node;
 Node* n2 = n1.next; // нормально

• хотелось бы, чтобы все доступное через const Node было const;
• ФП-функция не может получить доступ к данным, при условии, что они могут быть изменены.

• const защищает данные только от прямого воздействия:
• данные с косвенным доступом остаются изменяемыми.

Транзитивность в const-функциях:

 class Node {
  Node* next_;
 public:
  Node* next() { return next_; }
  const Node* next() const
  { return next_; }
  }

Написанные вручную контракты статически не проверяемы.

Определение транзитивного const:

• конструктор типа, запись: invariant(T);
• правило 0: запрещено присваивать к invariant(T);
• правило 1: если T.field имеет тип U, то invariant(T).field имеет тип invariant(U);
• правило 2: invariant(invariant(T)) ≡ invariant(T);
• правило 3: T неявно конвертируется из и в invariant(T), если T ссылается на неизменяемую память.

Например,

 struct Node { int value; Node* next; ... }
 invariant(Node)* n1 = new invariant(Node);
 Node* n2 = n1.next; // ошибка!
 invariant(Node)* n3 = n1.next; // нормально
 invariant(int) x = n1.value; // нормально
 int y = n1.value; // нормально потому что
 // int не ссылка

Проблема выразительности:

 void print(invariant(Node)* n);
 Node* n = new Node;
 print(n); // ошибка!

invariant слишком строго; как определить функцию печати invariant и изменяемых данных? необходимо дублировать тело функции print или использовать преобразование типов.

Определение const как посредника:

• конструктор типа, запись: const(T);
• правило 0: запрещено присваивать к const(T);
• правило 1: если T.field имеет тип U, то const(T).field имеет тип const(U);
• правило 2: const(const(T)) ≡ const(T);
• правило 3: T и invariant(T) неявно конвертируется в const(T).

Может возникнуть проблема сложных типов:

const(invariant(const(…T …)))

Решение:
invariant(const(T)) ≡ invariant(T)
const(invariant(T)) ≡ invariant(T)

Интуитивно:

• const(T) x: я не могу изменять x, и ничего, что достижимо через x;
• invariant(T) x: никто не может изменять x, и ничего, что достижимо через x;
• invariant удобно для ФП-кода;
• отсутствие модификаторов удобно для !ФП-кода;
• const удобный посредник между обоими типами кода!

Инициализация данных, типа invariant:

• при создании, все поля должны быть определены;
• присваиваемые значения могут быть изменяемы!

 Node.this() invariant {
 value = 0;
 global = &next;
 }

Чистые функции

Неизменяемых данных недостаточно, необходимы синтаксические различия:

 int fun(invariant(Node) n) pure {
 ...
 }

Определение чистой функции (попытка 1):

• запрещает вызовы всех не чистых функций;
• запрещает доступ ко всем не-invariant-данным;
• по определениям invariant и pure можно заключить, что результат зависит только от аргумента.

 int foonctional(invariant(Node) n) pure {
 static int i = 42; // ошибка!
 writeln(++i); // ошибка!
 return n.value + i; // ошибка!
 }

 int foonctional(invariant(Node) n) pure {
 invariant(int) i = 42; // нормально
 writeln(i); // ошибка!
 return n.value + i; // нормально
 }

Не необходимые ограничения:

 int fun(invariant(Node) n) pure {
 int i = 42; // ошибка?
 if (n.value) ++i; // ошибка?
 return n.value + i; // ошибка?
 }

Почему необходимо запрещать изменения автоматических переменных, если это не влияет на результат?

Определение чистой функции (попытка 2):

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