Programming with Sets

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 Operations on tuples and strings.- 6.5.5 The execution time of programs containing loops.- 6.5.6 The execution time of while loops.- 6.5.7 Efficiency analysis of recursive routines.- 6.5.8 The cost of copying, or space is time after all.- 6.5.9 Data structures used for the efficient realization of some SETL primitives: the linked list.- 6.5.10 Some techniques for program transformation.- 6.5.10.1 The elimination of repeated calculations.- 6.5.10.2 Reuse of storage and recursion elimination: the case of quicksort.- 6.6 Formal Verification of Programs.- 6.6.1 Formal verification using Floyd assertions: general approach.- 6.6.2 Formal verification using Floyd assertions: an example.- 6.7 Formative Influences on Program Development.- 6.8 References to Material on Alternative Data Structures: References for Additional Material on Algorithms.- 7 Backtracking.- 7.1 Backtracking.- 7.1.1 Implementation of backtracking.- 7.1.2 Total failure.- 7.1.3 Tiling problems.- 7.1.4 Other uses of ok and fail.- 7.1.4.1 Combinational generators.- 7.1.4.2 Failures and exceptions.- 7.1.5 Nondeterministic programs, or it is ok after all.- 7.1.6 Auxiliary backtracking primitives.- 7.1.6.1 Housecleaning: the succeed primitive.- 7.1.6.2 Controlling the depth of the search: the lev primitive.- 8 Structuring Large SETL Programs.- 8.1 The const Declaration.- 8.2 Macros.- 8.2.1 Macro definitions.- 8.2.2 Parameterless macros.- 8.2.3 Macros with parameters.- 8.2.4 Macros with generated parameters.- 8.2.5 The lexical scope of macros: macro nesting.- 8.2.6 Dropping and redefining macros.- 8.3 Programming Examples.- 8.4 Programs, Modules, Libraries, and Directories: Structuring Constructs for Large SETL Programs.- 8.4.1 Textual structure of complex programs.- 8.4.2 Separate compilation and binding of program subsections.- 9 Input/Output and Communication with the Environment.- 9.1 Input-Output Facilities.- 9.2 Use of Inclusion Libraries.- 9.3 Listing-Control Commands.- 9.4 Environment Operators and SETL Command Parameters.- 9.4.1 Standard SETL command options.- 9.4.1.1 Parse phase options.- 9.4.1.2 Semantic analysis phase options.- 9.4.1.3 Code generation phase options.- 9.4.1.4 Run-time support library options.- 9.4.1.5 Other options used for system checkout and maintenance.- 10 The Data Representation Sublanguage.- 10.0 Implementation of the SETL Primitives.- 10.1 The Standard Representation for Tuples.- 10.2 The Standard Representation for Sets.- 10.3 Type Declarations.- 10.3.1 Mode declarations.- 10.3.2 An example of the use of type declarations.- 10.4 Basing Declarations.- 10.4.1 Base sets.- 10.4.2 Based maps.- 10.4.2.1 Local maps.- 10.4.2.2 Remote maps.- 10.4.2.3 Sparse maps.- 10.4.3 Based representations for sets.- 10.4.4 Basing declarations for multivalued maps.- 10.5 Base Sets Consisting of Atoms Only.- 10.6 Constant Bases.- 10.7 The Packed Representations.- 10.8 Guidelines for the Effective Use of the Data Representation Sublanguage.- 11 The Language in Action: A Gallery of Programming Examples.- 11.1 Eulerian Paths in a Graph.- 11.2 Topological Sorting.- 11.3 The Stable Assignment Problem.- 11.4 A Text Preparation Program.- 11.5 A Simplified Financial Record-Keeping System.- 11.6 A Turing-Machine Simulator.- 11.7 Huffman Coding of Text Files.- 11.8 A Game-Playing Program.- 11.9 Implementation of a Macroprocessor.- Appendix A SETL Reserved Words.- Appendix B Syntax Diagrams.- B.1 Lexical Structure.- B.2 Program Structure.- B.3 Declarative Forms.- B.4 Statement Forms.- B.5 Expressions.