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 .. Extension: Unary Negation ..185 Adding Functions to the Defining Data Representations .. Growing the Interpreter .. Substitution .. The Interpreter, Resumed.

2 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 .. 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.

3 Terminology .. Syntax .. Interpreting Variables .. The Design of Stateful Language Operations .. Parameter Passing ..609 Recursion and Cycles: Procedures and Recursive and Cyclic Data .. 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?

4 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 .. 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.

5 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 .. 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.

6 Recursion in Data .. Types, Time, and Space .. Types and Mutation .. The Central Theorem: Type Soundness .. 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 .. Combining Contracts .. Blame .. 18917 Alternate Application Lazy Application .

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

8 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. However, this non-linear path ismore frustrating in the short term (you will often be tempted to say, Just tell me theanswer, already! ), and it makes the book a poor reference guide (you can t open up toa random page and be sure what it says is correct). However, that feeling of frustrationis the sensation of learning. I don t know of a way around various points you will encounter this:ExerciseThis is an exercise. Do try is a traditional textbook exercise. It s something you need to do on your you re using this book as part of a course, this may very well have been assigned ashomework.

9 In contrast, you will also find exercise-like questions that look like this:Do Now!There s an activity here! Do you see it?When you get to one of these,stop. Read, think, and formulate an answer beforeyou proceed. You must do this because this is actually anexercise, but the answeris already in the book most often in the text immediately following ( , in the partyou re reading right now) or is something you can determine for yourself by runninga program. If you just read on, you ll see the answer without having thought about it(or not see it at all, if the instructions are to run a program), so you will get to neither(a) test your knowledge, nor (b) improve your intuitions. In other words, these areadditional, explicit attempts to encourage active learning. Ultimately, however, I canonly encourage it; it s up to you to practice The Language of This BookThe main Programming language used in this book is Racket.

10 Like with all operatingsystems, however, Racket actually supports a host of Programming languages, so you7must tell Racketwhichlanguage you re Programming in. You inform the Unix shell bywriting a line like#!/bin/shat the top of a script; you inform the browser by writing, say,<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML " ..>Similarly, Racket asks that you declare which language you will be using. Racket lan-guages can have the same parenthetical syntax as Racket but with a different semantics;the same semantics but a different syntax; or different syntax and semantics. Thus ev-ery Racket program begins with#langfollowed by the name of some language: bydefault, it s Racket (written asracket). In this book we ll almost always use theIn DrRacket v. ,go to Language,then ChooseLanguage, andselect Use thelanguage declaredin the source.