# The SETL Programming Language

G22.3110-001 Fall 2000

## Introduction

• SETL (for SET Language)
• high level general purpose language, based on set theory
• invented by J. Schwartz,  R. Dewar, E. Dubinsky, E. Schonberg, and W.K. Snyder, at NYU since 1975
• no more development (as far as I know)

## An Introductory Example

program printprimes;
­­ This program prints out a list of prime numbers
-- which includes all primesless than a parameter
-- value which is specified as input data.
primes := { }; -­ set of primes output so far
p := 2;    ­­ initial value to test
­­ Loop to test successive values
while p < n loop    ­­ loop as long as p less than n
ifnot (exists t in primes | p mod t = 0) then
print(p);   ­­ no divisors, it's a prime
primes with:= p;­­ add it to set of primes
endif;
p := p + 1;     ­­ move to next test value
endloop;
end printprimes;

•
• Note the empty set, and the set operations

## Assignment Statements & Expressions involving integers, reals, and strings

• Imperative language
identifier := expression;
• Case  is not significant

•
• The type of the value in a variable associated with the identifier is determined by the last value assigned:
•
abc := 4;   ­­ abc now contains an integer
abc := 4.5; ­­ abc now contains a real
• The following are examples of valid constants:
•
123             ­­ integer
134134145767671 ­­ integer
3.1415926535    ­­ real
0.45E+13        ­­ real
"abc"           ­­ string
"123"           ­­ string
"end quote\""   ­­ string
• Arithmetic operators: il general, both operand must be of the same type:
a := 3 + 4.0;        ­­ INVALID!
b := float(3) + 4.0; ­­ b = 7.0
c := 3 + fix(4.0);   ­­ c = 7
• and work on different types:
•
a := "abc";
b := "cd";
c := a + b; ­­ c now contains "abccd"
• assigning operators: like in C
•
a := 3;         ­­ a = 3
a +:= 4;        ­­ a = 7
b := a +:= 1;   ­­ a = 8, b = 8
• Strings:
•
abc := "the quick brown fox";
cde := abc(5..8);         ­­ cde = "quic"
cde := abc(5);            ­­ cde = "q"
-- abc(5..)  means 5 to end of string
cde := abc(5..);          ­­ cde = "quick brown fox"
• Substring notation can also be used on the left side of an assignment statement:
abc := "hello";
abc(3..4) := "xyz";     ­­ abc = "hexyzo"
abc(4..) := "m";        ­­ abc = "hexm"
• Slices with negative indices are also allowed, and extract elements from the end of the string

•
• A boolean can only be one of two values, either true or false.

•
• An atom is a type which is created only using the newat procedure:
•
v := newat( );

Atoms are typically used as domain elements for maps (later)

• Any procedure, all of whose formal parameters are read­only (type rd), can be used as the value of a procedure variable, and can be assigned to variables, passed as parameters, used as elements in sets, maps, and tuples, and can also be executed.
•
x := cos;
c := x(1.0);

A procedure may be defined using a procedure definition, or by means of the lambda construction:

x := lambda(y);
pi := 3.1415926536;
y := 2.0*pi*y/360.;
return cos(y);
end lambda;
c := x(90.0);                  ­­ c = 0.0

## Errors & Omega

• Improper operations, such as applying the / operator to string operands, normally causes termination of the program with an appropriate error message.
• In addition to this class of errors, there is a special undefined state called om (for omega). The "value" of undefined identifiers, or other undefined state. (Or rather the absence of any value).
• Denotes the absence of value
• May be used for resetting an identifier:

• a := om; ­­ a is now undefined

• Any attempt to perform an operation on the undefined value causes an error, excepted:

•
• equality
•
if x = om then ...
• or the shortcut
•
x := expr1 ? expr2;

that is, if expr1 evaluates to om, then x receives the value of expr2

## Tuples

• A tuple is an ordered, possibly heterogeneous sequence of zero or more values.

•
• May be created using the tuple brackets [ and ].
•
t := [1, 9, "abc", [1, 5]];
• Individual elements of a tuple can be extracted by subscripting,
• t := [1,9,"abc","def"];
x := t(3);       ­­ x = "abc"
t(4) := 0;       ­­ t = [1,9,"abc",0]
• If a non­existent element (e.g. t(7) in the above case) is selected, then om is obtained as a result.

•
• It is perfectly valid to assign a value to a non­existent element, and may result in increasing the length of the tuple:
•
t := [1,9,"abc",0];
t(5) := 5;       ­­ t = [1,9,"abc",0,5]
• If such an assignment creates "holes" in a tuple, the missing element values are set to om.

•
• It is possible to undefine a previously defined element by assigning om to it.

•
• This will either create a "hole" in the tuple value, or it will decrease the length of the tuple in the case where the last element is undefined in this manner.
• Binary Tuple Operators
•
+           Tuple concatenation
t*i or i*t   Concatenates i copies (integer i) of the tuple t.
with                 Appends an element to a tuple
frome       Extracts an element from the end of a tuple
fromb       Extracts an element from the beginning of a tuple
• Unary Tuple Operator
•
#                     Index of highest defined element
• Examples
•
a := [1,2,3];
b := [6,7];
c := a + b;     ­­ c = [1,2,3,6,7]
• Subtuples can be extracted using a notation similar to that used in extracting a substring:
•
a := [1,2,3,4,5,6,7,8,9];
b := a(6..8);       ­­ b = [6,7,8]
c := a(7..);        ­­ c = [7,8,9]
d := a(8..11);      ­­ d = [8,9]
• Subtuple operations extend to use on the left side of assignments:
•
t := [1,2,3,4,5,6];
t(2..5) := [7,10];     ­­ t = [1,7,10,6]
t(3..) := [ ];         ­­ t = [1,7]
A special notation is available for constructing tuples whose values consist of regular sequences of integers:

[1..10]    same as [1,2,3,4,5,6,7,8,9,10]
[1,3..12]  same as [1,3,5,7,9,11]
[2..1]     same as [ ]
[9,8..1]   same as [9,8,7,6,5,4,3,2,1]
[9,7..1]   same as [9,7,5,3,1]

The general form of this abbreviation is:

[first,next .. last]
• Tuples may appear on the left hand side of an assignment statement:
•
[a,b,c] := s;     ­­ a = s(1), b = s(2), c = s(3)
[d,-,f] := s;     ­­ d = s(1), f = s(3)
[e,f] := [2,4];   ­­ e = 2, f = 4
[a,b] := [b,a];   ­­ interchange a and b
• Value semantics, not pointer semantics:
•
abc := 12;
cde := abc;
abc := abc + 2;  ­­ cde still = 12

abc := [1,2,3];
cde := abc;
abc(2) := 0;     ­­ cde still = [1,2,3]

• The operator with adds a single element at the end of a tuple:
•
a := [1,5,10];
b := a with 6; ­­ a = [1,5,10], b = [1,5,10,6]
a with:= 7;    ­­ a = [1,5,10,7]
• The binary operator fromb removes the first element of a tuple

•
• and assigns it to the left operand.
• the right operand, is reassigned to contain the remainder of the tuple after removing this element.

•
• The binary operator frome is similar except that it removes the element from the end of the tuple.

•
• If fromb or frome is applied to a null tuple value, then om is obtained and the tuple value is unchanged:
•
a := [11,26,37,17];
b fromb a; ­­ b = 11, a = [26,37,17]
c fromb a; ­­ c = 26, a = [37,17]
d frome a; ­­ d = 17, a = [37]
e fromb a; ­­ e = 37, a = [ ]
f fromb a; ­­ f = om, a = [ ]
• The operators with:= and fromb used in conjunction allow a tuple to be used as a queue,

•
• with:= being the enqueue operation
• and fromb the dequeue operation:

• q := [ ];
q with:= 5; ­­ enqueue 5: q = [5]
q with:= 7; ­­ enqueue 7: q = [5,7]
e fromb q;  ­­ dequeue: e = 5, q = [7]
e fromb q;  ­­ dequeue: e = 7, q = [ ]
e fromb q;  ­­ dequeue: e = om, q = [ ] (queue empty)

Similarly,  with:= and frome used in conjunction allow a tuple to be used as a stack:

s := [ ];
s with:= 5; ­­ push 5: s = [5]
s with:=­­ push 7: s = [5,7]
e frome s;  ­­ pop: e = 7, s = [5]
e frome s;  ­­ pop: e = 5, s = [ ]
e frome s;  ­­ pop: e = om, s = [ ] (stack empty)

## Sets

• The main datatype in SETL.

• A set is like a tuple, except that it is unordered, and a given value can appear only once.

s := {1,2,"abc"};
t := {2,1,"abc"};
u := {2,1,"abc",2}; ­­ s = t = u
• Binary Set Operators
•
+         Set union
-         Set difference
*         Set intersection
with  Add one element to a set (no effect when already present)
less  Remove an element from a set (no effect if absent)
from  Remove an element and assign remainder (in a non-deterministic manner)
mod    Symmetric difference (exclusive or) of sets
npow  Set of subsets with fixed number of elements
• Unary Set Operator
•
#         Number of elements as integer
arb     Select arbitrary element (non-deterministic)
pow     Power set of a set (set of all subsets)
• Examples
•
a := {1,2,3,4};
b := {3,4,5,6};
c := a + b;     ­­ c = {1,2,3,4,5,6}
c := a * b;     ­­ c = {3,4}
c := a - b;     ­­ c = {1,2}

s := {5,2,8};
a := s with 7;  ­­ s = {5,2,8}, a = {5,2,7,8}
s with:= 6;     ­­ s = {5,6,2,8}
s with:= 5;     ­­ s = {5,6,2,8}
s less:= 5;     ­­ s = {6,2,8}
s less:= 0;     ­­ s = {6,2,8}

• Both arb and from yield om if applied to a null set, and in the case of from, the set value is unchanged.
•
a := {1,5};
b := arb a;     ­­ b = 1 or 5
c from a;       ­­ c = 1 (or 5!)
­­ a = {5} (or {1})
d from a;       ­­ d = 1 (if c was 5)
­­ d = 5 (if c was 1)
­­ a = { }
e from a;       ­­ e = om, a = { }
• As with tuples, an abbreviated form is permitted for constructing sets of integers:
•
{1..10} means {1,2,3,4,5,6,7,8,9,10}
{3,5..11} means {3,5,7,9,11}

## Maps

• Set of pairs (tuples of length 2)
•
sqroot := {[1,1], [4,2], [9,3], [16,4]};

• If a set has this special form, its values may be accessed using map notation:
•
x := sqroot(9); ­­ x = 3

• Map reference notation can also be used on the left side of an assignment:
•
sqroot(25) := 5; ­­ adds the pair [25,5] to sqroot

More precisely: compute a new map value by first removing all pairs starting with the given domain value (25, here), and then to add the specified pair.
• Reference to a non­existent element of a map (e.g. sqroot(19) in the example given) yields om.

•
• Duplicate elements in the domain are allowed, and, for example:

•
• sqroot(n) returns om, if n is duplicated;
• sqroot{n} returns the set of all values corresponding to n in sqroot.

• a := {[1,2], [1,3], [2,4], [5,5], [2,7], [2,8]};
c := a(1); ­­ c = om
d := a{1}; ­­ d = {2,3}
e := a{5}; ­­ e = {5}
f := a(5); ­­ f = 5
g := a{7}; ­­ g = { }

• This form can also be used on the left hand side of an assignment:
•
a := {[1,0], [1,2], [1,5], [2,5], [2,7]};
a{1} := {5,7}; ­­ a = {[1,5], [1,7], [2,5], [2,7]}

• All the operators which apply to sets can also be applied to maps.

•
• In addition the following special operators are provided for operating on maps:

• Binary Map Operators

lessf         Removes pairs for one domain value

Unary Map Operators

domain       Yields domain of a map
range         Yields range of a map
• All three operators cause an error if they are applied to a set which is not a map, i.e. a set which contains at least one element which is not a pair.

•
• The effect of lessf can also be obtained by an explicit assignment as shown in the following examples:

• a := {[1,2], [1,3], [2,2], [2,4], [3,6], [3,7]};
b := domain a;    ­­ b = {1,2,3}
c := range a;     ­­ c = {2,3,4,6,7}
a lessf:= 1;      ­­ removes [1,2] and [1,3]
a(2) := om;       ­­ removes [2,2] and [2,4]
a{3} := { };      ­­ removes [3,6] and [3,7]

• Special syntax is permitted when the domain elements of a map are all themselves tuples:

•
map(x,y,z) is a shorthand for map([x,y,z])
map{x,y,z} is a shorthand for map{[x,y,z]}

For example

c := {[[0,0],"a"],[[0,1],"b"],[[1,0],"c"],[[1,1],"d"]];
x := c(0,1);      ­­ x = "b"

Combining maps and atoms provides a way of dealing with pointers and dynamic data structures:

program point;
var p1 := newat();
p2 := newat();
mem2 := { [p1,"a"], [p2, "b"] };
-- mem2 is used as a store
-- where p1 and p2 act as locations
x := p1;
y := x;
mem2(x) := "hello";  -- x acts as a pointer to
print(mem2(y));      -- y is an alias to x,
-- that is, to p1
end point;

## Conditional

• If statements
•
if test1 then
statement; statement;
...
statement;
elseif test2 then
statement; statement;
...
else
statement;
...
statement;
end if;

• If expressions
•
if a > 0 then 1 elseif a < 0 then -1 else 0 end if

• Case Statements
•
case
when test1 => block1
when test2 => block2
.
.
otherwise => blocke
end case;

When more than one test succeeds, then only one of the blocks is executed, the choice of which block to execute being made in an arbitrary manner (in the same sense that the arb operator selects an arbitrary element from a set).
case expr
when expr1 => block1
when expr2 => block2
.
.
otherwise => blocke
end case;
If expr is equal to one of expr1, ..., the corresponding block is executed. A more general form is:
case expr
when expr11,expr12,... => block1
when expr21,expr22,... => block2
.
.
otherwise => blocke
end case;
• Case expressions
•
There is also a case expression, which is the same as a case statement, except that the blocks are replaced by expressions, one expression per block.
• Boolean Values & Operators
•
Binary Test Operators
=        Types and values match
/=       Types or values do not match
>        Left operand greater than right
>=       Left operand greater than or equal to right
<        Left operand less than right
<=       Left operand less than or equal to right
in       Left operand is an element or substring of right
notin    Left operand is not an element or substring of right
subset   Left operand is a subset of right (`<=' is equivalent)
incs     Left operand includes right as a subset (`>=' is equivalent)
Boolean Procedures
even(i)         Operand is even
odd(i)          Operand is odd
is_integer(v)   Operand is integer type
is_real(v)      Operand is real type
is_tuple(v)     Operand is tuple type
is_set(v)       Operand is set type
is_map(v)       Operand is map (set of pairs)
is_string(v)    Operand is string
is_atom(v)      Operand is atom
is_boolean(v)   Operand is boolean
is_procedure(v) Operand is procedure
The equality and inequality comparisons may be used to compare values of any type for exact identity, including testing for equality with om.
Binary Boolean Operators
and    Logical conjunction of two boolean values (sequential)
or     Logical inclusive disjunction (sequential)
Unary Boolean Operators
not    Logical negation
type   Yields the string "BOOLEAN"

## Loops

• Control loops
•
for iterator loop
block
end loop;

Two special statements:

continue;    -- Proceed with next iteration
exit;        -- Exit from the innermost loop

The iterator has one of several forms. Three forms are:

x in set      -- order is arbitrary
x in tuple    -- number of iterations is
--   the index of the last defined elt
x in string

for x in s loop
print(x); ­­ prints elements of s
end loop;

for x in [1,10,50] loop
...
end loop;

for [number,root] in sqrt loop    -- Several variables
...

for root=sqrt(number) loop ...  -- Alternative form
for y=t(i) loop ­­ iterate through tuple t,
-- assigning i and y
for c=s(i) loop ­­ iterate through string s,
-- assigning i and character c

The iterator may include a test:

for x in s | x > 5 loop ... -- "|" reads "such that"
for i in [1,2..10] | f(i) > 0 loop ...
Three other loop forms which can be written are:
while test loop  ­­ loop while test succeeds
...
end loop;

until test loop ­­ loop until test succeeds
...
end loop;

loop            ­­ indefinite loop
...
end loop;

• Loop expressions

• The exit statement may optionally contain an expression:

exit expression;

In this way, an entire loop may be used as a single expression, whose value is determined by the expression as evaluated when the exit statement is executed:

x := for s in set loop
statement1; ... ;
if ... then exit expression; end if;
statements; ... ;
end loop-- x is om if exit is never executed
• Set & Tuple Formers

• A set former is a special form of a loop which computes a set value with an iteration. The form is:

{expression : iterator}
-- read "the set of expression where iterator"

Examples:

{n : n in {1..100}}     ­­ integers from 1 to 100
{[x**2,x] : x in {1..5} ­­ square root map
{a : a in y | a>5}      ­­ elements > 5

Tuple formers:

[0 : i in [1..100]] ­­ tuple of length 100, all 0
[x in s | x < 0]    ­­ tuple of negative elements of s

• Quantified Tests: bind iteration variables
exists iterator | test
returns true or false, and binds the iteration variable to either om (when false) or a value that satisfies the test;
forall iterator | test
returns true or false, and binds the iteration variable to either om (when true) or a value that does not satisfies the test.

Examples:

s := {1,2,10,20};
t := [1,2,10,20];

if exists x in s | x > 3
then ... ­­ will be executed with x = 20 or 10
else ... ­­ will not be executed
end if;

if exists x in t | x > 3
then ... ­­ will be executed with x = 10
else ... ­­ will not be executed
end if;

if forall x in s | x < 30
then ... ­­ will be executed with x = om
else ... ­­ will not be executed
end if;

if exists x in t | x > 30
then ... ­­ will not be executed
else ... ­­ will be executed with x = om
end if;

if forall x in t | x < 10
then ... ­­ will not be executed
else ... ­­ will be executed with x = 10
end if;

• Compound Operators

•

Can be formed from any binary operator by appending a slash / to the name of the operator.

bop/ exprs        -- exprs must be a set or tuple
expre bop/ exprs  -- exprs must be a set or tuple
bop/ exprs    means  e1 bop e2 bop e3 ...
result is om if tuple or set is empty
expre bop/ exprs means expre bop e1 bop e2 ...
result is value of expre if tuple or set is empty
Examples:
+/ t       ­­ sum of values in tuple
0+/ t      ­­ same, but 0 rather than om for [ ]
*/ [a in s | 3 in a]  -- inters. sets that contain 3
" "+/ t    ­­ builds string from tuple of chars

# Stop and null statements

• The stop statement:
•
stop;

causes immediate termination of execution.

• The null statement:
•
null;

has no effect and thus acts as a no­operation statement.
case i
when 1,3,5 => print(i);
when 2,4,7 => print(i+1);
when 0,6,9 => null; ­­ do nothing in these cases
otherwise => print("no good");
end case;

# Using the interpreter

• When using SETL2, you must first create a library using the command:
•
stll -c setl2.lib

SETL2 modules (programs or packages) may then be compiled using:
stlc file
The compiled units will be stored in the library file setl2.lib under the working directory.

To execute a program that has been successfully compiled, execute the command

stlx prog_name

where prog_name is the name of the program from the program statement (and not the name of the file
containing the source file for the program).

See the manual pages for more information on the stll, stlc, and stlx commands.