Programming with Sets: An Introduction to Setl

ISBN-13: 9781461395775 / Angielski / Miękka / 2012 / 493 str.

J. T. Schwartz; R. B. K. Dewar; E. Dubinsky

Opis

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."

Spis treści

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.- 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.