Opened 4 years ago

Last modified 9 months ago

#10892 new task

ApplicativeDo should use *> and <*

Reported by: simonmar Owned by: bollu
Priority: normal Milestone: 8.10.1
Component: Compiler Version: 7.11
Keywords: ApplicativeDo, newcomer Cc: ekmett, danidiaz
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: #13309 Differential Rev(s):
Wiki Page:

Description

From @ekmett:

Would it be possible to tweak the generation to use (<*) or (*>) where appropriate when the result isn't being used?

For many Applicatives this can be a massive asymptotic win in terms of sharing and/or computational cost.

When desugaring using (<*) you'd just omit any handling of the unused result instead.

(\x y -> ...) <$> foo <* bar <*> baz

corresponds to

do x <- foo
  bar
  y <- baz
  return ...

Change History (33)

comment:1 Changed 4 years ago by simonpj

Owner: set to simonmar

comment:2 Changed 4 years ago by ekmett

Here's a sketch of how this could work:

The current patch for ApplicativeDo tracks applicative "chains".

This would modify the Applicative chains you have to hold a Maybe pattern instead of a pattern or you could just check for wildcard patterns.

There are basically 3 cases for dealing with the chain of (<*>)'s we use today.

If you have a prefix of things that don't have meaningful patterns, you can bind them with (*>), just like we'd bind with (>>) before.

do foo;bar;baz; x <- quux; y <- quaffle; return (xyzzy x y)

foo *> bar *> baz *> (xyzzy <$> quux <*> quaffle)

Otherwise, once you've seen a pattern that actually matters, any subsequent missing patterns can be dropped by using (<*) or (<$).

The (<*) case is mentioned in the description.

The (<$) case happens for

foo = do
   bar
   return whatever

which becomes

foo = whatever <$ bar

This desugaring should then favor all the right things.

(*>) is typically a little cheaper than (<*). (<$) and (*>) are cheaper than (<$>) and (<*>) when usable.

comment:3 Changed 4 years ago by simonpj

Could you give a concrete example demonstrating the "massive asymptotic win". That would be highly motivating.

comment:4 Changed 4 years ago by ekmett

Consider Data.Sequence. There

(<$>) is O(n), but (<$) is O(log n).

For any Functor that is representable, which is to say there exists x such that that f a is isomorphic to x -> a, you build a 'zipping' applicative that is isomorphic to reader. For that you can show that (m *> _ = m) and (_ <* m = m). So (<*) and (*>) are O(1) while the (<*>) pays for every point used. In the case of something like

data Stream a = a :- Stream a

which is isomorphic to Natural -> a, if we look at the zipping applicative (which behaves like ZipList) such an (*>) operation is O(1), but (<*>) incurs an ongoing cost O(n) in the length of the prefix of the result stream you inspect.

Last edited 4 years ago by ekmett (previous) (diff)

comment:5 Changed 4 years ago by simonpj

Interesting. For sequences why would you say

do { ...
   ; x <- e
   ; ... }

if you were just going to discard x? Can you give a particular example of a (plausible) program whose complexity becomes asymptotically better? I bet you have some in mind.

comment:6 Changed 4 years ago by ekmett

You often do have to use

_ <- char ')'

just to avoid unused result warnings in things like parsers given a parser like

char :: Char -> Parser Char

Also, even if you just have do x; y in the ApplicativeDo encoding, nothing currently says that that will invoke (*>) over a manual expansion involving (<*>).

comment:7 Changed 4 years ago by simonpj

You understand this so much better than me. By "particular" example, I was hoping for an executable program that would run asymptotically faster under one desugaring vs the other. Or more simply, a program using <*> that would run asymptotically faster if we replaced that <*> with *>.

comment:8 Changed 4 years ago by sjcjoosten

How about a program that would turn a sequence of characters into a sequence of space-characters of the same length? Such a program could be written as part of a pretty-printer or other template-like code.

asIndentation chars = do{_<-chars;return ' '}::Seq Char

This particular example would benefit asymptotically from replacing (\_ -> pure ' ') <$> with pure ' ' <$.

On a side note, I ran into this strange (but understandable) behavior, not sure if it should be considered a bug:

Prelude Data.Sequence> :t (\x -> do{_ <- x; return x})
(\x -> do{_ <- x; return x}) :: Functor f => f t -> f (f t)
Prelude Data.Sequence> :t (\x -> do{_ <- x; pure x})
(\x -> do{_ <- x; pure x}) :: Monad m => m a -> m (m a)
Prelude Data.Sequence> :t (\x -> do{pure x})
(\x -> do{pure x}) :: Applicative f => a -> f a
Prelude Data.Sequence> :t (\x -> do{return x})
(\x -> do{return x}) :: Monad m => a -> m a

comment:9 in reply to:  8 Changed 4 years ago by rwbarton

Replying to sjcjoosten:

On a side note, I ran into this strange (but understandable) behavior, not sure if it should be considered a bug:

Prelude Data.Sequence> :t (\x -> do{_ <- x; return x})
(\x -> do{_ <- x; return x}) :: Functor f => f t -> f (f t)
Prelude Data.Sequence> :t (\x -> do{_ <- x; pure x})
(\x -> do{_ <- x; pure x}) :: Monad m => m a -> m (m a)
Prelude Data.Sequence> :t (\x -> do{pure x})
(\x -> do{pure x}) :: Applicative f => a -> f a
Prelude Data.Sequence> :t (\x -> do{return x})
(\x -> do{return x}) :: Monad m => a -> m a

This is #11607.

comment:10 Changed 4 years ago by simonmar

Some of it is addressed by #11607, but this one:

Prelude Data.Sequence> :t (\x -> do{return x})
(\x -> do{return x}) :: Monad m => a -> m a

remains as it is. Perhaps we should turn that into pure x, but it seems like a special case and could be surprising. I'm undecided here.

comment:11 Changed 4 years ago by bgamari

Milestone: 8.0.18.2.1

It's unlikely that anything will happen on this front for 8.0.

comment:12 Changed 3 years ago by simonmar

Blocking: 12143 added

comment:13 Changed 3 years ago by simonmar

See #12666 for another request with an example.

comment:14 Changed 3 years ago by simonmar

Priority: normalhigh

comment:15 Changed 3 years ago by bgamari

Milestone: 8.2.18.4.1

It doesn't sound like this will happen for 8.2. However, feel free to step up if you, the motivated reader, would like to see this.

comment:16 Changed 3 years ago by bollu

Owner: changed from simonmar to bollu

comment:17 Changed 3 years ago by RyanGlScott

Keywords: ApplicativeDo added

comment:18 Changed 3 years ago by dfeuer

We should also use liftA2 when appropriate, which can as much as halve allocation in some cases. That is ticket #13309.

comment:19 Changed 3 years ago by AaronFriel

@ekmett, @simonpj, @bgamari

I am working on this issue and have a preliminary patch that explores the design space for this. For the exploring implementation, I added a new constructor of ApplicativeArg, ApplicativeArgNil, which lacks a pattern. To explore the design space and verify my type checking, I modified the renamer to use <$ and <* (in place of fmap and <*>) if and only if every statement in the segment was an ApplicativeArgNil:

mkApplicativeStmt ctxt args need_join body_stmts
  | all isAppArgNil args
  = do { (replace_op, fvs1) <- lookupStmtName ctxt replaceFName
       ; (but_op, fvs2) <- lookupStmtName ctxt butAName
  ...

For the sake of faithfully implementing your proposed desugaring, I need to ask about this:

-- Example:
f   = do foo;bar;baz; x <- quux; y <- quaffle; return (xyzzy x y)

-- Desugaring:
f'  = foo *> bar *> baz *> (xyzzy <$> quux <*> quaffle)

Is there a reason that desugaring is strictly better than:

-- Desugaring:
f'' = xyzzy <$> (foo *> bar *> baz *> quux) <*> quaffle

I don't think it'd be too difficult to move the *> "then" operators to the beginning, but it would involve changing more of the existing applicative code to do so. I think that this style is more suited to addressing #13309.

comment:20 Changed 3 years ago by simonpj

Simon Marlow is the one who should respond here. Let's await his response.

Meanwhile, I would strongly urge you to make a careful description of what you intend to do, using the language and notation of the paper. You could put the result as a sub-page of ApplicativeDo.

Thanks for working on this!

comment:21 Changed 3 years ago by simonmar

I think they're both equivalent. Can you write down the desugaring rule?

It seems to me we can use *> for *initial* ApplicativeArgNils in the group, and <* for *trailing* ApplicativeArgNils in the group. Anything in the middle will just need to behave like a wildcard pattern. Does that seem reasonable?

comment:22 Changed 3 years ago by simonmar

Well, I suppose we can do better than that (looking at the example in the description), it should be possible to handle ApplicativeArgNil anywhere in the group.

comment:23 Changed 3 years ago by AaronFriel

Yes, I was wondering about that too. Edward writes: "(*>) is typically a little cheaper than (<*).", which suggests using the *> everywhere except in the tail, where we would use <*.

Thus:

do x <- foo
   bar
   y <- baz
   return ...

⇕

(\x y -> ...) <$> foo <*> (bar *> baz)

That is, we can merge any ApplicativeArgNil lhsExpr with a following ApplicativeArg? rhsExpr, by omitting the ApplicativeArgNil and creating a new ApplicativeArg? rhsExpr', where rhsExpr' = lhsExpr *> rhsExpr.

In cases where there is no subsequent statement, we use <*.

This rewriting has the benefit of neatly addressing adding liftA2, as ApplicativeArgNil statements will be folded into ApplicativeArgOne/ApplicativeArgMany. e.g.:

do foo
   x <- bar
   baz
   y <- quux
   quaffle
   return (xyzzy x y)

⇕

(\x y -> xyzzy x y) <$> (foo *> bar) <*> (baz *> quux) <* quaffle

⇕

liftA2 (\x y -> xyzzy x y) (foo *> bar) (baz *> quux) <* quaffle

I'm working on the syntax and desugaring rules to address this and #13309.

Last edited 3 years ago by AaronFriel (previous) (diff)

comment:24 Changed 3 years ago by simonmar

Yes, seems like a good plan. Don't forget that you can do this rewriting in the desugarer, but not before that, so getting the typing rules right might be a little tricky.

comment:25 Changed 3 years ago by AaronFriel

Given the size and substance of this change, where should I best submit the proposal? To GHC RFCs on GitHub, Phab, or elsewhere?

As well, how formal should the documentation be? Is the EBNF and functional description at the page ApplicativeDo sufficient, or should I write up a paper with a more formal description? (I lack even have undergrad degrees yet - to be completed this summer - so I've little experience actually writing and submitting papers.)

comment:26 Changed 3 years ago by simonmar

Editing the ApplicativeDo wiki page is fine. Thanks for tackling this!

comment:27 Changed 2 years ago by AaronFriel

A user ElvishJerricco on Reddit posted an interesting test case (my analysis here). There were two interesting things that popped out. Here's the reduced test case:

{-# LANGUAGE ApplicativeDo #-}

-- The type signatures and Monad constraints are optional, 
-- but helpful for -ddump-ds and -ddump-rn.
foo :: Monad f => f () -> f ()
foo f = f

bar :: Monad f => f () -> f ()
bar f = do
    _ <- f
    foo f

Clearly the two statements of bar are independent, and so we should use *> here too. The other interesting thing to me is that this doesn't trigger the ApplicativeDo desugaring at all! The desugarer outputs: bar = f >>= \_ -> foo f. So this is another thing to make sure my revised rules cover.

Last edited 2 years ago by AaronFriel (previous) (diff)

comment:28 Changed 2 years ago by Simon Marlow <marlowsd@…>

In 41f9055/ghc:

ApplicativeDo: handle BodyStmt (#12143)

Summary:
It's simple to treat BodyStmt just like a BindStmt with a wildcard
pattern, which is enough to fix #12143 without going all the way to
using `<*` and `*>` (#10892).

Test Plan:
* new test cases in `ado004.hs`
* validate

Reviewers: niteria, simonpj, bgamari, austin, erikd

Subscribers: rwbarton, thomie

GHC Trac Issues: #12143

Differential Revision: https://phabricator.haskell.org/D4128

comment:29 Changed 2 years ago by simonmar

Blocking: 12143 removed

comment:30 Changed 22 months ago by bgamari

Keywords: newcomer added
Milestone: 8.4.18.6.1
Priority: highnormal

This certainly won't happen for 8.4 but it very well may be done for 8.6 if you, the motivated reader, picks it up!

comment:31 Changed 17 months ago by bgamari

Milestone: 8.6.18.8.1

These won't be fixed for 8.6, bumping to 8.8.

comment:32 Changed 11 months ago by osa1

Milestone: 8.8.18.10.1

Bumping milestones of low-priority tickets.

comment:33 Changed 9 months ago by danidiaz

Cc: danidiaz added
Note: See TracTickets for help on using tickets.