SETL

SETL - short for SET Language - is a very high-level programming language in which the primitive data types are the objects of finite set theory: unordered sets, tuples, and maps over arbitrary domains. Designed by Jacob T. “Jack” Schwartz at New York University’s Courant Institute around 1969-1970, its premise was that a programmer should be able to write down what an algorithm computes, in more or less the notation a mathematician would use, and leave the choice of data structures to the compiler.

SETL never became a widely used language. Its influence, however, is peculiarly large and peculiarly well hidden. It produced the first validated Ada compiler. It supplied the executable notation for Gregory Chaitin’s graph-colouring register allocator. And by way of ABC, it is the reason Python has dictionaries, a set type, and comprehensions.

History and origins

Schwartz was a mathematician - the co-author, with Nelson Dunford, of the three-volume Linear Operators - who came to computing through program optimization. Visiting IBM Research, he worked with John Cocke and Frances Allen on the optimization techniques that they had pioneered, and co-wrote with Cocke an encyclopedic report on compiler construction that, though never formally published, founded compiler optimization as a subject of study.

The algorithms that came out of that work - global data-flow analysis, interval analysis - have a natural expression in terms of sets and relations, and were miserable to write in Fortran, the language of choice at the time. According to a note on the C2 wiki cited by the SETL Historical Sources Archive, Schwartz drafted the first design of a set-theoretic language over the summer of 1969 while at IBM; IBM decided not to pursue it, and he carried it back to NYU. Dave Shields recalled running into him near 90th and Broadway “in late summer 1970 (or perhaps 1971)”, when Schwartz explained that he was building a programming language based on the theory of finite sets: “I thought it then, and have had the same view ever since, that this was the single greatest idea for a programming language that I have ever encountered.”

The first public document, “Set theory as a language for program specification and programming,” is dated September 1970. Its opening states the case plainly:

“It may be remarked in favor of SETL that the mathematical experience of the past half-century, and especially that gathered by mathematical logicians pursuing foundational studies, reveals the theory of sets to incorporate a very powerful language in terms of which the whole structure of mathematics can rapidly be built up from elementary foundations.”

The 298-page “Abstract algorithms and a set theoretic language for their expression” followed in December 1970, and SETL Newsletter number 1 - Malcolm Harrison’s proposal to prototype SETL in his own BALM language - is dated 5 November 1970. The newsletters eventually ran to 234 numbers across 1970-1981 and 1985-1989.

Three generations of implementation

The implementation history came in layers.

LITTLE was Schwartz’s own systems language, syntactically Fortran-like with a bit-field extraction notation and only two built-in types - fixed-length bit strings and floating-point numbers. Shields bootstrapped it to self-hosting by the end of 1973, and it was ported from the CDC 6600 to System/360, the DEC-10, and VAX. The 1986 book Programming with Sets records SETL implementations on the CDC 6600, CDC Cyber, DEC VAX, IBM System/370, and Sun and Apollo workstations; in the 1970s, Ershov’s group in Novosibirsk brought it to the BESM-6, and Soviet accounts report that it later reached ES EVM machines.

Design philosophy

The SETL argument runs roughly as follows. A programmer writing in a conventional language spends most of their effort on two things that have nothing to do with the problem: choosing concrete data structures, and writing the loops that walk them. Both are mechanical. Both can, in principle, be done by a compiler. Give the programmer sets and quantifiers instead, and the program shrinks to the size of its specification.

Schwartz’s goal, as the archive puts it, was “to express functionality rather than algorithm and data structure detail, in effect to think like a mathematician rather than a programmer.”

Crucially, this was not a functional language and made no attempt to be. The set-theoretic core sits inside an entirely conventional imperative shell: assignment, if, loops, procedures, recursion, global state. Higher-order functions were, in Davis and Schonberg’s description, deliberately omitted as too radical for the time. SETL is what you get when you take Fortran-era procedural programming and swap out its data types for those of ZF set theory.

Key features

Sets and tuples. The two aggregate types. Elements may be of any type, including other sets and tuples. Sets are unordered and duplicate-free; tuples are indexed sequences.

s := {1, 2, 3, 'apple', [4, 5]};
t := ["age", 21];

Maps as sets of pairs. There is no separate dictionary type - a map is a set of two-element tuples. Applying it with parentheses gives the single value, with braces the set of all values:

f("age")      -- single-valued retrieval
f{"age"}      -- multi-map retrieval: the set of all values
{[y, x] : [x, y] in m}    -- the inverse of a map, in one expression

om. The distinguished undefined value, returned by any map application or index with no value, and never a member of any set. om is SETL’s answer to what a partial function does off its domain, and it predates the null-safety debates by decades.

Set and tuple formers. The comprehension notation, in which the resemblance to modern Python is unmistakable in both directions of borrowing:

{x * x : x in {1..10} | x mod 2 = 1}

First-order quantifiers as expressions. forall, exists and notexists are ordinary boolean expressions, which makes the classic prime sieve a one-liner:

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

Compound operators. A reduction operator folds a binary operator over a tuple, so factorial has a conventional recursive definition and a more idiomatic one-expression form:

procedure factorial(n);          -- calculates n!
  return if n = 1 then 1 else n * factorial(n - 1) end if;
end factorial;

*/[1..n]                          -- the same thing, as a product reduction

Compound assignment over maps, which makes word-frequency counting about as short as it can be written:

count := {};
for word in split(getfile stdin) loop
  count(word) +:= 1;
end loop;

The representation sublanguage and automatic data structure choice

The hardest problem SETL set itself was performance, and its most original answer was to make representation a separate concern from the program. A programmer could write the algorithm purely set-theoretically and then, optionally and separately, annotate declarations with hints from a representation sublanguage describing how sets should actually be stored - as hash tables, bit vectors, linked structures, or based on an enumerated “base set.”

Better still, the compiler could choose for itself. Automatic data structure selection was the subject of Ssu-cheng Liu’s thesis and of Schonberg, Schwartz and Sharir’s POPL ‘79 and TOPLAS 1981 papers, and it was implemented in the SETL optimizer alongside Aaron Tenenbaum’s type-inference work and Robert Paige’s finite differencing - the systematic transformation of expensive expressions recomputed inside loops into cheaply updated invariants.

This is where SETL was furthest ahead of its time and, as Fritz Henglein observed, where its influence was most thoroughly forgotten:

“SETL has had a significant (but well-hidden) intellectual impact on programming language research and development; in some cases it was so far ahead of its time, e.g. for classical data flow analysis … value-oriented programming with updatable variables aliasing and hashing to make this work efficiently, flow/dynamic type analysis for structured data (rediscovered in the 90s without knowledge of SETL work in the 70s and 80s), set and map data types (via ABC, a predecessor for Python’s dictionaries), comprehension notation (popularized in 80s and 90s as list comprehensions …).”

The honest caveat is that the optimizer never fully closed the gap. It was a roughly 24,000-line SETL program, and on 1980s hardware it was too large to be applied to itself. SETL programs remained slow enough that the language was pitched as a prototyping medium rather than a production one - which, in the case of Ada/Ed, was exactly the point.

Evolution and descendants

SETL proper stopped evolving at NYU in the mid-1980s, as Schwartz’s attention moved to parallel computing and robotics and then to DARPA. What followed was a diaspora of dialects.

• SETL2 (W. Kirk Snyder, 1990) is a deliberately backward-incompatible redesign with syntax and style borrowed from Ada. Snyder has described two SETL2s: an officially funded Office of Naval Research effort with a front end in Ada that never ran, and his own skunkworks C implementation that started as fun and became the one people used.
• ISETL (Gary Levin, from 1986) went the other way: a smaller, interactive subset for teaching, with first-class functions added. Ed Dubinsky built a run of Springer textbooks around it.
• SETL/E and ProSet (Ernst-Erich Doberkat, Essen and Dortmund, from about 1990) added persistent stores and process creation, and later Linda tuple spaces, aimed at prototyping concurrent and parallel systems.
• Cantor (Jean-Pierre Keller, from about 1991) derived from ISETL and grew out of the ESPRIT SED (SETL Experimentation and Demonstration) project of the late 1980s, which had built a SETL-to-Ada translator, editor, debugger and profiler.
• Griffin (NYU, early 1990s) was the ambitious, never-completed general-purpose successor, blending SETL with ML- and Haskell-style type inference. Schonberg’s verdict: the trends “did not lead to a viable new language, but produced a number of extremely stimulating discussions among the participants.”
• SetlX (designed mostly by Karl Stroetmann, implemented by Tom Herrmann) is a modern reworking with C/Java-influenced syntax, Prolog-like terms, functional programming, backtracking and plotting, intended to make SETL’s ideas accessible to today’s students. It runs on the JVM; per its own documentation, version 2.7.2 dates from 2019.
• GNU SETL (David Bacon) is the closest thing to a living SETL. Bacon’s January 2000 NYU thesis, SETL for Internet Data Processing, set out to make SETL “play well in the Unix (POSIX) world of processes, pipes, filters, sockets, and programs written in other languages.”

Current status

GNU SETL is the implementation to use today. It is written in C, distributed under the GPL, and available from setl.org and from the davidjbacon/SETL repository on GitHub. Its first public source release was version 3.5.8 on 12 December 2022; subsequent releases have numbered themselves along the Fibonacci sequence - 5.8.13 (8 April 2024) and 8.13.21 (9 November 2024) - then 8.13.22 (7 February 2025), which steps one past it, a fix to non-MAGIC string matching. The project’s INSTALL file says to “expect best results for Posixy (Unix-supportive) environments such as Linux, QNX, Solaris, the BSDs, HP-UX, AIX, IRIX, Darwin, and Cygwin,” and notes that Macs on Apple silicon need a newer GMP than the bundled 6.1.2. There is no official Docker image.

The historical record is in unusually good shape. Since 2020, Paul McJones’s SETL Historical Sources Archive at the Computer History Museum’s Software Preservation Group has collected the LITTLE-based compiler and run-time sources (a VAX UNIX version from around January 1985, donated by Stefan Freudenberger), the optimizer, recovered distribution tapes, the SETL2, ISETL and Ada/Ed sources, theses, manuals, and scans of SETL Newsletters 1 through 217 - roughly 2,700 pages of the project’s internal correspondence.

Schwartz died on 2 March 2009; Robert Dewar, who went on from Ada/Ed to co-found AdaCore and lead GNAT, died in 2015. The language is dormant in the sense that nobody is designing it any further, but its artifacts are better preserved than those of most languages a hundred times more popular.

Why it matters

Fran Allen, asked in 2011 what she thought of SETL, gave the fairest summary anyone has: “It wasn’t the right thing for that time, but it may be an interesting language to go back and look at now that we’re mired in over-specifying.”

The specific things SETL got right, decades early, are now unremarkable. Sets and hash maps as language-level primitives with literal syntax. Dictionaries keyed by arbitrary values. Comprehensions with filters. Arbitrary-precision integers. A distinguished undefined value with defined semantics. Dynamic typing with a type inferencer trying to recover static information behind the programmer’s back - which is, more or less, what every modern JIT for a dynamic language does. Prototyping in a very high-level language before committing to an implementation.

The specific thing it got wrong was timing. A language whose whole proposition is “let the compiler pick the data structures” needs either a very good compiler or a very fast machine, and in 1975 it had neither. What SETL had instead was a set of ideas patient enough to wait: through ABC to Python, through Ada/Ed to GNAT, through the optimizer papers into the analysis literature, and through Chaitin’s appendix into every register allocator since.