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 Acknowledgments |
|
3 Getting Started |
3.1 Motivating Example: Flags |
3.2 Numbers |
3.3 Expressions |
3.4 Terminology |
3.5 Strings |
3.6 Images |
3.6.1 Combining Images |
3.6.2 Making a Flag |
3.7 Stepping Back: Types, Errors, and Documentation |
3.7.1 Types and Contracts |
3.7.2 Format and Notation Errors |
3.7.3 Finding Other
Functions: Documentation |
|
4 Naming Values |
4.1 The Definitions Window |
4.2 Naming Values |
4.2.1 Names Versus Strings |
4.2.2 Expressions versus
Statements |
4.3 The Program Directory |
4.3.1 Understanding the Run Button |
4.4 Using Names to Streamline Building Images |
|
5 From Repeated Expressions to Functions |
5.1 Example: Similar Flags |
5.2 Defining Functions |
5.2.1 How Functions Evaluate |
5.2.2 Type Annotations |
5.2.3 Documentation |
5.3 Functions Practice: Moon Weight |
5.4 Documenting Functions with Examples |
5.5 Functions Practice: Cost of pens |
5.6 Recap: Defining Functions |
|
6 Conditionals and Booleans |
6.1 Motivating Example: Shipping Costs |
6.2 Conditionals: Computations with Decisions |
6.3 Booleans |
6.3.1 Other Boolean Operations |
6.3.2 Combining Booleans |
6.4 Asking Multiple Questions |
6.5 Evaluating by Reducing Expressions |
6.6 Composing Functions |
6.7 Nested Conditionals |
6.8 Recap: Booleans and Conditionals |
|
7 Introduction to Tabular Data |
7.1 Creating Tabular Data |
7.2 Extracting Rows and Cell Values |
7.3 Functions over Rows |
7.4 Processing Rows |
7.4.1 Finding Rows |
7.4.2 Ordering Rows |
7.4.3 Adding New Columns |
7.4.4 Calculating New Column Values |
7.5 Examples for Table-Producing Functions |
|
8 Processing Tables |
8.1 Cleaning Data Tables |
8.1.1 Loading Data Tables |
8.1.2 Dealing with Missing Entries |
8.1.3 Normalizing Data |
8.1.4 Normalization, Systematically |
8.1.4.1 Using Programs to Detect Data Errors |
8.2 Task Plans |
8.3 Preparing Data Tables |
8.3.1 Creating bins |
8.4 Managing and Naming Data Tables |
8.5 Visualizations and Plots |
8.6 Summary: Managing a Data Analysis |
|
9 From Tables to Lists |
9.1 Basic Statistical Questions |
9.2 Extracting a Column from a Table |
9.3 Understanding Lists |
9.3.1 Lists as Anonymous Data |
9.3.2 Creating Literal Lists |
9.4 Operating on Lists |
9.4.1 Built-In Operations on Lists of Numbers |
9.4.2 Built-In Operations on Lists in General |
9.4.3 An Aside on Naming Conventions |
9.4.4 Getting Elements By Position |
9.4.5 Transforming Lists |
9.4.6 Recap: Summary of List Operations |
9.5 Lambda: Anonymous Functions |
9.6 Combining Lists and Tables |
|
10 Processing Lists |
10.1 Making Lists and Taking Them Apart |
10.2 Some Example Exercises |
10.3 Structural Problems with Scalar Answers |
10.3.1 my-len: Examples |
10.3.2 my-sum: Examples |
10.3.3 From Examples to Code |
10.4 Structural Problems with List Answers |
10.4.1 my-str-len: Examples and Code |
10.4.2 my-pos-nums: Examples and Code |
10.4.3 my-alternating: First Attempt |
10.4.4 my-running-sum: First Attempt |
10.5 Structural Problems with Sub-Domains |
10.5.1 my-max: Examples |
10.5.2 my-max: From Examples to Code |
10.5.3 my-alternating: Examples and Code |
10.6 More Structural Problems with Scalar Answers |
10.6.1 my-avg: Examples |
10.7 Structural Problems with Accumulators |
10.7.1 my-running-sum: Examples and Code |
10.7.2 my-alternating: Examples and Code |
10.8 Dealing with Multiple Answers |
10.8.1 uniq: Problem Setup |
10.8.2 uniq: Examples |
10.8.3 uniq: Code |
10.8.4 uniq: Reducing Computation |
10.8.5 uniq: Example and Code Variations |
10.8.6 uniq: Why Produce a List? |
10.9 Monomorphic Lists and Polymorphic Types |
|
11 Introduction to Structured Data |
11.1 Understanding the Kinds of Compound Data |
11.1.1 A First Peek at Structured Data |
11.1.2 A First Peek at Conditional Data |
11.2 Defining and Creating Structured and Conditional Data |
11.2.1 Defining and Creating Structured Data |
11.2.2 Annotations for Structured Data |
11.2.3 Defining and Creating Conditional Data |
11.3 Programming with Structured and Conditional Data |
11.3.1 Extracting Fields from Structured Data |
11.3.2 Telling Apart Variants of Conditional Data |
11.3.3 Processing Fields of Variants |
|
12 Collections of Structured Data |
12.1 Lists as Collective Data |
12.2 Sets as Collective Data |
12.2.1 Picking Elements from Sets |
12.2.2 Computing with Sets |
12.3 Combining Structured and Collective Data |
|
13 Recursive Data |
|
14 Interactive Games as Reactive Systems |
14.1 About Reactive Animations |
14.2 Preliminaries |
14.3 Version: Airplane Moving Across the Screen |
14.3.1 Updating the World State |
14.3.2 Displaying the World State |
14.3.3 Observing Time (and Combining the Pieces) |
14.4 Version: Wrapping Around |
14.5 Version: Descending |
14.5.1 Moving the Airplane |
14.5.2 Drawing the Scene |
14.5.3 Finishing Touches |
14.6 Version: Responding to Keystrokes |
14.7 Version: Landing |
14.8 Version: A Fixed Balloon |
14.9 Version: Keep Your Eye on the Tank |
14.10 Version: The Balloon Moves, Too |
14.11 Version: One, Two, ..., Ninety-Nine Luftballons! |
|
15 Examples, Testing, and Program Checking |
15.1 From Examples to Tests |
15.2 More Refined Comparisons |
15.3 When Tests Fail |
15.4 Oracles for Testing |
15.5 Testing Erroneous Programs |
|
16 Functions as Data |
16.1 A Little Calculus |
16.2 A Helpful Shorthand for Anonymous Functions |
16.3 Streams From Functions |
16.4 Combining Forces: Streams of Derivatives |
|
17 Predicting Growth |
17.1 A Little (True) Story |
17.2 The Analytical Idea |
17.3 A Cost Model for Pyret Running Time |
17.4 The Size of the Input |
17.5 The Tabular Method for Singly-Structurally-Recursive Functions |
17.6 Creating Recurrences |
17.7 A Notation for Functions |
17.8 Comparing Functions |
17.9 Combining Big-Oh Without Woe |
17.10 Solving Recurrences |
|
18 Sets Appeal |
18.1 Representing Sets by Lists |
18.1.1 Representation Choices |
18.1.2 Time Complexity |
18.1.3 Choosing Between Representations |
18.1.4 Other Operations |
18.2 Making Sets Grow on Trees |
18.2.1 Converting Values to Ordered Values |
18.2.2 Using Binary Trees |
18.2.3 A Fine Balance: Tree Surgery |
18.2.3.1 Left-Left Case |
18.2.3.2 Left-Right Case |
18.2.3.3 Any Other Cases? |
|
19 Halloween Analysis |
19.1 A First Example |
19.2 The New Form of Analysis |
19.3 An Example: Queues from Lists |
19.3.1 List Representations |
19.3.2 A First Analysis |
19.3.3 More Liberal Sequences of Operations |
19.3.4 A Second Analysis |
19.3.5 Amortization Versus Individual Operations |
19.4 Reading More |
|
20 Sharing and Equality |
20.1 Re-Examining Equality |
20.2 The Cost of Evaluating References |
20.3 On the Internet, Nobody Knows You’re a DAG |
20.4 From Acyclicity to Cycles |
|
21 Graphs |
21.1 Understanding Graphs |
21.2 Representations |
21.2.1 Links by Name |
21.2.2 Links by Indices |
21.2.3 A List of Edges |
21.2.4 Abstracting Representations |
21.3 Measuring Complexity for Graphs |
21.4 Reachability |
21.4.1 Simple Recursion |
21.4.2 Cleaning up the Loop |
21.4.3 Traversal with Memory |
21.4.4 A Better Interface |
21.5 Depth- and Breadth-First Traversals |
21.6 Graphs With Weighted Edges |
21.7 Shortest (or Lightest) Paths |
21.8 Moravian Spanning Trees |
21.8.1 The Problem |
21.8.2 A Greedy Solution |
21.8.3 Another Greedy Solution |
21.8.4 A Third Solution |
21.8.5 Checking Component Connectedness |
|
22 State, Change, and More Equality |
22.1 A Canonical Mutable Structure |
22.2 Equality and Mutation |
22.2.1 Observing Mutation |
22.2.2 What it Means to be Identical |
22.2.3 An Additional Challenge |
22.3 Recursion and Cycles from Mutation |
22.3.1 Partial Definitions |
22.3.2 Recursive Functions |
22.3.3 Premature Evaluation |
22.3.4 Cyclic Lists Versus Streams |
22.4 From Identifiers to Variables |
22.5 Interaction of Mutation with Closures: Counters |
22.5.1 Implementation Using Boxes |
22.5.2 Implementation Using Variables |
22.6 A Family of Equality Predicates |
22.6.1 A Hierarchy of Equality |
22.6.2 Space and Time Complexity |
22.6.3 Comparing Functions |
|
23 Algorithms That Exploit State |
23.1 Disjoint Sets Redux |
23.1.1 Optimizations |
23.1.2 Analysis |
23.2 Set Membership by Hashing Redux |
23.2.1 Improving Access Time |
23.2.2 Better Hashing |
23.2.3 Bloom Filters |
23.3 Avoiding Recomputation by Remembering Answers |
23.3.1 An Interesting Numeric Sequence |
23.3.1.1 Using State to Remember Past Answers |
23.3.1.2 From a Tree of Computation to a DAG |
23.3.1.3 The Complexity of Numbers |
23.3.1.4 Abstracting Memoization |
23.3.2 Edit-Distance for Spelling Correction |
23.3.3 Nature as a Fat-Fingered Typist |
23.3.4 Dynamic Programming |
23.3.4.1 Catalan Numbers with Dynamic Programming |
23.3.4.2 Levenshtein Distance and Dynamic Programming |
23.3.5 Contrasting Memoization and Dynamic Programming |
|
24 Processing Programs: Parsing |
24.1 Understanding Languages by Writing Programs About Them |
24.2 Everything (We Will Say) About Parsing |
24.2.1 A Lightweight, Built-In First Half of a Parser |
24.2.2 Completing the Parser |
24.2.3 Coda |
|
25 Processing Programs: A First Look at Interpretation |
25.1 Representing Arithmetic |
25.2 Writing an Interpreter |
25.3 A First Taste of “Semantics” |
25.4 Desugaring: Growing the Language Without Enlarging It |
25.4.1 Extension: Binary Subtraction |
25.4.2 Extension: Unary Negation |
25.5 A Three-Stage Pipeline |
|
26 Interpreting Conditionals |
26.1 The Design Space of Conditionals |
26.2 The Game Plan for Conditionals |
26.2.1 The Interpreter’s Type |
26.2.2 Updating Arithmetic |
26.2.3 Defensive Programming |
26.2.4 Interpreting Conditionals |
26.3 Growing the Conditional Language |
|
27 Interpreting Functions |
27.1 Adding Functions to the Language |
27.1.1 Defining Data Representations |
27.1.2 Growing the Interpreter |
27.1.3 Substitution |
27.1.4 The Interpreter, Resumed |
27.1.5 Oh Wait, There’s More! |
27.2 From Substitution to Environments |
27.2.1 Introducing the Environment |
27.2.2 Interpreting with Environments |
27.2.3 Deferring Correctly |
27.2.4 Scope |
27.2.5 How Bad Is It? |
27.2.6 The Top-Level Scope |
27.2.7 Exposing the Environment |
27.3 Functions Anywhere |
27.3.1 Functions as Expressions and Values |
27.3.2 A Small Improvement |
27.3.3 Nesting Functions |
27.3.4 Nested Functions and Substitution |
27.3.5 Updating Values |
27.3.6 Sugaring Over Anonymity |
27.4 Recursion and Non-Termination |
27.5 Functions and
Predictability |
|
28 Reasoning about Programs: A First Look at Types |
28.1 Types as a Static Discipline |
28.2 The Principle of Substitutability |
28.3 A Type(d) Language and Type Errors |
28.3.1 Assume-Guarantee Reasoning |
28.4 A Type Checker for Expressions and Functions |
28.4.1 A Pure Checker |
28.4.2 A Calculator and Checker |
28.4.3 Type-Checking Versus Interpretation |
28.5 Type-Checking, Testing, and Coverage |
28.6 Recursion in Code |
28.6.1 A First Attempt at Typing Recursion |
28.6.2 Program Termination |
28.6.3 Typing Recursion |
28.7 Recursion in Data |
28.7.1 Recursive Datatype Definitions |
28.7.2 Introduced Types |
28.7.3 Selectors |
28.7.4 Pattern-Matching and Desugaring |
|
29 Safety and Soundness |
29.1 Safety |
29.2 “Untyped” Languages |
29.3 The Central Theorem: Type Soundness |
29.4 Types, Time, and Space |
29.5 Types Versus Safety |
|
30 Parametric Polymorphism |
30.1 Parameterized Types |
30.2 Making Parameters Explicit |
30.3 Rank-1 Polymorphism |
30.4 Interpreting Rank-1 Polymorphism as Desugaring |
30.5 Alternate Implementations |
30.6 Relational Parametricity |
|
31 Type Inference |
31.1 Type Inference as Type Annotation Insertion |
31.2 Understanding Inference |
31.2.1 Constraint Generation |
31.2.2 Constraint Solving Using Unification |
31.3 Type Checking and Type Errors |
31.4 Over- and Under-Constrained Solutions |
31.5 Let-Polymorphism |
|
32 Mutation: Structures and Variables |
32.1 Separating Meaning from Notation |
32.2 Mutation and Closures |
32.3 Mutable Structures |
32.3.1 Extending the Language Representation |
32.3.2 The Interpretation of Boxes |
32.3.3 Can the Environment Help? |
32.3.4 Welcome to the Store |
32.3.5 Interpreting Boxes |
32.3.6 Implementing Mutation: Subtleties and Variations |
32.4 Variables |
32.4.1 The Syntax of Variable Assignment |
32.4.2 Interpreting Variables |
32.4.3 Reference Parameter Passing |
32.5 The Design of Stateful Language Operations |
32.6 Typing State |
32.6.1 Mutation and Polymorphism |
32.6.2 Typing the Initial Value |
|
33 Objects: Interpretation and Types |
33.1 Interpreting Objects |
33.2 Objects by Desugaring |
33.2.1 Objects as Named Collections |
33.2.2 Constructors |
33.2.3 State |
33.2.4 Private Members |
33.2.5 Static Members |
33.2.6 Objects with Self-Reference |
33.2.6.1 Self-Reference Using Mutation |
33.2.6.2 Self-Reference Without Mutation |
33.2.7 Dynamic Dispatch |
33.3 Member Access Design Space |
33.4 What (Goes In) Else? |
33.4.1 Classes |
33.4.2 Prototypes |
33.4.3 Multiple Inheritance |
33.4.4 Super-Duper! |
33.4.5 Mixins and Traits |
33.5 Object Classification and Object Equality |
33.6 Types for Objects |
33.6.1 Subtyping |
33.6.1.1 Subtyping Functions |
33.6.1.2 Subtyping and Information Hiding |
33.6.1.3 Implementing Subtyping |
33.6.2 Types for Self-Reference |
33.6.3 Nominal Types |
|
34 Control Operations |
34.1 Control on the Web |
34.1.1 Program Decomposition into Now and Later |
34.1.2 A Partial Solution |
34.1.3 Achieving Statelessness |
34.1.4 Interaction with State |
34.2 Conversion to Continuation-Passing Style |
34.2.1 Implementation by Desugaring |
34.2.2 Understanding the Output |
34.2.3 An Interaction Primitive by Transformation |
34.3 Implementation in the Core |
34.3.1 Converting the Interpreter |
34.3.2 An Interaction Primitive in the Core |
34.4 Generators |
34.5 Continuations and Stacks |
34.6 Tail Calls |
|
35 Pyret for Racketeers and Schemers |
35.1 Numbers, Strings, and Booleans |
35.2 Infix Expressions |
35.3 Function Definition and Application |
35.4 Tests |
35.5 Variable Names |
35.6 Data Definitions |
35.7 Conditionals |
35.8 Lists |
35.9 First-Class Functions |
35.10 Annotations |
35.11 What Else? |
|
36 Glossary |