SegmentedScanVectorMachine.hs

{-# LANGUAGE TypeFamilies, FlexibleInstances, MultiParamTypeClasses #-}

-- | An instance of @SegmentedScanVectorMachine@ provides a scalar
--   type @s@, a vector type @v@, and a segmented vector
--   (vector-of-vectors) type @v'@ such that @v@ implements the SVM
--   operations over @s@ /and/ @v'@ implements the SVM operations over
--   @v s@.
--
--   This file contains a default instance for @ScanVectorMachine V' (V S)@,
--   given an instance @ScanVectorMachine V S@.  In other words, given an
--   implementation of vectors-of-scalars, this will produce an
--   implementation of vectors-of-vectors-of-scalars.
--
--   This new type @V'@ provides SVM operations over
--   vectors-of-vectors-of-scalars; from the perspective of @V'@, the
--   vectors-of-scalars are called /segments/.  Notice that @V'@ uses
--   vectors-of-scalars wherever ordinary scalars were previously
--   used.  For example, when the /length/ operation is applied to a
--   vector-of-vectors the result is not a scalar, but rather a
--   vector-of-scalars giving the lengths of each of the segments.
--   This phenomenon is crucial to the replication theorem and
--   flattening transformation.
--
--   It turns out that @V'@ is basically @(,)@ -- but this is not
--   exposed to the user.  Blelloch outlines three encodings (figure
--   4.2): head-flags, length, and head-pointer.  The implementation
--   below uses the /length/ style since it can represent zero-length
--   vectors efficiently.
--
--   It is sometimes advantageous for hardware/platform providers to
--   implement vectors-of-vectors-of-scalars directly (see
--   @NestedVectors.hs@ for the reasoning).  To do this, implement the
--   class @SegmentedScanVectorMachine@ below.

module Control.Parallel.SegmentedScanVectorMachine(SegmentedScanVectorMachine) where
import Control.Parallel.ScanVectorMachine as SVM

-- sanity check that the two vectors have identical segment descriptors; if not, raise an error
check_eq a b = a  -- FIXME: implement; for now we just trust the user

class (SVM.ScanVectorMachine v s,
       SVM.ScanVectorMachine v' (v' (v s))) =>
       SegmentedScanVectorMachine v' v s

-- private; isomorphic to (,)
data SegVec v = SegVec v v

-- | Default implementation of segments using an auxiliary segment-length vector
instance SVM.ScanVectorMachine v s => SVM.ScanVectorMachine SegVec (v s) where
  neg         (SegVec a alens)                                   = SegVec (neg a)    alens
  leq         (SegVec a alens) (SegVec b blens)                  = SegVec (leq a b)  (check_eq alens blens)
  op       o  (SegVec a alens) (SegVec b blens)                  = SegVec (op o a b) (check_eq alens blens)
  select      (SegVec b blens) (SegVec x xlens) (SegVec y ylens) = SegVec (select b x y) (check_eq blens (check_eq xlens ylens))
  permute     (SegVec a alens) (SegVec i ilens)                  = undefined
  insert      (SegVec a alens) pos v                             = undefined
  extract     (SegVec a alens) pos                               = undefined
  distribute  v len                                              = undefined
  length      (SegVec a alens)                                   = undefined
  scan     o  (SegVec a alens)                                   = undefined