Name Last modified Size Description
![[PARENTDIR]](/icons/back.gif)
Parent Directory -
![[TXT]](/icons/text.gif)
README 1991-12-27 01:00 6.4K
![[DIR]](/icons/folder.gif)
angelic/ 2019-02-16 00:22 -
cc-abduction/ 2019-02-16 00:22 -
cc-atms/ 2019-02-16 00:22 -
ccal/ 2019-02-16 00:22 -
cccc/ 2019-02-16 00:22 -
ccfd/ 2019-02-16 00:22 -
ccp-book/ 2019-02-16 00:22 -
janus/ 2019-02-16 00:22 -
jlp-survey/ 2019-02-16 00:22 -
lambda-cc/ 2019-02-16 00:22 -
lcc/ 2019-02-16 00:22 -
ljanus/ 2019-02-16 00:22 -
mbc/ 2019-02-16 00:22 -
nl/ 2019-02-16 00:22 -
popl91/ 2019-02-16 00:22 -
psss/ 2019-02-16 00:22 -
rapper/ 2019-02-16 00:22 -
survey/ 2019-02-16 00:22 -
tcc/ 2019-02-16 00:22 -
true-cc/ 2019-02-16 00:22 -
vijay-macros.tex 1991-12-27 01:00 38K
![[ ]](/icons/compressed.gif)
winkach.zip 1996-03-07 01:00 0
This is the file transient/ccp/README on parcftp.xerox.com,
Internet address: 13.1.64.94.
Last updated: Sun Dec 22 06:50:13 1991
This directory contains papers on various aspects of concurrent
constraint programming.
cc-atms: ATMS-based constraint programming
ccfd: Constraint processing in cc(FD)
cccc: The category of constraint systems is Cartesian-closed.
psss: What is a constraint system?
Abstracts of these papers follow:
ATMS-based constraint programming
Vijay A. Saraswat
Johan de Kleer
Brian C. Williams
Xerox PARC
3333 Coyote Hill Road
Palo Alto, Ca 94304
October 1991
Abstract.
We are developing a broad and comprehensive theory of constraint
programming, subsuming the paradigms of functional and logic
programming [Sar89,SR90,SRP91,JSS91,SRvH91]. The
theory is based on a view of computation organized around the
notions of constraint systems as systems of *partial
information*, of *store-as-constraint* and
*process-as-information-transducer*, and emphasizes the use of
constraints for communication and control between concurrently
executing processes.
Such languages offer a very simple and abstract level for
specifying computations for combinatorial exploration. In prior
work [JSS91,SRvH91] we have shown how to smoothly integrate
Prolog-style backtracking and various local consistency
techniques within this framework. In this paper we develop the
integration of this framework with the alternate approach to
combinatorial exploration predominant in AI, *truth-maintenance
systems* (TMSs) [Doy79], [McAll90], [deKle86]. In particular, we
give a generic mechanism for enriching *any* constraint system B
with the notion of assumptions to obtain another constraint
system A(B). To implement A(B), ATMS-implementation techniques
are integrated with the constraint-solver for B. All the usual
cc combinators --- such as ask, tell, conjunction (parallel
composition) and hiding, all closed under recursion --- are
immediately available on top of A(B), providing a simple and
powerful constraint language. In addition, several new
combinators can now be defined which take advantage of the extra
structure of assumptions built into the constraint system. As
before, each of these new combinators can be given a very simple
mathematical characterization as closure operators over the
underlying constraint system. They enable a simple and elegant
expression of various previously developed programming notions on
top of ATMSs, such as (various kinds of) consumers [deKle86a].
-----------------------------------------
Constraint Processing in cc(FD)
Pascal Van Hentenryck, Brown University
Vijay Saraswat, Xerox PARC
Yves Deville, Universit\'e Catholique de Louvain
November 1991
Abstract.
Constraint logic programming languages such as CHIP [vHent89],
[Dinc88] have demonstrated the practicality of declarative
languages supporting consistency techniques and nondeterminism.
Nevertheless they suffer from the *black-box effect*: the
programmer must work with a monolithic, unmodifiable,
inextensible constraint-solver.
This problem can be overcome within the logically and
computationally richer concurrent constraint (cc) programming
paradigm [Sar89]. We show that some basic constraint-operations
currently hardwired into constraint-solvers can be abstracted and
made available as combinators in the programming language. This
allows complex constraint-solvers to be decomposed into logically
clean and efficiently implementable cc programs over a much
simpler constraint system. In particular, we show that the CHIP
constraint-solver can be simply programmed in cc(FD), a cc
language with an extremely simple built-in constraint solver for
finite domains.
-----------------------------------------
The category of constraints sytems is Cartesian-closed
Vijay Saraswat
December 1991
Abstract. The development of constraint programming has brought
to the forefront the notion of *constraint systems* as certain
first-order systems of partial information [JL87], [Sar89],
[SRP91]. Connections between such systems and domain theory have
seemed apparent for some time [Sar89], but have not yet been
explored in depth. The need for such a study becomes
unavoidable, however, when one considers the development of
*higher-order* constraint programming languages. To give
semantics to such languages, it becomes necessary to find
mathematical structures in which recursive ``domain equations''
involving constraint systems can be solved.
In this paper we give a general definition of constraint systems
utilizing Gentzen-style sequents. Constraint systems can be
regarded as enriching the propositional Scott information systems
with minimal first-order structure: the notion of variables,
existential quantification and substitution. Reflecting the
computational reality that an agent ``has access'' to only
finitely many free variables, we take as morphisms approximable
maps that are *generic* in all but finitely many variables. We
show that the resulting structure forms a category (called
ConstSys). Furthermore, the structure of Scott information
systems lifts smoothly to the first-order setting --- we show
that the category is cartesian-closed, and other usual functors
over Scott information systems (lifting, sums, Smyth
power-domain) are also definable and recursive domain equations
involving these functors can be solved. This makes it possible to
use this category to define the semantics of higher-order,
concurrent constraint programming languages.
-----------------------------------------
What is a Constraint System?
Prakash Panangaden, McGill University
Vijay Saraswat, Xerox PARC
P. J. Scott, University of Ottawa
R. A. G. Seely, McGill University and John Abbott College
Abstract.
We study a relationship between logic and computation via
concurrent constraint programming. In previous papers it has
been shown how a simple language for asynchronous concurrent
processes can be interpreted in terms of constraints. In the
present paper we show that the programming interpretation via
closure operators is intimately related to the logic of the
constraints. More precisely we show how the usual hyperdoctrinal
description of first order logic can be functorially related to
another hyperdoctrine built out of closure operators. The
logical connectives map onto constructions on closure operators
that turn out to model programming constructs, specifically
conjunction becomes parallel composition and existential
quantification becomes hiding of local variables.
-----------------------------------------