Programming with sets. An introduction to SETL. (English) Zbl 0604.68001

Texts and Monographs in Computer Science. New York etc.: Springer-Verlag. XV, 493 p. DM 108.00 (1986).
SETL (settheoretic language) is a very high level language that allows to concisely express programs very close to their formal specifications. It was designed at New York University’s Courant Institute of Mathematical Sciences by Jacob T. Schwartz and his group (of which R. Dewar and E. Schonberg are prominent members); design and implementation started in the early Seventies, at present, fairly stable implementations on a number of machines are available. The language belongs to the ALGOL family, it has the usual primitive data types (integer, real, Boolean, character, string, atom). In contrast to other members of that family, it offers objects of set theory as compound data structures, viz. sets, relations/maps, and tuples. These objects do not need to be homogeneous (so one may have e.g. a set which has another set, a map, a real and a string as its elements). Since they are represented explicitely in storage, they have to be finite. On the side of control structures, SETL offers the usual structures (conditional statements, case statements, various versions of loop constructs), and it has in addition quantification and backtracking. The language is weakly typed (so one does not have to declare variables at all, and one may change the type of a variable, as one goes); in addition a Data Representation Sublanguage is offered allowing the programmer to give hints to the compiler as far as the actual representation of objects in storage is concerned. This makes the language strongly typed, and is intended to improve efficiency. As far as Software Engineering is concerned, the language supports programming in the large (so it offers modules, libraries, which in some implementations may be compiled separately, it offers directories, and of course procedures), and because it is a wide spectrum language, it is somewhat accessible to program transformations. Hence a programmer may ideally start with a very high level version of her program, and then subsequently transform it into a sequence of lower level versions, using correctness preserving transformations. In this way, the production of correct code is facilitated. It should be added that the execution of SETL programs is somewhat slow; this is partly due to the fact that the language is weakly typed, and operators are heavily overloaded (so resolution of overloading is postponed to runtime), and to the fact that SETL has value semantics, but implements it in pointer semantics (which has the effect that at runtime many unnecessary copy operations of shared objects are done). As of now, the language is implemented on CDC, IBM/370 (under CMS as well as MVS), the VAX family (VMS and UNIX), the Apollo, and SUN workstations. The language has been used successfully to produce prototypes; the most prominent prototype was the Ada/Ed interpreter, the first certified Ada translator.
The book under review introduces the language at quite a leisurely pace (the cover suggests that it may be used by undergraduates with minimal programming knowledge). It first gives a brief overview of SETL, and introduces in a rather informal way some programming concepts. Actually, it gives here, too, some advice on how to appreciate the first error messages a SETL beginner will get from the SETL system. It then introduces first simple data structures (the usual primitive types), the compound data types like sets, tuples, maps and relations; this is complemented by the discussion of the elementary operators each data type has (union and intersection for sets, length for tuples, etc.). Chapter 4 is devoted to control structures, this chapter illustrates the concepts introduced so far with a rather nice example (a Turtle language interpreter). Procedures are introduced next, together with a rather thorough discussion of global vs. local variables, the scope of variables, and the like. The chapter discusses, too, procedures the user defines, and user-defined operators. The latter sections in that chapter give a couple of fairly interesting examples which rather convincingly display the power of this language. Chapter 6 is somewhat mixed in approach and level: it introduces methods and styles for program development, testing and debugging. Here one finds fairly well established methods discussed in the context of the language (like a checklist of common bugs, general remarks on program testing), but one finds, too, some very interesting and useful remarks on program transformations, and on program verification (this reviewer would have appreciated a longer section on program transformations, taking in particular the work of Bob Paige into account). Chapter 7 goes back to control structures and introduces backtracking as a very powerful way of implementing search problems. The aspect of programming in the large is focussed on in Chapter 8 (introducing libraries, modules, and directories to structure large programs), and the sometimes peculiar problem of communicating with the environment, i.e. I/O, is discussed in Chapter 9. The last but one Chapter 10 introduces and discusses the Data Representation Sublanguage mentioned above, and gives a little bit of insight into some details of the implementation, at least as far as the representation of data structures is concerned. The last chapter shows the language in action, nine sample implementations of problems in SETL are introduced and discussed, among them the Stable Assignment Problem, and the implementation of a macro processor (which is modelled after SETL’s own). This chapter demonstrates the power of the language, and it becomes evident here (at last here, I should say: it really shows rather early) that SETL is a language very suitable for rapid prototyping. It might be added that programmers familiar with mathematics, and rudimentary set theory in particular, will find themselves more at ease reading SETL prototypes, than, say prototypes written in the PROLOG language.
It should be mentioned that the language description is sometimes incomplete (as measured against the implementation on the SUN, for example), and sometimes inaccurate in details; features vital to programming in the large (as separate compilation) do not seem to work as indicated for all implementations. But these are minor points. It is useful to observe, however, that SETL is becoming a useful and important language in particulr for software design and rapid prototyping (as witnessed in Europe by the ESPRIT project SETL Experimentation and Design). This book introduces SETL to novices to the language, or to persons interesting in rapid prototyping, and it does it very well indeed. Thus it is wholeheartedly recommended to anybody interested or working in this field.
Reviewer: E.Doberkat


68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
68Nxx Theory of software