faster hashtable lookups for int and natural types

[chr.git] / ChangeLog

Jan 10, 2008

  * TS: Type check constraint declarations.
  * TS: Trie stores hidden behind `experimental' option.
  * TS: New option `verbose' prints constraint indices.
  * TS: Don't compute term_hash for int and natural types.

Jan 9, 2008

  * TS: Avoid trivial warning for declare_stored_constraints.
  * TS: Bug fix: missing full store was causing compiler to loop.

Jan 9, 2008

  * TS: Bug fix: atomic_constants store was causing compiler
        to loop.
  * TS: Clean-up and avoid adding additional global_ground store
        if atomic_constants store covers all cases.
  * TS: Clean-up and bug fix.

Jan 7, 2008

  * TS: Performance improvement: use new store
        implementation for multi-argument lookups
        on manifest ground terms. Should be faster than 
        hashtable.

Jan 4, 2008

  * TS: Performance improvement: use new store
        implementation for single-argument lookups
        on manifest atomics. Should be faster than
        hashtable. Will be generalized to arbitrary
        manifest ground lookups and non-manifest
        atomically typed lookups .
        
Jan 3, 2008

  * TS: Modified error messages of declare_stored_constraints
        option, to distinguish between stored, temporarily stored
        and never stored.
  * TS: write/1, writeln/1 and format/2 are now treated as non-binding
        builtins.
  * TS: Properly inline inthash constraint lookup.

Dec 31, 2007

  * TS: Additional assertion # default(Goal) for the
        declare_stored_constraints, which specifies that
        an unconditional simplification rule for the constraint
        must be added to the end of the program. The Goal
        parameter specifies the goal of that rule, e.g.
        true or fail or throw(...). Experimental.

Dec 29, 2007

  * TS: Experimental option declare_stored_constraints for
        telling the compiler to warn for stored constraints
        that are not asserted to be stored. Use the
                :- chr_constraint f(...) # stored.
        notation for asserting that a constraint is expected to
        be stored.

Dec 27, 2007

  * TS: Inline constraint lookup.
 
  * TS: Precompile term hashing.
 
Sep 26, 2007

  * TS: Code cleaning was hampered by line numbers.
        Reported by Mike Elston.

May 2, 2007

  * PVW: Bug fix in observation analysis.
  * PVW: Consistency checks of experimental history pragma.

Apr 5, 2007

  * TS: Lessened worst bottlenecks in CHR compiler,
        in the guard simplification phase.

Mar 26, 2007

  * TS: Experimental dynattr option, for dynamic size attribute terms.

Mar 16, 2007

  * TS: Extended observation analysis (abstract interpretation)
        to deal with disjunctions. With Paolo Tacchella.

Mar 14, 2007

  * TS: Renamed hprolog:substitute/4 to substitute_eq/4, because of
        name conflict with library(edit).

Mar 12, 2007

  * TS: Use line numbers in error and warning messages.

Mar 8, 2007

  * TS: Added maintenance of line numbers through CHR compilation
        as an option: chr_option(line_numbers,on).

Mar 5, 2007

  * TS: Bug fix: setarg/3 instantiation error reported by Mike Elston.
        Caused by missing suspension argument in debug off, optimize off
        mode.

Feb 22, 2007

 * LDK: O(1) removal from hashtables, with experimental
        chr_option(ht_removal,on).

Jan 25, 2007

 * PVW: Bugfixes for optional use of CHR constraints in rule guards.

Jan 18, 2007

  * PVW: Optional use of CHR constraints in rule guards.

Nov 20, 2006

  * TS: Bug fix in compiler_errors.pl.

Oct 25, 2006

  * TS: Bug fix in occurrence subsumption by Jon Sneyers.

Oct 18, 2006

  * TS: New preprocessor feature.

  * TS: Parametrization of experimental chr_identifier type.

Oct 16, 2006

  * TS: More inlining.

  * TS: Stronger static type checking.

  * TS: Omitted buggy FD analysis from bootstrapping process.

Oct 12, 2006

  * TS: More inlining.

  * TS: Experimental chr_identifier type.

Oct 10, 2006

  * TS: Allow for empty type definitions aka phantom types. These are 
        useful for some type-level tricks. A warning is issued so the 
        user can check whether a phantom type is intended. No other
        phantom type-specific checks are in place yet.

  * TS: Fixed static type checking of built-in types.

Oct 9, 2006

  * TS: The dense_int type can now appear on the rhs of type alias
        definitions.

Oct 3, 2006

  * TS: Fixed bug concerning matchings between ground and possibly
        non-ground arguments.   

Oct 2, 2006

  * TS: Fixed a bug in code generation, overeager removal of a clause.

Sep 28, 2006

  * TS: Refactored some code.

Sep 22, 2006

  * TS: Add exception handler to initialize chr_leash in new threads.
  
Sep 18. 2006

  * TS: Bug fix for programs in debugging mode.

Aug 30, 2006

  * JW: Fixed make clean
  * JW: Enlarged stacks to make build succeed

Aug 24, 2006

  * JW: Add target ln-install

Aug 21, 2006

  * TS: Fixed wrong arities in not inlined predicates. Mike Elston.

Aug 18, 2006

  * TS: Code clean-up, more inlining, only generate used imports.

Aug 17, 2006

  * TS: Inlining and more specialization of auxiliary predicates.

Aug 10, 2006

  * TS: Fixed bug for constraints without rules in debug mode.

  * TS: Compiler clean-up

  * TS: Experimental var_assoc_store.


Aug 9, 2006

  * TS: Various minor code generation improvements, including smaller
        suspension terms.

Aug 8, 2006

  * TS: Absolutely no lock checking when check_guard_bindings is disabled.

Aug 4, 2006

  * TS: Minor optimizations for (-) arguments.

  * TS: Important optimization for awakening fewer suspended constraints

Aug 3, 2006

  * TS: Fixed typo in static type checker.

  * TS: Documented static and dynamic type checking.

Aug 2, 2006

  * TS: Fixed bug (type alias related) in static type checker. Mike Elston.
 
  * TS: Added static type checking on variable matching in rule heads.

  * TS: Added static type checking on CHR constraints in rule bodies.

Aug 1, 2006

  * TS: New (limited) compile time type checking of rule heads.

Jul 28, 2006

  * TS: New experimental robustness feature in debug mode:
        runtime type checking of CHR constraints.

Jul 5, 2006

  * TS: Minor bug fixes.

Jun 22, 2006

  * TS: Improved performance of ai_observation_analysis,
        mainly via additional tabling and passive declarations.

Jun 8, 2006

  * TS: Disabled some code only intended for SICStus.

  * TS: Fixed bug in removal of constraints. Spotted by Leslie De Koninck.

Jun 7, 2006

  * TS: Next fix to tracer. Cconstraints in propagation
        rules are shown in textual order.

Jun 2, 2006

  * TS: Next few fixes to tracer. Constraints in simpagation rules
        are now shown on the right side of the backslash.

Jun 1, 2006

  * TS: Synchronization with SICStus version of K.U.Leuven CHR.

  * TS: First few fixes to tracer. Cconstraints in simplification
        rules are shown in textual order. Constraint insertions
        are always shown.

May 17, 2006

  * TS: Termination bug fixed in guard_entailment.

  * TS:  Runtime library predicate run_suspensions is now specialized
        per constraint, avoiding requirement of fixed suspension layout.

  * TS: Further update to suspension term layout. Only constraints for
        which the propagation history is used get a history field.

May 9, 2006

  * TS: Ignore propagation rules with trivial body 'true'.

Apr 24, 2006

  * TS: Guard entailment now first simplifies the formula it processes,
        in order to reduce the number of disjunctions, to obtain a smaller
        search tree.

Apr 22, 2006

  * TS: Bug fix by Jon Sneyers:  type aliases now support built-in types.
        Spotted by Mike Elston.

  * TS: Small refactorings based on Ciao port experience.

  * TS: Removed -singleton stylecheck option now that portray_clause
        prints singleton variables as _.

Apr 19, 2006

 * JW: Make library(chr) load its private stuff silent.

Apr 14, 2006
 
 * TS: Bug fix: too many guards were locked.

Apr 11, 2006

  * TS: Most runtime library predicates are now specialized
        per constraint, avoiding generic =.. and lists code.

        Mayor update to suspension term layout. Layout may now
        differ from one constraint to the other. Some unused suspension
        fields (continuation goal and generation number) are omitted.
        Further analysis can remove more fields.

        Default store constraints now each have
        their own global variable: a list of all the suspensions.
        Removal from this list is now O(1) thanks to setarg/1 and
        back pointers in the suspension terms. This can cause time
        time complexity improvements in solvers that always have 
        variable indexing on their constraints.

        Ground, non-indexed constraints are now removed from
        their global list store in O(1), as for the default store.

        Minor bug fixes in a number of places.

Mar 16, 2006

  * TS: Fixed subtle bug in ai_observation analysis,
        that caused goal sequences to only generate
        the optimistic default answer pattern, leading
        to invalid 'not observed' conclusions.
  * TS: Variable indexing/suspension analysis now ignores functor/3
        in guards. Could be extended to other built-ins
        that cause an error when arguments are not
        properly instantiated.

Mar 11, 2006
  
  * TS: Renamed global variable id to chr_id in chr_runtime.pl.

Mar 9, 2006
  * JS: Synchronization with experimental version:
        - minor optimizations, e.g. efficient lookups with statically known
          instantiated data 
        - new alternative syntax for passive declarations
        - new dense_int built-in type + underlying store
        - new type alias definitions, like in Mercury

Mar 4, 2006
  * BD: small changes in chr_compiler_options.pl and chr_translate.chr
        affecting only the SICStus port

Mar 3, 2006
  * BD: lots of changes related to porting to SICStus
  * TS: Now exception/3 hook is only used in SWI-Prolog

Mar 2, 2006

  * TS: Use exception/3 hook to catch undefined 
        global variables of chr_runtime.pl and CHR modules,
        for multi-threaded programs and saved states.

Feb 9, 2006

  * JW: Fix "make check" path issues.
  * TS: Removed all is_chr_file tests when loading file.

Feb 8, 2006

  * BD: chr_swi.pl: option(optimize --> :- chr_option(optimize
  * TS: Removed obsolete experimental optimization option.
  * TS: Correctly report variable pragmas!
  * TS: No constraints declared is no longer a special case.

Jan 19, 2006

  * BD: chr_swi.pl - use_module(hprolog added for SICStus port
  * TS: Removed operator declaration for '::'. No longer used.

Dec 23, 2005

  * TS: Removed chr_constraints declaration again, in favor
        of only the chr_constraint declaration and modified
        documentation accordingly.
  * TS: Modified documentation based on recommendations of Bart Demoen.
  * TS: Added chr_info/3 predicate to chr_compiler_errors, as suggested by
        Jon Sneyers. Now print banner on calling compiler.

Dec 13, 2005

  * TS: warnings are now written to user_error stream.

Dec 12, 2005

  * TS: option and constraints declarations are now deprecated. They
        are replaced by chr_option and chr_constraint(s).
  * TR: Made an interface for warnings and errors. Errors now implemented
        with exceptions.
  * TR: Revised documentation.

Dec 2, 2005
  * BD: chr_translate.chr, chr_translate_bootstrap2.chr
           mutables "abstracted"
  * BD: chr_translate_bootstrap1.chr
           atomic_concat - some duplicate code of it is in more than one file :-(
           create_get_mutable definitions if-deffed
           verbosity_on/0 for porting
        hprolog.pl
           definitions of init_store/2, get_store/2, update_store/2
           and of make_init_store_goal/make_get_store_goal/make_update_store_goal
           removed prolog_flag/3 (seemed  nowhere used)
        chr_translate_bootstrap2.chr
           make_init_store_goal/make_get_store_goal/make_update_store_goal introduced
           verbosity_on/0 for porting
        chr_translate_bootstrap.pl
           atom_concat -> atomic_concat
           verbosity_on/0 for porting
           conditional import van library(terms)
        chr_translate.chr
           make_init_store_goal etc. introduced
        create_get_mutable_ref wherever needed (chr_translate*)


Nov 30, 2005
  * BD: chr_runtime.pl:
           chr_init for SICStus
           included contents of chr_debug.pl
           removed show_store/1
           create_mutable changed into 'chr create_mutable'
           got rid of explicit inlining and did it by goal expansion
           inlining also of 'chr default_store'
  * BD: chr_swi.pl:
           removed :- use_module(chr(chr_debug))
           module header: version for SICStus
  * BD: chr_debug.pl: emptied
  * BD: chr_translate.chr:
           system specific declarations factored out in insert_declarations
           changed two atom_concat/3 into atomic_concat/3 (because arg 2 was sometimes an int)
  * BD: chr_compiler_utility.pl:
           put atomic_concat/3 there 
           adapted atom_concat_list/2 to use it
  * BD: chr_swi_bootstrap.pl:
           introduced chr_swi_bootstrap/2 for ease of porting
           exported also chr_compile/3
           porting code for get_time stuff/read_term/absolute_file_name
  * BD: builtins.pl, a_star.pl, clean_code.pl:
           some ifdefs


Nov 29, 2005
  * BD: hprolog.pl: removed strip_attributes/2 and restore_attributes/2

Nov 29, 2005
  * BD: chr_swi.pl: Removed code that took Handler for Module (in chr_expand(end_of_file)
                    Added :- chr_option(_,_) with same meaning as option(_,_)
                    is_chr_file: .chr is no longer a recognised suffix
                    added use_module(library(lists))
                    changed calls to source_location/2 into prolog_load_context/2
  * BD: chr_translate.chr: chr_translate/2: added end_of_file to translated program
                           adapted SICStus compatibility message
                           made :- chr_option(_,_) available
                           changed precedence of + - ? to 980 (these ops are
                                     probably not local enough to the module)

Nov 21, 2005

  * TS: Further synchronization with hProlog.

Nov 18, 2005

  * TS: Removed dead code in guard_entailment.chr
  * TS: Fixed performance bug: now lookup is indexed
        on maximal number of arguments.
  * TS: Removed some redundant intermediate predicates
        in chr_runtime.pl.
  * TS: It is now possible to disable the printing
        of the CHR constraint store per module,
        through the option toplevel_show_store on/off
  * TS: Synchronized with hProlog
  * TS: bug fix in functional dependency analysis

Nov 17, 2005

  * TS: Removed two dead predicates in chr_translate.chr
        and hooked up the late_storage_analysis
        that was being bypassed.
  * TS: Renamed global_term_ref_1 to default_store.
  * TS: Removed redundant predicate values_ht.
  * TS: Compiler no longer generates dead code for never stored constraints,
        i.e. attach/detach predicates.
        This reduces the generated .pl by about 700 lines.

Nov 10, 2005

  * TS: Two more bug fixes for constraints without
        active occurrences that trigger.

Nov 4, 2005

  * TS: Small optimization of code for constraints
        without any active occurrence.
  * TS: Fixed bug caused by previous bug fix:
        added only_ground_indexed_arguments/1 test
        to separate out that meaning from may_trigger/1.

Nov 3, 2005

  * TS: Removed strip_attributes code.
  * TS: Fixed bug that causes new constraints to be added on triggering.

Oct 25, 2005

  * TS: Two minor bug fixes.

Oct 19, 2005

  * TS: Fixed bug due to overly aggressive inlining of get_mutable_value.

Oct 18, 2005

  * JS: Compiled code is broken, if debug is off and optimize too.
        Debug off now entails optimize on.

  * TS: Some fixes of the documentation. Thanks to Bart Demoen
        and Thom Fruehwirth. 

Sep 2, 2005

  * TS: Synchronized with hProlog.

Aug 31, 2005

  * TS: Added missing operator declarations for prefix (?).

Aug 9, 2005

  * JW: import lists into chr_compiler_utility.pl

  * JW: make message hook for query(yes) detect CHR global variables.

  * JW: Exported pairlist_delete_eq/3 from pairlist and use this in
    chr_hashtable_store.pl

Aug 4, 2005

  * TS: Renamed pairlist:delete/3 to pairlist:pairlist_delete/3.
        Mike Elston.
Aug 1, 2005

  * TS: Extended more efficient ground matching code to
        removed simpagation occurrence code.

Jul 28, 2005

  * TS: New input verification: duplicate constraint declaration
        now reported as an error. Requested by Mike Elston.
  * TS: More efficient matching code for ground constraints
        when matching an argument of a partner constraint with
        a ground term
  * JS: Bug fix in guard simplification.

Jul 3, 2005

  * TS: Factored out option functionality into separate module.
  * TS: Factored out utility code into separate module.

Jun 29, 2005

  * TS: Changed chr_show_store/1 to use print/1 instead of write/1.

Jun 28, 2005

  * TS: Removed spurious and conflicting operator definitions
        for +, - and ? as mode declarations.

Jun 27, 2005

  * TS: Added find_chr_constraint/1 functionality.

Jun 8, 2005

  * TS: Improved compiler scalability: use nb_setval/2 to
        remember compiled code through backtracking over
        compilation process instead of assert/1.
  * TS: Removed spurious comma from file.

Jun 1, 2005

  * TS: Added option to disable toplevel constraint store printing.
  * TS: Slightly improved hash table constraint store implementation.
 
Apr 16, 2005

  * JW: Added patch from Jon Sneyers.

Mar 11, 2005

  * TS: Improved head reordering heuristic.
  * TS: Added support primitive for alternate built-in solver dependency.

Mar 4, 2005

  * TS: Fixed bug that causes wrong output in chr_show_store.

Feb 25, 2005

  * TS: Fixed several bugs in generation of debugable code.

Feb 19, 2005

  * JW: Cleanup integration in SWI-Prolog environment:
        - Extended SWI-Prolog library ordsets.  Renamed ord_delete/3 to
          ord_del_element/3 and ord_difference/3 to ord_subtract/3 for
          better compatibility.
        - Renamed module find to chr_find to avoid name conflict and declared
          preds as meta-predicate.
        - Re-inserted and exported strip_attributes/2 and
          restore_attributes/2 in hprolog.pl. Deleted hprolog: from
          chr_translate.chr.
        - Added dummy option declarations to bootstrap compiler.
        - Fixed path problems in makefile (-p chr=.) and install new
          components.
        - Fixed typo 'chr show_store' --> chr_show_store.

Feb 17, 2005

  * JS: Added guard entailment optimizations and
        new syntax for type and mode declarations.

Dec 15, 2004

  * TS: Use prolog:message/3 hook to automatically print
        contents of CHR constraint stores with query bindings
        on toplevel.

Dec  3, 2004

  * TS: Bugfix in code generation. Reported by Lyosha Ilyukhin.

Jul 28, 2004

  * TS: Updated hashtable stores. They now start small and expand.

Jul 19, 2004

  * JW: Removed chr_pp: module prefixes
  * JW: Updated Windows makefile.mak (more similar organisation, added check)

Jul 17, 2004

  * TS: Added chr_hashtable_store library.
  * TS: Added find library.
  * TS: Added builtins library.
  * TS: Added clean_code library.
  * TS: Added binomial_heap library.
  * TS: Added a_star library.
  * TS: Added new intermediate bootstrapping step
  * TS: Synchronized CHR compiler with most recent development version

  Summary of changes:

   "The new version of the compiler contains several new optimizations, both
    fully automatic, such as the antimonotny-based delay avoidance (see
    http://www.cs.kuleuven.be/publicaties/rapporten/cw/CW385.abs.html for
    the technical report), and enabled by mode declarations (see CHR
    documentation), such as hashtable-based constraint indexes."

Apr 9, 2004

  * JW: Added chr_messages.pl.  Make all debug messages use the print_message/2
    interface to enable future embedding.

Apr 7, 2004

  * JW: Added chr:debug_interact/3 hook.  Defined in chr_swi.pl to void
    showing constraints first as goal and then as CHR call.
  * JW: Added chr:debug_event/2 hook.  Defined in chr_swi.pl to make the
    CHR debugger honour a skip command from the Prolog tracer.

Apr 6, 2004

  * JW: Added b (break) to the CHR debugger.
  * TS: added chr_expandable/2 clause for pragma/2

Apr 5, 2004

  * JW: fixed reference to format_rule/2.
  * JW: Use select/3 rather than delete/3 in diff/2 in Tests/zebra.pl
  * TS: CHR translation now leaves CHR store empty

Apr 4, 2004

  * JW: added :- use_module(library(chr)) to all examples.
  * JW: mapped -O --> option(optimize, full).
  * JW: introduced file-search-path `chr' for clarity and to enable running
    make check from the local environment instead of the public installation.
  * JW: mapped prolog flag generate_debug_info --> option(debug, on)
  * JW: Replaced the chr -> pl step with term_expansion/2.
  * JW: Moved insert_declarations/2 to chr_swi.pl

Apr 2, 2004

  * JW: fixed Undefined procedure: chr_runtime:run_suspensions_loop_d/1
  * TS: Added <space> for creep and shortened debug line prefix to CHR:

Mar 29, 2004

  * JW: Use \+ \+ in chr_compile/3 to undo changes to the constraint
    pool.  Regression test suite using "make check" works again.

Mar 25, 2004

  * TS: Added skip and ancestor debug commands

Mar 24, 2004
G
  * TS: Added bootstrapping process for CHR compiler using CHR.
  * TS: CHR compiler now uses CHR.
  * TS: Fixed bug in compilation of multi-headed simpagation rules.
  * TS: Cleaned up compiler.
  * TS: Added analysis + optimization for never attached constraints.
  * TS: Exploit uniqueness (functional dependency) results to detect
    set semantics type simpagation rules where one rule can be passive
  * TS: Compiler generates 'chr debug_event'/1 calls
  * TS: Rudimentary support for debugging.
    option(debug,on) causes a trace of CHR events to be printed

Mar 15, 2004

  * JW: Fix operator handling.

Mar 3, 2004

  * JW: Integrated new version from Tom Schrijvers.