Когда использовать CPS против четкости и отражения без угрызений совести в Haskell

Есть ли какие-либо эмпирические правила о том, когда при создании монад в Haskell можно использовать стиль продолжения-прохождение против против без сожаления.

В качестве примера я собираюсь использовать простую coroutine monad. Если вы никогда не видели этого раньше, вы можете проверить статью "Трубы Coroutine" в Monad.Reader Issue 19 или pipes. Полный код для следующих примеров можно найти в этом репозитории.

  • Normal

    Это обычная монада, определяемая как тип данных:

    data FooM i o a
  = Await (i -> FooM i o a)
  | Yield o (FooM i o a)
  | Done a

    Этот стиль широко используется в экосистеме Хаскелла. Одним из примеров этого стиля является Proxy тип данных из pipes.

  • Стиль продолжения-передачи (CPS)

    Это похоже на стиль обычный, но каждый конструктор данных стал аргументом для продолжения:

    newtype FooCPS i o a = FooCPS
  { runFooCPS
      :: forall r.
         ((i -> FooCPS i o a) -> r)
      -> (o -> FooCPS i o a -> r)
      -> (a -> r)
      -> r
  }

    Этот стиль используется как в attoparsec, так и parsec.

  • Codensity

    В этом стиле используется трансформатор монотонности конвертации, обернутый вокруг монады, определенной в стиле обычный. Это дает O (1) лево-ассоциативное связывание.

    Трансформатор монодальности с кодировкой выглядит следующим образом:

    newtype Codensity m a = Codensity
  { runCodensity :: forall b. (a -> m b) -> m b
  }

    Наша настоящая монада может быть определена как новый тип с использованием трансформатора Codensity. Обратите внимание, что FooCodensity использует FooM внутренне.

    newtype FooCodensity i o a = FooCodensity
  { runFooCodensity :: Codensity (FooM i o) a
  }

    Этот стиль используется conduit в ConduitM.

  • Отражение без сожаления

    Это стиль, обсуждаемый в статье Отражение без сожаления.

    Это похоже на стиль обычный, но рекурсивные вызовы стали структурой данных с O (1) добавлением и амортизацией O (1) uncons. Это дает O (1) лево-ассоциативное связывание и монадическое отражение в монаде FooRWR:

    data FooRWR i o a
  = AwaitRWR (forall x. i -> FooExplicit i o x a)
  | YieldRWR  o (forall x. FooExplicit i o x a)
  | DoneRWR a

    Тип FooExplicit определяется как:

    type FooExplicit i o = FTCQueue (FooRWR i o)

    FTCQueue представляет собой структуру данных с O (1) добавлением и амортизацией O (1) uncons.

    Этот стиль используется freer-effects и extensible. Он доступен как автономная библиотека в monad-skeleton.

Когда следует использовать нормальный vs CPS vs плотность против отражения без раскаяния? Я предполагаю, что жесткий и быстрый ответ потребует бенчмаркинга данной монады и приложения, но существуют ли какие-либо эмпирические правила?

Из моих собственных исследований я встретил следующие идеи/комментарии:

  • CPS может быть быстрее, чем стиль обычный, потому что вам может не потребоваться анализ case. Хотя фактическое ускорение может варьироваться в зависимости от того, как код компилируется GHC. Codensity и отражение без раскаяния имеют некоторые накладные расходы.

    Габриэль Гонсалес (автор pipes) пишет о том, как он придерживается стиля обычного для pipes в this reddit thread и issue в Github.

    Брайан О'Салливан (автор attoparsec) пишет, что изменение attoparsec от обычного до CPS дало коэффициент 8 ускорения. В некоторых комментариях к этому сообщению также говорится о нормальном стиле vs CPS.

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

    Вот пример из статьи "Reflection without Remorse", которая будет демонстрировать квадратичное время выполнения.

    data It i a = Get (i -> It i a) | Done a

sumInput :: Int -> It Int Int
sumInput n = Get (foldl (>=>) return (replicate (n - 1) f))
  where
    f x = get >>= return . (+ x)

    Если sumInput переписывается с четкостью или отражением без раскаяния, он будет работать очень быстро.

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

    Майкл Снойман (автор conduit) рассказывает об этом в сообщении в блоге о ускорении conduit.

    Библиотека pipes используется для обеспечения трансформатора плотности.

  • CPS и . не поддерживают O (1) отражение.

    Вот функция, которая требует монадического отражения. Этот пример адаптирован из документа "Reflection without Remorse":

    data It i a = Get (i -> It i a) | Done a

par :: It i a -> It i b -> It i (It i a, It i b)
par l r
  | Done <- l = Done (l, r)
  | Done <- r = Done (l, r)
  | Get f <- l, Get g <- r = Get Done >>= \x -> par (f x) (g x)

    Этот метод не может быть записан в стиле CPS или с четностью без предварительного преобразования в стиль обычный. Стиль отражения без сожаления не имеет этой проблемы.

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

  • Отражение без раскаяния добавляет некоторые служебные данные, но это единственный стиль, который дает как лево-ассоциативную привязку, так и отражение O (1).

бонусный вопрос: аналогичный вопрос можно задать о Free (обычный) vs F ( CPS) из free. Когда следует использовать Free? Когда следует использовать F?

Ответы

Ответ 1

Эта проблема может быть разбита на две части, как вы представляете тип данных и как их составлять вместе.

Типы данных

В приведенных вами стилях используются только 2 типа типов данных, "нормальный" стиль и стиль продолжения прохождения. Они отличаются тем, что объекты выбраны в качестве примитивов языка.

В стандартном стиле типы данных и их конструкторы выбираются как примитивные. Типы данных представляют собой суммы (имеющие несколько конструкторов) продуктов (имеющих несколько значений)

data Sum a b = Left a | Right b
data Product a b = Product a b

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

either :: (a -> c) -> (b -> c) -> Sum a b -> c
either l _ (Left a)  = l a
either _ r (Right b) = r b

uncurry :: (a -> b -> c) -> Product a b -> c
uncurry f (Product a b) = f a b

Вы можете создать эквивалентный язык, где универсально квантифицированные типы рассматриваются как примитивные, а не типы данных. В этом случае вы можете определить типы данных с точки зрения универсальной квантификации. Суммы представлены их функцией either, универсально определенной по типу возврата. Продукты представлены их функцией uncurry, универсально определенной по типу возврата. Необходимость расширения языка (RankNTypes) для представления типов данных таким образом подсказывает, почему вы назвали бы первый стиль "нормальным".

{-# LANGUAGE RankNTypes #-}

newtype Product a b = Product (forall r. (a -> b -> r) -> r)

product :: a -> b -> Product a b
product a b = Product (\f -> f a b)

uncurry :: (a -> b -> c) -> Product a b -> c
uncurry both (Product f) = f both

newtype Sum a b = Sum (forall r. (a -> r) -> (b -> r) -> r)

left :: a -> Sum a b
left a = Sum (\l r -> l a)

right :: b -> Sum a b
right b = Sum (\l r -> r b)

either :: (a -> c) -> (b -> c) -> Sum a b -> c
either l r (Sum f) = f l r

Это приводит к одному из основных различий между двумя стилями. В универсально-количественном стиле нет конструкторов. Вся структура данных должна храниться в замыканиях на функции, и именно там помещаются замены для конструкторов left, right и product. В универсально-количественном стиле вы не можете создавать ненужные промежуточные объекты; для вас нет объекта. Вы все равно можете построить ненужные промежуточные блокировки. По крайней мере, вы обманете профайлера, сообщив вам, что у вас нет кучи предметов, висящих вокруг.

Ваш тип данных FooM, повторяемый здесь, также может быть представлен в стиле продолжения передачи.

data FooM i o a
  = Await (i -> FooM i o a)
  | Yield o (FooM i o a)
  | Done a

Он будет представлен функцией matchFoo, которую я определил.

matchFoo :: ((i -> FooM i o a) -> r) -> (o -> FooM i o a -> r) -> (a -> r) -> r
matchFoo a _ _ (Await f) = a f
matchFoo _ y _ (Yield o next) = y o next
matchFoo _ _ d (Done a) = d a

Универсально квантифицированный FooM идентифицирует a FooM с его функцией matchFoo, универсальной над его возвращаемым типом.

newtype FooCPS i o a = FooCPS
  { runFooCPS
      :: forall r.
         ((i -> FooCPS i o a) -> r)
      -> (o -> FooCPS i o a -> r)
      -> (a -> r)
      -> r
  }

await :: (i -> FooCPS i o a) -> FooCPS i o a
await f = FooCPS (\a _ _ -> a f)

yield :: o -> FooCPS i o a -> FooCPS i o a
yield o next = FooCPS (\_ y _ -> y o next)

done :: a -> FooCPS i o a
done a = FooCPS (\_ _ d -> d a)

Нарушение проблемы в 2

Чтобы использовать тот же тип данных для всех способов их компоновки, мы заменим FooM его базовым функтором. Базовый функтор - это нормальный тип данных с заменой рекурсий на переменную типа.

data FooF i o a next
  = Await (i -> next)
  | Yield o next
  | Done a
    deriving (Functor)

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

newtype FooFCPS i o a next = FooFCPS
  { runFooCPS
      :: forall r.
         ((i -> next) -> r)
      -> (o -> next -> r)
      -> (a -> r)
      -> r
  }
  deriving (Functor)

Сопоставление их обратно вместе

  • Normal

Мы можем немедленно восстановить FooM, определив

newtype FooM i o a = FooM (FooF i o a (FooM i o a))

Если вы уже определили неподвижную точку функтора:

newtype Fix f = Fix (f (Fix f))

Тогда FooM может быть восстановлен на

newtype FooM i o a = FooM (Fix (FooF i o a))
  1. Стиль перехода к продолжению

Стиль прохождения продолжения может быть немедленно восстановлен из универсально квантифицированного FooFCPS

newtype FooCPS i o a = FooCPS (Fix (FooFCPS i o a))
  1. Codensity

Трансформатор плотности работает с FooM или FooCPS.

  1. Отражение без сожаления

Мы можем определить отражение без раскаяния в терминах базовых функторов без воспроизведения типа данных FooM в FooRWR.

newtype RWR f a = RWR { runRWR :: f (RWRExplicit f a) }

newtype RWRExplicit f a = RWRExplicit (forall x. FTCQueue (RWR f) x a)

И затем восстановите FooRWR с помощью

newtype FooRWR i o a = FooRWR {runFooRWR :: RWR (FooF i o a) a}

Бонусные наблюдения

Free

Оба Free и F будут работать с любым из базовых функторов FooF или FooFCPS.

Monad Transformers

Базовый функтор также может использоваться для создания монадного трансформатора. Там подробное обсуждение построения трансформатора MachineT (которое тесно связано с FooM) в этом вопросе и ответе.

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