Personal tools
You are here: Home Projects SETL
Document Actions

SETL Historical Sources Archive

by Paul McJones last modified 2021-09-19 17: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 materials (which will all 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]

  • 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, 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

  • Jacob T. Schwartz. Set theory as a language for program specification and programming. Courant Institute of Mathematical Sciences, September 1970, 97 pages. [Abes 1973] lists this in part 4.
  • Jacob T. Schwartz. Abstract algorithms and a set theoretic language for their expression. Computer Science Department, Courant Institute of Mathematical Sciences, New York University, December 1970, 298 pages. [Abes 1973] lists this in part 4, and notes it as "The 'SETL manuscript'."

    Newsletter 101 says "This is the basic reference work on SETL. It includes a discussion of programming principles, details concerning the design of the language, and a variety of algorithms written up in SETL."

  • 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, 1973; 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 Number 1, Computer 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
  • Aaron 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
  • Peter Markstein. Operating System Specification Using Very High Level Dictions. Ph.D. thesis, New York University, June 1975. Scan provided by Peter Markstein. PDF at cs.nyu.edu / PDF
  • Philip Sidell Shaw. Gyve, a programming language for protection and control in a concurrent processing environment. Ph.D. thesis, New York University, June 1978.
  • R. Grishman. The structure of the PUMA computer system: Overview and the central processor. Courant Mathematics and Computing Laboratory Report COO-3077-157, New York University, New York (1978). PDF / osti.gov / 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 bee 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
  • Ssu-cheng Liu and Robert Paige. Data structure choice/formal differentiation : Two papers on very high level program optimization. Courant Computer Science Report Number 15, New York University, September 1979. PDF / archive.org
    Combines two SETL-based Ph.D. theses:
    • Ssu-cheng Liu. Automatic data structure choice in SETL.
    • Robert Paige. Expression continuity and the formal differentiation of algorithms.
  • 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
  • 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
  • Fritz Henglein. Polymorphic type inference and semi-unification. PhD thesis, Rutgers University, May 1989. Available as NYU Technical Report 443, May 1989, from New York University, Courant Institute of Mathematical Sciences, Department of Computer Science. PDF / PDF at tufts.edu (references missing) / archive.org

 

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:

  • 1. M. C. Harrison. BALM-SETL: A simple implementation of SETL. 5 November 1970. PDF

    "It is suggested that a preliminary implementation of SETL be done in BALM. Though inefficient, such an implementation would be simple, and would permit experimentation with the form of the language, and perhaps be useful as a bootstrap for later versions.

    Given below are routines to implement most of the basic SETL operations. A set is implemented as a BALM list whose first item is the value of the variable SETMARK, which will print as ***. An ordered set is represented by a BALM list. All other data-objects in BALM can be members of sets or ordered sets."

  • 2. Pat Goldberg. A critical comment. 10 November 1970. Patricia C. ("Pat") Goldberg (1937-2004) was a specialist in programming languages and compilers, with a long career at IBM Research. PDF
  • 3. Anonymous. [Modifications and extensions for SETL. Part 1.] 17 November 1970. PDF
  • 4. [Peter Markstein?] APL Version of Peter Markstein's McKeeman Table Routine. 17 November 1970. PDF
  • 5. J. T. Schwartz. Miscellaneous algorithms written in SETL. 18 November 1970. PDF
  • 6. Peter Markstein. [Revised SETL version of McKeeman parse.] 20 November 1970. PDF
  • 7. Dave Shields. [Modifications and extensions for SETL. Part 2.] 24 November 1970. PDF
  • 8. J. T. Schwartz. Additional miscellaneous SETL algorithms. 25 November 1970. PDF

    Permutation generator, generator of unordered trees, Huffman table, Huffman encode and decode, Fisher-Galler equivalence declaration analysis algorithm, polynomial addition and multiplication in form described by Knuth.

  • 9. Malcolm Harrison. Implementation and language design. 1 December 1970. PDF
  • 10. Kurt Maly. Sorting algorithm. 9 December 1970. PDF
  • 11. David Shields. [Modifications and extensions for SETL. Part 3.] 22 December 1970. PDF
  • 12. Jack Schwartz. Recapitulation of the basic parts of the SETL language. 12 January 1971. A later version of this appears as Item 9, A precis of the SETL language, On Programming (1975 version), pages 79-87. PDF
  • 13. J. T. Schwartz. Additional miscellaneous algorithms. 14 January 1971. PDF
  • 14. J. T. Schwartz. Additional syntactic extensions (not recorded in revised version of SETL paper). 19 January 1971. PDF
  • 15. J. T. Schwartz. A proposed SETL implementation plan through the end of the bootstrap phase. 9 February 1971. PDF
  • 16. Kurt Maly. SETL 64-character set / 48-character set (026 keypunch) / CDC6600 64-character set (029 keypunch). 12 February 1971. PDF
  • 17. [No longer available.]
  • 18. D. Shields. Preliminary specification of BALMSETL conventions. 19 February 1971. PDF
  • 19. Kurt Maly. Lexical description of SETL. 26 February 1971. PDF
  • 20. David Shields. BALMSETL user’s guide (in brief). 9 March 1971. PDF
  • 21. Anonymous. An Outside Review: Comments on the SETL draft. 15 April 1971. PDF

    Anonymous review recommending against an [unnamed] paper on SETL being published.

  • 22. J. Schwartz. Some small and large language extensions for consideration. 16 April 1971. PDF
  • 23. Dave Shields. Current Status of BALMSETL Implementation. 20 April 1971. PDF
  • 24. K. Kennedy. Description of a register allocation algorithm. 20 April 1971. PDF
  • 25. B. Loerinc. Print routine. 27 April 1971. PDF
  • 26. J. Schwartz. The currently specified form of SETL from a more fundamental point of view. 3 May 1971. PDF
  • 27. J. T. Schwartz. Code for the postparse setup procedure (Postparse metalanguage analysis). 3 May 1970. PDF
  • 28. K. Kennedy. An algorithm for common subexpression elimination and code motion. 17 May 1971. PDF
  • 29. J. Schwartz. Some issues connected with subroutine linkage. 6 May 1971. PDF
  • 30. J. T. Schwartz. Sinister calls. 7 May 1971. PDF
  • 31. J. Schwartz. An additional preliminary remark on the importance of "object types". 10 May 1971. PDF
  • 32. J. T. Schwartz. Hyper-SETL procedural languages. 15 May 1971. PDF
  • 33. J. T. Schwartz. What is programming? 15 May 1971. A later version of this appears as Item 2, A second general reflection on programming, On Programming (1975 version), pages 12-20. PDF
  • 34. J. T. Schwartz. Syntax revisions in preparation for implementation. 16 May 1971. PDF
  • 35. Dave Shields. New form for IFF-statement. 13 May 1971. PDF
  • 36. J. T. Schwartz. Syntactic and semantic conventions for programmer-definable object types. Date unknown.
  • 37. K. Kennedy and P. Owens. An algorithm for use-definition chaining. 16 July 1971. PDF
  • 38. K. Kennedy. Algorithm for live-dead analysis including node-splitting. 13 January 1972. PDF
  • 39. J. T. Schwartz. More detailed suggestions concerning 'data strategy' elaborations for SETL. 31 May 1971. PDF

    "This note will contain remarks concerning: (i) SETL implementation; (ii) the possibility (raised in Newsletter 30, pp 31-32, and 31, pp. 5-7) of securing increased efficiency by adding a system of optional elaborations to the language. These elaborations, if present, should increase running speed considerably and lead also to significant data compressions."

  • 40. Anonymous. List of Newsletters #1-40. Undated - circa June 1971? PDF
  • 41. J. T. Schwartz. Additional planning detail for the current and next phase of SETL implementation. 2 June 1971. PDF

    "This newsletter brings Newsletter 15 of Feb. 19, 1971 up to date.

    Status Report: A first version of the BALMSETL parsing system is now close to working, though very inefficiently (approximately 30,000 times slower than FORTRAN)."

  • 42. J. T. Schwartz. Revised conventions concerning tuples. 4 June 1971. PDF
  • 43. Samson Gruber. A parsing scheme for FORTRAN. 13 July 1971. PDF
  • 44a. Kurt Maly. Comprehensive SETL specifications. 6 July 1971. PDF
  • 45. Dave Shields. Semi-local SETL optimization. 19 July 1971. PDF
  • 46. J. Schwartz. Generalized nodal span parse routine; preliminary draft. 21 July 1971. PDF
  • 47. Kurt Maly. Outline for a parsing scheme for SETL. 27 July 1971. PDF
  • 48. Jerry Hobbs. Toward a documentation of the String Project's program for parsing English sentences. 5 August 1971. PDF
  • 49. Henry Warren. Detailed specifications of certain SETL operations. 10 August 1971. PDF

    "This specification serves two purposes: 1. It is a starting point for a BALM implementation of a SETL-like language in which sets are accessed by means of a hashing scheme. 2. It is a detailed specification of the meaning of most current SETL operators, and a few other SETL constructions such as functional application."

    Part 2 is essentially a specification of SRTL (the SETL Run Time Library) in SETL.

  • 50. Kurt Maly. Three-phase parsing scheme for SETL. 10 September 1971. PDF

    "We will give a more detailed specification of the parser of SETL outlined in Newsletter 47."

  • 51. Anonymous. List of Newsletters 41-59a. Undated; circa February 1972? Also lists LITTLE Newsletters 1-3. PDF
  • 52. Jay Earley. Comments on SETL. 16 September 1971. PDF

    Proposals for symmetric use of relations; tuples, sequences, and strings; conditions on sets. Cites Codd's paper on the relational model and Earley's own work on the VERS language.

  • 53. H. S. Warren. SETL to LITTLE Translation: a first look. September 1971. Item 7 of On Programming: An Interim Report on the SETL Project (1975 version, pages 54–68), titled "SETL implementation and optimization: A first look at SETL compilation—target code style", says it is a revision of this newsletter; it is less detailed. PDF

    "This newsletter discusses the possibility of compiling SETL programs into LITTLE code, without using the "SETL machine" approach. The motivation for this is run-time efficiency on conventional (non-microprogrammable) machines, while maintaining portability.

    A primary goal is to produce, by early 1972, the first version of a SETL compiler capable of compiling a preliminary SETL language, but probably without optimizations. The implementation in early 1972 should be able to handle most SETL features, such as recursive procedures, arbitrarily large integers, the compile statement, SETL name-scoping rules, and SETL rules for matching arguments to formal parameters."

  • 54. S. Gruber. Current status of BALM-SETL 4. 24 September 1971. PDF

    "The BALM-SETL 4 routines follow Newsletter 49 fairly closely. There are a few points of divergence and many things which are not included in the specs, and it is these that will be elaborated upon here."

  • 55. S. Finkelstein. SETL suggestions and questions. 29 September 1971. PDF
  • 56. Jay Earley. Additional comments on some basic SETL operations: Infinite sets and the set formers. 29 September 1971. PDF
  • 56A. Jay Earley. More comments on SETL: Types. 6 October 1971. PDF
  • 56B. Jay Earley. More SETL comments: A set-former optimization. 10 October 1971. PDF
  • 57. H. S. Warren. Minimizing copying in SETL: Preliminary observations. 8 October 1971. PDF
  • 58. Kurt Maly. Phase one of the SETL compiler. 22 October 1971. The last two pages are Addenda and Errata, constituting Number 58a, 15 November 1971. PDF
  • 59. Rudolph A. Krutar. An algebra of assignment. 27 October 1971; submitted 29 February 1972. Newsletter 51 lists this as 59, with 59a being Addenda and Errata. PDF
  • 60. H. S. Warren. SETL compiled code: Calls to SETL procedures. 4 November 1971. PDF
  • 61. Kurt Maly. Syntactic structure of SETL. 15 November 1971. PDF
  • 62. Kurt Maly. Final specification part of SETL and the parser. 8 December 1971. PDF
  • 63. G. Fisher. The SETL print routine. 11 January 1972. PDF
  • 64. Kurt Maly. SETL compiler with elaborated data structures. 26 January 1972. PDF
  • 65. Robert A. Bonic. Some notational suggestions. 2 February 1972. PDF
  • 66. Elie Milgrom. BALMSETL Users Manual Version 1.0. February 1972; revised August 1972. Marked "obsolete" in Newsletter 69.
  • 67. Kurt Maly. Data structures of the SETL compiler for the LITTLE version. 22 February 1972. PDF
  • 68. S. Brown. Some Thoughts on Efficient Programming in SETLB. 26 October 1972. PDF

    "To compile and execute a SETLB program actually requires running two programs. The first is the SETLB preprocessor. It reads the SETLB program and translates it into BALMSETL. The second program is BALM. BALM reads the BALMSETL and produces 6600 code which is then executed."

  • 69. R. Abes. The SETL project - master catalog. 5 February 1973; revised March 1980. An earlier September 1973 revision of this newsletter was published as [Abes 1973]. PDF
  • 70. J. Schwartz, S. Brown, and E. Schonberg. SETLA user's manual. February 1972; revised January 1975 according to [Abes 1980]. A revision of 1 August 1974 appears in On Programming: An Interim Report on the SETL Project (1975 version), pages 90–159. Appendix 1 of On Programming (1975 version) listed this as: SETL Users Manual. J. T. Schwartz. PDF
  • 71. J. Schwartz. Deducing the logical structure of objects occuring in SETL programs. 17 April 1972. PDF
  • 72. D. Shields. An introductory explanation of SETL, a status review, and a profile of SETL User-Group. 17 April 1972. PDF

    It describes how BALM, BALMSETL, SETLB and SETL/LITTLE were being implemented, including bootstrapping.

  • 73. Kurt Maly and Hank Warren. SRTL: User's guide to the SETL Run Time Library. Revision 3, 16 May 1973. PDF

    "The SETL Run Time Library is a collection of subroutines and macros, written in the LITTLE language, that are capable of evaluating SETL expressions. Subroutines are provided to build sets, test SETL objets for equality, concatenate strings, etc. The library includes a storage allocation mechanism that is based on a compacting garbage collector."

  • 74. L. V. Gorodnaya, D. A. Levin, and V. Chernobrod. Project Plan for First Stage of Implementation. 5 May 1972, Novosibirsk. Partial translation from the Russian. PDF

    See also Siberian SETL.

  • 75. E. Milgrom. Some thoughts on the use of BALM to implement SETL. 1 June 1972. Also issued as BALM Bulletin Number 13. PDF
  • 76. J. Schwartz and G. Jennings. Semantic-definition matters. May 1973. PDF

    "In the present newsletter, a preliminary attempt at systematic semantic definition of SETL will be made. This will be done by describing, in a deliberately abstract way, a hypothetical 'back end' for the SETL compiler. The 'back end' will consist of a set of routines concerned with name scoping, compilation of abstract recursively structured syntactic trees into interpretable serial structures, digestion of labels, and finally with the interpretation of an ultimate code form. The total package will include almost all the routines necessary to go from a simplified 'host language' form of SETL to interpretable text."

  • 77. J. Schwartz. Transferring SETLB to other machines. 20 September 1972. PDF
  • 78. R. Paige. Executing BALM and SETLB at NYU Courant. Date unknown.
  • 79. R. Paige. SETL, LITTLE, BALM files. Date unknown.
  • 80. Kent Curtis. Algorithms in the SETLB test package. 28 September 1972. PDF

    This and other newsletters mention "SETL Notes" (with page number references as high as 251); Newsletter 101 suggestions this was [Schwartz 1971].

  • 81. J. Schwartz and S. Brown. Memory size of SETLB runs. 28 September 1972. PDF
  • 82. E. Desautels. Timing comparison between SETL and FORTRAN. 3 October 1972. PDF
  • 83. J. Schwartz, et al. User experience and human factors improvement of SETL. 1 November 1972. PDF
  • 84. J. Schwartz. Plan for a library of algorithms. 5 November 1972; revised October 1973. PDF
  • 85. H. Warren. Estimate of minimum running size for the next SETL system. 24 April 1973. PDF

    Includes listing of SETL Run Time Library routines.

  • 86. J. Schwartz. Proposal for a temporary, but easily implemented, software paging scheme. 8 November 1972. PDF
  • 87. J. Schwartz. Workplan for the next phases of the SETL project. 15 November 1972. PDF
  • 88. J. Schwartz. A scheme for BALMSETL measurements. 10 November 1972. PDF
  • 89. Anonymous. User information for the lexical scanner setup. 8 November 1972; revision 1, 16 January 1973. PDF
  • 90. J. Schwartz. Preliminary reflections on the use of SETL in a data-base context. 5 December 1972. PDF
  • 91. J. Schwartz. A 'grammarless' parse and a related procedure for retrieval by similarity. 7 December 1972. PDF
  • 92. Kent Curtis. Some experiments with SETLB programs. 2 January 1973. PDF
  • 93. Kent Curtis. A note on optimization and programming style in SETL. 5 January 1973. PDF
  • 94. G. Jennings. An algorithm to represent a collection of sets as intervals. 23 January 1973. PDF
  • 95. Yeshiah Feinroth. Generalized nodal span parse routine, corrected version. 17 January 1973. PDF

    "This newsletter gives a rewrite of the generalized nodal span parse routine described in Newsletter 46. A SETLB program was written in accordance with the SETL algorithm therein described, debugged, and retranslated into true SETL."

  • 96. N. Minsky. Pointers and "Very high level languages". January 1973. PDF
  • 97. P. Markstein. SETL extensions for operating system description: Installment I of a thesis draft. 1 February 1973. PDF

    Chapter 2 describes PSETL (Parallel SETL).

  • 98. J. Schwartz. Reflections on P. Markstein's newsletter on SETL extensions for operating system description. 27 January 1973. PDF
  • 99. S. Brown. Paging, the quick and dirty way. 31 January 1973. Also published as BALM Bulletin 21. PDF

    A version of BALMSETL with paging is available. The implementation is loosely based upon the description in SETL Newsletter 86. It proved to be only slightly more difficult to implement than anticipated. The SETLB user should not expect the paging version to solve all of his space problems as this version represents, at best, an interim solution. The user will find himself once again confronted by the dilemma of trading core size against running time.

  • 100. Hank Warren. Making SRTL debugging runs. 20 February 1973. PDF

    "This note describes the present manner of making debugging runs involving the SETL run time library. The setup of a run is complicated because of the existence of global macros and variables, and because the present LITTLE compiler has no provisions designed to avoid recompiling a complete program to test any change to the program, no matter how small the change may be. The purpose of most of the complications is to circumvent the latter deficiency."

  • 101. Robert Bonic. How to program if you must (the SETL style). 1 March 1973. PDF

    Section 8 says: "A powerful aspect of SETL is that it allows procedure names to be elements of sets or components of tuples. This use will be illustrated below."

    Was this true in 1973?

  • 102. K. Kennedy. Reduction in strength using hashed temporaries. 12 March 1973. PDF
  • 103. J. Schwartz. Preliminary plan for BALM-to-LITTLE translator. 10 April 1973. PDF

    "The debugging of the LITTLE-written, SRTL-compatible BALM interpreter which will initially support the new SETLB system is now far advanced. However, in order to avoid substantial losses in BALM compile efficiency, and possibly significant losses in SETLB execution efficiency as well, we will undoubtedly require a SRTL-compatible BALM translator as a replacement for the interpreter. This is, of course, an SRTL-compatible version of the present (R. Paige) BALM translator. This newsletter will outline a plan for such a translator."

  • 104. Gray Jennings. An algorithm to represent a collection of sets as a direct product of intervals. 28 March 1973. PDF
  • 105. S. Marateck and J. Schwartz. SETL programs for a basic block optimizer and an extended basic block optimizer. 23 April 1973. PDF
  • 106. Gray Jennings. User variation of the semantics of function and subroutine invocation. 17 May 1973. PDF

    "The second generation of SETLB, SETLB.2, based upon a version of the BALM interpreter written in LITTLE and the SETL Run Time Library, will become operational in the near future. It will offer a limited capability for variation of the semantics of subroutine and function invocation by the SETLB programmer."

  • 107. Ken Kennedy. Linear function test replacement. 20 May 1973. PDF

    "This newsletter is a sequel to SETL Newsletter #102 ('Reduction in Strength Using Hashed Temporaries')."

  • 108. G. Jennings. APL-SETL, an extension of SETL achieved from user varied semantics. May 1973. PDF
  • 109. Stephanie Brown. Faster execution for the LITTLE based BALM system. 27 July 1973. PDF

    "Initial runs of the LITTLE written MBALM [the BALM virtual machine] simulator indicate that it runs almost a factor of two times more slowly than the current FORTRAN based MBALM simulator. Allowing for expected improvements in the new LITTLE assembler the LITTLE based simulator can probably be made to perform as well as the FORTRAN version. Since the LITTLE based simulator will use the SETL run time library procedures in executing SETLB programs it will actually be considerably faster than the FORTRAN based version. However, it seems unlikely that the LITTLE based simulator will match the overall speed of our current MBALM to COMPASS translator system. Consequently a SRTL-compatible BALM translator will probably be necessary to make the LITTLE based system a viable alternative."

  • 110. [Never issued?]
  • 111. K. Kennedy. Global dead computation elimination. 7 August 1973. PDF
  • 112. K. Kennedy. An algorithm to compute compacted used-definition chains. 14 August 1973. PDF
  • 113. Stephanie Brown. LITTLE code generation from the BALM compiler. 8 August 1973. PDF
  • 114. Abraham Getzler. A SETLB to Publication SETL translator. 17 August 1973. PDF

    "As a byproduct of Malcolm Harrison's Artificial Intelligence Algorithms Project, there's now available on the 6600 a working program to turn SETLB source decks into publication SETL manuscripts.

    The output of the program should be listed using Malcolm Harrison's deluxe teletype to take advantage of its lower case capabilities, backspacing, underlining, and extended character set."

  • 115. G. Weinberger and A. Tenenbaum. A SETL representation of the Maryland GRAAL graph-manipulation language. 21 August 1973. PDF
  • 116. [A. Ershov et al.] Catalog of SETL(C) Newsletters as of July 30, 1973. 1 August 1973. "C" stood for "Cyrillic"; see Siberian SETL. According to [Abes 1980], this was also SETL(C) Newsletter 11. PDF
  • 117. E. Schonberg. A static debugging system for LITTLE. 4 October 1973. PDF
  • 118. A. Tenenbaum. Revised and extended algorithms for deducing the types of objects occuring in SETL programs. 20 October 1973. PDF
  • 119. J. Schwartz. A suggested generalization and revision of the SETL compound operator form. 25 August 1973. PDF
  • 120. J. Schwartz. A general-recursive extension of function application, and its uses. 4 December 1983. PDF

    Proposes adding a feature based on the "meta composition" of the family of "reduction languages" defined in [Backus 1973] (which Schwartz intended to cite but omitted).

    • John Backus. Programming language semantics and closed applicative languages. In Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages (POPL '73). Association for Computing Machinery, pages 71–86. ACM Digital Library
  • 121. Aaron Tenenbaum. An algorithm to determine the identity of SETL run-time objects. 2 January 1974. PDF
  • 122. J. T. Schwartz. More local and semi-local SETL optimisations. 20 January 1974. PDF

    "... continues D. Shields' Newsletter 45 on the same subject."

  • 122A. J. Schwartz. A few peephole optimisations applicable to iterators. 2 July 1974. PDF
  • 122B. J Schwartz. Still more optimisations. 24 July 1974. PDF
  • 123. K. Kennedy. Variable subsumption with constant folding. 1 February 1974. PDF
  • 124. Ed Schonberg. The VERS2 language of J. Earley considered in relation to SETL. 30 January 1974. PDF
  • 125. K. Kennedy (Rice University). Schaefer's node splitting algorithm. 6 February 1974. PDF
  • 126. Michael Brenner. A SETLB specification of EDIT. 4 February 1974. PDF
  • 127. K. Kennedy. Edge-listing data-flow algorithms. 15 March 1973. PDF
  • 128. Ed. Schonberg and Stephanie Brown. A LITTLE written translator from SETL to LITTLE. 25 April 1974. PDF

    "We examine here the feasibility of a direct SETL to LITTLE translation as the next phase of development of the SETL system. The interest of such a direct translation is two-fold:

    a) by eliminating the BALMSETL link from the present system, many of the annoying semantic restrictions imposed by BALM on SETLB can be removed. In particular, the implementation of the proposed SETL namescoping scheme becomes possible. Current restrictions on the use of labels and recursive calls within iteration loops can also be removed.

    b) Bypassing BALM as an intermediate language streamlines the SETL system and simplifies its maintenance. Incrementality of the language can actually be assured more easily than with a SETL-to BALM-to LITTLE system, where tables of variables, procedures and linkages have to be maintained in two places simultaneously (the BALM and SRTL environment)."

  • 129. J. Schwartz. More on SETL in a data-base environment. 20 May 1974. PDF

    This newsletter
    > i. takes up the discussion initiated in newsletter 90;
    > ii. tries to put the discussion on a more reasoned semantic basis;
    iii. arrives at a proposal differing substantially from that of NL. 90...

    The discussion which follows is much influenced by the proposals made by George Weinberger in his thesis-in-progress.

  • 130. J. Schwartz. Deducing relationships of inclusion and membership in SETL programs. 29 May 1974. PDF

    "This newsletter takes up the 'high level optimisation' theme of NL.71, NL.118, NL.121, and of Aaron Tenenbaum's thesis (hereinafter referenced as TT). The generally good performance of Tenenbaum's 'type-finder' program suggests that it may be feasible to deduce deeper properties of the objects appearing in SETL programs. In the present newsletter, we will outline techniques which, building on the approach and result of the typefinder, allow useful relationships, among them relationships of inclusion and membership,to be established."

  • 130A. J. Schwartz. Estimates from below of the domain of a mapping. 1 August 1974. PDF
  • 130B. J. T. Schwartz. The use of equalities in the deduction of inclusion/membership relations. 30 May 1975. PDF
  • 131. J. Schwartz. More on copy optimization of SETL programs. 7 June 1974. PDF
  • 132. J. Schwartz. Some optimizations using type information. 3 June 1974. PDF
  • 133. J. Schwartz. A higher-level control diction. 20 June 1974. PDF

    The Pursue block

  • 133A. J. Schwartz. Additional Pursue block examples. 2 July 1974. PDF
  • 133B. J. T. Schwartz. General comments on high level dictions and specific suggestions concerning 'Converge' iterators and some related dictions. 29 January 1975. PDF
  • 134. J. Schwartz. Inter-procedural optimization. 1 July 1974. PDF
  • 135. J. T. Schwartz. Introductory lecture at the June 28 'Informal Optimisation Symposium'. 1 July 1974. PDF
  • 135A. J. Schwartz. Structureless programming, or the notion of 'Rubble', and the reduction of programs to Rubble. 12 July 1974. PDF
  • 135B. J. T. Schwartz. Additional thoughts on 'Language level' and optimisation. 12 January 1975. PDF
  • 135C. J. T. Schwartz. On the genesis of complex programs. 1 August 1975. PDF
  • 136. J. T. Schwartz. A framework for certain kinds of high-level optimisation. 16 July 1974. PDF
  • 137. J. T. Schwartz. Additional thoughts concerning automatic data structure choices. 25 July 1974. PDF
  • 138. J. T. Schwartz and R. Paige. On Jay Earley's 'Method of iterator inversion'. Undated; summer of 1974? PDF
  • 138A. J. T. Schwartz. Optimisation by set suppression. 12 August 1974. PDF
  • 138B. J. T. Schwartz. Updating the lower bound of a set of integers in set-theoretic strength reduction. 6 January 1976. PDF
  • 139. [Never issued?]
  • 140. J. Schwartz. Use-use chaining as a technique in typefinding. 27 September 1974. PDF
  • 141. J. T. Schwartz. Reflections on some very-high level dictions have an English / "automatic programming" flavor. 16 January 1975. PDF
  • 142. J. T. Schwartz. What programmers should know. 29 January 1975. A version of this appears as Item 3.II of On Programming (1975 version), pages 24-27. PDF
  • 143. J. T. Schwartz. 'Arguments from use' in the proof of relationships of inclusion and membership. 3 February 1975. PDF
  • 144. J. T. Schwartz. Interprocedural live-dead analysis. 25 February 1975. PDF
  • 145. P. Shaw. GYVE-oriented inter-process coordination and control features for an extended SETL (SETLG): Preliminary notes. 1 March 1975. PDF
  • 146. J. T. Schwartz. Adaptation of GYVE/SETLG to distributed network of computers: Preliminary proposal. 7 March 1975. PDF
  • 147. J T. Schwartz. A syntactic construct useful for checking parameters. 8 March 1975. PDF
  • 148. Ed Schonberg and A. Stein. Technical and human factor improvements for the fully compiled SETL system. 21 April 1975. PDF

    "SETL1, the first fully compiled implementation of SETL, is nearing completion. This system uses a BALM-to-LITTLE translator, written in BALM, to produce LITTLE source code, which is then compiled as a LITTLE program and executed in the environment of the run-time library. The translator is itself interpreted by the BALM interpreter, written in LITTLE, which also utilizes the SRTL. The full system consists of the following modules:

    a) SETLA: A lexical scanners and syntactic analyzer. SETLA is written in LITTLE. Its output consists of various token tables and a sequence of calls to generators.

    b) TREEWLK: A series of treewalking routines, written in BALM, which build BALM parse-trees using the output from a).

    c) TRANS: The translator proper, which replaces the code generators of the BALMSETL system, so that LITTLE code is emitted (instead of extended MBALM code).

    d) BALMINT: A BALM interpreter, which uses a portion of SRTL, and executes b) and c).

    e) The LITTLE compiler.

    f) SRTL."

    Was "SETLA" promoted from the name of the lexer/parser to the name of this whole system?

  • 149. J. T. Schwartz. Conventions allowing other languages to be used within GYVE; Files; Memory hierarchy questions; Some suggestions for GYVE extensions. 20 April 1975. PDF
  • 150. J. T. Schwartz. What constitutes progress in programming. 10 May 1975. A version of this appears as Item 3.I of On Programming (1975 version), pages 21-23. PDF
  • 151. J .T. Schwartz. Additional considerations concerning semi-automatic data structure choices. 20 June 1975. PDF

    "This newsletter returns to the theme of NL 39 (More Detailed Suggestions Concerning 'Data Strategy' Elaborations for SETL), namely to the idea of a declarative, programmer-assisted approach to the problem of data structure choice. Since such an approach is an alternative to and perhaps also a preparation for fully automatic structure choice, it deserves investigation. This newsletter will simplify and flesh out the suggestions made in NL 39."

  • 152. J. T. Schwartz. An alternative for a 'MIDL'-level language. 5 July 1975. PDF

    See [Deak et al. 1977].

  • 153. J. T. Schwartz. The significance of 'backtracking', and its cost. 15 July 1975. PDF
  • 154. Ed Schonberg. Timing considerations for the SETL translator system. 24 July 1975. PDF

    Timings are provided for three versions of each of five algorithms: SETL running on SETLA (which ran on the MBALM virtual machine), SETL compiled by TSETL to LITTLE code, and hand-translated LITTLE versions. The results showed that TSETL was 2 to 5 times faster than SETLA. The hand-translated LITTLE versions were 20-200 times faster than SETLA, and 7-50 times faster than TSETL.

  • 155. J. T. Schwartz. Intermediate result recording and other techniques for optimizing recursions and backtrack programs. 7 October 1975. PDF
  • 156. J. Schwartz. The next phase of our work. 1 August 1975. PDF

    "The fully compiled version of the SETL system (SETLC) is now functioning adequately (though problems still exist; see below). Our main effort from now on will be directed at the global optimization of SETL. Toward this end the following has already been done:

    (a) A large variety of peephole optimizations have been installed. Our experience with these is disappointing; speed gain is small. This makes it clear that purely local optimization of SETL cannot improve its speed much.

    (b) Extensive, but still quite unpolished, SETL code for the various forms of global analysis described in 'Optimization of Very High Level Languages' (Jour. Prog. Langs., v. 1, # 2,3) has been developed.

    (c) Dave Shields' work on global optimization of LITTLE is going forward. When complete, this should improve the speed of our whole system by about 20 %.

    (d) A semi-automatic data structure choice scheme has been outlined in NL 151."

  • 157. J. T. Schwartz. 'Whenever' dictions. 7 August 1975. PDF
  • 158. E. Schonberg. Implementation of reference counts in the SETL system. 15 October 1975. PDF

    "This Newsletter extends the remarks of SETL Newsletter no. 57 (Hank Warren: copy minimization in SETL) and describes a somewhat restricted implementation of reference counts (RF's) in the SETLA interpretive system."

  • 159. J. Schwartz. On the 'base form' of algorithms. 6 November 1975. PDF
  • 160. J. T. Schwartz. An algebra of program events potentially useful in a debugging language. 13 November 1975. PDF
  • 161. Art Grand. Specifications for a new optimizer-oriented SETL front end. 31 December 1975. PDF
  • 162. J. T. Schwartz. Improved target code forms available in the presence of global information. 20 January 1976. PDF
  • 163. Martin C. Golumbic. Recognizing comparability graphs in SETL. 19 March 1976. PDF
  • 164. Robert B. K. Dewar. Copy optimization in SETL. 13 April 1976. PDF
  • 164A. J. T. Schwartz. 'Copy on assignment' optimization in SETL. 7 April 1976. PDF
  • 165. J. T. Schwartz. A simple criterion for avoiding basing errors. 7 April 1976. PDF
  • 166. R. Dewar and J. T. Schwartz. An easy scheme for incorporating backtracking into the new SETL implementation. 8 April 1976. PDF
  • 167. J. T. Schwartz. A variant SETL implementation incorporating 'Whenever' dictions. 14 April 1976. PDF
  • 168. Robert B. K. Dewar. The trouble with triples. 13 April 1976. PDF
  • 169. Robert Dewar, Art Grand, Len Vanek, and Ed Schonberg. Some changes to the SETL language in preparation for the optimizer implementation. 11 April 1976. PDF
  • 170. Robert Dewar, Art Grand, Ed Schonberg, and Len Vanek. Provisional plan for the SETL optimizer interface. 22 April 1976. PDF
  • 171. R. Dewar, J. Schwartz, and E. Schonberg. More on basings. 29 April 1976. PDF
  • 171A. J. Schwartz and R. Dewar. 'Basing semantics' revisited. 9 December 1976. PDF
  • 171B. J. Schwartz and A. Grand. Remark on the Implementation of the basing scheme. 14 December 1976. PDF
  • 171C. Art Grand. Implementation of base assignments. 22 April 1977. PDF
  • 172. Robert B. K. Dewar, Art Grand, Edmond Schonberg, and Len Vanek. 25 May 1976. PDF
  • 173. Leonard Vanek. Simplifying and extending the SETL type calculus. 30 April 1976. PDF
  • 174. Robert Dewar. Relaxation of basing restrictions. 19 July 1976. PDF
  • 175. S. C. Liu and E. Schonberg. More on copy optimization. 21 July 1976. PDF
  • 176. J. T. Schwartz. A coarser, but simpler and considerably more efficient copy optimization technique. 2 August 1976. PDF
  • 177. J .Schwartz. Measurement utilities for the optimized SETL system. 6 August 1976. PDF
  • 178. J. T. Schwartz. Motion range checks out of loops; optimization of integer arithmetic. 6 August 1976. PDF
  • 179. S. C. Liu. Dynamic multiple member basings. 9 October 1976. PDF
  • 180. S. C. Liu and E. Schonberg. Uncovering profitable basic relations. 14 February 1977. PDF
  • 181. W. H. Tsui. A reformulation of value-flow analysis. March 1977. PDF
  • 182A. Leonard I. Vanek. Linkage conventions for the SETL optimizer. (Supercedes NL 1982). 28 April 1977. PDF
  • 183. E. Schonberg, R. Dewar, A. Grand, and J. Schwartz. Some revisions of basing semantics and implementation. 16 December 1976. PDF
  • 184. Robert B. K. Dewar. Extending the notion of basing. 18 March 1977. PDF
  • 185. Leonard Vanek. Using output from the SETL copy optimizer. 28 March 1977. PDF
  • 186. R. Dewar and J. Schwartz. Syntax and semantics of a restricted backtrack implementation. 21 April 1977. PDF
  • 187. M. Sharir. On Inter-procedural flow analysis. April 1977. PDF
  • 187A. Micha Sharir. More on inter-procedural data flow analysis. May 1977. PDF
  • 188. Leonard Vanek. A limited form of common subexpression elimination for SETL programs. 31 May 1977. PDF
  • 189. R Dewar, A. Grand, E. Schonberg, and J. Schwartz. SETL data structures. 7 July 1977. PDF

    "This Newsletter describes the data structures which will be used for the run time systems of both the interpreted and compiled versions of the new SETL system. The introduction of basings has provided an opportunity for redesign of the SETL runtime system since it will be necessary to modify much of the runtime library in any case to support the basings. Consequently, the data structures have been completely redesigned and it is expected that programs will run faster with the redesigned structures even if the basing declarations are not used."

  • 189B. Stefan M. Freudenberger. SETL data structures. 15 May 1980; revised 23 October 1982. PDF

    "This Newsletter describes the data structures which are used for the run-time systems of both the interpreted and compiled versions of the SETL 2.1 system. It replaces SETL Newsletter 189 on the SETL Data Structures by Robert B. K. Dewar, Art Grand, Edmond Schonberg, and Jacob T. Schwartz.

    Most of the changes to the previous newsletter are in the details, rather than in the general design of the data structure. In the course of the implementation, however, a sufficient number of differences developed to make this revision necessary."

  • 190. Art Grand. The implementation of backtracking. 5 May 1977. PDF
  • 191. Art Grand. More language changes. 6 May 1977. PDF
  • 192. R. Dewar, A. Grand, R. Kenner, and J. Schwartz. 6600, 370, and PUMA Microcode Nubbins. 13 May 1977. PDF

    PUMA was a microprogrammable computer sharing the CDC 6600 instruction set architecture that was designed and built at NYU.

    • See [Grishman 1978].
    • See [CIMS 1978, page 20].
    • Ralph Grishman. The PUMA project: Computer design automation in the university. In Proceedings of the ACM 1980 annual conference (ACM '80). Association for Computing Machinery, New York, NY, USA, 490–497. ACM Digital Library
  • 193. Micha Sharir. On a static scheme to find procedure variables. 16 May 1977. PDF
  • 194. Sandra Rapps. Nondeterminism, backtracking, and pattern matching in SETL. 13 June 1977. PDF
  • 195. Micha Sharir. An algorithm for copy optimization, based on NL176. 11 July 1977. PDF
  • 196. Art Grand. Current state of the SETL implementation. 28 August 1977. PDF

    "We are currently in the process of debugging the new SETL system. At this point we have successfully executed a 200 line program which tests the I/O, all the control structures, arithmetic, and most of the primitives for sets, maps, and tuples. It also tests the garbage collector, including the feature which turns off share bits of objects which are not actually shared. The test program does not contain any declarations since they cannot currently be processed by the compiler.

    The run time library is close to completion. ...

    At this stage we must put a considerable amount of work into the compiler. ..."

  • 197. Micha Sharir. Some comments on extending code motion and expression availability algorithms for the SETL optimizer. 30 September 1977. PDF
  • 198. Robert B. K. Dewar. String primitives. 18 January 1978. PDF

    "This newsletter contains a suggestion for introduction of string primitives into SETL.

    The suggestions derive from SNOBOL-4, but lack (deliberately) the complexity of this language's pattern matching facility. In particular, they do not contain any imbedded backtracking. In those rare cases where backtracking matches are desired, the suggested functions can be used in conjuction with the existing backtracking prinitives to provide the required effect."

  • 199. Micha Sharir. Non-propagation of errors — a modified type-finding algorithm. 5 January 1978. PDF
  • 200. J. T. Schwartz. Possible additional REPRs for the new SETL system. 12 February 1978. PDF

    "The new SETL system is now beginning to approach operational status. As the present library of data representations, and the routines which support them become operational, it may become feasible to add various significant new representations, with corresponding code, to the library. Some of these representations may be easily implementable by short routines which invoke existing facilities. This note will comment on two potentially significant representations not currently provided: list and B-trees."

  • 201. Micha Sharir. On compaction on RC-paths. 15 February 1978. PDF
  • 202. Henry M. Lewis. Stropping and character-set conventions. 21 July 1978. PDF
  • 203. Micha Sharir. A simplified approach to automatic data structure choice. 5 January 1978. PDF
  • 204. J. T. Schwartz and M. Sharir. Tarjan's fast interval finding algorithm. 3 March 1978. PDF
  • 205. Micha Sharir. On disjointness detection in automatic data-structure choice. 11 July 1978. PDF
  • 206. A. Grand and M. Sharir. On name splitting in SETL optimization. 5 February 1978. PDF
  • 207. Micha Sharir. A second simplified approach to automatic data structure choice. 8 March 1978. PDF

    "This note follows SETL Newsletter No. 203, where a new approach to automatic data-structure selection has been described. The approach suggested there, although it has a rather simple structure, suffers from several deficiencies which have led us to look for an alternative approach. The new and probably improved approach, to be described in this newsletter, is closer to Ed Schonberg's algorithm (to be described in a coming newsletter) and seems to be faster than the first approach. In spite of the differences between these two methods, they still have a similar overall logic which is much simpler than that of previously suggested algorithms. Among these simplifications are: using the BFROM and FFROM maps instead of value-flow maps and dispensing altogether with a phase which inserts 'locate' instructions into the code. ..."

  • 208. Micha Sharir. A few cautionary notes on the convergence of iterative data-flow analysis algorithms. 7 April 1978. PDF
  • 209. E. Schonberg. Automatic data structure choice. 17 March 1978. PDF

    "This newsletter outlines the design of the automatic data-structuring module currently incorporated in the optimizer of the SETL compiler. Although several aspects of this design have been considerably revised and modified, it is presented in unretouched form, first to serve as a short introduction to the use of bases for automatic data-structuring, and second, as a background for M. Sharir's recent newsletter on the subject (SETLNL.203), which details several major improvements to the scheme presented here."

    See also Newsletter 207, an improvement of Newsletter 203.

  • 210. J. T. Schwartz. Remarks on debugging. 6 February 1979. PDF
  • 211. Robert B. K. Dewar and Art Grand. SETL character set—the final decisions. Undated; 1979? PDF
  • 212. J. Schwartz. A note on program genesis. 30 September 1979. PDF
  • 213. M. Sharir. Future plans for the SETL optimizer. 1 January 1980. PDF

    "The work on the SETL optimizer is now approaching the end of another phase. A first implementation, written in SETL, is about to be completed. It contains most of the major optimizations that we have contemplated, including common subexpression elimination and code motion, type analysis, automatic data-structure selection and copy optimization. It has been tested on a few small to medium size SETL programs with satisfactory results.

    Of course, in its current state, the optimizer is still far from the state at which it could be used routinely as part of the SETL compiler. Currently it does not contain based data-structure declarations, and because of its length it is compiled and executed as nine successive phases. On the average the optimizer currently processes one SETL source line per minute. However, we can estimate the speed-up that could be achieved by the following improvements:

    (a} Introduction of based representations (especially in the sections which perform bitvectoring data-flow analysis, where currently the analysis bitvectors are still represented as unbased sets). This should give a speed-up of at least 2.

    (b} Improvement of the SETL system, e.g. by generation of hard code and elimination of the interpretive overhead, should give a speed-up of approximately 4.

    (c) Elimination of the binary I/O currently needed for communication between subsequent phases of the optimizer, and minimization of the dumps and other printouts currently produced by the optimizer, should give a speed-up of approximately 4. All these improvements together could bring the optimizer to a level at which it could process roughly 30 lines/minute.

    (d) Optimization of the optimizer by self-application. This might double the optimizer speed once more. Note however that the optimizer is roughly 10,000 lines long, so self- application will initially require a run of approximately five hours. If these estimates are correct, then the optimizer will reach only a minimal production level after these improvements.

    It therefore appears likely that we will want to recode all, or significant parts of the optimizer in a lower-level language (probably LITTLE)."

  • 214. Micha Sharir. A strange sorting algorithm inspired by formal differentation. 27 March 1980. PDF

    See also:

    • Micha Sharir. Some observations concerning formal differentiation of set theoretic expressions. ACM Trans. Program. Lang. Syst. Volume 4, Number 2 (April 1982), pages 196–225. ACM Digital Library
  • 215. Stefan M. Freudenberger. Optimisation of case statements. 15 April 1981. PDF
  • 216. Stefan M. Freudenberger. On plex bases in SETL. 17 May 1981. PDF
  • 217. Stefan M. Freudenberger. An example of how to initialize the SETL heap dynamically. 11 November 1981. PDF

SETL Newsletter. Citations for Numbers 220-233 were provided by Fritz Henglein:

  • 220. F. Henglein. Overloading in SETL is not (syntactic) overloading after all. April 1987. PDF
  • 221. Fritz Henglein. A polymorphic type model for SETL. 17 July 1987. PDF
  • 222. Fritz Henglein. Semi-unification. 6 April 1988. PDF
  • 223. Fritz Henglein. The Milner-Mycroft Calculus. April 1988.
  • 224. C. Dubois and F. Henglein. A first-order axiomatization of parametric polymorphism and dynamic overloading and its Typol specification. May 1988.
  • 225. M. Smosna. SETL-2 -- A rationale for the redesign of SETL. June 1988.
  • 226. Matthew Smosna. The implementation of SETL-2—An experiment in the use of Ada as an implementation language. June 1988.
  • 228. Jiazhen Cai, Philippe Facon, Fritz Henglein, Robert Paige, and Edmond Schonberg. Type transformation and data structure choice. November 1988, updated 12 January 1994. PDF
  • 229. Fritz Henglein. Polymorphic type inference is semi-unification. October 1988.
  • 231. Fritz Henglein. A fast algorithm for computing uniform semi-unifiers. October 1988.
  • 232. Fritz Henglein. Simple type inference and unification. 12 October 1988. PDF
  • 233. Fritz Henglein. Algebraic properties of semi-unification. November 1988.

 

Publications

  • B. N. Dickman. Review of "Symposium on Some Directions in High-Level Languages. ACM SIGPLAN Notices. 7, no. 5: pages 4-8, May 1972. ACM Digital Library

    The symposium, held at NYU on 22 May 1972, included lectures by James B. Morris, Edsger Dijkstra, Aiden Falkoff, Gerald Sussman, John Backus, and Andrew Yershov as well as lectures by NYU authors:

    • Jack Schwartz: Abstract and Concrete Algorithms.
    • Rudolph Krutar: An Algebra of Assignment.
    • David Shields: Optimization Algorithms in a Set Theoretic Language.
    • E. Milgrom: The Use of Sets in the Extensible Programming Language AEPL.
    • Kurt Maly: The Front End of the SETL Compiler.
    • Henry Warren: SETL Internals.
    • K. Kennedy: Some Optimization Strategies for High Level Languages.
  • W. R. Franta and Kurt Maly. The suitability of a very high level language (SETL) for simulation structuring and control. In: Robinet B. (eds) Programming Symposium. Lecture Notes in Computer Science, vol 19, 1974. Springer, Berlin, Heidelberg. SpringerLink
  • 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
  • J. T. Schwartz. Semantic and syntactic issues in programming. Bull. Amer. Math. Soc. Volume 80, Number 2, March, 1974, pages 185-206. Project Euclid (open acceess)
  • 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
  • Kurt Maly. A Programming Style. International Journal of Computer Mathematics, Volume 4, Issue 1-4, 1974, pages 309-325. Taylor & Francis Online
  • 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. Optimization of very high level languages. Computer Languages, Volume 1, 1975, in two parts:
    1. Value transmission and its corollaries. Issue 2, pages 161-194. ScienceDirect
    2. Deducing relationships of inclusion and membership. Issue 3, Pages 197-218. ScienceDirect
  • J. T. Schwartz. Automatic data structure choice in a language of very high level. Two versions were published:
    • 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
    • Commun. ACM Volume 18, Number 12 (Dec. 1975), pages 722–728. ACM Digital Library
  • H.S. Warren. Definition of the concept “vector” in set theoretic programming languages. Computers & Mathematics with Applications, Volume 2, Issue 1, 1976, Pages 73-83. ScienceDirect (open access)
  • Edith Deak, M. Shimasaki, and J. Schwartz. MIDL: a hybrid language of medium level. In: A. Ershov and C. H. A. Koster (eds). Methods of Algorithmic Language Implementation. Lecture Notes in Computer Science, vol 47. Springer, Berlin, Heidelberg, 1977. PDF / SpringerLink

    "The MIDL language currently being developed at NYU incorporates features of two other NYU languages (SETL and LITTLE), and welds these rather different languages together."

  • 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. Hierarchical design and efficient implementation in SETL: a case study. SIGPLAN Not. Volume 14, Number 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. Volume 5, Number 1, January 1983, pages 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, 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]

TODO: Add a full list of people who worked on LITTLE-based SETL.

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

  • Final version, identical to stlopt.opl above, together with the last changeset (smfl) in stlopt.upd from the .tar.xz file. 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.

    TODO: Change the next three items from Plone "files" to "pages", to allow viewing in browser.

    • 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

 

Programs and specifications written in SETL

  • See [Markstein 1975]. From the Abstract:

    "PSETL is a version of SETL which has been enlarged to allow the description of algorithms involving interrupts, parallelism, and to some extent, machine dependent features. Using PSETL, several operating systems are presented in detail. The first, a simple uniprogrammed batch system illustrates basic control mechanisms and scheduling. The second, a multiprogrammed batch system, shows additional complications which arise due to contention for resources and conflicting objectives. Our third system is interactive and includes data sharing capabilities."

  • See SETL Optimizer.
  • See Ada/Ed, a translator-interpreter for Ada 83: the first version was written in SETL (two-part NYU technical report).
  • Robert Paige. 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

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]

  • 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
  • See SETL Newsletter 116: "Catalog of SETL(C) Newsletters as of July 30, 1973".
  • See Part 6, The SETL(Cyrillic) Newsletters, in [Abes 1973], page 24.
  • L. Chernobrod. Plan for the development of a LITTLE compiler for the BESM/6. August 1973. Published as [LITTLE Newsletter 26].]. Listed in [Abes 1973].
  • See SETL Newsletter 74: "Project Plan for First Stage of Implementation".
  • D. Y. Levin. Experimental implementation of SETL. In: A. Ershov and C. H. A. Koster (eds). Methods of Algorithmic Language Implementation. Lecture Notes in Computer Science, vol 47. Springer, Berlin, Heidelberg, 1977. PDF / SpringerLink
  • Dave Shields. In Memory of Academician A. P. Ershov. The Wayward Word Press, 6 November 2006. Online at daveshields.wordpress.com

 

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, pages 330–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. Ph.D. thesis, University of Leeds, 1980. White Rose eTheses Online
  • 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, visit 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 and 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. APTS project. APTS was an experimental prototype system for constructing transformations, compilers, and other tools that manipulate and analyze programs. Circa 1998.
  • 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."

  • Robert Paige. Prototype SETL2 program to compute the maximum ready simulation relation between two finite transition processes, with sample input. Circa 1995. cs.nyu.edu

    A derivation of the program is presented in:

    • B. Bloom and R. Paige. Transformational Design and Implementation Of A New Efficient Solution To The Ready Simulation Problem. Science of Computer Programming, Volume 24, Number 3, 1995, pages 189-220. cs.nyu.edu
  • 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

 

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:

  • SETL is very large and is not useable on the small personal computers just beginning to become popuular in academia.
  • SETL is slow.
  • SETL is a compiled language and it was necessary to operate in batch mode.
  • SETL has many complex features that are not essential for educational purposes.
  • Functions are not first class objects in SETl.

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

  • 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 LaTeX source
  • Gary Marc Levin. An Introduction to ISETL. Department of Math and Computer Science, Clarkson University. Final version, circa 1990. PDF / original LaTeX source
  • Jennie Dautermann. ISETL: A language for learning mathematics. ISETL user's manual. West Educational Publishing, 1992.

Publications about ISETL

  • 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
  • Donald L. Muench. ISETL—interactive set language. Notices of the American Mathematical Society, Volume 37, Number 3, pages 276–279, March 1990. Review of the software package ISETL 2.0. PDF at ams.org
  • Ed Dubinsky. ISETL: A programming language for learning mathematics: In honor of Jack Schwartz on his 65th birthday. Communications on Pure and Applied Mathematics, Volume 48, Issue 9, 1995, pages 1027-1051. Wiley Online Library PDF at math.bas.bg

Publications using ISETL

TO DO:

 

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 code.

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

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

  • GNU SETL web site. setl.org/setl

Applications written in GNU SETL

  • Zhiqing Liu. Lazy SETL Debugging with Persistent Data Structures. Ph.D. thesis, Computer Science Department, New York University, November, 1994. PDF at nyu.edu

    A debugger based on maintaining a complete execution history, using persistent data structures, was built. It used the translator from Bacon's GNU SETL, together with a runtime system written in Scheme.

  • 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

 

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

  • 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.
  • Investigate Griffin (see also here and here).
  • 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
  • Lucy Chernobrod
  • James Cottrill
  • Martin Davis
  • Ernst-Erich Doberkat
  • Edward Dubinsky
  • Jay Earley
  • Stefan M. Freudenberger
  • Fritz Henglein
  • Richard Kenner
  • Philippe Kruchten
  • Richard Lethin
  • Gary Marc Levin
  • Annie Liu
  • Kurt Maly
  • Peter Markstein
  • Elie Milgrom
  • Eugenio Omodeo
  • Salvatore Paxia
  • Rob Pike
  • Diana Robinson
  • Jean-Pierre Rosen
  • Edith Schonberg (formerly Edith Deak)
  • Edward Schonberg
  • Peter Schow
  • Ron Schnell
  • Micha Sharir
  • David Shields
  • Mark Smotherman
  • W. Kirk Snyder
  • Nigel Williams
  • Denis Zorin

 

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]

  • 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, January 1966, pages 25–32. ACM Digital Library

    "I met John [Cocke] at Yorktown. I had written the paper -- the paper appeared in 1967 so this must have been around 1966 -- on parallel computing which they had somehow noticed and contacted me and I met him at that time. I believe he and Jack Bertram visited at New York University. After the visit I came up to Yorktown; I spent a summer at Yorktown learning something about how machine architecture was actually done, getting familiar with the basic issues and then continued as a consultant in the California days of the [ACS] project." [Van Deusen 1990]

    A management shuffle at the ACS project led to an exodus: "Among those leaving, Cocke took a sabbatical at the Courant Institute of Mathematical Sciences at New York University to work with Jacob Schwartz ..." [Smotherman et al. 2016]

  • 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

    See also: M. C. Harrison. Implementations of the SHARER2 time-sharing system. Commun. ACM, Volume 11, Number 12 (Dec. 1968), page 845. 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

    "John certainly had a great influence on me. He had in his head ... a whole host of compiler optimization techniques that were quite novel and became quite influential. The intellectual history there really is that that I learned them from him and wrote them down. They were written down first in a series of internal IBM technical reports connected with the ACS project that must have been, oh, 1972 or something like that. But those never were publicly distributed you know some people still have them as as old ACS workbook files and that sort of thing. Then I wrote them down in a set of notes on compilers -- these are the old Cocke and Schwartz notes on compilers, and I think from there they got into the more standard textbook literature - you know, Aho and Ullman [1977] and that sort of place. But I think the first publications of them were in that set of notes, the Cocke and Schwarz notes." [Van Deusen 1990]

    "I used this material to produce the optimizer for the compilers we wrote for IBM’s RISC machines. The optimizer and register allocator (invented by Greg Chaitin) were so effective that we made back-ends for the compiler to also generate code for the IBM/370, and the Motorola 68000, which IBM used extensively as an embedded microprocessor in many devices. For a while, I think IBM had more 68000 code than anyone else, and the high quality of the code harks back to the optimizations gotten from Cocke and Schwartz. I still have a copy, but the spine is completely worn off!" [Peter Markstein, personal communication, 27 March 2021]

  • ARTSPEAK was a language for teaching simple computer graphics conceived by Jack Schwartz and implemented and improved by several people at NYU and Hunter College.
    • Henry Mullish in cooperation with Jimmy Lewis. A Short Course in ARTSPEAK. Second edition, University Computer Center, New York University, November 1972.
    • Henry Mullish. The Art of Programming ARTSPEAK. Courant Institute of Mathematical Sciences, New York Univbersity, October 1974.
    • Caroline Wardle. 1976. ARTSPEAK: A graphics language for artists. In The papers of the ACM symposium on Graphic languages. Association for Computing Machinery, New York, NY, USA, 32–39. ACM Digital Library
    • Jehosua Friedmann. ARTSPEAK - A Computer Language for Young at Heart and The Art Lover. The Best of Creative Computing Volume 3, 1980. Online at atariarchives.org
    • Ron Schnell. ARTSPEAK Interpreter. Web-based interpreter, with ARTSPEAK Reference Guide. Online at artspeak.quogic.com
  • Alfred V. Aho and Jeffrey D. Ullman. Principles of Compiler Design. Addison-Wesley, 1977.
  • Mary S. Van Deusen, interviewer. Jack Schwartz Talks About John Cocke. 26 April 1990. YouTube video
  • Mark Smotherman, Ed Sussenguth, and Russ Robelen. The IBM ACS Project. IEEE Annals of the History of Computing, Volume 38, Number 1, January-March 2016, pages 60-74. IEEE Xplore

 

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]

  • 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. 1970. BALM: an extendable list-processing language. In Proceedings of the May 5-7, 1970, Spring Joint Computer Conference (AFIPS '70 (Spring)). Association for Computing Machinery, New York, NY, USA, pages 507–511. PDF at computer.org (open access)
  • M. C. Harrison. Introduction to BALM. Courant Institute, 1971.
  • M. C. Harrison. BALM reference manual. Courant Institute, 1971.
  • R. Paige. An MBALM to 6600 translator. M.S. Thesis, Courant Institute, 1972.
  • 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, 1973, pages 161–168. ACM Digital Library

    "The MBALM machine is designed to provide as much freedom as possible in the choice of representation in the object machine. No assumptions are made about the representation of code, for example, so the instruction which creates a procedure from a vector of integers representing the MBALM code is free to leave it as is, or to translate it into more efficient code. We have used this property to implement a faster version of the MBALM emulator which translates the MBALM code into machine code, which is then executed directly [Paige 1972]. The MBALM (and BALM4) programmer is unaware of this change, except that his program executes faster, and takes more memory."

  • Malcolm C. Harrison. Data-structures and programming. Scott, Foresman and Company, 1973.

    SETL Newsletter Number 5 ("Miscellaneous algorithms written in SETL", 18 November 1970), begins "Here are various algorithms from Harrison's 'Data structures and programming' and from other sources written out in SETL ..."

    Chapter 19 describes BALM, and Appendix B is a listing of a BALM translator written in BALM.

  • Malcolm Harrison and Stephanie Brown. BALM: The BALM programming language. Courant Institute of Mathematical Sciences, New York University, September 1974.
  • M. L. Griss and M. R. Swanson. MBALM/1700: A microprogrammed LISP machine for the Burroughs B1726. In Proceedings of the 10th annual workshop on Microprogramming (MICRO 10). IEEE Press, September, 1977, pages 15–25. ACM Digital Library

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

  • 1. A. Stein and J. Schwartz. I/O conventions and proposal; quoted strings; octal constants; user information for improved macroprocessor. October 1971.
  • 2. D. Goldberg. Files for the LITTLE project. 20 October 1971. PDF
  • 3. J. T. Schwartz. Possible future extensions to LITTLE. 1 November 1971. PDF
  • 4. J. T. Schwartz. A 'LITTLE' machine. 28 November 1971. PDF
  • 5. J. T. Schwartz. User information concerning LITTLE-to-FORTRAN translator. 29 November 1971. PDF
  • 6. No longer available.
  • 7. T. Stuart. LITTLE for minicomputers. 27 March 1972. PDF
  • 8. No longer available.
  • 9. D. Shields. Some suggestions for simplifying the preparation of SETL and LITTLE text: keyboard and lexical macros. March 1972.
  • 10. J. T. Schwartz. Interspersing macros. 2 April 1972. PDF
  • 11. R. Abes, H. Warren, and E. Milgrom. Input/output statements for LITTLE. Obsolete, April 1972.
  • 12. D. Shields. New conventions for LITTLE comments; use of semi-colon as statement terminator. 5 June 1972. PDF
  • 13. R. Abes and H. Warren. Macro capabilities for structured programming. July 1972.
  • 14. Pete Maclean. Mass storage utilisation in LITTLE. 21 July 1972. PDF
  • 15. A. Stein. [Partial multi-word facility.] Undated. PDF
  • 16. D. Shields. Some timing statistics for LITTLE. October 1972.
  • 17. R. Abes. Test packages for the LITTLE compiler. November 1972.
  • 18. J. Schwartz. A new array optimization for basic blocks, and some suggestions concerning the installation of optimizations into LITTLE. 10 November 1972. PDF
  • 19. Mike Brenner. Users' guide to LITTLE. May 1973. PDF
  • 20. David Shields. Remarks on structure of the SETL run-time library. 16 November 1972. PDF
  • 21. David Shields. Some proposals for improving accessibility of the LITTLE compiler. Appendix is comments by Kent Curtis. 4 December 1972. PDF
  • 22. David Shields. Examples of some LITTLE-generated code. 12 December 1972. PDF
  • 23. D. Shields. NAMESETS: A new way to handle global variables in LITTLE. 17 January 1973. PDF
  • 24. D. Shields. Proposals for the next phase of LITTLE development. 19 March 1973. PDF
  • 26. L. Chernobrod. Plan for the development of a LITTLE compiler for the BESM/6. This is also SETL (C) Newsletter #11. August 1973. PDF
  • 27. R. Abes. Multiple word items in LITTLE. October 1973.
  • 28. S. Brown. An intermediate language for the LITTLE compiler. 12 October 1973. PDF
  • 29. J. Schwartz. A medium-level semantic environment based on LITTLE. 1 September 1973. PDF
  • 30. J. Schwartz. Interrupt handling facilities in LITTLE. 28 December 1973. PDF
  • 31. J. Schwartz and A. Stein. Representation of BALM in LITTLE. January 1974. PDF
  • 32. P. Shaw. Interrupt handling in LITTLE: possible revisions. 4 February 1974. PDF
  • 32A. Claudette McDonald. Realisation of the LITTLE interrupt system described in Newsletters #30 and 32. 9 January 1975. PDF
  • 33. D. Shields. Guide to the LITTLE language. March 1974.
  • 34. R. Abes. Input/output statements for LITTLE. (This will replace LITTLE Newsletter 11.) To appear shortly.
  • 35A. I. Chakravarty, H. Jacobs, M. Marks, and E. McGovern. Design of a LITTLE code generator for the ADAGE agt-30. January 1975.
  • 35B. R. Aronson, M. Macias, D. Patel, and D. Reilly. LITTLE code generator for the IBM 1130. January 1975.
  • 35C. S Gold, A. Carduso, and G. Lucans. LITTLE code generator for the UNIVAC 1108 - preliminary remarks. January 1975.
  • 35D. R. Rosenthal, A. Eng, M. Potmesil, and A. Fogel. LITTLE code generator for the PDP-8. January 1975.
  • 35E. R. Colle, D. Farkas, and J. Farrelly. LITTLE code generator for the PDP-11. January 1975.
  • 36. E. Desk. Run-time considerations for MIDL. 1 November 1974. PDF
  • 36A. M. Shimasaki. Illustrative examples of MIDL. 10 November 1974. PDF
  • 37. Edith Deak. Proposal for MIDL (GLITTLE). September 1974. PDF
  • 38. G. Story. Guide to the MIDL language. August 1975.
  • 39. T. Stuart. Post-partum reflections on the Honeywell minicomputer implementation of LITTLE. 15 September 1975. PDF
  • 40. Art. Grand. Standardised and more efficient communication with the LITTLE codegenerators. 26 November 1975. PDF
  • 41. R. Dewar. Dynamic arrays in LITTLE. 1 December 1975. PDF
  • 42. T. Stuart. A parser-code generator interface. 20 July 1976. PDF
  • 42A. T. Stuart. A parser-code generator interface: Appendix. 20 July 1976. PDF

Documentation

  • David Shields. Guide to the LITTLE language. 4 October 1982. PDF

    Describes the syntax and semantics of the language. Includes examples.

  • David Shields. LITTLE user manual. 8 December 1981. PDF

    Describes the implementation of LITTLE, including lexical scan, parse and semantic analysis, code generation, and library (used at compile time and also at runtime of generated code).

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) to plan 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.

  • LEX: Lexical scan phase. ltllex.opl
  • GEN: Parse and semantic analysis phase. ltlgen.opl
  • ASM: Code generation phase, specific to a particular target machine. This version is for the Digital Equipment Corporation DECsystem-10. By Richard Kenner and David Shields, based on the LITTLE code generator for the IBM System/370 by Kenner. ltlasm.opl
  • LIB: Run-time library for the LITTLE system (compile time and run time). ltllib.opl
  • SYN: Syntax generator for the LITTLE system. By Edith Deak and David Shields. ltlsyn.opl

    "This program translates an annotated BNF-like description of a programming language grammar into tables and text fragments which form the central part of a parser for the language, which consists of an interpreter for an abstract parsing machine.

  • GRM: Grammars for SYN and LITTLE. By Edith Deak and David Shields. ltlgrm.opl
  • REF: Cross-reference processor of the LITTLE compiler. By David Shields. ltlref.opl
  • TST: Various test programs for the LITTLE system software, principally the compiler. ltltst.opl
  • UPD: Source maintenance program. By David Shields. ltlupd.opl
  • UTL: Various utility programs, some machine dependent and some principally of interest to the CDC 6600, IBM System/370, or DEC VAX implementations. By David Shields, except objname by Richard Kenner. ltlutl.opl

 

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

  • 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.

« September 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
 

Powered by Plone CMS, the Open Source Content Management System

This site conforms to the following standards: