forsyde-shallow-3.3.1.0: src/ForSyDe/Shallow/DataflowLib.hs
-----------------------------------------------------------------------------
-- |
-- Module : ForSyDe.Shallow.DataflowLib
-- Copyright : (c) SAM Group, KTH/ICT/ECS 2007-2008
-- License : BSD-style (see the file LICENSE)
--
-- Maintainer : forsyde-dev@ict.kth.se
-- Stability : experimental
-- Portability : portable
--
-- The dataflow library defines data types, process constructors and
-- functions to model dataflow process networks, as described by Lee and
-- Parks in Dataflow process networks, IEEE Proceedings, 1995 ([LeeParks95]).
--
-- Each process is defined by a set of firing rules and corresponding
-- actions. A process fires, if the incoming signals match a firing
-- rule. Then the process consumes the matched tokens and executes the
-- action corresponding to the firing rule.
--
-----------------------------------------------------------------------------
module ForSyDe.Shallow.DataflowLib
(
-- * Data Types
-- | The data type @FiringToken@ defines the data type for tokens. The
-- constructor @Wild@ constructs a token wildcard, the constructor
-- @Value a@ constructs a token with value @a@.
--
-- A sequence (pattern) matches a signal, if the sequence is a prefix of
-- the signal. The following list illustrates the firing rules:
--
-- * [⊥] matches always (/NullS/ in ForSyDe)
--
-- * [*] matches signal with at least one token (/[Wild]/ in ForSyDe)
--
-- * [v] matches signal with v as its first value (/[Value v]/ in ForSyDe)
--
-- * [*,*] matches signals with at least two tokens (/[Wild,Wild]/ in ForSyDe)
--
FiringToken(Wild, Value),
-- * Combinational Process Constructors
-- | Combinatorial processes
-- do not have an internal state. This means, that the output
-- signal only depends on the input signals.
--
-- To illustrate the concept of data flow processes, we create a process that selects tokens from two inputs according to a control signal.
--
-- The process has the following firing rules [LeeParks95]:
--
--
-- * R1 = {[*], ⊥, [T]}
--
-- * R2 = {⊥, [*], [F]}
--
--
-- The corresponding ForSyDe formulation of the firing rules is:
--
-- @
-- selectRules = [ ([Wild], [], [Value True]),
-- ([], [Wild], [Value False]) ]
-- @
--
-- For the output we formulate the following set of output functions:
--
-- @
-- selectOutput xs ys _ = [ [headS xs], [headS ys] ]
-- @
--
-- The select process /selectDF/ is then defined by:
--
-- @
-- selectDF :: Eq a => Signal a -> Signal a
-- -> Signal Bool -> Signal a
-- selectDF = zipWith3DF selectRules selectOutput
-- @
--
-- Given the signals /s1/, /s2/ and /s3/
--
-- @
-- s1 = signal [1,2,3,4,5,6]
-- s2 = signal [7,8,9,10,11,12]
-- s3 = signal [True, True, False, False, True, True]
-- @
--
-- the executed process gives the following results:
--
-- @
-- DataflowLib> selectDF s1 s2 s3
-- {1,2,7,8,3,4} :: Signal Integer
-- @
--
-- The library contains the following combinational process constructors:
mapDF, zipWithDF, zipWith3DF,
-- * Sequential Process Constructors
-- | Sequential processes have
-- an internal state. This means, that the output signal may
-- depend internal state and on the input signal.
--
-- As an example we can view a process calculating the running sum
-- of the input tokens. It has only one firing rule, which is
-- illustrated below.
--
-- @
-- Firing Rule Next State Output
-- ------------------------------------
-- (*,[*]) state + x {state}
-- @
--
-- A dataflow process using these firing rules and the initial state 0 can be formulated in ForSyDe as
--
-- @
-- rs xs = mealyDF firingRule nextState output initState xs
-- where
-- firingRule = [(Wild, [Wild])]
-- nextState state xs = [(state + headS xs)]
-- output state _ = [[state]]
-- initState = 0
-- @
--
-- Execution of the process gives
--
-- @
-- DataflowLib> rs (signal[1,2,3,4,5,6])
-- {0,1,3,6,10,15} :: Signal Integer
-- @
--
-- Another 'running sum' process /rs2/ takes two tokens, pushes
-- them into a queue of five elements and calculates the sum as
-- output.
--
-- @
-- rs2 = mealyDF fs ns o init
-- where
-- init = [0,0,0,0,0]
-- fs = [(Wild, ([Wild, Wild]))]
-- ns state xs = [drop 2 state ++ fromSignal (takeS 2 xs)]
-- o state _ = [[(sum state)]]
-- @
--
-- Execution of the process gives
--
-- @
-- DataflowLib>rs2 (signal [1,2,3,4,5,6,7,8,9,10])
-- {0,3,10,20,30} :: Signal Integer
-- @
scanlDF, mooreDF, mealyDF
) where
import ForSyDe.Shallow.CoreLib
------------------------------------------------------------------------
--
-- DATA TYPES
--
------------------------------------------------------------------------
data FiringToken a = Wild
| Value a deriving (Eq, Show)
------------------------------------------------------------------------
--
-- COMBINATIONAL PROCESS CONSTRUCTORS
--
------------------------------------------------------------------------
-- |The process constructor @mapDF@ takes a list of firing rules, a list of corresponding output functions and generates a data flow process with one input and one output signal.
mapDF :: Eq a => [[FiringToken a]]
-> (Signal a -> [[b]]) -> Signal a -> Signal b
mapDF _ _ NullS = NullS
mapDF rs as xs = output +-+ mapDF rs as xs'
where
xs' = if matchedRule < 0 then
NullS
else
consumeDF rule xs
matchedRule = (matchDF rs xs)
rule = rs !! matchedRule
output = if matchedRule < 0 then
NullS
else
signal ((as xs) !! matchedRule)
-- |The process constructors @zipWithDF@ takes a list of firing rules, a list of corresponding output functions to generate a data flow process with two input signals and one output signal.
zipWithDF :: (Eq a, Eq b) =>
[([FiringToken b], [FiringToken a])]
-> (Signal b -> Signal a -> [[c]]) -> Signal b
-> Signal a -> Signal c
zipWithDF _ _ NullS NullS = NullS
zipWithDF rs as xs ys = output +-+ zipWithDF rs as xs' ys'
where
(xs', ys') = if matchedRule < 0 then
(NullS, NullS)
else
consume2DF rule xs ys
matchedRule = (match2DF rs xs ys)
rule = rs !! matchedRule
output = if matchedRule < 0 then
NullS
else
signal ((as xs ys) !! matchedRule)
-- |The process constructors @zipWith3DF@ takes a list of firing rules, a list of corresponding output functions to generate a data flow process with three input signals and one output signal.
zipWith3DF :: (Eq a, Eq b, Eq c) =>
[([FiringToken a],[FiringToken b],[FiringToken c])]
-> (Signal a -> Signal b -> Signal c -> [[d]])
-> Signal a -> Signal b -> Signal c -> Signal d
zipWith3DF _ _ NullS NullS NullS = NullS
zipWith3DF rs as xs ys zs = output +-+ zipWith3DF rs as xs' ys' zs'
where
(xs', ys', zs') = if matchedRule < 0 then
(NullS, NullS, NullS)
else
consume3DF rule xs ys zs
matchedRule = (match3DF rs xs ys zs)
rule = rs !! matchedRule
output = if matchedRule < 0 then
NullS
else
signal ((as xs ys zs) !! matchedRule)
------------------------------------------------------------------------
--
-- SEQUENTIAL PROCESS CONSTRUCTORS
--
------------------------------------------------------------------------
-- | The process constructor @scanlDF@ implements a finite state machine without output decoder in the ForSyDe methodology. It takes a set of firing rules and a set of corresponding next state functions as arguments. A firing rule is a tuple. The first value is a pattern for the state, the second value corresponds to an input pattern. When a pattern matches, the process fires, the corresponding next state is executed, and the tokens matching the pattern are consumed.
scanlDF :: (Eq a, Eq b) => [(FiringToken b,[FiringToken a])]
-> (b -> Signal a -> [b])
-> b -> Signal a -> Signal b
scanlDF _ _ _ NullS = NullS
scanlDF fs ns state xs = (unitS state)
+-+ scanlDF fs ns state' xs'
where
xs' = if matchedRule < 0 then
NullS
else
consumeDF rule xs
matchedRule = matchStDF fs state xs
rule = snd (fs !! matchedRule)
state' = if matchedRule < 0 then
error "No rule matches the pattern!"
else
(ns state xs) !! matchedRule
-- | The process constructor @mooreDF@ implements a Moore finite state machine in the ForSyDe methodology. It takes a set of firing rules, a set of corresponding next state functions and a set of output functions as argument. A firing rule is a tuple. The first value is a pattern for the state, the second value corresponds to an input pattern. When a pattern matches, the process fires, the corresponding next state and output functions are executed, and the tokens matching the pattern are consumed.
mooreDF :: (Eq a, Eq b) => [(FiringToken b,[FiringToken a])]
-> (b -> Signal a -> [b]) -> (b -> [c])
-> b -> Signal a -> Signal c
mooreDF _ _ _ _ NullS = NullS
mooreDF fs ns o state xs = output +-+ mooreDF fs ns o state' xs'
where
xs' = if matchedRule < 0 then
NullS
else
consumeDF rule xs
matchedRule = matchStDF fs state xs
rule = snd (fs !! matchedRule)
output = signal (o state)
state' = if matchedRule < 0 then
error "No rule matches the pattern!"
else
(ns state xs) !! matchedRule
-- | The process constructor @mealyDF@ implements the most general state machine in the ForSyDe methodology. It takes a set of firing rules, a set of corresponding next state functions and a set of output functions as argument. A firing rule is a tuple. The first value is a pattern for the state, the second value corresponds to an input pattern. When a pattern matches, the process fires, the corresponding next state and output functions are executed, and the tokens matching the pattern are consumed.
mealyDF :: (Eq a, Eq b) => [(FiringToken b,[FiringToken a])]
-> (b -> Signal a -> [b]) -> (b -> Signal a -> [[c]])
-> b -> Signal a -> Signal c
mealyDF _ _ _ _ NullS = NullS
mealyDF fs ns o state xs = output +-+ mealyDF fs ns o state' xs'
where
xs' = if matchedRule < 0 then
NullS
else
consumeDF rule xs
matchedRule = matchStDF fs state xs
rule = snd (fs !! matchedRule)
output = signal ((o state xs) !! matchedRule)
state' = if matchedRule < 0 then
error "No rule matches the pattern!"
else
(ns state xs) !! matchedRule
------------------------------------------------------------------------
--
-- SUPPORTING FUNCTIONS
--
------------------------------------------------------------------------
-- The function 'prefixDF' takes a pattern and a signal and returns
-- 'True', if the pattern is a prefix from the signal.
prefixDF :: Eq a => [FiringToken a] -> Signal a -> Bool
prefixDF [] _ = True
prefixDF _ NullS = False
prefixDF (Wild:ps) (_:-xs) = prefixDF ps xs
prefixDF ((Value p):ps) (x:-xs) = if p == x then
prefixDF ps xs
else
False
-- The function 'consumeDF' takes a pattern and a signal and consumes
-- the pattern from the signal. The functions 'consume2DF' and
-- 'consume3DF' work in the same way as 'consumeDF', but with two and
-- three input signals.
consumeDF :: Eq a => [FiringToken a]
-> Signal a -> Signal a
consumeDF _ NullS = NullS
consumeDF [] xs = xs
consumeDF (Wild:ts) (_:-xs) = consumeDF ts xs
consumeDF (Value t:ts) (x:-xs) = if t == x then
consumeDF ts xs
else
error "Tokens not correct"
consume2DF :: (Eq a, Eq b) =>
([FiringToken a], [FiringToken b])
-> Signal a -> Signal b -> (Signal a, Signal b)
consume2DF (px, py) xs ys = (consumeDF px xs,
consumeDF py ys)
consume3DF :: (Eq a, Eq b, Eq c) =>
([FiringToken a], [FiringToken b], [FiringToken c])
-> Signal a -> Signal b -> Signal c
-> (Signal a,Signal b,Signal c)
consume3DF (px, py, pz) xs ys zs = (consumeDF px xs,
consumeDF py ys,
consumeDF pz zs)
-- The function 'matchDF' checks, which firing rule, starting from 0, is
-- matched by the input signal. If no firing rule matches, the output is
-- '-1'. The functions 'maptch2S' and 'match3DF' work in the same way
-- for two and three inputs.
matchDF :: (Num a, Eq b) =>
[[FiringToken b]] -> Signal b -> a
matchDF rs xs = matchDF' 0 rs xs
where matchDF' _ [] _ = -1
matchDF' n (r:rs) xs = if prefixDF r xs then
n
else
matchDF' (n+1) rs xs
match2DF :: (Num a, Eq b, Eq c) =>
[([FiringToken b], [FiringToken c])]
-> Signal b -> Signal c -> a
match2DF rs xs ys = match2DF' 0 rs xs ys
where match2DF' _ [] _ _ = -1
match2DF' n ((rx, ry):rs) xs ys
= if prefixDF rx xs &&
prefixDF ry ys
then
n
else
match2DF' (n+1) rs xs ys
match3DF :: (Num a, Eq b, Eq c, Eq d) =>
[([FiringToken b], [FiringToken d], [FiringToken c])]
-> Signal b -> Signal d -> Signal c -> a
match3DF rs xs ys zs = match3DF' 0 rs xs ys zs
where match3DF' _ [] _ _ _ = -1
match3DF' n ((rx, ry, rz):rs) xs ys zs
= if prefixDF rx xs &&
prefixDF ry ys &&
prefixDF rz zs
then
n
else
match3DF' (n+1) rs xs ys zs
-- The function 'matchStDF' works in the same way as 'matchDF', but it looks on patterns that include the state.
matchStDF :: (Num a, Eq b, Eq c) =>
[(FiringToken c,[FiringToken b])]
-> c -> Signal b -> a
matchStDF rs state xs = matchStDF' 0 rs state xs
where matchStDF' _ [] _ _ = -1
matchStDF' n (r:rs) state xs
= if prefixDF (snd r) xs &&
matchState (fst r) state
then
n
else
matchStDF' (n+1) rs state xs
matchState :: Eq a => FiringToken a -> a -> Bool
matchState Wild _ = True
matchState (Value v) x = x == v
------------------------------------------------------------------------
--
-- CODE FOR TESTING
--
------------------------------------------------------------------------
{-
selectRules :: [([FiringToken a], [FiringToken a1], [FiringToken Bool])]
selectRules = [ ([Wild], [], [Value True]),
([], [Wild], [Value False]) ]
selectOutput :: Signal t1 -> Signal t1 -> t -> [[t1]]
selectOutput xs ys _ = [ [headS xs], [headS ys] ]
selectDF :: Eq a => Signal a -> Signal a
-> Signal Bool -> Signal a
selectDF = zipWith3DF selectRules selectOutput
s1 :: Signal Integer
s1 = signal [1,2,3,4,5,6]
s2 :: Signal Integer
s2 = signal [7,8,9,10,11,12]
s3 :: Signal Bool
s3 = signal [True, True, False, False, True, True]
rs :: (Eq c, Num c) => Signal c -> Signal c
rs xs = mealyDF firingRule nextState output initState xs
where firingRule = [(Wild, [Wild])]
nextState state xs = [(state + headS xs)]
output state _ = [[state]]
initState = 0
rs2 :: Signal Integer -> Signal Integer
rs2 = mealyDF fs ns o init
where init = [0,0,0,0,0]
fs = [(Wild, ([Wild, Wild]))]
ns state xs = [drop 2 state ++ fromSignal (takeS 2 xs)]
o state _ = [[(sum state)]]
-}