🚀 go-pugleaf

From: fromherz@ifi.unizh.ch (Markus P.J. Fromherz)
To: mod-ki@unido.informatik.uni-dortmund.de
Date: Wed, 29 May 1991 13:24:39 +0200
Subject: <mod-ki 0719> Prolog Forum 5.6.91
Keywords: Vortraege

mod-ki message 0719
************************************************************************
                            Prolog Forum

Wednesday, June 5, 1991, 12.30 at room 21-G-74 (below the mensa)
Institut fuer Informatik, University of Zuerich-Irchel

                            F. Kuechenhoff
                            ECRC Muenchen

             CONSTRAINT PROPAGATION IN LOGIC PROGRAMMING

The declarative semantics of logic programming enables to write complex
programs while preserving important properties as clarity, modifiability
and extensibility. This ease for the programmer implies a
correspondingly greater demand on the evaluation engine. If it is not
powerful enough program evaluation can be very inefficient.

Tasks where this shortcoming is particularly evident are constraint
satisfaction problems. No general algorithm exists for such problems
since they are usually NP complete. So solving them means relying
heavily on intelligent search / constraint manipulation techniques.

A variety of mechanisms have been developed that prune the search space
by propagation: given a state of the search, constraints can be used to
reduce the search space before a failure occurs. But powerful
propagation also introduces considerable runtime costs.

Predicates can be written as demons to express propagation, avoiding
these costs. They delay till their arguments are sufficiently
instantiated to match one of the demon clauses. Then they are executed,
performing the propagation. This technique has been applied successfully
with CHIP e.g. for hardware verification. As they have a complex
operational semantics, hand coding of demons is hard and error prone.

We are therefore developing a compiler that generates from an arbitrary
finite predicate the set of demons that perform the same propagation at
runtime as a given dynamic propagation mechanism (in our case
generalized propagation as defined in PROPIA). We thus ensure
correctness and push analysis costs for propagation to compile time
instead of incurring them repeatedly at runtime.

The method is orthogonal to the propagation mechanism chosen, i.e. the
language on which propagation is based. It is further independent of how
the constraint is defined, i.e. an intentional logic program is
sufficient.

The mechanism is based on a breadth first search on the space of
possible instances of the goal. Whenever propagation is possible, a
demon is generated.

The scheme allows the programmer to concentrate entirely on the
declarative semantics of the constraint program, while obtaining a
sophisticated data driven computation schema. Further it can be
naturally combined with heuristic based labeling procedures that
initiate search if that is necessary.

For more information:
   Markus Fromherz                   Tel.:   +41-1-257 4313 / 4311
   Institut fuer Informatik          E-Mail: fromherz@ifi.unizh.ch
   Universitaet Zuerich-Irchel
   Winterthurerstrasse 190
   CH-8057 Zuerich
************************************************************************