SETL Historical Sources Archive — Software Preservation Group (original) (raw)

Document Actions

A collection of artifacts from the SETL programming language project, led by Jack Schwartz at New York University.

Paul McJones, editor (paul@mcjones.org - https://mcjones.org/paul/)
Software Preservation Group
Computer History Museum

Abstract

This project attempts to discover, preserve, and present primary and secondary source materials (including specifications, source code, manuals, and papers discussing theory, design and implementation) from the history of SETL. Jacob T. "Jack" Schwartz started the SETL project around 1970 at the Courant Institute of Mathematical Sciences of New York University. The project developed a very high level programming language, SETL, based on the idea of finite sets as the fundamental data structure.

Comments, suggestions, and donations of materials (which will be housed at the Computer History Museum) are greatly appreciated.

Contents

Introduction

"While visiting IBM, Jack worked with the IBM researchers John Cocke and Frances ("Fran") Allen in connection with the work on program optimization that they had pioneered. ... Jack’s own interest in programming languages was triggered by working with Allen and Cocke. He collaborated with John Cocke on an encyclopedic treatment of concepts and techniques for compiler construction that, although published only as a Courant Institute report, was quite influential. It contained the first systematic survey of parsing techniques, as well as code-generation algorithms for imperative and functional languages, and more recondite pattern-matching techniques. Far more important were optimization techniques that were truly seminal to the field of compiler development and its history. In addition to new techniques, a lasting framework for the subject was created. Compiler optimization as a subject of study began with this report, and as a result the Courant Institute became the place where the most important optimization techniques, and students, were produced. This work has been directly present in virtually every compiler ever written since, usually in much the way first laid out in the Cocke-Schwartz report.

The algorithms developed at IBM for global data-flow analysis and program decomposition (interval analysis) have a natural set-theoretic expression, but these algorithms proved to be hard to implement in the programming language of choice at the time, namely Fortran. This led Jack to embark on a large effort to design and implement his programming language SETL based on set-theory, and to prove its usefulness as a specification language by recasting numerous algorithms in various areas of computer science into this language. SETL underwent several implementations, and design improvements with substantial contributions from Robert Dewar and others [Schwartz et al. 1986]. The central feature of the language is the use of sets and mappings over arbitrary domains, as well as the use of universally and existentially quantified expressions to describe predicates and iterations over composite structures. this set-theoretic core is embedded in a conventional imperative language with familiar control structures, subprograms, recursion, and global state in order to make the language widely accessible. Conservative for its time, it did not include higher-order functions. The final version of the language incorporated a backtracking mechanism (with success and fail primitives) as well as database operations. The popular scripting and general purpose programming language Python is understood to be a descendent of SETL, and its lineage is apparent in Python’s popularization of the use of mappings over arbitrary domains." [Davis and Schonberg 2011]

"Guy L. Steele: Could you talk about Jack Schwartz?

Fran E. Allen: Jack spent a summer at ACS and had a huge influence. He wrote a number of wonderful papers on optimizing transformations, one being "Strength reduction, or Babbage's differencing engine in modern dress." Jack had a list of applications for strength reduction, which we in compilers never took advantage of. He and John wrote a big book, never published but widely circulated, on a lot of this work [Cocke and Schwartz 1970]. I spent a year in the Courant Institute -- I taught graduate compilers. And Jack and I were married for a number of years. So it was a good relationship all around.

GLS: What did you think about SETL [a programming language developed by Schwartz]?

FEA: 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.

GLS: Gregory Chaitin's classic PLDI paper on "Register Allocation and Spilling via Graph Coloring" [Chaitin 1982] contains a substantial chunk of SETL code, four and a half pages, that implements the algorithm.

FEA: I liked SETL and was amazed that they got some good compiling applications out of it. In the context of multicores and all the new challenges that we've got, I like it a lotit's one instance of specifying the problem at such a high level that there's a good possibility of being able to target multiple machines and to get high performance from programs that are easy to write." [Steele 2011]

"In the present paper we will outline a new programming language, designated as SETL, whose essential features are taken from the mathematical theory of sets. SETL will have a precisely defined formal syntax as well as a semantic interpretation to be described in detail; thus it will permit one to write programs for compilation and execution. 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. By applying SETL to the specification of a number of fairly complex algorithms taken from various parts of compiler theory, we shall see that it inherits these same advantages from the general set theory upon which it is modeled. It may also be noted that, perhaps partly because of its classical familiarity, the mathematical set-notion provides a comfortable framework, that is, requiring the imposition of relatively few artificial constructions upon the basic skeleton of an analysis. We shall see that SETL inherits this advantage also, so that it will allow us to describe algorithms precisely but with relatively few of those superimposed conventions which make programs artificial, lengthy, and hard to read." [From Schwartz, September 1970, written when he was working at IBM in the summer of 1969, according to https://wiki.c2.com/?SetlLanguage]

"I recall well the day I ran into Jack Schwartz at the corner of 90th and Broadway or near about in late summer 1970 (or perhaps 1971). He said he had been working on a project at IBM Research, but since IBM had decided not to pursue it any more, it was up to him. He then said he was working on creating 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." [Dave Shields, personal communication, 9 April 2020]

"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 (which did made it into mainstream compiler research), 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 [the?] predecessor for Python’s dictionaries), comprehension notation (popularized in 80s and 90s as list comprehensions and later via their analysis as monads, typically without knowledge of SETL and its predecessors such as SNOBOL and ICON)." [Fritz Henglein, personal communication, 17 May 2020]

Documents, reports, and theses

SETL Newsletters

"A miscellaneous collection of papers mostly concerned with implementation problems, but some have an independent theoretical importance. Variously authored." [Bonic 1973]

"NYU SETL Project. SETL Newsletters. Numbers 1–234, Courant Institute of Mathematical Sciences, New York University, 1970–1981 and 1985–1989." [Bacon 2000]

SETL Newsletter. Scans of Numbers 1-217 (constituting some 2700 pages) were provided by Stefan M. Freudenberger:

SETL Newsletter. Citations and some PDF files for Numbers 220-233 were provided by Fritz Henglein:

Publications

Implementations

BALM-based SETL: SETLB and SETLA

Around the time Schwartz began thinking about SETL, his NYU colleague Malcolm Harrison designed a language calledBALM, which became a tool for early prototypes of SETL:

"In fact there was an earlier implementation of SETL at NYU (one archeological layer below) done in BALM (which stood for branch-and-link mechanism) a language designed at NYU by Malcom Harrison, which had roughly the semantics of LISP and the syntax of ALGOL 60." [Ed Schonberg, personal communication, 8 April 2020]

"I wrote the first implementation of SETL, called BALMSETL, as it was written in BALM, a block-like extension of LISP. ..." [Dave Shields, personal communication, 9 April 2020]

"There have been a number of implementations of SETL and SETL-like languages over the years. The first was called SETLB [Mullish and Goldstein 1973] and was implemented using an extension of Harrison’s extensible LISP-like BALM language, BALMSETL [Harrison 1970, Shields 1971]. SETLB was succeeded by SETLA [Schwartz et al. 1972], was implemented in BALMSETL, and was an almost strict subset of SETL." [Bacon 2000]

"SETLA is an implemented version of a subset of SETL, a set-theoretic language developed at NYU by Jack Schwartz. ... SETLA is for the most part a compatible subset of SETL (to a much greater extend than its predecessor, SETLB). However, BALM still plays an important role in the structure of SETLA, and this is reflected in some of its features which do not properly belong to standard SETL. Note in particular that name scoping and the special conventions which apply to begin blocks and statement labels are the same in SETLA, BALMSETL, and, indeed, in BALM. The SETLA precedence rules and procedure linkage mechanisms are however those of SETL, rather than those of BALM or BALMSETL. 'BALMSETL' above refers to a series of BALM procedures which implement SETL primitives as BALM extensions. The structure, and indeed the existence of BALMSETL out to be invisible to the SETLA user, and will be for the most part. See however section 3, 5, and 8 for unavoidable instances of BALMSETL visibility." [Schwartz et al. 1972]

LITTLE-based SETL

"Jack had created a low-level language called LITTLE. It had the bitfield as the basic data type, and was based on a very clever macro language to extend LITTLE's expressive power. The original version was written in FORTRAN. I took over the project and bootstrapped it to a version coded in LITTLE. This was done by the end of 1973. The next implementation of SETL was written in LITTLE by Robert Dewar and Art Grand. During that time we were porting LITTLE from the CDC 6600 to other systems, notably System/360, DEC-10, VAX 32v and VAX/VMS. (LITTLE was later ported to the PDP-11, though I played no role in that.)" [Dave Shields, personal communication, 9 April 2020]

"Hank [Henry S. Warren] worked on SETL definition and SRTL, the run time library for SETL. It was written in LITTLE." [Dave Shields, personal communication, 27 April 2020]

"The full SETL language itself was implemented in LITTLE [Warren 1971], syntactically a Fortran-like language supplemented with a notation for bit-field extraction. LITTLE had only two built-in data types, fixed-length bit strings and floating-point numbers, but was used to implement both the compiler and run-time system of the version of SETL maintained and distributed by the Courant Institute of Mathematical Sciences (CIMS) at New York University from the mid-1970s until the late 1980s." [Bacon 2000]

Documentation

Source code

SETL was not placed in the public domain (as was LITTLE); it was only distributed in binary form, under license. However it is now being made available for study and non-commercial use. This copy was provided by Stefan M. Freudenberger.

"I am reasonably sure that I also have the sun-m68k-bsd4.2 setl/little version, including source and binaries, and including the ltlasm that I wrote for m68k and that is modelled after the ibm s370 ltlasm that Richard Kenner wrote. These code generators generate target code directly, not via the high-level format that was initially used for the dec 10 port (known as t10), and later for the vax port (known as t32). I would have to check whether I have vax780-vms version also ... I have a box with tapes, one of which I had given to a commercial service to read as I certainly don’t have hardware to read these. I also have directory listings of most of these tapes so I’ll have to do some research to see what I have." [Stefan Freudenberger, personal communication, 19 March 2021]

SETL optimizer

"The SETL project produced, among other things, the SETL optimizer [Schwartz 1975, Freudenberger, Schwartz, and Sharir 1988; Dubinsky, Freudenberger, Schonberg, and Schwartz 1983], a 24,000-line prototype written in SETL. Unfortunately, on the machines of the day, it was too large to apply to itself. [Bacon 2000]

The SETL optimizer is "pass two and a half", running between the semantic pass and the code generator of the regular SETL compiler. It was written by Stefan M. Freudenberger, Art Grand, Jacob T. Schwartz, Micha Sharir, and Leonard Vanek. See [Newsletter 213].

Executable releases

Programs and specifications written in SETL

Dialects of SETL

SETL in the Soviet Union

Schwartz and other SETL project members visited A. P. Ershov's group in Novosibirsk several times during the 1970s. Ershov's group implemented a version of SETL on the BESM/6 computer using the EPSILON programming language.

"Ershov was a pioneer in the field of computing in the U.S.S.R. In the early 1960’s he did fundamental, ground-breaking work in the area of programming optimization while constructing an Algol compiler. He did this work on his own, in isolation, and independently came up with many of the key ideas that were then being discovered by Western scientists in the early 60’s.

His work became known in the West because of the writings of my colleague and thesis advisor at New York University, Jacob T. Schwartz.

My wife and I made our first trip to Russia in November, 1973, just weeks after the “Yom Kippur War.” We went as ordinary tourists to visit her many relatives. Both her parents were born in Russia, and her relatives there were then living in the Ukraine, in the cities of Kiev and Lvov. Many of them later emigrated to the U.S. We also went to Novosibirsk, Siberia, during our stay to visit Ershov.

Ershov was a member of the Soviet Academy of Sciences, a position in those days that gave its owner about the power and prestige of a U.S. Senator. He was one of the founders of Akademgorodok, a community based on education and research that was established in Siberia to provide a foothold for such work in Siberia, in the hopes it would speed Siberia’s development. [1] I believe he was a native of Siberia. It is similar in many ways to Los Alamos, New Mexico, in that respect.

[1] “Gorodok,” which means “small town,” was one of the first words I learned in Russian during the two years I studied Russian during my high-school years. A famous story by Lermontov begins with the words, “Taman yeset malenky gorodok … ” — “Taman is a small town …” [Dave Shields, 2006]

Setl-s

Setl-s was designed by Nigel P. Chapman at the University of Leeds, with guidance from Robert B. K. Dewar and contributions by Anthony McCann. A later port to MS-DOS was done by Julius J. VandeKopple at New York University, again with guidance from Dewar.

"The CIMS SETL system was quite slow and cumbersome, and LITTLE was not widely ported, so in the late 1970s Nigel Chapman, who was then a graduate student at the University of Leeds, designed and implemented a system called Setl-s [Chapman 1980]. It covers a substantial subset of SETL, leaving out only such ephemera as the macros, backtracking, the data representation sublanguage, support for separate compilation, and a few minor syntactic luxuries. The '-s' in the name can also stand for 'small', because Setl-s was a very compact system based on Dewar’s celebrated indirect threaded code [Dewar 1975] technique, and was written in MINIMAL, the portable assembly language in which the run-time system of MACRO SPITBOL [Dewar and McCann 1977] was implemented. Jay VandeKopple dropped the hyphen from Setl-s and worked on what was then called SETLS in the 1990s [Julius J. VandeKopple, private communication to David Bacon, 1999] while at NYU on sabbatical from Marymount College. " [Bacon 2000]

"I didn’t hear about Setl until I went up to Leeds for an interview in 1977, after I’d applied to do a PhD there. ...

Tony McCann at Leeds had worked with Robert Dewar on macro Spitbol. Dewar was part of the Setl team at NYU, and he had the idea of using indirect threaded code (ITC) to do for Setl what macro Spitbol had done for Snobol. Tony got involved and proposed to supervise a PhD student to work on the project. I thought it sounded interesting and in line with my interests, so I took it on.

It's ironic that an interest in high level languages led me to write thousands of lines of assembler. Being straight out of Cambridge, I was all for building the thing in BCPL, but Robert and Tony believed that you needed to be closer to the machine to get the benefit of ITC. The whole emphasis was to be on improved performance, so it had to be Minimal [the portable assembly language of Macro Spitbol].

...

The system was really Robert Dewar's baby. You've probably heard that Robert was something of a character, full of confidence and energy, also very bright. He breezed in and sketched out the implementation in a couple of afternoons then left us to it. I like to think that I made significant contributions later on, specially to the front end, but Setl-s is based on macro Spitbol.

Tony adapted the macro Spitbol garbage collector. He was adamant that the garbage collector had to come first. He also wrote the lexical analyzer to kick-start the development. I did all the rest.

The plan was to implement a subset of Setl, so naturally we started referring to it as subSetl. Dewar didn't like that, though – I guess he thought it made it sound inferior, or maybe he hoped to do the whole language one day. People were sticking letters on the end of language names to identify implementations, like Algol68C, so Tony came up with Setl-s. I never liked it, but it was just a name.

...

There was a guy called Dave Shields, who was our main contact at NYU. He worked on their Setl implementation as well as macro Spitbol. ..." [Nigel Chapman, personal communication, 21 June 2020]

Chapman completed version 1.9 in 1980. His Ph.D. thesis [Chapman 1980] uses SETL-S as an example of the techniques it describes. Later, Julius J. VandeKopple, working at New York University, adapted it for MS-DOS, and distributed versions through 2.2 in 1991.

Source code

Papers

SETL2

"SETL existed pretty much on machines which were falling out of favor. It was used on DEC VAX’s for most classes. There was an implementation for Motorola-based Sun Workstations and several on much larger machines. I don’t think there was ever a version for RISC machines. At any rate there was a project at NYC to develop a successor to SETL, funded by the Office of Naval Research. Jack was not around at the time as this was during his stint at DARPA. I got one of the RA positions on the project shortly after I started at NYU and was working on a SETL2 compiler under Matthew Smosna. We were writing a compiler front end in Ada. It didn’t go all that rapidly for a number of reasons, I think. I was pretty junior, there were still regular language design meetings so it was very much in flux, and I suspect Jack’s absence slowed things down. Frankly I mostly sat and listened in those meetings. Ed Schonberg would probably have more insightful comments. Fritz Henglein as well. Unfortunately those are the only two people that I remember being involved that haven’t passed away.

Anyway, the funding dried up. I was having fun with it so I started all over in C. At the time I didn’t have access to an Ada PC compiler and I preferred working on my own PC. With the design meetings over I didn’t have to worry about language changes any more, it was really just my own fun. When I had something feebly running I showed it to Matthew and he talked to some other people about it. Jack returned to NYU and became my advisor. There never was any funding for SETL2 but after I started working with Jack money never seemed to be a problem any more so I could spend time on it until it became pretty stable.

So I think you can kind of think of there being two SETL2’s, the official sponsored one which never got to the point where something ran, and mine that started out as skunkworks but became more accepted in the end."

[Kirk Snyder, personal communication, 14 May 2020]

Applications written in SETL2

ISETL

The ISETL language was designed and implemented by Gary Levin, based on Edward Dubinsky's experience using SETL to teach mathematics. Dubinsky and his colleagues used ISETL for a series of math textbooks.

"The main problematic features of SETL in 1985 were:

In summer 1985, I began conversations with Gary Levin about the possibility of an interactive version of SETL that would eliminate these problems and be more appropriate for educational uses. Discussions conntinued through the Fall and by January, 1986 we had agreed on specifications and Gary began to work on what would become (with the agreement of Jack Schwartz) ISETL. ... By Fall of 1988, ISETL version 1.0 was sufficiently stable that I could use it in courses on discrete mathematics and abstract algebra." [Dubinsky 1995]

"ISETL is an interactive version of SETL. It was inspired by Ed's desire to teach mathematics using manipulable objects. I stripped SETL down to the subset he needed and then added extra features (like first class functions) that I thought would be useful. The code owes nothing to the SETL implementation and is written in very basic C." [Gary Levin, personal communication, 12 May 2020]

Source code and executables

Documentation

Publications about ISETL

Publications using ISETL

Additional ISETL programs

Proteus (ISETL derivative)

The Proteus Project was "a collaborative effort by researchers at UNC Chapel Hill, Kestrel Institute, and Duke University to develop a system for the specification, prototyping, analysis and generation of parallel software." [Home page at cs.unc.edu]

The project included the Proteus language.

"I modified the ISETL interpreter to execute Proteus programs, but they were mostly ISETL with a few additional operations for task parallel and data parallel execution. I wrote some relatively large programs manipulating gravitational fields using Proteus.

ISETL was really a remarkable tool. It enabled so many concepts so easily. Two of my favorites were functions as expressions and pointwise function definitions.

I ran ISETL on a Sparc4 sun workstation. I had to get help from Gary as the compiler laid out structs differently and ISETL crashed. He fixed it quickly and we were off. I would run week long programs. 20 years later, I rebuilt ISETL on my Dell laptop. It was so much faster." [Lars Nyland, private communication, September 2021]

ISETL-LINDA (ISETL derivative)

ISETL-LINDA was part of the LINDA project at The University of York.

"ISETL-LINDA is an imperative interpreted language, built on top of Gary Levin's ISETL language. ISETL (Interactive SET Language) is novel, because it has as its major data structures sets and tuples.

We have embedded the LINDA primitives into ISETL. To do this, we introduced a type of bags, which represent tuple spaces, and templates, which are the counter-part of tuples." [ISETL-LINDA page at cs.york.ac.uk]

SETL in Europe: SED / SETL/E and ProSet / Cantor

SED

The Esprit-funded SED research project was led by Jean-Pierre Keller.

"SETL’s success as a prototyping tool spawned the Esprit SED (SETL Experimentation and Demonstration) project [Keller 1989] of the late 1980s, which was a sweeping effort to create a SETL-based prototyping environment complete with highly sophisticated language manipulation tools at the syntactic and semantic levels [Donzeau-Gouge et al. 1987]. This included a SETL-to-Ada translator [Doberkat and Gutenbeil 1987, Doberkat et al. 1989], an editor, a debugger, and a performance-profiling monitor [Bouzas et al. 1989]. The latter was rendered particularly accommodating and non-invasive by the use of coöperating processes sharing messages over TCP sockets. Abstract interpretation was the operative model in both the ambitious Tenenbaum-based [Tenenbaum 1974] type inferencer and Paige’s more general RAPTS [Paige 1986] transformational system (the predecessor to APTS), which was used to prototype “meta-SETL” [Aliffi et al. 1988], an AST-traversing interpreter. .... Interoperability was addressed in the SETL-to-Ada translator and in the performance monitor by means of ISLE (the Interface Specification Language and Environment), which was important for the SED project’s demonstration of rapid prototyping in SETL in a cartography application containing a package of computational geometry algorithms [Bistiolas et al. 1989].” [Bacon 2000]

Papers and reports about SED

SETL/E and ProSet

"Encouraged by SED’s contributions to the art of programming in the large and by the project’s inchoate plans for persistence in SETL, but disappointed by SED’s failure to arrive at a coherent product [Doberkat et al. 1992a], Ernst-Erich Doberkat proposed integrating persistent backing stores called P-files and their requisite namespace support into SETL/E [Doberkat 1990, Doberkat et al. 1990], a revision of SETL that was extended with a process creation operator and renamed ProSet [Doberkat et al. 1992b] to signify its role in prototyping. Doberkat’s interest in SETL during the 1980s [Doberkat et al. 1983, Doberkat 1985, Hyun and Doberkat 1985, Doberkat and Gutenbeil 1987, Doberkat and Fox 1989, Doberkat et al. 1989] grew in the 1990s into a more general interest in software engineering with set-oriented languages having intrinsic persistence features [Doberkat and Gutenbeil 1991, Doberkat and Sobottka 1991, Doberkat 1992, Doberkat et al. 1992a, Doberkat et al. 1992b, Doberkat et al. 1996] that sought to spare the programmer the trouble of coding data movement operations explicitly. Willi Hasselbring also showed how to translate [Hasselbring 1991a] a subset of SETL/E into Snyder’s SETL2. ProSet tuples are natural candidates for inter-process communication via Linda tuple spaces [Gelernter 1985], so Hasselbring has worked extensively throughout the 1990s on and with a methodology for prototyping concurrent applications using a hybrid system called ProSet-Linda [Hasselbring 1991b, Hasselbring 1992, Hasselbring 1993, Hasselbring 1994, Hasselbring and Fisher 1994, Hasselbring and Fisher 1995, Hasselbring et al. 1997, Hasselbring 1997b], and compared this approach to several others [Hasselbring 1997a, Hasselbring and Kröber 1998]." [Bacon 2000]

Cantor

"Jean-Pierre Keller, the leader of the SED project, went on to define a SETL descendant which he called Cantor [Keller 1991, Keller 1994]." [Bacon 2000]

"In its current version, Cantor has been derived from iSETL (by Gary Levin). Cantor has the usual collection of statements common to procedural languages, but a richer and simpler set of expressions" [Keller 1994, Volume 2, "Cantor short history"]

Keller used Cantor to write the NAP first-order logic proof checker [Keller and Paige 1994]. NAP was itself intended for use in proving properties of Cantor programs [Keller and Paige 1995].

GNU SETL

David Bacon designed and implemented another version of SETL at NYU in the 1990s.

Applications written in GNU SETL

SETL4

SETL4 is an implementation of SETL written by Dave Shields in Macro SPITBOL [Dewar and McCann 1977]. The name stands for the fact that it followed several implementations of SETL by the original project team.

SPITBOL is an implementation of SNOBOL4. The original version was designed by Robert B. K. Dewar and Ken Belcher in 1969, for the IBM System 360. Later Dewar and Anthony P. McCann of Leeds University created Minimal, a portable assembly language and then rewrote SPITBOL in Minimal, resulting in Macro SPITBOL.

Source code

See in particular the file setl4, which is the Spitbol source program.

SetlX

"setlX is an interpreter for the high level programming language SetlX (set language extended).

The most distinguishing feature of this language is the support it offers for sets and lists. As set theory is the language of mathematics, many mathematical algorithms that are formulated in terms of set theory have very straightforward implementations in SetlX.

Designed mostly by Karl Stroetmann, the SetlX language is an evolution of Setl by Jack Schwartz. It was specifically conceived to make the unique features of Setl more accessible to today's computer science students." [setlx.randoom.org]

Like SETL, SetlX is dynamically typed. It has a terse syntax based on C and Java. The language combines SETL's support for sets and tuples (called lists), and adds Prolog-like terms, support for functional programming, regular expressions, limited backtracking, object-oriented programming, vectors and matrices, several probability distributions, a plotting library, and a small set of graphical primitives. It is implemented in Java and is thus multiplatform; the implementation is called setlX.

Griffin

A follow-on rather than a dialect, Griffin was heavily influenced by the experience of using SETL.

"The Griffin [Dewar et al. 1992] language which was designed at New York University in the early 1990s was intended to be a general-purpose successor to SETL. Its goals were very lofty, and included what is surely the most comprehensive type and type inference system ever proposed. Griffin was supposed to give the programmer complete freedom of choice as to whether to code in a functional or an imperative style. It had language constructs for database-style transactions, namespaces, and persistence. Real-time facilities, Ada interoperability, exceptions, and broad support for concurrency were also built in at the language level. Much of Griffin has been implemented in a compiler, but a major obstacle to the completion of that enormous task has been the difficulty of fixing on a fully self-consistent language definition." [Bacon 2000]

"Griffin was a short-lived effort at language design, which was unusual in its attempt to combine ideas from various trends in language design, coming from SETL, LISP (via BALM, the language designed by Malcom Harrision), ML and Haskell and type inference (thanks to the participation of the late Paul Hudak who had been Ben Goldberg's thesis advisor at Yale). These different trends did not lead to a viable new language. but produced a number of extremely stimulating discussions among the participants!" [Ed Schonberg, private conversation, 5 October 2021]

Acknowledgments

This project would not have been possible without help from many people. Special thanks go to Annie Liu for coaxing me to begin this project in the spring of 2020, and to Nigel Williams, who had presciently started the search for artifacts back in 2013.

Appendices

Appendix 1: Early computer science work by Schwartz

"In the mid-1960s Jack began to devote his creative energies to the emerging field of computer science. In 1969 he founded the Computer Science Department at New York University under the umbrella of the Courant Institute of Mathematical sciences. He served as chair of the department until 1977. Jack’s directorship of the Information Science and Technology Office at the Defense Advanced Research Projects agency during his two-year leave (1987-1989) from NYU enabled him to seriously influence the direction of research in computer science in the United States." [Davis and Schonberg 2011]

Appendix 2: BALM

"The name BALM is actually an acronym (Block And List Manipulator) but is also intended to imply that its use should produce a soothing effect on the worried programmer. The system has the following features:

1. An Algol-like input language, which is translated into an intermediate language prior to execution.

2. Data-objects of type list, vector and string, with a simple external representation for reading and printing and with appropriate operations.

3. The provision for changing or extending the language by the addition of new prefix or infix operators, together with macros for specifying their translation into the intermediate language.

4. Availability of a batch version and a conversational version with basic file editing facilities.

The intermediate language is actually a form of LISP 1.5 which has been extended by the incorporation of new data-types corresponding to vector, string and entry-point. The interpreter is a somewhat smoother and more general version of the LISP 1.5 interpreter, using value-cells rather than an association-list for looking up bindings, and no distinction between functional and other bindings. The system is implemented in a mixture of Fortran (!) and MLISP, a machine-independent macro-language similar to LISP which is translated by a standard macro-assembler. New routines written in Fortran or MLISP can be added by the user, though if Fortran is used a certain amount of implementation knowledge is necessary." [Harrison 1970]

BALM Newsletters

These were similar to the SETL Newsletters, but focussed on the BALM language and its implementation. Some 20 were issued between 1971 and 1972; they are listed in Part 5 of [Abes 1973].

Appendix 3: LITTLE

Chapter 8 of Programming language and their compilers, "The self-compiling compiler", sketches how to port a self-compiling compiler to a new target machine via a bootstrapping process. To make the description more concrete, it presents a particular programming language as an appropriate vehicle for writing such a portable, self-compiling compiler. That language is called LITTLE.

"In defining this language, it is our intent to incorporate only that relatively minima1 set of essential features which are truly necessary in the convenient expression of compiler function." [Cocke and Schwartz 1970, page 649]

The language is similar to FORTRAN, but with one datatype, the bitstring. The report goes on to give a full syntax for LITTLE, as well as an overview of how its compiler would be organized.

A few years later Schwartz initiated the SETL project, and by 1971 it became clear that a more efficient implementation language than BALM was needed; work began on a serious implementation of LITTLE. Over the next decade, implementations of LITTLE were created for the CDC 6000, IBM System/370, Digital Equipment DECsystem-10, and Digital Equipment VAX-11/780. [Shields 1982]

LITTLE vs. C:

"... LITTLE was conceived by Jack before C was available. I remember Jack being favorably impressed by the design of C later on. Much of the low-level implementation work at NYU was influenced by the fact that the one available large machine was a CDC6000 with an awkward 60-bit word and no byte addressability, so that Jack saw machine-level programming as bit-vector manipulations (and 64-bit arithmetic). The SETL library had a large collection of operations on bit-vectors, but the 6600 (Cray's design) was really designed for numerical computations, and LITTLE was an awkward fit." [Ed Schonberg, personal communication, 13 October 2022]

LITTLE Newsletters

These were similar to the SETL Newsletters, but focussed on the LITTLE language and its implementation. Lists of the authors, titles, and dates are included in [Abes 1973] and [Abes 1980].

LITTLE Newsletter. Scans of Numbers 2-42A (constituting some 465 pages, with some gaps) were provided by David Bacon.

Documentation

Source code

Robert Abes, Edith Deak, Richard Kenner, David Shields, and Aaron Stein are the principal authors of the LITTLE compiler (LEX, GEN, LIB, and TST). LITTLE is in the public domain except [Shields 1982], which is Copyright © 1982 David Shields and is included here by permission from Shields. For a complete snapshot circa 1984, see the little directory of setl-vax-unix.tar.xz in the LITTLE-based SETL section.

In 1978 there was a collaboration with Anthony McCann and later Nigel Chapman (University of Leeds) on a plan to port LITTLE to the DEC PDP-10. It appears that Richard Kenner and David Shields ended up doing the bulk of the work but used a set of macros by Chapman to translate from the artificial targer t10 to valid MACRO-10 code -- see little/mk/ltlasm.opl for details. Chapman ended up developing Setl-s, using the MINIMAL language from MACRO SPITBOL by Dewar and McCann.

In 1980, Rob Pike at Bell Labs ported SETL from VAX/VMS to VAX UNIX. See comments in the source files little/mk/clib.c.bky, little/mk/clib.c.uts, little/mk/ltlt32.c, little/mk/LOG, little/clarkson/t32.c, and setl/bin/README.

"I do have a sometimes hilarious Bell Labs memo written by Rob Pike, as one of his very first jobs at BTL was to port the VAX implementation to Unix 32v, 32v was BTL's version of a paging Unix from VAX, though Berkeley of course won that battle." [Dave Shields, personal communication, 9 April 2020]

"I did the port because Doug McIlroy asked me to, and it was my job. ... I enjoyed the work and enjoyed my time meeting with people at NYU ... I did very much enjoy meeting Jack and Robert ... I had to port LITTLE first, to do SETL. " [Rob Pike, personal communication, 13 and 14 April 2020]

In addition to the .opl files below, there are .upd files with changes corresponding to some of them; see the .tar.xz file.

Appendix 4: Ada/Ed

Nigel Williams and Paul McJones (paul@mcjones.org), editors.

"Robert Dewar joined the NYU faculty in the mid-1970’s. He was a member of the Algol-68 committee, and among other things had created SPITBOL, a remarkably efficient implementation of SNOBOL, the pattern-matching language designed by Ralph Griswold. He immediately improved the perfomance of SETL and displayed an extraordinary talent for software design and language design. At the time Jack Schwartz was interested in developing techniques for Software Prototyping using very high-level languages, and the Department of Defense was in the process of looking for a common programming language for all the needs of the DoD. ... In any case, the design of Ada took several years, and the production of several requirement documents with the names Strawman, Stoneman, Ironman, and Steelman. This last one was the basis for an international competition for a new programming language, which became Ada83. To showcase the capabilities of SETL as a prototyping language, Jack and Robert got a grant from the US Army to create a prototype implementation of the new language. Robert wrote what was in essence an executable denotational definition of the language, including all of the concurrency model of the language, with tasks, entries, and rendez-vous as the basic synchronization constructs. I wrote a conventional semantic analyzer to perform static correctness checks (visibility, typing, overload resolution). The fact that this was an executable program meant that it could also be used early on to check the test suite being written at the sase time (by Softech, under the leadership of John Goodenough). Ada/Ed (which later became NYU/ADA) was extremely slow (we used to say that it was for the real-time simulation of paper-and-pencil calculations) but it was sufficient to execute the test suite (ACVC, or Ada Compiler Validation Capability) whose purpose was to ensure that all compilers were conformant to the language definition, ensuring the portability of Ada code. NYU/Ada ended up being the first officially validated implementation of the language (which was politically convenient for the DoD because it was not a commercial product).

NYU/Ada was used as a teaching tool for a few years, and served as a design model for a more efficient interpreter (written in C) and years later as the basis for the GNAT compiler. This was another demonstration project involving the next revision of the language, which became Ada95. This was a large addition and redesign of the language, and GNAT was intended to show the implementability of this new language, whose lead designer was Tucker Taft (then at Intermetrics). Like other languages with an ISO presence, there is an official maintenance committee (known as the ARG , or Ada Rapporteur Group) in charge of revising the standard periodically, and releasing new versions of the language. There have been such in 2005 and 2012, and a new one will be released early next year. Tucker Taft (now at Adacore) remains the chief designer and guide of the evolution of the language.

GNAT stands for “GNU-NYU Ada translator” indicating our close association with the Free Software community, and the use of the GNU code generator as the back-end of the compiler. (Internally the name was also understood to mean an irritant to developers of other commercial compilers for Ada)." [Ed Schonberg, personal communication, 1 April 2020]

Source code

See Version 1.4 below.

Papers and theses

Original NYU Ada/Ed Compiler, written in SETL

Version 19.7, of March 21, 1983
Version 1.4, validated June 28th, 1984

The source code of this version was published as a two-part NYU technical report. Staff at the Courant Institute scanned these reports for Nigel Williams in 2018.

Version 1.10, 1989

This version was validated on a Sun-3/60 in 1989:

Version 1.10 was distributed through the National Technical Information Service for VAX computers running VMS Version 5.2 and UNIX (version unknown). Here are reports describing the availability of distribution tapes:

NYU Ada/Ed-C

Ada/Ed-C was a rewrite from SETL to C, for Unix-based machines. This paper describes the design process:

NYUADA project. Ada/Ed-C version 1.11.0a, 1992

Version 11.11.0a could be built for various Unix systems; see #ifdefs in config.h.

NYUADA project. Ada/Ed-C system version 1.11.2, September 30, 1992

Version 1.11.2, as released by the NYUADA project, could be built for the following targets:

Source code

"The sources for NYU Ada/ED Version 1.11.2, obtained from http://www2.informatik.uni-stuttgart.de/iste/ps/ada-software/html/dos\_ada.html on 9 July 2012.

NYU Ada/Ed was the first Ada compiler to pass the Ada Compiler Validation Suite. Ada/ED for the IBM PC was the first compiler to pass the suite on an IBM PC.

I initiated the project in late 1983, after finishing my PhD disseration. I worked on it until mid 1987, until I left NYU's Courant Institute of Mathematical Sciences (CIMS) to join IBM Research."

In addition, the GW-Ada/Ed project at The George Washington University, led by Professor Michael B. Feldman, produced the GW-Ada/Ed Program Development Environment for Macintosh and MS-DOS that extenderd the Ada/Ed interpreter with an editor and a "shell" to control compiling, binding and execution of an Ada program.

NYU Ada/Ed-SETL2

In the late 1980s, W. Kirk Snyder designed and implemented a successor to SETL called SETL2. A version of the original Ada/Ed was modified for SETL2. Mentioned in [Bacon 2000], page 21.

THE END

« April 2025 »
Su Mo Tu We Th Fr Sa
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30