lvish-2.0: Parallel scheduler, LVar data structures, and infrastructure to build more.

Safe HaskellNone




The lvish package provides a parallel programming model based on monotonically growing data structures.

This module provides the core scheduler and basic control flow operations. But to do anything useful you will need to import, along with this module, one of the data structure modules (Data.LVar.*).

Here is a self-contained example. This program writes the same value to an LVar called num twice. It deterministically prints 4 instead of raising an error, as it would if num were a traditional IVar rather than an LVar. (You will need to compile using the -XDataKinds extension.)

 import Control.LVish  -- Generic scheduler; works with any lattice.
 import Data.LVar.IVar -- The particular lattice in question.
 p :: Par Det s Int
 p = do
   num <- new
   fork $ put num 4
   fork $ put num 4
   get num
 main = do
   print $ runPar $ p


CRITICAL OBLIGATIONS for the user: valid Eq and total Ord

We would like to tell you that if you're programming with Safe Haskell (-XSafe), that this library provides a formal guarantee that anything executed with runPar is guaranteed-deterministic. Unfortunately, as of this release there is still one back-door that hasn't yet been closed.

If an adversarial user defines invalid Eq instances (claiming objects are equal when they're not), or if they define a compare function that is not a pure, total function, and then they store those types within LVars, then nondeterminism may leak out of a parallel runPar computation.

In future releases, we will strive to require alternate, safe versions of Eq and Ord that are derived automatically by our library and by the GHC compiler.

Par computations and their parameters

data Par

The type of parallel computations. A computation Par e s a may or may not be deterministic based on the setting of the d parameter (of kind Determinism). The s parameter is for preventing the escape of LVars from Par computations (just like the ST monad).

Implementation note: This is a wrapper around the internal Par type, only with more type parameters.


Monad (Par $a $b) 
Functor (Par $a $b) 
Applicative (Par $a $b) 
ParFuture (Par e s) 
ParIVar (Par e s) 
ParSealed (Par e s) 
LVarSched (Par e s) 
ParThreadSafe (Par e s) 
ParMonad (Par e s) 
MonadIO (Par e s) 
(Deterministic e1, ~ EffectSig e2 (SetF F e1)) => ParQuasi (Par e1 s) (Par e2 s) 
(Deterministic e1, ~ EffectSig e2 (SetF F e1)) => LVarSchedQ (Par e1 s) (Par e2 s) 

data LVishException

All LVars share a common notion of exceptions. The two common forms of exception currently are conflicting-put and put-after-freeze. There are also errors that correspond to particular invariants for particular LVars.

Running various Par computations

runPar :: (forall s. Par (Ef P G NF B NI) s a) -> a

If a computation is guaranteed-deterministic, then Par becomes a dischargeable effect. This function will create new worker threads and do the work in parallel, returning the final result.

(For now there is no sharing of workers with repeated invocations; so keep in mind that runPar is an expensive operation. [2013.09.27])

runParQuasiDet :: (forall s. Par (Ef P G F B NI) s a) -> IO a

Run a computation that allows freezes but not IO.

Thus the input computation is QuasiDeterministic, and this may throw a LVishException nondeterministically on the thread that calls it, but if it returns without exception then it always returns the same answer.

If the input computation is in fact deterministic (no freezes), then runQuasiDet will return the same result as runPar. However, it is still possibly useful for avoiding an extra unsafePerformIO required inside the implementation of runPar.

Finally, note that in the future runQuasiDet may behave differently than runNonDet; in particular, it may attempt recovery or retry strategies when an LVishException is thrown.

runParNonDet :: (forall s. Par (Ef P G F B I) s a) -> IO a

Run a Par computation where everything is permitted, i.e. all effect-signature switches are switched to on.

More polymorphic variants of same

runParPoly :: Deterministic e => (forall s. Par e s a) -> a

Version of runPar that gives you more flexibility in the effect signature of the input computation. The downside is th

runParPolyIO :: (forall s. Par e s a) -> IO a

More flexible alternative to runParNonDet and runParQuasiDet. This will run any kind of Par computation, but just like with runParPoly, you must fully constrain the effect signature of the input computation to avoid ambiguity type errors.

Effect signature manipulation and conversion

liftQD :: Par t t1 a -> Par e s a

It is always safe to lift a deterministic computation to a quasi-deterministic one. liftQD :: Par Det s a -> Par QuasiDet s a

Combinators for manually constraining the type of a given Par computation

isDet :: e ~ Ef P G NF B NI => Par e s a -> Par e s a

isQD :: e ~ Ef P G F B NI => Par e s a -> Par e s a

isND :: e ~ Ef P G F B I => Par e s a -> Par e s a

isIdemD :: e ~ Ef P G NF NB NI => Par e s a -> Par e s a

isIdemQD :: e ~ Ef P G F NB NI => Par e s a -> Par e s a

isReadOnly :: e ~ Ef NP G NF NB NI => Par e s a -> Par e s a

hasPut :: HasPut e => Par e s a -> Par e s a

hasFreeze :: HasFreeze e => Par e s a -> Par e s a

hasBump :: HasBump e => Par e s a -> Par e s a

hasGet :: HasGet e => Par e s a -> Par e s a

hasIO :: HasIO e => Par e s a -> Par e s a

noPut :: NoPut e => Par e s a -> Par e s a

noFreeze :: NoFreeze e => Par e s a -> Par e s a

noBump :: NoBump e => Par e s a -> Par e s a

noGet :: NoGet e => Par e s a -> Par e s a

noIO :: NoIO e => Par e s a -> Par e s a

Subtyping, add more effects to the signature

These effects are a conservative approximation, therefore it is always ok, for example, to turn no put (NP) into put (P).

addP :: Par (Ef NP g f b i) s a -> Par (Ef p g f b i) s a

addG :: Par (Ef p NG f b i) s a -> Par (Ef p g f b i) s a

addF :: Par (Ef p g NF b i) s a -> Par (Ef p g f b i) s a

addB :: Par (Ef p g f NB i) s a -> Par (Ef p g f b i) s a

addI :: Par (Ef p g f b NI) s a -> Par (Ef p g f b i) s a

liftReadOnly :: Par (Ef NP g NF NB NI) s a -> Par (Ef p g f b i) s a

Lift a read-only computation to participate in a parent computation with more effects.

Basic control flow

fork :: Par e s () -> Par e s ()

Execute a computation in parallel.

yield :: Par e s ()

Cooperatively schedule other threads.

Lifting IO, sacrifices determinism

parIO :: HasIO e => IO a -> Par e s a

Lifting IO into Par in a manner that is fully accounted for in the effect signature.

Various loop constructs

parForL :: (Int, Int) -> (Int -> Par e s ()) -> Par e s ()

Deprecated: These will be removed in a future release in favor of a more general approach to loops.

Left-biased parallel for loop. As worker threads beyond the first are added, this hews closer to the sequential iteration order than an unbiased parallel loop.

Takes a range as inclusive-start, exclusive-end.

parForSimple :: (Int, Int) -> (Int -> Par e s ()) -> Par e s ()

Deprecated: These will be removed in a future release in favor of a more general approach to loops.

The least-sophisticated form of parallel loop. Fork iterations one at a time.

parForTree :: (Int, Int) -> (Int -> Par e s ()) -> Par e s ()

Deprecated: These will be removed in a future release in favor of a more general approach to loops.

Divide the iteration space recursively, but ultimately run every iteration in parallel. That is, the loop body is permitted to block on other iterations.

parForTiled :: Maybe HandlerPool -> Int -> (Int, Int) -> (Int -> Par e s ()) -> Par e s ()

Deprecated: These will be removed in a future release in favor of a more general approach to loops.

Split the work into a number of tiles, and fork it in a tree topology.

for_ :: Monad m => (Int, Int) -> (Int -> m ()) -> m ()

A simple for loop for numeric ranges (not requiring deforestation optimizations like forM). Inclusive start, exclusive end.



:: (Split c, Generator c) 
=> Maybe HandlerPool

Optional pool to synchronize forked tasks

-> c

element generator to consume

-> (ElemOf c -> Par e s ())

compute one result

-> Par e s () 

Non-blocking version of pforEach.

Logical control flow operators

asyncAnd :: Maybe HandlerPool -> Par e s Bool -> Par e s Bool -> (Bool -> Par e s ()) -> Par e s ()

A parallel And operation that can return early---whenever a False appears on either branch.

asyncOr :: Maybe HandlerPool -> Par e s Bool -> Par e s Bool -> (Bool -> Par e s ()) -> Par e s ()

Analagous operation for Or.

andMap :: (HasGet e, HasPut e) => Maybe HandlerPool -> (a -> Par e s Bool) -> [a] -> Par e s Bool

orMap :: (HasGet e, HasPut e) => Maybe HandlerPool -> (a -> Par e s Bool) -> [a] -> Par e s Bool

Synchronizing with handler pools

data HandlerPool

A HandlerPool contains a way to count outstanding parallel computations that are affiliated with the pool. It detects the condition where all such threads have completed.

newPool :: Par e s HandlerPool

Create a new pool that can be used to synchronize on the completion of all parallel computations associated with the pool.

withNewPool :: (HandlerPool -> Par e s a) -> Par e s (a, HandlerPool)

Execute a Par computation in the context of a fresh handler pool.

withNewPool_ :: (HandlerPool -> Par e s ()) -> Par e s HandlerPool

Execute a Par computation in the context of a fresh handler pool, while ignoring the result of the computation.

quiesce :: HandlerPool -> Par e s ()

Block until a handler pool is quiescent, i.e., until all associated parallel computations have completed.

forkHP :: Maybe HandlerPool -> Par e s () -> Par e s ()

A version of fork that also allows the forked computation to be tracked in a HandlerPool, that enables the programmer to synchronize on the completion of the child computation. But be careful; this does not automatically wait for all downstream forked computations (transitively).

Reexport IVar operations for a full, standard Par Monad API

Debug facilities and internal bits

logDbgLn :: Int -> String -> Par e s ()

Log a line of debugging output. This is only used when *compiled* in debugging mode. It atomically adds a string onto an in-memory log.

The provided Int, is the debug level associated with the message, 1-5. One is the least verbose, and five is the most. When debugging, the user can control the debug level by setting the env var DEBUG, e.g. DEBUG=5.

runParLogged :: (forall s. Par e s a) -> IO ([String], a)

A version of runParPolyIO that exposes more debugging information. That is, it returns debugging logs, in realtime order, in addition to the final result.



:: DbgCfg

Debugging configuration

-> Int

How many worker threads to use.

-> (forall s. Par e s a)

The computation to run.

-> IO ([String], Either SomeException a) 

A variant of with runParPolyIO with full control over the relevant knobs.

Returns a list of flushed debug messages at the end (if in-memory logging was enabled, otherwise the list is empty).

This version of runPar catches ALL exceptions that occur within the runPar, and returns them via an Either. The reason for this is that even if an error occurs, it is still useful to observe the log messages that lead to the failure.

data OutDest

A destination for log messages



Output via GHC's traceEvent runtime events.

OutputTo Handle

Printed human-readable output to a handle.


Accumulate output in memory and flush when appropriate.

data DbgCfg




dbgRange :: Maybe (Int, Int)

Inclusive range of debug messages to accept (i.e. filter on priority level). If Nothing, use the default level, which is (0,N) where N is controlled by the DEBUG environment variable. The convention is to use Just (0,0) to disable logging.

dbgDests :: [OutDest]

Destinations for debug log messages.

dbgScheduling :: Bool

In additional to logging debug messages, control thread interleaving at these points when this is True.

data LVar s all delt

The generic representation of LVars used by the scheduler. The end-user can't actually do anything with these and should not try to.