AI.ELLIE@MCC.COM (Ellie Huck) (04/16/87)
As announced earlier, please join the AI Program for the following
talk:
Concurrent Logic Programming Languages
Vijay A. Saraswat
CSD CMU
April 17 - 9:30am
MCC Auditorium
In this talk we present the language CP(!,|,&), which, together with
languages such as Concurrent Prolog and GHC explores the space of
concurrent logic programming (CLP) languages. Theoretically, CLP
languages offer a simple model of concurrent computation; practically,
they offer a powerful pointer-based, concurrent programming vehicle
that supports new paradigms of computation.
We illustrate the conceptual simplicity of CLP languages by presenting
a simple formal semantics for (Flat) CP(!,|,&), showing how to extend
the semantic techniques to GHC and Concurrent Prolog, and proving some
relationships between these languages. We show that there is a natural
definition of the relationship `IS-A-SUBSET-OF' between CLP languages,
and that:
GHC is-a-subset-of CP(!,|) is-a-subset-of (Safe) Concurrent Prolog
We also present the notion of CONSISTENT COMPLETENESS of LP languages
and argue that it serves to identify those languages which may
legitimately be called (Horn) LOGIC programming languages. We show:
CP(!,|,&), and hence GHC, is consistently complete.
Concurrent Prolog and (sequential) Prolog (with cut) are not.
On the practical side, of the various styles of programming supported
by CP, perhaps the most novel is that of CONCURRENT, CONTROLLABLE
constraint systems. We argue that purely declarative search
formalisms, whether they are based on dependency-directed backtracking
(as in Steele's thesis or the work of Bruynooghe et al) or bottom-up
breadth-first definite clause theorem provers (deKleer's ATMS) or
built-in general purpose heuristics (Laurier's ALICE) are unlikely to
be efficient enough to serve as the basis of a GENERAL PURPOSE
programming formalism which supports the notion of constraint-based
computation. CP allows the user to express domain-specific heuristics
and CONTROL the forward search process based on eager propagation of
constraints and early detection of determinacy and contradiction.
This control follows naturally from the alternate metaphor of viewing
constraints as processes that communicate by exchanging messages. The
language, in addition, provides naturally for the dynamic generation
and hierarchical specification of constraints, for concurrent
exploration of alternate solutions, for pruning and merging sub-spaces
and for expressing preferences over which portions of the search space
to explore next.
Friday - April 17
9:30am
MCC Auditorium
-------