On this page:
Programming and Programming Languages
Saturday, December 31st, 2016 11:25:27pm

Programming and Programming Languages

Shriram Krishnamurthi, Benjamin S. Lerner, Joe Gibbs Politz

This is the new, unstable edition of the book, under constant revision. The current, stable edition is also available.

    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 uqiq: 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 Variable Names

      34.5 Data Definitions

      34.6 Conditionals

      34.7 Annotations

      34.8 What Else?

    35 Glossary