Henning Christiansen
Computer Science Dept.
Roskilde University, Denmark
© Henning Christiansen 2005-2008, 2016.
Version X.0.2, released 2008, and SWI.0.3, released 2016. Last modification 16 aug 2016.
HYPROLOG is available in versions for different Prolog platforms,
indicated by different 'X' in the version code; this document covers all versions.
SWI.0.3 is adapted to run under SWI Prolog version 7, but is otherwise identical to SWI.0.2.
This document explains how to use the HYPROLOG system. HYPROLOG is an extension to Prolog and Constraint Handling Rules (CHR) with abduction and assumptions. The system is basically implemented by a compiler that translates the HYPROLOG syntax in a rather direct way into Prolog and CHR; HYPROLOG queries are then executed directly by Prolog and CHR.
HYPROLOG is fully integrated with the underlying Prolog+CHR environment, which means that all built-ins can be used with abductive and assumptions.
HYPROLOG has been thought out by Henning Christiansen and Veronica Dahl and implemented by Henning Christiansen.
To run HYPROLOG, you need to a version of Prolog with CHR installed on your computer, corresponding the the version of HYPROLOG that you have downloaded.
The get the full benefit of the HYPROLOG system and this User's Guide, you need to be familiar with Prolog and, preferably and to some extent, with CHR as CHR is used for integrity constraint.
Links: HYPROLOG homepage (with downloads), CHR homepage
HYPROLOG is implemented directly on top of Prolog and CHR and can use the full power of these languages, including grammar notation, built-in predicates, and all available constraint solvers and other libraries; be aware that the syntax and available facilities supplied by different versions of Prolog+CHR may differ slightly.
Notice especially that Prolog's grammar notation (DCGs) can be used transparently with HYPROLOG.
HYPROLOG differs from Prolog+CHR by having its own declarations of abducibles and predicates for assumptions and a few other additional facilities, but you'll be able to run any existing program of Prolog or CHR under HYPROLOG.
The efficiency of HYPROLOG, especially when compared with other systems for abductive logic programming, comes from the fact the programs are executed directly by the underlying Prolog and CHR systems, and additional mechanisms for abduction and assumptions are only activated when specific HYPROLOG facilities are used (such as a call to an abducible predicate).
The implementation of specific HYPROLOG facilities is done in CHR, and CHR can be used as a convenient and powerful language for defining integrity constraints. HYPROLOG declarations are compiled into a few lines of CHR code, and in principle HYPROLOG just provides convenient syntactic sugar over programming techniques that can be applied manually.
For background on HYPROLOG and references to related work, see the following paper.
Henning Christiansen and Veronica Dahl,
HYPROLOG: A New Logic Programming
Language with Assumptions and Abduction, In:
Proc. International Conference on Logic Programming, ICLP'05,
M. Gabbrielli and G. Gupta (Eds.), pp. 159-173, 2005.
Lecture Notes in Computer Science 3668.
See pdf.
You may start the HYPROLOG system as follows from within the relevant Prolog version as follows; notice that the file you consult will compile a bunch of other files using Prologs optimizing compiler (and most likely issue a series of messages and warnings).
?- [hyprolog]. |
Having done this, you can compile your own HYPROLOG programs in the following way; here it is assumed that your program file is named myProgram.
?- hyprolog(myProgram). |
You do not need to load the CHR library, HYPROLOG does this for you. Notice that the hyprolog command applies Prolog's optimizing compiler after doing its own compilation process.
In fact, you can run any Prolog or CHR program file through hyprolog and it will execute as usual. The following source file, which does not implement a very interesting program, illustrates some of these declarations; these and other facilities are described in detail below.
abducibles a/1, b/2. compaction a/1. assumptions s/1. timeless_assumptions t/2. a(X), b(X,Y), a_(Y) ==> +s(X), =*t(X,Y). test(A,B,C):- p(a), -s(A), =-t(B,C). p(X):- a(X), q(X,b). q(X,Y):- a_(Y), b(X,Y). |
First line introduces two abducible predicates with indication on number of arguments. The abducibles can be called as any other predicate in Prolog rules and be used in the integrity constraints as indicated; integrity constraints are just another name for CHR rules with abducibles in the head.
When an abducible, say a/1, is declared, two abducible predicates are created, a/1 and a_/1 where the latter represents explicit negation of a/1. Explicit negation means that you cannot have a(X) and a_(X) at the same time. However, it is a weak sort of negation as not having a(X) does not indicate that you have a_(X).
The next declaration, compaction a/1, indicates that the system will try to produce small abductive answers by, each time a new abducible is called, try to unify it with an existing abducible (and trying different alternatives on backtracking). In most other abductive systems, this is the default, but in HYPROLOG it is an option; there are good reasons for this choice, both from the point of view of efficiency and methodological reasons (discussed below). Notice that compaction for a/1 does not imply the same thing for a_/1, so if that is what you want, you need to do declare it for both.
The next two declarations introduce an assumption and a timeless assumption. Declaring s/1 as assumption makes it possible to write linear assumption +s(a), intuitionistic assumption *s(b), as well as expectation -s(X). We explain the semantics in detail below but briefly, +s(a) introduces an assumption that can be used once in the following computation by means of expectation -s(X). So +s(a), ..., -s(X) may bind X to a, thus consuming the particular assumption, (and alternative assumptions may be used instead under backtracking). Intuitionistic assumptions *s(b) works in the same way, except that they are not consumed but can be used an indefinite number times.
Timeless assumptions and expectations are similar, written with an additional prefix "=", except that expectations can be given in the computation before the matching assumption. It is possible to refer to assumptions and expectations (including timeless) in the head of integrity constraints, however, the semantics may sometimes become a bit complicated.
The following is a test run of the sample program,
| ?- test(A,B,C). A = a, B = a, C = b, a(a), a_(b), b(a,b), '=*t'(a,b) ? |
The answer is a set of bindings to variables in the query together with abducibles and different assumptions (and expectations) that have not been consumed.
Notice that the assumption predicates in some Prolog systems are printed in with single quotes as shown; an explanation follows below.
Notice that these declarations should be written as indicated and not be preceeded by any Prolog-like ":-".
| Declaration | Purpose | Remarks |
| abducibles specs. |
The indicated predicates can be used as abducibles as well as
similar predicates for explicit negation. For example,
for a/2 is also created an abducible
predicate a_/2.
See also the section on abduction in HYPROLOG below. |
It is not recommended to declare abducibles whose names end with an underline, as this in rare cases may cause confusion among the rules generated internally by HYPROLOG. |
| compaction specs. |
Indicates that the mentioned abducible predicates are
made subject of compaction,
i.e., when an abducible for such a predicate is created
during execution, the system will attempt to unify it with existing
abducibles, trying all possibilities under backtracking, and as the last alternative,
not unifying with any of those.
Declaring a/2 to be compaction does not indicate that
a_/2 also is compaction; this must be declated separately if wanted.
See also the section on abduction in HYPROLOG below. |
Should be used following an abducibles declaration and refer to it's abducible predicates (and negated counterparts). |
| assumptions specs. |
Makes assumptions and expectations available for the given name.
If you declare, say, c/2 as an assumption, you can use
the syntax +c(term,term) for linear assumptions,
*c(term,term) for the intuitionistic ones,
and -c(term,term) for expectations.
See the section on assumptions in HYPROLOG below for more explanation. |
Declaring, say, c/2 as assumption does not indicate any special meaning for c/2 used as predicate without preceedings operator as indicated. |
| timeless_assumptions specs. | Syntax and description similar to the above,
except that it generates timeless versions;
indicated as above but using operators
=+, =*, and =-.
See the section on assumptions in HYPROLOG below for more explanation. | Similar to the above. |
| abducible specs. compactions specs. assumption specs. timeless_assumptions specs. |
Identical to the above, just in alternative plural/singular forms. Any form can be used independently of the specs. | Included to fit inconsistent usages in published papers on HYPROLOG. |
Nothing prevents you from declaring CHR constraints in the usual way and mix them with HYPROLOG's facilities. Check the relevant Prolog manual's section on CHR for the detailed syntax.
Notice also that a HYPROLOG program may have several abducibles declarations; you just need to be sure to declare the abducibles before they are used in any rule. The similar thing goes for assumptions and timeless_assumptions.
The following HYPROLOG declarations serve very specific purposes, mostly relevant for HYPROLOG implementors and for optimizations. In practice you will not need them, except show_internal_rules which may give the curious HYPROLOG programmer some insight in what goes on behind the surface when HYPROLOG declarations are compiled.
| Declaration | Effect | Comment |
| show_internal_rules. | When a source file is compiled, this command will print out on the screen those additional rules of CHR and Prolog that are introduced in order to implement HYPROLOG's behaviour. | Useful for those who want to understand how HYPROLOG works,
and (hopefully only rarely) for tracing strange program behaviour.
With some care, it may be possible to copy the rules that are shown into a new source file and run it separately from the HYPROLOG system. |
| allow_duplicate_abducibles. allow_duplicate_abducibles specs. |
Switches off HYPROLOG's default removal of duplicate abducibles for all or specified abducibles. | Normally, the removal of an abducible identical to one already in the store
may suppress a lot of useless rule applications. However, in some applications this check may slow down execution a bit; this may be the case if the application by nature produces many abducibles but only very few actual duplicates. NB: This command has no effect for abducibles that are specified to be compacting, as compaction automatically gets rid of duplicates with a very small cost. |
| no_explicit_negation. no_explicit_negation specs. |
Avoid creation of a negative versions of all or specified abducibles., thus, also the corresponding rules that implement explicit negation. | If your program does not make use of explicit negation,
and you want to avoid checking for possible negation violation
each time anything happens to the abducibles, you may use this option. NB: Makes only a small difference and is only relevant for producing benchmarks. |
| no_star. no_plus. |
To optimize the execution of assumptions and timeless assumption by avoiding compiling code for linear, resp., intuitionistic assumptions. |
If both are used, only no_plus is in action (in fact,
there is interesting in using both. NB: Not implemented in the version for SICStus 3. |
| reset_star_plus. | Cancels the effect of no_star or no_plus. |
Useful if you want to the optimizations made by
no_star or no_plus to go only for some of the
assumptions or timeless assumption in your source program.
NB: Not implemented in the version for SICStus 3. |
Henning Christiansen and Veronica Dahl,
HYPROLOG: A New Logic Programming
Language with Assumptions and Abduction, In:
Proc. International Conference on Logic Programming, ICLP'05,
M. Gabbrielli and G. Gupta (Eds.), pp. 159-173, 2005.
Lecture Notes in Computer Science 3668.
See pdf.
In order to use abduction in HYPROLOG, you need to declare your abducible predicates as described in section 3.
Assumptions are very useful for linguistic applications, for example combined with the Definite Clause Grammar notation. Linear assumptions can also be used for modelling resource sceduling in a straightforward way; see the HYPROLOG sample files for examples.
Each assumption symbol needs to be declared as described in section 3 in order to make the indicated operators available. Consider as an example the relevant of assumptions h/1. or timeless_assumptions h/1. which make the following facilities available for use in the subsequence program text and from the command line.
| +h(a) | Assert linear assumption h(a) for
available for subsequent computations. Linear means "can be used once". |
| *h(a) | Assert intuitionistic assumption for
subsequent computations Intuitionistic means "can be used any number of times". |
| -h(X) | So-called expectation: consume/apply assumption. |
| =+h(a), =*h(X), =-h(X) | As above but computational order of assertion and application/consumption can be arbitrary. |
In many examples, the argument to operators with a star or plus are ground but that need not be the case. Operators including "=" are called timeless, the others sequential.
We say that sequential expectation -h(t) is satisfied if there is a matching assumption +h(s) or -h(s) in the relevant so that the unification s=t succeeds. A sequential expectation will try all possible assumptions on backtracking, and it fails when no expectation is left for which the indicated unification suceeds.
The timeless versions works in an analogously way except that expectations do not fail if no assumption exists at the time of call, as one may show up later in the execution history.
The following predicate may be useful for programs in which all timeless expectations must be satisfied at the end.
| expectations_satisfied. | This predicate fails if there are unsatisfied assumptions in the execution state. | Only timeless expectations are checked as sequential ones that are not satisfied anyhow leads to failure. |
There is no interaction between sequential and timeless assumption/expectations. It is not recommended but you may in principle declare the same name for sequential and timeless assumptions and the system will keep them separate. So for example =+h(a) can never satisfy an expectation -h(X).
Notice that HYPROLOG treats a call such as =+h(a) as a call to a predicate '=+h'; this is done for efficiency only and is implemented by having the HYPROLOG compiler to map =+h(a) into '=+h'(a); calls from the command can avoid the quotes as =+ is defined as a predicate (with prefix syntax) that maps its argument into the relevant predicate call.
HYPROLOG includes a useful where clause which can be used together with any Prolog or CHR rule. This facility provides a way to take out complicated subexpressions and replace them by variables. See the following example.
p(X,Y):- q(A,Z), B, C
where A = ugly(st(r,u,c(t,u,r(e)))),
B = =+something(X,A),
C = (append(X,Y,Z), write(Z)).
|
The meaning is that any occurrence in the rule of A, B, and C is replaced by the indicated term. The transformation is purely syntactical and executed when HYPROLOG reads the rule from a source file.
The rule above is identical to the following, which is more difficult to read.
p(X,Y):- q(ugly(st(r,u,c(t,u,r(e)))),Z), =+something(X,ugly(st(r,u,c(t,u,r(e))))), append(X,Y,Z), write(Z). |
The where clause is implementing by executing the equations as unifications at the time of loading, and if unification fails, you will receive an error message.
For assumptions, you should be aware that a source file is preprocessed
so that each declared assumption and expectation has its own
predicate. For example, if h/2 is declared as timeless
assumption, the string =*h(a,X) is read as one
a call with function symbol '=*h'.
This is implemented by a finite state automaton which makes
a preprocessing of the source file,
looking for such occurrences of
assumption and expectation operators followed by names
that has been declared as (respectively!) assumptions or timeless assumptions;
in such cases, single quotes are added as indicated.
The finite state automaton is made in such a way that
it respects comments, string constants and quoted atoms.
When a file, say myFile is loaded by
hyprolog(myFile), an auxiliary file myFileIntermediate
which include the additional quotes is created.
No spaces are allowed between the assumption/expectation operator and the name, i.e., =* h(a,X) is wrong. Quoted atoms are not allowed to be declared as assumptions.
In some cases, the HYPROLOG compiler avoids checking errors that are likely found by CHR or Prolog.
If you experience weird errors when compiling a HYPROLOG source file you may try to use the declaration show_internal_rules. in the source file. This will print out the on the screen, the additional CHR and Prolog rules that are created by the compiler and normally hidden for the user.
NB: In case you consult or compile a HYPROLOG source file using Prolog's standard consult (square brackets) or compile facilities, the system may in some cases accept you file and sometimes not. However, it will not execute right!, remember to load the file with hyprolog(myFile).