Note: This edition is out of date. The language has improved in many ways, making some of the code in this book no longer executable. In addition, there are many revisions, improvements, and additions to the book. Please instead refer to the 2019 edition.
1 Introduction |
1.1 Our Philosophy |
1.2 Predictability as a Theme |
1.3 The Structure of This Book |
1.4 The Language of This Book |
|
2 Basic Data and Expressions |
2.1 Numbers |
2.2 Expressions Versus Values |
2.3 Variables to Name Values |
2.4 Strings |
2.4.1 Multi-Line Strings |
2.4.2 Operations on Strings |
2.5 Booleans |
2.5.1 Other Comparisons |
2.5.2 Other Boolean-Producing Operations |
2.5.3 Combining Booleans |
2.5.4 Using Booleans |
2.6 Evaluating by Reducing Expressions |
2.7 Images |
2.8 Roughnums |
|
3 From Repeated Expressions to Functions |
3.1 Example: Moon Weight |
3.2 Example: Japanese Flag |
3.3 Tests: Keeping Track of Examples |
3.4 Type Annotations |
3.5 Defining Functions in Steps |
|
4 Introduction to Tabular Data |
4.1 Creating Tabular Data |
4.2 Processing Rows |
4.2.1 Keeping |
4.2.2 Ordering |
4.2.3 Combining Keeping and Ordering |
4.2.4 Extending |
4.2.5 Transforming, Cleansing, and Normalizing |
4.2.6 Selecting |
4.2.7 Summary of Row-Wise Table Operations |
|
5 From Tables to Lists |
5.1 Basic Statistical Questions |
5.2 Extracting a Column from a Table |
5.3 Understanding Lists |
5.3.1 Lists as Anonymous Data |
5.3.2 Creating Literal Lists |
5.4 Operating on Lists |
5.4.1 Built-In Operations on Lists |
5.4.2 Combining Lists and Tables |
|
6 Processing Lists |
6.1 Making Lists and Taking Them Apart |
6.2 Some Example Exercises |
6.3 Structural Problems with Scalar Answers |
6.3.1 my-len: Examples |
6.3.2 my-sum: Examples |
6.3.3 From Examples to Code |
6.4 Structural Problems with List Answers |
6.4.1 my-str-len: Examples and Code |
6.4.2 my-pos-nums: Examples and Code |
6.4.3 my-alternating: First Attempt |
6.4.4 my-running-sum: First Attempt |
6.5 Structural Problems with Sub-Domains |
6.5.1 my-max: Examples |
6.5.2 my-max: From Examples to Code |
6.5.3 my-alternating: Examples and Code |
6.6 More Structural Problems with Scalar Answers |
6.6.1 my-avg: Examples |
6.7 Structural Problems with Accumulators |
6.7.1 my-running-sum: Examples and Code |
6.7.2 my-alternating: Examples and Code |
6.8 Dealing with Multiple Answers |
6.8.1 uniq: Problem Setup |
6.8.2 uniq: Examples |
6.8.3 uniq: Code |
6.8.4 uniq: Reducing Computation |
6.8.5 uniq: Example and Code Variations |
6.8.6 uniq: Why Produce a List? |
6.9 Monomorphic Lists and Polymorphic Types |
|
7 Introduction to Structured Data |
7.1 Understanding the Kinds of Compound Data |
7.1.1 A First Peek at Structured Data |
7.1.2 A First Peek at Conditional Data |
7.2 Defining and Creating Structured and Conditional Data |
7.2.1 Defining and Creating Structured Data |
7.2.2 Annotations for Structured Data |
7.2.3 Defining and Creating Conditional Data |
7.3 Programming with Structured and Conditional Data |
7.3.1 Extracting Fields from Structured Data |
7.3.2 Telling Apart Variants of Conditional Data |
7.3.3 Processing Fields of Variants |
|
8 Collections of Structured Data |
8.1 Lists as Collective Data |
8.2 Sets as Collective Data |
8.2.1 Picking Elements from Sets |
8.2.2 Computing with Sets |
8.3 Combining Structured and Collective Data |
|
9 Recursive Data |
|
10 Tree-Shaped Data [EMPTY] |
|
11 Interactive Games as Reactive Systems |
11.1 About Reactive Animations |
11.2 Preliminaries |
11.3 Version: Airplane Moving Across the Screen |
11.3.1 Updating the World State |
11.3.2 Displaying the World State |
11.3.3 Observing Time (and Combining the Pieces) |
11.4 Version: Wrapping Around |
11.5 Version: Descending |
11.5.1 Moving the Airplane |
11.5.2 Drawing the Scene |
11.5.3 Finishing Touches |
11.6 Version: Responding to Keystrokes |
11.7 Version: Landing |
11.8 Version: A Fixed Balloon |
11.9 Version: Keep Your Eye on the Tank |
11.10 Version: The Balloon Moves, Too |
11.11 Version: One, Two, ..., Ninety-Nine Luftballons! |
|
12 Examples, Testing, and Program Checking |
12.1 From Examples to Tests |
12.2 More Refined Comparisons |
12.3 When Tests Fail |
12.4 Oracles for Testing |
12.5 Testing Erroneous Programs |
|
13 Functions as Data |
13.1 A Little Calculus |
13.2 A Helpful Shorthand for Anonymous Functions |
13.3 Streams From Functions |
13.4 Combining Forces: Streams of Derivatives |
|
14 Predicting Growth |
14.1 A Little (True) Story |
14.2 The Analytical Idea |
14.3 A Cost Model for Pyret Running Time |
14.4 The Size of the Input |
14.5 The Tabular Method for Singly-Structurally-Recursive Functions |
14.6 Creating Recurrences |
14.7 A Notation for Functions |
14.8 Comparing Functions |
14.9 Combining Big-Oh Without Woe |
14.10 Solving Recurrences |
|
15 Sets Appeal |
15.1 Representing Sets by Lists |
15.1.1 Representation Choices |
15.1.2 Time Complexity |
15.1.3 Choosing Between Representations |
15.1.4 Other Operations |
15.2 Making Sets Grow on Trees |
15.2.1 Converting Values to Ordered Values |
15.2.2 Using Binary Trees |
15.2.3 A Fine Balance: Tree Surgery |
15.2.3.1 Left-Left Case |
15.2.3.2 Left-Right Case |
15.2.3.3 Any Other Cases? |
|
16 [EMPTY] |
|
17 Halloween Analysis |
17.1 A First Example |
17.2 The New Form of Analysis |
17.3 An Example: Queues from Lists |
17.3.1 List Representations |
17.3.2 A First Analysis |
17.3.3 More Liberal Sequences of Operations |
17.3.4 A Second Analysis |
17.3.5 Amortization Versus Individual Operations |
17.4 Reading More |
|
18 Sharing and Equality |
18.1 Re-Examining Equality |
18.2 The Cost of Evaluating References |
18.3 On the Internet, Nobody Knows You’re a DAG |
18.4 From Acyclicity to Cycles |
|
19 Graphs |
19.1 Understanding Graphs |
19.2 Representations |
19.2.1 Links by Name |
19.2.2 Links by Indices |
19.2.3 A List of Edges |
19.2.4 Abstracting Representations |
19.3 Measuring Complexity for Graphs |
19.4 Reachability |
19.4.1 Simple Recursion |
19.4.2 Cleaning up the Loop |
19.4.3 Traversal with Memory |
19.4.4 A Better Interface |
19.5 Depth- and Breadth-First Traversals |
19.6 Graphs With Weighted Edges |
19.7 Shortest (or Lightest) Paths |
19.8 Moravian Spanning Trees |
19.8.1 The Problem |
19.8.2 A Greedy Solution |
19.8.3 Another Greedy Solution |
19.8.4 A Third Solution |
19.8.5 Checking Component Connectedness |
|
20 State, Change, and More Equality |
20.1 A Canonical Mutable Structure |
20.2 What it Means to be Identical |
20.3 Recursion and Cycles from Mutation |
20.3.1 Partial Definitions |
20.3.2 Recursive Functions |
20.3.3 Premature Evaluation |
20.3.4 Cyclic Lists Versus Streams |
20.4 From Identifiers to Variables |
20.5 Interaction of Mutation with Closures: Counters |
20.5.1 Implementation Using Boxes |
20.5.2 Implementation Using Variables |
20.6 A Family of Equality Predicates |
20.6.1 A Hierarchy of Equality |
20.6.2 Space and Time Complexity |
20.6.3 Comparing Functions |
|
21 Algorithms That Exploit State |
21.1 Disjoint Sets Redux |
21.1.1 Optimizations |
21.1.2 Analysis |
21.2 Set Membership by Hashing Redux |
21.2.1 Improving Access Time |
21.2.2 Better Hashing |
21.2.3 Bloom Filters |
21.3 Avoiding Recomputation by Remembering Answers |
21.3.1 An Interesting Numeric Sequence |
21.3.1.1 Using State to Remember Past Answers |
21.3.1.2 From a Tree of Computation to a DAG |
21.3.1.3 The Complexity of Numbers |
21.3.1.4 Abstracting Memoization |
21.3.2 Edit-Distance for Spelling Correction |
21.3.3 Nature as a Fat-Fingered Typist |
21.3.4 Dynamic Programming |
21.3.4.1 Catalan Numbers with Dynamic Programming |
21.3.4.2 Levenshtein Distance and Dynamic Programming |
21.3.5 Contrasting Memoization and Dynamic Programming |
|
22 [EMPTY] |
|
23 Processing Programs: Parsing |
23.1 Understanding Languages by Writing Programs About Them |
23.2 Everything (We Will Say) About Parsing |
23.2.1 A Lightweight, Built-In First Half of a Parser |
23.2.2 Completing the Parser |
23.2.3 Coda |
|
24 Processing Programs: A First Look at Interpretation |
24.1 Representing Arithmetic |
24.2 Writing an Interpreter |
24.3 A First Taste of “Semantics” |
24.4 Desugaring: Growing the Language Without Enlarging It |
24.4.1 Extension: Binary Subtraction |
24.4.2 Extension: Unary Negation |
24.5 A Three-Stage Pipeline |
|
25 Interpreting Conditionals |
25.1 The Design Space of Conditionals |
25.2 The Game Plan for Conditionals |
25.2.1 The Interpreter’s Type |
25.2.2 Updating Arithmetic |
25.2.3 Defensive Programming |
25.2.4 Interpreting Conditionals |
25.3 Growing the Conditional Language |
|
26 Interpreting Functions |
26.1 Adding Functions to the Language |
26.1.1 Defining Data Representations |
26.1.2 Growing the Interpreter |
26.1.3 Substitution |
26.1.4 The Interpreter, Resumed |
26.1.5 Oh Wait, There’s More! |
26.2 From Substitution to Environments |
26.2.1 Introducing the Environment |
26.2.2 Interpreting with Environments |
26.2.3 Deferring Correctly |
26.2.4 Scope |
26.2.5 How Bad Is It? |
26.2.6 The Top-Level Scope |
26.2.7 Exposing the Environment |
26.3 Functions Anywhere |
26.3.1 Functions as Expressions and Values |
26.3.2 A Small Improvement |
26.3.3 Nesting Functions |
26.3.4 Nested Functions and Substitution |
26.3.5 Updating Values |
26.3.6 Sugaring Over Anonymity |
26.4 Recursion and Non-Termination |
26.5 Functions and
Predictability |
|
27 Reasoning about Programs: A First Look at Types |
27.1 Types as a Static Discipline |
27.2 The Principle of Substitutability |
27.3 A Type(d) Language and Type Errors |
27.3.1 Assume-Guarantee Reasoning |
27.4 A Type Checker for Expressions and Functions |
27.4.1 A Pure Checker |
27.4.2 A Calculator and Checker |
27.4.3 Type-Checking Versus Interpretation |
27.5 Type-Checking, Testing, and Coverage |
27.6 Recursion in Code |
27.6.1 A First Attempt at Typing Recursion |
27.6.2 Program Termination |
27.6.3 Typing Recursion |
27.7 Recursion in Data |
27.7.1 Recursive Datatype Definitions |
27.7.2 Introduced Types |
27.7.3 Selectors |
27.7.4 Pattern-Matching and Desugaring |
|
28 Safety and Soundness |
28.1 Safety |
28.2 “Untyped” Languages |
28.3 The Central Theorem: Type Soundness |
28.4 Types, Time, and Space |
28.5 Types Versus Safety |
|
29 Parametric Polymorphism |
29.1 Parameterized Types |
29.2 Making Parameters Explicit |
29.3 Rank-1 Polymorphism |
29.4 Interpreting Rank-1 Polymorphism as Desugaring |
29.5 Alternate Implementations |
29.6 Relational Parametricity |
|
30 Type Inference |
30.1 Type Inference as Type Annotation Insertion |
30.2 Understanding Inference |
30.2.1 Constraint Generation |
30.2.2 Constraint Solving Using Unification |
30.3 Type Checking and Type Errors |
30.4 Over- and Under-Constrained Solutions |
30.5 Let-Polymorphism |
|
31 Mutation: Structures and Variables |
31.1 Separating Meaning from Notation |
31.2 Mutation and Closures |
31.3 Mutable Structures |
31.3.1 Extending the Language Representation |
31.3.2 The Interpretation of Boxes |
31.3.3 Can the Environment Help? |
31.3.4 Welcome to the Store |
31.3.5 Interpreting Boxes |
31.3.6 Implementing Mutation: Subtleties and Variations |
31.4 Variables |
31.4.1 The Syntax of Variable Assignment |
31.4.2 Interpreting Variables |
31.4.3 Reference Parameter Passing |
31.5 The Design of Stateful Language Operations |
31.6 Typing State |
31.6.1 Mutation and Polymorphism |
31.6.2 Typing the Initial Value |
|
32 Objects: Interpretation and Types |
32.1 Interpreting Objects |
32.2 Objects by Desugaring |
32.2.1 Objects as Named Collections |
32.2.2 Constructors |
32.2.3 State |
32.2.4 Private Members |
32.2.5 Static Members |
32.2.6 Objects with Self-Reference |
32.2.6.1 Self-Reference Using Mutation |
32.2.6.2 Self-Reference Without Mutation |
32.2.7 Dynamic Dispatch |
32.3 Member Access Design Space |
32.4 What (Goes In) Else? |
32.4.1 Classes |
32.4.2 Prototypes |
32.4.3 Multiple Inheritance |
32.4.4 Super-Duper! |
32.4.5 Mixins and Traits |
32.5 Object Classification and Object Equality |
32.6 Types for Objects |
32.6.1 Subtyping |
32.6.1.1 Subtyping Functions |
32.6.1.2 Subtyping and Information Hiding |
32.6.1.3 Implementing Subtyping |
32.6.2 Types for Self-Reference |
32.6.3 Nominal Types |
|
33 Control Operations |
33.1 Control on the Web |
33.1.1 Program Decomposition into Now and Later |
33.1.2 A Partial Solution |
33.1.3 Achieving Statelessness |
33.1.4 Interaction with State |
33.2 Conversion to Continuation-Passing Style |
33.2.1 Implementation by Desugaring |
33.2.2 Understanding the Output |
33.2.3 An Interaction Primitive by Transformation |
33.3 Implementation in the Core |
33.3.1 Converting the Interpreter |
33.3.2 An Interaction Primitive in the Core |
33.4 Generators |
33.5 Continuations and Stacks |
33.6 Tail Calls |
|
34 Pyret for Racketeers and Schemers |
34.1 Numbers, Strings, and Booleans |
34.2 Infix Expressions |
34.3 Function Definition and Application |
34.4 Tests |
34.5 Variable Names |
34.6 Data Definitions |
34.7 Conditionals |
34.8 Lists |
34.9 First-Class Functions |
34.10 Annotations |
34.11 What Else? |
|
35 Glossary |