SETL(ID:1268/set002)

Set based programming language 

SET Language. Courant Inst, early 70's. A very high level set-oriented language. Data types include sets (unordered collections), tuples (ordered collections) and maps (collections of ordered pairs). Expressions may include quantifiers ('for each' and 'exists').
The first Ada translator was written in SETL.

The optimisation routines developed in making the SETL compilers have been quite influential, especially in quantification and automatic type discovery.
Places
Structures:
Related languages
BALM => SETL   Influence
SETL => BALMSETL   Evolution of
SETL => Griffin   Successor
SETL => GYVE   Extension of
SETL => ISETL   Adaptation of
SETL => PSETL   Extension of
SETL => SETL/E   Extension of
SETL => SETL2   Evolution of
SETL => SETLB   Subset
SETL => SetLog   Derivation of

Samples:
References:
  • Schwartz, Jacob T. "Set Theory as a Language for Program Specification and Programming". Courant Institute of Mathematical Sciences, New York University, 1970. view details
  • Dickman, B. N.: Review of "Symposium on some directions in high-level languages", May 22-23, 1972, New York University view details
          in SIGPLAN Notices 7(05) May 1972 view details
  • Sammet, Jean E., "Roster of Programming Languages 1972" 251 view details
          in Computers & Automation 21(6B), 30 Aug 1972 view details
  • Schwartz, Jacob T. "Abstract and Concrete Algorithms" view details
          in Courant Symposium on High Level Level Languages, Computer Science Department of the Courant Institute of Mathematical Sciences, May 22, 1972 view details
  • Shields, David "Optimization Algorithms in a Set Theoretic Language" view details
          in Courant Symposium on High Level Level Languages, Computer Science Department of the Courant Institute of Mathematical Sciences, May 22, 1972 view details
  • Warren, Henry S. "SETL Internals" view details
          in Courant Symposium on High Level Level Languages, Computer Science Department of the Courant Institute of Mathematical Sciences, May 22, 1972 view details
  • Morris, J.B. A Comparison of Madcap and SETL, Los Alamos Sci. Lab., University of California, Los Alamos, N. Mexico 1973 view details
          in Courant Symposium on High Level Level Languages, Computer Science Department of the Courant Institute of Mathematical Sciences, May 22, 1972 view details
  • Sammet, Jean E. "Roster of Programming Languages for 1973" p147 view details
          in ACM Computing Reviews 15(04) April 1974 view details
  • Schwartz, J. "On Programming, An Interim Report on the SETL Project", Computer Science Department, Courant Institute of Math. Sci., New York University (1973). view details
          in ACM Computing Reviews 15(04) April 1974 view details
  • Stock, Marylene and Stock, Karl F. "Bibliography of Programming Languages: Books, User Manuals and Articles from PLANKALKUL to PL/I" Verlag Dokumentation, Pullach/Munchen 1973 530 view details Abstract: PREFACE  AND  INTRODUCTION
    The exact number of all the programming languages still in use, and those which are no longer used, is unknown. Zemanek calls the abundance of programming languages and their many dialects a "language Babel". When a new programming language is developed, only its name is known at first and it takes a while before publications about it appear. For some languages, the only relevant literature stays inside the individual companies; some are reported on in papers and magazines; and only a few, such as ALGOL, BASIC, COBOL, FORTRAN, and PL/1, become known to a wider public through various text- and handbooks. The situation surrounding the application of these languages in many computer centers is a similar one.

    There are differing opinions on the concept "programming languages". What is called a programming language by some may be termed a program, a processor, or a generator by others. Since there are no sharp borderlines in the field of programming languages, works were considered here which deal with machine languages, assemblers, autocoders, syntax and compilers, processors and generators, as well as with general higher programming languages.

    The bibliography contains some 2,700 titles of books, magazines and essays for around 300 programming languages. However, as shown by the "Overview of Existing Programming Languages", there are more than 300 such languages. The "Overview" lists a total of 676 programming languages, but this is certainly incomplete. One author ' has already announced the "next 700 programming languages"; it is to be hoped the many users may be spared such a great variety for reasons of compatibility. The graphic representations (illustrations 1 & 2) show the development and proportion of the most widely-used programming languages, as measured by the number of publications listed here and by the number of computer manufacturers and software firms who have implemented the language in question. The illustrations show FORTRAN to be in the lead at the present time. PL/1 is advancing rapidly, although PL/1 compilers are not yet seen very often outside of IBM.

    Some experts believe PL/1 will replace even the widely-used languages such as FORTRAN, COBOL, and ALGOL.4) If this does occur, it will surely take some time - as shown by the chronological diagram (illustration 2) .

    It would be desirable from the user's point of view to reduce this language confusion down to the most advantageous languages. Those languages still maintained should incorporate the special facets and advantages of the otherwise superfluous languages. Obviously such demands are not in the interests of computer production firms, especially when one considers that a FORTRAN program can be executed on nearly all third-generation computers.

    The titles in this bibliography are organized alphabetically according to programming language, and within a language chronologically and again alphabetically within a given year. Preceding the first programming language in the alphabet, literature is listed on several languages, as are general papers on programming languages and on the theory of formal languages (AAA).
    As far as possible, the most of titles are based on autopsy. However, the bibliographical description of sone titles will not satisfy bibliography-documentation demands, since they are based on inaccurate information in various sources. Translation titles whose original titles could not be found through bibliographical research were not included. ' In view of the fact that nany libraries do not have the quoted papers, all magazine essays should have been listed with the volume, the year, issue number and the complete number of pages (e.g. pp. 721-783), so that interlibrary loans could take place with fast reader service. Unfortunately, these data were not always found.

    It is hoped that this bibliography will help the electronic data processing expert, and those who wish to select the appropriate programming language from the many available, to find a way through the language Babel.

    We wish to offer special thanks to Mr. Klaus G. Saur and the staff of Verlag Dokumentation for their publishing work.

    Graz / Austria, May, 1973
          in ACM Computing Reviews 15(04) April 1974 view details
  • Franta, William R. and Kurt Maly "Simulation Structures and SETL" pp208-212 view details
          in Rosenfeld, Jack L. (Ed.): Information Processing 74, Proceedings of IFIP Congress 74, Stockholm, Sweden, August 5-10, 1974 view details
  • Leavenworth, Burt M.; Sammet, Jean E. "An overview of nonprocedural languages" pp1-12 view details Abstract: This paper attempts to describe some of the basic characteristics and issues involving the class of programming languages commonly referred to as ?nonprocedural? or ?very high level?. The paper discusses major issues such as terminology, relativeness, and arbitrary sequencing. Five features of nonprocedural languages are described, and a number of specific languages are discussed briefly. A short history of the subject is included.
    Extract: SETL and MADCAP
    We will discuss the languages SETL (Schwartz, 1973) and MADCAP (Morris and Wells, 1972) as representative of a class of set oriented langauges.
    [...]
    SETL is a very high level mathematically oriented language.Its important composite data structures are finite unordered sets, tuples, and functions. The set operations in both languages are very similar except that SETL allows heterogeneous sets. Functions in both SETL and MADCAP are not only available in the conventional sense but can also be represented by sets of tuples, i.e., relations. Both languages have a "set former" capability which is to say that they provide associative referencing on the elements of sets. SETL has a "compound operator" which works very much like the APL reduction operator, and both languages have other constructions which can be used to obviate loops in most cases.
    MADCAP has a backtracking facility (not currently provided in SETL) as well as a control structure called an iterative expression.
    As an example of the power of SETL, consider the following expression which specifies the prime numbers between 2 and lO0:
    {P,2 <= P <= lO0 + (v 2 <: N < P ÷ (P//N)NE. 0)}
    which can be read in English as "the set of P's between 2 and 1O0 such that for every N greater than or equal to 2 and less than P the remainder of P/N is not equal to zero".
    The above specification is obviously not an efficient one; a practical program at the very least would just consider the odd numbers from 3 to lO0.
          in Proceedings of the ACM SIGPLAN symposium on Very high level languages, March 28-29, 1974, Santa Monica, California, United States view details
  • Schwartz, J. T. "Automatic and semiautomatic optimization of SETL" view details
          in Proceedings of the ACM SIGPLAN symposium on Very high level languages, March 28-29, 1974, Santa Monica, California, United States view details
  • Deak, Edith; Shimasaki, M.; Schwartz, J. "MIDL: a hybrid language of medium level" 277-289 view details
          in Koster, C.H.A. "Methods of Algorithmic Language Implementation", LNCS 47, Springer 1977 view details
  • Schwartz, J. T. "Automatic data structure choice in a language of very high level" view details Abstract: SETL is a set-theoretically oriented language of very high level whose repertoire of semantic objects includes finite sets, ordered n-tuples, and sets of ordered n-tuples usable as mappings. This paper describes the structure of an optimizer for this language. Among other methods of interest, the optimizer uses techniques which allow relations of inclusion and membership to be established, the domains and ranges of (tabulated) mappings to be estimated from above and below, and the single-valuedness of (tabulated) mappings to be proved. Once facts of this kind have been established, automatic choice of data structures becomes possible. The methods employed are based upon, and extend, known techniques of data flow analysis.
          in [ACM] CACM 18(12) (Dec 1975) view details
  • Axford, T.H., Diana Burkhardt, W.P. Dodd, Susan Laflin, D.G. Parkyn and P. Ramsay "ATOL:* A Simple Language with Powerful Data Structuring Facilities" Computer Centre, University of Birmingham, Birmingham U.K. view details
          in [ACM] CACM 18(12) (Dec 1975) view details
  • Dewar, Robert; Grand, Arthur; Liu, Cheng; Schonberg, Edmond; and Schwartz, Jacob "SETL as a tool for generation of quality software" in "Constructing quality software" pp353-366 view details Abstract: "Pure" SETL is a language of very high level, allowing algorithms to be programmed rapidly and concisely with minimum attention to specification of detailed data structures. A representation sublanguage adds a system of declarations which allow the user of the language to specify the data structures that will be used to implement an algorithm which has already been written in pure SETL, without necessitating any rewriting of the algorithm itself.
          in Hibbard, P. G. and Schuman, S. A. (Eds.), Proc. IFIP working conference on constructing quality software, Elsevier North-Holland, Inc., New York, 1978 view details
  • Sammet, Jean E "Roster of programming languages for 1976-77" pp56-85 view details
          in SIGPLAN Notices 13(11) Nov 1978 view details
  • Dewar, Robert K.; Arthur and Ssu-Cheng Liu; and Schwartz, Jacob T. and Schonberg, Edmond "Programming by Refinement, as Exemplified by the SETL Representation Sublanguage" view details Abstract: “Pure” SETL is a language of very high level allowing algorithms to be programmed rapidly and succintly. SETL's representation sublanguage adds a system of declarations which allow the user of the language to control the data structures that will be used to implement an algorithm which has already been written in pure SETL, so as to improve its efficiency. Ideally no rewriting of the algorithm should be necessary. The facilities provided by the representation sublanguage and the run-time data structures that it can generate are described; based on this a heuristic which uses some of the methods of global program analysis and which should be capable of selecting an acceptably efficient representation automatically is given. DOI
          in TOPLAS 1(1) Jan 1979 view details
  • Schonberg, Edmond; Schwartz, Jacob T.; and Sharir, Micha Automatic data structure selection in SETL. in Conference record of the 6th annual ACM symposium on principles of programming languages (San Antonio, Texas, Jan. 29- 31. 1979), ACM, New York, 1979 pp197-210 view details
          in TOPLAS 1(1) Jan 1979 view details
  • Barnard, D. T., review of Dewar 1978 view details Extract: Review
    SETL is a language for expressing algorithms in a high level set-oriented notation. As originally defined, the language allowed the expression of algorithms without any specification of the storage structure to be used in implementing sets. This paper defines an extended language that allows a programmer to choose among several different representations for particular data structures. A declaration capability has been added to SETL (this is called a "representation sublanguage" in the paper). The intention of the declarations is to increase efficiency by improving on the default representation, rather than to facilitate strong type checking. Minor changes in the declaration of a set can result in major changes in computation time. The problem of topological sorting is treated at length in the paper as an example to illustrate the concepts.
    Unfortunately, a knowledge of the way SETL maps data structures into physical storage is required to exploit the power of the declaration mechanism. It seems easy to write declarations that will not lead to more efficient programs. In addition, the concern with efficiency seems somewhat out of place in the context of a language like SETL that is designed for the very abstract expression of algorithms. Finally, examples of more substantial problems solved using SETL, made more efficient via added declarations, are required to demonstrate the effectiveness of the language.
    D. T. Barnard, Kingston, Ont., Canada

          in ACM Computing Reviews 21(02) Feb 1980 view details
  • Davis, T. M. review of Schonberg 1979 view details Abstract: This paper describes the authors' research into the automatic generation of data structures for high-level language programs. The language chosen for use is SETL, a set-manipulation language with very powerful data structuring mechanisms. The first sections describe the language itself, including its algorithmic and set operations. (Just this section by itself is a good, quick introduction for those interested in an acquaintance with the language.) The next topic discussed, with an example, is the set of data structures used by the SETL system to represent the various set constructs permitted.

    The second half of the paper is a moderately detailed coverage of the authors' attempts to give SETL the ability to choose its own data structures for any given program. This is, in their words, "an automatic technique which enables the SETL programmer to code his program in a high-level, relatively independent of specific data structure, and yet allows a reasonable level of efficiency to be achieved."



          in ACM Computing Reviews 21(11) November 1980 view details
  • Robert B.K. Dewar, E. Schonberg, J.T. Schwartz, "Higher-level programming; introduction to the use of the set-theoretic programming language SETL", New York, Computer Science Department, Courant Institute of Mathematics, New York University, 1981 view details
          in ACM Computing Reviews 21(11) November 1980 view details
  • Freudenberger, Stefan M.; Schwartz, Jacob T.; and Micha Sharir "Experience with the SETL Optimizer" pp26-45 view details Abstract: The structure of an existing optimizer for the very high-level, set theoretically oriented programming language SETL is described, and its capabilities are illustrated. The use of novel techniques (supported by state-of-the-art interprocedural program analysis methods) enables the optimizer to accomplish various sophisticated optimizations, the most significant of which are the automatic selection of data representations and the systematic elimination of superfluous copying operations. These techniques allow quite sophisticated data-structure choices to be made automatically. DOI
          in TOPLAS 5(1) January 1983 view details
  • Gries, D. and J. Prins (1985). "A new notion of encapsulation." view details Abstract: Generally speaking, a `module' is used as an `encapsulation mechanism' to tie together a set of declarations of variables and operations upon them. Although there is no standard way to instantiate or use a module, the general idea is that a module describes the implementation of all the values of a given type. We believe that this is too inflexible to provide enough control: one should be able to use different implementations (given by different modules) for variables (and values) of the same type. When incorporated properly into the notation, this finer grain of control allows one to program at a high level of abstraction and then to indicate how various pieces of the program should be implemented. It provides simple, effective access to earlier-written modules, so that they are usable in a more flexible manner than is possible in current notations. Existing languages such as SETL, Smalltalk, ML, CLU, and Ada already provide some of the capabilities listed above, but our new notion may provide more flexibility and ease of use. The paper is organized as follows. Section 2 gives some basic ground rules for our programming notation and outlines our idea for encapsulation. Section 3 discusses some of the issues involved. Section 4 outlines proofs of correctness. Section 5 discusses a `real' example in detail. This is a report of ongoing work, and not a finished product.     
          in SIGPLAN Notices 20(07) July 1985 (Proceedings of the ACM SIGPLAN 85 symposium on Language issues in programming environments) view details
  • Schwartz, Jacob T. et al, "Programming With Sets An Introduction to SETL", Springer 1986. view details
          in SIGPLAN Notices 20(07) July 1985 (Proceedings of the ACM SIGPLAN 85 symposium on Language issues in programming environments) view details
  • Bacon, David "SETL for Internet Data Processing" PhD NYU 2000 view details
          in SIGPLAN Notices 20(07) July 1985 (Proceedings of the ACM SIGPLAN 85 symposium on Language issues in programming environments) view details