Add deriving via Generically/Generically1 by sjoerdvisscher · Pull Request #316 · tweag/linear-base

sjoerdvisscher · 2021-02-25T16:46:13Z

I think the Traversable instances nicely show the difference between traversing with linear control Applicatives and linear data Applicatives. (I'm planning to write a blogpost about this part.)

The linear control Functor generics are a bit more complicated, since you need to prove that the mapping function is used exactly once, which means having Par1 exactly once. My approach has some runtime overhead, maybe there's a better way?

aspiwack · 2021-02-26T08:26:42Z

I'm not really very comfortable with this, until Generic actually exposes linear functions. Maybe we could have deriving via stuff, so that we can hide this capability behind a module named OmgDangerWillRobinsonHereBeDragons.Generic. Because it probably mostly works. But is not technically legal.

Also, one quick question: why does Control.Functor require a GFunctor class, but in Data.Functor you seem to reuse the Functor class on the representation?

sjoerdvisscher · 2021-02-26T09:46:11Z

Using deriving via is actually a really good idea, I don't like the default signatures way.

Control.Functor needs a separate class because I need to prove that the mapping function is used only once. This doesn't work f.e. for Control.Functor:

instance (Functor f, Functor g) => Functor (f :*: g) where
  fmap f (l :*: r) = fmap f l :*: fmap f r

because f needs to be used linearly. GFunctor threads the f through, starting out as One (a %1-> b) and switching to Zero (a %1-> b) once it is used.

Par1 is where this happens:

instance GFunctor One Zero Par1 where
  gmap (One f) (Par1 a) = (Par1 (f a), Zero)

And for the product instance you see the threading happening:

instance (GFunctor i m l, GFunctor m o r) => GFunctor i o (l :*: r) where
  gmap f (l :*: r) = gmap @i @m f l & \case
    (l1, f') -> gmap @m @o f' r & \case
      (r1, f'') -> (l1 :*: r1, f'')

aspiwack · 2021-02-26T10:01:50Z

Makes sense. I was trying to remember why I've always needed a separate class for the generic thing. I haven't made a generic deriver for quite a while. And maybe it actually was for this very reason of needing extra parameters.

src/Control/Functor/Linear/Internal/Class.hs

sjoerdvisscher · 2021-02-26T10:19:41Z

You also need a separate class for classes of kind Type -> Constraint, reusing the same class only works for classes of kind (Type -> Type) -> Constraint because GHC.Generics gives everything this p argument.

aspiwack

I approve of the new implementation strategy for deriving control functors. But it needs a little documentation for when we come back there later 🙂

Aside from that (and the comments below), may I ask of you to add an example file in the examples/ directory. Probably with a couple of tests (we have a dedicated test suite for the examples).

src/Control/Functor/Linear/Internal/Class.hs

src/Data/Functor/Linear/Internal/Functor.hs

src/Unsafe/Linear.hs

src/Unsafe/Linear/Internal.hs

src/Unsafe/Linear/Internal/Generically.hs

aspiwack · 2021-04-09T14:15:31Z

src/Unsafe/Linear/Internal/Generically.hs

+import Prelude.Linear.Internal
+import Data.V.Linear ()
+
+newtype Generically a = Generically a


Please add some Haddock to explain why one would use Generically, and why it is presently unsafe. And when it is safe to use.

src/Unsafe/Linear/Internal/Generically.hs

aspiwack · 2021-04-09T14:50:44Z

src/Control/Functor/Linear/Internal/Class.hs

+  eitherNoPar1Map f (l :*: r) = unused l :*: fmap f r
+instance (Unused r, Functor l, NoPar1 l ~ 'False) => EitherNoPar1 'False 'True l r where
+  eitherNoPar1Map f (l :*: r) = fmap f l :*: unused r
+type MessageMany = 'Text "Can't derive an instance of Functor. One of the constructors of your datatype uses the type parameter more than once."


This is fine for the first brush. But I think that we can improve on this error message by carrying the name and type of the offending constructor and adding it to the error message.

@aspiwack, yes, we'll want to add a GFunctor class that takes the name of the type as well as the constructor.

src/Control/Functor/Linear/Internal/Class.hs

Co-authored-by: Arnaud Spiwack <arnaud.spiwack@tweag.io>

# Conflicts: # src/Data/Unrestricted/Internal/Instances.hs

aspiwack · 2021-09-29T07:08:45Z

Thanks @treeowl for raising this again

I remember that there was an issue with this Pull Request which prevented us from moving forward. But it seems that we failed to document the problem here. @sjoerdvisscher do you remember what happened?

sjoerdvisscher · 2021-09-29T08:40:50Z

The problem is that the generated code by deriving Generic1 for types having :.: in the representation uses regular fmap, but it needs to be linear for our use cases. I guess this is also what @treeowl found out.

treeowl · 2021-09-29T14:19:06Z

The problem is that the generated code by deriving Generic1 for types having :.: in the representation uses regular fmap, but it needs to be linear for our use cases. I guess this is also what @treeowl found out.

I wasn't even thinking about that aspect. Where does fmap show up in generated code? I remember it shows up in a lot of Generic1-based instances. The fundamental error in Generic1 deriving is the way it constructs compositions. It should associate them to the left (e.g., (Rec1 (Either Int) :.: []) :.: Maybe), but instead associates them to the right (Either Int :.: ([] :.: Rec1 Maybe)). Is it possible to patch this up for linear-base?

sjoerdvisscher · 2021-09-29T15:19:36Z

I remember it shows up in a lot of Generic1-based instances.

Yes that's what I meant, the generated instances.

I still don't know what the best way is to do deriving of linear generics. I was hoping to do it with some type level hackery and maybe a minimal amount of TH based on the generated instances of regular generics, but I couldn't really figure that one out. Doing everything in TH seems a daunting task, maybe there's a library that we can hook into? Or else baking it in into GHC might be the easiest approach?

treeowl · 2021-09-29T15:57:13Z

Generic1 isn't nearly as popular as Generic, so I think it's best to start with the latter. But I'll make an attempt at a hacked Generic1.

aspiwack · 2021-09-29T16:23:10Z

Generic1 isn't nearly as popular as Generic, so I think it's best to start with the latter. But I'll make an attempt at a hacked Generic1.

True, but this is partly because there are stock derivers for Functor/Foldable/Traversable. Maybe we ought to split the PR to get the easy bits in, though.

treeowl · 2021-09-29T17:06:04Z

Where are the linear to and from exported? I couldn't figure that out easily from the PR. Yes, I think splitting is a great idea.

treeowl · 2021-10-12T02:49:26Z

Could you possibly rebase this? I can't figure out which pieces are supposed to go where.

treeowl · 2021-10-12T15:06:59Z

I was thinking to rework this whole thing to use linear-generics, but if you have other plans I don't want to get in the way.

sjoerdvisscher · 2021-10-12T15:10:44Z

@treeowl No please, go ahead, I'm done now. I was just trying to get this in the shape that's hopefully the most useful to you.

treeowl · 2021-10-12T15:13:08Z

Great, as long as we're on the same page.

aspiwack · 2021-10-12T16:29:38Z

@treeowl note that now that you have write access you can work directly on this branch, if it's convenient to you.

treeowl · 2021-10-12T16:40:40Z

Sounds good. I'll let y'all know when I'm ready for review. I expect I'll need other people to tell me what to name everything and where to put it, since I don't know your conventions, but that can happen later.

* Switch to `linear-generics`. * Make `Unused (f :.: g)` handle the case that `g` is `Unused` but `f` is not. * Avoid `error` when facing unsatisfiable constraints.

The contents of `Unsafe.Linear` were moved to `Unsafe.Linear.Internal`, presumably to avoid cyclical imports with `Generically` stuff. `Generically` is no longer unsafe, so we don't need that, at least for now. We can get it back if we want/need, but it doesn't belong in this PR and it makes the diff hard for me to use.

* Put the 'Generically' and 'Generically1' types in a module, `Prelude.Linear.Generically`, at the very base of the module hierarchy. This seems to help avoid the module cycle problems that have been worked around various ways. * Move the generic-deriving machinery for each class into the module that defines that class. * Start unwinding orphan instance spaghetti. I'm optimistic this will work, but I know it's not a sure thing.

The knots are coming undone. If this works, I'll eventually need to write a proper dependency explanation, like the one in `GHC.Base`.

* Many more orphans removed. * Many more instances added. * Added generic deriving for data `Applicative`s.

src/Data/Functor/Linear/Internal/Applicative.hs

* Improve generic `Traversable`. It works well for product types and sufficiently simple sum types. For nontrivial sum types the GHC optimizer makes hash of it in 9.0; I don't have 9.2 yet, so I don't know if that's changed any. * Add `Yoneda` and `Coyoneda` for both data functors and control functors, and `Curried` for control functors. `Yoneda` and `Coyoneda` especially tend to come in handy.

Make `GTraversable` lazier for `V1` to match behavior typical in `base`. Follow Sjoerd Visscher's advice adding more `Unsatisfiable` constraints for bogus `GApplicative` instances.

aspiwack · 2022-02-15T17:18:52Z

This branch is slated for the v2.0 release (next week-ish). @treeowl will take care of updating it to master (when he recovers from his cold). Thanks @treeowl .

treeowl · 2022-02-22T02:14:51Z

I finally felt well enough today to start the rebasing process. No major roadblocks yet. What Trustworthy module should I re-export GHC.Types.Multiplicity from so I can use it in (low dependency order) Safe modules?

treeowl · 2022-02-22T19:09:21Z

@aspiwack I'd really like to merge Data.Unrestricted.Linear.Internal.Dupable with Data.Unrestricted.Linear.Internal.Movable to get rid of orphan instances. Is that okay with you? My manual "rebase" has now reached the tricky bit (the generic Dupable stuff all needs to be redone), and I'd love to finish it up today or this weekend at the latest.

Another question: do we want Data.Functor and Traversable instances for Data.Vector.Vector and Data.Primitive.Array? I was a bit surprised not to see those.

treeowl · 2022-02-23T04:55:41Z

Progress continues. I may not need to merge the Dupable and Movable modules after all. AsMovable doesn't have any obvious benefits over generic deriving for basic instances.

One frustrating thing: generic deriving of Dupable a => Dupable [a] doesn't work out all that great. The Core is quite nice, with one glaring exception: the whole dupR definition becomes a loop breaker and GHC doesn't produce an unfolding. Writing an instance manually, I can use an explicit go function with scoped type variables to get what I want. General suggestions welcomed. See #394 for the work in progress.

aspiwack · 2022-02-23T07:35:25Z

I finally felt well enough today to start the rebasing process. No major roadblocks yet. What Trustworthy module should I re-export GHC.Types.Multiplicity from so I can use it in (low dependency order) Safe modules?

I've never payed much attention Safe Haskell, to be honest I don't really know how this works (plus linear-base has a fairly large kernel of trust).

I suggest that we don't care about it for the sake of this PR. And if you want to make linear-base safe-haskell compatible, we discuss how in a second PR.

@aspiwack I'd really like to merge Data.Unrestricted.Linear.Internal.Dupable with Data.Unrestricted.Linear.Internal.Movable to get rid of orphan instances. Is that okay with you?

I honestly don't care either way. If it's useful to your PR, feel free. If it's orthogonal, I prefer we do that in a separate step.

My manual "rebase" has now reached the tricky bit (the generic Dupable stuff all needs to be redone),

Is it worth splitting this to another PR? (I feel my remarks, so far, have been having a theme 🙂; at the end of the day, do whatever is more expedient).

Another question: do we want Data.Functor and Traversable instances for Data.Vector.Vector and Data.Primitive.Array? I was a bit surprised not to see those.

I'd say yes. It's an oversight that we haven't (but, you guessed it: it should be a different PR)

One frustrating thing: generic deriving of Dupable a => Dupable [a] doesn't work out all that great. The Core is quite nice, with one glaring exception: the whole dupR definition becomes a loop breaker and GHC doesn't produce an unfolding. Writing an instance manually, I can use an explicit go function with scoped type variables to get what I want. General suggestions welcomed.

I suggest that we keep the instance for [a] manual for the time being, and that we think of ways to improve code generation for this case when the Generic work is merged and we have mental room to focus on the problem.

Topsii · 2022-03-03T15:38:48Z

src/Prelude/Linear/Generically.hs

+newtype Generically a = Generically a
+


Generically and Generically1 have been added to base-4.17. I don't know whether this is relevant for you, but I thought I'd mention it just in case.

It's definitely relevant. I'm not sure how we will handle this, but when 9.4 is out, we will strive to make these newtypes re-exports from base.

sjoerdvisscher added 3 commits February 25, 2021 17:32

Added generic deriving of data linear Functor instances

c42341d

Added generic deriving of data linear Traversable instances

8157f86

Added generic deriving of control linear Functor instances

35993bf

aspiwack reviewed Feb 26, 2021

View reviewed changes

src/Control/Functor/Linear/Internal/Class.hs Outdated Show resolved Hide resolved

sjoerdvisscher added 3 commits February 26, 2021 13:32

Control Functor generics with "some type class magic"

b42c381

Add Generically and Generically1 for deriving via

bff8d17

Add deriving via Generically for Consumable, Dupable and Movable

7218913

sjoerdvisscher mentioned this pull request Mar 2, 2021

Add default instances for the Data.Unrestricted classes based on the Generic framework #311

Closed

sjoerdvisscher changed the title ~~Derive Functor and Traversable instances with GHC.Generics~~ Add deriving via Generically/Generically1 Mar 2, 2021

aspiwack reviewed Apr 9, 2021

View reviewed changes

sjoerdvisscher and others added 5 commits April 10, 2021 18:11

Apply suggestions from code review

24c2493

Co-authored-by: Arnaud Spiwack <arnaud.spiwack@tweag.io>

Merge branch 'master' into sv/functor-traversable-generics

2f2ce5c

# Conflicts: # src/Data/Unrestricted/Internal/Instances.hs

Merge branch 'master' into sv/functor-traversable-generics

b0c5a1e

Fix build after merge

5c596a4

Add a bit of documentation

3e8792e

aspiwack mentioned this pull request Sep 29, 2021

Generics #345

Closed

This was referenced Oct 8, 2021

Switch Generic classes linear-generics/linear-generics#3

Merged

Add examples of linear use? linear-generics/linear-generics#5

Open

sjoerdvisscher added 2 commits October 12, 2021 15:24

Merge branch 'master' into sv/functor-traversable-generics

05f8215

Some fixes

269bb07

treeowl added 6 commits October 12, 2021 21:07

Switch to linear-generics

9c318ad

* Switch to `linear-generics`. * Make `Unused (f :.: g)` handle the case that `g` is `Unused` but `f` is not. * Avoid `error` when facing unsatisfiable constraints.

Make the DerivingVia example compile

e219c67

Progress!

4a74255

The knots are coming undone. If this works, I'll eventually need to write a proper dependency explanation, like the one in `GHC.Base`.

Hope nobody shoots me

a443d21

* Many more orphans removed. * Many more instances added. * Added generic deriving for data `Applicative`s.

sjoerdvisscher commented Oct 13, 2021

View reviewed changes

src/Data/Functor/Linear/Internal/Applicative.hs Show resolved Hide resolved

treeowl force-pushed the sv/functor-traversable-generics branch from 03e1f0b to 4415181 Compare October 14, 2021 02:34

Tweaks

607ee19

Make `GTraversable` lazier for `V1` to match behavior typical in `base`. Follow Sjoerd Visscher's advice adding more `Unsatisfiable` constraints for bogus `GApplicative` instances.

aspiwack added this to the v0.2.0 milestone Feb 11, 2022

aspiwack mentioned this pull request Feb 15, 2022

Some documentation on genericTraverse and friends #384

Merged

aspiwack assigned treeowl Feb 15, 2022

treeowl mentioned this pull request Feb 23, 2022

Rebasing generic work #394

Merged

tbagrel1 removed this from the v0.2.0 milestone Feb 25, 2022

Topsii reviewed Mar 3, 2022

View reviewed changes

sjoerdvisscher closed this Apr 5, 2022

Conversation

sjoerdvisscher commented Feb 25, 2021

Uh oh!

aspiwack commented Feb 26, 2021

Uh oh!

sjoerdvisscher commented Feb 26, 2021

Uh oh!

aspiwack commented Feb 26, 2021

Uh oh!

Uh oh!

sjoerdvisscher commented Feb 26, 2021

Uh oh!

aspiwack left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

aspiwack Apr 9, 2021

Choose a reason for hiding this comment

Uh oh!

Uh oh!

aspiwack Apr 9, 2021

Choose a reason for hiding this comment

Uh oh!

treeowl Oct 13, 2021

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

aspiwack commented Sep 29, 2021

Uh oh!

sjoerdvisscher commented Sep 29, 2021

Uh oh!

treeowl commented Sep 29, 2021

Uh oh!

sjoerdvisscher commented Sep 29, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

treeowl commented Sep 29, 2021

Uh oh!

aspiwack commented Sep 29, 2021

Uh oh!

treeowl commented Sep 29, 2021

Uh oh!

treeowl commented Oct 12, 2021

Uh oh!

treeowl commented Oct 12, 2021

Uh oh!

sjoerdvisscher commented Oct 12, 2021

Uh oh!

treeowl commented Oct 12, 2021

Uh oh!

aspiwack commented Oct 12, 2021

Uh oh!

treeowl commented Oct 12, 2021

Uh oh!

Uh oh!

aspiwack commented Feb 15, 2022

Uh oh!

treeowl commented Feb 22, 2022

Uh oh!

treeowl commented Feb 22, 2022

Uh oh!

treeowl commented Feb 23, 2022

Uh oh!

aspiwack commented Feb 23, 2022

Uh oh!

Topsii Mar 3, 2022

Choose a reason for hiding this comment

Uh oh!

aspiwack Mar 7, 2022

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

sjoerdvisscher commented Sep 29, 2021 •

edited

Loading