On this page:
Programming and Programming Languages
Saturday, October 24th, 2020 12:53:39pm

Programming and Programming Languages

Shriram Krishnamurthi, Benjamin S. Lerner, Joe Gibbs Politz, Kathi Fisler

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 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