Example JCHR Handlers

for the K.U.Leuven JCHR System

Contents

This page contains a collection of example JCHR handlers illustrating most of the systems features. Some examples of how to use the compiled handlers from within a Java application are also provided. Example usage of several other handlers can be found in our benchmark collection. For more information on how to compile and run the examples, we refer to the manual on the documentation page.

All the examples are tested with the latest version of the K.U.Leuven JCHR System. It is possible they do not work with older versions.

Most of these examples are 'classic' CHR handlers, ported to Java. Many visitors might want to skip the following acknowlegements and go directly to the examples.

Acknowledgements

These examples are based upon handlers found throughout the literature or e.g. on the CHR Website or WebCHR.

The union-find, Dijkstra and Fibonacci heap handlers are adapted from respectively:

• T. Schrijvers and T. Frühwirth. Implementing and Analyzing Union-Find in CHR , K.U.Leuven, Department of Computer Science, Report CW 389, July, 2004. [report, online appendix]
• Jon Sneyers, Tom Schrijvers and Bart Demoen. Dijkstra's algorithm with Fibonacci heaps: An executable description in CHR, 20th Workshop on Logic Programming (WLP'06), Vienna, Austria (Fink, M. and Tompits, H. and Woltran, S., eds.), pp 182-191, February 2006 [proceedings, paper + extented report, BibTeX]

The Fibonacci examples were inspired by an attended talk by Thom Frühwirth at CP 2005:

• Thom Frühwirth, CHR - Programming with a Chinese Horse, invited talk, 11th International Conference on Principles and Practice of Constraint Programming (CP 2005), Sitges, Spain, October 2005 [slides, tutorial notes]

Finally, the Turing and RAM machine simulators were easily ported from:

• Jon Sneyers, Tom Schrijvers and Bart Demoen. The Computational Power and Complexity of Constraint Handling Rules, 2nd Workshop on Constraint Handling Rules (CHR'05) at ICLP'05, Sitges, Spain (Schrijvers, T. and Frühwirth, T., eds.), October 2005, Best Paper Award [proceedings, paper]

The examples

File(s)	Description
leq.jchr Leq.java	A prototypical example of a generic handler is this "lesser-than-or-equal-to" handler, amongst other things also illustrating infix notation for constraints. Leq.java shows how easy it is to create and use a built-in solver and a generic handler from within Java code. Read the documentation of the source code for more information.
bool.jchr	A pure constraint solver, a bit larger than the other examples, but nonetheless just as intuitive, flexible and efficient.
gcd.jchr gcd2.jchr Gcd.java	Using a well-known algorithm--called Euclid's algorithm--this handler calculates the greatest common divider of two numbers. This is not a pure constraint solver, but illustrates the use of CHR as a "general purpose" constraint programming language. gcd2.jchr is a faster variant. Gcd.java shows how to call the gcd-handler from Java.
fib_rec.jchr fib_tab.jchr fib.jchr fib_bo_inf.jchr fib_bo_all.jchr fib_bo.jchr	Some handlers that calculate the famous Fibonacci numbers: fib_rec.jchr is a naive, recursive implementation, with well-known exponential complexity due to recomputations of smaller numbers. A small adaptation however gives us a very efficient algorithm (fib_tab.jchr). Previously computed numbers are kept in the constraint store, preventing unnessary recomputation. This technique is called tabulation. fib.jchr is a less efficient variant, using a simplification rule instead of a simpagation rule. Unless otherwise noted, this is the version used in published benchmarks. The above handlers compute Fibonacci numbers top-down. It is equally straightforward to write bottom-up versions in JCHR: fib_bo_inf.jchr just starts calculating all Fibonacci numbers and printing them to the standard output. Note that this is a non-terminating handler, as clearly no fix-point will ever be reached (pressing CTRL+C will stop execution on most systems). A small modification gives us fib_bo_all.jchr, a handler that calculates all Fibonacci numbers up to a given maximum. This is the bottom-up equivalent of fib.jchr. If you are only interested in the last number, again only a small change is needed: fib_bo.jchr! These handlers also show one of the advantages of using Java as a host language, namely a rich class library. The BigInteger class offers an easy and efficient way to represent arbitrary large integers. They also illustrate the elegant side-by-side use of logical and primitive variables.
acker.jchr tak.jchr tak_tab.jchr	Two more examples similar to the Fibonacci handlers, computing two other famous functions: acker.jchr implements the Ackermann function. Note that its value grows extremely quickly; even for small inputs, for example (4,3), the values of the Ackermann function are so large that they cannot be feasibly computed. The two other handlers both compute the TAK function, or Takeuchi Function. One version uses the naïve implementation, the other is an optimized implementation that uses tabulation.
guf.jchr	The generic union-find handler is a nice example of the possibilities of generic handlers, easing the transition of untyped Prolog to strongly typed Java.
iuf.jchr	The integer union-find handler is a modified version of the previous handler using primitive integers. Note that without generic handlers one would have to make such a modification for each type of variables required, not only for the primitive types!
primes.jchr	Like the gcd-handler not a pure constraint solver, this handler is nevertheless a nice example of the powerful declarative characteristics of Constraint Handling Rules. It uses the Sieve of Eratosthenes to calculate all prime numbers up to a given maximum.
mergesort.jchr	Again an example of the use of CHR as general purpose programming language, this two-rule handler illustrates the use of upper-bounds within generic handler declarations. Have a look at the corresponding benchmark to see how it is used.
dijkstra.jchr	This handler is a JCHR implementation of Dijkstra's classical shortest path algorithm. Most notably is the illustrated use of JCHR constraints as built-ins (this handler uses a Fibonacci heap, which is itself implemented in JCHR!).
fib_heap.jchr	An implementation of the Fibonacci heap data structure with optimal time complexity. This handler is used by the Dijkstra handler, but can just as well be used elsewhere.
turing.jchr Direction.java	Writing a Turing machine simulator in (pure) JCHR was probably the easiest way of showing the JCHR language is Turing complete. We used a simple enum class in this example, Direction. This class should be placed in the examples/turing package. The handler itself is part of the same package.
ram.jchr Instruction.java	A JCHR simulator of the standard-arithmetic Random Access Machine (RAM). Shows the use of static imports, and how enums can be imported and used elegantly. The examples.ram.Instruction enum class, part of the same package as the ram handler, is needed to compile and run this example.

All examples are part of the examples package, or a subpackage thereof. Remember this if you compile them.