-----------------------------------------------------------------------------
-- |
-- Module  :  ForSyDe.Shallow.MoC.Dataflow
-- Copyright   :  (c) ForSyDe Group, KTH 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.MoC.Dataflow
    (
  -- * 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.Core 


------------------------------------------------------------------------
-- DATA TYPES
------------------------------------------------------------------------

data FiringToken a = Wild
       | Value a deriving (FiringToken a -> FiringToken a -> Bool
(FiringToken a -> FiringToken a -> Bool)
-> (FiringToken a -> FiringToken a -> Bool) -> Eq (FiringToken a)
forall a. Eq a => FiringToken a -> FiringToken a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: FiringToken a -> FiringToken a -> Bool
$c/= :: forall a. Eq a => FiringToken a -> FiringToken a -> Bool
== :: FiringToken a -> FiringToken a -> Bool
$c== :: forall a. Eq a => FiringToken a -> FiringToken a -> Bool
Eq, Int -> FiringToken a -> ShowS
[FiringToken a] -> ShowS
FiringToken a -> String
(Int -> FiringToken a -> ShowS)
-> (FiringToken a -> String)
-> ([FiringToken a] -> ShowS)
-> Show (FiringToken a)
forall a. Show a => Int -> FiringToken a -> ShowS
forall a. Show a => [FiringToken a] -> ShowS
forall a. Show a => FiringToken a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [FiringToken a] -> ShowS
$cshowList :: forall a. Show a => [FiringToken a] -> ShowS
show :: FiringToken a -> String
$cshow :: forall a. Show a => FiringToken a -> String
showsPrec :: Int -> FiringToken a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> FiringToken a -> ShowS
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 :: [[FiringToken a]] -> (Signal a -> [[b]]) -> Signal a -> Signal b
mapDF [[FiringToken a]]
_ Signal a -> [[b]]
_ Signal a
NullS = Signal b
forall a. Signal a
NullS 
mapDF [[FiringToken a]]
rs Signal a -> [[b]]
as Signal a
xs  = Signal b
output Signal b -> Signal b -> Signal b
forall a. Signal a -> Signal a -> Signal a
+-+ [[FiringToken a]] -> (Signal a -> [[b]]) -> Signal a -> Signal b
forall a b.
Eq a =>
[[FiringToken a]] -> (Signal a -> [[b]]) -> Signal a -> Signal b
mapDF [[FiringToken a]]
rs Signal a -> [[b]]
as Signal a
xs'
  where
    xs' :: Signal a
xs'         = if Int
matchedRule Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 then
                    Signal a
forall a. Signal a
NullS
                  else
                    [FiringToken a] -> Signal a -> Signal a
forall a. Eq a => [FiringToken a] -> Signal a -> Signal a
consumeDF [FiringToken a]
rule Signal a
xs
    matchedRule :: Int
matchedRule = ([[FiringToken a]] -> Signal a -> Int
forall a b. (Num a, Eq b) => [[FiringToken b]] -> Signal b -> a
matchDF [[FiringToken a]]
rs Signal a
xs)
    rule :: [FiringToken a]
rule        = [[FiringToken a]]
rs [[FiringToken a]] -> Int -> [FiringToken a]
forall a. [a] -> Int -> a
!! Int
matchedRule
    output :: Signal b
output      = if Int
matchedRule Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 then
                    Signal b
forall a. Signal a
NullS
                  else
                    [b] -> Signal b
forall a. [a] -> Signal a
signal ((Signal a -> [[b]]
as Signal a
xs) [[b]] -> Int -> [b]
forall a. [a] -> Int -> a
!! Int
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 :: [([FiringToken b], [FiringToken a])]
-> (Signal b -> Signal a -> [[c]])
-> Signal b
-> Signal a
-> Signal c
zipWithDF [([FiringToken b], [FiringToken a])]
_ Signal b -> Signal a -> [[c]]
_ Signal b
NullS Signal a
NullS = Signal c
forall a. Signal a
NullS
zipWithDF [([FiringToken b], [FiringToken a])]
rs Signal b -> Signal a -> [[c]]
as Signal b
xs Signal a
ys     = Signal c
output Signal c -> Signal c -> Signal c
forall a. Signal a -> Signal a -> Signal a
+-+ [([FiringToken b], [FiringToken a])]
-> (Signal b -> Signal a -> [[c]])
-> Signal b
-> Signal a
-> Signal c
forall a b c.
(Eq a, Eq b) =>
[([FiringToken b], [FiringToken a])]
-> (Signal b -> Signal a -> [[c]])
-> Signal b
-> Signal a
-> Signal c
zipWithDF [([FiringToken b], [FiringToken a])]
rs Signal b -> Signal a -> [[c]]
as Signal b
xs' Signal a
ys'
  where 
    (Signal b
xs', Signal a
ys')  = if Int
matchedRule Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 then
                    (Signal b
forall a. Signal a
NullS, Signal a
forall a. Signal a
NullS)
                  else
                    ([FiringToken b], [FiringToken a])
-> Signal b -> Signal a -> (Signal b, Signal a)
forall a b.
(Eq a, Eq b) =>
([FiringToken a], [FiringToken b])
-> Signal a -> Signal b -> (Signal a, Signal b)
consume2DF ([FiringToken b], [FiringToken a])
rule Signal b
xs Signal a
ys
    matchedRule :: Int
matchedRule = ([([FiringToken b], [FiringToken a])] -> Signal b -> Signal a -> Int
forall a b c.
(Num a, Eq b, Eq c) =>
[([FiringToken b], [FiringToken c])] -> Signal b -> Signal c -> a
match2DF [([FiringToken b], [FiringToken a])]
rs Signal b
xs Signal a
ys)
    rule :: ([FiringToken b], [FiringToken a])
rule        = [([FiringToken b], [FiringToken a])]
rs [([FiringToken b], [FiringToken a])]
-> Int -> ([FiringToken b], [FiringToken a])
forall a. [a] -> Int -> a
!! Int
matchedRule
    output :: Signal c
output      = if Int
matchedRule Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 then
                    Signal c
forall a. Signal a
NullS
                  else
                    [c] -> Signal c
forall a. [a] -> Signal a
signal ((Signal b -> Signal a -> [[c]]
as Signal b
xs Signal a
ys) [[c]] -> Int -> [c]
forall a. [a] -> Int -> a
!! Int
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 :: [([FiringToken a], [FiringToken b], [FiringToken c])]
-> (Signal a -> Signal b -> Signal c -> [[d]])
-> Signal a
-> Signal b
-> Signal c
-> Signal d
zipWith3DF [([FiringToken a], [FiringToken b], [FiringToken c])]
_ Signal a -> Signal b -> Signal c -> [[d]]
_ Signal a
NullS Signal b
NullS Signal c
NullS = Signal d
forall a. Signal a
NullS
zipWith3DF [([FiringToken a], [FiringToken b], [FiringToken c])]
rs Signal a -> Signal b -> Signal c -> [[d]]
as Signal a
xs Signal b
ys Signal c
zs = Signal d
output Signal d -> Signal d -> Signal d
forall a. Signal a -> Signal a -> Signal a
+-+ [([FiringToken a], [FiringToken b], [FiringToken c])]
-> (Signal a -> Signal b -> Signal c -> [[d]])
-> Signal a
-> Signal b
-> Signal c
-> Signal d
forall a b c d.
(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 [([FiringToken a], [FiringToken b], [FiringToken c])]
rs Signal a -> Signal b -> Signal c -> [[d]]
as Signal a
xs' Signal b
ys' Signal c
zs'
  where 
    (Signal a
xs', Signal b
ys', Signal c
zs') = if Int
matchedRule Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 then
                        (Signal a
forall a. Signal a
NullS, Signal b
forall a. Signal a
NullS, Signal c
forall a. Signal a
NullS)
                      else
                        ([FiringToken a], [FiringToken b], [FiringToken c])
-> Signal a
-> Signal b
-> Signal c
-> (Signal a, Signal b, Signal c)
forall a b c.
(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 ([FiringToken a], [FiringToken b], [FiringToken c])
rule Signal a
xs Signal b
ys Signal c
zs
    matchedRule :: Int
matchedRule     = ([([FiringToken a], [FiringToken b], [FiringToken c])]
-> Signal a -> Signal b -> Signal c -> Int
forall a b c d.
(Num a, Eq b, Eq c, Eq d) =>
[([FiringToken b], [FiringToken d], [FiringToken c])]
-> Signal b -> Signal d -> Signal c -> a
match3DF [([FiringToken a], [FiringToken b], [FiringToken c])]
rs Signal a
xs Signal b
ys Signal c
zs)
    rule :: ([FiringToken a], [FiringToken b], [FiringToken c])
rule            = [([FiringToken a], [FiringToken b], [FiringToken c])]
rs [([FiringToken a], [FiringToken b], [FiringToken c])]
-> Int -> ([FiringToken a], [FiringToken b], [FiringToken c])
forall a. [a] -> Int -> a
!! Int
matchedRule
    output :: Signal d
output          = if Int
matchedRule Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 then
                        Signal d
forall a. Signal a
NullS
                      else
                        [d] -> Signal d
forall a. [a] -> Signal a
signal ((Signal a -> Signal b -> Signal c -> [[d]]
as Signal a
xs Signal b
ys Signal c
zs) [[d]] -> Int -> [d]
forall a. [a] -> Int -> a
!! Int
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 :: [(FiringToken b, [FiringToken a])]
-> (b -> Signal a -> [b]) -> b -> Signal a -> Signal b
scanlDF [(FiringToken b, [FiringToken a])]
_  b -> Signal a -> [b]
_  b
_     Signal a
NullS   = Signal b
forall a. Signal a
NullS
scanlDF [(FiringToken b, [FiringToken a])]
fs b -> Signal a -> [b]
ns b
state Signal a
xs      = (b -> Signal b
forall a. a -> Signal a
unitS b
state) 
                              Signal b -> Signal b -> Signal b
forall a. Signal a -> Signal a -> Signal a
+-+ [(FiringToken b, [FiringToken a])]
-> (b -> Signal a -> [b]) -> b -> Signal a -> Signal b
forall a b.
(Eq a, Eq b) =>
[(FiringToken b, [FiringToken a])]
-> (b -> Signal a -> [b]) -> b -> Signal a -> Signal b
scanlDF [(FiringToken b, [FiringToken a])]
fs b -> Signal a -> [b]
ns b
state' Signal a
xs'
  where 
     xs' :: Signal a
xs'         = if Int
matchedRule Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 then
                     Signal a
forall a. Signal a
NullS
                   else
                     [FiringToken a] -> Signal a -> Signal a
forall a. Eq a => [FiringToken a] -> Signal a -> Signal a
consumeDF [FiringToken a]
rule Signal a
xs
     matchedRule :: Int
matchedRule = [(FiringToken b, [FiringToken a])] -> b -> Signal a -> Int
forall a b c.
(Num a, Eq b, Eq c) =>
[(FiringToken c, [FiringToken b])] -> c -> Signal b -> a
matchStDF [(FiringToken b, [FiringToken a])]
fs b
state Signal a
xs
     rule :: [FiringToken a]
rule        = (FiringToken b, [FiringToken a]) -> [FiringToken a]
forall a b. (a, b) -> b
snd ([(FiringToken b, [FiringToken a])]
fs [(FiringToken b, [FiringToken a])]
-> Int -> (FiringToken b, [FiringToken a])
forall a. [a] -> Int -> a
!! Int
matchedRule)
     state' :: b
state'      = if Int
matchedRule Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 then
                     String -> b
forall a. HasCallStack => String -> a
error String
"No rule matches the pattern!"
                   else
                     (b -> Signal a -> [b]
ns b
state Signal a
xs) [b] -> Int -> b
forall a. [a] -> Int -> a
!! Int
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 :: [(FiringToken b, [FiringToken a])]
-> (b -> Signal a -> [b])
-> (b -> [c])
-> b
-> Signal a
-> Signal c
mooreDF [(FiringToken b, [FiringToken a])]
_  b -> Signal a -> [b]
_  b -> [c]
_ b
_     Signal a
NullS = Signal c
forall a. Signal a
NullS
mooreDF [(FiringToken b, [FiringToken a])]
fs b -> Signal a -> [b]
ns b -> [c]
o b
state Signal a
xs    = Signal c
output Signal c -> Signal c -> Signal c
forall a. Signal a -> Signal a -> Signal a
+-+ [(FiringToken b, [FiringToken a])]
-> (b -> Signal a -> [b])
-> (b -> [c])
-> b
-> Signal a
-> Signal c
forall a b c.
(Eq a, Eq b) =>
[(FiringToken b, [FiringToken a])]
-> (b -> Signal a -> [b])
-> (b -> [c])
-> b
-> Signal a
-> Signal c
mooreDF [(FiringToken b, [FiringToken a])]
fs b -> Signal a -> [b]
ns b -> [c]
o b
state' Signal a
xs'
  where 
    xs' :: Signal a
xs'         = if Int
matchedRule Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 then
                    Signal a
forall a. Signal a
NullS
                  else
                    [FiringToken a] -> Signal a -> Signal a
forall a. Eq a => [FiringToken a] -> Signal a -> Signal a
consumeDF [FiringToken a]
rule Signal a
xs
    matchedRule :: Int
matchedRule = [(FiringToken b, [FiringToken a])] -> b -> Signal a -> Int
forall a b c.
(Num a, Eq b, Eq c) =>
[(FiringToken c, [FiringToken b])] -> c -> Signal b -> a
matchStDF [(FiringToken b, [FiringToken a])]
fs b
state Signal a
xs
    rule :: [FiringToken a]
rule        = (FiringToken b, [FiringToken a]) -> [FiringToken a]
forall a b. (a, b) -> b
snd ([(FiringToken b, [FiringToken a])]
fs [(FiringToken b, [FiringToken a])]
-> Int -> (FiringToken b, [FiringToken a])
forall a. [a] -> Int -> a
!! Int
matchedRule)
    output :: Signal c
output      = [c] -> Signal c
forall a. [a] -> Signal a
signal (b -> [c]
o b
state)
    state' :: b
state'      = if Int
matchedRule Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 then
                    String -> b
forall a. HasCallStack => String -> a
error String
"No rule matches the pattern!"
                  else
                    (b -> Signal a -> [b]
ns b
state Signal a
xs) [b] -> Int -> b
forall a. [a] -> Int -> a
!! Int
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 :: [(FiringToken b, [FiringToken a])]
-> (b -> Signal a -> [b])
-> (b -> Signal a -> [[c]])
-> b
-> Signal a
-> Signal c
mealyDF [(FiringToken b, [FiringToken a])]
_  b -> Signal a -> [b]
_  b -> Signal a -> [[c]]
_ b
_     Signal a
NullS     = Signal c
forall a. Signal a
NullS
mealyDF [(FiringToken b, [FiringToken a])]
fs b -> Signal a -> [b]
ns b -> Signal a -> [[c]]
o b
state Signal a
xs = Signal c
output Signal c -> Signal c -> Signal c
forall a. Signal a -> Signal a -> Signal a
+-+ [(FiringToken b, [FiringToken a])]
-> (b -> Signal a -> [b])
-> (b -> Signal a -> [[c]])
-> b
-> Signal a
-> Signal c
forall a b c.
(Eq a, Eq b) =>
[(FiringToken b, [FiringToken a])]
-> (b -> Signal a -> [b])
-> (b -> Signal a -> [[c]])
-> b
-> Signal a
-> Signal c
mealyDF [(FiringToken b, [FiringToken a])]
fs b -> Signal a -> [b]
ns b -> Signal a -> [[c]]
o b
state' Signal a
xs'
  where 
    xs' :: Signal a
xs'         = if Int
matchedRule Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 then
                    Signal a
forall a. Signal a
NullS
                  else
                    [FiringToken a] -> Signal a -> Signal a
forall a. Eq a => [FiringToken a] -> Signal a -> Signal a
consumeDF [FiringToken a]
rule Signal a
xs
    matchedRule :: Int
matchedRule = [(FiringToken b, [FiringToken a])] -> b -> Signal a -> Int
forall a b c.
(Num a, Eq b, Eq c) =>
[(FiringToken c, [FiringToken b])] -> c -> Signal b -> a
matchStDF [(FiringToken b, [FiringToken a])]
fs b
state Signal a
xs
    rule :: [FiringToken a]
rule        = (FiringToken b, [FiringToken a]) -> [FiringToken a]
forall a b. (a, b) -> b
snd ([(FiringToken b, [FiringToken a])]
fs [(FiringToken b, [FiringToken a])]
-> Int -> (FiringToken b, [FiringToken a])
forall a. [a] -> Int -> a
!! Int
matchedRule)
    output :: Signal c
output      = [c] -> Signal c
forall a. [a] -> Signal a
signal ((b -> Signal a -> [[c]]
o b
state Signal a
xs) [[c]] -> Int -> [c]
forall a. [a] -> Int -> a
!! Int
matchedRule)
    state' :: b
state'      = if Int
matchedRule Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 then
                    String -> b
forall a. HasCallStack => String -> a
error String
"No rule matches the pattern!"
                  else
                    (b -> Signal a -> [b]
ns b
state Signal a
xs) [b] -> Int -> b
forall a. [a] -> Int -> a
!! Int
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 :: [FiringToken a] -> Signal a -> Bool
prefixDF [] Signal a
_    = Bool
True
prefixDF [FiringToken a]
_ Signal a
NullS = Bool
False
prefixDF (FiringToken a
Wild:[FiringToken a]
ps)      (a
_:-Signal a
xs) = [FiringToken a] -> Signal a -> Bool
forall a. Eq a => [FiringToken a] -> Signal a -> Bool
prefixDF [FiringToken a]
ps Signal a
xs
prefixDF ((Value a
p):[FiringToken a]
ps) (a
x:-Signal a
xs) = if a
p a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
x then
                                    [FiringToken a] -> Signal a -> Bool
forall a. Eq a => [FiringToken a] -> Signal a -> Bool
prefixDF [FiringToken a]
ps Signal a
xs
                                  else
                                    Bool
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 :: [FiringToken a] -> Signal a -> Signal a
consumeDF [FiringToken a]
_  Signal a
NullS =  Signal a
forall a. Signal a
NullS           
consumeDF [] Signal a
xs    =  Signal a
xs
consumeDF (FiringToken a
Wild:[FiringToken a]
ts)    (a
_:-Signal a
xs)  =  [FiringToken a] -> Signal a -> Signal a
forall a. Eq a => [FiringToken a] -> Signal a -> Signal a
consumeDF [FiringToken a]
ts Signal a
xs     
consumeDF (Value a
t:[FiringToken a]
ts) (a
x:-Signal a
xs)  =  if a
t a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
x then
                                     [FiringToken a] -> Signal a -> Signal a
forall a. Eq a => [FiringToken a] -> Signal a -> Signal a
consumeDF [FiringToken a]
ts Signal a
xs
                                   else
                                     String -> Signal a
forall a. HasCallStack => String -> a
error String
"Tokens not correct"

consume2DF :: (Eq a, Eq b) => 
              ([FiringToken a], [FiringToken b]) 
           -> Signal a -> Signal b -> (Signal a, Signal b)
consume2DF :: ([FiringToken a], [FiringToken b])
-> Signal a -> Signal b -> (Signal a, Signal b)
consume2DF ([FiringToken a]
px, [FiringToken b]
py) Signal a
xs Signal b
ys = ([FiringToken a] -> Signal a -> Signal a
forall a. Eq a => [FiringToken a] -> Signal a -> Signal a
consumeDF [FiringToken a]
px Signal a
xs,
                             [FiringToken b] -> Signal b -> Signal b
forall a. Eq a => [FiringToken a] -> Signal a -> Signal a
consumeDF [FiringToken b]
py Signal b
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 :: ([FiringToken a], [FiringToken b], [FiringToken c])
-> Signal a
-> Signal b
-> Signal c
-> (Signal a, Signal b, Signal c)
consume3DF ([FiringToken a]
px, [FiringToken b]
py, [FiringToken c]
pz) Signal a
xs Signal b
ys Signal c
zs = ([FiringToken a] -> Signal a -> Signal a
forall a. Eq a => [FiringToken a] -> Signal a -> Signal a
consumeDF [FiringToken a]
px Signal a
xs,
                                    [FiringToken b] -> Signal b -> Signal b
forall a. Eq a => [FiringToken a] -> Signal a -> Signal a
consumeDF [FiringToken b]
py Signal b
ys,
                                    [FiringToken c] -> Signal c -> Signal c
forall a. Eq a => [FiringToken a] -> Signal a -> Signal a
consumeDF [FiringToken c]
pz Signal c
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 :: [[FiringToken b]] -> Signal b -> a
matchDF [[FiringToken b]]
rs Signal b
xs       =  a -> [[FiringToken b]] -> Signal b -> a
forall t a.
(Num t, Eq a) =>
t -> [[FiringToken a]] -> Signal a -> t
matchDF' a
0 [[FiringToken b]]
rs Signal b
xs
  where matchDF' :: t -> [[FiringToken a]] -> Signal a -> t
matchDF' t
_ []     Signal a
_    =  -t
1
        matchDF' t
n ([FiringToken a]
r:[[FiringToken a]]
rs) Signal a
xs   =  if [FiringToken a] -> Signal a -> Bool
forall a. Eq a => [FiringToken a] -> Signal a -> Bool
prefixDF [FiringToken a]
r Signal a
xs then
                                    t
n
                                  else
                                    t -> [[FiringToken a]] -> Signal a -> t
matchDF' (t
nt -> t -> t
forall a. Num a => a -> a -> a
+t
1) [[FiringToken a]]
rs Signal a
xs

match2DF :: (Num a, Eq b, Eq c) => 
            [([FiringToken b], [FiringToken c])]
         -> Signal b -> Signal c -> a
match2DF :: [([FiringToken b], [FiringToken c])] -> Signal b -> Signal c -> a
match2DF [([FiringToken b], [FiringToken c])]
rs Signal b
xs Signal c
ys       =  a
-> [([FiringToken b], [FiringToken c])]
-> Signal b
-> Signal c
-> a
forall t a a.
(Num t, Eq a, Eq a) =>
t
-> [([FiringToken a], [FiringToken a])]
-> Signal a
-> Signal a
-> t
match2DF' a
0 [([FiringToken b], [FiringToken c])]
rs Signal b
xs Signal c
ys
  where match2DF' :: t
-> [([FiringToken a], [FiringToken a])]
-> Signal a
-> Signal a
-> t
match2DF' t
_ [] Signal a
_ Signal a
_     =  -t
1
        match2DF' t
n (([FiringToken a]
rx, [FiringToken a]
ry):[([FiringToken a], [FiringToken a])]
rs) Signal a
xs Signal a
ys
          =  if [FiringToken a] -> Signal a -> Bool
forall a. Eq a => [FiringToken a] -> Signal a -> Bool
prefixDF [FiringToken a]
rx Signal a
xs Bool -> Bool -> Bool
&&
                [FiringToken a] -> Signal a -> Bool
forall a. Eq a => [FiringToken a] -> Signal a -> Bool
prefixDF [FiringToken a]
ry Signal a
ys 
             then
               t
n
             else
               t
-> [([FiringToken a], [FiringToken a])]
-> Signal a
-> Signal a
-> t
match2DF' (t
nt -> t -> t
forall a. Num a => a -> a -> a
+t
1) [([FiringToken a], [FiringToken a])]
rs Signal a
xs Signal a
ys

match3DF :: (Num a, Eq b, Eq c, Eq d) => 
            [([FiringToken b], [FiringToken d], [FiringToken c])]
         -> Signal b -> Signal d -> Signal c -> a
match3DF :: [([FiringToken b], [FiringToken d], [FiringToken c])]
-> Signal b -> Signal d -> Signal c -> a
match3DF [([FiringToken b], [FiringToken d], [FiringToken c])]
rs Signal b
xs Signal d
ys Signal c
zs    = a
-> [([FiringToken b], [FiringToken d], [FiringToken c])]
-> Signal b
-> Signal d
-> Signal c
-> a
forall t a a a.
(Num t, Eq a, Eq a, Eq a) =>
t
-> [([FiringToken a], [FiringToken a], [FiringToken a])]
-> Signal a
-> Signal a
-> Signal a
-> t
match3DF' a
0 [([FiringToken b], [FiringToken d], [FiringToken c])]
rs Signal b
xs Signal d
ys Signal c
zs
  where match3DF' :: t
-> [([FiringToken a], [FiringToken a], [FiringToken a])]
-> Signal a
-> Signal a
-> Signal a
-> t
match3DF' t
_ [] Signal a
_ Signal a
_ Signal a
_   = -t
1 
        match3DF' t
n (([FiringToken a]
rx, [FiringToken a]
ry, [FiringToken a]
rz):[([FiringToken a], [FiringToken a], [FiringToken a])]
rs) Signal a
xs Signal a
ys Signal a
zs 
          =  if [FiringToken a] -> Signal a -> Bool
forall a. Eq a => [FiringToken a] -> Signal a -> Bool
prefixDF [FiringToken a]
rx Signal a
xs Bool -> Bool -> Bool
&&
                [FiringToken a] -> Signal a -> Bool
forall a. Eq a => [FiringToken a] -> Signal a -> Bool
prefixDF [FiringToken a]
ry Signal a
ys Bool -> Bool -> Bool
&&
                [FiringToken a] -> Signal a -> Bool
forall a. Eq a => [FiringToken a] -> Signal a -> Bool
prefixDF [FiringToken a]
rz Signal a
zs 
             then
               t
n
             else
               t
-> [([FiringToken a], [FiringToken a], [FiringToken a])]
-> Signal a
-> Signal a
-> Signal a
-> t
match3DF' (t
nt -> t -> t
forall a. Num a => a -> a -> a
+t
1) [([FiringToken a], [FiringToken a], [FiringToken a])]
rs Signal a
xs Signal a
ys Signal a
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 :: [(FiringToken c, [FiringToken b])] -> c -> Signal b -> a
matchStDF [(FiringToken c, [FiringToken b])]
rs c
state Signal b
xs       = a -> [(FiringToken c, [FiringToken b])] -> c -> Signal b -> a
forall t a t.
(Num t, Eq a, Eq t) =>
t -> [(FiringToken t, [FiringToken a])] -> t -> Signal a -> t
matchStDF' a
0 [(FiringToken c, [FiringToken b])]
rs c
state Signal b
xs
  where matchStDF' :: t -> [(FiringToken t, [FiringToken a])] -> t -> Signal a -> t
matchStDF' t
_ [] t
_ Signal a
_     =  -t
1
        matchStDF' t
n ((FiringToken t, [FiringToken a])
r:[(FiringToken t, [FiringToken a])]
rs) t
state Signal a
xs    
          =  if [FiringToken a] -> Signal a -> Bool
forall a. Eq a => [FiringToken a] -> Signal a -> Bool
prefixDF ((FiringToken t, [FiringToken a]) -> [FiringToken a]
forall a b. (a, b) -> b
snd (FiringToken t, [FiringToken a])
r) Signal a
xs Bool -> Bool -> Bool
&& 
                FiringToken t -> t -> Bool
forall a. Eq a => FiringToken a -> a -> Bool
matchState ((FiringToken t, [FiringToken a]) -> FiringToken t
forall a b. (a, b) -> a
fst (FiringToken t, [FiringToken a])
r) t
state
             then
               t
n
             else
               t -> [(FiringToken t, [FiringToken a])] -> t -> Signal a -> t
matchStDF' (t
nt -> t -> t
forall a. Num a => a -> a -> a
+t
1) [(FiringToken t, [FiringToken a])]
rs t
state Signal a
xs  
        
matchState :: Eq a => FiringToken a -> a -> Bool
matchState :: FiringToken a -> a -> Bool
matchState FiringToken a
Wild      a
_ = Bool
True
matchState (Value a
v) a
x = a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
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)]]
-}