On this page:
Programming and Programming Languages
Monday, September 1st, 2014 9:03:19pm

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 2014 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 The Value(s) of Computing

      2.1 Simple Programs

      2.2 Less Simple Programs

      2.3 Precedence

      2.4 Predicting the Value of Expressions

    3 Functions

      3.1 Abstracting Expressions

      3.2 Functions as Expression Abstractions

      3.3 Testing

      3.4 Annotations

    4 Data Structures

    5 Fun with Functions

      5.1 A Little Calculus

      5.2 Streams From Functions

      5.3 Combining Forces: Streams of Derivatives

    6 Predicting Growth

      6.1 A Little (True) Story

      6.2 The Analytical Idea

      6.3 A Cost Model for Pyret Running Time

      6.4 The Size of the Input

      6.5 The Tabular Method for Singly-Structurally-Recursive Functions

      6.6 Creating Recurrences

      6.7 A Notation for Functions

      6.8 Comparing Functions

      6.9 Combining Big-Oh Without Woe

      6.10 Solving Recurrences

    7 Sets Appeal

      7.1 Representing Sets by Lists

        7.1.1 Representation Choices

        7.1.2 Time Complexity

        7.1.3 Choosing Between Representations

        7.1.4 Other Operations

      7.2 Making Sets Grow on Trees

        7.2.1 Converting Values to Ordered Values

        7.2.2 Using Binary Trees

        7.2.3 A Fine Balance: Tree Surgery

          7.2.3.1 Left-Left Case

          7.2.3.2 Left-Right Case

          7.2.3.3 Any Other Cases?

    8 Halloween Analysis

      8.1 A First Example

      8.2 The New Form of Analysis

      8.3 An Example: Queues from Lists

        8.3.1 List Representations

        8.3.2 A First Analysis

        8.3.3 More Liberal Sequences of Operations

        8.3.4 A Second Analysis

        8.3.5 Amortization Versus Individual Operations

      8.4 Reading More

    9 Sharing and Equality

      9.1 The Dawn of a New Equality

      9.2 The Cost of Evaluating References

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

      9.4 Constructing Data Values With Sharing

      9.5 Cyclic Data

      9.6 Cyclic Lists Versus Streams

    10 Graphs

      10.1 Representations

        10.1.1 Direct Links

        10.1.2 Links by Name

        10.1.3 Links by Indices

        10.1.4 A List of Edges

      10.2 Measuring Complexity for Graphs

      10.3 Reachability

        10.3.1 Simple Recursion

        10.3.2 Cleaning up the Loop

        10.3.3 Traversal with Memory

        10.3.4 A Better Interface

      10.4 Depth- and Breadth-First Traversals

      10.5 Graphs With Weighted Edges

      10.6 Shortest (or Lightest) Paths

      10.7 Moravian Spanning Trees

        10.7.1 The Problem

        10.7.2 A Greedy Solution

        10.7.3 Another Greedy Solution

        10.7.4 A Third Solution

        10.7.5 Checking Component Connectedness

    11 State and Change

      11.1 A Canonical Mutable Structure

      11.2 Implementing Disjoint Sets with Mutation

        11.2.1 Optimizations

        11.2.2 Analysis

      11.3 What it Means to be Identical

      11.4 From Identifiers to Variables

      11.5 Interaction of Mutation with Closures: Counters

        11.5.1 Implementation Using Boxes

        11.5.2 Implementation Using Variables

      11.6 Set Membership Again

        11.6.1 Improving Access Time

        11.6.2 Better Hashing

        11.6.3 Bloom Filters

      11.7 Avoiding Recomputation by Remembering Answers

        11.7.1 An Interesting Numeric Sequence

          11.7.1.1 Using State to Remember Past Answers

          11.7.1.2 From a Tree of Computation to a DAG

          11.7.1.3 The Complexity of Numbers

          11.7.1.4 Abstracting Memoization

        11.7.2 Edit-Distance for Spelling Correction

        11.7.3 Nature as a Fat-Fingered Typist

        11.7.4 Dynamic Programming

          11.7.4.1 Catalan Numbers with Dynamic Programming

          11.7.4.2 Levenshtein Distance and Dynamic Programming

        11.7.5 Contrasting Memoization and Dynamic Programming

      11.8 The Perils of Mutation [EMPTY]

    12 Shrinking the Language [EMPTY]

    13 Everything (We Will Say) About Parsing

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

      13.2 Completing the Parser

      13.3 Coda

    14 A First Look at Interpretation

      14.1 Representing Arithmetic

      14.2 Writing an Interpreter

      14.3 Did You Notice?

      14.4 Enlarging the Language Without Growing It

        14.4.1 Extension: Binary Subtraction

        14.4.2 Extension: Unary Negation

    15 Evaluating 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 An Answer Type

        15.3.6 Sugaring Over Anonymity

      15.4 Functions and Predictability

    16 Mutation: Structures and Variables

      16.1 Separating Meaning from Notation

      16.2 Mutable Structures

        16.2.1 Extending the Language Representation

        16.2.2 The Interpretation of Boxes

        16.2.3 Can the Environment Help?

        16.2.4 Welcome to the Store

        16.2.5 Interpreting Boxes

        16.2.6 The Bigger Picture

      16.3 Variables

        16.3.1 The Syntax of Variable Assignment

        16.3.2 Interpreting Variables

        16.3.3 Reference Parameter Passing

      16.4 The Design of Stateful Language Operations

    17 Recursion and Cycles

      17.1 Recursive and Cyclic Data

      17.2 Recursive Functions

      17.3 Syntactic Sugar for Recursive Function Definitions

      17.4 Premature Observation

      17.5 Recursion Without Explicit State

    18 Objects

      18.1 Interpreting Objects

      18.2 Objects by Desugaring

        18.2.1 Objects as Named Collections

        18.2.2 Constructors

        18.2.3 State

        18.2.4 Private Members

        18.2.5 Static Members

        18.2.6 Objects with Self-Reference

          18.2.6.1 Self-Reference Using Mutation

          18.2.6.2 Self-Reference Without Mutation

        18.2.7 Dynamic Dispatch

      18.3 Member Access Design Space

      18.4 What (Goes In) Else?

        18.4.1 Classes

        18.4.2 Prototypes

        18.4.3 Multiple Inheritance

        18.4.4 Super-Duper!

        18.4.5 Mixins and Traits

    19 Control Operations

      19.1 Control on the Web

        19.1.1 Program Decomposition into Now and Later

        19.1.2 A Partial Solution

        19.1.3 Achieving Statelessness

        19.1.4 Interaction with State

      19.2 Continuation-Passing Style

        19.2.1 Implementation by Desugaring

        19.2.2 Implementation in the Core

      19.3 Generators

      19.4 Continuations and Stacks

      19.5 Tail Calls

    20 Checking Program Invariants Statically: Types

      20.1 Types as a Static Discipline

      20.2 A Classical View of Types

        20.2.1 A Simple Type Checker

        20.2.2 Type-Checking Conditionals

        20.2.3 Recursion in Code

          20.2.3.1 A First Attempt at Typing Recursion

          20.2.3.2 Program Termination

          20.2.3.3 Typing Recursion

        20.2.4 Recursion in Data

          20.2.4.1 Recursive Datatype Definitions

          20.2.4.2 Introduced Types

          20.2.4.3 Selectors

          20.2.4.4 Pattern-Matching and Desugaring

        20.2.5 Types, Time, and Space

        20.2.6 Types and Mutation

      20.3 The Central Theorem: Type Soundness

      20.4 Union Types

        20.4.1 Structures as Types

        20.4.2 Untagged Unions

        20.4.3 Discriminating Untagged Unions

        20.4.4 Retrofitting Types

        20.4.5 Design Choices

      20.5 Nominal Versus Structural Systems

      20.6 Intersection Types

      20.7 Recursive Types

      20.8 Subtyping

        20.8.1 Subtyping Unions

        20.8.2 Subtyping Intersections

        20.8.3 Subtyping Functions

        20.8.4 Implementing Subtyping

      20.9 Object Types

      20.10 Explicit Parametric Polymorphism

        20.10.1 Parameterized Types

        20.10.2 Making Parameters Explicit

        20.10.3 Rank-1 Polymorphism

        20.10.4 Interpreting Rank-1 Polymorphism as Desugaring

        20.10.5 Alternate Implementations

        20.10.6 Relational Parametricity

    21 Dynamic Reliability: Contracts [EMPTY]

    22 Alternate Application Semantics [EMPTY]

    23 Automated Memory Management

      23.1 Garbage

      23.2 What is “Correct” Garbage Recovery?

      23.3 Manual Reclamation

        23.3.1 The Cost of Fully-Manual Reclamation

        23.3.2 Reference Counting

      23.4 Automated Reclamation, or Garbage Collection

        23.4.1 Overview

        23.4.2 Truth and Provability

        23.4.3 Central Assumptions

      23.5 Convervative Garbage Collection

      23.6 Precise Garbage Collection

    24 Representation Decisions

      24.1 Changing Representations

      24.2 Errors

      24.3 Changing Meaning

      24.4 Representing the Environment

    25 Desugaring as a Language Feature [EMPTY]

    26 Glossary