On this page:
Programming and Programming Languages
Monday, November 30th, 2015 9:51:16am

Programming and Programming Languages

Shriram Krishnamurthi and Joe Gibbs Politz

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 2016 edition.

    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 Programming in Pyret

      2.1 Values

      2.2 Expressions

      2.3 Recipe for Primitive Values

        2.3.1 Abstracting Common Parts

      2.4 Evaluating by Reducing Expressions

      2.5 Recipe for Simple Data

        2.5.1 Functions Over Mixed, Related Data

        2.5.2 More Refined Comparisons

      2.6 Recipe for Recursive Data

      2.7 Parameterizing Data Definitions

        2.7.1 List and the list Abbreviation

      2.8 Abstracting Common Parts of List Functions

      2.9 Functions that Return Functions

      2.10 More and Mutually Recursive Data

        2.10.1 Other Recursive Patterns

        2.10.2 Mutually Recursive Data

        2.10.3 A Note on Parametric Data Definitions

      2.11 Naming Intermediate Values

      2.12 More to Learn

    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 Testing, Examples, and Program Checking

      4.1 From Examples to Tests

      4.2 Oracles for Testing

      4.3 Testing Erroneous Programs

    5 Functions as Data

      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 [EMPTY]

    9 Halloween Analysis

      9.1 A First Example

      9.2 The New Form of Analysis

      9.3 An Example: Queues from Lists

        9.3.1 List Representations

        9.3.2 A First Analysis

        9.3.3 More Liberal Sequences of Operations

        9.3.4 A Second Analysis

        9.3.5 Amortization Versus Individual Operations

      9.4 Reading More

    10 Sharing and Equality

      10.1 Re-Examining Equality

      10.2 The Cost of Evaluating References

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

      10.4 From Acyclicity to Cycles

    11 Graphs

      11.1 Understanding Graphs

      11.2 Representations

        11.2.1 Links by Name

        11.2.2 Links by Indices

        11.2.3 A List of Edges

        11.2.4 Abstracting Representations

      11.3 Measuring Complexity for Graphs

      11.4 Reachability

        11.4.1 Simple Recursion

        11.4.2 Cleaning up the Loop

        11.4.3 Traversal with Memory

        11.4.4 A Better Interface

      11.5 Depth- and Breadth-First Traversals

      11.6 Graphs With Weighted Edges

      11.7 Shortest (or Lightest) Paths

      11.8 Moravian Spanning Trees

        11.8.1 The Problem

        11.8.2 A Greedy Solution

        11.8.3 Another Greedy Solution

        11.8.4 A Third Solution

        11.8.5 Checking Component Connectedness

    12 State, Change, and More Equality

      12.1 A Canonical Mutable Structure

      12.2 What it Means to be Identical

      12.3 Recursion and Cycles from Mutation

        12.3.1 Partial Definitions

        12.3.2 Recursive Functions

        12.3.3 Premature Evaluation

        12.3.4 Cyclic Lists Versus Streams

      12.4 From Identifiers to Variables

      12.5 Interaction of Mutation with Closures: Counters

        12.5.1 Implementation Using Boxes

        12.5.2 Implementation Using Variables

      12.6 A Family of Equality Predicates

        12.6.1 A Hierarchy of Equality

        12.6.2 Space and Time Complexity

        12.6.3 Comparing Functions

    13 Algorithms That Exploit State

      13.1 Disjoint Sets Redux

        13.1.1 Optimizations

        13.1.2 Analysis

      13.2 Set Membership by Hashing Redux

        13.2.1 Improving Access Time

        13.2.2 Better Hashing

        13.2.3 Bloom Filters

      13.3 Avoiding Recomputation by Remembering Answers

        13.3.1 An Interesting Numeric Sequence

          13.3.1.1 Using State to Remember Past Answers

          13.3.1.2 From a Tree of Computation to a DAG

          13.3.1.3 The Complexity of Numbers

          13.3.1.4 Abstracting Memoization

        13.3.2 Edit-Distance for Spelling Correction

        13.3.3 Nature as a Fat-Fingered Typist

        13.3.4 Dynamic Programming

          13.3.4.1 Catalan Numbers with Dynamic Programming

          13.3.4.2 Levenshtein Distance and Dynamic Programming

        13.3.5 Contrasting Memoization and Dynamic Programming

    14 [EMPTY]

    15 Processing Programs: Parsing

      15.1 Understanding Languages by Writing Programs About Them

      15.2 Everything (We Will Say) About Parsing

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

        15.2.2 Completing the Parser

        15.2.3 Coda

    16 Processing Programs: A First Look at Interpretation

      16.1 Representing Arithmetic

      16.2 Writing an Interpreter

      16.3 A First Taste of “Semantics”

      16.4 Desugaring: Growing the Language Without Enlarging It

        16.4.1 Extension: Binary Subtraction

        16.4.2 Extension: Unary Negation

      16.5 A Three-Stage Pipeline

    17 Interpreting Conditionals

      17.1 The Design Space of Conditionals

      17.2 The Game Plan for Conditionals

        17.2.1 The Interpreter’s Type

        17.2.2 Updating Arithmetic

        17.2.3 Defensive Programming

        17.2.4 Interpreting Conditionals

      17.3 Growing the Conditional Language

    18 Interpreting Functions

      18.1 Adding Functions to the Language

        18.1.1 Defining Data Representations

        18.1.2 Growing the Interpreter

        18.1.3 Substitution

        18.1.4 The Interpreter, Resumed

        18.1.5 Oh Wait, There’s More!

      18.2 From Substitution to Environments

        18.2.1 Introducing the Environment

        18.2.2 Interpreting with Environments

        18.2.3 Deferring Correctly

        18.2.4 Scope

        18.2.5 How Bad Is It?

        18.2.6 The Top-Level Scope

        18.2.7 Exposing the Environment

      18.3 Functions Anywhere

        18.3.1 Functions as Expressions and Values

        18.3.2 A Small Improvement

        18.3.3 Nesting Functions

        18.3.4 Nested Functions and Substitution

        18.3.5 Updating Values

        18.3.6 Sugaring Over Anonymity

      18.4 Recursion and Non-Termination

      18.5 Functions and Predictability

    19 Reasoning about Programs: A First Look at Types

      19.1 Types as a Static Discipline

      19.2 The Principle of Substitutability

      19.3 A Type(d) Language and Type Errors

        19.3.1 Assume-Guarantee Reasoning

      19.4 A Type Checker for Expressions and Functions

        19.4.1 A Pure Checker

        19.4.2 A Calculator and Checker

        19.4.3 Type-Checking Versus Interpretation

      19.5 Type-Checking, Testing, and Coverage

      19.6 Recursion in Code

        19.6.1 A First Attempt at Typing Recursion

        19.6.2 Program Termination

        19.6.3 Typing Recursion

      19.7 Recursion in Data

        19.7.1 Recursive Datatype Definitions

        19.7.2 Introduced Types

        19.7.3 Selectors

        19.7.4 Pattern-Matching and Desugaring

    20 Safety and Soundness

      20.1 Safety

      20.2 “Untyped” Languages

      20.3 The Central Theorem: Type Soundness

      20.4 Types, Time, and Space

      20.5 Types Versus Safety

    21 Parametric Polymorphism

      21.1 Parameterized Types

      21.2 Making Parameters Explicit

      21.3 Rank-1 Polymorphism

      21.4 Interpreting Rank-1 Polymorphism as Desugaring

      21.5 Alternate Implementations

      21.6 Relational Parametricity

    22 Type Inference

      22.1 Type Inference as Type Annotation Insertion

      22.2 Understanding Inference

        22.2.1 Constraint Generation

        22.2.2 Constraint Solving Using Unification

      22.3 Type Checking and Type Errors

      22.4 Over- and Under-Constrained Solutions

      22.5 Let-Polymorphism

    23 Mutation: Structures and Variables

      23.1 Separating Meaning from Notation

      23.2 Mutation and Closures

      23.3 Mutable Structures

        23.3.1 Extending the Language Representation

        23.3.2 The Interpretation of Boxes

        23.3.3 Can the Environment Help?

        23.3.4 Welcome to the Store

        23.3.5 Interpreting Boxes

        23.3.6 Implementing Mutation: Subtleties and Variations

      23.4 Variables

        23.4.1 The Syntax of Variable Assignment

        23.4.2 Interpreting Variables

        23.4.3 Reference Parameter Passing

      23.5 The Design of Stateful Language Operations

      23.6 Typing State

        23.6.1 Mutation and Polymorphism

        23.6.2 Typing the Initial Value

    24 Objects: Interpretation and Types

      24.1 Interpreting Objects

      24.2 Objects by Desugaring

        24.2.1 Objects as Named Collections

        24.2.2 Constructors

        24.2.3 State

        24.2.4 Private Members

        24.2.5 Static Members

        24.2.6 Objects with Self-Reference

          24.2.6.1 Self-Reference Using Mutation

          24.2.6.2 Self-Reference Without Mutation

        24.2.7 Dynamic Dispatch

      24.3 Member Access Design Space

      24.4 What (Goes In) Else?

        24.4.1 Classes

        24.4.2 Prototypes

        24.4.3 Multiple Inheritance

        24.4.4 Super-Duper!

        24.4.5 Mixins and Traits

      24.5 Object Classification and Object Equality

      24.6 Types for Objects

        24.6.1 Subtyping

          24.6.1.1 Subtyping Functions

          24.6.1.2 Subtyping and Information Hiding

          24.6.1.3 Implementing Subtyping

        24.6.2 Types for Self-Reference

        24.6.3 Nominal Types

    25 Control Operations

      25.1 Control on the Web

        25.1.1 Program Decomposition into Now and Later

        25.1.2 A Partial Solution

        25.1.3 Achieving Statelessness

        25.1.4 Interaction with State

      25.2 Conversion to Continuation-Passing Style

        25.2.1 Implementation by Desugaring

        25.2.2 Understanding the Output

        25.2.3 An Interaction Primitive by Transformation

      25.3 Implementation in the Core

        25.3.1 Converting the Interpreter

        25.3.2 An Interaction Primitive in the Core

      25.4 Generators

      25.5 Continuations and Stacks

      25.6 Tail Calls

    26 Glossary