Безопасность создания вектора

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

Одним из основных способов создания Vector является использование unsafeFreeze. Как следует из его названия, unsafeFreeze действительно небезопасен. В частности, ничто не мешает MVector передавать unsafeFreeze из модификации после его замораживания. Это приводит к двум различным проблемам:

  1. Он может превращать "неизменные" векторы в стоимость. Это просто вид жуткий действия на расстоянии Хаскелл обычно избегает.

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

vector пакет [1] предлагает два эффективных, казалось бы, безопасных примитива для создания неизменяемых векторов: create and createT:

create :: (forall s. ST s (MVector s a)) -> Vector a
createT :: Traversable t => (forall s. ST s (t (MVector s a))) -> t (Vector a)

Игнорируя бизнес векторного слияния, основные реализации выглядят как

create m = runST $ m >>= unsafeFreeze
createT m = runST $ m >>= traverse unsafeFreeze

create довольно ясно безопасно. Он запускает MVector s ST s, которое должно создавать свежий MVector s (тип runST гарантирует, что он не может использовать существующий, а также гарантирует, что fixST не может играть в какие-либо смешные трюки), замораживает его и возвращает замороженный вектор.

createT довольно четко защищен, когда экземпляр Traversable является законным. Со списками, например, createT m запускает действие, производящее список MVector s, а затем замораживает их все. Параметричность в s тогда кажется достаточной, как для create, чтобы гарантировать, что ничего плохого не происходит. Обратите внимание, что действие может создать список с несколькими копиями одного и того же MVector. Они будут заморожены дважды, но в этом не должно быть никакого вреда. Законные Traversable экземпляры выглядят так же, как украшенные списки, поэтому они должны вести себя аналогичным образом. Теперь я, наконец, доберусь до первого вопроса:

createT ли createT при использовании с незаконным экземпляром Traversable?

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

Один очевидный способ обобщить createT - позволить пользователю передать свою собственную функцию обхода:

createTOf
  :: (forall f x y. Applicative f => (x -> f y) -> t x -> f (u y))
  -> (forall s. ST s (t (MVector s a))) -> u (Vector a)
createTOf trav m = runST $ m >>= trav unsafeFreeze

Обратите внимание, что я разрешил обход изменить тип контейнера от t до u. Это позволяет пользователю, например, создавать Vector (MVector sa) но возвращать [Vector a]. Когда t ~ u, это, очевидно, столь же безопасно, как createT с незаконным экземпляром Traversable. Повышает ли гибкость в изменении типа "контейнера" безопасность? Edit: Я только понял, что могу ответить на этот вопрос: нет, это не имеет значения. См. [2] ниже для объяснения.

Когда мы используем createT, нам может не понадобиться контейнер векторов; возможно, мы хотим пройти этот контейнер, чтобы получить что-то еще. Мы можем написать что-то вроде

traverse f <$> createT m

Гибкость дополнительного типа createTOf означает, что мы не обязательно имеем Traversable в наших руках и не можем это делать. Но используя закон композиции для Traversable, мы можем интегрировать этот обход в функцию создания:

createTOfThen
  :: Applicative g
  => (forall f x y. Applicative f => (x -> f y) -> t x -> f (u y))
  -> (Vector a -> g b)
  -> (forall s. ST s (t (MVector s a)))
  -> g (u b)
createTOfThen trav f m =
  runST $ m >>= getCompose . trav (Compose . fmap f . unsafeFreeze)

Является ли createTOfThen безопасным, если trav не является законным обходом?

Я сказал, что буду говорить о решетке, не так ли? Следующий вопрос: насколько (если вообще) мы можем ослабить полиморфизм обхода, не вызывая проблем. Все будет проверяться, даже если обход требуется только для того, чтобы быть полиморфным в s, но это, очевидно, небезопасно, поскольку он может чередовать замораживание с модификацией, но ему это нравится. Выяснение того, что конечный результат имеет значение Vector кажется, скорее всего, безвредным, но мы, конечно же, не можем позволить обходу знать, что он работает в ST s и что он обрабатывает значения MVector sa. Но можем ли мы сообщить об этом одному из этих фактов? Исправление Applicative вопроса, безусловно, было бы полезно:

createTOf'
  :: (forall s x y. (x -> ST s y) -> t x -> ST s (u y))
  -> (forall s. ST s (t (MVector s a))) -> u (Vector a)

createTOfThen'
  :: Applicative g
  => (forall s x y. (x -> Compose (ST s) g y) -> t x -> Compose (ST s) g (u y))
  -> (Vector a -> g b)
  -> (forall s. ST s (t (MVector s a)))
  -> g (u b)

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

С другой стороны, я подозреваю, что мы можем позволить MVector знать, что он обрабатывает MVector... пока мы не даем ему знать, с какой государственной нитью они связаны. Этого достаточно, чтобы удалить их, а также (возможно, к сожалению) получить их размеры.

Редактировать! Если обход позволяет узнать, что он создает Vector (который кажется очень проблематичным, createTOfThen может быть очень проблематичным), тогда createTOfThen может быть реализовано с точки зрения createTOf:

createTOfThen trav post m = getConst $
  createTOf (\f ->
    fmap Const . getCompose . (trav (Compose . fmap post . f))) m

Возьмем решетку в третьем направлении, перейдем к обходам ранга 2. Пакет rank2classes предлагает собственный класс Traversable, который я буду называть R2.Traversable:

class (R2.Functor g, R2.Foldable g) => R2.Traversable g where
  R2.traverse :: Applicative m
              => (forall a. p a -> m (q a))
              -> g p -> m (g q)

Мы можем играть точно в те же игры с этим, чтобы создать гетерогенные контейнеры Vector s:

createTHet
  :: R2.Traversable t
  => (forall s. ST s (t (MVector s)))
  -> t Vector
createTHet m = runST $ m >>= R2.traverse unsafeFreeze

createTHetOf
  :: (forall h f g.
       (Applicative h => (forall x. f x -> h (g x)) -> t f -> h (u g)))
  -> (forall s. ST s (t (MVector s)))
  -> u Vector
createTHetOf trav m = runST $ m >>= trav unsafeFreeze

createTHetOfThen
  :: Applicative q
  => (forall h f g.
       (Applicative h => (forall x. f x -> h (g x)) -> t f -> h (u g)))
  -> (forall x. Vector x -> q (r x))
  -> (forall s. ST s (t (MVector s)))
  -> q (u r)
createTHetOfThen trav post m =
    runST $ m >>= getCompose . trav (Compose . fmap post . unsafeFreeze)

наряду с аналогичными версиями, где обход позволяет узнать, что он работает в ST s. Я бы предположил, что защитные свойства версий ранга-2 идентичны тем, что соответствуют версиям ранга-1, но я не знаю, как это можно доказать.

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

createTHetOfThen'
  :: (forall s1 s2.
       ((forall x. MVector s2 x -> Compose (ST s1) q (r x)) -> t (MVector s2) -> Compose (ST s1) q (u r)))
  -> (forall x. Vector x -> q (r x))
  -> (forall s. ST s (t (MVector s)))
  -> q (u r)
createTHetOfThen' trav post m =
    runST $ m >>= getCompose . trav (Compose . fmap post . unsafeFreeze)

[1] Я связался со Stackage, потому что Hackage сегодня не работает. Если я помню и у меня есть время, я исправлю ссылки позже.

[2] Доказательство Data.Functor.Sum из Data.Functor.Sum. Учитывая не изменяющий тип createTOfSame, мы можем написать

createTOf
  :: (forall f a b. Applicative f => (a -> f b) -> t a -> f (u b))
  -> (forall s. ST s (t (MVector s a)))
  -> u (Vector a)
createTOf trav m =
  case createTOfSame (\f (InL xs) -> InR <$> trav f xs)
                     (InL <$> m) of
    InR u -> u

Это будет фактически тотально, хотя "обход" является частичным: мы всегда встречаем случай с тем, что мы обязательно найдем.

Ответы

Ответ 1

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

createTOf
  :: (forall s1 s2.
       (MVector s1 a -> ST s2 (Vector a))
       -> t (MVector s1 a) -> ST s2 (u (Vector a)))
  -> (forall s. ST s (t (MVector s a)))
  -> u (Vector a)
createTOf trav m = runST $ m >>= trav unsafeFreeze

Это, конечно, довольно многообразная подпись! Позвольте сосредоточиться на те свойства безопасности, о которых мы заботимся: ни один MVector не мутируется после его замораживания. Первое, что мы делаем, это запустить m для создания чего-то типа t (MVector sa).

t сейчас очень загадочно. Это контейнер? Это какое-то действие, которое производит векторы? Мы не можем действительно сказать ужасно о том, что это такое, но мы можем сказать некоторые вещи о том, что trav unsafeFreeze не может с этим поделать. Пусть начнется с разбивки сигнатуры типа trav:

trav :: forall s1 s2.
        (MVector s1 a -> ST s2 (Vector a))
     -> t (MVector s1 a) -> ST s2 (u (Vector a)))

trav превращает t (MVector s1 a) в ST s2 (u (Vector a)). Если t имеет в нем векторы, то эти векторы живут в потоке состояний s1. Результатом, однако, является действие в потоке состояния s2. Таким образом, trav не может изменять MVector заданный с помощью обычных операций. Он может применять только unsafeFreeze функцию (которая будет unsafeFreeze), и использовать любое оборудование может ездить на t. Какая машина могла ездить на t? Ну, вот глупый пример:

data T :: Type -> Type where
  T :: [ST s (MVector s a)] -> t (MVector s a)

Может ли trav чередовать эти действия ST с помощью замораживания? Нет! Эти действия ST соответствуют MVector s, но они не соответствуют MVector состояния, в котором работает trav. Таким образом, trav ничего не может с ними поделать.