Portability | tested on GHC only |
---|---|
Stability | experimental |
Maintainer | Noam Lewis <jones.noamle@gmail.com> |
Framework for expressing monadic actions that require initialization and finalization. This module provides a functional interface for defining and chaining a series of processors.
Motivating example: in the IO monad, bindings to C libraries that use functions such as: f(foo *src, foo
*dst), where the pointer dst
must be pre-allocated. In this case we normally do:
foo *dst = allocateFoo(); ... while (something) { f(src, dst); ... } releaseFoo(dst);
You can use the runUntil
function below to emulate that loop.
Processor is an instance of Category, Functor, Applicative and Arrow.
In addition to the general type
, this module also defines (and gives a semantic model
for) Processor
m a b
, which has synonym Processor
IO a b
.
IOProcessor
a b
- data Processor m a b where
- type IOProcessor a b = Processor IO a b
- type IOSource a b = Processor IO a b
- type IOSink a = IOProcessor a ()
- processor :: Monad m => (a -> x -> m x) -> (a -> m x) -> (x -> m b) -> (x -> m ()) -> Processor m a b
- chain :: Processor m a b' -> Processor m b' b -> Processor m a b
- parallel :: Processor m a b -> Processor m c d -> Processor m (a, c) (b, d)
- forkJoin :: Processor m a b -> Processor m a b' -> Processor m a (b, b')
- empty :: Monad m => Processor m a a
- split :: Functor f => f a -> f (a, a)
- (--<) :: (Functor (cat a), Category cat) => cat a a1 -> cat (a1, a1) c -> cat a c
- run :: Monad m => Processor m a b -> a -> m b
- runUntil :: Monad m => Processor m a b -> a -> (b -> m Bool) -> m b
- runWith :: Monad m => (m b -> m b') -> Processor m a b -> a -> m b'
- wrapProcessor :: Monad m => (a -> x -> m x) -> (c -> x -> m x) -> (a -> m x) -> (x -> m b) -> (x -> m d) -> (x -> m ()) -> Processor m b c -> Processor m a d
- trace :: Show a => IOProcessor a a
- scanlT :: Monad m => m t -> (b -> b -> t -> c -> c) -> c -> Processor m a b -> Processor m a c
- differentiate :: (VectorSpace v, Fractional (Scalar v), Monad m) => m (Scalar v) -> Processor m a v -> Processor m a v
- integrate :: (VectorSpace v, Fractional (Scalar v), Monad m) => m (Scalar v) -> Processor m a v -> Processor m a v
- maxP :: (Ord b, Monad m) => m t -> b -> Processor m a b -> Processor m a b
- minP :: (Ord b, Monad m) => m t -> b -> Processor m a b -> Processor m a b
- nStepsMemory :: Monad m => Int -> ([(t, b)] -> c) -> (t, b) -> c -> m t -> Processor m a b -> Processor m a c
- holdMaybe :: (Num t, Monad m) => b -> m t -> Processor m a (Maybe b) -> Processor m a (b, t)
- revertAfterT :: (Monad m, Ord t) => t -> b -> Processor m a (b, t) -> Processor m a b
- discreteConv :: VectorSpace a => [Scalar a] -> [a] -> a
- fir :: (Monad m, Fractional (Scalar v), VectorSpace v) => [Scalar v] -> t -> m t -> Processor m a v -> Processor m a v
Documentation
data Processor m a b whereSource
The type of Processors
-
a
,b
= the input and output types of the processor (think a -> b) - x = type of internal state (existentially quantified)
The arguments to the constructor are:
-
a -> x ->m x
- Processing function: Takes input and internal state, and returns new internal state. -
a -> m x
- Allocator for internal state (this is run only once): Takes (usually the first) input, and returns initial internal state. -
x -> m b
- Convertor from state x to output b: Takes internal state and returns the output. -
x -> m ()
- Releaser for internal state (finalizer, run once): Run after processor is done being used, to release the internal state.
TODO: re-define in terms that don't need the x
existential (and the allocator), using a
continuation-style processing function.
type IOProcessor a b = Processor IO a bSource
The semantic model for IOProcessor
is a function:
[[ 'IOProcessor' a b ]] = a -> b
To satisfy this model, the Processor value (the implementation) must obey the rules:
- The processing function (
a -> x -> m x
) must act as if purely, so that indeed for a given input the output is always the same. One particular thing to be careful with is that the output does not depend on time (for example, you shouldn't use IOProcessor to implement an input device). TheIOSource
type is defined exactly for time-dependent processors. For pointer typed inputs and outputs, see next law. - For processors that work on pointers,
[[ Ptr t ]] = t
. This is guaranteed by the following implementation constraints forIOProcessor a b
: - If
a
is a pointer type (a = Ptr p
), then the processor must NOT write (modify) the referenced data. - If
b
is a pointer, the memory it points to (and its allocation status) is only allowed to change by the processor that created it (in the processing and releasing functions). In a way this generalizes the first constraint.
Note, that unlike Yampa, this model does not allow transformations of the type (Time -> a) -> (Time ->
b)
. The reason is that I want to prevent arbitrary time access (whether causal or not). This limitation
means that everything is essentially point-wise in time. To allow memory-full operations under this
model, scanlT
is defined. See http://www.ee.bgu.ac.il/~noamle/_downloads/gaccum.pdf for more about
arbitrary time access.
type IOSource a b = Processor IO a bSource
is the type of time-dependent processors, such that:
IOSource
a b
[[ 'IOSource' a b ]] = (a, Time) -> b
Thus, it is ok to implement a processing action that outputs arbitrary time-dependent values during runtime
regardless of input. (Although the more useful case is to calculate something from the input a
that is
also time-dependent. The a
input is often not required and in those cases a = ()
is used.
Notice that this means that IOSource doesn't qualify as an IOProcessor
. However, currently the
implementation does NOT enforce this, i.e. IOSource is not a newtype; I don't know how to implement it
correctly. Also, one question is whether primitives like chain will have to disallow placing IOSource
as the second element in a chain. Maybe they should, maybe they shouldn't.
type IOSink a = IOProcessor a ()Source
TODO: What's the semantic model for
?
IOSink
a
processor :: Monad m => (a -> x -> m x) -> (a -> m x) -> (x -> m b) -> (x -> m ()) -> Processor m a bSource
TODO: do we need this? we're exporting the data constructor anyway for now, so maybe we don't.
chain :: Processor m a b' -> Processor m b' b -> Processor m a bSource
Chains two processors serially, so one feeds the next.
parallel :: Processor m a b -> Processor m c d -> Processor m (a, c) (b, d)Source
A processor that represents two sub-processors in parallel (although the current implementation runs them sequentially, but that may change in the future)
forkJoin :: Processor m a b -> Processor m a b' -> Processor m a (b, b')Source
Constructs a processor that: given two processors, gives source as input to both processors and runs them independently, and after both have have finished, outputs their combined outputs.
Semantic meaning, using Arrow's (&&&) operator: [[ forkJoin ]] = &&& Or, considering the Applicative instance of functions (which are the semantic meanings of a processor): [[ forkJoin ]] = liftA2 (,) Alternative implementation to consider: f &&& g = (,) & f * g
empty :: Monad m => Processor m a aSource
The identity processor: output = input. Semantically, [[ empty ]] = id
split :: Functor f => f a -> f (a, a)Source
Splits (duplicates) the output of a functor, or on this case a processor.
(--<) :: (Functor (cat a), Category cat) => cat a a1 -> cat (a1, a1) c -> cat a cSource
'f --< g' means: split f and feed it into g. Useful for feeding parallelized (***'d) processors. For example, a -- (b *** c) = a >> (b &&& c)
run :: Monad m => Processor m a b -> a -> m bSource
Runs the processor once: allocates, processes, converts to output, and deallocates.
runUntil :: Monad m => Processor m a b -> a -> (b -> m Bool) -> m bSource
Keeps running the processing function in a loop until a predicate on the output is true. Useful for processors whose main function is after the allocation and before deallocation.
runWith :: Monad m => (m b -> m b') -> Processor m a b -> a -> m b'Source
Runs the processor once, but passes the processing + conversion action to the given function.
wrapProcessor :: Monad m => (a -> x -> m x) -> (c -> x -> m x) -> (a -> m x) -> (x -> m b) -> (x -> m d) -> (x -> m ()) -> Processor m b c -> Processor m a dSource
Creates a processor that operates around an inner processor.
Useful for sharing resources between two actions, a pre and a post action.
The outer processor has two processing functions, pre: a->b
and post: c->d
. The last argument is the
inner processor, Processor b c
. Thus, the resulting processor takes the a
, processes it into a b
,
feeds that through the inner processor to get a c
, and finally post-processes the c
into a d
.
Example scenario: A singleton hardware device context, that cannot be duplicated or allocated more than once. You need to both read and write to that device. It's not possible to create two processors, one for reads and one for writes, because they need to use the same allocation (the device context). With wrapPrcessor you can have the read as the pre-processing and write as the post-processing. Let's call the result of calling wrapProcessor except the last argument, myDeviceProcessor. Thus, you have:
[[ myDeviceProcessor innerProc ]] = read >>> innerProc >>> write
TODO: Find a more general / elegant solution to the shared resource problem.
trace :: Show a => IOProcessor a aSource
scanlT :: Monad m => m t -> (b -> b -> t -> c -> c) -> c -> Processor m a b -> Processor m a cSource
scanlT provides the primitive for performing memory-full operations on time-dependent processors, as | described in http://www.ee.bgu.ac.il/~noamle/_downloads/gaccum.pdf.
Untested, and also doesn't implement the limit as dt -> 0 part of the model. Currently the precision of the approximation is set by the samplerate (how many times per second the resulting processor is run, the more the better for precision).
scanlT and all its uses are probably most (or only?) useful in the context of Processor IO. However for generality it is defined here on arbitrary Processor m.
The Processor m a b
argument should really be time-dependent during runtime, so it's model can't be a ->
b
. Thus it is most logical to use only IOSource
types for the processor argument.
differentiate :: (VectorSpace v, Fractional (Scalar v), Monad m) => m (Scalar v) -> Processor m a v -> Processor m a vSource
Differentiate of time-dependent values, using scanlT
integrate :: (VectorSpace v, Fractional (Scalar v), Monad m) => m (Scalar v) -> Processor m a v -> Processor m a vSource
Integration of time-dependent values, using scanlT
, implemented by trapezoidal approximation.
maxP :: (Ord b, Monad m) => m t -> b -> Processor m a b -> Processor m a bSource
Running maximum of a processor's values
minP :: (Ord b, Monad m) => m t -> b -> Processor m a b -> Processor m a bSource
Running minimum of a processor's values
nStepsMemory :: Monad m => Int -> ([(t, b)] -> c) -> (t, b) -> c -> m t -> Processor m a b -> Processor m a cSource
holdMaybe :: (Num t, Monad m) => b -> m t -> Processor m a (Maybe b) -> Processor m a (b, t)Source
Holds a Maybe-valued processor and reports the time passed since last value was seen.
revertAfterT :: (Monad m, Ord t) => t -> b -> Processor m a (b, t) -> Processor m a bSource
Given a holdMaybe
-type processor, reverts back to a default value if no input was
seen for more than a given time limit
discreteConv :: VectorSpace a => [Scalar a] -> [a] -> aSource
fir :: (Monad m, Fractional (Scalar v), VectorSpace v) => [Scalar v] -> t -> m t -> Processor m a v -> Processor m a vSource
Finite impulse response