Asynchronous Arrows need Type Specialization - Help!
I was giving Control.Arrow a try for a reactive programming system. The arrows are agents that communicate by sending and returning time-varying state. Different agents may live in different 'vats' (event-driven threads) to roughly model distributed computing. For the most part, the state varies asynchronously - i.e. a file updates at a different rate than the mouse position. Anyhow, I ran into a problem: The (***) and (&&&) operations, as specified in Control.Arrow, are inherently synchronization points. Ideally one could do something like: (a1 *** a2) >>> first a3 and the output from a1 would be piped directly as input to a3, without touching a2. However, arrows also allow: (a1 *** a2) >>> arr f And, in this case, the current state of a1 and a2 must be combined into a stream of pairs so that f may be mapped over the stream. Obtaining both streams at a single place (a single vat) and time is a synchronizing operation. The synchronization operations are severely undermining the intended scalability and performance of this agent abstraction. Now, I believe I could make it work if I could somehow specialize the arrow type with aparametric structure... A (b,b') (c,c') = A b c = But I've not been able to make the Haskell type system happy with this. Type families allow some specialization, but they don't allow ambiguity or defaults. Given the 'arr' function, I must be able to instantiate an A involving any type at all. Today I explored an alternative version of Control.Arrow, using an opaque product type specialized to the arrow, but I still bumped into the issue of specializing the arrow type for this. I don't see how GADTs would help. I've been stuck on this for a couple weeks now. Ideas would be appreciated.
David, On 21/03/2011, at 4:18 PM, David Barbour wrote:
I was giving Control.Arrow a try for a reactive programming system. The arrows are agents that communicate by sending and returning time-varying state. Different agents may live in different 'vats' (event-driven threads) to roughly model distributed computing. For the most part, the state varies asynchronously - i.e. a file updates at a different rate than the mouse position. Anyhow, I ran into a problem: The (***) and (&&&) operations, as specified in Control.Arrow, are inherently synchronization points.
Indeed. Take a look here: http://www.haskell.org/haskellwiki/Research_papers/Monads_and_arrows#Arrows In particular, "ProdArrows -- Arrows for Fudgets" by Magnus Carlsson. cheers peter
On Sun, Mar 20, 2011 at 10:18 PM, David Barbour
The (***) and (&&&) operations, as specified in Control.Arrow, are inherently synchronization points.
Ideally one could do something like:
(a1 *** a2) >>> first a3
and the output from a1 would be piped directly as input to a3, without touching a2. However, arrows also allow:
(a1 *** a2) >>> arr f
And, in this case, the current state of a1 and a2 must be combined into a stream of pairs so that f may be mapped over the stream. Obtaining both streams at a single place (a single vat) and time is a synchronizing operation. The synchronization operations are severely undermining the intended scalability and performance of this agent abstraction.
If what you mean by "synchronization" is that for every output of a1 there must be an output of a2, then YES. But if you mean that both the outputs of a1 and a2 have to be available (fully evaluated) due to the tupling, then NO, at least not in Haskell where things are evaluated lazily. Even in the former case, when the number of outputs from a1 and a2 do not match up, you can still model them as type: a1 :: a ~> [b] a2 :: c ~> [d] BTW, according to arrow laws, (a1 *** a2) >>> first a3 is equivalent to (a1 >>> a3) *** a2, does the latter look more appealing to you? If yes, I don't see where is the problem, unless you intentionally want to make them different, and then it is no longer arrow. -- Regards, Paul Liu
On 2011-03-21 01:18, David Barbour wrote:
I was giving Control.Arrow a try for a reactive programming system. The arrows are agents that communicate by sending and returning time-varying state. Different agents may live in different 'vats' (event-driven threads) to roughly model distributed computing. For the most part, the state varies asynchronously - i.e. a file updates at a different rate than the mouse position. Anyhow, I ran into a problem: The (***) and (&&&) operations, as specified in Control.Arrow, are inherently synchronization points.
Hughes's remark in his original paper may be relevant: "In a deep sense, then, the Either type behaves more like a product than the pair type does, when we work with stream processors. And indeed, a channel carrying a sum type corresponds much more closely to a pair of channels than does a channel carrying pairs."
participants (4)
-
David Barbour -
Paul L -
Peter Gammie -
Scott Turner