*Ross Paterson,
26th January 1999.*

John Hughes
has defined a new abstract view of computation,
in his (currently draft) paper
*Generalising Monads to Arrows*.
That paper uses a point-free style.
This proposal introduces a notation for arrows similar to the existing
`do` notation, with a semantics also defined by translation
into the core language.
Some familiarity with the arrows paper is assumed.
Comments welcome.

To illustrate the similarity with `do` notation,
here is a reformulation of the interpreter from the arrows paper
(think of ``proc`' as an extended lambda):

eval (Var s) = proc env -> returnA (lookup s env) eval (Add e1 e2) = proc env -> ~(Num u) <- eval e1 env ~(Num v) <- eval e2 env returnA (u + v) eval (If e1 e2 e3) = proc env -> ~(Bl b) <- eval e1 env if b then eval e2 env else eval e3 env eval (Lam x e) = proc env -> returnA (Fun (proc v -> eval e ((x,v):env))) eval (App e1 e2) = proc env -> ~(Fun f) <- eval e1 env v <- eval e2 env f v returnA :: Arrow a => a b b returnA = arr id

Though the syntax resembles `do` notation,
the translation to core Haskell is a bit more convoluted.

`proc` is a new reserved word.

Add the productions

exp-> ... | procpat-> {stmts[;] }stmts->fexpaexp|pat<-fexpaexp;stmts| letdecllist;stmts| ifexpthenstmtselsestmts| caseexpof {salt; ... ;_{1}salt[;] }_{n}salt->pat->stmts

Unlike the `do` case,
it is necessary to treat conditionals specially,
as will become clear in the translation.
(I have omitted guards from the `case` for simplicity.
Adding them doesn't raise any extra issues.)

Note also that a juxtaposition *fexp aexp* does not
denote application in the above contexts.
(Perhaps that's too tricky, and some extra syntax would be more honest.
Another glitch is that composition of arrows reads from left to right,
so perhaps pseudo-application should too.)

The following equations define a naive translation into current Haskell.
There is plenty of scope for improvement,
for example by assuming that `arr` preserves composition,
dead variable elimination, simplifying patterns and so on.

The first step is to eliminate head patterns that could fail. These are replaced by failure-free patterns (defined as in Haskell 1.4):

procp-> {s} = proc x -> case x ofp-> {Flatten(p)<- arr (\p->Flatten(p)) x ;s} _ -> zeroArrow x

where *Flatten(p)* is a failure-free pattern with the same irrefutable
subpatterns as *p*.
One way to do this is by replacing all non-unique constructors with tuples,
e.g. *Flatten(y:ys)* could be `(y,ys)`.

(Note that this translation requires an arrow in both `ArrowChoice`
and `ArrowZero`.
A Haskell-98-style definition would only eliminate the `ArrowZero`,
while changing the `Arrow` class.)

From here on, the head pattern is assumed to be failure-free.

As noted above, juxtaposition of expressions is not application. It translates to the arrow version of application:

procp-> {fe} = arr (\p-> (f,e)) >>> app

This requires that the arrow belongs to `ArrowApply`
(and is thus equivalent to a monad).
However, if *f* does not use the variables of *p*,
the following may be used instead:

procp-> {fe} = arr (\p->e) >>>f

In this case, any arrow is allowed.

The binding construct for arrows requires some plumbing:

procp-> {p'<-fe;s} = arr (\ x -> (x,x)) >>> first (procp->fe) >>> (proc (p',p) -> {s})

Local definitions are also possible, but they are not as useful here
as in `do` expressions:

procp-> { letdecllist;s} = arr (\ p -> letdecllistin (p',p)) >>> (proc (p',p) -> {s})

where *p'* is a tuple of the variables defined in *decllist*.
Note that in contrast to `do` expressions,
these variables are monomorphic.
(This can be fixed with a messy translation using first class polymorphism.)

As noted above, conditionals require special translations.
As one might expect, they require that the arrow is an `ArrowChoice`:

procp-> { ifethenselse_{1}s} = arr (\_{2}p-> ifethen Leftpelse Rightp) >>> (procp-> {s}) ||| (proc_{1}p-> {s})_{2}

The translation of `case` is more of the same
(assuming that `|||` is right-associative):

procp-> { caseeof {p->_{1}s; ... ;_{1}p->_{n}s} } = arr (\_{n}p-> caseeofp-> Left (_{1}p,Flatten(p) ..._{1})p-> Right_{n-1}^{n-2}(Left (p,Flatten(p))_{n-1})p-> Right_{n}^{n-1}(p,Flatten(p)) >>> (proc (_{n})p,Flatten(p) -> {_{1})s}) ||| ... ||| (proc (_{1}p,Flatten(p) -> {_{n})s})_{n}

Of course the if-then-else could be treated as a special case:

procp-> { ifethenselse_{1}s} = proc_{2}p-> { caseeof { True ->s; False ->_{1}s} }_{2}

though this yields a worse naive translation.