1 Introduction

      1.1 Our Philosophy

      1.2 The Structure of This Book

      1.3 The Language of This Book

    2 Everything (We Will Say) About Parsing

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

      2.2 A Convenient Shortcut

      2.3 Types for Parsing

      2.4 Completing the Parser

      2.5 Coda

    3 A First Look at Interpretation

      3.1 Representing Arithmetic

      3.2 Writing an Interpreter

      3.3 Did You Notice?

      3.4 Growing the Language

    4 A First Taste of Desugaring

      4.1 Extension: Binary Subtraction

      4.2 Extension: Unary Negation

    5 Adding Functions to the Language

      5.1 Defining Data Representations

      5.2 Growing the Interpreter

      5.3 Substitution

      5.4 The Interpreter, Resumed

      5.5 Oh Wait, There’s More!

    6 From Substitution to Environments

      6.1 Introducing the Environment

      6.2 Interpreting with Environments

      6.3 Deferring Correctly

      6.4 Scope

        6.4.1 How Bad Is It?

        6.4.2 The Top-Level Scope

      6.5 Exposing the Environment

    7 Functions Anywhere

      7.1 Functions as Expressions and Values

      7.2 Nested What?

      7.3 Implementing Closures

      7.4 Substitution, Again

      7.5 Sugaring Over Anonymity

    8 Mutation: Structures and Variables

      8.1 Mutable Structures

        8.1.1 A Simple Model of Mutable Structures

        8.1.2 Scaffolding

        8.1.3 Interaction with Closures

        8.1.4 Understanding the Interpretation of Boxes

        8.1.5 Can the Environment Help?

        8.1.6 Introducing the Store

        8.1.7 Interpreting Boxes

        8.1.8 The Bigger Picture

      8.2 Variables

        8.2.1 Terminology

        8.2.2 Syntax

        8.2.3 Interpreting Variables

      8.3 The Design of Stateful Language Operations

      8.4 Parameter Passing

    9 Recursion and Cycles: Procedures and Data

      9.1 Recursive and Cyclic Data

      9.2 Recursive Functions

      9.3 Premature Observation

      9.4 Without Explicit State

    10 Objects

      10.1 Objects Without Inheritance

        10.1.1 Objects in the Core

        10.1.2 Objects by Desugaring

        10.1.3 Objects as Named Collections

        10.1.4 Constructors

        10.1.5 State

        10.1.6 Private Members

        10.1.7 Static Members

        10.1.8 Objects with Self-Reference

          10.1.8.1 Self-Reference Using Mutation

          10.1.8.2 Self-Reference Without Mutation

        10.1.9 Dynamic Dispatch

      10.2 Member Access Design Space

      10.3 What (Goes In) Else?

        10.3.1 Classes

        10.3.2 Prototypes

        10.3.3 Multiple Inheritance

        10.3.4 Super-Duper!

        10.3.5 Mixins and Traits

    11 Memory Management

      11.1 Garbage

      11.2 What is “Correct” Garbage Recovery?

      11.3 Manual Reclamation

        11.3.1 The Cost of Fully-Manual Reclamation

        11.3.2 Reference Counting

      11.4 Automated Reclamation, or Garbage Collection

        11.4.1 Overview

        11.4.2 Truth and Provability

        11.4.3 Central Assumptions

      11.5 Convervative Garbage Collection

      11.6 Precise Garbage Collection

    12 Representation Decisions

      12.1 Changing Representations

      12.2 Errors

      12.3 Changing Meaning

      12.4 One More Example

    13 Desugaring as a Language Feature

      13.1 A First Example

      13.2 Syntax Transformers as Functions

      13.3 Guards

      13.4 Or: A Simple Macro with Many Features

        13.4.1 A First Attempt

        13.4.2 Guarding Evaluation

        13.4.3 Hygiene

      13.5 Identifier Capture

      13.6 Influence on Compiler Design

      13.7 Desugaring in Other Languages

    14 Control Operations

      14.1 Control on the Web

        14.1.1 Program Decomposition into Now and Later

        14.1.2 A Partial Solution

        14.1.3 Achieving Statelessness

        14.1.4 Interaction with State

      14.2 Continuation-Passing Style

        14.2.1 Implementation by Desugaring

        14.2.2 Converting the Example

        14.2.3 Implementation in the Core

      14.3 Generators

        14.3.1 Design Variations

        14.3.2 Implementing Generators

      14.4 Continuations and Stacks

      14.5 Tail Calls

      14.6 Continuations as a Language Feature

        14.6.1 Presentation in the Language

        14.6.2 Defining Generators

        14.6.3 Defining Threads

        14.6.4 Better Primitives for Web Programming

    15 Checking Program Invariants Statically: Types

      15.1 Types as Static Disciplines

      15.2 A Classical View of Types

        15.2.1 A Simple Type Checker

        15.2.2 Type-Checking Conditionals

        15.2.3 Recursion in Code

          15.2.3.1 A First Attempt at Typing Recursion

          15.2.3.2 Program Termination

          15.2.3.3 Typing Recursion

        15.2.4 Recursion in Data

          15.2.4.1 Recursive Datatype Definitions

          15.2.4.2 Introduced Types

          15.2.4.3 Pattern-Matching and Desugaring

        15.2.5 Types, Time, and Space

        15.2.6 Types and Mutation

        15.2.7 The Central Theorem: Type Soundness

      15.3 Extensions to the Core

        15.3.1 Explicit Parametric Polymorphism

          15.3.1.1 Parameterized Types

          15.3.1.2 Making Parameters Explicit

          15.3.1.3 Rank-1 Polymorphism

          15.3.1.4 Interpreting Rank-1 Polymorphism as Desugaring

          15.3.1.5 Alternate Implementations

          15.3.1.6 Relational Parametricity

        15.3.2 Type Inference

          15.3.2.1 Constraint Generation

          15.3.2.2 Constraint Solving Using Unification

          15.3.2.3 Let-Polymorphism

        15.3.3 Union Types

          15.3.3.1 Structures as Types

          15.3.3.2 Untagged Unions

          15.3.3.3 Discriminating Untagged Unions

          15.3.3.4 Retrofitting Types

          15.3.3.5 Design Choices

        15.3.4 Nominal Versus Structural Systems

        15.3.5 Intersection Types

        15.3.6 Recursive Types

        15.3.7 Subtyping

          15.3.7.1 Unions

          15.3.7.2 Intersections

          15.3.7.3 Functions

          15.3.7.4 Implementing Subtyping

        15.3.8 Object Types

    16 Checking Program Invariants Dynamically: Contracts

      16.1 Contracts as Predicates

      16.2 Tags, Types, and Observations on Values

      16.3 Higher-Order Contracts

      16.4 Syntactic Convenience

      16.5 Extending to Compound Data Structures

      16.6 More on Contracts and Observations

      16.7 Contracts and Mutation

      16.8 Combining Contracts

      16.9 Blame

    17 Alternate Application Semantics

      17.1 Lazy Application

        17.1.1 A Lazy Application Example

        17.1.2 What Are Values?

        17.1.3 What Causes Evaluation?

        17.1.4 An Interpreter

        17.1.5 Laziness and Mutation

        17.1.6 Caching Computation

      17.2 Reactive Application

        17.2.1 Motivating Example: A Timer

        17.2.2 Callback Types are Four-Letter Words

        17.2.3 The Alternative: Reactive Languages

        17.2.4 Implementing Transparent Reactivity

          17.2.4.1 Dataflow Graph Construction

          17.2.4.2 Dataflow Graph Update

          17.2.4.3 Evaluation Order