Эффекты в Haskell

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

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

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

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

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

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

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

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

data Maybe a = Nothing | Just a

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

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

p :: a -> Maybe b

Пример.

headM :: [a] -> Maybe a
headM []    = Nothing -- невозможно взять голову пустого списка
headM (x:_) = Just x  -- голова непустого списка — вот она!

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

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

Пример.

data Either a b
    = Left a  -- условно ошибка
    | Right b -- условно успех

data MyError = EmptyList

headE :: [a] -> Either MyError a
headE []    = Left EmptyList
headE (x:_) = Right x

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

headE
    :: MonadError MyError m -- 'm' поддерживает эффект "ошибки"
    => [a] -> m a
headE (x:_) = pure x
headE []    =
    throwError EmptyList -- эффект ошибки, прекращение дальнейших вычислений

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

-- простейший бесконечный цикл
x = x -- вычисление 'x' приводит к вычислению 'x', снова и снова

-- не столь тривиальный пример зависания
n = length $ takeWhile (< 10) [2, 1 ..]

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

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

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

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

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

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

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

p :: a -> r -> b

Пример.

getDataDir :: Config -> FilePath
getDataDir Config{dataDir} = dataDir

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

type Reader r b = r -> b
p :: a -> Reader r b

-- процедура, читающая неявное значение и возвращающая его
ask :: Reader r r
ask = id

getDataDir :: Reader Config FilePath
getDataDir = do
    Config{dataDir} <- ask -- читаем конфиг, переданный неявно
    pure dataDir

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

data MyError = DataDirNotSpecified

getDataDir
    :: ( MonadError MyError m
       , MonadReader Config m
         -- 'm' поддерживает эффект неявной зависимости от 'Config'
       )
    => m FilePath
getDataDir = do
    Config{mDataDir} <- ask -- читаем конфиг, переданный неявно
    case mDataDir of
        Nothing      -> throwError DataDirNotSpecified
        Just dataDir -> pure dataDir

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

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

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

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

p :: a -> [b]

Пример.

rollADie :: Int -> [Int]
rollADie n = [1..n]

rollTwoDiceAndSum :: Int -> [Int]
rollTwoDiceAndSum n = do
    a <- rollADie n
    b <- rollADie n
    pure $ a + b

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

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

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

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

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

p :: a -> (b, s)

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

newtype Putter s b = Putter (b, s)
p :: a -> Putter s b

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

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

Пример.

-- процедура, откладывающая побочное значение
tell :: w -> Writer w ()
tell w = Writer ((), w)

-- процедура с побочным эффектом журналирования
sumWithLog :: Int -> Int -> Writer String Int
sumWithLog x y = do
    tell $ "sum: x = " ++ show x ++ "\n" -- запишем в лог аргументы процедуры
    tell $ "sum: y = " ++ show y ++ "\n"
    let result = x + y
    tell $ "sum: result = " ++ show result ++ "\n" -- и результат запишем
    pure r

-- функция склейки процедур, спрятанная в do-синтаксисе
-- тут-то и происходит сборка моноида
(>>) :: Monoid w => Writer w a -> Writer w b -> Writer w b
Writer (_, w1) >> Writer (b, w2) = Writer (b, w1 <> w2)

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

data MyError = DataDirNotSpecified
type AccessCounter = Sum Int

-- процедура с побочным эффектом подсчёта количества вызовов
getDataDir
    :: ( MonadError MyError m
       , MonadReader Config m
       , MonadWriter AccessCounter m
         -- 'm' поддерживает побочный эффект счётчика
       )
    => m FilePath
getDataDir = do
    tell 1 -- добавить 1 ко счётчику обращений
    Config{mDataDir} <- ask
    case mDataDir of
        Nothing      -> throwError DataDirNotSpecified
        Just dataDir -> pure dataDir

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

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

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

p :: a -> s -> (b, s)

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

newtype State s b = State (s -> (b, s))
p :: a -> State s b

Пример.

-- получить значение внутренней переменной
get :: State a a
get = State $ \s -> -- старое значение
    ( s -- результат
    , s -- новое значение переменной совпадает со старым
    )

-- присвоить значение внутренней переменной
put :: a -> State a ()
put s = State $ \_ -> -- старое значение игнорируем
    ( () -- результат
    , s -- новое значение переменной
    )

-- изменить значение внутренней переменной
modify :: (a -> a) -> State a ()
modify f = State $ \s -> -- старое значение
    ( () -- результат
    , f s -- новое значение переменной
    )

-- процедура-генератор псевдослучайных чисел по простейшей формуле
prng
    :: State
        Int -- тип внутренней переменной
        Int -- тип результата
prng = do
    modify $ \s -> s * 23 + 97
    get

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

type Storage = Map FilePath Value -- имитация файловой системы для демонстрации

-- процедура с побочным эффектом подсчёта количества вызовов
putData
    :: ( MonadError MyError m
       , MonadReader Config m
       , MonadWriter AccessCounter m
       , MonadState Storage m -- 'm' поддерживает эффект изменения 'Storage'
       )
    => m FilePath
putData key value = do
    dataDir <- getDataDir
    modify $ Map.insert (dataDir </> key) value -- вносим изменения в Storage

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

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

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

newtype Identity a = Identity a

Тип 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 управляемый.

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

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

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

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

p :: a -> f b

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

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

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

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

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

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

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

Заключение

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

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

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