Programming Languages: Application and Interpretation

1 Programming Languages: Application andInterpretationVersion Second EditionShriram KrishnamurthiApril 14, 20171 Contents1 Our Philosophy .. The Structure of This Book .. The Language of This Book ..72 Everything (We Will Say) About A Lightweight, Built-In First Half of a Parser .. A Convenient Shortcut .. Types for Parsing .. Completing the Parser .. Coda ..133 A First Look at Representing Arithmetic .. Writing an Interpreter .. Did You Notice? .. Growing the Language ..164 A First Taste of Extension: Binary Subtraction.

2 Extension: Unary Negation ..185 Adding Functions to the Defining Data Representations .. Growing the Interpreter .. Substitution .. The Interpreter, Resumed .. Oh Wait, There s More! ..256 From Substitution to Introducing the Environment .. Interpreting with Environments .. Deferring Correctly .. Scope .. How Bad Is It? .. The Top-Level Scope .. Exposing the Environment ..317 Functions Functions as Expressions and Values .. Nested What? .. Implementing Closures.

3 Substitution, Again .. Sugaring Over Anonymity ..3928 Mutation: Structures and Mutable Structures .. A Simple Model of Mutable Structures .. Scaffolding .. Interaction with Closures .. Understanding the Interpretation of Boxes .. Can the Environment Help? .. Introducing the Store .. Interpreting Boxes .. The Bigger Picture .. Variables .. Terminology .. Syntax .. Interpreting Variables .. The Design of Stateful Language Operations .. Parameter Passing ..609 Recursion and Cycles: Procedures and Recursive and Cyclic Data.

4 Recursive Functions .. Premature Observation .. Without Explicit State ..6610 Objects Without Inheritance .. Objects in the Core .. Objects by Desugaring .. Objects as Named Collections .. Constructors .. State .. Private Members .. Static Members .. Objects with Self-Reference .. Dynamic Dispatch .. Member Access Design Space .. What (Goes In) Else? .. Classes .. Prototypes .. Multiple Inheritance .. Super-Duper! .. Mixins and Traits ..7911 Memory Garbage .. What is Correct Garbage Recovery?

5 Manual Reclamation .. The Cost of Fully-Manual Reclamation .. Reference Counting .. Automated Reclamation, or Garbage Collection .. Overview .. Truth and Provability .. Central Assumptions .. Convervative Garbage Collection .. Precise Garbage Collection ..8712 Representation Changing Representations .. Errors .. Changing Meaning .. One More Example ..9013 Desugaring as a Language A First Example .. Syntax Transformers as Functions .. Guards .. Or: A Simple Macro with Many Features .. A First Attempt.

6 Guarding Evaluation .. Hygiene .. Identifier Capture .. Influence on Compiler Design .. Desugaring in Other Languages .. 10114 Control Control on the Web .. Program Decomposition into Now and Later .. A Partial Solution .. Achieving Statelessness .. Interaction with State .. Continuation-Passing Style .. Implementation by Desugaring .. Converting the Example .. Implementation in the Core .. Generators .. Design Variations .. Implementing Generators .. Continuations and Stacks.

7 Tail Calls .. Continuations as a Language Feature .. Presentation in the Language .. Defining Generators .. Defining Threads .. Better Primitives for Web Programming .. 13015 Checking Program Invariants Statically: Types as Static Disciplines .. A Classical View of Types .. A Simple Type Checker .. Type-Checking Conditionals .. Recursion in Code .. Recursion in Data .. Types, Time, and Space .. Types and Mutation .. The Central Theorem: Type Soundness.

8 Extensions to the Core .. Explicit Parametric Polymorphism .. Type Inference .. Union Types .. Nominal Versus Structural Systems .. Intersection Types .. Recursive Types .. Subtyping .. Object Types .. 17516 Checking Program Invariants Dynamically: Contracts as Predicates .. Tags, Types, and Observations on Values .. Higher-Order Contracts .. Syntactic Convenience .. Extending to Compound Data Structures .. More on Contracts and Observations .. Contracts and Mutation.

9 Combining Contracts .. Blame .. 18917 Alternate Application Lazy Application .. A Lazy Application Example .. What Are Values? .. What Causes Evaluation? .. An Interpreter .. Laziness and Mutation .. Caching Computation .. Reactive Application .. Motivating Example: A Timer .. Callback Types are Four-Letter Words .. The Alternative: Reactive Languages .. Implementing Transparent Reactivity .. Backtracking Application .. Searching for Satisfaction.

10 20561 Our PhilosophyPlease watch the video on YouTube. Someday there will be a textual description The Structure of This BookUnlike some other textbooks, this one does not follow a top-down narrative. Ratherit has the flow of a conversation, with backtracking. We will often build up programsincrementally, just as a pair of programmers would. We will include mistakes, notbecause I don t know the answer, but becausethis is the best way for you to mistakes makes it impossible for you to read passively: you must insteadengage with the material, because you can never be sure of the veracity of what you the end, you ll always get to the right answer.