Programming and Programming Languages

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 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
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 Wrapping up: Composing Functions
7 Introduction to Tabular Data
7.1 Creating Tabular Data
7.2 Processing Rows
7.2.1 Keeping
7.2.2 Ordering
7.2.3 Combining Keeping and Ordering
7.2.4 Extending
7.2.5 Transforming, Cleansing, and Normalizing
7.2.6 Selecting
7.2.7 Summary of Row-Wise Table Operations
8 From Tables to Lists
8.1 Basic Statistical Questions
8.2 Extracting a Column from a Table
8.3 Understanding Lists
8.3.1 Lists as Anonymous Data
8.3.2 Creating Literal Lists
8.4 Operating on Lists
8.4.1 Built-In Operations on Lists
8.4.2 Combining Lists and Tables
9 Processing Lists
9.1 Making Lists and Taking Them Apart
9.2 Some Example Exercises
9.3 Structural Problems with Scalar Answers
9.3.1 my-len: Examples
9.3.2 my-sum: Examples
9.3.3 From Examples to Code
9.4 Structural Problems with List Answers
9.4.1 my-str-len: Examples and Code
9.4.2 my-pos-nums: Examples and Code
9.4.3 my-alternating: First Attempt
9.4.4 my-running-sum: First Attempt
9.5 Structural Problems with Sub-Domains
9.5.1 my-max: Examples
9.5.2 my-max: From Examples to Code
9.5.3 my-alternating: Examples and Code
9.6 More Structural Problems with Scalar Answers
9.6.1 my-avg: Examples
9.7 Structural Problems with Accumulators
9.7.1 my-running-sum: Examples and Code
9.7.2 my-alternating: Examples and Code
9.8 Dealing with Multiple Answers
9.8.1 uniq: Problem Setup
9.8.2 uniq: Examples
9.8.3 uniq: Code
9.8.4 uniq: Reducing Computation
9.8.5 uniq: Example and Code Variations
9.8.6 uniq: Why Produce a List?
9.9 Monomorphic Lists and Polymorphic Types
10 Introduction to Structured Data
10.1 Understanding the Kinds of Compound Data
10.1.1 A First Peek at Structured Data
10.1.2 A First Peek at Conditional Data
10.2 Defining and Creating Structured and Conditional Data
10.2.1 Defining and Creating Structured Data
10.2.2 Annotations for Structured Data
10.2.3 Defining and Creating Conditional Data
10.3 Programming with Structured and Conditional Data
10.3.1 Extracting Fields from Structured Data
10.3.2 Telling Apart Variants of Conditional Data
10.3.3 Processing Fields of Variants
11 Collections of Structured Data
11.1 Lists as Collective Data
11.2 Sets as Collective Data
11.2.1 Picking Elements from Sets
11.2.2 Computing with Sets
11.3 Combining Structured and Collective Data
12 Recursive Data
13 Interactive Games as Reactive Systems
13.1 About Reactive Animations
13.2 Preliminaries
13.3 Version: Airplane Moving Across the Screen
13.3.1 Updating the World State
13.3.2 Displaying the World State
13.3.3 Observing Time (and Combining the Pieces)
13.4 Version: Wrapping Around
13.5 Version: Descending
13.5.1 Moving the Airplane
13.5.2 Drawing the Scene
13.5.3 Finishing Touches
13.6 Version: Responding to Keystrokes
13.7 Version: Landing
13.8 Version: A Fixed Balloon
13.9 Version: Keep Your Eye on the Tank
13.10 Version: The Balloon Moves, Too
13.11 Version: One, Two, ..., Ninety-Nine Luftballons!
14 Examples, Testing, and Program Checking
14.1 From Examples to Tests
14.2 More Refined Comparisons
14.3 When Tests Fail
14.4 Oracles for Testing
14.5 Testing Erroneous Programs
15 Functions as Data
15.1 A Little Calculus
15.2 A Helpful Shorthand for Anonymous Functions
15.3 Streams From Functions
15.4 Combining Forces: Streams of Derivatives
16 Predicting Growth
16.1 A Little (True) Story
16.2 The Analytical Idea
16.3 A Cost Model for Pyret Running Time
16.4 The Size of the Input
16.5 The Tabular Method for Singly-Structurally-Recursive Functions
16.6 Creating Recurrences
16.7 A Notation for Functions
16.8 Comparing Functions
16.9 Combining Big-Oh Without Woe
16.10 Solving Recurrences
17 Sets Appeal
17.1 Representing Sets by Lists
17.1.1 Representation Choices
17.1.2 Time Complexity
17.1.3 Choosing Between Representations
17.1.4 Other Operations
17.2 Making Sets Grow on Trees
17.2.1 Converting Values to Ordered Values
17.2.2 Using Binary Trees
17.2.3 A Fine Balance: Tree Surgery
18 Halloween Analysis
18.1 A First Example
18.2 The New Form of Analysis
18.3 An Example: Queues from Lists
18.3.1 List Representations
18.3.2 A First Analysis
18.3.3 More Liberal Sequences of Operations
18.3.4 A Second Analysis
18.3.5 Amortization Versus Individual Operations
18.4 Reading More
19 Sharing and Equality
19.1 Re-Examining Equality
19.2 The Cost of Evaluating References
19.3 On the Internet, Nobody Knows You're a DAG
19.4 From Acyclicity to Cycles
20 Graphs
20.1 Understanding Graphs
20.2 Representations
20.2.1 Links by Name
20.2.2 Links by Indices
20.2.3 A List of Edges
20.2.4 Abstracting Representations
20.3 Measuring Complexity for Graphs
20.4 Reachability
20.4.1 Simple Recursion
20.4.2 Cleaning up the Loop
20.4.3 Traversal with Memory
20.4.4 A Better Interface
20.5 Depth- and Breadth-First Traversals
20.6 Graphs With Weighted Edges
20.7 Shortest (or Lightest) Paths
20.8 Moravian Spanning Trees
20.8.1 The Problem
20.8.2 A Greedy Solution
20.8.3 Another Greedy Solution
20.8.4 A Third Solution
20.8.5 Checking Component Connectedness
21 State, Change, and More Equality
21.1 A Canonical Mutable Structure
21.2 Equality and Mutation
21.2.1 Observing Mutation
21.2.2 What it Means to be Identical
21.2.3 An Additional Challenge
21.3 Recursion and Cycles from Mutation
21.3.1 Partial Definitions
21.3.2 Recursive Functions
21.3.3 Premature Evaluation
21.3.4 Cyclic Lists Versus Streams
21.4 From Identifiers to Variables
21.5 Interaction of Mutation with Closures: Counters
21.5.1 Implementation Using Boxes
21.5.2 Implementation Using Variables
21.6 A Family of Equality Predicates
21.6.1 A Hierarchy of Equality
21.6.2 Space and Time Complexity
21.6.3 Comparing Functions
22 Algorithms That Exploit State
22.1 Disjoint Sets Redux
22.1.1 Optimizations
22.1.2 Analysis
22.2 Set Membership by Hashing Redux
22.2.1 Improving Access Time
22.2.2 Better Hashing
22.2.3 Bloom Filters
22.3 Avoiding Recomputation by Remembering Answers
22.3.1 An Interesting Numeric Sequence
22.3.2 Edit-Distance for Spelling Correction
22.3.3 Nature as a Fat-Fingered Typist
22.3.4 Dynamic Programming
22.3.5 Contrasting Memoization and Dynamic Programming
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.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.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