An Invitation to SETL

Mathematicians, rejoice. The SETL programming language, almost as old as C, is closely modeled on set theory and looks like a version of Perl with a mathematical flavour.
Conditionals and Loops

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$.

Further Examples

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]}

Conclusion

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.

Roberto De Leo (roberto.deleo@ca.infn.it) has been using Linux happily for the past ten years. He's currently doing research at the Physics Department of the University of Cagliari and spending too much time with his MoviX Project.

______________________

Comments

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

SETL-like sources

Edwood Ocasio's picture

This open source project is based in SETL and it includes sources. Read the download instructions:

http://isetlw.muc.edu/isetlw/about.htm

Of course, if someone has an URL to the original SETL's sources ... please, share.

Roberto De Leo wrotes: | ...

SU Yong's picture

Roberto De Leo wrotes:
| ...
| open-source programming language that implements as closely as
~~~~~~~~~~~
| possible the Set Theory formal language. The language is called SETL
| (Set Language).
| ...
Where can one download the source of some implementation of SETL/SETL2?
Is it only available via email according to the comments from ftp://cs.nyu.edu/pub/languages/setl2/README.SOURCES ?
And how about its license?

Thx.

SU Yong wrote: Where can one

Mike Anderson's picture

SU Yong wrote:
Where can one download the source of some implementation of SETL/SETL2?
Is it only available via email according to the comments from ftp://cs.nyu.edu/pub/languages/setl2/README.SOURCES ?
And how about its license?

When i sent an email to address provided in the referenced file the email bounced. Has anyone else located the sources?

Mike