On this page:
Programming and Programming Languages
Tuesday, December 2nd, 2014 7:34:24am

Programming and Programming Languages

Shriram Krishnamurthi

Note: This edition is out of date. The language has improved in many ways, making some of the code in this book no longer executable. In addition, there are many revisions, improvements, and additions to the book. Please instead refer to the 2015 edition.

    1 Introduction

      1.1 My Philosophy

      1.2 Predictability as a Theme

      1.3 The Structure of This Book

      1.4 The Language of This Book

    2 Programming in Pyret

      2.1 Values

      2.2 Expressions

        2.2.1 Aggregate Values

        2.2.2 Precedence

      2.3 Functions: Abstracting Over Expressions

      2.4 Examples and Testing: Predicting Behavior

      2.5 Data Structures

        2.5.1 Dangerous Field Accesses

      2.6 Annotations

        2.6.1 Annotation Refinement

    3 Interactive Games as Reactive Programs

      3.1 About Reactive Animations

      3.2 Preliminaries

      3.3 Version: Airplane Moving Across the Screen

        3.3.1 Updating the World State

        3.3.2 Displaying the World State

        3.3.3 Observing Time (and Combining the Pieces)

      3.4 Version: Wrapping Around

      3.5 Version: Descending

        3.5.1 Moving the Airplane

        3.5.2 Drawing the Scene

        3.5.3 Finishing Touches

      3.6 Version: Responding to Keystrokes

      3.7 Version: Landing

      3.8 Version: A Fixed Balloon

      3.9 Version: Keep Your Eye on the Tank

      3.10 Version: The Balloon Moves, Too

      3.11 Version: One, Two, ..., Ninety-Nine Luftballons!

    4 Predicting Growth

      4.1 A Little (True) Story

      4.2 The Analytical Idea

      4.3 A Cost Model for Pyret Running Time

      4.4 The Size of the Input

      4.5 The Tabular Method for Singly-Structurally-Recursive Functions

      4.6 Creating Recurrences

      4.7 A Notation for Functions

      4.8 Comparing Functions

      4.9 Combining Big-Oh Without Woe

      4.10 Solving Recurrences

    5 Sets Appeal

      5.1 Representing Sets by Lists

        5.1.1 Representation Choices

        5.1.2 Time Complexity

        5.1.3 Choosing Between Representations

        5.1.4 Other Operations

      5.2 Making Sets Grow on Trees

        5.2.1 Converting Values to Ordered Values

        5.2.2 Using Binary Trees

        5.2.3 A Fine Balance: Tree Surgery

          5.2.3.1 Left-Left Case

          5.2.3.2 Left-Right Case

          5.2.3.3 Any Other Cases?

    6 Halloween Analysis

      6.1 A First Example

      6.2 The New Form of Analysis

      6.3 An Example: Queues from Lists

        6.3.1 List Representations

        6.3.2 A First Analysis

        6.3.3 More Liberal Sequences of Operations

        6.3.4 A Second Analysis

        6.3.5 Amortization Versus Individual Operations

      6.4 Reading More

    7 Fun with Functions

      7.1 A Little Calculus

      7.2 Streams From Functions

      7.3 Combining Forces: Streams of Derivatives

    8 Sharing and Equality

      8.1 Re-Examining Equality

      8.2 The Cost of Evaluating References

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

      8.4 From Acyclicity to Cycles

    9 Graphs

      9.1 Representations

        9.1.1 Links by Name

        9.1.2 Links by Indices

        9.1.3 A List of Edges

        9.1.4 Abstracting Representations

      9.2 Measuring Complexity for Graphs

      9.3 Reachability

        9.3.1 Simple Recursion

        9.3.2 Cleaning up the Loop

        9.3.3 Traversal with Memory

        9.3.4 A Better Interface

      9.4 Depth- and Breadth-First Traversals

      9.5 Graphs With Weighted Edges

      9.6 Shortest (or Lightest) Paths

      9.7 Moravian Spanning Trees

        9.7.1 The Problem

        9.7.2 A Greedy Solution

        9.7.3 Another Greedy Solution

        9.7.4 A Third Solution

        9.7.5 Checking Component Connectedness

    10 State, Change, and More Equality

      10.1 A Canonical Mutable Structure

      10.2 What it Means to be Identical

      10.3 Recursion and Cycles from Mutation

        10.3.1 Partial Definitions

        10.3.2 Recursive Functions

        10.3.3 Premature Evaluation

        10.3.4 Cyclic Lists Versus Streams

      10.4 From Identifiers to Variables

      10.5 Interaction of Mutation with Closures: Counters

        10.5.1 Implementation Using Boxes

        10.5.2 Implementation Using Variables

      10.6 A Family of Equality Predicates

        10.6.1 A Hierarchy of Equality

        10.6.2 Space and Time Complexity

        10.6.3 Comparing Functions

    11 Algorithms That Exploit State

      11.1 Disjoint Sets Redux

        11.1.1 Optimizations

        11.1.2 Analysis

      11.2 Set Membership by Hashing Redux

        11.2.1 Improving Access Time

        11.2.2 Better Hashing

        11.2.3 Bloom Filters

      11.3 Avoiding Recomputation by Remembering Answers

        11.3.1 An Interesting Numeric Sequence

          11.3.1.1 Using State to Remember Past Answers

          11.3.1.2 From a Tree of Computation to a DAG

          11.3.1.3 The Complexity of Numbers

          11.3.1.4 Abstracting Memoization

        11.3.2 Edit-Distance for Spelling Correction

        11.3.3 Nature as a Fat-Fingered Typist

        11.3.4 Dynamic Programming

          11.3.4.1 Catalan Numbers with Dynamic Programming

          11.3.4.2 Levenshtein Distance and Dynamic Programming

        11.3.5 Contrasting Memoization and Dynamic Programming

    12 Processing Programs: Parsing

      12.1 Understanding Languages by Writing Programs About Them

      12.2 Everything (We Will Say) About Parsing

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

        12.2.2 Completing the Parser

        12.2.3 Coda

    13 Processing Programs: A First Look at Interpretation

      13.1 Representing Arithmetic

      13.2 Writing an Interpreter

      13.3 A First Taste of “Semantics”

      13.4 Desugaring: Growing the Language Without Enlarging It

        13.4.1 Extension: Binary Subtraction

        13.4.2 Extension: Unary Negation

      13.5 A Three-Stage Pipeline

    14 Interpreting Conditionals

      14.1 The Design Space of Conditionals

      14.2 The Game Plan for Conditionals

        14.2.1 The Interpreter’s Type

        14.2.2 Updating Arithmetic

        14.2.3 Defensive Programming

        14.2.4 Interpreting Conditionals

      14.3 Growing the Conditional Language

    15 Interpreting Functions

      15.1 Adding Functions to the Language

        15.1.1 Defining Data Representations

        15.1.2 Growing the Interpreter

        15.1.3 Substitution

        15.1.4 The Interpreter, Resumed

        15.1.5 Oh Wait, There’s More!

      15.2 From Substitution to Environments

        15.2.1 Introducing the Environment

        15.2.2 Interpreting with Environments

        15.2.3 Deferring Correctly

        15.2.4 Scope

        15.2.5 How Bad Is It?

        15.2.6 The Top-Level Scope

        15.2.7 Exposing the Environment

      15.3 Functions Anywhere

        15.3.1 Functions as Expressions and Values

        15.3.2 A Small Improvement

        15.3.3 Nesting Functions

        15.3.4 Nested Functions and Substitution

        15.3.5 Updating Values

        15.3.6 Sugaring Over Anonymity

      15.4 Recursion and Non-Termination

      15.5 Functions and Predictability

    16 Reasoning about Programs: A First Look at Types

      16.1 Types as a Static Discipline

      16.2 The Principle of Substitutability

      16.3 A Type(d) Language and Type Errors

        16.3.1 Assume-Guarantee Reasoning

      16.4 A Type Checker for Expressions and Functions

        16.4.1 A Pure Checker

        16.4.2 A Calculator and Checker

        16.4.3 Type-Checking Versus Interpretation

      16.5 Type-Checking, Testing, and Coverage

      16.6 Recursion in Code

        16.6.1 A First Attempt at Typing Recursion

        16.6.2 Program Termination

        16.6.3 Typing Recursion

      16.7 Recursion in Data

        16.7.1 Recursive Datatype Definitions

        16.7.2 Introduced Types

        16.7.3 Selectors

        16.7.4 Pattern-Matching and Desugaring

    17 Safety and Soundness

      17.1 Safety

      17.2 “Untyped” Languages

      17.3 The Central Theorem: Type Soundness

      17.4 Types, Time, and Space

      17.5 Types Versus Safety

    18 Parametric Polymorphism

      18.1 Parameterized Types

      18.2 Making Parameters Explicit

      18.3 Rank-1 Polymorphism

      18.4 Interpreting Rank-1 Polymorphism as Desugaring

      18.5 Alternate Implementations

      18.6 Relational Parametricity

    19 Type Inference

      19.1 Type Inference as Type Annotation Insertion

      19.2 Understanding Inference

        19.2.1 Constraint Generation

        19.2.2 Constraint Solving Using Unification

      19.3 Type Checking and Type Errors

      19.4 Over- and Under-Constrained Solutions

      19.5 Let-Polymorphism

    20 Mutation: Structures and Variables

      20.1 Separating Meaning from Notation

      20.2 Mutation and Closures

      20.3 Mutable Structures

        20.3.1 Extending the Language Representation

        20.3.2 The Interpretation of Boxes

        20.3.3 Can the Environment Help?

        20.3.4 Welcome to the Store

        20.3.5 Interpreting Boxes

        20.3.6 Implementing Mutation: Subtleties and Variations

      20.4 Variables

        20.4.1 The Syntax of Variable Assignment

        20.4.2 Interpreting Variables

        20.4.3 Reference Parameter Passing

      20.5 The Design of Stateful Language Operations

      20.6 Typing State

        20.6.1 Mutation and Polymorphism

        20.6.2 Typing the Initial Value

    21 Objects: Interpretation and Types

      21.1 Interpreting Objects

      21.2 Objects by Desugaring

        21.2.1 Objects as Named Collections

        21.2.2 Constructors

        21.2.3 State

        21.2.4 Private Members

        21.2.5 Static Members

        21.2.6 Objects with Self-Reference

          21.2.6.1 Self-Reference Using Mutation

          21.2.6.2 Self-Reference Without Mutation

        21.2.7 Dynamic Dispatch

      21.3 Member Access Design Space

      21.4 What (Goes In) Else?

        21.4.1 Classes

        21.4.2 Prototypes

        21.4.3 Multiple Inheritance

        21.4.4 Super-Duper!

        21.4.5 Mixins and Traits

      21.5 Object Classification and Object Equality

      21.6 Types for Objects

        21.6.1 Subtyping

          21.6.1.1 Subtyping Functions

          21.6.1.2 Subtyping and Information Hiding

          21.6.1.3 Implementing Subtyping

        21.6.2 Types for Self-Reference

        21.6.3 Nominal Types

    22 Control Operations

      22.1 Control on the Web

        22.1.1 Program Decomposition into Now and Later

        22.1.2 A Partial Solution

        22.1.3 Achieving Statelessness

        22.1.4 Interaction with State

      22.2 Conversion to Continuation-Passing Style

        22.2.1 Implementation by Desugaring

        22.2.2 Understanding the Output

        22.2.3 An Interaction Primitive by Transformation

      22.3 Implementation in the Core

        22.3.1 Converting the Interpreter

        22.3.2 An Interaction Primitive in the Core

      22.4 Generators

      22.5 Continuations and Stacks

      22.6 Tail Calls

    23 Glossary