### SETL - The SET Programming Language

The last weeks I have played with the programming language SETL (

SETL was created in the late 1960's and is to be considered one early very high level language (VHLL) using sets as the bearing principle (like mathematical formulation) together with a PASCAL-like syntax. Some trivia:

I like SETL, much for its handling of sets and tuples (arrays) which make prototyping of some kinds of problem easy, especially those with a mathematical bent. However, the advantages SETL once had as been a VHLL, prior to the "agile" languages - e.g. Perl, Python, Ruby, Haskell, etc - is not so big anymore. (I should probably mention that I'm at least acquainted with these mentioned languages..)

In case I forgot it: See my SETL page with links and my SETL programs (and maybe some not mentioned here).

All the examples below works with GNU SETL. Many of the smaller examples is shown as a command one-liner, since I often test different features this way. And as you may notice, quite a few of the examples are not very unlike programs written in Python or Haskell.

The mandatory

A map is represented as a set of tuples of

First a slow solution:

The construct

SETL has a special syntax for multi-maps, i.e. where a key has more than one values: use "{}" instead of using the parenthesis "()" for accessing. Here the key

With a compound operators (as

GNU SETL has built in support for regular expressions (which standard SETL has not). Some examples:

Substitution (cf.

SETL also has SNOBOL/SPITBOL like patterns (but not as nicely integrated as in SNOBOL). Except as experiments, I tend to use regular expression rather than these functions.

Example: any is used like this:

A SETL procedure for

(Shell) filters:

GNU SETL has a lot of extensions for system (UNIX) handling, e.g. filter.

This is rather slow since it has to loop through a lot of values. However it don't loop through all permutations since for each variables we exclude values of the previous stated variables.

A rather fast version of calculating the prime factors of a number. Note that in GNU SETL division (

Somewhat surprising, (GNU) SETL don't have a built-in sort function, so I have to implement it myself (SETL2 has a package with a lot of different sort methods, though.). Here is the Quick sort we know from Haskell, Python etc using list/array comprehensions:

A rather inefficient but elegant version of finding the cliques in a graph is shown in cliques.setl (inspired by

This problem is from Rosetta Code (where I have taken some other problems). The SETL program is luhn_tests_of_credit_card_numbers.sets, where the procedure is as follows:

Pancake sort (see Wikipedia and Rosetta code) is a constrained method of sorting, where you may only flip a range of numbers in sequence. Here is one way to do it in SETL (see pancake_sort.setl for tests).

**Set L**anguage). I like learning these kind of "paradigmatic" programming language even if they are not very much in use anymore. There is almost always new things to learn from them, or they make one to see well known things in a new light.SETL was created in the late 1960's and is to be considered one early very high level language (VHLL) using sets as the bearing principle (like mathematical formulation) together with a PASCAL-like syntax. Some trivia:

- The first validating ADA compiler was written in SETL.
- ABC, one of the inspirations of Python was inspired by SETL.
- SETL is attributed as the first programming language that supported list (set/array) comprehensions. A very handy concept. Haskell's list comprehensions was inspired by SETL.

I like SETL, much for its handling of sets and tuples (arrays) which make prototyping of some kinds of problem easy, especially those with a mathematical bent. However, the advantages SETL once had as been a VHLL, prior to the "agile" languages - e.g. Perl, Python, Ruby, Haskell, etc - is not so big anymore. (I should probably mention that I'm at least acquainted with these mentioned languages..)

In case I forgot it: See my SETL page with links and my SETL programs (and maybe some not mentioned here).

### Different versions of SETL

There are some the different versions (or off springs) of SETL:- GNU SETL. This is the version I use here, and seems to be the only public available and working version.
- SETL2. Documented as a draft at The Restored Eye (settheory.com).
- ISETL. See ISETLJ, ISETL in Java which is to released in May/June this year. ISETL has been used in teaching mathematics, e.g. abstract algebra.

## Examples of SETL

I will not go through all features of SETL here, just show some example of what I have done and like about the language. See Programming in SETL. (Draft in Progress) (at settheory.com) for an in-depth tutorial of the language (SETL2 but much is also applied to SETL), or Robert B. K. Dewar's The SETL Programming Language (PDF) for an overview, or An Invitation to SETL.All the examples below works with GNU SETL. Many of the smaller examples is shown as a command one-liner, since I often test different features this way. And as you may notice, quite a few of the examples are not very unlike programs written in Python or Haskell.

The mandatory

**prime generation**program:primes2 := {p in {2..10000} | forall i in {2..fix(sqrt(p))} | p mod i /= 0}; print(primes2);One feature I like (and use a lot) is test things from the command line:

$ setl 'time0:=time();primes:= {p in {2..100000} | forall i in {2..fix(sqrt(p))} | p mod i /= 0}; print("Num primes:",#primes);print("It took", (time()-time0)/1000,"seconds");' Num primes: 9592 It took 2.222 secondsA variant of

**prime number generation**using`not exists`

instead of `forall`

:
$ setl 'print({n in {2..100} | (not (exists m in{2..n - 1} | n mod m = 0))}); ' {2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97}Still another variant using intersection of

`{2..n}`

and the compound numbers:
$ setl 'n := 150; print({2..n} - {x : x in {2..n} | exists y in {2..fix(sqrt(x))} | x mod y = 0});' {2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149}Here are some other examples of set/array comprehensions.

**Fibonacci sequence**As a one liner:$ setl 'f:= [1,1]; r := [f(i) := f(i-1)+f(i-2) : i in [3..10]]; print(f);'

**Pythagorean triplets**as a "one-liner" (not very fast for say [1..300]).$ setl 'print({[a, b, h]: b in {1..30}, a in {1..b - 1} | (exists h in {2..a + b} | (a*a + b*b = h*h)) and (not (exists d in {2..b - 1} | ((b mod d) = 0 and (a mod d) = 0)))}); ' {[3 4 5] [5 12 13] [7 24 25] [8 15 17] [20 21 29]}Creation of a

**power set**(all subsets of a set), with the intermediate values printed;$ setl 'a := {1,2,3}; p := { {}}; (for x in A, y in P) p with:= Y with x; print(p); end; print(p);' {{} {1}} {{} {1} {2}} {{} {1} {2} {1 2}} {{} {1} {2} {3} {1 2}} {{} {1} {2} {3} {1 2} {1 3}} {{} {1} {2} {3} {1 2} {1 3} {2 3}} {{} {1} {2} {3} {1 2} {1 3} {2 3} {1 2 3}} {{} {1} {2} {3} {1 2} {1 3} {2 3} {1 2 3}}

**Collect**values from a tuple to a map (hash table).A map is represented as a set of tuples of

`[key, value]`

.
First a slow solution:

a := [1,1,2,2,3,3,3,4,4,4,4]; m:={ [i, #[j : j in [1..#a] | a(j) = i ]] : i in { i : i in a}};Then a faster version:

$ setl 'a := [1,1,2,2,3,3,3,4,4,4,4]; m:= {}; for i in a loop m(i) +:= 1; end loop; print(m);' {[1 2] [2 2] [3 3] [4 4]}

**Index and value of a map**The construct

`for x = s(i) in ...`

in a map (hash table) loop gives both the index (i) and the value (x). Here we also see how to represent ranges with increment other than 1 (much like Haskell).
setl 's := {[i,i**2] : i in [1,3..15]}; for x = s(i) loop print(i,x); end loop;' 1 1 3 9 5 25 7 49 9 81 11 121 13 169 15 225

**Multi-map**(`m{value}`

)SETL has a special syntax for multi-maps, i.e. where a key has more than one values: use "{}" instead of using the parenthesis "()" for accessing. Here the key

*1*has two values (*a*and*c*). Using a "single-map" access (`a(2)`

gives `OM`

, the special undefined value (represented as "*" i GNU SETL).
setl 'a := {[1,["a"]], [2, ["b"]], [1, ["c"]]}; print(a);print(a(2));print(a(1));print(a{1});' {[1 [a]] [1 [c]] [2 [b]]} [b] * {[a] [c]}

**Compound operators**With a compound operators (as

**op**/tuple

or **op**/map

) makes it possible to write quite sparse code (somewhat akin to APL and J). Here is the factorial of 100, also showing the support for arbitrary precision.
$ setl 'print(*/[1..20]);' 2432902008176640000There is no built-in

`max`

for tuples. Instead we use the compound operator version, which is possible since `max`

is a binary operator:
$ setl 'setrandom(0); print(Another example of compound operators is from Project Euler problem #5 (max/[random(10000) : i in [1..100]]);' 9898

*the smallest number that is evenly divisible by all of the numbers from 1 to 20*). In my solution (project_euler5.setl) lcm and gcd is defined as operators (in contrast to procedures):print(lcm/[2..20]); -- Prints the answer. op lcm(a,b); g := a gcd b; return (a*b) div g; end op lcm; op gcd(u, v); return if v = 0 then abs u else v gcd u mod v end; end op;Speaking of Project Euler problems, here is the SETL program for the first problem (

*Find the sum of all the multiples of 3 or 5 below 1000*):print(+/{i : i in [1..999] | i mod 3 = 0 or i mod 5 = 0});In averages_pythagorean_means.setl, three different version of mean are defined (as procedures) using compound operators (maybe not the most efficient way).

-- arithmetic mean proc mean_A(x); return +/x/#x; end proc; -- geometric mean proc mean_G(x); return (*/x)**(1/#x); end proc; -- harmonic mean proc mean_H(x); return #x/+/[1/i:i in x]; end proc;

**Randomization**The`setrandom(0)`

is for creating random variables starting with an "arbitrary" seed.
setl 'setrandom(0); s := [1,3,5,8]; print([random(s) : i in [1..10]]);' [5 1 8 8 5 3 3 1 5 3]With a set we get a value only once:

$ setl 's1 := {1..10}; setrandom(0); print({ random(s1) : i in [1..10]});' {3 5 6 7 8}In GNU SETL the

**order**of the set is always presented as sorted, but this is not a requirement in the SETL language.**Regular expressions**GNU SETL has built in support for regular expressions (which standard SETL has not). Some examples:

$ setl 's:="nonabstractedness"; m:=s("a.*b.*c*.d*.e*"); print(s);print(m);' nonabstractedness abstractednessAlso see read_test2.setl that search for words like this in a word file.

Substitution (cf.

`gsub`

for global substitution):
$ setl 's:="nonabstractedness"; m:=sub(s,"a.*b.*c*.d*.e*",""); print(s);print(m);' non abstractednessNote that GNU SETL don't support non-greedy regular expressions (i.e. the ".+?" constructs from Perl etc), so the plain old

`[^...]`

construct must be used.:
$ setl 's:="nonabstractedness"; m:=s("a[^s]+s"); print(s);print(m);' nonabstractedness absA small drawback is that GNU SETL don't have support for national characters in strings. The only acceptable characters are the "plain ASCII".

**SNOBOL like pattern matching**SETL also has SNOBOL/SPITBOL like patterns (but not as nicely integrated as in SNOBOL). Except as experiments, I tend to use regular expression rather than these functions.

Example: any is used like this:

$ setl 'x := "12345 12345 12345"; print(any(x, "123"));print(x);' 1 2345 12345 12345However, I miss the

`many`

function which takes **many**characters from the beginning, not just the first and it is quite easy to create it. First let's see how it works, where we will take all the characters from the beginning of the string if they are any of "123":$ setl 'x := "12345 12345 12345"; print(x); while any(x, "123") /= "" loop print(x); end;;print(x);' 12345 12345 12345 2345 12345 12345 345 12345 12345 45 12345 12345 45 12345 12345(The corresponding regular expression for this is, of course

`^[123]+`

.)
A SETL procedure for

`many`

is defined below. The first argument is defined as read-write (`rw`

) so we can modify the string `s`

. The value returned (`z`

) contains all the matched characters.
proc many(rw s,p); z := ""; while (zz := any(s,p)) /= "" and zz /= "" loop z +:= zz; end loop; return z; end proc;'And here is

`many`

in action. Note: procedures must always be placed last in a program.
x := "12345 12345 12345"; print(x); z:=many(x, "123"); print("x",x); print("z",z); proc many(rw s,p); print(s); print(p); while (zz := any(s,p)) /= "" and zz /= "" loop z +:= zz; end loop; return z; end proc;Result:

12345 12345 12345 12345 12345 12345 123 x 45 12345 12345 z 123In look_and_say_sequence.setl

`many`

is used, as well as a direct approach and one using regular expression.
(Shell) filters:

GNU SETL has a lot of extensions for system (UNIX) handling, e.g. filter.

$ setl 'f := filter("ls p*.setl"); print(f);s := split(f,"\n");print([s,#s]);' perm.setl pointer.setl primes2.setl primes3.setl primes.setl printprimes.setl [['perm.setl' 'pointer.setl' 'primes2.setl' 'primes3.setl' 'primes.setl' 'printprimes.setl' ''] 7]Reading a file directly is by

`getline`

. Note `split()`

.
x := split(getfile("file.txt"), "\n"); print(#x);

### Some larger examples

**SEND + MORE = MONEY**This is rather slow since it has to loop through a lot of values. However it don't loop through all permutations since for each variables we exclude values of the previous stated variables.

print(send_more_money1()); proc send_more_money1; ss := {0..9}; smm := [[S,E,N,D,M,O,R,Y] : -- ensure that all numbers are different S in ss , E in ss - {S} , N in ss - {S,E} , D in ss - {S,E,N} , M in ss - {S,E,N,D} , O in ss - {S,E,N,D,M} , R in ss - {S,E,N,D,M,O} , Y in ss - {S,E,N,D,M,O,R} | S > 0 and M > 0 and (S * 1000 + E * 100 + N * 10 + D) + (M * 1000 + O * 100 + R * 10 + E) = (M * 10000 + O * 1000 + N * 100 + E * 10 + Y )]; return smm; end proc;For some other (and slower) variants, see send_more_money.setl.

**prime factors**A rather fast version of calculating the prime factors of a number. Note that in GNU SETL division (

`/`

) returns a real number, whereas in SETL2 `/`

returns an integer. So here we use `div`

instead of `/`

.
procedure prime_factors(n); facts := []; while even(n) loop facts with:= 2; n := n div 2; end loop; while exists k in [3,5..ceil(sqrt(float(n)))] | n mod k = 0 loop facts with:= k; n := n div k; end loop; facts with:= n; return facts; end prime_factors;

**Quick sort**Somewhat surprising, (GNU) SETL don't have a built-in sort function, so I have to implement it myself (SETL2 has a package with a lot of different sort methods, though.). Here is the Quick sort we know from Haskell, Python etc using list/array comprehensions:

proc qsort(a); if #a > 1 then pivot := a(#a div 2 + 1); a := qsort([x in a | x < pivot]) + [x in a | x = pivot] + qsort([x in a | x > pivot]); end if; return a; end proc;In the programs anagrams.setl and sorting.setl I compare some different sort algorithms.

**Clique**A rather inefficient but elegant version of finding the cliques in a graph is shown in cliques.setl (inspired by

`{log}`

(setlog) program Clique.slog):
proc clique(G); V := { vv : p in G, vv in p}; -- the vertices cliques := {}; for C in pow(V) loop if forall I in C | forall J in C | {I,J} in {{I}} + G then cliques with:= C; end if; end loop; return cliques; end proc;

**Luhn test of credit card numbers**This problem is from Rosetta Code (where I have taken some other problems). The SETL program is luhn_tests_of_credit_card_numbers.sets, where the procedure is as follows:

proc isluhn10(num); x := [val(i) : i in reverse(num)]; m := {[i,val("0246813579"(i+1))] : i in [0..9]}; return +/[x(i) + m(x(i+1)?0) : i in [1,3..#num]] mod 10 = 0; end proc;

**Pancake sort**Pancake sort (see Wikipedia and Rosetta code) is a constrained method of sorting, where you may only flip a range of numbers in sequence. Here is one way to do it in SETL (see pancake_sort.setl for tests).

procedure pancake_sort(rw nums); for i in [#nums,#nums-1..1] loop -- find the index of the largest element not yet sorted -- this variant is sligtly faster [this_max, max_idx] := find_max(nums(1..i)); if max_idx = i then continue; -- element already in place end if; -- flip this max element to index 1 if max_idx > 1 then nums(1..max_idx) := rev(nums(1..max_idx)); end if; -- then flip the max element to its place nums(1..i) := rev(nums(1..i)); end loop; end procedure; -- reverse a tuple procedure rev(a); return [a(i) : i in [#a,#a-1..1]]; end procedure; -- -- find the (first) index of the max value -- in a tuple. -- Returns [max_value, index] procedure find_max(a); max_idx := 1; this_max := a(1); for j in [2..#a] loop if a(j) > this_max then this_max := a(j); max_idx := j; end if; end loop; return [this_max, max_idx]; end procedure;

## Some SETL links

Here are some references of SETL.- GNU SETL: This the SETL implementation I use.
- SETL Wiki
- Library reference in GNU SETL
- www.settheory.com: "Programming in SETL", Jack Schwartz's draft of a book in SETL2 (not everything is supported in GNU SETL)
- David Bacon's PhD thesis SETL for Internet Data Processing
- Rosetta Code's entry SETL
- The SETL Programming Language: Lecture notes
- Wikipedia: SETL
- Dave's Famous Original SETL Server
- Robert B. K. Dewar: The SETL Programming Language (PDF)

## My SETL programs

I have collected some of my SETL programs at my SETL page. They are mostly small examples and experiments, and a lot are from Project Euler and Rosetta Code.- all_pairs.setl: All pairs (a slow variant of
`is_tuple`

) - anagram.setl: Anagram of a given word from a word list
- anagrams.setl: Largest sets of anagrams given a word list (Rosetta code)
- array_concatenation.setl: Array concatenation (Rosetta code)
- averages_pythagorean_means.setl: Averages/Pythagorean means (Rosetta code)
- binary_search.setl: Binary search (Rosetta code)
- binomoal.setl: Binomial coefficients
- clique.setl: Clique. Sample data: clique.in
- closest_pair_problem.setl: Closest pair problem
- collect.setl: Collect the number of occurrences in a tuple
- comb_sort.setl: Comb sort
- equation_sys.setl: Equation system
- evolutionary_algorithm.setl: Evolutionary Algorithm (Rosetta code)
- fibonacci_sequence.setl: Fibonacci sequence (different implementations)
- find_the_missing_permutation.setl: Find the missing permutation (Rosetta code)
- fizzbuzz.setl: FizzBuzz (Rosetta code)
- flatten_a_list.setl: Flatten a list (Rosetta code)
- forward_difference.setl: Forward difference (Rosetta code)
- gnome_sort.setl: Gnome sort
- greatest_subsequential_sum.setl: Greatest subsequential sum (Rosetta code)
- hailstone_sequence.setl: Hailstone sequence (Collatz sequence) (Rosetta code)
- happy_numbers.setl: Happy numbers (Rosetta code)
- hash_from_two_arrays.setl: Hash from two arrays
- in_difference.setl: In difference
- knuth_shuffle.setl: Knuth shuffle (Rosetta code)
- longest_common_subsequence.setl: Longest common sub sequence
- look_and_say_sequence.setl: Look and say sequence (Rosetta code)
- luhn_tests_of_credit_card_numbers.setl: Luhn tests of credit card numbers (Rosetta code)
- mandelbrot.setl: Mandelbrot set
- median.setl: Median
- min_max.setl: Min and max
- minimum_common_multiple.setl: Minimum Common Multiple
- pancake_sort.setl: Pancake sort
- pangram_checker.setl: Pangram checker (Rosetta code)
- perfect_numbers.setl: Perfect numbers (Rosetta code)
- primes4.setl: Primes (one of many different implementations, this is not very efficient...)
- project_euler1.setl: Project Euler, problem 1, multiples of 3 or 5
- project_euler2.setl: Project Euler, problem 2, sum of all even-valued terms in Fibonacci sequence
- project_euler3.setl: Project Euler, problem 3, largest prime factor of 600851475143
- project_euler4.setl: Project Euler, problem 4, largest palindromic number from product of two 3-digits numbers
- project_euler5.setl: Project Euler, problem 5, smallest number evenly divisible by 1..20
- project_euler6.setl: Project Euler, problem 6, difference between sum of squares and squares of sums for 1..100
- project_euler7.setl: Project Euler, problem 7, 10001st prime number
- project_euler8.setl: Project Euler, problem 8, greatest product of five consecutive digits in a 1000-digit number
- project_euler9.setl: Project Euler, problem 9, Pythagorean triplet a+b+c=1000
- project_euler10.setl: Project Euler, problem 10, sum of all primes below 2 million
- project_euler11.setl: Project Euler, problem 11, greatest product of four adjacent numbers in a 20x20 grid
- project_euler12.setl: Project Euler, problem 12, first triangle number with over 500 divisors
- project_euler13.setl: Project Euler, problem 13, first 10 digits of a sum of 100 50-digit numbers
- project_euler14.setl: Project Euler, problem 14, Collatz problem (Hailstone sequence): longest sequence for n < 1000000
- project_euler15.setl: Project Euler, problem 15, how many routes through a 20x20 grid
- project_euler16.setl: Project Euler, problem 16, sum of the digits of 2^1000
- project_euler20.setl: Project Euler, problem 20, sum of the digits in 100! (factorial)
- project_euler21.setl: Project Euler, problem 21, sum of all amicable numbers under 10000
- project_euler22.setl: Project Euler, problem 22, total of all name scores in a file
- project_euler25.setl: Project Euler, problem 25, first Fibonacci term containing 1000 digits
- project_euler28.setl: Project Euler, problem 28, sum of numbers in a 1001x1001 spiral
- project_euler30.setl: Project Euler, problem 30, sum of all numbers that can be written as the sum of fifth powers of their digits
- project_euler31.setl: Project Euler, problem 31, in how many different ways can £2 be made using any number of coins
- project_euler32.setl: Project Euler, problem 32, sum of 1..9-pandigital numbers
- project_euler34.setl: Project Euler, problem 34, sum of all numbers that are equal to the sum of the factorial of their digits
- project_euler35.setl: Project Euler, problem 35, how many circular primes are there under 1000000
- project_euler36.setl: Project Euler, problem 36, sum of all numbers, less than one million, which are palindromic in base 10 and base 2
- project_euler48.setl: Project Euler, problem 48, find the last ten digits of the series 1^(1) + 2^(2) + 3^(3) + ... + 1000^(1000)
- read_test2.setl: Reading a dictionary with regular expressions, e.g. "a.*b.*c.*d", "b.*c.*d.*e", etc). (This is one of my standard tests when learning a new programming language.)
- rot13.setl: ROT-13
- send_more_money.setl: SEND + MORE = MONEY
- shell_sort.setl: Shell sort
- shur_numbers.setl: Shur numbers
- sort_map.setl: Sorting a map
- sorting.setl: Some sorting methods
- soundex.setl: Soundex (Rosetta code)
- squares.setl: Squares
- tree_traversal.setl: Tree traversal (Rosetta code)