An ArrowCircuit instance for stream processors which could block

Question

The Control.Arrow.Operations.ArrowCircuit class is for:

An arrow type that can be used to interpret synchronous circuits.

I want to know what synchronous means here. I looked it up on Wikipedia, where they are speaking of digital electronics. My electronics is quite rusty, so here is the question: what is wrong (if anything is) with such an instance for the so-called asynchronous stream processors:

data StreamProcessor a b = Get (a -> StreamProcessor a b) | 
                           Put b    (StreamProcessor a b) |
                           Halt

instance Category StreamProcessor where
    id = Get (\ x -> Put x id)
  
    Put c bc . ab = Put c (bc . ab)
    Get bbc . Put b ab = (bbc b) . ab
    Get bbc . Get aab = Get $ \ a -> (Get bbc) . (aab a)
    Get bbc . Halt = Halt
    Halt . ab = Halt

instance Arrow StreamProcessor where
    ...

getThroughBlocks :: [a] -> StreamProcessor a b -> StreamProcessor a b
getThroughBlocks ~(a : input) (Get f)   = getThroughBlocks input (f a)
getThroughBlocks _input       putOrHalt = putOrHalt

getThroughSameArgBlocks :: a -> StreamProcessor a b -> StreamProcessor a b
getThroughSameArgBlocks = getThroughBlocks . repeat

instance ArrowLoop StreamProcessor where
    loop Halt               = Halt
    loop (Put (c, d) bdcd') = Put c (loop bdcd')
    loop (Get f)            = Get $ \ b -> 
         let 
            Put (c, d) bdcd' = getThroughSameArgBlocks (b, d) (f (b, d))
         in Put c (loop bdcd')

instance ArrowCircuit StreamProcessor where
    delay b = Put b id

I reckon this solution to work for us as: we want someArrowCircuit >>> delay b to be someArrowCircuit delayed by one tick with b coming before anything from it. It is easy to see we get what we want:

someArrowCircuit >>> delay b
= someArrowCircuit >>> Put b id 
= Put b id . someArrowCircuit
= Put b (id . someArrowCircuit)
= Put b someArrowCircuit

Are there any laws for such a class? If I made no mistake writing delay down, how does synchronous live alongside asynchronous?

Cannabin

I'm pretty sure the idea of synchronicity here is that each input produces a corresponding output. However, the StreamProcessor arrow isn't synchronous, which means you can't really talk about delaying by 1 tick. For instance, if you write delay a >>> someSP, it's not at all clear that the output is delayed 1 tick. If someSP has some extra Gets, it could be entirely undelayed, and if it 20 Puts per Get, then it could be delayed by 20 ticks. (Side note: the getThroughBlocks function is concerning — do the ArrowLoop laws hold here?) – Hyonhyoscine

@Hyonhyoscine sorry, I don't quite get you. First of all, what do we want delay a >>> someSP to do? someSP >>> delay a is understandable - we just push an extra value, no matter whether it's Get or Put or Halt to follow: arr ([0..] !!) waits for i and returns i, whereas arr ([0..] !!) >>> delay (-1) spits -1 out first and then works as usual. – Cannabin

@Hyonhyoscine Besides, what's wrong with getThroughBlocks? Are you speaking about getThroughSameArgBlocks in loop? I haven't checked the definition for ArrowLoop laws - which one looks shaky? – Cannabin

delay a >>> someSP would theoretically provide a as "one tick's worth" of data to someSP. In a synchronous circuit, this would allow someSP to compute "one tick's worth" of output. Keep in mind that arr for StreamProcessor does indeed create a synchronous circuit by virtue of it having Gets and Puts precisely interleaved. However, if there were 5 Puts per Get, then results would indeed by asynchronous to inputs, and delay would seem a bit strange. – Hyonhyoscine

Yes, I'm talking about getThroughSameArgBlocks. I don't know which law might break (if any), but it seems alarming to me that you're duplicating values from the input stream. – Hyonhyoscine

@Hyonhyoscine how would’ve you written loop down? I tested my snippet on processors with consts as blocks - works fine. I will put a bit more thought into testing and write another comment. As for delay, let me sleep on that :). My electronics (or whatever this is) is quite rusty, so I am not quite following straight away. Thank you! – Cannabin

Answer 1

The only law that I know of related to ArrowCircuit is actually for the similar ArrowInit class from Causal Commutative Arrows, which says that delay i *** delay j = delay (i,j). I'm pretty sure your version satisfies this (and it looks like a totally reasonable implementation), but it still feels a little strange considering that StreamProcessor isn't synchronous.

Particularly, synchronous circuits follow a pattern of a single input producing a single output. For example, if you have a Circuit a b and provide it a value of type a, then you will get one and only one output b. The "one-tick delay" that delay introduces is thus a delay of one output by one step.

But things are a little funky for asynchronous circuits. Let's consider an example:

runStreamProcessor :: StreamProcessor a b -> [a] -> [b]
runStreamProcessor (Put x s) xs = x : runStreamProcessor s xs
runStreamProcessor _ [] = []
runStreamProcessor Halt _ = []
runStreamProcessor (Get f) (x:xs) = runStreamProcessor (f x) xs

multiplyOneThroughFive :: StreamProcessor Int Int
multiplyOneThroughFive = Get $ \x -> 
  Put (x*1) $ Put (x*2) $ Put (x*3) $ Put (x*4) $ Put (x*5) multiplyOneThroughFive

Here, multiplyOneThroughFive produces 5 outputs for each input it receives. Now, consider the difference between multiplyOneThroughFive >>> delay 100 and delay 100 >>> multiplyOneThroughFive:

> runStreamProcessor (multiplyOneThroughFive >>> delay 100) [1,2]
[100,1,2,3,4,5,2,4,6,8,10]
> runStreamProcessor (delay 100 >>> multiplyOneThroughFive) [1,2]
[100,200,300,400,500,1,2,3,4,5,2,4,6,8,10]

Inserting the delay at a different point in the circuit actually caused us to produce a different number of results. Indeed, it seems as if the circuit as a whole underwent a 5-tick delay instead of just a 1-tick delay. This would definitely be unexpected behavior in a synchronous environment!

Hyonhyoscine

So, to put it short, if we put delay a at the end of the series of compositions, we would get this actual “one tick delay”, whereas if it turns up somewhere in the middle, this a may become input in some asynchronous circuit, which would use up several ticks to output. Have I got the answer right? – Cannabin

Yes, that's my thought. It's not clear that this is a bad thing! But it is worth noting. – Hyonhyoscine