On this page:
Programming and Programming Languages
Saturday, May 9th, 2020 7:34:05pm

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 Acknowledgments

    3 Basic Data and Expressions

      3.1 Numbers

      3.2 Expressions Versus Values

      3.3 Variables to Name Values

      3.4 Strings

        3.4.1 Multi-Line Strings

        3.4.2 Operations on Strings

      3.5 Booleans

        3.5.1 Other Comparisons

        3.5.2 Other Boolean-Producing Operations

        3.5.3 Combining Booleans

        3.5.4 Using Booleans

      3.6 Evaluating by Reducing Expressions

      3.7 Images

      3.8 Roughnums

    4 From Repeated Expressions to Functions

      4.1 Example: Moon Weight

      4.2 Example: Japanese Flag

      4.3 Tests: Keeping Track of Examples

      4.4 Type Annotations

      4.5 Defining Functions in Steps

    5 Introduction to Tabular Data

      5.1 Creating Tabular Data

      5.2 Processing Rows

        5.2.1 Keeping

        5.2.2 Ordering

        5.2.3 Combining Keeping and Ordering

        5.2.4 Extending

        5.2.5 Transforming, Cleansing, and Normalizing

        5.2.6 Selecting

        5.2.7 Summary of Row-Wise Table Operations

    6 From Tables to Lists

      6.1 Basic Statistical Questions

      6.2 Extracting a Column from a Table

      6.3 Understanding Lists

        6.3.1 Lists as Anonymous Data

        6.3.2 Creating Literal Lists

      6.4 Operating on Lists

        6.4.1 Built-In Operations on Lists

        6.4.2 Combining Lists and Tables

    7 Processing Lists

      7.1 Making Lists and Taking Them Apart

      7.2 Some Example Exercises

      7.3 Structural Problems with Scalar Answers

        7.3.1 my-len: Examples

        7.3.2 my-sum: Examples

        7.3.3 From Examples to Code

      7.4 Structural Problems with List Answers

        7.4.1 my-str-len: Examples and Code

        7.4.2 my-pos-nums: Examples and Code

        7.4.3 my-alternating: First Attempt

        7.4.4 my-running-sum: First Attempt

      7.5 Structural Problems with Sub-Domains

        7.5.1 my-max: Examples

        7.5.2 my-max: From Examples to Code

        7.5.3 my-alternating: Examples and Code

      7.6 More Structural Problems with Scalar Answers

        7.6.1 my-avg: Examples

      7.7 Structural Problems with Accumulators

        7.7.1 my-running-sum: Examples and Code

        7.7.2 my-alternating: Examples and Code

      7.8 Dealing with Multiple Answers

        7.8.1 uniq: Problem Setup

        7.8.2 uniq: Examples

        7.8.3 uniq: Code

        7.8.4 uniq: Reducing Computation

        7.8.5 uniq: Example and Code Variations

        7.8.6 uniq: Why Produce a List?

      7.9 Monomorphic Lists and Polymorphic Types

    8 Introduction to Structured Data

      8.1 Understanding the Kinds of Compound Data

        8.1.1 A First Peek at Structured Data

        8.1.2 A First Peek at Conditional Data

      8.2 Defining and Creating Structured and Conditional Data

        8.2.1 Defining and Creating Structured Data

        8.2.2 Annotations for Structured Data

        8.2.3 Defining and Creating Conditional Data

      8.3 Programming with Structured and Conditional Data

        8.3.1 Extracting Fields from Structured Data

        8.3.2 Telling Apart Variants of Conditional Data

        8.3.3 Processing Fields of Variants

    9 Collections of Structured Data

      9.1 Lists as Collective Data

      9.2 Sets as Collective Data

        9.2.1 Picking Elements from Sets

        9.2.2 Computing with Sets

      9.3 Combining Structured and Collective Data

    10 Recursive Data

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

      16.1 A First Example

      16.2 The New Form of Analysis

      16.3 An Example: Queues from Lists

        16.3.1 List Representations

        16.3.2 A First Analysis

        16.3.3 More Liberal Sequences of Operations

        16.3.4 A Second Analysis

        16.3.5 Amortization Versus Individual Operations

      16.4 Reading More

    17 Sharing and Equality

      17.1 Re-Examining Equality

      17.2 The Cost of Evaluating References

      17.3 On the Internet, Nobody Knows You’re a DAG

      17.4 From Acyclicity to Cycles

    18 Graphs

      18.1 Understanding Graphs

      18.2 Representations

        18.2.1 Links by Name

        18.2.2 Links by Indices

        18.2.3 A List of Edges

        18.2.4 Abstracting Representations

      18.3 Measuring Complexity for Graphs

      18.4 Reachability

        18.4.1 Simple Recursion

        18.4.2 Cleaning up the Loop

        18.4.3 Traversal with Memory

        18.4.4 A Better Interface

      18.5 Depth- and Breadth-First Traversals

      18.6 Graphs With Weighted Edges

      18.7 Shortest (or Lightest) Paths

      18.8 Moravian Spanning Trees

        18.8.1 The Problem

        18.8.2 A Greedy Solution

        18.8.3 Another Greedy Solution

        18.8.4 A Third Solution

        18.8.5 Checking Component Connectedness

    19 State, Change, and More Equality

      19.1 A Canonical Mutable Structure

      19.2 Equality and Mutation

        19.2.1 Observing Mutation

        19.2.2 What it Means to be Identical

        19.2.3 An Additional Challenge

      19.3 Recursion and Cycles from Mutation

        19.3.1 Partial Definitions

        19.3.2 Recursive Functions

        19.3.3 Premature Evaluation

        19.3.4 Cyclic Lists Versus Streams

      19.4 From Identifiers to Variables

      19.5 Interaction of Mutation with Closures: Counters

        19.5.1 Implementation Using Boxes

        19.5.2 Implementation Using Variables

      19.6 A Family of Equality Predicates

        19.6.1 A Hierarchy of Equality

        19.6.2 Space and Time Complexity

        19.6.3 Comparing Functions

    20 Algorithms That Exploit State

      20.1 Disjoint Sets Redux

        20.1.1 Optimizations

        20.1.2 Analysis

      20.2 Set Membership by Hashing Redux

        20.2.1 Improving Access Time

        20.2.2 Better Hashing

        20.2.3 Bloom Filters

      20.3 Avoiding Recomputation by Remembering Answers

        20.3.1 An Interesting Numeric Sequence

          20.3.1.1 Using State to Remember Past Answers

          20.3.1.2 From a Tree of Computation to a DAG

          20.3.1.3 The Complexity of Numbers

          20.3.1.4 Abstracting Memoization

        20.3.2 Edit-Distance for Spelling Correction

        20.3.3 Nature as a Fat-Fingered Typist

        20.3.4 Dynamic Programming

          20.3.4.1 Catalan Numbers with Dynamic Programming

          20.3.4.2 Levenshtein Distance and Dynamic Programming

        20.3.5 Contrasting Memoization and Dynamic Programming

    21 Processing Programs: Parsing

      21.1 Understanding Languages by Writing Programs About Them

      21.2 Everything (We Will Say) About Parsing

        21.2.1 A Lightweight, Built-In First Half of a Parser

        21.2.2 Completing the Parser

        21.2.3 Coda

    22 Processing Programs: A First Look at Interpretation

      22.1 Representing Arithmetic

      22.2 Writing an Interpreter

      22.3 A First Taste of “Semantics”

      22.4 Desugaring: Growing the Language Without Enlarging It

        22.4.1 Extension: Binary Subtraction

        22.4.2 Extension: Unary Negation

      22.5 A Three-Stage Pipeline

    23 Interpreting Conditionals

      23.1 The Design Space of Conditionals

      23.2 The Game Plan for Conditionals

        23.2.1 The Interpreter’s Type

        23.2.2 Updating Arithmetic

        23.2.3 Defensive Programming

        23.2.4 Interpreting Conditionals

      23.3 Growing the Conditional Language

    24 Interpreting Functions

      24.1 Adding Functions to the Language

        24.1.1 Defining Data Representations

        24.1.2 Growing the Interpreter

        24.1.3 Substitution

        24.1.4 The Interpreter, Resumed

        24.1.5 Oh Wait, There’s More!

      24.2 From Substitution to Environments

        24.2.1 Introducing the Environment

        24.2.2 Interpreting with Environments

        24.2.3 Deferring Correctly

        24.2.4 Scope

        24.2.5 How Bad Is It?

        24.2.6 The Top-Level Scope

        24.2.7 Exposing the Environment

      24.3 Functions Anywhere

        24.3.1 Functions as Expressions and Values

        24.3.2 A Small Improvement

        24.3.3 Nesting Functions

        24.3.4 Nested Functions and Substitution

        24.3.5 Updating Values

        24.3.6 Sugaring Over Anonymity

      24.4 Recursion and Non-Termination

      24.5 Functions and Predictability

    25 Reasoning about Programs: A First Look at Types

      25.1 Types as a Static Discipline

      25.2 The Principle of Substitutability

      25.3 A Type(d) Language and Type Errors

        25.3.1 Assume-Guarantee Reasoning

      25.4 A Type Checker for Expressions and Functions

        25.4.1 A Pure Checker

        25.4.2 A Calculator and Checker

        25.4.3 Type-Checking Versus Interpretation

      25.5 Type-Checking, Testing, and Coverage

      25.6 Recursion in Code

        25.6.1 A First Attempt at Typing Recursion

        25.6.2 Program Termination

        25.6.3 Typing Recursion

      25.7 Recursion in Data

        25.7.1 Recursive Datatype Definitions

        25.7.2 Introduced Types

        25.7.3 Selectors

        25.7.4 Pattern-Matching and Desugaring

    26 Safety and Soundness

      26.1 Safety

      26.2 “Untyped” Languages

      26.3 The Central Theorem: Type Soundness

      26.4 Types, Time, and Space

      26.5 Types Versus Safety

    27 Parametric Polymorphism

      27.1 Parameterized Types

      27.2 Making Parameters Explicit

      27.3 Rank-1 Polymorphism

      27.4 Interpreting Rank-1 Polymorphism as Desugaring

      27.5 Alternate Implementations

      27.6 Relational Parametricity

    28 Type Inference

      28.1 Type Inference as Type Annotation Insertion

      28.2 Understanding Inference

        28.2.1 Constraint Generation

        28.2.2 Constraint Solving Using Unification

      28.3 Type Checking and Type Errors

      28.4 Over- and Under-Constrained Solutions

      28.5 Let-Polymorphism

    29 Mutation: Structures and Variables

      29.1 Separating Meaning from Notation

      29.2 Mutation and Closures

      29.3 Mutable Structures

        29.3.1 Extending the Language Representation

        29.3.2 The Interpretation of Boxes

        29.3.3 Can the Environment Help?

        29.3.4 Welcome to the Store

        29.3.5 Interpreting Boxes

        29.3.6 Implementing Mutation: Subtleties and Variations

      29.4 Variables

        29.4.1 The Syntax of Variable Assignment

        29.4.2 Interpreting Variables

        29.4.3 Reference Parameter Passing

      29.5 The Design of Stateful Language Operations

      29.6 Typing State

        29.6.1 Mutation and Polymorphism

        29.6.2 Typing the Initial Value

    30 Objects: Interpretation and Types

      30.1 Interpreting Objects

      30.2 Objects by Desugaring

        30.2.1 Objects as Named Collections

        30.2.2 Constructors

        30.2.3 State

        30.2.4 Private Members

        30.2.5 Static Members

        30.2.6 Objects with Self-Reference

          30.2.6.1 Self-Reference Using Mutation

          30.2.6.2 Self-Reference Without Mutation

        30.2.7 Dynamic Dispatch

      30.3 Member Access Design Space

      30.4 What (Goes In) Else?

        30.4.1 Classes

        30.4.2 Prototypes

        30.4.3 Multiple Inheritance

        30.4.4 Super-Duper!

        30.4.5 Mixins and Traits

      30.5 Object Classification and Object Equality

      30.6 Types for Objects

        30.6.1 Subtyping

          30.6.1.1 Subtyping Functions

          30.6.1.2 Subtyping and Information Hiding

          30.6.1.3 Implementing Subtyping

        30.6.2 Types for Self-Reference

        30.6.3 Nominal Types

    31 Control Operations

      31.1 Control on the Web

        31.1.1 Program Decomposition into Now and Later

        31.1.2 A Partial Solution

        31.1.3 Achieving Statelessness

        31.1.4 Interaction with State

      31.2 Conversion to Continuation-Passing Style

        31.2.1 Implementation by Desugaring

        31.2.2 Understanding the Output

        31.2.3 An Interaction Primitive by Transformation

      31.3 Implementation in the Core

        31.3.1 Converting the Interpreter

        31.3.2 An Interaction Primitive in the Core

      31.4 Generators

      31.5 Continuations and Stacks

      31.6 Tail Calls

    32 Pyret for Racketeers and Schemers

      32.1 Numbers, Strings, and Booleans

      32.2 Infix Expressions

      32.3 Function Definition and Application

      32.4 Tests

      32.5 Variable Names

      32.6 Data Definitions

      32.7 Conditionals

      32.8 Lists

      32.9 First-Class Functions

      32.10 Annotations

      32.11 What Else?

    33 Glossary