Эффекты в Haskell

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

Для примера возьмём Haskell — чистый язык, в котором, в отличие от «нечистых» C, OCaml, JavaScript и прочих, нет никаких встроенных эффектов. (Ну, почти нет.) Однако, средствами этого языка можно построить чистые управляемые эффекты, и не хуже, чем «нечистые».

Замечание о терминах. Я позволю себе называть параметрические типы с опущенными параметрами просто типами, хотя строгий хаскелит употребил бы термин конструктор типов. Конструктор типов сам типом не является, но принадлежит языку типов. В разговорной речи и не очень строгих статьях, как эта, такая вольность вполне допустима, чтобы речь звучала не так тяжело («ехал конструктор через конструктор…»), благо, ни к каким противоречиям при программировании это не приводит. Если параметр не указан, то это конструктор типа, а если по контексту подразумевается всё-таки конкретный тип, значит, речь идёт о конструкторе с произвольными значениями параметров.

0. Отсутствие эффектов

Представим чистую функцию f :: a -> b в виде чёрного ящика:

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

Частичная функция либо возвращает результат, либо не возвращает.

Такая вариативность легко моделируется с помощью типа-суммы.

Значение типа Maybe a либо содержит значение типа a, либо нет.

Мы можем описать частичную процедуру, иногда возвращающую b, как функцию, всегда возвращающую Maybe b.

Пример.

Обратите внимание, что тип Maybe принадлежит Functor, Applicative, Monad и многим другим интересным и полезным классам.

На практике также применяется типы Either и Except, реализующие тот же эффект, но позволяющий добавить информацию о том, почему вычисление не может быть завершено.

Пример.

Можно комбинировать частичность с другими эффектами:

На самом деле частичность — единственный неуправляемый эффект, доступный в Хаскеле непосредственно. Любая функция может оказаться частичной, то есть зависнуть или выбросить исключение, по ошибке или из-за несовершенства реального мира.

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

К счастью, в Хаскеле доступна управляемая частичность, и иметь дело с неуправляемой частичностью приходится редко.

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

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

Если процедура для одного и того же значения аргумента может вернуть от раза к разу разные результаты, это значит, что на самом деле результат зависит от чего-то ещё.

Даже генератор случайных чисел (настоящий, аппаратный) — это «чистая» функция, зависящая от состояния источника энтропии.

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

Пример.

Для удобства рассуждений об эффектах удобно ввести синоним

Можно комбинировать неявную зависимость с другими эффектами:

Обратите внимание, что тип Reader r (конструктор типа Reader, частично применённый к одному аргументу) принадлежит Functor, Applicative, Monad и многим другим интересным и полезным классам.

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

Здесь всё просто и очевидно. Функция, дающая много ответов сразу — это функция, имеющая единственный ответ-множество.

В Хаскеле есть тип Set для множеств, но для моделирования эффекта множественности оказывается более удобным список — [].

Пример.

Обратите внимание, что тип [] (конструктор типа списка) принадлежит Functor, Applicative, Monad и многим другим интересным и полезным классам.

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

Таким образом, тип [] реализует и эффект частичности.

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

Побочный эффект — это просто неявный результат. Сделаем же неявное явным!

Для удобства рассуждений об эффектах удобно ввести обёртку

Обратите внимание, что тип Putter s (конструктор типа Putter, частично применённый к одному аргументу) принадлежит Functor, Applicative, Monad и многим другим интересным и полезным классам.

На практике чаще применяется тип Writer, структурно идентичный, но с более полезными свойствами: все побочные эффекты собираются в моноид.

Пример.

Можно комбинировать!

2 + 3. Эффект состояния

Если соединить результат побочного эффекта и источник нестабильности, из их комбинации (композиции) получается эффект состояния — процедура, которая может и зависеть от текущего состояния «переменной», и задавать ей новое состояние.

Проведя рассуждения, аналогичные случаям Reader и Putter, получим

Для удобства рассуждений об эффектах удобно ввести обёртку

Пример.

Комбинируем с предыдущими эффектами.

Не будет сюрпризом, что тип State s (конструктор типа State, частично применённый к одному аргументу) принадлежит Functor, Applicative, Monad и многим другим интересным и полезным классам.

0. Отсутствие эффектов (продолжение)

Рассмотрим тип

Тип Identity a полностью аналогичен типу a. То есть это своего рода функция id, только на уровне типов.

Тип Identity не может выражать никаких эффектов. С другой стороны, можно сказать, что он выражает отсутствие эффектов.

Конечно же, конструктор типа Identity принадлежит Functor, Applicative, Monad и многим другим интересным и полезным классам.

Эффекты! Эффекты повсюду!

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

Реализация IO не определена в спецификации языка. Если вы заглянете в исходники стандартной библиотеки, скорее всего, действительно увидите что-то подобное State RealWorld, но эта реализация нужна только для внутренних нужд компилятора и пропадает при компиляции, так что верить ей не стоит.

Вы уже догадались, что конструктор типа IO принадлежит Functor, Applicative, Monad и многим другим интересным и полезным классам.

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

Иными словами, IO даёт доступ к неуправляемым эффектам, но доступ к самому IO управляемый.

Процедуры и чистые функции

Вернёмся к нашей дихотомии.

С одной стороны, функция — это просто процедура без эффектов.

С другой стороны, нам удалось все процедуры выразить в типах вида

где b — тип результата, он может быть любым, f — тип, реализующий эффект.

Иными словами, процедура — это чистая функция, вычисляющая эффект.

Обратите внимание, что все упомянутые типы эффектов принадлежат Functor, Applicative, Monad и многим другим интересным и полезным классам (разве что Writer с некоторыми ограничениями). Эти классы предоставляют общий механизм для работы с эффектами. Подробнее можно почитать в www.staff.city.ac.uk/~ross/papers/Applicative.

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

Управляемые эффекты

Что даёт возможность управлять эффектами? Переводя процедуры с эффектами в пространство чистых функций, мы, не теряя выразительности, получаем возможности

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

Заключение

Соберём в таблицу аспекты чистоты, эффекты, нарушающие эти аспекты, и типы, моделирующие эти эффекты.

Свойство чистой функции Эффект Тип
Все Нет Identity
Тотальность Частичность Maybe, Either e, []
Детерминированность Нестабильность Reader r
Детерминированность Множественность []
Нет побочных эффектов Побочный Putter s, Writer w
Детерминированность и нет побочных Состояние State s
Любое Любой IO

Все упомянутые типы встроены в язык или легко находятся в стандартной библиотеке (пакеты base, mtl), кроме Putter. Putter я придумал только для иллюстрации, но его легко представить как State, ограниченный до операции put.

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