Arrays in Flux: SETL - The SET Programming Language (original) (raw)

The last weeks I have played with the programming language SETL (Set Language). 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:

For more about the history of SETL, see A Brief History of SETL in David Bacon's dissertation "SETL for Internet Data Processing". David Bacon is the person behind GNU SETL. In the section Comparison with Other Languages Bacon compares SETL with some other languages (Perl, Icon, Functional Languages, Python, Rexx, and Java).

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:

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 seconds

A 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 sequenceAs 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} | (aa + bb = 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]);' 2432902008176640000

There 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(max/[random(10000) : i in [1..100]]);' 9898

Another example of compound operators is from Project Euler problem #5 (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;

RandomizationThe 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 abstractedness

Also 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 abstractedness

Note 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 abs

A 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 12345

However, 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 123

In 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;

Here are some references of SETL.

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.