Introduction
This page shows the version history of the K.U.Leuven JCHR system, starting from the original release by Peter Van Weert at the completion of his master's thesis, which we have labelled version 1.0.0 for convenience's sake. For subsequent releases we increase the last number for minor updates or bug fixes and the second number for larger updates or when backwards incompatibilities were introduced (to non-experimental features). Incrementing the first number is reserved for major updates...
The current version is a prototype, proof of concept implementation, developed to test and demonstrate the architecture, and to be used as a research vehicle. However, though there might be some implementation issues and bugs distinguishing it from a production-quality system, it is certainly complete and stable enough to be used readily in your applications. The system is also under active development, and each release is a step forward! We kindly ask our users to submit all issues they encounter, so we can keep improving the system.
Version 1.x
Version 1.6.0 (10-03-2008)
- Broken Feature Debug and trace support is broken and will be restored in upcoming versions.
- New Compilation Scheme Code generation has been rewritten from scratch and uses an entirely new compilation scheme, resulting in improved memory use. Recursive CHR programs no longer result in Java call stack overflows.
- New Feature
The generated code is compiled on-the-fly to Java bytecode.
For this to work, the JCHR compiler will try
to locate a java compiler on your system
(commonly a java compiler is installed as part of a
JDK).
If using Java 6,
javax.tools
is used. If using an older version, the non-core packagecom.sun.tools.javac
is used. For the latter to work, thetools.jar
has to be in the user class path (the archive is commonly located in thelib
directory of the JDK installation directory). The generation of source code and bytecode can be controlled using theoutput
option (by default both are generated). - New Analysis Functional dependencies are derived and incorporated in the join ordering.
- Replaced the propagation history analysis with a stronger instance that considers both the join ordering and information derived about set semantics.
- New Feature Each handler now contains a series of methods to reactivate constraints, either all constraints or all constraints of a certain type. These can be used to reactivate constraints after modifications are made in Java code. It is also possible to provide a filter to selectively reactivate constraints.
- Passive occurrences never check a history: this obvious fact is taken into account now to determine whether propagation rules need a history.
- Improved Analysis
Added an analysis that decides whether Java statements
will contain callbacks to the CHR handler or not.
This is important for analyses based on forms of
abstract interpretation (observation, history, ...).
All analyses have been adapted to take this information
into account. Before they were often too conservative
(e.g. now the compiler knows that
System.out.println
will probably not add any CHR constraints) or even incorrect. So the changes have improved both correctness and completeness of several existing analyses. Of course, for method calls on unknown classes, the analysis has to be conservative. It is however possible add extra information to the analyser it can use to improve its precision. There are two options:-
You can add annotations to your code
indicating which members are free
of calls to a CHR handler
(more precisely: to an external CHR handler).
We call these members JCHR-free members.
The annotation used for this is
annotations.JCHR_Free
. If added to a member (a method or a constructor) this means it is JCHR free; if added to a class it means all its members are JCHR free. You can even add the annotation to the package to an entire package if you prefer (see the discussion in section 7.4.1.1 of the Java Language Specification). -
You can add the class or member reflections
to the sets exposed by the
compiler.analysis.JCHRFreeAnalysor
class.
-
You can add annotations to your code
indicating which members are free
of calls to a CHR handler
(more precisely: to an external CHR handler).
We call these members JCHR-free members.
The annotation used for this is
- New Optimisation
Two clever improvements to the logical equality solvers
resulted in a 30% speedup for the
leq
benchmark. - Using set semantics results and constraint-coreflexivity meta information (both introduced in version 1.5.0) to detect rules that can never fire.
-
Improved runtime data-structures: instead of using general purpose
HashMap
's, specially tailored data structures are used for all runtime data structures (hash indices, hash-based propagation histories, and hash-based observer sets). This results in an overall improvement of speed (not that much), memory, and platform independence (earlier code relied on implementation details of Sun's reference implementation ofHashMap
that were not at all specified in the API). - Replaced the propagation history for single identifiers with an implementation based on linear probing hashing (the collision resolution used to be chaining). This resulted in substantial performance improvements: obviously less space is used, and also up to 35% gains in time are measured.
-
Reimplemented the iterators over doubly linked lists:
-
Fixed two outstanding issues:
they never throw
ConcurrentModificationException
s anymore, plus they no longer fail when removing elements after a call ofhasNext()
returningtrue
. - More interestingly: the new iterators are up to 15% faster than before.
- A distinction is made between universal, semi-universal and existentional iterators. In earlier versions the iterators used were always universal. The current existentional and semi-universal iterators are again 15% faster than their universal counterparts.
-
Fixed two outstanding issues:
they never throw
- For constraints that are never removed singly linked lists are used instead of doubly linked lists, and no storage backpointers are kept. This improves both memory and time performance.
- Added a path compression optimisation to the doubly linked list classes, which in certain (degenerate) cases results in time complexity improvements (amortised constant next element retrieval). We suspect time complexity of the double linked iterators is still not optimal (retrieving the next element in an iteration is probably still worst case linear). This could be solved by introducing extra indirections for the linked list pointers, and for instance using union-by-rank to make pointers equal. This would however result in too much constant time overhead for all regular, practical cases. The beauty of the path compression optimisation is that the latter cases are completely unaffected.
- Only the hash of indexed variables is observed. This can improve performance considerably.
- Backwards incompatibility
The
terminate()
method of theConstraint
class is encapsulated: only constraint handlers are supposed to terminate their constraints. - In the join ordering the order of multiple consecutive guards is no longer random, but determined using heuristics. Very selective and very cheap guards, are scheduled as early as possible.
-
For fixed classes of which you do not want to,
or cannot, alter the code to add the
JCHR_Fixed
annotation, there are now some solutions:-
An extra option, called
fixed
, can be used to tell the compiler to treat the class with the given fully qualified name as a fixed type. The option can be set from the command-line, or from within the source code. -
The
compiler.CHRIntermediateForm.types.Type
class contains a static fieldFIXED_CLASSES
that you can use to inspect and alter the compiler's knowledge on fixed types.
FIXED_CLASSES
set (cf. above) is initialised with about ten fixed types. -
An extra option, called
-
For built-in solvers only declaring a single constraint, the
@JCHR_Constraint
annotation no longer has to wrapped in an enclosing@JCHR_Constraints
annotation, but can be added directly to the class or interface. -
Instantiation exceptions are detected: if the
getValue()
method is called on an instance of one of the logical variable classes, and the variable is not instantiated, aruntime.InstantiationException
is thrown (aRuntimeException
, similar to the related, well-knownjava.lang.NullpointerException
). - For set semantics constraints that use a hash map on all all arguments, the number of constraints present in the store is determined in constant time (instead of in linear time for all other constraints).
- New Optimisation
A bug fix caused the
leq
benchmark to run twice as slow. Luckily, a new optimisation made up for this loss, making the benchmark run twice as fast again. The main idea is utilising set semantics (the set semantics analysis had to be refined) information to remove duplicate constraints early during rehashing. - The part of the propagation history of constraints that are terminated is released such that it can be reclaimed by the garbage collector, even if the constraints are still reachable (from user code).
- Bug fixes:
- Doubles can no longer occur in observer lists.
- Fixed some bugs in the delay avoidance analysis.
-
Critical bug fix in the generation of
includeProtected()
andincludePackage()
forpublic
generic handlers. - Using the raw type of a generic type (i.e. using the type without providing any type parameters) no longer results in a weird exception. A clear warning will be raised instead.
- In certain cases the late storage optimisations would result in lists of constraints that were not sorted on identifier, which could result in wrong results when constraint lists are merged (using the obvious linear algorithm of course). By only assigning constraint identifiers the moment constraints are stored, the problem is solved. This meant though that in certain rare cases a separate identifier is needed to be used in propagation histories.
- Fixed a critical bug that prevented rehashing (no observers were ever really attached to variables). The result after the fix was that the leq benchmark for instance took became twice as slow (no idea why it worked correctly before). Correctness is more important than speed though.
- Fixed a bug that sometimes caused an exception to be thrown during rehashing.
-
A
ConcurrentModificationException
can no longer be thrown when removing a rule that will never fire during compilation. -
Fixed bugs in the
isEmpty()
andcanAddFirst
method of linked constraint lists. Not sure what the impact will be though. Seems to improve performance a bit (memory is certainly improved as we saved out a member field)? - It took almost four hours, but we managed to track down two bugs that in some very rare case caused the compiler to fail when compiling multiple source files at once.
Version 1.5.1 (16-10-2006)
-
Improved the encapsulation of constraints with default or
protected
access. In version 1.5.0, these constraints were exposed throughpublic
methods likeiterator()
andfilter()
. This is no longer the case (only for non-public
handlers). If you have access to these more restricted constraints, you can however easily get a view of the handler that does include them in its constraint store inspectors. For example, the following iteration will iterate overpublic
(andlocal
) constraints, as well asprotected
constraints:for (Constraint constraint : handler.includeProtected()) System.out.println(constraint);
TheincludeProtected()
method is generated for allpublic
handlers, and has of courseprotected
access itself. TheincludePackage()
method is similar, and also includes constraints with default access. Note that this way,private
constraints are never exposed. If you pass a handler object returned by one of the two above methods to e.g. code outside the package, or, similarly, if you pass an instance of a non-public
handler class, this less trusted code will see the non-public
constraints as well. This is the programmer's responsibility. The whole purpose of non-public
constraints is to restrict access to them to trusted code (in the same package): if this code then leaks restricted information, it should not have been trusted in the first place! - Reactivating less occurrences: a new analysis tries to avoid reactivating occurrences that are not guarded. As a result, reactivation becomes cheaper, and less observers are attached. The analysis has been adapted to remain conservative: the refined semantics does not always allow skipping occurrences (unfortunately?).
- Replaced the propagation history analysis with a more powerful (and more correct) analysis, that uses the reactiveness results from the above analysis. Since this is the second analysis written in JCHR (the first being the observation analysis), the compiler is starting to need quite some bootstrapping!
-
The reactiveness results are also used to specialise code
generation for the generation optimisation.
This implied moving the generation field from the generic runtime
class
Constraint
to its generated subclasses. Therefore all your constraint classes will have to be recompiled when upgrading to this version. - Slight specialisation for the different-partners test in case the active constraint cannot be stored yet.
- Bug fixes:
- A JCHR handler can no longer be declared
protected
. -
The
removeSelf()
method of rehashable keys is no longer publicly accessible.
- A JCHR handler can no longer be declared
-
Improved the encapsulation of constraints with default or
Version 1.5.0 (10-10-2006)
- New Feature
JCHR handler source files now start with a
package
declaration, both syntactically and semantically analogous to the corresponding structure in Java, i.e.: if no package declaration is given the handler becomes part of the unnamed package, classes from the same package as the declared one do not have to be imported, etc. - Backwards incompatibility
The above new keyword of course implies the generated code
is no longer written to the
ud
directory as before, but to a directory corresponding to the package the handler is part of. - Backwards incompatibility
Constraints are no longer generated as top-level classes in
a separate source files. Instead, constraint classes are now
inner classes of their handler class. This ensures that
generated source files will not coincide if different
handlers in the same package define constraints with the same
name.
Generated tuple classes are generated as classes of the
runtime.tuples
package. - Backwards incompatibility Partly due to the above item, constraint classes are no longer parameterised. Instead, they share the type parameters of their enclosing handler class.
- Deprecated syntax
The
constraints
keyword is now deprecated, and support for this syntax will be discontinued in the near future. Instead,constraint
can now be followed by a comma-separated list of constraint declarations. There was never any real need for two distinct keywords, other then compatibility with both older Prolog systems (who usedconstraints
) and JaCK (who only offered theconstraint
keyword). Since recently the most prominent Prolog CHR system, the K.U.Leuven CHR System, has deprecatedconstraints
forchr_constraint
, we found the time ripe to make a similar decision: better now, while our language is still young and evolving, then later, when we have millions of users... - New Feature / Backwards incompatibility
The generated handler class is no longer
public
by default: instead, it takes the access modifier that is provided in the handler declaration. Examples can be found on the examples page. Most of the time, handlers will be declaredpublic
, but you can also use default (no modifier) access. As no other types can be declared in the same file,private
handlers do not make sense at the moment, and are thus not allowed. - New Feature / Backwards incompatibility
Similar to the above item, generated constraint classes are
no longer always public. Constraint declarations now also take
an access modifier. Valid are the familiar modifiers
public
,protected
,private
or no modifier (default accessibility), indicating which other classes are allowed to tell, lookup, inspect, etc. these declared constraints.private
constraints are essentially invisible for all classes other than their handler. A final, often occurring type of JCHR constraints are those that should only be told from within the JCHR rules of their handler, but that the user should be able to lookup and inspect nevertheless. The declaration of such constraints is preceded by thelocal
access modifier. This feature is still quite young, and might undergo some minor changes, but as our example handlers show, these access modifiers seem sufficient. - Backwards incompatibility
User-defined constraint objects (even if they are declared
public
) can only be created from within their handler. So, as of now the following syntax:new LeqConstraint<T>(X, Y, leqHandler).activate();
no longer works (actually, this syntax has already been deprecated since version 1.2.0). Instead, you always have to use the more natural:leqHandler.tellLeq(X, Y);
- New Analysis
Constraints that are never stored are detected
(as always only the relatively easy -- but often occurring!
-- cases for now).
No constraint stores have to be kept for these constraints,
improving mostly memory, but also some speed performance.
This analysis also has an influence on the detection of
passive occurrences, and of rules that cannot fire.
The latter two analysis have also been improved significantly
for this version (in the ram
simulator for example, no less then 31 passive occurrences
are detected!).
We also added an extra inspector method,
isStored(Class<? extends Constraint>
, to the generated handlers, allowing users to inspect whether certain constraints can (in theory) be stored in a particular handler. - New Analysis Set semantics constraints are detected (explicit set semantics only). The results of this analysis influence join ordering, index selection and, mostly, code generation. It can also help in detecting rules that can never fire under the refined operational semantics, enabling early detection of programming errors.
- New Analysis We added an observation analysis, which seems to be just as strong as the abstract interpretation based equivalent in our Prolog compilers. The results of this analysis improve never stored analysis and passive occurrence detection, and allow to generate more efficient code (constraint storage is delayed longer). The core of this analysis is implemented in JCHR.
- New Analysis In version 1.4.0 we tried to avoid the generation of some propagation histories of rules that could not be reactivated. This optimisation was incorrect in the general case. A new analysis, enabled partly by the observation analysis (cf. supra), analyzes correctly which occurrences do not have to check the propagation history upon activation, and which (propably) do. From this, it derives (correctly this time) which propagation rules really do not need a propagation history, and which (probably) do.
- New Feature
We extended the amount of meta-information that can be
provided about binary built-in constraints through the
familiar
JCHR_Constraint
: you can tell the compiler a binary constraint is antisymmetric, asymmetric, coreflexive, irreflexive, reflexive, symmetric, total, transitive and/or trichotomous. For more information on these fields, their semantics and their default values, we refer to the API specification ofannotations.JCHR_Constraint
. For the defenitions of these relations, you can also have a look at wikipedia. - Reflexivity information is exploited to improve the set semantics analysis.
-
Introduced a new built-in constraint
fail(String message)
, similar to the nullaryfail
built-in, but now with a user-defined failure message. - Backwards incompatibility The acute accents used to enclose infix identifiers are no longer valid syntax. They caused problems in editors and browsers, certainly when switching platforms. They are now replaced with regular single quotes. An example can be seen in the union find handlers (iuf and guf).
- New Feature
The generated handler code now features extra methods
get...Constraints(Filter)
, one per constraint, that allow you to get a filtered view of the constraints in their constraint store. For example, if you want to iterate over all prime numbers between 123 and 321, you can use (theprimes
handler is available on the examples page):PrimesHandler handler = new PrimesHandler(); handler.tellCandidate(1000); Filter<PrimeConstraint> myFilter = new InclusionFilter<PrimeConstraint>( @Override public boolean hasToInclude(PrimeConstraint constraint) { return (constraint.get$0() > 123) && (constraint.get$0() < 321); } ); for (PrimeConstraint constraint : handler.getPrimeConstraints(myFilter)) System.out.println(constraint);
You cannot directly subclass theFiltered.Filter
class, instead you should extend one of its subclassesInclusionFilter
,ExclusionFilter
,IndexInclusionFilter
orIndexExclusionFilter
. -
To get a filtered view of all constraints in the store, you
can use
Handler.filter(Filter)
. -
New built-in constraints for
Object
s: before onlyeq
/=
could be asked, which would be compiled to a call ofequals
, whereas as of now, the complementneq
/!=
can be used as well, which is translated to!equals
(i.e. a negated call toequals
). For primitive wrapper objects the compiler will first coerce the objects to their primitive values. Also new is that, for reasons of symmetry with primitive types, and to ease the transition for Prolog users, we let==
be an alternative infix identifier foreq/=
. Finally,ref_eq
/===
andref_neq
/!==
can now be used to ask reference equality and disequality of objects respectively. Note that the these infix identifiers take an extra=
over their Java equivalent. As in Java, both constraints can only be used between compatible expressions (i.e. one expression can be assigned to the other, possibly after some coercion). Remember that it is possible for built-in constraints to override these infix identifiers: when you declare aEqualitySolver
built-in solver for example,eq/=/==
between twoLogical
expressions will be translated to a call to this solver (cf. also next item). Note that for enumeration values, the compiler knows to always use reference equality, even if you useeq
/=
orneq
/!=
. -
Extended the meta-data regarding infix identifiers that can be
added to built-in constraint solvers. You can now:
-
Declare more then one infix identifier for each constraint:
the
infix
field is now an array of strings. Singleton arrays can still be written the same way as before, so existing annotations will still work. -
Declare the infix identifiers to aks and tell a constraint
separately. The
@JCHR_Constraint
annotation now has fields (both string arrays)ask_infix
andtell_infix
for this. You have to use eitherinfix
, or both the latter fields, or no infix field at all. You can set a field to the empty array if you want (e.g. only using infix identifiers to ask a constraint). -
You can even use different infix identifiers for each seperate
method. For this, the
@JCHR_Asks
and@JCHR_Tells
annotations have been given an extra fieldinfix
. The identifiers given here (or the empty array) override the default value given in the corresponding@JCHR_Constraint
annotation. If you use this feature, the compact notation of the constraint identifier field (e.g.@JCHR_Asks("eq")
as short for@JCHR_Asks(constraint="eq")
) can no longer be used, so it has to be written in full (@JCHR_Asks(constraint="eq", infix={"=", "=="})
)
-
Declare more then one infix identifier for each constraint:
the
-
User-defined constraints can also be declared to have more then
one infix identifier: the
infix
keyword can now be followed by a comma-separated list of infix identifiers. -
getTracer()
andsetTracer(Tracer)
methods are generated for handler classes (if thedebug
option indicates debug code has to be generated). -
Added two new
Tracer
implementations,runtime.debug.FileTracer
, that prints trace events to a given file, andruntime.debug.StatisticsTracer
, that collects basic runtime statistics like number of constraint activations, rule firings, etc. -
If you just want to use free logical variables (i.e. never bind
them to a value), you no longer have to pick some random type
for the variables: the
runtime
package now containsFreeLogical
andFreeLogicalEqualitySolver
. -
Bugs fixed, small code improvements, etc.
-
The
remove
trace event is no longer thrown for constraints that were not really stored. -
Improved the heuristics concerning coercion
translating built-in constraints: the generated code should
be closer to what you would write yourself.
For example: coercion methods for primitive wrappers are
now constrained to the the ones to their corresponding
primitive type (e.g.
Integer.intValue()
,Float.floatValue()
). -
No tracer code is generated in handler classes if the
debug
option isdefault
and no rule is annotated. - Fixed some crucial bugs in the resolution of conjuncts: statically imported method calls were not possible, and user defined conjuncts were not taken into account in guards (though the latter are not allowed, the use of such deep guards should be detected).
-
Specialized the generated code for the reset method introduced in
version 1.4.0 such that no
ConcurrentModificationException
can be thrown anymore while terminating the constraints. -
Fixed a bug in the parser that prevented the use of the
"
debug
" compiler option. - Propagation histories are no longer checked if the active constraint is not yet stored.
- Declarators that do not use identifiers are preferred over declarators that do. Remember the improvement introduced in version 1.4.0: lazy creation of identifiers is better where possible: as of now this will pay off even more.
- If some built-in solver does require an identifier, the unique identifier provided to it will be correct (even this was not true before).
- Some minor refactorings in the equality solver implementations: hash-observers are released if no longer needed (improves memory performance) and merges of hash-observer lists are only done when necessary (improves runtime performance). The effects of these changes will probably be rather marginal.
- Escaped character literals are treated correctly.
-
=>
is compiled as<=
- Nullary statically imported methods and nullary built-in constraints work.
- Fixed a critical bug in the symmetry analysis: kept occurrences cannot subsume other occurrences (or better put: it might subsume them, but we don't care, since the active constraint remains alive)!
- Fixed a critical bug in the greedy join ordering analysis: implicit guards with non-variable operands are no longer discarded!
-
The
- New Feature
JCHR handler source files now start with a
Version 1.4.0 (20-09-2006)
Because this is a somewhat more substantial release, we have tried to group the many changes and improvements that were made since version 1.3.3; a short overview:- The command line has been improved, and its possible options have changed.
- Many syntactic advances have been made, most notably in the context of variable declarations and (static) imports.
- Much progress is also made in the static analysis phase
- More performance improvements and corrections have been made to the runtime code and the compilation scheme.
- A final new feature is a simple (non-interactive) trace debugger.
- There have been many other changes and refactoring over the long period since the previous version, some of which are listed below.
The command line tool
- Backwards incompatibility: We switched to args4j version 2. The older version 1 we used before will no longer work!
-
The command-line compiler will now print a usage overview,
including overview of known options. At the time of writing,
this looks like this:
No input file(s) given... Usage: java compiler.Main [-options] files... (to compile one or more jchr source files) or: java compiler.Main [-options] < file (to compile a jchr source supplied through the standard input stream) where possible options include: -debug LEVEL : set the debug level (off/default/full) -hash : toggle hash indexing (yes/no; on/off; true/false) -standardinput : toggle blocking input from standard input stream
-
The
hashMap
option has been renamed tohash
. - The compiler now works if you provide it with a list of filenames (wildcards are currently not supported). This way more than one handler can be compiled in one session. This was not possible before because you had to provide the source file through the default input stream. The old mode of input can still be used if preferred: (only) if no filename is provided, the default input stream will be tried. The compiler will however no longer block if this stream is empty as it did before. If you want the compiler to wait for incoming data through the default input stream, use the standardinput option.
- Bug-fix: the compiler can now compile more than one handler, without restarting the virtual machine. Thanks to Eric Lindahl for pointing out this limitation.
-
There is one final new option,
debug
, which we discuss below.
Syntactic improvements
-
Added more syntactic sugar for passive pragma's. Before, you could use
-
the original, verbose (SICStus) Prolog syntax:
a#Id1, b # Id2, c <=> true pragma passive(Id1), passive(Id2).
Note that this rule probably does not even fit in its box anymore! -
since version 1.3.1 (JCHR only):
a # Id1, b#Id2, c <=> true pragma passive(Id1, Id2).
passive
):a#passive, b # passive, c <=> true.
We recently introduced this syntax in the K.U.Leuven CHR System as well (cf. e.g. the SWI Prolog Manual). Becausepassive
will probably always remain the most widely used pragma, K.U.Leuven JCHR now also offers even more concise syntax for passive declarations:a#, b #, c <=> true.
But, however easy it is now to write these annotations, use them with care: they should only be used to declare occurrences passive that really can never become active. They are not intended to be used to alter the semantics of a program, only to help the compiler with detecting passive occurrences (cf. also the new subsumption analysis). -
the original, verbose (SICStus) Prolog syntax:
- Constraint(s) declarations, built-in solver declarations and options can be defined in any order, and can be interleaved freely. Before these had to be done in some fixed order.
-
Nullary constraints (also known as flag constraints) can now
be written without cumbersome empty parenthesis. An example is the
findmin
constraint in the Fibonacci heap solver. The same is of course possible for built-in flag constraints. -
Several smaller fixes and improvements:
- Identifiers can now contain arbitrary unicode characters.
- Fixed some bugs in the parser and CIF builder: constructor invocations can now be used as an argument.
- Two bugs prevented method calls or constructor invocations without arguments.
- Field accesses or constructor invocations can now be used as conjunct (field accesses of course only in a guard).
- Boolean variables (primitive or wrapper) can be used as a conjunct in a guard.
null
can now be used as an argument
Variables
- New Feature:
Variables no longer have to declared per se: the compiler can now
infer most type information from the
constraint(s)
declarations. To be more concrete: variables are declared implicitly if you use them as a top-level argument in a head conjunct. This new feature eliminates the need of all those cumbersome variable declarations: in many handlers -- leq, bool, gcd, ram, fib_heap, ... -- no more variable declarations are needed at all. Also, if you use the same variable name in different rules, it no longer needs to have the same type, so you do not need to come up with a different name anymore (note that within the same rule however a variable can only have one type: cf. below).
Local variables on the other hand do still have to be declared. Local variables are variables that do not occur as a top-level argument in the head, and are used for the first time in the body of a rule (local variables are currently not yet allowed in (implicit) guards).- If a variable occurring as a top-level argument in the head of a rule has an identifier that was declared to be local, the non-local variable will simply hide the local variable (i.e. they can even have different types).
-
If a variables has the same name as an imported type
(no matter how it has been imported: implicit or explicit using
a single-type-import or a import-on-demand), it will hide
the type name.
A warning is generated by the compiler in that case,
because this leads to certain pathological cases like:
constraint c(Integer); ... c(String) ==> foo(String.valueOf(13)).
In the above example, the semantics dictates thatString
in the body is a variable of typeInteger
, i.e.String.valueOf(13)
is of typeInteger
, whereas most probably the user intended it to be of typeString
, the return type of the staticvalueOf
method of classString
. -
Unfortunately there are still some non-local variables that
could pose problems in the current version.
Luckily this only occurs very rarely, and is never a big problem.
When you use variables as a non-top-level argument
(i.e. in an implicit guard) in the head before you have used it
as a top-level argument. For example:
a(X.foo()), b(X) <=> bar(X). c(inc(X)) \ c(X) <=> true. d(inc(X), X) <=> fail.
None of the rules will compile. There are several ways you can solve this in the current version: reorder heads (not always applicable):b(X), a(X.foo()) <=> bar(X).
and/or make the guards explicit (always applicable):a(Y), b(X) <=> Y = X.foo() | bar(X). c(Y), \ c(X) <=> Y = inc(X) | true. d(Y, X) <=> Y = inc(X) | true.
Also, a more pragmatic variable declaration has been introduced to deal with these cases:pragma_var int X; c(inc(X)) \ c(X) <=> true.
Apragma_var
declaration is only valid in the rule directly following it. The type of such a pragmatically declared variable has to be identical to the formal type of the first use as a top-level argument in this rule. As soon as this somewhat artificial limitation is elevated, all you have to do is remove thesepragma_var
declarations.
We plan to remedy this unfortunate flaw in the future (though maybe not the near future).
- Deprecated syntax:
As we said above, only local variables have to be declared.
This is however no longer done using the legacy
variable
declarations, but with the newlocal
keyword, that is otherwise completely analogous. Support for the now deprecatedvariable
syntax (currently read aslocal
by the compiler) will be discontinued in the near future. - Backwards incompatibility:
All occurrences of a variable in a rule have to be of the
same type. This was not true before, which led to some counterintuitive
examples in previous versions:
constraints c(int), d(Logical<Integer>); ... variable int X; // Did compile: c(X), d(X) ==> foo(). // Gave a compilation error: d(X), c(X) ==> foo().
Also, there was actually an ambiguity in the body of such rules, which was more or less arbitrarily resolved. These situations are as of now simply prohibited. If you want to declare that two constraint arguments of a different type have to be equal in a matching -- which, as practice shows, hardly ever is the case -- simply use different identifiers and write the guards explicitly. - New Feature: Singleton variables are detected and replaced by anonymous variables. A singleton variable is a non-anonymous variable that is declared and used only once in the head, and that is never used in a guard or a body. The user also receives a warning because singleton variables could indicate programming errors. Note that this also has an impact on the generated code: variables that are never used are not declared and assigned a value to.
- For the same reason, a warning will also be generated if local variables are declared but never used.
- Backwards incompatibility:
Using the same named anonymous variable (i.e. variables
like
_X
,_Result
, ...) more than once as a top level argument in the head of a rule will now result in the generation of an implicit guard (i.e. they will be considered the same variable). This was not the case before. Every occurrence of_
on the other hand will still be treated as a different variable.
The restriction that anonymous variables, so also the named ones, cannot be used in guards, bodies, or as non-top-level argument in a head, also remains.
Imports
-
The implicit import of
java.lang
package is dealt with more correctly. - New Feature:
Static imports (both single static imports and static
imports on demand) are supported for static member types,
fields and methods.
Statically imported fields whose name start with an upper case letter could be mistaken for an implicit declaration of a variable if used as a top-level argument in a head. The Java code conventions however states that only constants should start with an upper case (in fact: constants should have all upper case names). Therefore the compiler will only consider a capitalized name an implicit variable declaration if it is not a constant (i.e. annotated withfinal
) statically imported field. Using other capitalized fields in the head will require the explicit use of the implicit argument (so you cannot profit from static imports there), but this should never occur if you obey the naming conventions. - New Feature:
One important consequence of the previous item is that
enumeration
types can easily be used (they are implemented in Java
using
final static
fields): all you have to do is use an import-on-demand for all theenum
class' fields. We extended the compiler with knowledge on the correct built-in constraints to compare enum values. An example can be seen in the new ram handler, implementing a ram simulator in JCHR. - Fixed a bug in the parser that caused it to fail on most import-on-demands.
- Fixed several other small bugs concerning import declarations (was only a problem in very contrived examples).
- Imports (both single-type and on-demand) now also work for inner classes.
- Accessing inner classes of an imported type works (accessing inner classes without importing works as well).
Static analysis
- New Feature: A reasonable subsumption checker was added. It detects some of the more common types of passive occurrences. In the leq handler for example it finds all two passive occurrences, in the bool it finds nine. In the ram handler it even discovered four passive occurrences I (Peter) was not aware of. Compared to the one used in the K.U.Leuven CHR system, it of course remains a very naïve version: still more interesting work awaits us here!
- New Feature: A quite good join-ordering analysis has been added to the compiler. The heuristic, greedy search algorithm used is closest to the one used by the HAL compiler (without the functional dependency analysis for now). This new analysis results in a substantial performance improvement for multi-headed rules (three or more heads).
- Index selection has been rewritten, but does more or less the same as before, besides of course the fact that it now comes after join-ordering is done!
-
Extremely basic guard simplification (removing rules with rules that
have equivalents of
fail
orfalse
in their guards). Expect more elaborate guard simplification someday!
Generated Code
-
The generated constraint classes override the
equals
andhashCode
methods. Theequals
uses built-in constraints to compare the different variables. -
A
reset
method is generated for each handler. Calling this method will terminate and remove all constraints of that handler. Note that this does not clear possible variable bindings (even if they were made by that handler at some time). - The file for a constraint with an infix identifier no longer gets generated twice.
-
Many small optimisations and corrections to the compilation scheme:
- Propagation histories are now based on the explicit constraint identifiers instead of the implicit object identities. This fixes a memory leak that could occur before, in theory (it has never been a problem in practice), plus it will simplify constraint object reuse later.
- No extra tuple objects get created for a propagation history update following a history test.
- Due to the improvements to the propagation history made in version 1.3.1 (less tuples are used, and if used they generally have a smaller arity) the correct tuple classes were not always generated.
- Constraints where an equal variable appears more then once as an argument are no longer added more then once as an observer. This should improve performance in some cases.
- Occurrences that cannot be reactivated are detected. This results in less calls to occurrence-methods on reactivation, less propagation histories and less pointless observations.
- One assignment is saved per call to an occurrence method.
- Removed the last test for explicit backjumping (we jumped to the innermost loop regardless of the outcome of this test).
-
Identifier generation fixed. The 12'th occurrence of a variable
X
in the same head no longer has the same identifier as the second occurrence of a variableX1
(used to be both$X10
).
Trace debugger
Added a new feature for reasoning explanation: it is possible to register listeners for important JCHR events (constraint activation, rule firings, ...). The current implementation is in a limited, experimental stage, but is already very helpful for debugging and understanding JCHR execution.
Code generation for debugging is controlled through options and pragma's. Thedebug
option can be set command-line or in the source file, and has three valid values:off
- No code for (debug) tracing will be generated.
default
-
This is the default value: code to add a tracer to a handler will
be generated. The only event told are rule-firing, from rules annotated
with
pragma debug
. I.e. by default none of the generated code is affected by this new feature. full
- More events are raised then in the default case: all constraint activations, reactivations, storages in and removals from the constraint store also result in events. Also, all rule firings will raise events, independent of possible pragma's.
Runtime code
-
Replaced one of the internal hash sets by one backed by an
IdentityHashMap
. The new version appears to be a bit slower (System.identityHashCode
is two orders of magnitude slower) but it uses less space. Combined with garbage collection costs the new version seems to scale a bit better to larger problems. - Naming logical variables lazily improves performance of benchmarks up to 40%, and reduces the memory footprint by an equally large amount.
- Made the iterators of single linked lists a bit faster.
Miscellaneous
- Fixed some ambiguities in the parser.
- Switched to the visitor pattern in many parts of the code. This design pattern made it possible to replace several switch statements and explicit casts, and to extend the model with extra functionality. The visitors are already used extensively in the analysis phase.
-
Added
void
to the primitive types in the meta-model. - Fixed a weird bug in one of the core classes responsible for translating built-in constraints to method calls. No idea how or why the old implementation was able to work correctly.
- Reimplemented one of the core algorithms for the reflection on types. The new version is far more elegant: the previous one was dozens of illegible lines of code! Consequently I am now also more convinced that it is correct (it is not complete though, but this was exactly the same before).
- Fixed a bug involving (what we call) "recursive generic types" (the reflection code would go in an infinite loop).
- Far too many code refactorings to mention here.
- Some interesting new feature we decided not even to document.
-
Version 1.3.3 (26-02-2006)
-
The generated store methods in
Handler
subclasses are no longer public. They were never intended to be used externally: you should use the tell methods instead. As a similar guideline: try to avoid the lookup-methods withHashMap
in their name, as they are not stable (they may be renamed or removed frequently in future versions of the compiler). - Equality solvers now throw a FailureException if they cannot make two logical variables equal. As already noted in the previous version, this behavior is likely to change as soon as support for backtracking is integrated with the system.
-
Bug fixes:
- Fixed a bug in the propagation history template.
- Character literals are now parsed correctly.
- Hash code of logical true and false are no longer both 0.
-
Constraints that have no (active) occurrences and are therefor
just stored were never removed from the constraint store
(the
stored
-flag was never set). - No more "zombie constraints"! Zombie constraints are constraints that are killed but find their way back into the constraint store (there were actually two ways this could happen, one of which was really hard to find). Some of these zombies were even killed several times and still kept popping up! Using these dead constraints as partners in the matching phase could clearly result in a wrong outcome. Luckily, we managed to keep the performance impact of the extra tests needed very low.
- It is no longer possible that certain hash keys are told to remove themselves from their hash indices, when there still are constraints behind them.
-
The generated store methods in
-
Version 1.3.2 (18-02-2006)
-
New Feature: Type-import-on-demand declarations are now supported,
just as they are in Java.
A type-import-on-demand declaration imports all the (accessible) types
of a named type or package as needed.
For example
import java.util.*;
allows you to address all types in thejava.util
package using their simple name. Unlike in Java it is not a compile-time error for a type-import-on-demand declaration to name a type or package that is not accessible or does not exist. Other then that type-import-on-demands behave completely analogously to their Java counterpart. - It is now a compile time error to import a type from the unnamed package.
- A compile-time error no longer occurs when importing the same type twice using single-type-import declarations.
- Experimental Feature:
The
fail
-keyword has been added to the JCHR language. The keyword can be used in the body of a rule. For now, if it gets executed a runtime-exceptionruntime.FailureException
is thrown and the execution of the handler is stopped. Its behavior is likely to change as soon as backtracking gets introduced into the system, but its use can nevertheless be interesting already, e.g. to detect programming bugs or unexpected inconsistencies. An example of its usage can be found somewhere in the bool-handler. Finally,false
is a synonym forfail
(and therefore an antonym fortrue
) when used as a constraint in the body of a rule. ExperimentalFeature: Each handler now truly is a collection ofConstraint
s (i.e. it implements the Java interfacejava.util.Collection<Constraint>
). Note that several methods are not yet implemented as efficient as they should be, but it still is a handy feature. You can e.g. use the handler in a for-each loop somewhere in your Java code:for (Constraint constraint : handler) { ... }
In fact: only those methods that require the size of the collection are inefficient at the moment (size()
,toArray()
, ...): iteration is implemented just fine!-
The
getConstraints()
-method is no longer generated, as the handler itself is already aCollection
containing all constraints. We did keep thelookup()
-method as a synonym for theiterator()
-method. -
The specification of the generated
lookup()
- andgetXXXConstraint()
-methods has been altered to reflect their implementation. -
The
toString()
of theHandler
s has been implemented.
-
New Feature: Type-import-on-demand declarations are now supported,
just as they are in Java.
A type-import-on-demand declaration imports all the (accessible) types
of a named type or package as needed.
For example
-
Version 1.3.1 (13-02-2006)
-
Backwards incompatibility: Due to popular demand
to shorten the way logical variables are declared,
LogicalVariable<Type>
has been renamed toLogical<Type>
. -
New feature: Logical variables and corresponding
built-in solvers have been created for primitive integers
and booleans (
the classes
LogicalInt
,LogicalBoolean
,BooleanEqualitySolver
,BooleanEqualitySolverImpl
,IntEqualitySolver
andIntEqualitySolverImpl
in packageruntime.primitive
). Using them instead of their generic counterpart (i.e.Logical<Integer>
,EqualitySolver<Integer>
, etc) improves efficiency, but can reduce code-reuse and increase the maintainability cost. In fact, maintainability cost is the only reason the other primitives (char
,long
,double
, ...) do not yet have a logical version! -
Experimental feature: For each user defined
constraint
XXX
a method:public Collection<XXXConstraint> getXXXConstraints()
gets generated.A method returning a collection containing all constraints currently in the store is also generated:This is no longer the case, as as of version 1.3.2 theHandler
itself is this collection, making the former method redundant.
Note that the collections returned by these methods tend to be quite inefficient in the current release (the size of the collection has to be recalculated each time), but they can nevertheless be used readily. We will try to make them more efficient in one of the following releases. A final new method that might be useful is:public Iterator<Constraint> lookup()
For more information on this method, and in fact all methods mentioned in this paragraph, we refer to the JavaDoc specification that is generated with them. - Remark: when compiling the generated code of a handler you might receive "unchecked generic array creation" warnings. This is due to a bug in the Java compiler, which is fixed since Tiger update 6 (more info).
- The compilation of the propagation history has been improved. The compilation optimisation we removed in the previous version, has been re-introduced (it was correct after all) and extended towards multi-headed rules. This will improve efficiency (the Fibonacci benchmark for one again runs as fast as it did before!).
-
Passive occurrences can now be declared in a comma-separated list
using
pragma passive(ID1, ID2, ...)
. The Fibonacci heap handler contains an example. - Java field accesses can now be used as an argument to constraint and method calls as expected.
- Created a new header for the generated source files. We probably went a bit overboard here :-)
-
Many bug fixes, some of which can have a huge impact
on correctness and performance:
- Merging sorted constraint lists could not have been implemented worse then it was. Fixing this bug will probably improve the compliance to the refined semantics (we do not know for sure it was not in compliance before, because for some reason it all seemed to work fine...) and will definitely benefit performance: the leq-benchmark now runs more then twice as fast!!
- Some bugs removed in the rehashing-code.
-
Fixed a bug that disallowed the use of type-parameter
as a solver. An example would be (the rest of the
solver is the same as the example on the
examples page,
mergesort.jchr):
... handler mergesort<T, C extends java.util.Comparator<T>> { solver C comparator; ... }
-
Comparisons between e.g. two
BigInteger
s orBigDecimal
s is done using theircompareTo
-methods, no longer through coercion todouble
. -
Comparisons between
String
s andBoolean
s (and thusboolean
s after coercion) are treated correctly (also using thecompareTo
-methods). -
Comparison between two
Character
s is treated correctly (through coercion tochar
). -
Using e.g. both
Logical<BigInteger>
andBigInteger
no longer results in ambiguity-exceptions. - Fixed a small bug in the bool-benchmark.
- The use of FreeMarker imports resulted in several redundant re-evaluations of the constraint-template. Fixing this has improved the compiler performance a bit.
- Fixed an important bug in the compilation scheme: if more then one occurrence of the same constraint occurred in a head, besides an occurrence of another constraint, the test for mutually different partner constraints was incomplete.
- Several other improvements and fixes...
-
Backwards incompatibility: Due to popular demand
to shorten the way logical variables are declared,
-
Version 1.3.0 (11-12-2005)
-
New feature: Anonymous variables in rule heads are now
supported. These variables do not have to be (in fact: cannot be)
declared, nor have a unique name. Example usage can be seen in the
Dijkstra and
Fibonacci heap handlers. Note
that not only
_
, but also "named" anonymous variables (which is a contradictio in terminis of course) like e.g._X
,_result
,... are allowed. The latter might be of interest to make code more readable. Anonymous variables are only allowed in rule heads, not in guards and bodies, since the compiler uses the declared variable-types to infer the constraints/methods it has to use. -
Backwards incompatibility: Since anonymous variables are
now supported, variables starting with an underscore ('
_
') are no longer allowed to be declared usingvariable
-declarations. -
Many bug fixes:
-
Nullary constraints (constraints with no arguments)
can now be used. Note that the
()
-postfix still has to be written everywhere. An example is thefindmin()
-constraint in fib_heap. - Due to a bug that was probably introduced in version 1.1.2 many constraint store indices did not get generated. Fixing this might have a serious (positive) impact on the performance of your constraint handlers.
- In certain cases (especially when using JCHR constraints as built-in constraints in another handler) local variables did not get declared in the generated code. This is fixed as of this version.
The propagation history of single-headed rules is now treated correctly. This affects the Fibonacci-benchmark, which now, unfortunately, is quite a lot slower then before (the fact that this handler used to work correctly was a mere coincidence).(This bug fix is fixed in version 1.3.1)- Partner constraints that are declared passive using a pragma are now treated as they should in propagation histories.
- The access rights of several important and not-so important members (most importantly in the runtime and generated code) were too restricting: access to them has to be emulated by synthetic accessor methods. By increasing their visibility performance should have been improved.
- Several other fixes.
-
Nullary constraints (constraints with no arguments)
can now be used. Note that the
-
New feature: Anonymous variables in rule heads are now
supported. These variables do not have to be (in fact: cannot be)
declared, nor have a unique name. Example usage can be seen in the
Dijkstra and
Fibonacci heap handlers. Note
that not only
-
Version 1.2.0 (27-11-2005)
-
Backwards incompatibility:
Instead of generating "
SharedState
" classes the K.U.Leuven JCHR System now generates "Handler
" classes. This means most code using JCHR handlers will have to be slightly refactored...
Rationale: Over time the so called "SharedState
" classes have obtained more functionality then originally anticipated. They have evolved from classes a user would not never be using directly, to central classes that are at least as important as theConstraint
classes themselves. Therefore the name "SharedState
" has not been very appropriate for some time now. Given that as of this version these classes can even be used as built-in solver for other JCHR constraint handlers (cf. infra), time seemed ripe to rename them (declarations like e.g. "solver BoolHandler;
" clearly look a lot more natural then e.g. "solver BoolSharedState;"
). -
Backwards incompatibility: Some time now I have been somewhat
malcontent with the names of our annotations, so, as long as we are
renaming things, why not act on it now? Annotation names are now
prefixed with "
JCHR_
" instead of "CHR
" and start with a capital (e.g.JCHR_Constraint
andJCHR_Asks
instead ofCHRconstraint
andCHRasks
).
Rationale: Pure conventional and subjective aesthetic reasons. Furthermore this change will not affect many users, as we doubt anyone has actually implemented a built-in solver or introduced new coercible variable types... -
New feature:
JCHR constraint handlers now can be used as built-in constraint
solvers in other JCHR handlers, as we already mentioned above. To do this
they have to be declared using the
solver
keyword, just as we would do with any other built-in solver.
In order for this to work, the generatedHandler
classes (replacing theSharedState
classes: cf. supra) very elegantly contain the necessary annotations and tell-methods (cf. also infra). Note that JCHR constraints cannot be used in guards, since they cannot be asked, nor can they be used in a head, since they are considered built-in constraints in the new JCHR handler. In other words: they are pure tell built-in constraints and can thus only be used in the body of a rule.
An excellent example is the implementation of Dijkstra's algorithm in JCHR using a JCHR handler that implements a Fibonacci heap based on work of Jon Sneyers [extended report].This example will be put online later as it has revealed the existence of a bug and the need for some new features (support for anonymous variables and constraints with arity zero).Meanwhile the example has been put online (cf. the examples page) as the bug has been fixed and the necessary features added (version 1.3.0). - New feature / guideline:
As of now the generated JCHR
Handler
classes contain methods to tell the constraints they handle. TheLeqHandler
for instance will contain methods like (note the annotation!):@JCHR_Tells("leq") public final void tellLeq( LogicalVariable<T> $X0, LogicalVariable<T> $X1 ) { new LeqConstraint<T>($X0, $X1, this).activate(); }
Instead of directly using for instance:new LeqConstraint<T>(X, Y, leqSharedState).activate();
users are encouraged to use the more natural:leqHandler.tellLeq(X, Y);
(note the shift in terminology fromSharedState
toHandler
!!!) as exemplified by the gcd-example. This new statement is more uniform and instinctive and could prove to be more stable in future versions (even though there are no concrete plans to change its implementation...). The extra indirection should not introduce a large performance penalty, so inlining this method explicitly will rarely be necessary.
-
Backwards incompatibility:
Instead of generating "
-
Version 1.1.4 (21-11-2005)
-
Fixed a bug preventing the use of
Comparator
built-in solvers. An example is this alternative definition of a mergesort-handler (the rest of the solver is the same as the example on the main page, mergesort.jchr):... handler mergesort<T> { solver java.util.Comparator<T> comparator; ... }
-
Fixed a bug preventing the use of
-
Version 1.1.3 (18-11-2005)
- Numbers larger than 1000 are printed correctly in the generated code, and a point is always used for decimal numbers. (123456.789 is no longer printed as 123.456,789). Thanks as usual to Armin Wolf and his students for reporting this bug.
-
The students of Armin also remarked that negative numbers are not
accepted by the parser. This is related to the open issue of mathematical
operators in general: for instance:
intUtil.add(X, Y)
has to be used instead of the commonX+Y
syntax. Solving this issue in general will necessitate a major rewrite of the ANTLR parser some day. For now I have adopted an analogous pragmatic solution and addedneg
-methods to the different util-classes (i.e. you can use e.g.intUtil.neg(123)
instead of-123
). - Finally, a bug we have discovered ourselves: in the generated code
multiple upper bounds were separated using comma's instead of
&
's. This silly bug is fixed now.
-
Version 1.1.2 (14-11-2005)
- User-defined constraints that are never used in the head of a rule are generated correctly. Thanks to Armin Wolf and his students for reminding us.
- Bug fixes:
- certain lookup methods did not get generated.
- occurrences like
c(X, X)
in the head of a rule should no longer cause problems.
-
Version 1.1.1 (10-11-2005)
- New feature: Passive pragmas have been added. The syntax and semantics in the K.U.Leuven JCHR system are completely analogous to the passive pragmas offered by Prolog systems. Read more about them here (of course you will find it also in our manual some day...). These annotations offer a pragmatic solution to the (hopefully temporary) fact that the K.U.Leuven JCHR compiler does not yet perform the necessary static analyses to detect passive occurrences automatically.
- New feature: The constraint stores have been made more user-friendly. Before the emphasis here was mainly on the efficiency dimension, leading to scattered constraint stores using hash-indices. From now on the generated constraint stores will always offer a method to iterate over all the constraints of a chosen type. Note that when the handler itself does never use this type of lookup of a particular type of constraint, no guarantees are made about the order in which the constraints are iterated (due to the hash-indices). Also in this case, fail-fast behavior can occur when the hash-indices are altered while iterating.
-
Version 1.1.0 (09-11-2005)
- Backwards incompatibility:
The
fixed
keyword can no longer be used and has been replaced by the shorter, more elegant and Prolog-like+
type-modifier. [guf.jchr, mergesort.jchr] - Several bug fixes in the parser, intermediate form and the code-generator enable the usage of upper-bounds, as exemplified by the mergesort-example [mergesort.jchr].
- Backwards incompatibility:
The
-
Version 1.0.3 (09-10-2005)
- Bug fix: assignments to local variables are being treated correctly.
- Some error messages given by the system when using illegal syntax have been improved.
Open issue: usage of local variables does not always work like it should. This will be addressed in one of the next versions.
-
Version 1.0.2 (22-09-2005)
- Bug fix: multi-headed rules with kept constraints of a different type than the active constraint should no longer cause problems. Thanks again to Armin Wolf and his students for pointing this out.
-
Version 1.0.1 (14-09-2005)
- Many classes and variables are renamed, spelling occurrence with two r's as it should.
- Tuple-bug fixed: the "import TupleX"-statements (only) get generated if required (thanks to Armin Wolf for bringing this to our attention).
- Several other minor bug fixes.
-
Version 1.0.0 (May 2005)
The original release by Peter Van Weert at the completion of his master's thesis.