GNU SETL Om

Introduction

{1..n}

{p in {2..n} | forall i in {2..p-1} | p mod i /= 0}

{p in {2..n} | notexists i in {2..p-1} | p mod i = 0}

["age", 21]

{["name", "Jack"], ["age", 21]}

To the Student of Programming Languages

There are no pointers (no references, no aliases) in SETL, and it is natural to wonder how such a language could be convenient or even widely useful.

The answer is the maps. Where you might be tempted to think pointers are necessary, such as in a linked data structure, it is usually better to make the nodes the range elements of a map over a more interesting domain than memory pointers, and let the node references be the keys of that map.

This pointer-free aspect of SETL is sometimes called its strict value semantics. Conceptually, every assignment or parameter pass means copying. For a set or tuple, copying applies recursively.

Programming without pointers seems to be much simpler than with them, as all the hazards of aliasing and of “dangling” pointers disappear. But what about the cost of all that copying?

As Annie Liu observes in some notes on files received from Jack Schwartz, the value semantics makes powerful optimization techniques such as Paige’s finite differencing much easier to implement than when aliases have to be considered.

Alas, GNU SETL does not employ those advanced techniques. It copies in many places where the copying could in principle be optimized or differenced away. It is surprising how seldom that matters in the typical data processing setting, however. Sets and in particular maps are efficiently implemented, which helps.

Maps are central to SETL. Here is how a map count might be built up, using a loop to tally input word frequencies:

count := {};           -- empty map
for word in split(getfile stdin) loop  -- whitespace-delimited words
  count(word) +:= 1;   -- init to 1, or add 1
end loop;

We can now print a crude histogram from the count map:

for [word, freq] in count loop  -- loop through the map
  print(freq * "*", word);   -- print freq stars and the word
end loop;

In that way of iterating over the map, successive ordered pairs are broken out from count and assigned to [word, freq], meaning word gets the string and freq gets the associated tally on each iteration.

EXERCISE 1. A set-building notation was introduced in the prime-numbers example (see primes). So now, for any given map m, what does

{[y, x] : [x, y] in m}

represent?

You may guess that it is the inverse of m (which it is), but is that colon a misprinted vertical bar?

Actually, it is not. The general form of the inside of a set former such as the above is:

expression : iterator | condition

The expression characterizes each member of the set being formed, and is evaluated for each iteration of the iterator for which the condition is true. Bound variables (like word, or like x and y) are assigned values on each iteration, and will often appear in the condition and expression.

The iterator itself can actually be a series of chained iterators separated by commas, where the iterators to the right loop within those to the left, and can therefore refer to variables bound by them.

A tuple former is just like a set former but uses square brackets ([]) instead of curly braces ({}). It constructs a tuple with elements in the order produced by iteration.

The general form shown above has two main degenerate forms. You can omit the condition, leaving

expression : iterator

as in the map-inverse example above, in which case the condition defaults to true. Or you can omit the expression, leaving

iterator | condition

as in the prime-numbers example (see primes). In that example, the expression defaults to p, the expression to the left of the first in.

The other major users of iterators in SETL, besides the loops and the set and tuple formers, are the quantified expressions, which have forall, exists, or notexists followed by iterator | condition. For example,

forall i in [2..10] | 11 mod i /= 0

is true, because 11 is in fact prime.

Let us now examine iterators in a little more detail. The most common kind has the general form

lhs in s

where the lhs is anything that can be assigned to, and s is an already existing set, string, or tuple. For a “structured” lhs such as [x, y] or [[x, y], z], every member of s must be a tuple that is structurally compatible with lhs, by the same rule that governs parallel assignments such as

[a, b] := [b, a]

which swaps the values of variables a and b.

When used in a set or tuple former, the lhs part of the above lhs in s iterator form serves also as the default expression when the expression is omitted.

For SETL beginners with a background in formal set theory, the resemblance between iterator-based SETL set formers and abstract mathematical set builders provides a dual view of the set as an object to be built up by computation on the one hand and as an intensionally defined comprehension on the other. In both cases, the expression gives the “shape” of the elements. There is a similar duality between the quantified expressions of SETL (forall, exists, notexists) and those of mathematical logic.

For SETL beginners without a background in set theory or logic, but with some familiarity with other programming languages, the iterators in formers and quantified expressions may be the least obvious aspect of SETL. The thing to remember is that they represent loops. Where you see a set former that looks as if it contains undefined variables, look to see if those variables are actually the bound variables of an iterator that is just after the colon and/or just before the vertical bar. An iterator will always have either the keyword in or an equals sign (=) in it.

An additional role for the in keyword is as the name of a binary operator;

x in s

is a boolean-valued membership test for whether the value x occurs in s.

EXERCISE 2. Given sets s1 and s2, identify the iterator and the boolean expression in

{x in s1 | x in s2}

EXERCISE 3. Given the same sets again, state whether that set is the same as

{x in s2 | x in s1}

The answer to the latter is indeed yes, these both represent the intersection of s1 and s2 (which could be written in SETL more simply as s1 * s2). But in the absence of some fairly sophisticated code optimization, they get there by different means: if s1 has a huge number of members, and s2 very few, it will take much longer to do it the first way (iterating through s1 and testing each member for membership in s2) than the second.

The order in which members are selected during iteration over a set in SETL is left up to the implementation. It is arbitrary. Similarly, the SETL arb (“choice”) operator selects a set member arbitrarily, and the SETL from statement selects and removes an arbitrary member from a set. Programmers should treat this arbitrariness as nondeterministic, but not random. “Random” implies some kind of stochastic process in the selection, and SETL has a separate operator to approximate that, called random.

SETL has further iterator forms such as

y = f(x)

for iterating over a single-valued map f while assigning successive corresponding domain and range values to x and y respectively. For the single-valued map case, this iteration is equivalent to the form

[x, y] in f

so we could tighten up the loop header in the word-counting example to read

for freq = count(word) loop

in order to document and check that the map count is expected to be single-valued. If count were any other kind of set, such as a multi-map or a set containing something other than ordered pairs, a run-time error would result.

Once again, we see a strong syntactic resemblance between an iterator and a boolean expression; and “freq = count(word)” is certainly true within the body of the above loop.

That functional-style iterator form is also applicable when f is a string or tuple, in which case x successively takes on the values 1 through the length of the string or tuple, as y gets assigned the corresponding characters of the string or members of the tuple. This is also consistent with the notation for element access (“subscripting”) for these types.

Multi-map iteration is indicated by braces rather than parentheses, as in multi-map selection:

ys = f{x}     -- ys gets range subset for each x

These iterator shorthands also work like their corresponding selection operations:

z = f(x, y)   -- means z = f([x, y])
zs = f{x, y}  -- means zs = f{[x, y]}

GNU SETL

GNU SETL is an implementation of SETL, with a few extensions. The goal was always a setl command that would play well in a Unix-like environment, allowing it to be used as easily as say awk, sed, or grep. Even with an external interface consisting of little more than basic I/O, setl did indeed prove to be a valuable tool in a variety of roles, from combinatorial experiments to routine scientific data processing. However, there came a time when it seemed worthwhile to add new facilities for working more directly with processes, signals, timers, and sockets.

SETL is something of a natural for event-driven and distributed systems. Passing SETL maps etc. between processes is particularly easy, as most values can be serialized for transport by a simple write and deserialized by a simple read.

Neither the SETL language nor the GNU SETL implementation is well suited to “programming in the large”. But Unix has taught us how useful it can be to chain processes into pipelines in everyday data processing, and I personally have had great fun prototyping event-driven systems as trees of processes, all on the same general pattern as advertised in the case study in dB’s thesis. The SETL programs in those systems range from tiny (buffers, dispatchers, multiplexers, etc.) to medium-sized. The decentish high-level string handling in GNU SETL, and its rich repertoire of process management, let it deal pretty competently with external programs, especially the many text-based utilities in the Unix/POSIX canon. Another reusable text-based pattern is seen in practice where wish interpreter is invoked as a subprocess and fed Tcl/Tk commands to build a GUI based on traversal of a nested SETL tuple that specifies the elements and layout in a rather declarative manner. Events from the widgets come back as text, and updates are sent as further Tcl/Tk commands.

Here is a summary of GNU SETL’s main extensions to SETL:

• a POSIX-based interface to networks, signals, timers, and processes;
• substring extraction and substitution by regular expression;
• support for SETL2 control structure syntax and packages;
• a dot notation f.x as syntactic sugar for f("x"), letting a map f act as a record with a field x that may come and go dynamically;
• procedure references and indirect calls;
• a notation that allows one variadic procedure to call another with trailing args presented as if they had come from the caller of the first procedure, for use in implementing things like logging functions where you want to pass the top-level caller’s args to print after some context args such as a timestamp.

For a list of GNU SETL functions, operators, and special values and variables, including extensions, see the GNU SETL Library Reference.

SETL Variations

*** To be a summary of how GNU SETL differs from CIMS SETL and from SETL2. May point to www.settheory.com and Jack’s unfinished book, perhaps commenting on the different approach embodied in his Tk chapter vs. how I use wish pumps.

*** This might also be the place for some brief mention of SETL’s relatives such as Python, or at least a few words to mention that my thesis goes into that a bit.

Links

Administrivia

Index