Being a mathematician, I've always dreamt of a programming language that would make use of the powerful formalism of Set Theory. Two years ago, I started looking for an open-source software tool to use in an elementary Set Theory class. I had a hard time finding any on the Net, but in the end I found the object of my dreams: a structured, general-purpose, open-source programming language that implements as closely as possible the Set Theory formal language. The language is called SETL (Set Language). As I found out later, it has been around for quite a long time, 33 years to date. For some reason, though, it does not seem to be in widespread use, at least according to the small number of related resources available on the Net.

The aim of this article is not to offer a thorough discussion of SETL internals or a comparisons with other languages. Rather it intends to show the strong points of SETL by using elementary examples to convince you of how useful it can be in the right setting. For example, SETL appears to be one of the most suitable environments in which to make Set Theory calculations on a PC. As most problems may be formulated using the sets formalism, SETL is a good choice for all those times when compactness and elegance are more relevant than speed or memory consumption.

SETL was introduced in 1970 by Professor J. Schwartz, a distinguished mathematician who made major contributions in the field of parallel computations and many other areas of Pure and Applied Mathematics and Computer Science. SETL's syntax reproduces quite closely the one used in the language of Set Theory, because Schwartz observed that such highly powerful language was suited perfectly to constitute the skeleton of a compact and easy-to-read programming language. The programming language itself primarily was designed to study compiler optimization problems. Nevertheless, its approach works perfectly for problems where Set Theory formalism is used, because its syntax is pretty much the same as what mathematicians use on the blackboard.

SETL is an interpreted language with a syntax that is loosely C-like and in many cases similar to Perl. For example, variables types are determined automatically by their last assignment and every statement is terminated by a semicolon. Variable names are case-insensitive and the assignment operator is :=, the standard mathematical notation for defining an object, rather than =, which is used as the logical test for equality. Comments begin with $ or --.

From my point of view, SETL's nicest feature is it looks like a version of Perl with a mathematical flavour. Although Perl has an elementary structure that works as sets work, namely the keys of an associative array, no operations for union and intersection of sets are provided. Thus, working with sets in that environment would not look as natural as it does in SETL.

The scalar data types used in SETL are the standard self-explanatory kinds: BOOLEAN, INTEGER, REAL and STRING. No limitation is set on the size or range of these variables except for the obvious hardware limitation. Moreover, a data type of OM is assigned to any never-declared variable:

a:=1;
b:=3.4;
c:='hello world';
print(a,b,c,d);
print(type(a),type(b),type(c),type(d));

1 3.4 hello world *
INTEGER REAL STRING OM

Operations on these variables are the same as in Perl except for the div operator, which returns the integer part of the quotient between two integers, and the + operator, which acts on strings as concatenation:

a:=3;
b:=2;
print(a+b,a-b,a*b,a div b, a mod b,a/b,a**b);
a:='hello';
b:='world';
print(a+' '+b);

5 1 6 1 1 1.5 9
hello world

Moreover, all the usual logical tests are available in SETL and have the same syntax as they do in Perl and many other languages, except for the not equal operator, /=:

a:=5;
b:=7;
print(a>b,a>=b,a=b,a<=b,a<b,a/=b);

#F #F #F #T #T #T

The data type that gives SETL its name is the SET data type, used to represent the usual (finite) sets of Set Theory. The syntax is exactly the same as what is found in mathematical literature, except for the final semicolon that tells the interpreter the instruction is over:

$ a set defined by listing its elements
$ (extensive definition)
A:={2,4,7.3,'Hello World!'};
print(type(A),A);

SET {2 4 7.3 'Hello World!'}

Even though SETL is case-insensitive, we use upper-cased names for variables representing sets and lower-cased letters for the others, simply to make the code easier to read. A set whose brackets encloses nothing is the empty set, and sets also can contain other sets:

A:={};               $ the empty set
B:={A,{6,'abc'},3};  $ a random set
C:={1..5};           $ all integers between 1 and 5
print(A,B,C);

{} {3 {} {6 abc}} {1 2 3 4 5}

Let me recall that a set is an unordered collection of elements that can be scalar data types or other sets. Therefore, the print instruction is not guaranteed to print them in the same order in which they were inserted. The same happens with hash keys in Perl.

All elementary natural operations on sets are defined in SETL:

A:={1,3,5,7};
B:={3,6,8};
print(A,B);
print('union = ',A+B);
print('intersection = ',A*B);
print('difference = ',A-B);
print('A plus 0 = ',A with 0);
print('A  minus 5',A less 5);

{1 3 5 7} {3 6 8}
union =  {1 3 5 6 7 8}
intersection =  {3}
difference =  {1 5 7}
A plus 0 =  {0 1 3 5 7}
A  minus 5 {1 3 7}

Analogously, the two main logical tests involving sets are implemented:

a:=3;
B:={1,3,8,10};
C:={3,10};
print('does a belong to B? ',a in B, a notin B);
print('is B a subset of C? ',B subset C);  
print('is C a subset of B? ',B incs C);

does or does not a belong to B?  #T #F
is B a subset of C?  #F
is C a subset of B?  #T

Often in mathematics sets are defined as subsets of bigger sets whose elements satisfy some particular property or properties. For example, the set of even integers E may be defined as:

Here the symbol | stands for “such that” and precedes a logical statement; therefore, only those elements for whom that value is true are included in the subset. As promised, this formalism is reproduced faithfully in SETL through an expression called Set Formers:

Z:={-10..10};  $ no infinite sets in SETL!
E:={n: n in Z | n mod 2 = 0};
print(E);

{0 2 4 6 8 10 -2 -4 -6 -8 -10}

In SETL it is impossible to deal with infinite sets but, apart from that, the notation is essentially identical to the standard one used in mathematics.

The implementation of sets as elementary SETL data types would not be so effective without the quantifiers exists and forall that, for example, allow subsets to be built in a compact way because each of them implicitly involves a loop. Needless to say, quantifiers syntax is the one usually used in mathematics:

A:={3,5,7};
print( exists x in A | x mod 2 = 0 );
print( forall x in A | x >= 2 );

#F
#T

For example, quantifiers can be used to define sets in a compact way:

N:={1..50};
P:={x: x in N | forall y in {2..x-1} | x mod y /=0};
print(P);

{1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47}

The P set defined above in one line contains all integers smaller than 50 that cannot be divided exactly by any other integer number except for 1 and itself, namely all prime numbers smaller than 50.

The Cartesian Product of sets, of course, could not be left out from SETL. Given two or more sets, their Cartesian Product is the collection of all ordered couples (or n-tuples) of elements from the two or more sets. In formulas this is expressed as:

In SETL, the notation for the elements of the Cartesian Product—implemented through the data type array in other languages, such as C or Perl—uses squared rather than the round parentheses usually used in mathematics. SETL uses the round parenthesis to access single elements of a tuple, so here it is exactly the opposite of Perl:

t:=[2,8,3.4,'hello world',[2,3],{4,5}];
print(t(4));

hello world

As can be seen in the example above, the first index is 1 rather than 0. Tuples can contain not only scalar data types but also sets or other tuples, making it an extremely flexible tool.

New elements are added simply by defining the right value of the right array element or by using the with instruction to append a value as the last element of the array. Operators fromb and frome are used to get rid of a single element, from the beginning and the end of an array, respectively. Finally, the operator + is used to append the second tuple to the first, and the operator # returns the index of the last element of the tuple.

a:=[3,9,4.2];
a:= a with 'abc';
print(a,#a);
a(8):=1;
print(a,#a);
b frome a;
print(a,#a);

[3 9 4.2 abc]
[3 9 4.2 abc * * * 1]
[3 9 4.2 abc]

The simple fact of being ordered makes tuples and sets quite different objects. For example, the sum (union) of two equal sets produces the same set, while the sum (concatenation) of two equal tuples produces a longer tuple, that is a tuple belonging to a different Cartesian Product:

print({1}+{1});
print([1]+[1]);

{1}
[1 1]

The whole Cartesian Product of two sets can be generated easily with a simple Set Former expression:

A:={1,2};
B:={'a','b','c'};
C:={[x,y]:x in A, y in B};
print(C);

{[1 a] [1 b] [1 c] [2 a] [2 b] [2 c]}

Last but not least, SETL comes with natural support for maps.

In mathematics it is called map when between two sets (A and B), any rule f that associates to each element a of A and element b of B. The element b also is called value of the map f at the point a; in short: b = f(a). Any such map f can be described unequivocally by a subset F of the Cartesian product A×B if we agree to put in F all pairs (a,b) where b=f(a).

SETL automatically enables special calls for every subset of a Cartesian Product of two sets, which are sets containing only pairs. It allows you to access such a set with the same notation used in mathematics as in the following example:

sqroot:={[1,1],[4,2],[9,3],[16,4]};
print(sqroot(9));

3

Each map f from A to B has a domain, namely the set of all elements of A on which it is defined (like the keys of a Perl hash), and a co-domain, namely the set of all of the elements of B it is able to reach (the values of a Perl hash). Because these sets are crucial for working with maps, SETL implements two calls, domain and range, to return those two sets.

sqroot:={[1,1],[4,2],[9,3],[16,4]};
print(domain(sqroot));
print(range(sqroot));

{1 4 9 16}
{1 2 3 4}

Finally, SETL is aware of the concept of multivalued map, those maps f from A to B that associate to some element a more than one element of B. In this case the function must be called using the set brackets:

f:={[1,1],[1,2],[1,3],[16,4]}; print(f{1}); print(f(1));

{1 2 3} * 

The conditional syntax is simple:

a:=1;
b:=2;
if a >= b 
  then
    print('a is not smaller than b!');
  else
    print('a is smaller than b!');
end;

More complicated logical expressions can be obtained using the usual logical operator and (conjunction), or (disjunction) and not (negation):

A:={1,2};
B:={1,2,3};
if A subset B and not B subset A
  then
     print('A is a proper subset of B');
end;

Loops syntax over sets or tuples is similar to the Perl foreach instruction:

A:={1,3,6};
(for x in A)
  print(x);
end;

1
3
6

Adjacent nested loops often can be compacted into a single loop, as in the following example:

A := {1,2,3};
P := { {} };
(for x in A, Y in P)
  P with:= Y with x;
end;
print(P);

{{} {1} {2} {3} {1 2} {1 3} {2 3} {1 2 3}}

The with:= operator above is a shortcut analogous to the C += syntax, so P with:= Y with x stands for P := P with (Y with x). The example above generates the power set of a given set $A$, namely the set of all its subsets, looping on all elements of $A$ (external loop) and all sets contained in $P$ (internal loop). Initially P contains only the empty set. At the first loop in $A$ it will contain {} and, say, {1}; at the second it will contain {},{1},{2},{1,2} and at the third step it will contain all possible subsets of $A$.

Let me show two more examples of the effectiveness of SETL, binary relations and Pythagorean triples.

Binary relations among elements of the same set (for example, the equality relation) are important in mathematics. These relations, like maps, may be represented unequivocally by subsets of a Cartesian Product, because we can associate to any relation the set $R$ of pairs [a1,a2] that contains all pairs in relation to each other—all pairs [a,a] in case of the equality relation. Three properties of relations are extremely important: reflexivity, every pair [a,a] belongs to $R$; symmetry, if [a1,a2] belongs to $R$ so does [a2,a1]; and transitivity, if [a1,a2] and [a2,a3] belong to $R$ then so does [a1,a3].

Of course, equality satisfies all of them but other relations do not; for example, the relation “is bigger than” is neither reflexive nor symmetric. In SETL a one-line logical test can be written for each of these properties. The following code, for example, is testing the transitive property:

A:={1..4};
AxA:={[x,y]:x in A,y in A};
$ the R below is not transitive
R:={[x,y]:[x,y] in AxA | y=1 or x=1 };
$ the R below is transitive
$R:={[x,y]:[x,y] in AxA | y mod x = 0 };
print('R =',R);

if exists [x,y] in R, z in A | [y,z] in R and [x,z] notin R then
  print('This relation is not transitive');
  print([x,y],[y,z],[x,z]);
  print([x,y] in R,[y,z] in R,[x,z] in R);
end if;

R = {[1 1] [1 2] [1 3] [1 4] [2 1] [3 1] [4 1]}
This relation is not transitive
[2 1] [1 2] [2 2]
#T #T #F

Triples of integers [a,b,c] ordered in increasing order and such that they are the length of the sides of a right triangle are called Pythagorean triples; the smallest of such triangles is the one with legs of length 3, 4 and hypotenuse of length 5. Once a triple is known, infinitely many new ones can be generated simply by multiplying such a triple by any integer bigger than 1. We get a new triple [6,8,10] by multiplying the smallest triple by 2; a triple whose numbers have no common factors is called primitive. It is possible to generate in SETL with a single line all primitive triples whose bigger leg is smaller than some fixed number:

l:={[a, b, c]: b in {1..30}, a in {1..b-1} |
  (exists c in {2..a + b} | (a *a + b*b = c*c) and
   not exists d in {2..b - 1} |
   ((b mod d) = 0 and (a mod d) = 0))
   };
print(l);

{[3 4 5] [5 12 13] [7 24 25] [8 15 17] [20 21 29]}

SETL is a powerful language, especially good for those who like the Set Theory language. Its many features exceed the scope of this article, but hopefully the few examples shown here have encouraged people to read more about it.

Last but not least, I want to thank David Bacon for providing many documents and examples and Toto Paxia for his help with the SETL packages.