forsyde-atom-0.3.0.0: Shallow-embedded DSL for modeling cyber-physical systems
Copyright(c) George Ungureanu KTH/ICT/ESY 2016
LicenseBSD-style (see the file LICENSE)
Maintainerugeorge@kth.se
Stabilityexperimental
Portabilityportable
Safe HaskellSafe
LanguageHaskell2010

ForSyDe.Atom.Skel.Vector

Description

This module defines the data type Vector as a categorical type, and implements the atoms for the Skeleton class. Algorithmic skeletons for Vector are mostly described in their factorized form (see the factorization theorem). For practical reasons some skeletons are implemented as recurrences , but their factorized form is still documented.

Useful links:

Synopsis

Vector data type

data Vector a Source #

Although the name Vector is borrowed from <ForSyDe-Atom.html#reekie95 [Reekie95]> since it is more suggestive in the context of process networks, the Vector type is in fact modeling an infinite list defined as a category in [Skillicorn05]. According to this definition it should be implemented as following:

data Vector a = Null                   -- null element
              | Unit a                 -- singleton vector
              | Vector a <++> Vector a -- concatenate two vectors

This construction suggests the possibility of splitting a Vector into multiple parts and evaluating it in parallel. For simplicity and to ensure that the structure is flat and homogeneous, Vector is implemented using the same constructors as a regular Haskell list (see below). When defining skeletons of vectors we will not use the real constructors though, but the theoretical ones defined above and provided as functions. This way we align ForSyDe-Atom's Vector type with the skeleton theory and its theorems.

Another particularity of Vector is that it instantiates the reduction atom =\= as a right fold, as it is the most efficient lazy implementation of lists. As a consequence reduction is performed from right to left. This is noticed especially in the case of pipeline-based skeletons (see definition of pipe as a reduction with the right-associative composition operator .) is performed from right to left. Thus for reduce-based skeletons (e.g. prefix, suffix, recur, cascade, mesh) the result vectors shall be read from end to beginning.

Constructors

Null

Null element. Terminates a vector.

a :> (Vector a) infixr 3

appends an element at the head of a vector.

Instances

Instances details
Functor Vector Source #

Provides an implementation for =.=.

Instance details

Defined in ForSyDe.Atom.Skel.Vector.Core

Methods

fmap :: (a -> b) -> Vector a -> Vector b #

(<$) :: a -> Vector b -> Vector a #

Applicative Vector Source #

Provides an implementation for =*=.

Instance details

Defined in ForSyDe.Atom.Skel.Vector.Core

Methods

pure :: a -> Vector a #

(<*>) :: Vector (a -> b) -> Vector a -> Vector b #

liftA2 :: (a -> b -> c) -> Vector a -> Vector b -> Vector c #

(*>) :: Vector a -> Vector b -> Vector b #

(<*) :: Vector a -> Vector b -> Vector a #

Foldable Vector Source #

Provides an implementation for =\=.

Instance details

Defined in ForSyDe.Atom.Skel.Vector.Core

Methods

fold :: Monoid m => Vector m -> m #

foldMap :: Monoid m => (a -> m) -> Vector a -> m #

foldMap' :: Monoid m => (a -> m) -> Vector a -> m #

foldr :: (a -> b -> b) -> b -> Vector a -> b #

foldr' :: (a -> b -> b) -> b -> Vector a -> b #

foldl :: (b -> a -> b) -> b -> Vector a -> b #

foldl' :: (b -> a -> b) -> b -> Vector a -> b #

foldr1 :: (a -> a -> a) -> Vector a -> a #

foldl1 :: (a -> a -> a) -> Vector a -> a #

toList :: Vector a -> [a] #

null :: Vector a -> Bool #

length :: Vector a -> Int #

elem :: Eq a => a -> Vector a -> Bool #

maximum :: Ord a => Vector a -> a #

minimum :: Ord a => Vector a -> a #

sum :: Num a => Vector a -> a #

product :: Num a => Vector a -> a #

Skeleton Vector Source #

Ensures that Vector is a structure associated with the Skeleton Layer.

Instance details

Defined in ForSyDe.Atom.Skel.Vector.Core

Methods

(=.=) :: (a -> b) -> Vector a -> Vector b Source #

(=*=) :: Vector (a -> b) -> Vector a -> Vector b Source #

(=\=) :: (a -> a -> a) -> Vector a -> a Source #

(=<<=) :: Vector (a -> a) -> a -> a Source #

first :: Vector a -> a Source #

last :: Vector a -> a Source #

Eq a => Eq (Vector a) Source # 
Instance details

Defined in ForSyDe.Atom.Skel.Vector.Core

Methods

(==) :: Vector a -> Vector a -> Bool #

(/=) :: Vector a -> Vector a -> Bool #

Read a => Read (Vector a) Source #

The vector 1 :> 2 :> Null is read using the string "<1,2>".

Instance details

Defined in ForSyDe.Atom.Skel.Vector.Core

Show a => Show (Vector a) Source #

The vector 1 :> 2 :> Null is represented as <1,2>.

Instance details

Defined in ForSyDe.Atom.Skel.Vector.Core

Methods

showsPrec :: Int -> Vector a -> ShowS #

show :: Vector a -> String #

showList :: [Vector a] -> ShowS #

Plottable a => Plottable (Vector a) Source #

Vectors of plottable types

Instance details

Defined in ForSyDe.Atom.Utility.Plot

Methods

toCoord :: Vector a -> String Source #

Plottable a => Plot (Vector a) Source #

For plotting vectors of coordinates

Instance details

Defined in ForSyDe.Atom.Utility.Plot

"Constructors"

Theoretical constructors for the Vector type, used in the definition of skeletons as catamorphisms.

null :: Vector a Source #

Constructs a null vector.

>>> null
<>

unit :: a -> Vector a Source #

Constructs a singleton vector.

>>> unit 1
<1>

(<++>) :: Vector a -> Vector a -> Vector a infixr 5 Source #

Constructs a vector by appending two existing vectors.

>>> unit 1 <++> unit 2
<1,2>

Utilities

vector :: [a] -> Vector a Source #

Converts a list to a vector.

fromVector :: Vector a -> [a] Source #

Converts a vector to a list.

indexes :: Vector Int Source #

Creates the infinite vector:

<1,2,3,4,...>

Used mainly for operation on indexes.

isNull :: Vector a -> Bool Source #

Returns True if the argument is a null vector.

(<:) :: Vector a -> a -> Vector a infixl 5 Source #

Appends an element at the end of a vector.

Skeletons

Algorithmic skeletons on vectors are mainly presented in terms of compositions of the atoms associated with the Skeleton Layer. When defining them, we use the following operators:

where:

  • (1) is the unit constructor, constructing a singleton vector.
  • (2) is the <++> constructor, concatenating two vectors.
  • (3) is the <@! selector. The subscript notation is used to denote element at position n in a vector.
  • (4) suggests an arbitrary selector which returns a vector with another one's elements, based on some indices. The shown example is an alternative notation for the tail skeleton.

Functional networks

This sub-category denotes skeletons (patterns) which are take functions as arguments. If the functions are MoC layer entities, i.e. processes, then these patterns are capable of constructing parallel process networks. Using the applicative mechanism, the designer has a high degree of freedom when customizing process networks through systematic partial application, rendering numerous possible usages for the same pattern. To avoid over-encumbering the figures, they depict small test cases, which might not expose the full potential of the constructors.

see the naming convention rules on how to interpret, use and develop your own constructors.

farm22 Source #

Arguments

:: (a1 -> a2 -> (b1, b2))

function (e.g. process)

-> Vector a1

first input vector

-> Vector a2

second input vector

-> (Vector b1, Vector b2)

two output vectors

farm is simply the Vector instance of the skeletom farm pattern (see farm22). If the function taken as argument is a process, then it creates a farm network of data parallel processes.

Constructors: farm[1-4][1-4].

>>> let v1 = vector [1,2,3,4,5]
>>> S.farm21 (+) v1 v1
<2,4,6,8,10>
>>> let s1 = SY.signal [1,2,3,4,5]
>>> let v2 = vector [s1,s1,s1]
>>> S.farm11 (comb11 (+1)) v2
<{2,3,4,5,6},{2,3,4,5,6},{2,3,4,5,6}>
>>> S.farm21 (\x -> comb11 (+x)) v1 v2
<{2,3,4,5,6},{3,4,5,6,7},{4,5,6,7,8}>

reduce :: (a -> a -> a) -> Vector a -> a Source #

As the name suggests, it reduces a vector to an element based on an associative function. If the function is not associative, it can be treated like a pipeline.

Vector instantiates the skeletons for both reduce and reducei.

>>> let v1 = vector [1,2,3,4,5]
>>> S.reduce (+) v1
15
>>> let s1 = SY.signal [1,2,3,4,5]
>>> let s2 = SY.signal [10,10,10,10,10]
>>> let v2 = vector [s1,s1,s1]
>>> S.reduce (comb21 (+)) v2
{3,6,9,12,15}
>>> S.reducei (comb21 (+)) s2 v2
{13,16,19,22,25}

prefix :: (b -> b -> b) -> Vector b -> Vector b Source #

prefix peforms the parallel prefix operation on a vector. Equivalent process networks are constructed if processes are passed as arguments.

Similar to reduce and reducei, two versions prefix and prefixi are provided.

>>> let v1 = vector [1,2,3,4,5]
>>> prefix (+) v1
<15,14,12,9,5>
>>> let s1 = SY.signal [1,2,3,4,5]
>>> let s2 = SY.signal [10,10,10,10,10]
>>> let v2 = vector [s1,s1,s1]
>>> prefix (comb21 (+)) v2
<{3,6,9,12,15},{2,4,6,8,10},{1,2,3,4,5}>
>>> prefixi (comb21 (+)) s2 v2
<{13,16,19,22,25},{12,14,16,18,20},{11,12,13,14,15}>

suffix :: (b -> b -> b) -> Vector b -> Vector b Source #

suffix peforms the parallel suffix operation on a vector. Equivalent process networks are constructed if processes are passed as arguments.

Similar to reduce and reducei, two versions suffix and suffixi are provided.

>>> let v1 = vector [1,2,3,4,5]
>>> suffix (+) v1
<1,3,6,10,15>
>>> let s1 = SY.signal [1,2,3,4,5]
>>> let s2 = SY.signal [10,10,10,10,10]
>>> let v2 = vector [s1,s1,s1]
>>> suffix (comb21 (+)) v2
<{1,2,3,4,5},{2,4,6,8,10},{3,6,9,12,15}>
>>> suffixi (comb21 (+)) s2 v2
<{11,12,13,14,15},{12,14,16,18,20},{13,16,19,22,25}>

pipe Source #

Arguments

:: Vector (a -> a)

vector of functions

-> a

input

-> a

output

pipe creates a pipeline of functions from a vector. pipe simply instantiates the =<<= atom whereas pipeX instantiate their omologi from the ForSyDe.Atom.Skel module (see pipe2).

OBS: the pipelining is done in the order dictated by the function composition operator: from right to left.

Constructors: pipe[1-4].

>>> let v1 = vector [(+1),(+1),(+1)]
>>> S.pipe v1 1
4
>>> let s1 = SY.signal [1,2,3,4]
>>> let v2 = vector [1,2,3,4]
>>> S.pipe1 (\x -> comb11 (+x)) v2 s1
{11,12,13,14}

(=/=) :: Vector (a -> a) -> a -> Vector a infixl 2 Source #

Infix operator for recur.

recur Source #

Arguments

:: Vector (a -> a)

vector of functions

-> a

input

-> Vector a

output

recur creates a systolic array from a vector of functions. Just like pipe and pipeX, there exists a raw recur version with an infix operator =/=, and the enhanced recurX which is meant for systematic partial application of a function on an arbitrary number of vectors until the desired vector of functions is obtained.

Constructors: (=/=), recur, recuri, recur[1-4][1-4].

>>> let v1 = vector [(+1),(+1),(+1)]
>>> recur v1 1
<4,3,2>
>>> recuri v1 1
<4,3,2,1>
>>> let s1 = SY.signal [1,2,3,4]
>>> let v2 = vector [1,2,3,4]
>>> recur1 (\x -> comb11 (+x)) v2 s1
<{11,12,13,14},{10,11,12,13},{8,9,10,11},{5,6,7,8}>

cascade2 Source #

Arguments

:: (a2 -> a1 -> a -> a -> a)

function41 which needs to be applied to function21

-> Vector (Vector a2)

fills in the first argument in the function above

-> Vector (Vector a1)

fills in the second argument in the function above

-> Vector a

first input vector (e.g. of signals)

-> Vector a

second input vector (e.g. of signals)

-> Vector a

output

cascade creates a "cascading mesh" as a result of piping a vector into a vector of recur arrays.

Constructors: cascade, cascade[1-4].

>>> let v1 = vector [1,2,3,4]
>>> cascade (+) v1 v1
<238,119,49,14>
>>> let s1 = SY.signal [1,2,3,4]
>>> let vs = vector [s1, s1, s1]
>>> cascade (comb21 (+)) vs vs
<{20,40,60,80},{10,20,30,40},{4,8,12,16}>
>>> let vv = vector [vector [1,-1,1], vector [-1,1,-1], vector [1,-1,1] ]
>>> cascade1 (\x -> comb21 (\y z-> x*(y+z))) vv vs vs
<{16,32,48,64},{8,16,24,32},{-2,-4,-6,-8}>

mesh2 Source #

Arguments

:: (a2 -> a1 -> a -> a -> a)

function41 which needs to be applied to function21

-> Vector (Vector a2)

fills in the first argument in the function above

-> Vector (Vector a1)

fills in the second argument in the function above

-> Vector a

first input vector (e.g. of signals)

-> Vector a

second input vector (e.g. of signals)

-> Vector (Vector a)

output, a 2D vector

mesh creates a 2D systolic array as a result of piping a vector into a vector of 1D systolic arrays.

Constructors: mesh, mesh[1-4].

>>> let v1 = vector [1,2,3,4]
>>> mesh (+) v1 v1
<<238,119,49,14>,<119,70,35,13>,<49,35,22,11>,<14,13,11,8>>
>>> let s1 = SY.signal [1,2,3,4]
>>> let vs = vector [s1, s1, s1]
>>> mesh (comb21 (+)) vs vs
<<{20,40,60,80},{10,20,30,40},{4,8,12,16}>,<{10,20,30,40},{6,12,18,24},{3,6,9,12}>,<{4,8,12,16},{3,6,9,12},{2,4,6,8}>>
>>> let vv = vector [vector [1,-1,1], vector [-1,1,-1], vector [1,-1,1]]
>>> mesh1 (\x -> comb21 (\y z-> x*(y+z))) vv vs vs
<<{16,32,48,64},{8,16,24,32},{-2,-4,-6,-8}>,<{8,16,24,32},{-6,-12,-18,-24},{-3,-6,-9,-12}>,<{-2,-4,-6,-8},{-3,-6,-9,-12},{2,4,6,8}>>

Queries

Queries return various information about a vector. They are also built as skeletons.

length :: Num p => Vector a -> p Source #

returns the number of elements in a value.

>>> length $ vector [1,2,3,4,5]
5

index :: Vector a2 -> Vector Int Source #

returns a vector with the indexes from another vector.

>>> index $ vector [1,1,1,1,1,1,1]
<1,2,3,4,5,6,7>

Generators

Generators are specific applications of the prefix or suffix skeletons.

fanout :: t -> Vector t Source #

fanout repeats an element. As a process network it distributes the same value or signal to all the connected processes down the line. Depending on the target platform and the refinement decisions involved, it may be interpreted in the following implementations:

  • global or shared memory in case of a massively parallel platform (e.g. GPU)
  • a (static) memory or cache location in memory-driven architectures (e.g. CPU)
  • a fanout in case of a HDL system
  • a broadcast in case of a distributed system

fanoutn :: (Ord t, Num t) => t -> a -> Vector a Source #

fanoutn is the same as fanout, but the length of the result is also provided.

>>> fanoutn 5 1
<1,1,1,1,1>

generate :: (Ord t, Num t) => t -> (a -> a) -> a -> Vector a Source #

generate creates a vector based on a kernel function. It is just a restricted version of recur.

>>> generate 5 (+1) 1
<6,5,4,3,2>

iterate :: (Ord t, Num t) => t -> (a -> a) -> a -> Vector a Source #

iterate is a version of generate which keeps the initial element as well. It is a restricted version of recuri.

>>> iterate 5 (+1) 1
<5,4,3,2,1>

Permutators

Permutators perform operations on the very structure of vectors, and make heavy use of the vector constructors.

first :: Vector a -> a Source #

Instance of first

>>> S.first $ vector [1,2,3,4,5]
1

last :: Vector a -> a Source #

Instance of last

>>> S.last $ vector [1,2,3,4,5]
5

inits :: Vector a -> Vector (Vector a) Source #

creates a vector of all the initial segments in a vector.

>>> inits $ vector [1,2,3,4,5]
<<1>,<1,2>,<1,2,3>,<1,2,3,4>,<1,2,3,4,5>>

tails :: Vector a -> Vector (Vector a) Source #

creates a vector of all the final segments in a vector.

>>> tails $ vector [1,2,3,4,5]
<<1,2,3,4,5>,<2,3,4,5>,<3,4,5>,<4,5>,<5>>

init :: Vector a -> Vector a Source #

Returns the initial segment of a vector.

>>> init $ vector [1,2,3,4,5]
<1,2,3,4>

tail :: Vector a -> Vector a Source #

Returns the tail of a vector.

>>> tail $ vector [1,2,3,4,5]
<2,3,4,5>

concat :: Vector (Vector a) -> Vector a Source #

concatenates a vector of vectors.

>>> concat $ vector [vector[1,2,3,4], vector[5,6,7]]
<1,2,3,4,5,6,7>

reverse :: Vector a -> Vector a Source #

reverses the elements in a vector.

>>> reverse $ vector [1,2,3,4,5]
<5,4,3,2,1>

group :: Int -> Vector a -> Vector (Vector a) Source #

groups a vector into sub-vectors of n elements.

>>> group 3 $ vector [1,2,3,4,5,6,7,8]
<<1,2,3>,<4,5,6>,<7,8>>

shiftr :: Vector a -> a -> Vector a Source #

right-shifts a vector with an element.

>>> vector [1,2,3,4] `shiftr` 8
<8,1,2,3>

shiftl :: Vector a -> a -> Vector a Source #

left-shifts a vector with an element.

>>> vector [1,2,3,4] `shiftl` 8
<2,3,4,8>

rotr :: Vector a -> Vector a Source #

rotates a vector to the right.

>>> rotr $ vector [1,2,3,4]
<4,1,2,3>

rotl :: Vector a -> Vector a Source #

rotates a vector to the left.

>>> rotl $ vector [1,2,3,4]
<2,3,4,1>

rotate :: Int -> Vector a -> Vector a Source #

rotates a vector to the left or to the right depending on the index:

  • (> 0) : rotates the vector right with the corresponding number of positions.
  • (= 0) : does not modify the vector.
  • (< 0) : rotates the vector left with the corresponding number of positions.

take :: Int -> Vector a -> Vector a Source #

takes the first n elements of a vector.

>>> take 5 $ vector [1,2,3,4,5,6,7,8,9]
<1,2,3,4,5>

drop :: Int -> Vector a -> Vector a Source #

drops the first n elements of a vector.

>>> drop 5 $ vector [1,2,3,4,5,6,7,8,9]
<6,7,8,9>

takeWhile :: (a -> Bool) -> Vector a -> Vector a Source #

takes the first elements in a vector until the first element that does not fulfill a predicate.

>>> takeWhile (<5) $ vector [1,2,3,4,5,6,7,8,9]
<1,2,3,4>

filterIdx :: (Int -> Bool) -> Vector a -> Vector a Source #

returns a vector containing only the elements of another vector whose index satisfies a predicate.

>>> filterIdx (\x -> x `mod` 3 == 0) $ vector [0,1,2,3,4,5,6,7,8,9]
<2,5,8>

stride Source #

Arguments

:: Int

first index

-> Int

stride length

-> Vector a 
-> Vector a 

does a stride-selection on a vector.

>>> stride 1 3 $ vector [1,2,3,4,5,6,7,8,9]
<1,4,7>

get :: Int -> Vector a -> Maybe a Source #

returns the n-th element in a vector, or Nothing if n > l.

>>> get 3 $ vector [1,2,3,4,5]
Just 3

(<@) :: Vector a -> Int -> Maybe a Source #

the same as get but with flipped arguments.

(<@!) :: Vector p -> Int -> p Source #

unsafe version of <@. Throws an exception if n > l.

gather1 Source #

Arguments

:: Vector Int

vector of indexes

-> Vector a

input vector

-> Vector (Maybe a) 

selects the elements in a vector at the incexes contained by another vector.

The following versions of this skeleton are available, the number suggesting how many nested vectors it is operating upon: gather[1-5]

>>> let ix = vector [vector [1,3,4], vector [3,5,1], vector [5,8,9]]
>>> let v = vector [11,12,13,14,15]
>>> gather2 ix v
<<Just 11,Just 13,Just 14>,<Just 13,Just 15,Just 11>,<Just 15,Nothing,Nothing>>

(<@>) Source #

Arguments

:: Vector a

input vector

-> Vector Int

vector of indexes

-> Vector (Maybe a) 

the same as gather1 but with flipped arguments

The following versions of this skeleton are available, the number suggesting how many nested vectors it is operating upon.

(<@>), (<<@>>), (<<<@>>>), (<<<<@>>>>), (<<<<<@>>>>>),

replace :: Int -> a -> Vector a -> Vector a Source #

replaces the n-th element in a vector with another.

>>> replace 5 15 $ vector [1,2,3,4,5,6,7,8,9]
<1,2,3,4,15,6,7,8,9>

scatter :: Vector Int -> Vector a -> Vector a -> Vector a Source #

scatters the elements in a vector based on the indexes contained by another vector.

>>> scatter (vector [2,4,5]) (vector [0,0,0,0,0,0,0,0]) (vector [1,1,1])
<0,1,0,1,1,0,0,0>

Interfaces

zipx Source #

Arguments

:: MoC e 
=> Vector ((Vector a -> Vector a -> Vector a) -> Fun e (Vector a) (Fun e (Vector a) (Ret e (Vector a))))

vector of MoC-specific context wrappers for the function <++>

-> Vector (Stream (e a))

input vector of signals

-> Stream (e (Vector a))

output signal of vectors

zipx is a template skeleton for "zipping" a vector of signals. It synchronizes all signals (of the same MoC) in a vector and outputs one signal with vectors of the synced values. For each signal in the input vector it requires a function which translates a partition of events (see ForSyDe.Atom.MoC) into sub-vectors.

There exist helper instances of the zipx skeleton interface for all supported MoCs.

unzipx :: MoC e => (Vector a -> Vector (Ret e a)) -> Integer -> Stream (e (Vector a)) -> Vector (Stream (e a)) Source #

unzipx is a template skeleton to unzip a signal carrying vectors into a vector of multiple signals. It required a function that splits a vector of values into a vector of event partitions belonging to output signals. Unlike zipx, it also requires the number of output signals. The reason for this is that it is impossible to determine the length of the output vector without "sniffing" the content of the input events, which is out of the scope of skeletons and may lead to unsafe behavior. The length of the output vector is needed in order to avoid infinite recurrence.

There exist helper instances of the unzipx skeleton interface for all supported MoCs.