![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
Appeared in Volume 6/4, November 1993
carmen@ecrc.de
Carmen Gervet
24th May 1993 (Revised 23rd Sept. 1993)
mandayrv@ucunix.san.uc.edu writes:
I am doing a survey of high level languages based on sets. The only information
I have currently is on the language SETL. I would appreciate any pointers to
articles, magazines, books, etc. that have more information on this issue.
There was a workshop on Logic Programming with sets at ICLP'93 in Budapest, which looked at the various approaches for introducing sets into LP and CLP.
A lot of work has been carried out in the last 3-4 years, and two main new directions have developed since SETL.
The first direction concerns the introduction of sets into the deductive database oriented languages LPS and LDL1, and into the LP language {log}. The second concerns the introduction of set constraints into Constraint Logic Programming languages (CLP(Sigma), CLPS, Conjunto and a new version of {log}). These have been developed to solve or prototype combinatorial problems (coming from operations research, and other domains).
G. Kuper, Logic Programming with Sets, pp.44-64, 1990, Journal of Computer and System Sciences, Vol 41, 1, Academic Press, New York and London,
You should also read about LDL1, the successor of LDL with sets and negation. LDL1 has efficient intensional set definitions and computation via a grouping operator:
C. Beeri and S. Naqvi and R. Ramakrishnan and O. Shmueli and S. Tsur, Sets and Negation in a Logic Database Language (LDL1), Proc. of the Sixth Annual ACM Symp. on Principles of Database Systems, 1987, pp.21-37,
Another very well defined language is {log}:
A. Dovier and E. G. Omodeo and E. Pontelli and G. Rossi, {log}: A Logic Programming Language with Finite Sets, Proc. of the 8th Int. Conf. on LP (ICLP), 1991, pp.111-124, Paris, June
A. Dovier and E. G. Omodeo and E. Pontelli and G. Rossi, Embedding Finite Sets in a Logic Programming Language, Proc. of the 3rd Workshop, ELP'92, LNAI - Extensions of LP, 1992, Springer-Verlag, pp.150-167, Bologna, Italy, Feb.
Clifford Walinsky, CLP(Sigma): Constraint LP with Regular Sets, pp.181-190, ICLP, 1989
CLPS is being used to develop techniques for constraints satisfiability over Homogeneous Hereditarily Finite Sets (HHFS) i.e. sets of finite depth, multisets and sequences. These structures are built from atomic elements:
B. Legeard and E. Legros, Short Overview of the CLPS System, 3rd Int. Symp. on Programming Language Implementation and LP, PLILP'91, Passau, Germany, Aug. 1991
M. Hibti and H. Lombardi and B. Legeard, Deciding in HFS-Theory via Linear Integer Programming with Application to Set Unification, 4th Int. Conf. on LP and Automated Reasoning, LPAR'93, To appear in LNCS, Springer-Verlag 1993
{log} has recently been become a CLP language. The details will appear in the paper :
'Embedding Extensional Finite Sets in CLP' in ILPS'93, Vancouver.
Relations are sets of tuples, so when extending a LP or a CLP language with set
structures, it seems natural to introduce relations. Some work is currently
being done in this area at ECRC. The approach is to consider sets and relations
as constrained objects, and to add the intensional set definition via
constraint statements. A set variables is constrained to range over a finite
set domain e.g. S::<{2,1}..{5,3,4,2,1}>
.
Constraint satisfaction is
performed by propagating set constraints and thus new set domains are computed.
The language developed to examine these ideas is called Conjunto, and is
described in:
C. Gervet Sets and Binary Relation Variables viewed as Constrained Objects Workshop on Logic Programming with Sets in conjunction with ICLP'93, June 21-24, Budapest,Hungary
M. Livesey and J. Siekmann, Unification of Sets and Multisets, 1978, Internal report, Universitat Karlsruhe
W. Buettner, Unification in Datastructure Multisets, Journal of Automated Reasoning, 2:75-88,1986.
K.J. Perry et al., The Complexity of Logic Programming with Sets, Computer Science, 1986.
On implementation
John E. McEneaney, Implementing Set Theory in Prolog, Univ. of Georgia, 1989, Research Report AI-1989-07, Georgia USA, July
J. Goubault, Implementing Functional Languages with Fast Equality, Sets and Maps: an exercise in Hash Consing. technical Report RAD/DMA/92019, Bull BSP France,July 1992.
On programmation and expressive power
B. Jayaraman and D.A. Plaisted, Programming with Equations, Subsets, and Relations, LP, Proc. of the North American Conf., 1989, Lusk and Overbeek (eds.), pp.1051-1068
N. Heintze and J. Jaffar, A Decision Procedure for a Class of Set Constraints, Computer Science, Feb 14, 1991.
Alexander Aiken and Edward L. Wimmers, Solving Systems of Set Constraints, IEEE, 1992
A. P. Stolboushkin, On the Computing Power of Programs with Sets, Int. Journal of Foundations of Computer Science, 1992, Vol 3, No 2, pp.161-180
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |