Angelic non-determinism in concurrent constraint programming

Radha Jagadeesan, Vijay A. Saraswat, Vasant Shanbhogue

Abstract

Concurrent constraint programming is a simple and powerful model of computation based on the notions of store-as-constraint and process as information transducer. In this paper we describe a (domain-theoretic) semantic foundation for CC languages with ask, tell, parallel composition, hiding, recursion and angelic non-determinism (``parallel backtracking''). This class of languages includes the CC/Herbrand language and a simpler reworking (cc-FD) of CHIP.

Generalizing previous work on determinate constraint programming we describe the semantics for such a language based on modelling a process as a set of constraints, with parallel composition (conjunction) given by set intersection and or-parallel search (disjunction) given by set union. This is achieved by viewing processes as continuous linear closure operators on the Smyth power-domain of the underlying constraint system. The model is shown to be fully abstract for the observation of finite approximants to the limits of fair execution sequences. We also give a model for the ``non-ground success set'' semantics---a model fully abstract for the observation of the minimal final stores in terminated execution sequences.

Postscript file