SETL

Last updated
SETL
Paradigm multi-paradigm: imperative, procedural, structured, object-oriented
Designed by (Jack) Jacob T. Schwartz
Developer Courant Institute of Mathematical Sciences
First appeared1969;55 years ago (1969)
Stable release
1.1 / January 7, 2005;19 years ago (2005-01-07)
Typing discipline Dynamic
Website setl.org
Influenced by
ALGOL 60
Influenced
SETL2, ISETL, SETLX, Starset, ABC

SETL (SET Language) is a very high-level programming language [1] based on the mathematical theory of sets. [2] [3] It was originally developed at the New York University (NYU) Courant Institute of Mathematical Sciences in the late 1960s, by a group containing (Jack) Jacob T. Schwartz, [1] [3] R.B.K. Dewar, and E. Schonberg. [1] Schwartz is credited with designing the language. [4]

Contents

Design

SETL provides two basic aggregate data types: (unordered) sets, and tuples. [1] [2] [5] The elements of sets and tuples can be of any arbitrary type, including sets and tuples themselves, except the undefined value om [1] (sometimes capitalized: OM). [6] Maps are provided as sets of pairs (i.e., tuples of length 2) and can have arbitrary domain and range types. [1] [5] Primitive operations in SETL include set membership, union, intersection, and power set construction, among others. [1] [7]

SETL provides quantified boolean expressions constructed using the universal and existential quantifiers of first-order predicate logic. [1] [7]

SETL provides several iterators to produce a variety of loops over aggregate data structures. [1] [8]

Examples

Print all prime numbers from 2 to N:

print([n in [2..N] | forall m in {2..n - 1} | n mod m > 0]);

The notation is similar to list comprehension.

A factorial procedure definition:

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

A more conventional SETL expression for factorial (n > 0):

*/[1..n]

Uses

Implementations of SETL were available on the DEC VAX, IBM/370, SUN workstation and APOLLO. [9] In the 1970s, SETL was ported to the BESM-6, ES EVM and other Russian computer systems. [10]

SETL was used for an early implementation of the programming language Ada, named the NYU Ada/ED translator. [11] This later became the first validated Ada implementation, certified on April 11, 1983. [12]

According to Guido van Rossum, "Python's predecessor, ABC, was inspired by SETL -- Lambert Meertens spent a year with the SETL group at NYU before coming up with the final ABC design!" [13]

Language variants

SET Language 2 (SETL2), a backward incompatible descendant of SETL, was created by Kirk Snyder of the Courant Institute of Mathematical Sciences at New York University in the late 1980s. [14] Like its predecessor, it is based on the theory and notation of finite sets, but has also been influenced in syntax and style by the Ada language. [14]

Interactive SET Language (ISETL) is a variant of SETL used in discrete mathematics. [15]

GNU SETL is a command-line utility that extends and implements SETL. [16]

Related Research Articles

<span class="mw-page-title-main">Ada (programming language)</span> High-level programming language first released in 1980

Ada is a structured, statically typed, imperative, and object-oriented high-level programming language, inspired by Pascal and other languages. It has built-in language support for design by contract (DbC), extremely strong typing, explicit concurrency, tasks, synchronous message passing, protected objects, and non-determinism. Ada improves code safety and maintainability by using the compiler to find errors in favor of runtime errors. Ada is an international technical standard, jointly defined by the International Organization for Standardization (ISO), and the International Electrotechnical Commission (IEC). As of May 2023, the standard, called Ada 2022 informally, is ISO/IEC 8652:2023.

In computer science, denotational semantics is an approach of formalizing the meanings of programming languages by constructing mathematical objects that describe the meanings of expressions from the languages. Other approaches providing formal semantics of programming languages include axiomatic semantics and operational semantics.

In mathematics, a unary operation is an operation with only one operand, i.e. a single input. This is in contrast to binary operations, which use two operands. An example is any function f : AA, where A is a set. The function f is a unary operation on A.

<span class="mw-page-title-main">GNAT</span> Free-software compiler for the Ada programming language

GNAT is a free-software compiler for the Ada programming language which forms part of the GNU Compiler Collection (GCC). It supports all versions of the language, i.e. Ada 2012, Ada 2005, Ada 95 and Ada 83. Originally its name was an acronym that stood for GNU NYU Ada Translator, but that name no longer applies. The front-end and run-time are written in Ada.

Template metaprogramming (TMP) is a metaprogramming technique in which templates are used by a compiler to generate temporary source code, which is merged by the compiler with the rest of the source code and then compiled. The output of these templates can include compile-time constants, data structures, and complete functions. The use of templates can be thought of as compile-time polymorphism. The technique is used by a number of languages, the best-known being C++, but also Curl, D, Nim, and XL.

<span class="mw-page-title-main">F Sharp (programming language)</span> Microsoft programming language

F# is a general-purpose, high-level, strongly typed, multi-paradigm programming language that encompasses functional, imperative, and object-oriented programming methods. It is most often used as a cross-platform Common Language Infrastructure (CLI) language on .NET, but can also generate JavaScript and graphics processing unit (GPU) code.

SPITBOL is a compiled implementation of the SNOBOL4 programming language. Originally targeted for the IBM System/360 and System/370 family of computers, it has now been ported to most major microprocessors including the SPARC. It was created by Robert Dewar and Ken Belcher, who were then at the Illinois Institute of Technology.

<span class="mw-page-title-main">While loop</span> Control flow statement for repeating execution until a condition is met

In most computer programming languages, a while loop is a control flow statement that allows code to be executed repeatedly based on a given Boolean condition. The while loop can be thought of as a repeating if statement.

Set theoretic programming is a programming paradigm based on mathematical set theory. One example of a programming language based on this paradigm is SETL. The goal of set theoretic programming is to improve programmer speed and productivity significantly, and also enhance program clarity and readability.

In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recursion is particularly useful, and is often easy to optimize in implementations.

Programming Language Design and Implementation (PLDI) is an academic conference in computer science, in particular, in the study of programming languages and compilers. PLDI is organized by the Association for Computing Machinery under the SIGPLAN interest group.

<span class="mw-page-title-main">Courant Institute of Mathematical Sciences</span> Division of New York University, US (founded 1935)

The Courant Institute of Mathematical Sciences is the mathematics research school of New York University (NYU). Founded in 1935, it is named after Richard Courant, one of the founders of the Courant Institute and also a mathematics professor at New York University from 1936 to 1972, and serves as a center for research and advanced training in computer science and mathematics. It is located on Gould Plaza next to the Stern School of Business and the economics department of the College of Arts and Science.

<span class="mw-page-title-main">Jacob T. Schwartz</span> American mathematician

Jacob Theodore "Jack" Schwartz was an American mathematician, computer scientist, and professor of computer science at the New York University Courant Institute of Mathematical Sciences. He was the designer of the SETL programming language and started the NYU Ultracomputer project. He founded the New York University Department of Computer Science, chairing it from 1964 to 1980.

The New York University's Ultracomputer is a significant processor design in the history of parallel computing. The system has N processors, N memories, and an N log N message-passing switch connecting them. The system supported an innovative fetch-and-add process coordination instruction, and the custom VLSI network switches could combine references from several processors into a single reference, to reduce memory contention.

<span class="mw-page-title-main">Yann LeCun</span> French computer scientist (born 1960)

Yann André LeCun is a French-American computer scientist working primarily in the fields of machine learning, computer vision, mobile robotics and computational neuroscience. He is the Silver Professor of the Courant Institute of Mathematical Sciences at New York University and Vice-President, Chief AI Scientist at Meta.

This article describes the features in the programming language Haskell.

Haskell is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research, and industrial applications, Haskell has pioneered a number of programming language features such as type classes, which enable type-safe operator overloading, and monadic input/output (IO). It is named after logician Haskell Curry. Haskell's main implementation is the Glasgow Haskell Compiler (GHC).

<span class="mw-page-title-main">Robert Dewar</span> Computer scientist

Robert Berriedale Keith Dewar was an American computer scientist and educator. He helped to develop programming languages and compilers and was an outspoken advocate of freely licensed open-source software. He was a cofounder, CEO, and president of the AdaCore software company. He was also an enthusiastic amateur performer and musician, especially with the Village Light Opera Group in New York City.

References

  1. 1 2 3 4 5 6 7 8 9 Schwartz, J. T.; Dewar, R. B. K.; Schonberg, E.; Dubinsky, E. (1986). "Programming with Sets". SpringerLink: v–vii, 2, 48, 53, 57–58, 63, 113ff. doi:10.1007/978-1-4613-9575-1.
  2. 1 2 "GNU SETL Om". setl.org. Retrieved 2024-04-24.
  3. 1 2 Markoff, John (2009-03-04). "Jacob T. Schwartz, 79, Restless Scientist, Dies". The New York Times. ISSN   0362-4331 . Retrieved 2024-04-24.
  4. Computational Logic and Set Theory. pp. vii. doi:10.1007/978-0-85729-808-9.
  5. 1 2 "CHAPTER 2". www.settheory.com. Retrieved 2024-04-24.
  6. "CHAPTER 3". www.settheory.com. Retrieved 2024-04-24.
  7. 1 2 "CHAPTER 3". www.settheory.com. Retrieved 2024-04-24.
  8. "CHAPTER 4". www.settheory.com. Retrieved 2024-04-24.
  9. J.T. Schwartz; R.B.K. Dewar; E. Dubinsky; E. Schonberg (1986). Programming with sets. An Introduction to SETL. Springer-Verlag New York Inc. ISBN   978-1-4613-9577-5.
  10. И.В. Поттосин, ed. (2001). Становление новосибирской школы программирования (мозаика воспоминаний) [Formation of the Novosibirsk school of programming (mosaic of memories)](PDF) (in Russian). Новосибирск: Институт систем информатики им. А. П. Ершова СО РАН. pp. 106–113.
  11. Dewar, Robert B. K.; Fisher Jr., Gerald A.; Schonberg, Edmond; Froelich, Robert; Bryant, Stephen; Goss, Clinton F.; Burke, Michael (November 1980). "The NYU Ada translator and interpreter". Proceeding of the ACM-SIGPLAN symposium on Ada programming language - SIGPLAN '80. Vol. 15. pp. 194–201. doi:10.1145/948632.948659. ISBN   0-89791-030-3. S2CID   10586359.
  12. SofTech Inc., Waltham, MA (1983-04-11). "Ada Compiler Validation Summary Report: NYU Ada/ED, Version 19.7 V-001". Archived from the original on June 7, 2017. Retrieved 2010-12-16.{{cite web}}: CS1 maint: multiple names: authors list (link)
  13. Python-Dev: SETL (was: Lukewarm about range literals)
  14. 1 2 "SETL2 - EDM2". www.edm2.com. Retrieved 2024-04-24.
  15. Baxter Hastings, Nancy; Dubinsky, Ed; Levin, Gary (1989). Learning discrete mathematics with ISETL. New York: Springer-Verlag. ISBN   978-0-387-96898-8.
  16. "GNU SETL". setl.org. Retrieved 2024-04-24.

Further reading