Reflecting Code to Syntax (with Arrows)

21

I agree, arrows should have a desugaring mode like ApplicativeDo where the compiler analyses whether the bound variable isn’t used in a later statement, and then uses arr and *** (or &&&) instead of arr and first. A little bit of arr for plumbing is probably unavoidable, but the real benefit IMO is to have *** instead of first, like <*> instead of >>= in ApplicativeDo. I sometimes tinker on something like this in my spare time, but it’s much more complicated than just desugaring with first.

1 Like
22

That’s a cool paper! However, they don’t actually seem to say applicatives (idioms) are strictly weaker than arrows. They just say applicatives can be embedded into arrows, but it does not say anything about the other direction.

They do show a program that uses a state arrow which cannot be implemented by the usual state applicative:

freshName = get >>> arr (\x -> (x + 1, x)) >>> first put >>> arr snd

But using my “higher-order” applicative encoding I am able to implement that:

data State a where
  Put :: State Int -> State ()
  Get :: State Int
  Pure :: a -> State a
  Ap :: State (a -> b) -> State a -> State b

instance Functor State where
  fmap f = Ap (Pure f) 
instance Applicative State where
  pure = Pure
  (<*>) = Ap

freshName :: State Int
freshName = Get <* Put ((+ 1) <$> Get)
(and to show this free syntax does have an implementation) 
interpret :: State a -> Int -> (a, Int)
interpret (Put p) s = let (x, _) = interpret p s in ((), x)
interpret Get s = (s, s)
interpret (Pure x) s = (x, s)
interpret (Ap p q) s = let (f, s') = interpret p s
                           (x, s'') = interpret q s'
                       in (f x, s'')

Here I used the Get operation twice, which just happens to work for this simple program. However, we could generalize the Put operation to avoid that:

  Put :: (a -> Int) -> State a -> State a

freshName = snd <$> Put fst ((\x -> (x + 1, x)) <$> Get)
1 Like
23

For completeness, there’s been some recent and not-so-recent chatter on the Arrow/Monad hierarchy question

2 Likes
24

Well yes, but the cost here is that Put is higher order. The effect signature of your applicative is different than the signature of the arrow. Although applicative vs. arrow is a bit like apples vs. oranges because arrows are profunctors and not functors.

Oh, I realize I didn’t link the paper I wanted to link!

This is the one:

What I really like about that paper is that it recognises how all these “effectish” structures like applicatives, arrows and monads are also about “dynamic” and “static” scopes, like in a DSL. In the plain Haskell world, we have a static language to build up a program with effects using functors, applicatives, arrows, selectives, monads etc., and the values inside these are the dynamic values that are going to be sent around at runtime. So there really is a staged aspect to this.

The point of the paper is then that monads are completely dynamic, they blur the distinction between these two stages. Applicatives are completely static. Arrows/ArrowChoices (and also selectives, not treated in the paper) cover a middle ground by having static data flow, but _dynamic control flow. That is, you can use dynamic values coming out of an arrow to branch, but not to construct a new arrow.

In that sense, arrows are really strictly between applicatives and monads.

4 Likes
25

arrows should have a desugaring mode like ApplicativeDo

Could the same be achieved using a QualifiedProc extension, analogous to QualifiedDo? It could potentially offer more flexibility with the typeclasses that back the notation, perhaps even allowing the use of Profunctor.

1 Like
26

Yes and no.

First, you cannot straightforwardly reproduce the effects of ApplicativeDo with QualifiedDo. First, QualifiedDo does something very similar like RebindableSyntax. It just replaces >>= and pure etc. with your custom definitions. But it doesn’t change the structure of the desugared do-Block, just its building blocks. So ApplicativeDo is something quite different (and more complicated) than QualifiedDo/RebindableSyntax because it really analyses usage and changes the structure of the desugared code.

Now, it’s probably easy to generalise QualifiedDo to arrows. Already now, RebindableSyntax supports arrow notation, but it’s not that useful: The arrow desugaring is very rigid and seemingly has a lot of incidental complexity from tuple packing & unpacking, pre-/postcomposition with certain functions in order to bring everything into the right type signature. I’m not aware of any nontrivial usages of RebindableSyntax with arrows, not to the extent to what other have done with monads (like indexed monads etc.).

And still, you’re (rightfully) asking whether we can improve the way arrows are desugared. Yes, but it probably takes a bit more than just QualifiedProc. We should in the end be able to do e.g. this:

procDimap :: Profunctor a => (b -> c) -> (d -> e) -> a c d -> a b e
procDimap f g a = proc b -> do
  d <- a -< f b
  returnA -< g d

This should only require Profunctor to work, not Arrow. But as of now, Profunctor is not even a superclass of Arrow. So the first step is implementing a hierarchy proposal similar to the Functor-Applicative-Monad proposal: Arrow should have Profunctor and CartesianCategory as superclasses. Then desugaring should be able to detect those simpler cases where these two superclasses are sufficient, similar to how ApplicativeDo works.

See:

3 Likes
27

And, to go full circle and come back to what stevan said in the beginning: Oleg Grenrus’ plugin Overloaded.Categories actually achieves that to some extent! The trouble is that it’s a GHC plugin and not part of GHC source code. I believe it was too much effort to keep it working after every GHC update, so it bitrotted and doesn’t work beyond 9.0.

2 Likes