The SETL Programming Language

G22.3110-001 Fall 2000

Introduction
An Introductory Example
Assignment Statements & Expressions involving integers, reals, and strings
Errors & Omega
Tuples
Sets
Maps
Conditional
Loops
Input-output: cf. SETL report
Stop and null statements
Using the interpreter
Example Programs

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.
    read(n);   read input parameter
    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;

Ada-like syntax

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 readonly (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 nonexistent 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 nonexistent 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:= 7 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 nonexistent 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).

caseexpr
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 expreif 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

Input-output: cf. SETL report.

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 nooperation 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

SETL2 may be obtained by anonymous ftp to ftp://cs.nyu.edu/ .

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.

Example programs

[Back to top]