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.


The multisetrewrite library is implemented in Haskell and available


(look for the multisetrewrite library among the Concurrency packages)


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.


Anonymous said...

welcome to the wow power leveling, cheap service site,WoW Gold buy cheap wow gold,wow gold,world of warcraft buy wow power leveling

Anonymous said...

WoW shares many wow gold of its features with previously launched games. Essentially, you battle with Cheapest wow gold monsters and traverse the countryside, by yourself or as a buy cheap wow gold team, find challenging tasks, and go on to higher Cheap Wow Gold levels as you gain skill and experience. In the course of your journey, you will be gaining new powers that are increased as your skill rating goes up. All the same, in terms of its features and quality, that is a ture stroy for this.WoW is far ahead of all other games of the genre the wow power leveling game undoubtedly is in a league of its own and cheapest wow gold playing it is another experience altogether.
Even though WoW is a wow gold cheap rather complicated game, the controls and interface are done in buy warhammer gold such a way that you don't feel the complexity. A good feature of the game is that it buy wow items does not put off people with lengthy manuals. The instructions cannot be simpler and the pop up tips can help you start playing the game World Of Warcraft Gold immediately. If on the other hand, you need a detailed manual, the instructions are there for you to access. Buy wow gold in this site,good for you ,WoW Gold, BUY WOW GOLD.