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

White Paper
Linux Management with Red Hat Satellite: Measuring Business Impact and ROI

Linux has become a key foundation for supporting today's rapidly growing IT environments. Linux is being used to deploy business applications and databases, trading on its reputation as a low-cost operating environment. For many IT organizations, Linux is a mainstay for deploying Web servers and has evolved from handling basic file, print, and utility workloads to running mission-critical applications and databases, physically, virtually, and in the cloud. As Linux grows in importance in terms of value to the business, managing Linux environments to high standards of service quality — availability, security, and performance — becomes an essential requirement for business success.

Learn More

Sponsored by Red Hat

White Paper
Private PaaS for the Agile Enterprise

If you already use virtualized infrastructure, you are well on your way to leveraging the power of the cloud. Virtualization offers the promise of limitless resources, but how do you manage that scalability when your DevOps team doesn’t scale? In today’s hypercompetitive markets, fast results can make a difference between leading the pack vs. obsolescence. Organizations need more benefits from cloud computing than just raw resources. They need agility, flexibility, convenience, ROI, and control.

Stackato private Platform-as-a-Service technology from ActiveState extends your private cloud infrastructure by creating a private PaaS to provide on-demand availability, flexibility, control, and ultimately, faster time-to-market for your enterprise.

Learn More

Sponsored by ActiveState