Programming with Sets

SETL allows one to manipulate two main kinds of data items, namely simple data items and composite data items. The intuitive distinction between these is that composite data items have elements, or components, which are themselves other (simple or composite) data items.

Sets in SETL are finite collections of arbitrary SETL values. These values, called the members (or elements) of the set, are themselves data items of any SETL type. To write a set denotation, we simply list the members of the set, with commas between successive members, within the set brackets “{” and “}”.

Execution of a SETL program proceeds sequentially, one statement being executed after the other. In the simplest case, the order of execution is simply the order in which the statements are written in the program.

A procedure in SETL is a sequence of computational steps which have been given a name and which, using one or more data items passed to it for processing, will compute and deliver a value. Most of the built-in SETL operators, for example max, which returns the maximum of two values x and y, and cos, which returns the cosine of a floating-point number x passed to it, are procedures in this sense. However, since no finite collection will ever exhaust the whole catalog of procedures that a programmer may want to use, it is important to have a way of defining, and then using, as many additional operations as are helpful.

The normal stages of a program’s life cycle are:

Backtracking or nondeterministic programming is an ingenious technique useful for solving a very common and important type of search problem. Such problems can be regarded as logical or combinatorial “mazes” which a program must explore in order to find a desired solution point. In favorable cases, one will be able to do this by devising an algorithm which proceeds in relatively direct fashion from an initial position to a solution, along a path involving little or no trial and error. However, some problems are too complex for such algorithms to be available, and it is for these problems that the method of backtracking is most useful. Characteristically, programs for solving these problems encounter situations in which a decision must be made as to which of several alternatives is to be explored next, but in which no clear grounds can be found for making one rather than another decision. A correct decision will lead on to a solution of the problem being explored, but an incorrect decision will wind up in a dead end, and the program will have to revert to the point at which it took its first wrong turning and try an alternative originally ignored. Finding paths through mazes and solving geometric and spatial puzzles like “instant insanity” are obvious examples of this kind of problem.

In the present chapter we round out our account of the control structures of SETL by describing certain useful facilities not covered in earlier chapters.

In this chapter, we cover various SETL capabilities that have been ignored in the preceding chapters. These include additional facilities for input/output, for sensing aspects of the environment in which a SETL program is running, and for passing strings or integers as parameters to SETL runs in a particularly convenient way. A full account of all the memory options and listing control commands which can be used to modify various aspects of SETL compilation and execution is given.

The level of a programming language is determined by the power of the semantic primitives which it provides. The operations provided by the ordinary low-level languages, e.g., languages of the FORTRAN type, all lie close to those elementary operations with a few dozen bits of input and output which computer hardware implements directly. Languages of somewhat higher level, e.g., PL/I, PASCAL, or Ada, supplement these primitives with more advanced pointer-oriented memory management mechanisms and also support recursion; nevertheless, even these languages stay close to operations which can be translated into efficient machine code in relatively obvious ways. SETL aims more radically than any of these languages at simplification of the programmer’s task; for this reason it supports use of abstract objects (sets and maps) whose best machine-level representation is not obvious. Of course, many possible representations for objects of this kind are known, but which representation is best will vary from program to program in subtle ways that depend on the specific operations that a program applies to the objects that it manipulates. If the most effective representation of a program’s data objects is not chosen, efficiency will suffer, and it is this efficiency barrier that has prevented rapid and widespread adoption of very high level languages like SETL.

In this, our last chapter, we illustrate the use of SETL by giving a variety of programs which exhibit its features and can serve as useful models of style. Some of the smaller programs present significant algorithms; the larger examples show how more substantial programming problems and applications can be addressed.