Programming with { Sets }

Welcome to PROGRAMMING WITH {SETS}
Sets are a wellestablished 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 highlevel 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 productionefficiency programming, but as a vehicle for rapid experimentation with algorithms and program design'' where efficiency is not a primary requirement. Only relatively few realworld 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 logicbased 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. Generalpurpose set constructs and basic operations on sets are inserted into some general logicbased 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., typechecking 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 subclasses of them. Setoriented programming means thinking and designing programs with set data abstractions in mind, trying to really exploit all the potentialities offered by set constructs. Nondeterminism 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. SpringerVerlag, 1986.


WebMaster: complog@cs.nmsu.edu Last Modified: July 20th, 1998 