Any objection to small breaking change in abstract-par's ParIVar class? (Eq constraint)

[Ryan Newton]

We're getting close to releasing our LVar library which lockfree monotonic sets, maps, vectors in addition to IVars.

The LVar implementation (termed LVish and found here) is also a valid Par monad, and we should expect it to have a ParIVar instance, as found here.

There's a small hitch though.  The current LVish scheduler depends on the idempotence of all actions in the monad, and it will repeat actions with low probability.  Thus we cannot make the same decision we did with the first crop of monad-par schedulers -- that a second put is always an error, even if you put the same value.

But to detect a repeated put of the same value, we need an Eq constraint on several operations:

  put_ :: Eq a => ivar a -> a -> m ()




Does anyone object to adding this Eq constraint in the ParIVar class (a breaking change)?  Note that this will not affect anyone that imports Control.Monad.Par directly---rather than the generic interface---which is probably everyone.



By the way, this does not inhibit storing IVars in IVars.  Instead we simply add an Eq instance for IVars similar to that for 




  -Ryan




P.S.  There are a couple advantages of LVish vis a vis monad-par presently:



It uses the 's' parameter, avoiding that big omission in the first monad-par that can lead to segfaults.
It waits for all workers properly before exiting a runPar.  We had played fast and loose with that in some monad-par schedulers, resulting in sloppiness in when exceptions crop up and possible nondeterminism if the process exits just before a worker would have hit an exception.

[Simon Marlow]

Hmm, I'm not terribly keen on this.  Apart from breaking the API, it feels like the implementation is leaking into the types.  Is this really the only way to do it?

How much code do we have that is overloaded on the Par class? It's just monad-par-extras, right?

Cheers,
    Simon

[Ryan Newton]

Well, my feeling was that its not requiring a specific implementation as much as making a wider range of implementations possible.  (Schedulers that allow double puts are not possible without the Eq constraint.  The monad-par policy of not allowing them is still possible with Eq constraints.)

It's not much code at all -- indeed just monad-par-extras that I'm aware of.

It does restrict the domain of things that can go in an IVar.  Indeed, the LVar theory requires that there be a lattice... and you can't take the LUB of functions in Haskell either.

The alternative is to make a separate class for the Eq-variant (IdempIVar?).... but that grows a bit messy as well.  I'll explore that option for the moment and perhaps we can grow the abstract-par type class hierarchy in a backwards compatible way.

  -Ryan

--
You received this message because you are subscribed to the Google Groups "monad-par" group.
To unsubscribe from this group and stop receiving emails from it, send an email to monad-par+...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Ryan Newton]

It's not much code at all -- indeed just monad-par-extras that I'm aware of.

By the way, the motivation for having this at all is to:

• Reuse the generic combinators in monad-par-extras for LVish
• Have a reason to start growing those combinators into a more useful set of general utilities 

-Ryan

[Ryan Newton]

Another issue that I'd like to put on the table is if we do end up making a breaking change to the generic interface, it may also be nice to use that opportunity to switch to associated types rather than MPTC and functional dependencies for relating the Par and IVar/Future types.

Finally, if we want to *really* make breaking changes then we could try to actually make monad-par safe:

• Exception safety: stop using raw forkOn
• Termination safety: wait for workers before exiting runPar
• Type safety: require an 's' parameter.

[Ryan Newton]

Ok, well we could abstract over the constraint using constraint kinds, like this.  Those have been around since 7.4, and with 7.8 coming out, that might be an acceptable window.

-- | @ParFuture@ captures the class of Par monads which support
--   futures.  This level of functionality subsumes @par@/@pseq@ and is

--   similar to the "Control.Parallel.Strategies.Eval" monad.


--
--   A minimal implementation consists of `spawn_` and `get`.

--   However, for monads that are also a member of `ParIVar` it is


--   typical to simply define `spawn` in terms of `fork`, `new`, and `put`.
-- 

class Monad m => ParFuture future m | m -> future where

-- class Monad m => ParFuture m where
  

  -- | The type of a future that goes along with the particular `Par`


  -- monad the user chooses.
--   type Future a 


  -- | Different implementations may place different constraints on

  -- what is allowable inside a Future.  For example, some


  -- implementations require an Eq Constraint.
  type FutContents a :: Constraint


  -- | Create a potentially-parallel computation, and return a /future/

  -- (or /promise/) that can be used to query the result of the forked


  -- computataion.
  --

  -- >  spawn p = do
  -- >    r <- new

  -- >    fork (p >>= put r)
  -- >    return r

  --
  spawn  :: (NFData a, FutContents a) => m a -> m (future a)


  -- | Like 'spawn', but the result is only head-strict, not fully-strict.

  spawn_ :: FutContents a => m a -> m (future a)


  -- | Wait for the result of a future, and then return it.

  get    :: future a -> m a


  -- | Spawn a pure (rather than monadic) computation.  Fully-strict.

  --
  -- >  spawnP = spawn . return

  spawnP :: (NFData a, FutContents a) =>   a -> m (future a)


  -- Default implementations:


  spawn  p = spawn_ (do x <- p; deepseq x (return x))

  spawnP a = spawn (return a)

On Sun, Sep 8, 2013 at 3:28 PM, Simon Marlow <marl...@gmail.com> wrote:

[Ryan Newton]

Oops, it needs to be a bit uglier than the above.  The FutContents type function needs an input to distinguish which "Par" monad we're talking about.  Below is an example that runs the same code with monad par and LVish.  It does add some clutter.

import qualified Control.Monad.Par as MP 

import qualified Data.LVar.IVar as LI

import qualified Control.LVish as LVish

.....

-- We achieve backwards compatibility simply by putting in a null constraint:


instance ParFuture MP.Par where

  type Future      MP.Par a = MP.IVar a 

  type FutContents MP.Par a = ()

  get    = MP.get

  spawn  = MP.spawn

  spawn_ = MP.spawn_

  spawnP = MP.spawnP


par :: (ParFuture p, FutContents p String) => p String

par = do x <- spawn $ return "hello"

         get x



test2 :: String


test2 = MP.runPar par


instance ParFuture (LVish.Par d s) where

  type Future      (LVish.Par d s) a = LI.IVar s a   

  type FutContents (LVish.Par d s) a = (Eq a)

  spawn_ m = LI.spawn_ m

  get iv = LI.get iv


test3 :: String

test3 = LVish.runPar par

[Simon Marlow]

On 09/09/13 15:46, Ryan Newton wrote:
> Another issue that I'd like to put on the table is if we do end up
> making a breaking change to the generic interface, it may also be nice
> to use that opportunity to switch to associated types rather than MPTC
> and functional dependencies for relating the Par and IVar/Future types.
>
> Finally, if we want to *really* make breaking changes then we could try
> to actually make monad-par safe:
>

> * Exception safety: stop using raw forkOn
> * Termination safety: wait for workers before exiting runPar
> * Type safety: require an 's' parameter.

I'm wondering whether it might be time to fork monad-par to start
working on these changes. That way we could leave the existing
monad-par for users to continue to rely on, and you can forge ahead. I
don't want to stand in the way of progress, but I do want to keep things
stable - the only way to have both of these seems to be to have two
branches, perhaps even two package names.

On the subject of double-put, I'm still not sure we want/need an Eq
constraint. Given that you can assign an identity to every put in the
program (a hash of some kind), you can tell when a put is being
re-executed based on its hash, without having to compare values. Won't
that work?

The reason I asked about monad-par-extras is, if it isn't that much
code, we might not mind duplicating it rather than keeping this
abstraction that isn't used much. That would decouple you, leaving you
free to change the monad-par API for LVars however you like.

Cheers,
Simon

>
> On Mon, Sep 9, 2013 at 10:43 AM, Ryan Newton <rrne...@gmail.com
> <mailto:rrne...@gmail.com>> wrote:
>
>
> It's not much code at all -- indeed just monad-par-extras that
> I'm aware of.
>
>
> By the way, the motivation for having this at all is to:
>

> * Reuse the generic combinators in monad-par-extras for LVish
> * Have a reason to start growing those combinators into a more

[Aaron Todd]

This seems like a dangerous change to make. First, we are presuming that
no one will want to put something without Eq defined in an Ivar, which
seems really unfortunate. What if Ivars holding functions would be useful?

It also seems quite quirky in that in some cases this would be shallow
equality, but in other cases it could be deep equality that forces
computation. Would this be an issue for infinite lists? Naively trying
to check equality on a pair of infinite lists in ghci:

Prelude> let x = cycle [5,120]
Prelude> x == x
*hangs*

So it seems like requiring Eq and actually doing the check on a
double-put invalidates programs that rely on laziness in this way.

~ Aaron Todd

On 09/08/2013 03:28 PM, Simon Marlow wrote:
> Hmm, I'm not terribly keen on this. Apart from breaking the API, it
> feels like the implementation is leaking into the types. Is this really
> the only way to do it?
>
> How much code do we have that is overloaded on the Par class? It's just
> monad-par-extras, right?
>
> Cheers,
> Simon
>
> On 08/09/13 19:30, Ryan Newton wrote:
>> We're getting close to releasing our LVar library which lockfree
>> monotonic sets, maps, vectors in addition to IVars.
>>
>> The LVar implementation (termed LVish and found here

>> <https://github.com/iu-parfunc/lvars/tree/master/haskell-prototype>)

>> is also a valid Par monad, and we should expect it to have a ParIVar
>> instance, as found here

>> <https://github.com/iu-parfunc/lvars/blob/667b3938809cddf2aaf6da8ca1cb4650f6a1de33/haskell-prototype/Data/LVar/IVar.hs#L142>.

>>
>> There's a small hitch though. The current LVish scheduler depends on

>> the */idempotence/* of all actions in the monad, and it will repeat

>> actions with low probability. Thus we cannot make the same decision
>> we did with the first crop of monad-par schedulers -- that a second
>> put is always an error, even if you put the same value.
>>
>> But to detect a repeated put of the same value, we need an Eq
>> constraint on several operations:
>>
>> put_ :: Eq a => ivar a -> a -> m ()
>>
>>

>> *Does anyone object to adding this Eq constraint in the ParIVar class
>> (a breaking change)? *Note that this will not affect anyone that

>> imports Control.Monad.Par directly---rather than the generic
>> interface---which is probably everyone.
>> By the way, this does not inhibit storing IVars in IVars. Instead we
>> simply add an Eq instance for IVars similar to that for
>>
>>
>> -Ryan
>>
>>
>> P.S. There are a couple advantages of LVish vis a vis monad-par
>> presently:
>>
>>

>> * It uses the 's' parameter, avoiding that big omission in the first

>> monad-par that can lead to segfaults.

>> * It waits for all workers properly before exiting a runPar. We had

>> played fast and loose with that in some monad-par schedulers,
>> resulting in sloppiness in when exceptions crop up and possible
>> nondeterminism if the process exits just before a worker would
>> have hit an exception.
>>
>

[Ryan Newton]

[Aaron Turon -- Cc'ing you because you are the primary architect of the idempotency-leveraging scheduler.]

On the subject of double-put, I'm still not sure we want/need an Eq constraint.  Given that you can assign an identity to every put in the program (a hash of some kind), you can tell when a put is being re-executed based on its hash, without having to compare values.  Won't that work?

Yes, the best way I know to have a reproducible hash is to dynamically reify the "pedigree" of the operation. Unfortunately, it's expensive-ish and we wouldn't be able to pay that cost *only* when we run across the second put.  Rather, we'd have to store (at least a thunk) on the first put to record who touched it first.  Aaron, can you think of any way to make that cheaper?  (Note that the cost of the Eq is only paid on the second put and later... and that happens only with low probability.)  

 

Forking may be necessary, but let's hold off a tad longer.  I agree that we should keep Control.Monad.Par around as a reliable, simple API, even if it has some dangers.  (For example the exception thing....  though on that one we should probably port it to use Control.Async so exceptions on workers don't get lost.  That would be an internal change only.)

I am convinced that we shouldn't do the Eq constraint [1].  I just want to exhaust the options for either the Constraint-kind design or a bigger class hierarchy with finer distinctions.

  -Ryan

[1] But even if we did, it wouldn't affect someone importing Control.Monad.Par directly!!  By the way, do you have an application in mind that uses functions in IVars or some such?  Or is the objection on based primarily on aesthetics and principle?  

On Mon, Sep 9, 2013 at 10:43 AM, Ryan Newton <rrne...@gmail.com

<mailto:rrne...@gmail.com>> wrote:


        It's not much code at all -- indeed just monad-par-extras that
        I'm aware of.


    By the way, the motivation for having this at all is to:

      * Reuse the generic combinators in monad-par-extras for LVish
      * Have a reason to start growing those combinators into a more

        useful set of general utilities

    -Ryan

--
You received this message because you are subscribed to the Google Groups "monad-par" group.

To unsubscribe from this group and stop receiving emails from it, send an email to monad-par+unsubscribe@googlegroups.com.

[Aaron Turon]

On Mon, Sep 9, 2013 at 11:00 PM, Ryan Newton <rrne...@gmail.com> wrote:
> [Aaron Turon -- Cc'ing you because you are the primary architect of the
> idempotency-leveraging scheduler.]
>
>> On the subject of double-put, I'm still not sure we want/need an Eq
>> constraint. Given that you can assign an identity to every put in the
>> program (a hash of some kind), you can tell when a put is being re-executed
>> based on its hash, without having to compare values. Won't that work?
>
> Yes, the best way I know to have a reproducible hash is to dynamically reify
> the "pedigree" of the operation. Unfortunately, it's expensive-ish and we
> wouldn't be able to pay that cost *only* when we run across the second put.
> Rather, we'd have to store (at least a thunk) on the first put to record who
> touched it first. Aaron, can you think of any way to make that cheaper?
> (Note that the cost of the Eq is only paid on the second put and later...
> and that happens only with low probability.)

Sorry, I think I'm lacking the context here: are you asking about the
situation with our LVish scheduler (and the expensive "trick" we can
use to make operations idempotent) or a situation in the general Par
monad? What is the problem you're trying to solve?

Cheers,
Aaron