1 THE SETL PROGRAMMIG LAGUAGE TAPASYA PATKI POOJA BHANDARI Department of Computer Science University of Arizona Abstract This paper presents a study on the language SETL, which is a very-high level, wide spectrum programming language based on the mathematical theory of sets, primarily used for transformational programming, compiler optimization, algorithm design and data processing. We describe the language features and delve into the issues from the compiler’s perspective. 1 HISTORY In the late 1960s, researchers were addressing compiler optimization problems, and a need for an expressive, high-level language that supported set-intensive algorithm design was felt. SETL, introduced by Prof. Jacob Schwartz at the New York University (NYU) at the Courant Institute of Mathematical Sciences in 1970, was conceived to meet this purpose. Prof. Schwartz, who obtained his PhD from Yale University in 1951, is a renowned mathematician and a computer scientist, and currently holds professorship at NYU. Most of the research and developmental work related to SETL has been carried out at NYU. Modern computer programming languages can be broadly grouped into Object-Oriented languages, Functional programming languages, and Scripting languages. Since SETL was developed during 1970s, SETL does not strictly belong to the above classification. While SETL provides no support for object-orientation, newer versions and dialects of SETL, like SETL2 and ISETL support object oriented and graphics programming. SETL is a very powerful language, and has various application domains. The first ADA translator, ADA/Ed and the first implementation of AIML, the markup language for Artificial Intelligence, were written in it. Python’s predecessor ABC, is also heavily influenced by SETL. 2 KEY FEATURES SETL is an interpreted, very high-level, dynamic language that provides for set-theoretic syntax and semantics. Derived from the Algol-family, it bears syntactic similarity with C and Perl. It offers the programmer a lot of flexibility by letting the code be independent of any data-structure implementation details, and thus strives to put the needs of the programmer ahead of those of the machine. SETL is more-or-less an imperative, sequential language with assignment, and partial support for functional programming through backtracking. Program development in SETL is facilitated by the use of fewer and more abstract operations. Typically, a small SETL program can do a lot.. A variable in SETL is weakly and dynamically typed, and storage allocation is done at run time. SETL has value semantics, and does not allow pointer manipulations. In this respect, SETL realizes Hoare's ideal of programming without pointers. This brings with it a substantial measure of orthogonality and robustness.2 SETL is called a wide spectrum language (WSL) as it allows all levels of abstraction from problem specifications down to hardware level implementations. This is the most important feature of language that makes the language suitable for rapid prototyping and transformational programming. 3 TYPES, OPERATORS AD SCOPIG The conventional mathematical and logical operations are supported in SETL [1,2,3]. An identifier is not statically associated with a particular data-type in this language. Instead, depending upon the last value assigned to a variable, the type of the variable is set. Also, the operator is applied depending upon the type-context of its operands, for example, a ‘+’ may mean an integer addition or a string concatenation. Scalar Data Types SETL primarily has two levels of data-typing - Simple/ Scalar types, and Compound types. Simple types include atom, integer, real, string, and boolean. There are no limitations on the size and the range of these simple types (except in situations where there might be hardware constraints). Compound Data Types Compound data types in SETL are in the form of sets, tuples and maps. A set is an unordered collection of distinct elements of arbitrary types. Sets are represented by listing the elements within the curly braces { }. SETL does not allow sets of infinite size. Various set operators are listed in Table 1. The following example illustrates the basic set operations: Ex 1: Set A tuple is an ordered sequence of arbitrary types, with support for direct indexing. Tuples are similar to one dimensional vectors, but possess greater degree of flexibility. The components of a tuple are stored at contiguous locations within a dynamically managed memory area. The elements of a tuple can be accessed using subscripting. If a previously defined value in a tuple is set to om, a hole is created in the tuple. Om, or omega, is a special type in SETL which represents an undefined value. Various tuple operators are listed in Table 1. The following example depicts tuple usage: Ex 2: Tuple a := {2, 3, 4}; b := {3, 5, 6}; c := a + b; $ c = {2, 3, 4, 5, 6} x := c with 9; $ c = {2, 3, 4, 5, 6}, x = {2, 3, 4, 5, 6, 9} x less:=9; $ x = {2, 3, 4, 5, 6} p := {1,2} e := arb p; $ e = 1 or 2 tuple := [ 2, ’xyz’, [1, 2, 3], 44 ]; a:=tuple(1); $ a := 2 tuple(1) := 7; $ tuple = [ 7, ’xyz’, [1, 2, 3], 44 ] tuple(3) := om; $ creates a hole in the tuple3 A map is simply a set of tuples of length 2, where the first element of each tuple is said to belong to the domain of the map, and the second element to the range. More formally, given sets A and B, a map is a subset F of the Cartesian Product A x B, defined under the relation b = f (a), where a ϵ A, b ϵ B, and f is a function. Single valued maps are for functions and multi-valued maps are for relations. Maps provide simple and easy to use facility for representing data structures and databases [20]. SETL implements the domain and range of a map by calls. All the map operators are discussed in Table 1. The following example shows all the properties of maps: Ex 3: Map Operators Operators Function + Set Union/ Tuple Concatenation - Set difference * less from arb Set Intersection Removes an element from a set Removes an element and assigns remaining Selects an arbitrary element # Highest
View Full Document
Unlocking...