Programming and Meta-Programming in Scheme

By now, Scheme is a well-established programming language and is finding increasing popularity in programming courses for undergraduates. This undergraduate textbook provides a first course in programming in Scheme and an introduction to programming principles.

1.1 LISP.- 1.1.1. LISP Dialects.- 1.2 Scheme.- 1.2.1. Scheme on the Web.- 1.3. Structure of the Text.- 1.3.1. Themes.- 1. Expressions and Values.- 1.1. Values.- 1.1.1. Numbers.- 1.1.2. Characters.- 1.1.3Booleans.- 1.1.4 Symbols.- 1.1.5. Procedures.- 1.1.6. Strings.- 1.1.7. Lists.- 1.1.8. Vectors.- 1.1.9. Pairs.- 1.1.10. Other Value Domains.- 1.2. Expressions.- 1.2.1. Literals.- 1.2.2. Symbols and the Global Environment.- 1.2.3. Applications.- 1.2.4. Structures.- 1.2.5. Literals Revisited.- 1.3. The Scheme Interpreter.- 1.3.1. The Expression Evaluator.- 1.3.2. The Control Loop.- 1.4. Definitions.- Appendices.- Appendix 1.1. Defining Domains.- Appendix 1.2. Sessions.- Appendix 1.3. Numbers.- Problems.- 2. Procedures.- 2.1. Defining and Applying Procedures.- 2.1.1. The Environmental Influence.- 2.1.2. The Modularity Principle and Top-Down Design.- 2.2. Building Procedures Using Application.- 2.2.1. Example: Coercions.- 2.2.2. Example: Palindromes.- 2.3. The Abstraction Principle.- 2.3.1. Constructors.- 2.3.2. Selectors.- 2.3.3. Lists as Pairs.- 2.3.4. Example: Association Lists as Records.- 2.4. Polymorphic Procedures.- 2.4.1. Equivalence Predicates.- 2.4.2. The not and null? Predicates.- 2.4.3. Recognition Predicates.- 2.4.4. Example: Searching Association Lists.- 2.5. Meta-Procedures.- Appendices.- Appendix 2.1. Mathematics in Scheme.- Appendix 2.2. Sequences.- Appendix 2.3. The Edit-Test-Debug Cycle.- Problems.- 3. Evaluation Control and Recursion.- 3.1. Evaluation Control.- 3.2. Short Circuit Evaluation.- 3.3. Conditional Evaluation.- 3.3.1. The if-structure.- 3.3.2. The cond-structure.- 3.3.3. Input Validation.- 3.3.4. The case-structure.- 3.4. Recursion.- 3.4.1. Example: Triangle Numbers.- 3.4.2. Tracing.- 3.4.3. More on Input Validation.- 3.4.4. Mathematical Induction.- 3.5. Thinking Recursively.- 3.5.1. Example: make-list.- 3.5.2. Example: nat-expt.- 3.5.3. Example: evaluate.- Problems.- 4. Data Control.- 4.1. Procedure Blocks.- 4.1.1. The Nesting Instinct.- 4.2. The Environment Model of Eager Evaluation.- 4.2.1. Bindings.- 4.2.2. Environments.- 4.2.3. Static Versus Dynamic Scope Rules.- 4.3. Abstract Data Types.- 4.3.1.Example : The CARD ADT.- 4.3.2. Information Hiding and Data Abstraction.- 4.3.3. Example: The POINT ADT.- 4.4. Overloading.- 4.5. Domains as Data.- 4.5.1. Programmer-Defined Types.- 4.5.2. Example: Complex Numbers.- 4.6. Data-Driven Programming.- Appendices.- Appendix 4.1. Object-Oriented Programming.- Appendix 4.2. Expression Blocks.- Problems.- 5. Iteration.- 5.1. Modeling Systems.- 5.1.1. Iterative Evaluation.- 5.1.2. Control Loops.- 5.1.3. Example: A Digital Clock.- 5.1.4. Example: Compound Interest.- 5.1.5. Example: A Simple Interactive System.- 5.1.6. Example: Guess and Test.- 5.2. Computations as Data.- 5.2.1. Predicting the Future.- 5.2.2. Measuring Computations.- 5.2.3. Measuring Efficiency.- 5.2.4. The Tyranny of Growth Rate.- 5.3. Finding Iterative Solutions.- 5.4. Tail Recursion: Are do-loops Necessary?.- 5.5. Finding Elementary Solutions.- Appendices.- Appendix 5.1. The Hyper-Exponential Hierarchy.- Appendix 5.2. Undecidability.- Appendix 5.3. Chaos.- Problems.- 6. Recursive Domains.- 6.1. Recursive Domains as Hierarchies.- 6.1.1. Recursion over Hierarchies.- 6.2. List Recursion.- 6.2.1. Application: Are Lists Necessary?.- 6.2.2. Application: Association Lists.- 6.3. The Signal Processing Paradigm.- 6.3.1. Filters.- 6.3.2. Amplifiers (Map).- 6.3.3. Receivers (Accumulators).- 6.3.4. Transmitters (Generators).- 6.3.5. Applications.- 6.4. Trees and Tree Recursion.- 6.4.1. Terminology.- 6.4.2. The TREE Domain.- 6.4.3. Tree Recursion.- 6.4.4. Efficiency of Tree Recursions.- Appendices.- Appendix 6.1. Promises.- Appendix 6.2. Streams.- Problems.- 7. Variables.- 7.1. Stores.- 7.2. Variables and References.- 7.3. Commands.- 7.4. L-Value versus R-Value.- 7.5. Aliasing.- 7.6. Define Versus Assign.- 7.7. Imperative Programming.- 7.8. The Bank Account Example.- 7.8.1. Pass-by-Value.- 7.8.2. Pass-by-Reference.- 7.83. Bank Accounts Revisited.- Appendices.- Appendix 7.1. Implementing Heaps.- Appendix 7.2. Sequential Access Stores.- Appendix 7.3. Files and Ports.- Problems.- 8. Expressions as Values.- 8.1. Macros.- 8.1.1. While Structures.- 8.1.2. Lazy Procedures.- 8.1.3. Implementing Streams.- 8.2. Semantic Prototyping.- 8.3. Alpha.- 8.3.1. Alpha Values and Phrases.- 8.3.2. The Alpha Control Loop.- 8.3.3. The Alpha Declaration Resolver.- 8.3.4. The Alpha Expression Evaluator.- 8.4. Beta.- 8.4.1. Beta Commands.- 8.4.2. The Beta Control Loop.- 8.4.3. The Beta Resolver.- 8.4.4. The Beta Evaluator.- Appendices.- Appendix 8.1. Lambda.- Problems.- References.