Programming with Sets

The programming language SETL is a relatively new member of the so-called "very-high-level" class of languages, some of whose other well-known mem bers are LISP, APL, SNOBOL, and PROLOG. These languages all aim to reduce the cost of programming, recognized today as a main obstacle to future progress in the computer field, by allowing direct manipulation of large composite objects, considerably more complex than the integers, strings, etc., available in such well-known mainstream languages as PASCAL, PL/I, ALGOL, and Ada. For this purpose, LISP introduces structured lists as data objects, APL introduces vectors and matrices, and SETL introduces the objects characteristic for it, namely general finite sets and maps. The direct availability of these abstract, composite objects, and of powerful mathematical operations upon them, improves programmer speed and pro ductivity significantly, and also enhances program clarity and readability. The classroom consequence is that students, freed of some of the burden of petty programming detail, can advance their knowledge of significant algorithms and of broader strategic issues in program development more rapidly than with more conventional programming languages.

Klappentext

The programming language SETL is a relatively new member of the so-called "very-high-level" class of languages, some of whose other well-known mem­ bers are LISP, APL, SNOBOL, and PROLOG. These languages all aim to reduce the cost of programming, recognized today as a main obstacle to future progress in the computer field, by allowing direct manipulation of large composite objects, considerably more complex than the integers, strings, etc., available in such well-known mainstream languages as PASCAL, PL/I, ALGOL, and Ada. For this purpose, LISP introduces structured lists as data objects, APL introduces vectors and matrices, and SETL introduces the objects characteristic for it, namely general finite sets and maps. The direct availability of these abstract, composite objects, and of powerful mathematical operations upon them, improves programmer speed and pro­ ductivity significantly, and also enhances program clarity and readability. The classroom consequence is that students, freed of some of the burden of petty programming detail, can advance their knowledge of significant algorithms and of broader strategic issues in program development more rapidly than with more conventional programming languages.

Inhalt

1 Programming Concepts.- 1.1 An Informal Overview of SETL.- 1.2 Advice to the Would-Be Programmer.- 1.3 Programming Steps: How to Run Your Program and Read Its Results.- 1.4 How to Type a Program: Character Sets.- 1.4.1 Comments.- 1.5 Appendix: More on How to Read Your Output Listing.- 1.5.1 Missing quotation marks.- 1.5.2 Other features of the compilation history.- 1.5.3 Review of principal actions which occur when a job is run.- 2 Simple Data Types, Expressions, and Operations.- 2.1 The Main Classes of Data Objects.- 2.2 Simple Types and Their Constants.- 2.2.1 Integer constants.- 2.2.2 Floating-point constants.- 2.2.3 String constants.- 2.2.4 Boolean constants.- 2.2.5 Atoms.- 2.2.6 Om: the underfined value.- 2.3 Variable Identifiers.- 2.4 Expressions and Statements.- 2.5 Operations with Simple Data Types.- 2.5.1 Integer operators.- 2.5.1.1 Binary operations on integers.- 2.5.1.2 Predicates on integers.- 2.5.1.3 Unary integer operators.- 2.5.2 Floating-point operators.- 2.5.2.1 Binary floating-point operators.- 2.5.2.2 Predicates on floating-point values.- 2.5.2.3 Unary floating-point operators.- 2.5.3 String operators.- 2.5.4 Boolean operators.- 2.5.4.1 Boolean equivalences.- 2.5.5 Operations with atoms.- 3 Compound Data Types and Operators.- 3.1 Sets and Set Denotations.- 3.1.1 Some useful sets of integers.- 3.2 Tuples.- 3.2.1 Some useful tuples of integers.- 3.3 Maps.- 3.4 The Size of Composite Objects: The # Operator.- 3.5 Set Operations and Set Formers.- 3.5.1 Binary set operators.- 3.5.2 Unary set operators.- 3.5.3 Set former expressions.- 3.5.4 Existential and universal quantifiers.- 3.5.4.1 A remark on bound variables in compound set formers and quantifiers.- 3.5.5 Some illustrative one-statement programs.- 3.5.5.1 More about prime numbers.- 3.5.5.2 Integer right triangles.- 3.6 Tuple Operations and Tuple Formers.- 3.6.1 Binary tuple operators.- 3.6.2 Unary tuple operators.- 3.6.3 Other tuple operators. Indexing and slicing.- 3.7 Tuple Formers; Simple Tuple and String Iterators.- 3.8 Map Operations.- 3.8.1 The image-set operator f{x}.- 3.8.2 The single-valued image operator f(x).- 3.8.3 Some remarks on multivalued maps.- 3.8.4 Two useful map operations.- 3.8.5 Multiparameter maps.- 3.9 Compound Operators.- 3.10 Types and Type-Testing Operators.- 3.11 The? Operator.- 3.12 General Form of the SETL Assignment: The Operators from, frome, and fromb.- 3.12.1 Assigning forms of infix operators.- 3.12.2 Assignment expressions.- 3.12.3 Other positions in which assignment targets are allowed.- 3.12.4 The operators from, frome, and fromb.- 3.13 Operator Precedence Rules.- 3.14 Om and Errors.- 4 Control Structures.- 4.1 The if Statement.- 4.1.1 Omitting the else branch of an if statement.- 4.1.2 The null statement.- 4.1.3 Multiple alternatives in an if statement.- 4.1.4 An important note on indentation and programming style.- 4.1.5 The if expression.- 4.2 The case Statement.- 4.2.1 The case expression.- 4.3 Loops.- 4.3.1 Set iterators.- 4.3.1.1 Conditional set iterators.- 4.3.2 Tuple iterators.- 4.3.3 String iterators.- 4.3.4 Numerical iterators 120 4.3.4.1 The general form of the numerical iterator.- 4.3.5 Additional loop control statements: continue and quit.- 4.3.6 Map iterators.- 4.3.7 Compound iterators.- 4.3.8 The general loop construct.- 4.3.8.1 The while loop.- 4.3.8.2 The until loop.- 4.3.8.3 The general loop construct.- 4.3.8.4 The doing and step clauses.- 4.3.8.5 The init and term clauses.- 4.4 The goto Statement.- 4.5 The stop Statement.- 4.6 The assert Statement.- 4.7 Programming Examples.- 4.7.1 An interpreter for a simple language.- 4.7.1.1 Construction of a Turtle language interpreter.- 4.7.2 Various elementary sorting techniques.- 4.8 Reading and Writing Data.- 4.8.1 Reading data from a terminal.- 4.8.2 Character sets.- 5 Procedures.- 5.1 Writing and Using Procedures.- 5.1.1 Some simple sorting procedures.- 5.1.1.1 The main block of a program.- 5.1.2 A character-conversion procedure.- 5.1.3 A package of procedures for manipulating polynomials.- 5.2 Name Scopes; Local and Global Variable Names: The var Declaration.- 5.3 Programming Examples 177 5.3.1 The buckets and well problem: a simple artificial intelligence example.- 5.4 Recursive Procedures.- 5.4.1 The quicksort procedure.- 5.4.2 Another recursive procedure: mergesort.- 5.4.3 Binary searching: a fast recursive searching technique.- 5.4.4 The Towers of Hanoi problem.- 5.5 Procedures that Modify Their Parameters.- 5.6 Other Procedure-Related Facilities.- 5.6.1 Procedures with a variable number of arguments.- 5.6.2 User-defined prefix and infix operators.- 5.6.3 Refinements.- 5.7 Rules of Style in the Use of Procedures.- 5.8 String Scanning Primitives.- 5.8.1 Examples of use of the string scanning primitives.- 5.8.1.1 A simple lexical scanner.- 5.8.1.2 A concordance program.- 5.8.1.3 A Margin Justification procedure.- 5.9 Use of Atoms.- 5.10 Additional Examples.- 5.10.1 Solution of systems of linear equations.- 5.10.2 An interactive text-editing routine.- 6 Program Development, Testing, and Debugging.- 6.1 Bugs: How to Minimize Them.- 6.2 Finding Bugs.- 6.3 A Checklist of Common Bugs.- 6.4 Program Testing.- 6.4.1 First-stage testing.- 6.4.2 Quality assurance testing.- 6.4.3 Regression testing.- 6.5 Analysis of Program Efficiency.- 6.5.1 Estimation of program efficiency.- 6.5.2 The execution time of elementary instructions.- 6.5.3 Operations on sets.- 6.5.3.1 Elementary operations on sets.- 6.5.3.2 Global operations on sets.- 6.5.4…