PROLOG SETS-AS-INTERVAL PREDICATES Jocelyn Ireson-Paine Shelved on the 21st of December 1987 This file defines predicates for manipulating sets of integers, represented as lists of disjoint intervals. This is a compact way of representing large sets, provided that they contain few gaps between intervals. Here are two examples of the representation: Set Representation { -32768 .. 32767 } [ -32768--32767 ] { 1,3,4,5,9,10,11,12,15,16,100,101,102} [ 1--1, 3--5, 9--12, 15--16, 100--102 ] The predicates in this entry include ones for forming the union, intersection, and difference of such sets, and for various operations on single intervals. For efficiency, I keep sets in a canonical form; one in which the intervals are disjoint, and are in ascending order, and form a minimal covering (i.e. there is no other representation of a set, using fewer intervals). There is a predicate for converting a list of arbitrary unordered intervals into a canonical form. I have found the predicates useful when writing programs for syntax-directed translation of character data. For example, some tag field on a line may specify that the line is a record of type R1 if the field lies in the set C1 of characters, or a record of type R2 if the field lies in the set C2 of characters, and so on. Using these predicates, I can check for ambiguous specifications by testing whether C1 and C2 overlap; and I can generate quick tests for whether some character is in C1 or C2 by knowing that the set are represented by as few intervals as possible. SIZE : 26 kilobytes. CHECKED ON EDINBURGH-COMPATIBLE (POPLOG) PROLOG : yes. PORTABILITY : Easy, no known problems. INTERNAL DOCUMENTATION : Comments for each main predicate; the properties of the representation; summary of proofs of correctness.