Set Based Languages

Appeared in Volume 6/4, November 1993

Keywords: sets.

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).

1. Deductive Database and LP Languages

LPS has a semantics for sets based on restricted universal quantifiers. Set structures are natural tools for expressing queries on nested relations. You can find information in:

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.

2. CLP Languages

CLP(Sigma) is an instance of the constraint logic programming scheme with efficient string handling. It deals specifically with regular sets, which are finite sets composed of finite strings:

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

Some Other Interesting Articles

On set unification

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