We show that a simple concurrent pruning mechanism over standard SLD derivation trees, called constructive negation by pruning, provides a complete operational semantics for normal constraint logic programs (CLP) w.r.t. Fitting-Kunen's 3-valued logic semantics. The principle of concurrent pruning is the only extra machinery needed to handle negation, in particular there is no need for considering complex subgoals with explicit quanti ers outside the constraint part. The main result of the paper is the de nition of a xpoint semantics for normal CLP programs which is fully abstract for the observation of computed answer constraints. This allows to generalize the s-semantics approach to normal CLP programs, and provides a xpoint characterization of Kunen's semantics. The de nition is based on a non-ground continuous nitary version of Fitting's operator. We relate also these results to an important aspect of CLP programming practice: optimization. We investigate various forms of goal optimization within CLP languages, and provide a declarative semantics for them via a translation to normal CLP programs. We show that constructive negation by pruning specializes for these classes of programs to a more e cient concurrent branch and bound like procedure.
Fages proposes a simple concurrent pruning mechanism over standard SLD derivation trees for constructive negation in constraint logic programs REF .
Constructive Negation by Pruning
J. Log. Program.
Mathematics Computer Science