Programming

with

{ Sets }

Sign our Guestbook

Welcome to

PROGRAMMING WITH {SETS}

Sets are a well-established conceptual tool in mathematics.

In the practice of computer science, on the other hand, the use of sets as a data structure is not so common as it might be. Actually, it is widely agreed that the availability of set data abstractions, and of powerful operations upon them, would represent a valuable feature of high-level programming languages and specification languages. According to [1], it would

``[...] improve programmer speed and productivity significantly, and also enhance program clarity and readability''

The price for the added expressive power is a certain loss of efficiency. Certainly, this is one of the reasons sets are relatively uncommon as data objects. And this is also the reason for which such kind of languages [1]

``[...] should be regarded, not as a tool for production-efficiency programming, but as a vehicle for rapid experimentation with algorithms and program design''

where efficiency is not a primary requirement.

Only relatively few real-world languages provide sets as primitive objects. Among them, the specification language Z, the procedural language SETL, and the functional language MIRANDA. More recently, a number of proposals have been put forward in the area of the integration between logic-based programming paradigms and set theory. Attention to this area has come first from the field of deductive databases.

Recently, a number of papers have addressed the problem also in a wider setting. General-purpose set constructs and basic operations on sets are inserted into some general logic-based framework: pure logic programming languages, equational logic languages, and Constraint Logic Programming (CLP) languages. Also, set constraints on their own are extensively studied as a natural formalism for many problems that arise in program analysis (e.g., type-checking or optimization).

A number of satisfiability checking procedures exist for general set constraints (actually, conjunctions of formulae of the form

where X and Y are set expressions constructed using the set union, intersection and complement operators) and for smaller sub-classes of them.

Set-oriented programming means thinking and designing programs with set data abstractions in mind, trying to really exploit all the potentialities offered by set constructs. Non-determinism in set unification, set constraints, intensional set formers, are all features that potentially allow one to write programs in a more declarative fashion, and definitively to obtain simpler and more readable programs.

The development of (programming) languages with sets raises several interesting theoretical as well as practical problems.

Aim of these pages is to provide a reference point to researchers and practitioners interested in computational uses of set theory.

[1] J.T. Schwartz, R.B.K. Dewar, E. Dubinsky, and E. Schonberg. Programming with sets, an introduction to SETL. Springer-Verlag, 1986.

WebMaster: complog@cs.nmsu.edu