Multi-set rewrite rules with guards and a parallel execution scheme

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.
    
  
  
• 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.