### Latest news/updates

- Sat Dec 6 18:34:20 CET 2008:
- Parallel join pattern with guards and propagation extension built on top of multisetrewrite.
- Check here here for more information.

- Parallel join pattern with guards and propagation extension built on top of multisetrewrite.
- Wed Nov 12 11:08:47 CET 2008:

New multisetrewrite-0.1.1 version uploaded to hackage

- Includes more examples, a CHRSolver.hs and Join.hs abstraction

built on top of multi-set rewrite

- Some fun examples using these abstractions: GossipingGirls and BaggerProblem.

### Brief description

We provide a library for multi-set rewrite rules with guards. Rewrite rules are executed concurrently as long as they operate on non-overlapping left-hand sides. We make use of highly-concurrent, non-blocking data structures based on CAS lists. Thus, we can parallelize concurrent rule executions on a multi-core architecture.

The library is similar in style to the below described actor library. The difference is that while actors run concurrently, their receive clauses (sort of multi-set rewrite rules) are only executed sequentially.

### Download

The multisetrewrite library is implemented in Haskell and available

via

http://hackage.haskell.org

(look for the multisetrewrite library among the Concurrency packages)

### Examples

The library comes with two examples (will hopefully increase over time).

#### Concurrent stack

The gist of the multi-set rewrite rules describing a concurrent stack (the actual example in Stack.hs is more verbose, after all it's 'only' a library and not

a new compiler).

[push x, pop y] .->. y := x

[push x, stack s] .->. stack (x:s)

[pop y, stack s] `when` (isNotEmptyStack s) .->. let (x:xs) = s

y := x

stack xs

push is synchronous whereas pop and stack are asynchronous. The above shows how to encode join-patterns via multisetrewrite. We are more expressive than join-patterns because we also support guards, non-linear (aka shared) variables (doesn't show up in the above).

#### CHR solver

On top of multisetrewrite we implement a CHR solver. See CHR.hs in the distribution.

To illustrate the expressive power, we implement the mergesort algorithm

via multi-set rewrite rules.

Here's the gist of the rules (as said above already, the actual implementation is more verbose).

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

Merge(n,a), Merge(n,b) when a < b <==> \Leq(a,b),\Merge(n+1,a)

Points to note:

- The right-hand side of the first rule uses a mix of propagation and simplification. Leq(x,a) is propagated (ie not removed) whereas Leq(x,b) is simplified.
- We make use of non-linear variables and guards in both rules.