Up Next

7.1  Overview

Propia is the name for the implementation of Generalised Propagation in ECLiPSe.

Generalised propagation is not restricted to integer domains, but can be applied to any goal the user cares to specify even if the variables don't have domains.

Effectively the system looks ahead to determine if an approximation to the possible answers has a non-trivial generalization. It is non-trivial if it enables any variables in the goal to become further instantiated, thus reducing search.

The background and motivation for Generalised Propagation is given in references [15, 14, 16]. This section focusses on how to use it. Further examples of the use of Propia are distributed with ECLiPSein the doc/examples/propia/ directory . A simple demonstration of Propia in action on Lewis Carroll's Zebra problem can be run by compiling zebra.pl and issuing the query lib(ic), zebra(Houses,ic) . An slightly more complex application of Propia to crossword generation can be run by compiling crossword.

Using Propia it is easy to take a standard Prolog program and, with minimal syntactic change, to turn it into a constraint logic program. Any goal Goal in the Prolog program, can be transformed into a constraint by annotating it thus Goal infers most. The resulting constraint admits just the same answers as the original goal, but its behaviour is quite different. Instead of evaluating the goal by non-deterministically selecting a clause in its definition and evaluating the clause body, Propia evaluates the resulting constraint by extracting information from it deterministically. Propia extracts as much information as possible from the constraints before selecting an ordinary Prolog goal and evaluating it. In this way Propia reduces the number of choices that need to be explored and thus makes programs more efficient.

Up Next