Учитывая глубокое внедрение простой DSL обработки данных [1]:
{-# LANGUAGE GADTs, StandaloneDeriving #-}
import Data.List
import Text.Show.Functions
data Dist e where
Concat :: [Dist [a]] -> Dist [a]
-- We use ConcatMap as a primitive because it can express e.g.
-- both map and filter.
ConcatMap :: (a -> [b]) -> Dist [a] -> Dist [b]
-- Expensive to traverse input (think distributed file).
Input :: Dist [a]
Let :: Name -> Dist e -> Dist e -> Dist e
-- We're not dealing with name collisions here for simplicity.
Var :: Name -> Dist e
deriving instance Show (Dist e)
type Name = String
мы можем реализовать знакомый синтез-производитель-потребитель так
-- ---------------------------------------------------------------------
-- Producer-consumer fusion
-- Fuses adjacent ConcatMaps.
fuseProducerConsumer :: Dist e -> Dist e
fuseProducerConsumer = go
where
go :: Dist e -> Dist e
go (ConcatMap f (ConcatMap g e)) = ConcatMap (concatMap f . g) (go e)
go e = e
Небольшой пример, показывающий, как это работает:
-- Should be able to fuse this to a single ConcatMap.
producerConsumerFusable :: Dist [Int]
producerConsumerFusable = ConcatMap (singleton . (+ 1))
(ConcatMap (singleton . (* 2)) Input)
singleton :: a -> [a]
singleton = (: [])
-- Expected result after optimization.
expectedProducerConsumerResult =
ConcatMap (concatMap (singleton . (+ 1)) . (singleton . (* 2))) Input
Там другой, гораздо менее известный [2], тип слияния, называемый sibling fusion, который удаляет множественные обходы одного и того же входа. Идея состоит в том, чтобы заменить что-то вроде
(map f xs, map g xs)
с
let ys = map (\ x -> (f x, g x)) xs
in (map fst ys, map snd ys)
Если перемещение ys намного дешевле, чем перемещение xs (например, если xs является файлом в сети), или если мы можем, например, используйте слияние производителей-потребителей, чтобы позже сливать немаркировку с каким-либо другим обходом, это победа.
В то время как слияние производителей и потребителей легко реализуется с использованием нашего стандарта AST выше, я не вижу, как реализовать слияние с братом, используя это представление.
-- ---------------------------------------------------------------------
-- Sibling fusion
-- Fuses ConcatMaps that consumer the same input.
fuseSibling :: Dist e -> Dist e
fuseSibling = id -- ???
Пример того, что мы хотим:
-- The use of Concat below is not important, we just need some Dist e
-- that contains an opportunity for sibling fusion.
siblingFusable :: Dist [Int]
siblingFusable = Let "xs" Input $ -- shares one input
Concat [ConcatMap (singleton . (+ 1)) (Var "xs"),
ConcatMap (singleton . (* 2)) (Var "xs")]
-- Expected result after optimization.
expectedSiblingResult =
Let "xs" Input $
(Let "ys" (ConcatMap
(mapTwo (singleton . (+ 1)) (singleton . (* 2)))
(Var "xs")) -- only one traversal of "xs" and thus Input
(Concat [ConcatMap lefts (Var "ys"),
ConcatMap rights (Var "ys")]))
-- Some helper functions:
lefts :: Either a b -> [a]
lefts (Left x) = [x]
lefts _ = []
rights :: Either a b -> [b]
rights (Right x) = [x]
rights _ = []
mapTwo :: (a -> [b]) -> (a -> [c]) -> a -> [Either b c]
mapTwo f g x = map Left (f x) ++ map Right (g x)
Проблема заключается в том, что, хотя мы можем легко выявить возможности слияния производителей-производителей путем сопоставления шаблонов на ConcatMap ... (ConcatMap ... ...), два потребителя одного входа, которые приводят к возможности совместного использования брака, не обязательно "близки" друг к другу в AST таким же образом.
Если бы мы могли пройти АСТ в противоположном направлении, то есть, начиная с Input s, было бы легче обнаружить параллельных потребителей одного входа. Я не могу понять, как это сделать, однако, учитывая, что каждая операция относится только к ее вводу, а не к выходным файлам.
Вопрос: Может ли слияние слияния быть реализовано с использованием этого представления AST или есть какое-то другое (например, графическое или продолжение) представление, которое позволило бы нам реализовать sibling fusion? Предпочтительно, при использовании GADT для безопасности типов.
- Этот DSL похож на DSL FlumeJava для распределенных вычислений: http://pages.cs.wisc.edu/~akella/CS838/F12/838-CloudPapers/FlumeJava.pdf
- Это, вероятно, менее известно, потому что это явно не выигрыш в отдельных процессах, где дополнительная бухгалтерия может перевесить затраты на предотвращение перебора ввода. Однако, если вы вводите файл 1TB, находящийся в сети, это может быть очень большой победой.
