Personal tools
You are here: Home Projects SETL
Document Actions

SETL Historical Sources Archive

by Paul McJones last modified 2021-03-04 10:04

A collection of artifacts from the SETL programming language, which was designed by Jack Schwartz and his colleagues 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 additional materials 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 [Cocke and Schwartz 1970].

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]

  • Martin Davis and Edmond Schonberg. Jacob Theodore Schwartz 1930-2009: A Biographical Memoir. National Academy of Science, 2011. nasonline.org

"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 1969, 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

  • Jacob T. Schwartz. Set Theory as a Language for Program Specification and Programming. Courant Institute of Mathematical Sciences, IBM Research and New York University, 1969-1970.
  • Jacob T. Schwartz. Abstract Algorithms and a Set Theoretic Language for Their Expression. Computer Science Department, Courant Institute of Mathematical Sciences, New York University, Preliminary draft, 1971.
  • Jacob T. Schwartz. On Programming: An Interim Report on the SETL Project. Installment 1: Generalities; Installment 2: The SETL Language, and Examples of Its Use. Computer Science Department, Courant Institute of Mathematical Sciences, New York University, revised June 1975. PDF with bookmarks in Adobe Reader] osti.gov

    Installment 1 was published in January 1973 and Installment 2 was published in October 1973. Installment 3, never published, was to be titled "Extended Facilities of the SETL Language". The June 1975 edition includes the first two installments, renamed parts I and II.

  • Henry Mullish and Max Goldstein. A SETLB primer: a step-by-step tutorial with over 100 illustrative programettes. Courant Institute of Mathematical Sciences, NewYork University, June 1973, 201 pages.

    "Unfortunately, however, the only 'language manuals' were A SETLB Primer, a well-intended document that hid the beauty of the language (actually, a subset thereof) behind the ugly face of the IBM 029 keypunch and its extraordinary mapping to the character set of a 63-character CDC line printer, and Schwartz’s own 675-page On Programming, a compilation of philosophical musings, language definitions, algorithms, and implementation details which, though impressive in the best sense of the word, presented a formidable front to the novice programmer." [from a review of Dewar 1979 by Scott Hurd]

  • Kurt Maly. A Study in Programming Techniques. Ph.D. thesis, Department of Computer Science, Courant Institute of Mathematical Sciences, New York University, February 1973.
  • H. S. Warren, Jr. ASL, a proposed variant of SETL (preliminary). Courant Computer Science Report # 1, Computerr Science Department, New York University, May 1973. PDF / archive.org
  • Robert Abes, editor. SETL Master Catalog: A Comprehensive Listing of Reports, Working Papers, and Computer Readable Document and Program Files Pertaining to Work at New York University on the SETL Set-Theoretic Programming Language. Report IMM 396, Computer Science Department, CIMS, October 1973. PDF / archive.org
  • Aron M. Tenenbaum. Type determination for very high level languages. Courant Computer Science Report # 3, Computer Science Department, New York University, October 1974. PDF / archive.org
  • Progress Report No. 54, October 1, 1977 to September 30, 1978. Courant Mathematics and Computing Laboratory, New York University, December 1, 1978. PDF / osti.gov

    Page 22: "Since April intensive debugging of the run-time library has been in progress. For this purpose, a comprehensive set of test programs has been designed·and is currently being implemented. We intend to create an industrial grade library of standard test programs which will satisfy the following requirements: first, the library has to be modular so that additional tests can easily be added to it, and furthermore it must allow full or partial execution of all modules; second, each test has to check its results automatically, as much as possible, since the projected size of the test library makes it prohobitive to check the results manually.

    The overall design of the test library has been completed, and much of it has been implemented with some changes still to be made to include existing stand-alone tests into the library.

    Some preliminary effort aimed at installing SETL on the IBM 370 has been undertaken. A first attempt to run part of the compiler has been made; it pointed out some necessary changes both to the IBM LITTLE implementation and to the SETL source code. at this time. Most of these changes have been made on the SETL source."

    S. M. Freudenberger

  • Robert B. K. Dewar. The SETL Programming Language. 1979. Posted by permission of Jenny Dewar. PDF
  • J.T. Schwartz and M. Sharir. A Design for Optimizations of the Bitvectoring Class. NYU Courant Computer Science Report No. 17, September 1979. PDF / archive.org
  • Ssu-cheng Liu and Robert Paige. Data structure choice/formal differentiation : Two papers on very high level program optimization. Courant Computer Science Report #15, New York University, September 1979. PDF / archive.org

    Combines SETL-related Ph.D. theses of Liu and Paige.

  • R. B. K. Dewar E. Schonberg and J. T. Schwartz. Higher Level Programming: Introduction to the use of the Set-Theoretic programming language SETL. Courant Institute of Mathematical Sciences, Computer Science Department, New York University. Preliminary Trial Edition - Summer 1981. Gift of Jean-Pierre Rosen. Posted by permission of Ed Schonberg. PDF
  • See [Schonberg and Shields 1985].
  • Lynwood David Shields. Measuring SETL performance. Ph. D. thesis, New York University, Graduate School of Arts and Science, 1983.
  • Gerald Weiss. Recursive data types in SETL: automatic determination, data language description, and efficient implementation. Technical Report Number 201, Courant Institute of Mathematical Sciences, New York University, March 1986. PDF / archive.org
  • Gerald Weiss and Edmond Schonberg. Typefinding Recursive Structures: A Data-Flow Analysis in the Presence of Infinite Type Sets. Technical Report Number 235, Courant Institute of Mathematical Sciences, New York University, August 1986. PDF / archive.org

 

SETL Newsletters

"A series, currently at No. 82 [as of 1973], of miscellaneous studies and working papers growing out of the overall project. This series has appeared under the name 'SETL Newsletter'." [Schwartz 1973]

  • NYU SETL Project. SETL Newsletters. Numbers 1–234, Courant Institute of Mathematical Sciences, New York University, 1970–1981 and 1985–1989. From [Bacon 2000].
  • M. C. Harrison. BALM-SETL: A simple implementation of SETL. SETL Newsletter, Number 1, November 1970.
  • David Shields. BALMSETL user’s guide (in brief). SETL Newsletter, Number. 20, March 1971.
  • H. S. Warren, Jr. SETL implementation and optimization: A first look at SETL compilation—target code style. SETL Newsletter, Number 53, September 1971. A revision appears in On Programming: An Interim Report on the SETL Project, pages 54–68. PDF
  • J. Schwartz, S. Brown, and E. Schonberg. SETLA user’s manual. SETL Newsletter, Number. 70, February 1972. A revision of 1 August 1974 appears in On Programming: An Interim Report on the SETL Project, pages 90–159. PDF
  • J. T. Schwartz and M. Sharir. Tarjan's fast interval finding algorithm. SETL Newsletter, Number 204. 3 March 1978. PDF
  • Matthew Smosna. The Implementation of SETL-2—An Experiment in the Use of Ada as an Implementation Language. SETL Newsletter, Number226, New York University, June 1988.

 

Publications

  • J. T. Schwartz. Automatic and semiautomatic optimization of SETL. In Proceedings of the ACM SIGPLAN symposium on Very high level languages. Association for Computing Machinery, New York, NY, USA, March 1974, pages 43–49. ACM Digital Library
  • Aaron M. Tenenbaum.Compile time type determination in SETL. In Proceedings of the 1974 annual conference - Volume 1 (ACM '74). Association for Computing Machinery, New York, NY, USA, 95–100. ACM Digital Library
  • K. Kennedy and J. Schwartz. An introduction to the set theoretical language SETL. Computers & Mathematics with Applications, Volume 1, Number 1, January 1975, pages 97-119. Science Direct open access
  • J. T. Schwartz. Automatic data structure choice in a language of very high level. In Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages (POPL '75). Association for Computing Machinery, New York, NY, USA, pages 36–40. ACM Digital Library
  • J. T. Schwartz. Automatic data structure choice in a language of very high level. Commun. ACM Volume 18, Number 12 (Dec. 1975), pages 722–728. ACM Digital Library
  • Edmond Schonberg, Jacob T. Schwartz, and Micha Sharir. Automatic data structure selection in SETL. In Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages (POPL '79). Association for Computing Machinery, New York, NY, USA, 197–210. ACM Digital Library
  • Robert B. K. Dewar, Arthur Grand, Ssu-Cheng Liu, Jacob T. Schwartz, and Edmond Schonberg. 1979. Programming by Refinement, as Exemplified by the SETL Representation Sublanguage. ACM Trans. Program. Lang. Syst. Volume 1, Number 1 (July 1979), pages 27–49. ACM Digital Library
  • Robert B.K. Dewar and Edmond Schonberg. The elements of SETL style. In Proceedings of the 1979 annual conference (ACM '79). Association for Computing Machinery, New York, NY, USA, pages 24–32. ACM Digital Library
  • Edmond Schonberg. 1979. Hierarchical design and efficient implementation in SETL: a case study. SIGPLAN Not. 14, 10 (October 1979), pages 69–74. ACM Digital Library
  • Edmond Schonberg, Jacob T. Schwartz, and Micha Sharir. An Automatic Technique for Selection of Data Representations in SETL Programs. ACM Trans. Program. Lang. Syst.. Volume 3, Number 2 (April 1981), pages 126–143. ACM Digital Library
  • Jack Schwartz. SETL—a very high level language oriented to software systems prototyping. Abstract only. In Proceedings of the international conference on APL (APL '81). Association for Computing Machinery, New York, NY, USA, 280. ACM Digital Library
  • Stefan M. Freudenberger, Jacob T. Schwartz, and Micha Sharir. Experience with the SETL Optimizer. ACM Trans. Program. Lang. Syst. 5, 1 (Jan. 1983), 26–45. ACM Digital Library
  • E. E. Doberkat, E. Dubinsky, and J. T. Schwartz. Reusability of Design for Complex Programs: an Experiment with the SETL Optimizer. In: Proc. IT & T Workshop on Reusability of Software, Providence, RI, 1983, pages 106–108.
  • Jacob T. Schwartz, R. B. K. Dewar, E. Dubinsky, and E. Schonberg. Programming With Sets: An Introduction to SETL. Springer-Verlag, 1986. Springer
  • E. Dubinsky, S. Freudenberger, E. Schonberg, and J. T. Schwartz. 1989. Reusability of design for large software systems: and experiment with the SETL optimizer. Software reusability: vol. 1, concepts and models. Association for Computing Machinery, New York, NY, USA, pages 275–293.

 

Implementations

 

BALM-based SETL: SETLB and SETLA

Around the time Schwartz began thinking about SETL, his NYU colleague Malcolm Harrison designed a language called BALM:

  • Malcolm C. Harrison. BALM - An Extendable List-processing Language. Report NYO-1480-118, AEC Computing and Applied Mathematics Center, Courant Institute of Mathematical Sciences, New York University, June 1969. PDF / archive.org
  • Malcolm C. Harrison. A language-oriented instruction set for the BALM language. In: Proceedings of the meeting on SIGPLAN/SIGMICRO interface. Association for Computing Machinery, New York, NY, USA, 161–168. ACM Digital Library

BALM 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. A detailed description of SETL can be found in "On Programming - Vols. I and II. 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]

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]

  • Stefan M. Freudenberger, Art Grand, Jacob T. Schwartz, Micha Sharir, Leonard Vanek. SETL optimizer. Source code, written in SETL. Given to Annie Liu by Jack Schwartz on 4 February 2009.

Executable releases

  • SETL V30(?) for VAX VMS V3. Image of distribution tape of VAX SETL, circa 1982 (executables and documentation). Compressed archive

    Nigel Williams was given this tape by Jean-Pierre Rosen in Paris who, as a post-doc at NYU contributing to the Ada/Ed project, brought the tape home afterward. Nigel arranged to have it sent to Dennis Boone at Michigan State University, who was able to recover its contents.

    • David Shields and Stephen Tihor. Installation of SETL V26 for VAX VMS V3. 6 September 1982. INSTALL.doc
    • David Shields. SETL User Manual. Version 30, 24 July 1984. USER.doc
    • Availability, bibliography, and usage agreements. CATALOG.doc

 

Applications written in SETL

  • See SETL Optimizer.
  • See Ada/Ed, a translator-interpreter for Ada 83: the first version was written in SETL (two-part NYU technical report).
  • RAPTS (Rutgers Abstract Program Transformation System).
    • Robert Paige. Transformational programming: applications to algorithms and systems. In Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages (POPL '83). Association for Computing Machinery, New York, NY, USA, 73–87. ACM Digital Library
  • Griffin ...

 

Dialects of SETL

 

Siberian SETL

Jack Schwartz visited A. P. Ershov's group in Novosibirsk several times during the 1970s, which implemented a version of SETL on the BESM-6 computer using the EPSILON programming language.

  • Jacob T. Schwartz. Notes on the design of SETL. The Ershov Archive for the History of Computing, Folder 196, List 48, December 1972. PDF / Online at ershov.iis.nsk.su
  • D. Y. Levin. Experimental implementation of SETL. In: Ershov A., Koster C.H.A. (eds) Methods of Algorithmic Language Implementation. Lecture Notes in Computer Science, vol 47. Springer, Berlin, Heidelberg, 1977. SpringerLink

 

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 [VandeKopple 1999] while at NYU on sabbatical from Marymount College. " [Bacon 2000]

  • Robert B.K. Dewar. Indirect threaded code. Communications of the ACM, Volume 18, Number 6, pages330–331, June 1975. ACM Digital Library
  • R.B.K. Dewar and A.P. McCann. MACRO SPITBOL—a SNOBOL4 compiler. Software Practice and Experience, Volume 7, pages 95–113, 1977. Wiley Online Library
  • Nigel P. Chapman. Theory and practice in the construction of efficient interpreters. University of Leeds, 1980.
  • Julius J. VandeKopple. Private communication to David Bacon, 1999.

"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

  • Nigel Chapman and Julius J.VandeKopple. Source code for Setl-s, also known a SETLS. Github repository

    Includes the main source file for SETL-S, which is written in MINIMAL, and also includes the files distributed for version 2.2 on October 6, 1991 running on MS-DOS.

    To run the MS-DOS version of SETLS from the browser, vist this page:

    https://virtualconsoles.com/online-emulators/dos/
    and drag DISTR-ZIP.zip to the blue area on the web page, then press the blue Start button at the bottom. You’ll soon have a C:\> prompt; type “cd distr” to enter the directory, then type “setls fact” to run the factorial example, followed by two carriage returns to accept the default filenames for listing and executable. There’s DVED from Robert Dewar in this same directory if you want to write a new program.

Papers

  • Robert B. K. Dewar; Anthony P. McCann. MINIMAL - A Machine Independent Assembly Language. Technical Report Number 12, Computer Science Department, Courant Institute of Mathematical Sciences, 1979.

 

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]
  • See [Smosna 1988].
  • W. Kirk Snyder. The SETL2 Programming Language. Technical Report 490, Courant Institute of Mathematical Sciences, New York University, September 9, 1990. Gift of W. Kirk Snyder. PDF
  • W. Kirk Snyder. The SETL2 Programming Language: Update On Current Developments. Courant Institute of Mathematical Sciences, New York University, September 7, 1990. Gift of W. Kirk Snyder. PDF
  • Robert Hummel. A Gentle Introduction to the SETL2 Programming Language. 1991? Modified from [Dewar 1979]. Gift of W. Kirk Snyder. PDF
  • W. Kirk Snyder. SETL2 source code. This version provided by Salvatore Paxia, and includes additions by him. Posted here by permission of Snyder and Paxia. .tgz
  • ]W. Kirk Snyder.] Guide to SETL2 Installation. .txt
  • W. Kirk Snyder. SETL2 man page. .txt

TO DO: Add the SETL2 version of Programming in SETL that is available at http://www.settheory.com/ in draft form.

Applications using SETL2

  • See [Ada/Ed], a translator-interpreter for Ada 83 (two-part NYU technical report): the third version was written in SETL2.
  • Robert Paige. Analysis and Transformation of Set-Theoretic Languages. First of four topics for Honors Programming Languages (G22.3110), Fall 1997, Courant Institute, New York University. Online at cs.nyu.edu

    "This minicourse will use SETL2 as a vehicle for showing how types and transformations can be used to integrate algorithm design and analysis, program development, and high level compilation of set theoretic programming languages. There are four lectures, each lasting two hours. Several References may be found here."

  • Jack Schwartz. Big strings and database implementation in SETL. Given to Annie Liu on 4 February 2009. .zip
    • atkw_class_w_test.stl. "Syntactic and semantic conventions for the SETL widget class", with test.
    • DB_bs_wdoc.stl. "Specialized big string for storing word occurence lists", with test.
    • DB_btree_bigs.stl. "B-tree variant for big_strings, with use of disk_records, cumulants in parent, refcounts", with test.
    • DB_btree_dbix.stl. "B-tree variant for database index, 2 cumulants (cumulated record size, last rec. id), refcounts", with test.
    • DB_btree_wdix.stl. "B-tree variant for word index, with 2 cumulants (no. of occs, last wd. in parent), refcounts", with test.
    • DB_btree_wdoc.stl. "B-tree variant for word occurence_strings, with 2 cumulants in parent, refcounts", with test.
    • DB_byteutil.stl. Byte string and integer conversion functions.
    • DB_database.stl. The main big strings and database implementation, with test.
    • DB_records.stl. "Fourth disk record variant, allowing cumulants to be kept in parents", with test.
  • E. G. Omodeo, D. Cantone, A. Policriti, and J. T. Schwartz. AEtnaNova/Referee proof assistant. Gift of Eugenio Omodeo.
    • Source code, documentatation, etc. .zip
    • E. G. Omodeo, D. Cantone, A. Policriti, J. T. Schwartz. A computerized Referee. In O. Stock and M. Schaerf (Eds.), Aiello Festschrift, LNAI, vol. 4155, Springer, pages 114–136, 2006. SpringerLink

 

GNU SETL

David Bacon designed and implemented another version of SETL at NYU in the 1990s. He calls it "GNU SETL", but so far he has not published its source.

  • David Bacon. SETL for Internet Data Processing. Ph.D. thesis, Computer Science Department, New York University, January, 2000. PDF at cs.nyu.edu / website

    The section "A Brief History of SETL" and the Bibliography have been quite useful in preparing this web site.

Applications written in GNU SETL

  • Anonymous. SETLisp. "A Small implementation of Common Lisp written in SETL. Additional SETL features are added including the concept of a set-expression."
    • Anonymous. "(A ((Pretty OK) Lisp) Interpreter {in SETL})". Post, Neural Outlet blog, 7 May 2017. wordpress.com
    • Anonymous. Source repository. bitbucket.org
  • Hakan Kjellerstrand. SETL - The SET Programming Language. Post, Arrays in Flux blog, 27 April 2010. Many GNU SETL example programs. hakank.org

 

ISETL

The ISETL language was designed and implemented by Gary Levin, based on SETL. Edward Dubinsky and his colleagues used it for a series of math textbooks.

"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]

  • Gary Marc Levin. An Introduction to ISETL. Department of Math and Computer Science, Clarkson University. This was included when people ordered copies of ISETL at the time of [Baxter et al. 1989]. PDF / original .TEX
  • Gary Marc Levin. ISETL: a language for teaching discrete mathematics (abstract). In Proceedings of the 1990 ACM annual conference on Cooperation (CSC ’90). Association for Computing Machinery, New York, NY, USA, 455. ACM Digital Library
  • Nancy Baxter, Ed Dubinsky, and Gary Levin. Learning Discrete Mathematics With ISETL. Springer-Verlag, 1989.
  • William E. FentonEd Dubinsky. Introduction to Discrete Mathematics with ISETL. Springer, 1996. SpringerLink
  • I. Arnon, J. Cottrill, E. Dubinsky, A. Oktaç, S. Roa Fuentes, M. Trigueros, K. Weller. APOS Theory: A Framework for Research and Curriculum Developmentin Mathematics Education, Springer, 2014. Springer

Source code

TO DO:

  • Investigate Proteus
  • Look for ISETLJ (Window port using Java).
  • Investigate Cantor by Yo Keller (built on ISETL?) [Omedeo, personal communication, 18 August 2020]

 

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

 

TO DO

  • Extend the bibliography for SETL, including published papers, Ph.D. theses, and internal reports.
  • Add a timeline.
  • Add ISETL example programs and executable versions found on Internet.
  • Add SED (SETL Experimentation and Demonstration) (led by Jean-Pierre Keller) (ESPRIT) (see [Bacon 2000]).
  • Add work by Doberkat and his colleagues (see [Bacon 2000]), e.g.:
    • ProSet
    • E. Doberkat, U. Gutenbeil, W. Hasselbring. SETL/E Sprachbeschreibung. Technical Report Number 01-90, Universiät Essen, Version 0.1, March 1990.
    • E. Doberkat. A Proposal for Integrating Persistence into the Prototyping Language SETL/E. Technical Report Number 02-90, Universität Essen, April 1990.
    • W. Hasselbring. Translating a Subset of SETL/E into SETL2 Technical Report Number 02-91, Universität Essen, January 1991.
  • Consider Java-based SetlX?

 

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.

  • David Bacon
  • Dennis Boone
  • Peter Capek
  • Ernst-Erich Doberkat
  • Edward Dubinsky
  • Stefan M. Freudenberger
  • Fritz Henglein
  • Richard Kenner
  • Philippe Kruchten
  • Gary Marc Levin
  • Annie Liu
  • Kurt Maly
  • Elie Milgrom
  • Eugenio Omodeo
  • Salvatore Paxia
  • Rob Pike
  • Diana Robinson
  • Jean-Pierre Rosen
  • Edward Schonberg
  • Micha Sharir
  • David Shields
  • W. Kirk Snyder
  • Nigel Williams
  • Denis Zorin

 

Appendices

 

Appendix 1: 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

  • Robert B. K. Dewar, Gerald A. Fisher, Edmond Schonberg, Robert Froehlich, Stephen Bryant, Clinton F. Goss, and Michael Burke. The NYU Ada translator and interpreter. In Proceedings of the ACM-SIGPLAN symposium on Ada programming language (SIGPLAN '80). Association for Computing Machinery, New York, NY, USA, 194–201. ACM Digital Library

    Abstract: "The NYU-Ada project is engaged in the design and implementation of a translator-interpreter for the Ada language. The objectives of this project are twofold: a) to provide an executable semantic model for the full Ada language, that can be used for teaching, and serve as a starting point for the design of an efficient Ada compiler; b) to serve as a testing ground for the software methodology that has emerged from our experience with the very-high level language SETL. In accordance with these objectives, the NYU-Ada system is written in a particularly high-level, abstract SETL style that emphasizes clarity of design and user interface over speed and efficiency. A number of unusual design features of the translator and interpreter follow from this emphasis. Some of these features are described below. We also discuss the question of semantic specification of programming languages, and the general methodology of 'Software Prototyping' of which the NYU-Ada system is a sizeable example."

  • Philippe Kruchten and Edmond Schonberg. The ADA/ED System: A Large-Scale Experiment in Software Prototyping Using SETL. Pages 398-515 in: Budde R., Kuhlenkamp K., Mathiassen L., Züllighoven H. (eds) Approaches to Prototyping. Springer, Berlin, Heidelberg, 1984. SpringerLink
  • Heinrich P. Godbersen. Comments on "The Ada/Ed System: A Large-Scale Experiment in Software Prototyping Using SETL" by P. Kruchten and E. Schonberg. Pages 416-417 in Budde R., Kuhlenkamp K., Mathiassen L., Züllighoven H. (eds) Approaches to Prototyping. Springer, Berlin, Heidelberg, 1984. SpringerLink
  • Peter Schnupp. Comments on "The ADA/ED System: A Large-Scale Experiment in Software Prototyping Using SETL" by P. Kruchten and E. Schonberg. Pages 418-423 in Budde R., Kuhlenkamp K., Mathiassen L., Züllighoven H. (eds) Approaches to Prototyping. Springer, Berlin, Heidelberg, 1984. SpringerLink
  • Philippe Kruchten, Edmond Schonberg, and Jacob Schwartz. Software prototyping using the SETL programming language. IEEE Software, Volume 1, Number 4, pages 66–75, October 1984. IEEE Xplore
  • J.-P. Rosen. SETL: Un langage de très haut niveau pour le prototypage. Presented in the workshop Journées d'étude AFCET Nouveaux langages pour le génie logiciel; published in BIGRE+GLOBULE. Number 45, October 1985. PDF
  • Philippe Kruchten. Une machine Ada virtuelle : Architecture. Ph.D. thesis, École National Supérieure des Télécommunications, 2 Octobre 1986. PDF
  • Jean-Pierre Rosen. Une machine virtuelle pour Ada: Le système d'exploitation. Ph.D. thesis, École National Supérieure des Télécommunications, 2 Octobre 1986. PDF

Original NYU Ada/Ed Compiler, written in SETL

 

Version 19.7, of March 21, 1983
  • SofTech, Inc, Ada Compiler Validation Summary Report: NYU Ada/ED, Version 19.7. V-001, April 11, 1983. PDF at dtic.mil

    The New York University Ada translator (NYU Ada/Ed) version 19.7 (March 21, 1983), was tested with version 1.1 (March 4, 1983) of the ACVC validation tests. 1.1 of the test suite contained 1,633 tests, of which 1,325 were applicable to Version NYU Ada/Ed. Of the applicable tests, 14 were withdrawn, due to errors in the tests. NYU Ada/Ed passed all of the remaining 1,311 applicable correct tests.

 

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.

  • Ada Project. ADASEM: Static Semantics for Ada. Listing of the NYU Ada/Ed compiler, Version 1.4, validated June 28, 1984. Courant Institute, New York University, July 3, 1984. PDF
  • Ada Project. Ada/Ed INTERPRETER: Executable semantic model for Ada. Listing of the NYU Ada/Ed compiler, Version 1.4, validated June 28, 1984. Courant Institute, New York, July 3, 1984. University. PDF

 

Version 1.10, 1989

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

  • Wright-Patterson AFB. Ada Compiler Validation Summary Report: New York NYU Ada/Ed, Version 1.10, Sun-3/60 (Host & Target), 890523W1.10085. May 22, 1989. Online at apps.dtic.mil

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:

  • Stephen P. Wilson. Ada/Ed Compiler, Version 1.10(VAX). Aeronautical Systems Division, Wright-Patterson AFB, Ohio, January 29, 1990. Online at dtic.mil
  • Stephen P. Wilson. Ada/Ed Compiler, Version 1.10(UNIX). Aeronautical Systems Division, Wright-Patterson AFB, Ohio, January 29, 1990. Online at dtic.mil

NYU Ada/Ed-C

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

  • E. Schonberg and D. Shields. From prototype to efficient implementation: A case study using SETL and C. Technical Report 170, Courant Institute of Mathematical Sciences, New York University, July 1985. PDF / archive.org

 

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.

  • NYU Ada project, version 11.11.0a source. February 7, 1992. .zip / .tar.gz and README online at ftp.nice.ch
  • Ragnar Hojland. Full sources, with "a couple of tweaks" for Linux 2.2 glibc2. Hojland changed the version number to 1.12. .zip / .tar.gz at ibiblio.org / [mirror](RAW/www.ibiblio.org/pub/Linux/devel/lang/ada/Adaed-1.12.tar.gz)
  • Rolf Ebert. Linux executables and libraries, and a file of diffs to adapt the sources to Linux, circa 1992. Ebert is acknowledged in the release.notes file of version 1.11.2 as having contributed patches. .zip / adaed.README and adaed.tar.z at ibiblio.org
  • Dylan Kucera. Amiga executables and libraries, with only modified source files, circa 1993. Kucera changed the version number to 1.11.0b. .zip / Online at aminet.net
  • Eric Baigar. SGI Irix port. MIPS executables in SGI tardist format. tardist / Online at baigar.de

 

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:

  • Silicon Graphics IRIS running IRIX
  • Sun3 running SunOS
  • Sun Sparcstation running SunOS
  • RS6000/AIX
  • Decstation running ULTRIX
  • VAX running BSD 4.3 UNIX
  • 386/DOS machines (with at least 2 megabytes of RAM
Source code
  • Dave Shields. Source repository. github.com/daveshields/AdaEd
  • "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.

  • NYUADA and GWUADA projects. Ada/Ed 1.11.2 source code and executables for PC and Macintosh. 1992-1995.
    • .zip

      The nyu directory contains the original nyu/Adaed-1.11.2/) and copies (nyu/src/) apparently only differing by some renaming to produce shorter filenames. The gwu directory contains subdirectories for DOS (gwu/dos/) and Macintosh (gwu/mac/); within the Macintosh subdirectory there are several copies of most source files for unknown reasons.

    • The Public Ada Library, Walnut Creek CD-ROM, November 1997. Two ISO images at archive.org
  • Michael B. Feldman, Charles W. Kann, Arthur Vargas Lopes, and Manuel A. Pérez-Quiñones. GW-Ada/Ed: free Ada 83 development environments for IBM PC-compatible and Apple Macintosh computers. In Proceedings of the conference on TRI-Ada ’95: Ada’s role in global markets: solutions for a changing complex world (TRI-Ada ’95). Association for Computing Machinery, New York, NY, USA, 446–454. ACM Digital Library

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.

 

Appendix 2: 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]

  • Judith Glasner, Stanley Ocken, David Rosenberg, Jack Schwartz, George Shapiro and Alan Silverman. The Nu-Speak System. Report NYO-1480-9, Courant Institute of Mathematical Sciences, New York University, November 1964. PDF / archive.org

    "I wasn't present at the time, but a mutual colleague said roughly: Jack went home one weekend with a 7090 manual and came back on Monday having written NU SPEAK [an early list processing language]." [Peter Capek, personal commumication, 21 May 2020]

  • J. Schwartz. 1966. Large Parallel Computers. Journal of the ACM, Volume 13, Number 1 (Jan. 1966), pages 25–32. ACM Digital Library
  • J. T. Schwartz, editor. Mathematical Aspects of Computer Science. Proceedings of Symposia in Applied Mathematics, Volume XIX, American Mathematical Society, 1967. ams.org
  • M. C. Harrison and J. T. Schwartz. SHARER, a Time Sharing System for the CDC 6600. Communications of the ACM, Vol. 10, No. 10, October 1967, pages 659-665. ACM Digital Library
  • John Cocke and Jacob T. Schwartz. Programming Languages and Their Compilers. Preliminary Notes. 1968-1969; second revised version, Apri1 1970. Courant Institute of Mathematical Sciences, New York University. PDF
« March 2021 »
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 31
 

Powered by Plone CMS, the Open Source Content Management System

This site conforms to the following standards: