" /> Arrays in Flux: April 2010 Archives

« March 2010 | Main | November 2012 »

April 27, 2010

SETL - The SET Programming Language

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:
  • 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.
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:
  • 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 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 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]);'
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;
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
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;

Some SETL links

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.