Tyros learn simple computation on data descriptions that can be written in a way that defines each data class completely before any other description uses that class.
Simple design recipe; named functions; define; auxiliary functions arise from dependencies in the problem [Sections 1 to 3, design recipe Fig 4 page 21]
Conditional expressions and functions; cond [Section 4, design recipe Fig 6 page 44]
Symbols [Section 5] and strings [2nd edition, Section 1.2]
Structures, define-struct [Section 6, design recipe Fig 12 page 71]
Mixed data, type predicates such as number? and so on [Section 7, design recipe Fig 18 page 89]
BNF Grammar for Beginning Student Language [Intermezzo 1]
Beginning students learn to work with data descriptions that refer to themselves and so cannot be completely defined before they are used. The most common such data are lists and trees.
Defining and consuming lists using empty, cons, first, rest, and empty? [Section 9, design recipe Fig 26 page 132]
Producing lists; lists of structures [Section 10]
Peano numerals; zero? [Section 11]
Problem-solving; auxiliary functions [Section 12]
List abbreviations [Intermezzo 2]
Trees, nested lists (using existing structure and list primitives) [Section 14]
Groups of mutually referential data definitions [Section 15, design recipe Fig 43 page 218]
Problem-solving: iterative refinement [Section 16]
Forms of case analysis with multiple complex arguments [Section 17]
Intermediate students learn a key technique of computer science: abstraction.
local definitions of variables and functions; lexical scope [Intermezzo 3]
Don’t Repeat Yourself: abstracting similar functions and similar data definitions [Section 19]
Functions are values: filter1, map, sort, parametric polymorphism; “loops” [Section 20]
How to design abstractions; single point of control; clone and modify considered harmful [Section 21]
Designing abstractions with 1st-class functions [Section 22]
Examples: sequences, series, graphing [Section 23]
Anonymous functions with lambda [Intermezzo 4]
Recursive reasoners have the insight to find a recursive decomposition even when the decomposition is not there in the data. And they can write recursive algorithms that remember past actions.
Generative recursion; quicksort [Section 25]
Problem-solving: algorithm design; termination [Section 26]
Extended examples: fractals, files, Newton’s method, Gaussian elimination [Section 27, may not be covered]
Input via state machines [No book coverage]
Remembering the past with accumulating parameters [Sections 30, 31, 32]
Graph algorithms and search [Section 28]
Cost containers can reason about costs.
Cost modeling, vectors, big O notation [Section 29]
Inexact (floating-point) numbers [Intermezzo 6]
Memory mutators cut costs by using mutable state. We may replace this level with a project or something else.
Mutable variables and mutation (set!) [Sections 34 to 37]
Syntax and semantics of Advanced Scheme [Intermezzo 7]
Abstraction with mutable state [Section 39]
Mutable structures and vectors [Section 40]
Mutating elements (atomic or structured) [Section 41]
Extensional and intensional equality [Section 42]
Mutation practicum: quicksort, cyclic structures [Section 43]