Arc Forumnew | comments | leaders | submitlogin
2 points by rocketnia 1283 days ago | link | parent

In case anyone wonders what's wrong with (if ...), I've put together a demonstration of translating Arc-like code into the flavor of generalized arrows[4] David and I use for implementing this stuff:

  (if foo
    (bar baz)
    qux)
  
  
     (  |         +   |       )        |   |   |
     ( foo(true)  +  foo(nil) )       bar baz qux
  =======================Disjoin=====================
  foo(true) bar  baz  qux   +   foo(nil) bar baz qux
   |         |    |    |    +    |        |   |   |
  Drop      Drop Drop  |    +   Drop     =Apply= Drop
                       |    +               |
                       =========Merge========
                                  |
In this graph, sum types (A + B) are edges separated by + and product types (A * B) are simply juxtaposed edges. I've labeled the edges around Disjoin to show which signals go where.

The "Disjoin" operation is the distributive law on product and sum types, taking ((A + B) * C) to ((A * C) + (B * C)). In simple cases, it has to synchronize C with a combination of A and B so it knows which output to send C's packets down.

The "Merge" operation takes (A + A) to A, forgetting which branch it was on. In simple cases, it has to synchronize the original two signals becuase the output should only be inactive when both inputs are inactive. If we're using dynamic typing, we may also need to check the inputs dynamically to make sure their periods of activity don't overlap.

Overall, one call to (if ...) causes multiple synchronization points in the code.

You might wonder what Arc could use here if not (if ...), and my guess is it could use a structured data type with associated special forms that can be implemented with implicit concurrency:

  (def left (x) (annotate 'left x))
  (def right (x) (annotate 'right x))
  
  ; Sum types distribute over product types.
  ; ((A + B) * C) -> ((A * C) + (B * C))
  (disjoin (left a) c)   -->  (left (list a c))
  (disjoin (right b) c)  -->  (right (list b c))
  (disjoin other c)      -->  (err "Can't disjoin")
  
  ; Sum types are commutative.
  ; (A + B) -> (B + A)
  (mirror (left a))   -->  (right a)
  (mirror (right b))  -->  (left b)
  (mirror other)      -->  (err "Can't mirror")
  
  ; Sum types are associative.
  ; ((A + B) + C) -> (A + (B + C))
  (assocsl (left (left a)))    --> (left a)
  (assocsl (left (right b)))   --> (right (left b))
  (assocsl (right c))          --> (right (right c))
  (assocsl other)              --> (err "Can't assocsl")
  ; (A + (B + C)) -> ((A + B) + C)
  (assocsr (left a))           --> (left (left a))
  (assocsr (right (left b)))   --> (left (right b))
  (assocsr (right (right c)))  --> (right c)
  (assocsr other)              --> (err "Can't assocsr")
  
  ; (A + A) -> A
  (merge (left a))   -->  a
  (merge (right a))  -->  a
  (merge other)      -->  (err "Can't merge")
  
  ; (A -> C) -> (B -> D) -> ((A + B) -> (C + D))
  ((lift-sum l r) (left a))   -->  (left (l a))
  ((lift-sum l r) (right b))  -->  (right (r b))
  ((lift-sum l r) other)      -->  (err "Can't lift-sum")
This is quite a bundle of special forms to add, and I'm probably forgetting a few. I'm not exactly sure how to implement them, especially considering they would have to deal with Arc's arbitrary recursion. ^_^;

[4] http://www.megacz.com/berkeley/garrows/