Tuesday 28 October 2008

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.

No comments: