14
$\begingroup$

A while ago on lambda-the-ultimate, several times in fact, arrows - a concept related to/generalising monads came up.

At least one person (I think it was this one) felt they were a significant improvement over monads and worth basing a language around.

I don't know if any such langauges have ever been implemented.

What would be the advantages of including arrows as a first class concept?

What could be the limitations of basing a language around them?

$\endgroup$
1
  • 1
    $\begingroup$ GHC Haskell is an example of such a language. This is not used too often though, in my experience. You do not need that extension to use arrows, but it provides a nicer syntax (like the relationship between do notation and monads). Similar to Monads, Haskell has a type class for Arrows $\endgroup$ Jul 6, 2023 at 2:18

1 Answer 1

13
$\begingroup$

Why arrows?

Arrows, like monads, are a way to model effectful computations. Indeed, their relationship to monads is so significant that it can be helpful to understand arrows through the ways they differ from monads. I will therefore assume a familiarity with monadic programming in this answer, as plenty of resources on monadic programming already exist.

The limitations of monads

The monadic approach to modeling imperative computations has been exceedingly successful. Its interface is very small—just pure and >>=—yet it can express a great many things. To motivate arrows, it’s worth noting what things the monadic interface does not explicitly provide:

  • There is no explicit representation of branching or choice. Monadic branching can be implemented as a derived operator, using the non-monadic if ... then ... else from the host language:

    ifM :: Monad m => m Bool -> m a -> m a -> m a
    ifM cond_m then_m else_m = cond_m >>= \cond -> if cond then then_m else else_m
    
  • There is no explicit representation of looping. Monadic iteration can be implemented as a derived operator in terms of non-monadic recursion:

    forM :: Monad m => [a] -> (a -> m b) -> m [b]
    forM []     _ = pure []
    forM (x:xs) f = do
      y  <- f x
      ys <- forM xs f
      pure (y:ys)
    
  • The program structure is always fully sequenced. That is, every operation of the monadic language is always placed into an explicit, linear ordering. When we write the expression

    do x <- computeX
       y <- computeY
       computeZ x y
    

    there is no explicit data dependency between the computation of x and y. In many programs, it would be possible to run the computations in either order, or even in parallel! But the monadic interface fundamentally places an ordering on each action executed, since they must be sequenced via >>=.

In most cases, these are all fine, and in fact they are arguably desired. Being able to reuse operations from the host language is convenient and economical, and providing a total ordering on operations is precisely what allows monads to model effectful, imperative computations where order of evaluation is fixed. However, in some cases, these choices can actually be counterproductive. Here are a few things that you can’t do using a monadic approach.

Instrumenting computation structure

Suppose you want to collect statistics about how often each conditional branch in a program is taken (and which direction it takes). This can’t be done automatically via the monadic interface because branching is done by the native if ... then ... else, so there’s no way to “hook into” branching.

Similarly, suppose you want to collect statistics about which parts of a computation are run most often so that you can generate a profile that lists all the hottest code paths. Intuitively, you’d want the body of a loop to be considered “the same computation” no matter how many times it’s run, but this is actually impossible to do automatically, because the loop body is a function that produces a monadic action (it has type a -> m b). Therefore, even if your monad supports some form of equality, you’re still stuck, because you can’t compare functions for equality.

Analyzing computation structure

Suppose you have a parser that consumes tokens, and you’d like to get a list of all the different tokens the parser accepts without running the parser. This might seem possible to do automatically because you have a primitive with a type like this:

consumeToken :: Token -> ParseM ()

It seems as though you ought to be able to implement ParseM so that each parser is annotated with the set of all tokens it can potentially consume:

data ParseM a = ParseM
  { acceptedTokens :: Set Token
  , parserFunction :: [Token] -> Either ParseError ([Token], a)
  }

consumeToken :: Token -> ParseM ()
consumeToken expected = ParseM
  { acceptedTokens = Set.singleton expected
  , parserFunction = \input -> case input of
      (actual:rest) | actual == expected -> Right (rest, ())
      _                                  -> Left (ExpectedToken expected)
  }

However, if you actually attempt to implement >>= on this ParseM type, you’ll find that you run into a problem: how do you compute the acceptedTokens field? The problem is that >>=’s second argument is an arbitrary function, so it’s impossible to know what it will return without calling it, and calling it requires the previous parser’s result.

Another way of thinking about this is that monadic computations are extremely dynamic: the structure of the computation depends on values produced by earlier computations! This is a little bit surprising because we know that we’re not actually generating new code at runtime, so the set of possible code paths is statically known. However, nothing prevents us from writing something like this:

do next_expected <- parseSomething
   consumeToken next_expected

Here, the argument to consumeToken really does depend on the results of a previous computation, which could be arbitrarily complicated. So if we want to know all the tokens potentially accepted by a given parser, the monadic interface is actually a little too expressive!

Avoiding recomputation

Suppose you have an expensive computation that you repeatedly re-run with slightly modified inputs (like, say, a typechecker), and you’d like to avoid recomputing the result for parts of the input that didn’t change. Perhaps you’d like to add an operator with the following type:

cached :: Eq a => (a -> CacheM b) -> a -> CacheM b

The idea here is that writing cached f will behave just like f, but it will automatically cache its result so that it can avoid recomputing it on the next iteration if its input hasn’t changed. Unfortunately, there is nothing ensuring that the cached function doesn’t depend on earlier computation in ways that aren’t reflected in its argument. For example, we can write this:

do x <- computeSomething

   let expensiveOperation y = do
         z <- expensiveOperation1 y
         expensiveOperation2 x z

   y <- computeSomethingElse
   (cached expensiveOperation) y -- parens for clarity

The intent here is that expensiveOperation is known to be expensive, so we want to cache it. But we’ve overlooked the fact that expensiveOperation actually closes over x, which is the result of a previous computation, and therefore it must be recomputed if x changes, even if y does not. However, cached cannot possibly know about x, so we’ll end up caching too much.

Even if we ignored this problem, it’s not clear how we’d actually implement cached so that the state is properly persisted across invocations. How do we know that “the same” piece of code (the function passed to cached) is running on the next iteration? We run into the same “analyzing hot loops” problem mentioned above.

When monads are too much

As the above examples hopefully illustrate, the problems monadic approaches tend to run into are usually not that monads are insufficient, but that they’re actually a little too powerful. We want to be able to analyze the structure of a computation without running it, and this requires a more restrictive way of expressing computation. Fundamentally, >>= is just far too dynamic for these use cases: it allows the remainder of any computation to be computed on the fly from the results of all computation up to that point.

Introducing arrows

To perform the sorts of things listed above, we need a different set of building blocks. The building blocks will be somewhat less convenient to work with when writing programs, but that’s sort of the point: we want to trade some convenience when writing computations to gain some ability to inspect computations.

The key insight behind arrows comes from the following observation: it’s impossible to analyze the structure of a monadic function a -> m b without applying it because functions are opaque—the only thing we can do with one is apply it. Therefore, we cannot use arbitrary functions. Instead, we need to build our computation out of “function-like values” that are not opaque—we must be able to do more than just apply them.

Arrows are precisely these “function-like values”, and they have the following interface:

class Arrow p where
  arr   :: (a -> b) -> p a b
  (>>>) :: p a b -> p b c -> p a c
  (***) :: p a1 a2 -> p b1 b2 -> p (a1, b1) (a2, b2)
  (+++) :: p a1 a2 -> p b1 b2 -> p (Either a1 b1) (Either a2 b2)

(In reality the interface is arranged slightly differently in Haskell, but this is a valid simplification.)

If you’re familiar with monadic programming, you can understand arr and >>> as analogous to pure and >>=. Just as pure lifts a pure value into a monadic computation, arr lifts a pure function into an arrow. And just as >>= sequences monadic actions, >>> sequences arrows.

However, there is a crucial difference between >>= and >>>, and this is where all the magic comes from! The second argument to >>= has that horrible a -> m b type that we can’t look inside, but the function wrapper is unnecessary in the second argument to >>> because arrows are already function-like. This means the second argument to >>> cannot depend on the result of its first argument—it must be statically-known.

To see how severely this impacts using arrows in practice, consider the ifM definition we wrote above in terms of >>=. Remarkably, we cannot write an analogous ifA function in terms of arr and >>> alone! Try to do it yourself if you find this hard to believe: you’ll find that the arrow interface stratifies a computation into two levels, the “outer level” of constructing the computation, and the “inner level” of actually applying the computation to a value.

As you may be able to guess by now, the (***) and (+++) operations provide the remedy to this severe restriction in expressiveness. (***) is used to represent a sort of “fork–join” step in the computation, where two fields of a value are independently processed and recombined. Its dual, (+++), represents branching, so it is (+++) that allows us to implement ifA:

ifA :: Arrow p => p a Bool -> p a b -> p a b -> p a b
ifA cond_a then_a else_a =
      arr (\x -> (x, x))
  >>> (arr id *** cond_a)
  >>> arr (\(x, cond) -> if cond then Left x else Right x)
  >>> (then_a +++ else_a)
  >>> arr (\case { Left x -> x; Right x -> x })

Note a couple things about this definition:

  • We still used if ... then ... else inside of an opaque function to scrutinize the Bool, but only to convert it to an Either. The use of (+++) is what actually selects which subcomputation to run, and this is not opaque.

  • It is completely miserable to read or to write.

Let’s talk about that second point.

Why programming with arrows is so painful

The arrows API does technically allow us to express essentially all of the things we’d like to be able to express, but actually using it feels a little like a Turing tarpit. Expressing almost anything is remarkably miserable, to the point that the “callback hell” style that arises in monadic programming—even without do notation!—seems downright pleasant in comparison. Why is it so bad?

One way to view it is that programming with arrows is mandatory point-free programming. Arrows are “function-like things”, but we have special syntax for functions in the form of lambda expressions. This syntax is what allows us to give names to the arguments to a function, and it also lets us pull the arguments apart via pattern-matching. We can then refer to these names in the body, which is just an ordinary expression, and that expression can use all the usual features of expressions, such as case ... of or if ... then ... else.

Without additional help from the compiler, arrows provide none of that. Writing monadic code without do notation still allows all the nice features of functions to be used, but writing arrow code without specialized arrow notation is a unique sort of hell. This is why language support is essentially mandatory to make arrows practical, and it is as essential to understanding arrows as the primitives themselves.

Introducing arrow notation

Lambda expressions are the special notation used for writing functions, so arrow notation is a special notation used for writing arrows. (Incidentally, functions are also arrows, so arrow notation can be used to write ordinary functions, too. But arrow notation is more restrictive because it must work with any arrow, so you don’t have much reason to do that.)

This answer is already exceptionally long, and explaining all of the features of arrow notation would make it even longer, so I am not going to do that. Fortunately, I already wrote a lengthy description of arrow notation elsewhere, so read that if you want the gory details! However, for now, let me just illustrate that it allows simplifying our ifA definition to the following:

ifA :: Arrow p => p a Bool -> p a b -> p a b -> p a b
ifA cond_a then_a else_a = proc x ->
  cond <- cond_a -< x
  if cond then then_a -< x else else_a -< x

This is considerably less vomit-inducing.

Note, however, that arrow notation is not magic: ultimately each usage of arrow notation must be transformed by the compiler into the point-free definition given above. This is not always trivial, as the arrow API quite intentionally lacks any way to express lexical closure—that is, the input of every arrow must by explicitly provided; they can’t close over local definitions. This means that, in practice, compiling arrow notation is a lot like compiling closures via lambda lifting.

For this reason, while arrow notation is an enormous improvement over point-free combinator soup, it is still significantly more restrictive than writing non-arrow code. It must always be possible to express the computation in the stratified, two-level way that arrows require: the results of earlier computations must not be required to determine the structure of the computation graph. In some cases, this requirement can be significantly more painful to adhere to than you might expect.

What did we gain?

Given how much trouble arrows make us go to, it’s worth remembering what we gain from using them: all of the examples of things monads can’t do mentioned earlier in this answer. Whether you find this sufficiently compelling is ultimately a matter of opinion. In my experience, for many programmers, the answer is “definitely not”.

Arrow notation can be a very nice feature to have in a programming language when you really want it. I have used arrow notation in a production codebase, and I personally felt its benefits were worth the mental overhead. However, again, this will naturally vary from programmer to programmer.

As a final point, I’d like to return to the text of your question. In it, you write the following:

At least one person felt [arrows] were a significant improvement over monads and worth basing a language around. I don't know if any such langauges have ever been implemented.

What would be the advantages of including arrows as a first class concept?

It’s not entirely clear to me what this means. Does having arrow notation count as “including arrows as a first class concept”? It seems unlikely that it counts as “basing a language around them”.

It is perhaps worth keeping in mind that Haskell is by no means “based around monads”, it just so happens that monads are a useful structure for modeling a particular type of problem that programmers frequently have. In cases where monads are sufficient to solve a problem, they are unambiguously simpler, easier to reason about, easier to implement, and more expressive than arrows. An arrow can be formed from any monad, and the arrow interface can be extended slightly to be equally expressive as monads, but then you lose the very reason you would pick arrows! Their whole advantage is that they are a different compromise from monads for when you have a different problem. They are not really in competition with each other.

In Haskell, arrows were initially very popular for a while, but their popularity has largely faded. The difficulties of working with them motivated people to come up with alternative abstractions, like applicative functors, which provide simpler solutions to some of the problems arrows were originally developed to solve. However, arrows have not disappeared completely, as sometimes you really do just have the problem arrows solve. Whether those problems are frequent enough to support in your language is up to you.

$\endgroup$
4
  • $\begingroup$ Great answer, but I think you should add the qualifier "effectful, ordered, imperative" to "computations" already in your first sentence. Also the section on "arrow notation" should make clear in the very beginning (or even in the heading) that you're talking about arrow notation for Haskell specifically. $\endgroup$
    – Bergi
    Jul 13, 2023 at 19:09
  • $\begingroup$ @Bergi Do you know of arrow notation (or arrows more generally, really) being used in practice outside of Haskell? If so, I think it would add to this answer. (I am not aware of any such uses.) $\endgroup$
    – Alexis King
    Jul 13, 2023 at 19:16
  • $\begingroup$ I've not seen it anywhere else either (and definitely not in practice), but I wouldn't make it sound like this is the one and only true arrow notation. Different syntax would certainly be possible, no? $\endgroup$
    – Bergi
    Jul 13, 2023 at 19:25
  • $\begingroup$ @Bergi Technically, yes, it would be theoretically possible, but I think any notation for this particular API is going to end up looking pretty intensely similar. Sure, there might be some syntactic differences, but it’s hard to imagine the fundamental structure looking terribly different! $\endgroup$
    – Alexis King
    Jul 13, 2023 at 19:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .