Galliwasp Files

Galliwasp 1.3.4 -- Goal-Directed Answer Set Programming
=======================================================

Project page: <https://sourceforge.net/projects/galliwasp/>

By [Kyle Marple](kmarple1@hotmail.com).

Description
-----------

Galliwasp is a goal-directed answer set solving system. It accepts grounded
answer set programs in either normal logic or smodels format and finds produces
partial answer sets (if the program has an answer set) using a top-down
execution algorithm.

The software consists of two parts: the compiler and the interpreter. An ASP
grounder, such as lparse or gringo 4.0, is required but not included. The
compiler is written in Prolog, while the interpreter is written in standard C.
It has been successfully built under Linux and Mac OS X using gcc and Windows
using MinGW.

License
-------

Galliwasp is distributed under GNU Public License, see the file LICENSE for
details.

Package Contents
----------------

This README should be part of a distribution containing the following files and
directories.

* compiler/ -- Source code directory for the compiler
* interpreter/ -- Source code directory for the interpreter
* CHANGES -- Changelog
* config.h -- Configuration file used by interpreter
* COPYING -- GNU Public License
* INSTALL -- Dummy file, just directs the reader here
* Makefile.old -- The main Makefile for the project (old version)
* README -- This file
* Various files for running the 'configure' script and building the Makefile

Installation
------------

Building Galliwasp requires the GNU Compiler Collection (GCC), SWI Prolog, and
GNU make. It is also assumed that the commands 'gcc', 'swipl' and 'make', may
be used to invoke the three, respectively. Building has been tested using GCC
version 4.6.2, SWI-Prolog 64-bit version 6.3.3 and GNU make version 3.81.

If the build environment supports shell scripting (ex. POSIX OSes, Windows w/ 
MinGW), run './configure' to create the Makefile. If the configure script cannot
be run, rename 'Makefile.old' to 'Makefile' before continuing.

Finally, to build the compiler and interpreter, simply type 'make' from the
project directory. This will create two executables, 'gw', the interpreter, and
'gwc', the compiler, which can then be moved as needed.

Grounding
---------

To execute a program, it must first be grounded. Simple programs may be
grounded by hand, but a third-party grounder will be needed for more complex
programs. The compiler has been tested with text input from
[lparse](http://www.tcs.hut.fi/Software/smodels/) and smodels input from lparse
and [gringo 4.0-rc2](http://potassco.sourceforge.net). Note that gringo's text
output differs substantially from that of lparse and is not currently supported.

The choice of both grounder and input format can affect the output and runtime
performance of the interpreter. In particular, grounders may apply
transformation to a program before Galliwasp has access to it. For example, the
smodels input format separates the goals in a rule based on negation. When
compared to equivalent text format programs, this can result in answer sets
being produced in a different order, certain literals being omitted from answer
sets, and differing runtime performance. Additionally, if a grounder simplifies
the program by removing goals that will always succeed, this may lead to
incorrect results when using dynamic consistency checking (DCC).

Optionally, text format programs may contain a 'compute' statement, indicating
the number of solutions to compute and the query to execute if the interpreter
is run in automatic mode, e.g.

        compute N { q1,...,qn }.

where N is the number of solutions to compute and the list of literals in
braces forms the query.

Usage
-----

The compiler reads grounded problem instances from a given file and writes
them to either stdout or a file specified with the -o switch:

        gwc inputfile
        gwc inputfile -o output file

To see an overview of the compiler's command-line options, type

        gwc -?

Once a program has been compiled, the compiled version can be read by the
interpreter from stdin or a file, e.g.

        gwc inputfile | gw
        gw <compiledinput>

The interpreter can run in either automatic or interactive modes. Interactive
mode can only be used if the compiled program is read from a file rather than
stdin. To run in automatic mode, the program instance must contain a compute
statement, a non-empty NMR check, or at least one optimization statement. When
available, the interpreter will default to automatic mode. Otherwise, the
interpreter will run in interactive mode. The '-i' switch can be used to force
the interpreter to use interactive mode, ignoring the compute statement, if
present, e.g.

        gw -i <compiledinput>

For an overview of the available command-line options, type

        gw -h
or

        gw -?

When run in automatic mode, the interpreter will simply execute the query
given by the compute statement to find partial answer sets and print them,
stopping when the specified number of sets has been computed or no more sets
satisfying the query exist.

In interactive mode, the user will be presented with a prompt to enter a
query. For an overview of valid queries, enter 'help.' at the prompt. To exit
the interpreter when finished, enter 'exit.' at the prompt. After each answer
set has been printed, the user can enter '.' to accept the set and return to
the query prompt. Alternatively, the user can enter ';' to reject the set and
find the next one, if it exists. In this way,a user can find as many answer
sets as desired. Finally, entering 'h' at the prompt will give an overview of
both options.

Optimization Statements
-----------------------

As of version 1.2.1, optimization statements (minimization and maximization)
are supported. However, due to the implementation, the results may not always
be what one would expect. The handling of optimization statements is as follows.

* Optimization statements are executed first, before any goals in the query or
  NMR check.
* Statements are processed in the order they are encountered, first to last.
* Each statement yields the most optimal solution that the current partial
  answer set allows.

If an answer set exists for a program, the first answer set returned is
guaranteed to be optimal w.r.t. the first optimization statement in the program.
However, optimality w.r.t subsequent statements is not guaranteed. Furthermore,
if a solution count greater than 1 is specified, subsequent answer sets may be
less and less optimal.

Dynamic Consistency Checking (DCC)
----------------------------------

As of version 1.3.0, Galliwasp supports dynamic consistency checking (DCC).
Under normal execution, every NMR sub-check will be enabled by default, and thus
eventually executed unless failure can be determined before they are reached.
With DCC, NMR sub-checks are DISABLED by default and relevant sub-checks are
activated whenever a literal succeeds during execution.

DCC has two primary applications:

* When a query relates to only part of a larger program, DCC can result in
  improve performance and produce more relevant partial answer sets. For
  example, suppose a program is created by merging instances of the N-queens
  problem and the Schur numbers problem. Under normal execution, any answer set
  will contain solutions to both problems. However, with DCC enabled, either
  problem can be solved individually based on user-supplied queries.
* DCC can allow partial answer sets to be found for consistent subsets of an
  inconsistent program (no answer set exists). Note that this won't work in
  every case: if the call graph of a program is viewed as a set of connected
  components, DCC will only allow a query to succeed if the connected components
  accessed by the query are consistent. For example, if we take a program that
  has at least one answer set, and add the rule:
      p :- not p.
  where 'p' isn't present anywhere else in the program, no answer set will
  exist for the modified program. However, DCC will allow success for any query
  that doesn't contain 'p' or 'not p'.

For consistent programs, any partial answer set returned using DCC is guaranteed
to be a subset of some valid answer set, UNLESS EITHER OF THE FOLLOWING
CONDITIONS HOLD:

* The program was compiled with the simplification option enabled. This can be
  disabled by running Galliwasp's compiler with the '-ns' switch.
* The grounder performed simplification operations on the program before
  Galliwasp's compiler had access to it.

Additionally, the results produced by a query may not always be as expected.
If a compiled program that doesn't have a hard-coded query is run in automatic
mode, you may simply get an empty set. This is because no NMR sub-checks can be
relevant to an empty query. On the other hand, larger-than-expected sets may be
returned depending on the connected components of the program's call graph.