Version History

since May 2005

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 package com.sun.tools.javac is used. For the latter to work, the tools.jar has to be in the user class path (the archive is commonly located in the lib directory of the JDK installation directory). The generation of source code and bytecode can be controlled using the output 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:
    1. 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).
    2. You can add the class or member reflections to the sets exposed by the compiler.analysis.JCHRFreeAnalysor class.
  • 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 of HashMap 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 ConcurrentModificationExceptions anymore, plus they no longer fail when removing elements after a call of hasNext() returning true.
    • 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.
    The combined effect is that constraint iteration may become up to 28% faster than before. The primes benchmark for instance is now 27% faster.
  • 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 the Constraint 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 field FIXED_CLASSES that you can use to inspect and alter the compiler's knowledge on fixed types.
    If we encounter fixed classes, we will build them statically into the compiler. Currently the FIXED_CLASSES set (cf. above) is initialised with about ten fixed types.
  • 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, a runtime.InstantiationException is thrown (a RuntimeException, similar to the related, well-known java.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() and includePackage() for public 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() and canAddFirst 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 through public methods like iterator() and filter(). 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 over public (and local) constraints, as well as protected constraints:

      for (Constraint constraint : handler.includeProtected())
      	System.out.println(constraint);
    

    The includeProtected() method is generated for all public handlers, and has of course protected access itself. The includePackage() 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.

• 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 used constraints) and JaCK (who only offered the constraint keyword). Since recently the most prominent Prolog CHR system, the K.U.Leuven CHR System, has deprecated constraints for chr_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 declared public, 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 the local 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 of annotations.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 nullary fail 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 (the primes 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 the Filtered.Filter class, instead you should extend one of its subclasses InclusionFilter, ExclusionFilter, IndexInclusionFilter or IndexExclusionFilter.
  • To get a filtered view of all constraints in the store, you can use Handler.filter(Filter).
  • New built-in constraints for Objects: before only eq/= could be asked, which would be compiled to a call of equals, whereas as of now, the complement neq/!= can be used as well, which is translated to !equals (i.e. a negated call to equals). 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 for eq/=. Finally, ref_eq/=== and ref_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 a EqualitySolver built-in solver for example, eq/=/== between two Logical 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 use eq/= or neq/!=.
  • 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 and tell_infix for this. You have to use either infix, 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 field infix. 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={"=", "=="}))
  • 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() and setTracer(Tracer) methods are generated for handler classes (if the debug option indicates debug code has to be generated).
  • Added two new Tracer implementations, runtime.debug.FileTracer, that prints trace events to a given file, and runtime.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 contains FreeLogical and FreeLogicalEqualitySolver.
  • 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 is default 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!

• 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 to hash.
  • 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).

    New as of this version are in-head pragma's (for now only 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). Because passive 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).
  • 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 that String in the body is a variable of type Integer, i.e. String.valueOf(13) is of type Integer, whereas most probably the user intended it to be of type String, the return type of the static valueOf method of class String.
    • 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.

      A pragma_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 these pragma_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 new local keyword, that is otherwise completely analogous. Support for the now deprecated variable syntax (currently read as local 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 with final) 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 the enum 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 or false in their guards). Expect more elaborate guard simplification someday!

  Generated Code

  • The generated constraint classes override the equals and hashCode methods. The equals 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 variable X1 (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. The debug 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.

  After some more experimentation, these settings are likely to change in future versions, as well as the events that are raised. It would be e.g. interesting to integrate with the built-in solvers, to have a more fine-grained control on which events should be raised, etc.

  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 with HashMap 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.

• 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 the java.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-exception runtime.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 for fail (and therefore an antonym for true) when used as a constraint in the body of a rule.
  • Experimental Feature: Each handler now truly is a collection of Constraints (i.e. it implements the Java interface java.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 a Collection containing all constraints. We did keep the lookup()-method as a synonym for the iterator()-method.
  • The specification of the generated lookup()- and getXXXConstraint()-methods has been altered to reflect their implementation.
  • The toString() of the Handlers has been implemented.

• 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 to Logical<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 and IntEqualitySolverImpl in package runtime.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 the Handler 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 BigIntegers or BigDecimals is done using their compareTo-methods, no longer through coercion to double.
    • Comparisons between Strings and Booleans (and thus booleans after coercion) are treated correctly (also using the compareTo-methods).
    • Comparison between two Characters is treated correctly (through coercion to char).
    • Using e.g. both Logical<BigInteger> and BigInteger 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...

• 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 using variable-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 the findmin()-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.

• 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 the Constraint 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 and JCHR_Asks instead of CHRconstraint and  CHRasks).
    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 generated Handler classes (replacing the SharedState 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. The LeqHandler 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 from SharedState to Handler!!!) 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.

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

• 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 common X+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 added neg-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.
    Thanks again to Armin Wolf and his students for pointing these out.

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

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