PURPOSE

Parallel execution of multiset rewrite rules on
a multi-core platform. Rules are executed in parallel 
as long as their left-hand sides won't overlap.
Main novelty is the support of guards and propagation.
Here is a (sugared) version of an example using guards

 Seller x, Buyer x <==> "found matching seller/buyer"

The rule applies, i.e. fires, as soon as a seller has found
a matching buyer. The above non-linear pattern can be
expressed as a linear pattern (each pattern variable is distinct)
plus some guard

 Seller x, Buyer y when x == y <==> ...

A (sugared) example using guards and propagation

  Leq(x,a) \ Leq(x,b) when a<b <==> Leq(a,b)

The above rule replaces Leq(x,b) by Leq(a,b) but keeps (propagates)
Leq(x,a) when a<b

METHOD

We employ a variant of the LEAPS algorithm. Rules are triggered
by selecting a goal and trying the rules from top to bottom.
Concurrency/parallelism is achieved by having concurrent/parallel goals.
For further details, see

Parallel Execution of Multi Set Constraint Rewrite Rules
Parallel Join Patterns with Guards and Propagation 
by Martin Sulzmann, Edmund Lam

HASKELL IMPLEMENTATION

The packages provided are:

 - multisetrewrite: basic interface to multi-set rewriting engine
 - join: Join-style concurrency primitives built on top of multisetrewrite

The above are EDSLs which means that the syntax is more verbose
as in the above sugared examples. We have spent little effort
to make the syntax more pretty which is quite tricky because
there's no good way in Haskell to overload Haskell's pattern
matching syntax. The implementation are geared toward efficient
execution in a parallel setting, specifically, for the case of
rules making use of guards and propagation.

Examples with comments to explain the use of the above packages

extra source files multisetrewrite:

Stack.hs 

CHRSolver.hs 
concurrent CHR solver built on top of multisetwrite

MergeSort.hs 
is a chr solver application and is also described 
in Parallel Execution of Multi Set Constraint Rewrite Rules