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.

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.

The SETL Language

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.

Scalar Data Types and Operations

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

Sets

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.

______________________

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

Webinar
One Click, Universal Protection: Implementing Centralized Security Policies on Linux Systems

As Linux continues to play an ever increasing role in corporate data centers and institutions, ensuring the integrity and protection of these systems must be a priority. With 60% of the world's websites and an increasing share of organization's mission-critical workloads running on Linux, failing to stop malware and other advanced threats on Linux can increasingly impact an organization's reputation and bottom line.

Learn More

Sponsored by Bit9

Webinar
Linux Backup and Recovery Webinar

Most companies incorporate backup procedures for critical data, which can be restored quickly if a loss occurs. However, fewer companies are prepared for catastrophic system failures, in which they lose all data, the entire operating system, applications, settings, patches and more, reducing their system(s) to “bare metal.” After all, before data can be restored to a system, there must be a system to restore it to.

In this one hour webinar, learn how to enhance your existing backup strategies for better disaster recovery preparedness using Storix System Backup Administrator (SBAdmin), a highly flexible bare-metal recovery solution for UNIX and Linux systems.

Learn More

Sponsored by Storix