Dupable wars : implementation by tbagrel1 · Pull Request #360 · tweag/linear-base

tbagrel1 · 2022-01-18T18:29:35Z

No description provided.

aspiwack

What I would like to see, as well, is a function in Data.Array.Mutable.Linear which defines an array from a Replicator. To test the Replicator API.

src/Data/Unrestricted/Linear.hs

src/Data/V/Linear/Internal/V.hs

aspiwack · 2022-01-19T09:12:44Z

src/Data/Unrestricted/Internal/Replicator.hs

+data RepStream a where
+  RepStream :: (s %1 -> a) -> (s %1 -> (s, s)) -> (s %1 -> ()) -> s %1 -> RepStream a
+
+data Replicator a where
+  Moved :: a -> Replicator a
+  CollectFrom :: RepStream a %1 -> Replicator a


You don't have access to the Applicative class at this point†, but you should have a pure and a (<*>) function nonetheless. For both types.

We will probably need other functions, like a function Replicator %1 -> RepStream.

† Sometimes I feel as though this library should all be one big Internal file where everything is mutually recursive, and then we use the file hierarchy purely for exports.

Random thought: should we use unboxed pairs (and unit) in the projections? Maybe it'll be better?

If we use unboxed tuple for the dups projector, then it becomes harder to write dupR in terms of dup2 (or we should also change the dup2 signature to use unboxed tuples).
I don't know how to write an unboxed unit, but if we return some in the consumes projector, then writing consume (from Consumable) for ReplicationStream is also less trivial.
I also tried to use unboxed tuples in the Applicative instance for ReplicationStream (for <*>), but AFAIK, it's not possible because the projections cannot receive an unboxed tuple as a function parameter.

Also, without 9.2, I don't see how we can actually write this:

dupsf sf' & \case (# sf1, sf2 #)

We need the func_call & lambda_case syntax here for linearity, but because the result of the function call is now passed as an argument to &, then unboxed tuples are not allowed in that position.

Unboxed unit is (##).

Well, let's wait 9.2 before we decide to revisit this issue, then. It's not worth agonising over.

src/Data/Unrestricted/Internal/Instances.hs

aspiwack · 2022-01-19T17:58:02Z

I pushed a little something to restore the backward functional
dependency.

As I see it, there are two solutions:

Remove the n argument from the Elim type class arguments
altogether. It is effectively redundant, after all. This removes
all functional dependencies.
We need to tell the compiler how to compute n from f and
b. One way to convince oneself that GHC cannot know that n is
effectively determined by f is to consider what would happen if
we added an instance Elim 42 a b b? We need to make this
impossible!

While (1) is definitely the simpler solution, I went for (2) in my
commit, because I do like the idea of having the option of saying
elim @7 when the function type is under-determined. Rather than
having to state the entire function type.

What this implied is making a type family Arity b f which computes
the arity of f (assuming its headed by b). And force n ~ Arity b f as a super-class constraint. This way, no instance 42. This
suffices to convince GHC.

What I don't know if why I had to add Arity b (a %1 -> b) = 1, this
should follow from the definition. But when I remove it, Haskell is
very unhappy.

tbagrel1 · 2022-01-20T08:52:43Z

Should I redefine Arity when writing V.Elim, or should we share it someway?

Also, I was wondering yesterday, could we add a 2 <= n extra constraint on the last Elim n a b f instance instead of creating overlapping ones? What would be the cost of such a measure?

aspiwack · 2022-01-20T09:39:30Z

Should I redefine Arity when writing V.Elim, or should we share it someway?

I guess it's better to use the same.

Either way, it gives some pretty unappealing types, so we will have to give pretty solid documentation to elim.

Also, I was wondering yesterday, could we add a 2 <= n extra constraint on the last Elim n a b f instance instead of creating overlapping ones? What would be the cost of such a measure?

Unfortunately it wouldn't work. GHC only looks at the instance's head (the part to the right of the =>) to determine if instances are overlapping. You could add this constraint, but it would never apply.

tbagrel1 · 2022-01-20T09:42:30Z

Do you see where we could but the Arity thing so? In Data.Unrestricted.Linear.Internal.Arity?

Unfortunately it wouldn't work. GHC only looks at the instance's head (the part to the right of the =>) to determine if instances are overlapping. You could add this constraint, but it would never apply.

I would have used something like Elim (n + 1) a b f) => Elim (n + 2) a b (a %1 -> f) then, if only we could.

aspiwack · 2022-01-20T10:08:57Z

Do you see where we could but the Arity thing so? In Data.Unrestricted.Linear.Internal.Arity?

I guess. There is no good place where to put it anyway. The relation with Unrestricted is kind of dubious, though. Maybe Data.Linear.Internal.Arity instead?

facundominguez

I came to have some fun explaining the code. I shared some suggestions for documentation that I think could be helpful.

src/Data/Unrestricted/Internal/ReplicationStream.hs

src/Data/Unrestricted/Internal/Replicator.hs

src/Data/Arity/Linear/Internal/Arity.hs

src/Data/Replicator/Linear.hs

src/Data/Replicator/Linear/Internal/ReplicationStream.hs

src/Data/Replicator/Linear/Internal/Replicator.hs

src/Data/V/Linear/Internal/V.hs

src/Data/V/Linear/Internal/V.hs-boot

src/Streaming/Internal/Process.hs

aspiwack · 2022-01-25T15:19:16Z

I should add: this is another PR that got bigger than we planned. We should be more careful for the next ones.

tbagrel1 · 2022-01-26T15:04:40Z

Why are we deriving Prelude (non-linear) versions of Eq, Ord, and especially Functor for V?

src/Data/Replicator/Linear.hs

src/Data/Replicator/Linear/Internal.hs

src/Data/Replicator/Linear/Internal/ReplicationStream.hs

src/Data/Unrestricted/Internal/Dupable.hs

src/Data/Replicator/Linear/Internal.hs

src/Data/Unrestricted/Internal/Instances.hs

aspiwack · 2022-01-27T17:11:26Z

Why are we deriving Prelude (non-linear) versions of Eq, Ord, and especially Functor for V?

I don't remember for sure. But if I had to guess, it's because we wanted V n a to behave as much as possible as (a, …, a). We'd need a multiplicity polymorphic elim for this to work completely, though. We may have to wait until we are fully committed to 9.2 for this to work fine though. It may be worth a try (in a separate PR).

elim :: forall p n a b. (a %p -> … %p -> b) %1 -> V n a %p -> b

…iscoverable

aspiwack

I've got some comments on the documentation. You can address them then merge.

src/Data/Replicator/Linear.hs

src/Data/Replicator/Linear/Internal.hs

src/Data/Replicator/Linear/Internal/ReplicationStream.hs

src/Data/Unrestricted/Internal/Dupable.hs

src/Data/Replicator/Linear/Internal.hs

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

aspiwack reviewed Jan 19, 2022

View reviewed changes

facundominguez reviewed Jan 20, 2022

View reviewed changes

src/Data/Unrestricted/Internal/ReplicationStream.hs Outdated Show resolved Hide resolved

src/Data/Unrestricted/Internal/Replicator.hs Outdated Show resolved Hide resolved

src/Data/Unrestricted/Internal/Replicator.hs Outdated Show resolved Hide resolved

aspiwack reviewed Jan 25, 2022

View reviewed changes

tbagrel1 changed the title ~~Dupable wars : implementation attempt~~ Dupable wars : implementation Jan 26, 2022

tbagrel1 linked an issue Jan 26, 2022 that may be closed by this pull request

Dupable wars, episode IV: a new plan #343

Closed

tbagrel1 marked this pull request as ready for review January 26, 2022 15:09

tbagrel1 force-pushed the tbagrel1/dupable-new-impl branch from 3d5b286 to eec651f Compare January 26, 2022 15:34

tbagrel1 requested a review from aspiwack January 27, 2022 09:20

aspiwack reviewed Jan 27, 2022

View reviewed changes

tbagrel1 and others added 10 commits February 1, 2022 10:03

first attempt

ab835a8

change name of Replicator constructors

e1dc917

[WIP] Dupable rework

bf05894

Proposal: a solution to avoid @n in elim when arity is statically d…

c6c4190

…iscoverable

Apply changes as discussed with @aspiwack

55210f4

apply @aspiwack suggested change

b42584c

apply suggestions from @aspiwack 25/01

bec836a

fix docspec

81f11c9

add doc

9e1b8e9

apply changes from @aspiwack review from 27/01/2022

fc009e6

tbagrel1 force-pushed the tbagrel1/dupable-new-impl branch from 4da2e78 to fc009e6 Compare February 1, 2022 09:04

aspiwack approved these changes Feb 2, 2022

View reviewed changes

apply suggested changes from @aspiwack review - 2/02

85249d1

tbagrel1 added 2 commits February 3, 2022 11:45

fix haddock (1)

6fed233

add extend, fix haddock

8a16edc

aspiwack reviewed Feb 3, 2022

View reviewed changes

src/Data/Replicator/Linear/Internal.hs Outdated Show resolved Hide resolved

Update src/Data/Replicator/Linear/Internal.hs

d23664f

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

tbagrel1 merged commit dc4ae22 into master Feb 4, 2022

tbagrel1 deleted the tbagrel1/dupable-new-impl branch February 4, 2022 13:12

tbagrel1 mentioned this pull request Feb 4, 2022

Improve make/Make implementation for Data.V.Linear #364

Merged

aspiwack mentioned this pull request Feb 11, 2022

Using a mutable backing store (such as Array) for V #312

Closed

utdemir mentioned this pull request Mar 2, 2022

Introduce Data.VM.Linear and Data.LArray.Mutable.Unlifted.Linear #341

Draft

Conversation

tbagrel1 commented Jan 18, 2022

Uh oh!

aspiwack left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

aspiwack Jan 19, 2022

Choose a reason for hiding this comment

Uh oh!

aspiwack Jan 19, 2022

Choose a reason for hiding this comment

Uh oh!

tbagrel1 Jan 20, 2022

Choose a reason for hiding this comment

Uh oh!

treeowl Jan 20, 2022

Choose a reason for hiding this comment

Uh oh!

aspiwack Jan 20, 2022

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

aspiwack commented Jan 19, 2022

Uh oh!

tbagrel1 commented Jan 20, 2022

Uh oh!

aspiwack commented Jan 20, 2022

Uh oh!

tbagrel1 commented Jan 20, 2022

Uh oh!

aspiwack commented Jan 20, 2022

Uh oh!

facundominguez left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

aspiwack commented Jan 25, 2022

Uh oh!

tbagrel1 commented Jan 26, 2022

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

aspiwack commented Jan 27, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

aspiwack left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

aspiwack commented Jan 27, 2022 •

edited

Loading