Эффекты и чистые функции
date = fromGregorian 2018 jan 10
category = "Теория"
tags = ["эффекты"]
Тезис Чёрча — Тьюринга означает (несколько упрощая), что любая компьютерная программа может быть представлена машиной Тьюринга или функцией λ-исчисления, то есть математической функцией. Конечно, это относится и к составляющим программу функциям и процедурам языков программирования.
Но что такое математическая функция?
В математике у функции, конечно, есть строгое определение, но нам сейчас оно будет не так полезно, как 3 её не менее строгих и обязательных свойства:
- Полная определённость, или тотальность: функция должна давать ответ для каждого значения аргумента.
- Детерминированность: функция должна давать одинаковые ответы для одинаковых значений аргументов, то есть если мы её вычисляем несколько раз для одного и того же значения аргумента, функция должна давать всегда один и тот же ответ.
- Отсутствие побочных эффектов. Вообще-то в книжках по математике ничего про побочные эффекты не пишут, их придумали программисты, чтобы описать «функции», выполняющие ввод-вывод и запись в ячейки памяти. Так вот, настоящие математические функции ничем подобным не занимаются.
Оказывается, в применяемых повсеместно языках программирования «функции» — хотя я предпочитаю называть их процедурами — часто не удовлетворяют одному или нескольким из этих требований, возможно, всем сразу. Те редкие, что всё-таки удовлетворяют, называются чистыми функциями.
В мире чистого программирования нарушения этих свойств принято называть эффектами.
1. Эффект частичности
Если процедура частично определена, то есть не определена для каких-либо значений аргумента, она не возвращает значения для него, или, как говорят математики, не завершается. Погодите-ка! Если она не завершается, то что происходит?
В современных языках программирования процедура может «не завершаться» разными способами:
- уснуть в бесконечном цикле,
- убить процесс,
- выбросить исключение (да, программистами это считается завершением, но для математиков такое завершение не нормально),
- передать управление другой процедуре, например, обработчику сигнала,
и т. п.
Пример: деление на 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 и других языках программирования и как же всё-таки выразить любую процедуру любого языка программирования математической функцией.