Эффекты и чистые функции

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

Но что такое математическая функция?

В математике у функции, конечно, есть строгое определение, но нам сейчас оно будет не так полезно, как 3 её не менее строгих и обязательных свойства:

  1. Полная определённость, или тотальность: функция должна давать ответ для каждого значения аргумента.
  2. Детерминированность: функция должна давать одинаковые ответы для одинаковых значений аргументов, то есть если мы её вычисляем несколько раз для одного и того же значения аргумента, функция должна давать всегде один и тот же ответ.
  3. Отсутствие побочных эффектов. Вообще-то в книжках по математике ничего про побочные эффекты не пишут, их придумали программисты, чтобы описать «функции», выполняющие ввод-вывод и запись в ячейки памяти. Так вот, настоящие математические функции ничем подобным не занимаются.

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

В мире чистого программирования нарушения этих свойств принято называть эффектами.

1. Эффект частичности

Если процедура частично определена, то есть не определена для каких-либо значений аргумента, она не возвращает значения для него, или, как говорят математики, не завершается. Погодите-ка! Если она не завершается, то что происходит?

В современных языках программирования процедура может «не завершаться» разными способами:

  1. уснуть в бесконечном цикле,
  2. убить процесс,
  3. выбросить исключение (да, программистами это считается завершением, но для математиков такое завершение не нормально),
  4. передать управление другой процедуре, например, обработчику сигнала,

и т. п.

Пример: деление на 0 не определено. Математики легко обходят эту проблему. Они просто говорят, что функция \(\frac 1 x\) определена на множестве чисел без 0. В языках программирования, где нет соответствующего типа, \(\frac 1 0\) может убить всю программу или бросить исключение.

2. Эффекты недетерменированности (неопределённости)

2.1. Эффект нестабильности

Функция не всегда возвращает одинаковые значения для одного значения аргумента.

Пример: генератор случайных чисел.

2.2. Эффект множественности

Функция возвращает сразу много ответов.

Пример: «чистый» арксинус arcsin, возвращающий число только в диапазоне \(\left[ - \frac \pi 2; \frac \pi 2 \right]\), и «неопределённый» Arcsin, дающий бесконечно много значений — все, для которых \(\sin \alpha = x\). В программировании такие штуки встречаются редко.

Множественная функция может вернуть и пустое множество результатов, то есть эффект частичности можно рассматривать как частный случай эффекта множественности.

3. Побочный эффект

Любой результат функции, который можно наблюдать, кроме возвращённого значения.

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

Примеры вы сами можете легко привести.

(Иногда говорят об идемпотентных побочных эффектах. Это, несомненно, меньшее зло, чем произвольные побочные эффекты.)

Заключение

Мы рассмотрели основные виды эффектов в математике и программировании.

Свойство чистой функции Эффект
Тотальность Частичность
Детерминированность Нестабильность, Множественность
Нет побочных эффектов Побочный

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