Galliwasp: Goal-Directed Answer Set Programming
Galliwasp is an answer set programming system utilizing a goal-directed execution method. The current version is Galliwasp 1.3.3, released on September 21, 2013.
- Galliwasp 1.3.3: September 21, 2013
- Compiler: Fixed a potential bug. The largest integer with an associated string may be greater than the length of the symbol table, due to strings being removed by the grounder for various reasons.
- Compiler: Fixed a bug in the smodels DCG that would result in compilation failing when a program contained extended ASP literals in the body of a rule.
- Compiler: Fixed a bug that resulted in extended ASP rules not being detected when more than one such rule was present in a text-formatted input program.
- Compiler: Significant improvements to internal documentation.
- Galliwasp 1.3.2: September 1, 2013
- Revisions to DCC indexing:
- Relevant NMR sub-checks for a literal are now those in the same connected component of a modified call graph. The modified call graph is formed using only those literals which can be reached, directly or indirectly, by at least one NMR sub-check. Previously, only NMR sub-checks which could reach a literal were considered relevant, which could allow DCC queries to succeed even when an inconsistency was present in the same connected component.
- New format for DCC index in compiled programs. The index should now be much smaller.
- Compiler: Fixed a bug where the compiler would drop to a prompt from the underlying Prolog interpreter if no input file was specified. It will now print an error message an usage information, then terminate.
- Revisions to DCC indexing:
- Galliwasp 1.3.1: August 24, 2013
- NOTE: This is primarily a bug fix release. Version 1.3.0 contained major bugs related to dynamic consistency checking (aka DCC or dynamic NMR check construction).
- Fixed major bugs related to dynamic consistency checking (DCC).
- Extended the compiled program format to include an index of NMR sub-checks to activate when a literal succeeds. Previously, relevant sub-checks may not have been activated by a literal they called indirectly.
- Interpreter: Added warning messages when using DCC with selected options may lead to incorrect results. This includes when a program is compiled with simplification enabled or when the input program uses the smodels input format. If the grounder doesn't perform any simplification, you can ignore the latter.
- Updated README to include information on DCC.
- The values of certain compiler options are now embedded in the compiled program. This allows the interpreter to print warning messages if a combination of options may lead to incorrect results.
- Interpreter: Added a much shorter help message when an error in the command-line arguments is encountered. Previously, this would cause the full help output to be printed.
- Compiler: Added configurable, default settings in 'config.pl'.
- Compiler: Added command-line switches to enable and disable options that previously defaulted to enabled and could only be disabled.
- Compiler: Added the ability to disable simplification of a program using facts.
- Compiler: Greatly improved the help output produced by the '-h', '-?' and '--help' command-line switches.
- Compiler: Added an additional index to the compiled output for use with dynamic consistency checking.
- Galliwasp 1.3.0: August 13, 2013
- Interpreter: Added dynamic NMR check construction, controlled by the -d/-nd switches (disabled by default). If enabled, only NMR sub-checks relevant to literals in the partial answer set will be executed. This can improve performance in consistent programs as well as allow partial answer sets to be found for consistent subsets of inconsistent programs. Note that if a program is inconsistent, this option may produce partial answer sets that aren't valid under the ASP semantics (no answer set exists for an inconsistent program). However, any partial answer set produced by a consistent program will still be valid under ASP.
- Interpreter: Changed the way NMR check reordering is handled. There are now two options related to reordering: NMR check reordering and query reordering, controlled by the -r/-nr and -q/-nq switches, respectively. If both options are enabled (the default), reordering behavior is identical to that of previous releases: only NMR check goals are reordered, but they can be placed ahead of query goals to ensure faster execution. If NMR check reordering is enabled but query reordering is disabled, NMR check goals will only be moved ahead of other NMR check goals, but never ahead of goals in the query proper. This can improve performance in cases where the query might force backtracking over reordered NMR check goals.
- Interpreter: Split simplification of NMR sub-checks and reordering. Reordering will always enable simplification, but now simplification can be enabled even when reordering is disabled.
- Interpreter: Improved performance in cases where simplification will lead to one or more NMR sub-checks becoming unsatisfiable.
- Interpreter: Fixed a bug that could result in crashes and/or incorrect results when all rules for a literal were disabled.
- Interpreter: Internal changes for compatibility and type safety.
- Galliwasp 1.2.1: July 26, 2013
- IMPORTANT NOTE: As of this release, the smodels input format, as produced by gringo 4.0, is fully supported. This also means that ASP-CORE-2 is supported via gringo 4.0, excluding queries, which gringo doesn't currently allow. However, see the "Grounding" section of the README for information on how the use of this format as well as the choice of grounder can affect both performance and the partial answer sets produced.
- Added support for optimization statements (minimize and maximize). This applies to both the text format produced by lparse and the smodels input format as produced by either lparse or gringo 4.0.
- Interpreter: Added checking of current answer set against the previous one to eliminate sequentially produced duplicates. If the printed literals in an answer set will match those of the previous answer set, the answer set will be skipped, and won't be counted towards to number of solutions found. Note that only printed literals are used in comparison: only literals with strings will be checked, and negated literals will only be checked when the option to print them is enabled.
- Interpreter: Stacks can now be resized at runtime, starting at a given size and expanding as needed up to a specified maximum size or until not more memory is available. The default maximums are set to allow for unlimited expansion. This should avoid the need to recompile the interpreter when stack space errors are encountered. Command-line switches are available to modify the initial and maximum sizes.
- Interpreter: Added #defines for various default option values to config.h. These can be used to change the default interpreter behavior without having to use command-line switches.
- Interpreter: Greatly improved the help output produced by the '-h', '-?' and '--help' command-line switches.
- Interpreter: Fixed a bug in interactive mode that could lead to incorrect output on all queries but the first.
- Galliwasp 1.2.0: June 20, 2013
- Compiler: Added support for classical negation.
- Compiler: Added rudimentary support for smodels input as produced by Gringo 4. The use of Gringo will also allow programs with aggregates, as Gringo removes aggregates from its smodels output. Minimization rules are currently unsupported. Support for this format is still experimental, therefore its use is not recommended. Full support should be available in an upcoming release.
- Compiler: Added verbose and very verbose progress messages that can be enabled using the -v and -vv switches, respectively.
- Compiler: Fixed preservation of program ordering to restore operational semantics. When factorization is disabled, the relative ordering of rules and goals in the input program will be preserved.
- Compiler: Fixed a bug in OLON rule detection could lead to very long search times. Programs that were affected should compile much faster now.
- Compiler: Changes to the way unrecognized characters in an input file are handled. They should now be tokenized properly, even if the DCG will later reject them.
- Compiler: Changes to the way command-line options are stored internally, to allow for easier access without passing a list of options around.
- Compiler: Fixed a bug rule expansion that could lead to non-termination or incorrect results.
- Compiler: Various performance improvements.
- Interpreter: Fixed bug in which goal assumption of query could lead to incorrect answers being returned.
- Interpreter: Added option to specify number of answer sets from command line with the -s switch. Syntax is -s[#]. If a number greater than 0 is given, ex. -s3, this is used as the number of answer sets to compute. If 0 or no number is given, ex. -s or -s0, all answer sets are computed.
- Interpreter: Changed several internal data structures to use dynamic rather than static allocation. This removes the need to recompile the interpreter when running programs which exceeded the defined size limitations.
- Galliwasp 1.1.0: February 16, 2013
- IMPORTANT NOTE: The changes in this release constitute a significant improvement over the previous version in most respects. However, due to changes in the program representation, some programs which previously terminated quickly may now take an unreasonably long time. Some instances of the Schur numbers problem are known to be affected. This isn't a bug. Many ASP programs are written in a manner unsuited for goal-directed execution. While galliwasp is designed to accommodate these programs whenever possible, even minor changes in goal and clause ordering can lead to extreme changes in runtime performance.
- Compiler: Added common factor elimination. Goals present in multiple clauses with the same head will be factored out, reducing unnecessary repetition during execution. Note that this can cause partial answer sets to be unexpectedly small (albeit still correct) if fact priming is disabled by the interpreter.
- Compiler: Expanded simplification of program using known facts.
- Compiler: Added support for extended ASP syntax (weight and constraint literals, disjunctive heads, choice rules, etc.).
- Compiler: Added experimental support for abduction. Requires success on positive loops to be enabled in the interpreter (run the interpreter with the '-p' switch).
- Compiler: Added initial support for automatic source code documentation using pldoc.
- Interpreter: Added assumption of goals when a clause is selected. Goals called by a clause are added to the CHS with a special flag, allowing them to be used for failure but not for success. That is, if 'not p' is assumed, a call to 'p' will fail, but another call to 'not p' will not coinductively succeed. This both ensures that the clause does not directly violate the CHS and allows immediate failure and backtracking if later clauses will contradict assumed goals. Goal assumption can be disabled by running the interpreter with the -nq switch.
- Interpreter: Various performance improvements.
- NMR call indexing moved from interpreter to compiler.
- Significant improvements to source code readability and modularity.
- Default executable names have been shortened. The compiler is now 'gwc' (previously 'gwaspc') and the interpreter is now 'gw' (previously 'gwasp').
- Galliwasp 1.0.4: June 22, 2012
- Added detailed error messages for scanning and parsing. Debugging invalid programs should now be much easier.
- Galliwasp 1.0.3: June 1, 2012
- Major improvements to compiler speed for programs with a lot of headless rules.
- Galliwasp 1.0.2: May 27, 2012
- Fixed a bug where literals could succeed by calling themselves with no intervening negation, if backtracking occurred after they had previously succeeded.
- Fixed a bug where a valid recursive call could fail when it should have succeeded.
- Galliwasp 1.0.1: May 7, 2012
- Fixed a bug which allowed all clauses of an NMR sub-check to be disabled without failure occurring, which could result in invalid answer sets being returned.
- Galliwasp 1.0.0: March 23, 2012
- Initial release.
To build and run Galliwasp's compiler, SWI-Prolog must be installed. Additionally, the Lparse grounder is recommended for preparing input programs for the compiler. These programs are not included in the Galliwasp distribution, and may be obtained from their respective sites. For additional requirements, see the file README.TXT included in the Galliwasp distribution.
While we strive to work out any problems prior to release, Galliwasp is under continuous development, so bugs may turn up from time to time. If you encounter cases where Galliwasp crashes or returns an incorrect answer set, please let us know by sending an email to firstname.lastname@example.org with "Galliwasp Bug Report" in the subject. To help us fix the problem as quickly as possible, please include any error messages encountered, and in the case of incorrect answer sets being returned, the problem or instance used, the output received, and the output expected.
- Kyle Marple, Ajay Bansal, Richard Min, and Gopal Gupta. Goal-Directed Execution of Answer Set Programs. In Proceedings of the 14th symposium on Principles and Practice of Declarative Programming, (PPDP '12), pages 35-44. New York, NY, USA, 2012. ACM.
- Kyle Marple and Gopal Gupta. Galliwasp: A Goal-Directed Answer Set Solver. In Logic-Based Program Synthesis and Transformation, volume 7844 of Lecture Notes in Computer Science, pages 122-136. Springer Berlin Heidelberg, 2013.