Programming Languages: Application and Interpretation

1 Programming Languages: Application and Interpretation Version Second Edition Shriram Krishnamurthi April 14, 2017. 1. Contents 1 Introduction 7. Our Philosophy .. 7. The Structure of This Book .. 7. The language of This Book .. 7. 2 Everything (We Will Say) About Parsing 10. A Lightweight, Built-In First Half of a Parser .. 10. A Convenient Shortcut .. 10. Types for Parsing .. 11. Completing the Parser .. 12. Coda .. 13. 3 A First Look at Interpretation 13. Representing Arithmetic .. 14. Writing an Interpreter .. 14. Did You Notice? .. 15. Growing the language .. 16. 4 A First Taste of Desugaring 16. Extension: Binary Subtraction .. 17. Extension: Unary Negation .. 18. 5 Adding Functions to the language 19. Defining Data Representations .. 19. Growing the Interpreter .. 21. Substitution .. 22. The Interpreter, Resumed .. 23. Oh Wait, There's More! .. 25. 6 From Substitution to Environments 25.

2 Introducing the Environment .. 26. Interpreting with Environments .. 27. Deferring Correctly .. 29. Scope .. 30. How Bad Is It? .. 30. The Top-Level Scope .. 31. Exposing the Environment .. 31. 7 Functions Anywhere 31. Functions as Expressions and Values .. 32. Nested What? .. 35. Implementing Closures .. 37. Substitution, Again .. 38. Sugaring Over Anonymity .. 39. 2. 8 Mutation: Structures and Variables 41. Mutable Structures .. 41. A Simple Model of Mutable Structures .. 41. Scaffolding .. 42. Interaction with Closures .. 43. Understanding the Interpretation of Boxes .. 44. Can the Environment Help? .. 46. Introducing the Store .. 48. Interpreting Boxes .. 49. The Bigger Picture .. 54. Variables .. 57. Terminology .. 57. Syntax .. 57. Interpreting Variables .. 58. The Design of Stateful language Operations .. 59. Parameter Passing .. 60. 9 Recursion and Cycles: Procedures and Data 62.

3 Recursive and Cyclic Data .. 62. Recursive Functions .. 64. Premature Observation .. 65. Without Explicit State .. 66. 10 Objects 67. Objects Without Inheritance .. 67. Objects in the Core .. 68. Objects by Desugaring .. 69. Objects as Named Collections .. 69. Constructors .. 70. State .. 71. Private Members .. 71. Static Members .. 72. Objects with Self-Reference .. 72. Dynamic Dispatch .. 73. Member Access Design Space .. 75. What (Goes In) Else? .. 75. Classes .. 76. Prototypes .. 78. Multiple Inheritance .. 78. Super-Duper! .. 79. Mixins and Traits .. 79. 11 Memory Management 81. Garbage .. 81. What is Correct Garbage Recovery? .. 81. 3. Manual Reclamation .. 82. The Cost of Fully-Manual Reclamation .. 82. Reference Counting .. 83. Automated Reclamation, or Garbage Collection .. 84. Overview .. 84. Truth and Provability .. 84. Central Assumptions .. 85. Convervative Garbage Collection.

4 86. Precise Garbage Collection .. 87. 12 Representation Decisions 87. Changing Representations .. 87. Errors .. 89. Changing Meaning .. 89. One More Example .. 90. 13 Desugaring as a language Feature 90. A First Example .. 91. Syntax Transformers as Functions .. 92. Guards .. 94. Or: A Simple Macro with Many Features .. 95. A First Attempt .. 95. Guarding Evaluation .. 97. Hygiene .. 98. Identifier Capture .. 99. Influence on Compiler Design .. 101. Desugaring in Other Languages .. 101. 14 Control Operations 102. Control on the Web .. 102. Program Decomposition into Now and Later .. 103. A Partial Solution .. 104. Achieving Statelessness .. 106. Interaction with State .. 107. Continuation-Passing Style .. 109. Implementation by Desugaring .. 109. Converting the Example .. 114. Implementation in the Core .. 115. Generators .. 117. Design Variations .. 117. Implementing Generators.

5 118. Continuations and Stacks .. 120. Tail Calls .. 122. Continuations as a language Feature .. 123. Presentation in the language .. 125. Defining Generators .. 125. 4. Defining Threads .. 127. Better Primitives for Web Programming .. 130. 15 Checking Program Invariants Statically: Types 130. Types as Static Disciplines .. 132. A Classical View of Types .. 133. A Simple Type Checker .. 133. Type-Checking Conditionals .. 138. Recursion in Code .. 138. Recursion in Data .. 141. Types, Time, and Space .. 143. Types and Mutation .. 145. The Central Theorem: Type Soundness .. 145. Extensions to the Core .. 147. Explicit Parametric Polymorphism .. 147. Type Inference .. 153. Union Types .. 163. Nominal Versus Structural Systems .. 168. Intersection Types .. 169. Recursive Types .. 170. Subtyping .. 171. Object Types .. 175. 16 Checking Program Invariants Dynamically: Contracts 177.

6 Contracts as Predicates .. 179. Tags, Types, and Observations on Values .. 180. Higher-Order Contracts .. 181. Syntactic Convenience .. 185. Extending to Compound Data Structures .. 186. More on Contracts and Observations .. 187. Contracts and Mutation .. 187. Combining Contracts .. 188. Blame .. 189. 17 Alternate Application Semantics 193. Lazy Application .. 194. A Lazy Application Example .. 194. What Are Values? .. 195. What Causes Evaluation? .. 196. An Interpreter .. 197. Laziness and Mutation .. 199. Caching Computation .. 199. Reactive Application .. 199. Motivating Example: A Timer .. 200. Callback Types are Four-Letter Words .. 201. The Alternative: Reactive Languages .. 202. 5. Implementing Transparent Reactivity .. 203. Backtracking Application .. 205. Searching for Satisfaction .. 205. 6. 1 Introduction Our Philosophy Please watch the video on YouTube.

7 Someday there will be a textual description here instead. The Structure of This Book Unlike some other textbooks, this one does not follow a top-down narrative. Rather it has the flow of a conversation, with backtracking. We will often build up programs incrementally, just as a pair of programmers would. We will include mistakes, not because I don't know the answer, but because this is the best way for you to learn. Including mistakes makes it impossible for you to read passively: you must instead engage with the material, because you can never be sure of the veracity of what you're reading. At the end, you'll always get to the right answer. However, this non-linear path is more frustrating in the short term (you will often be tempted to say, Just tell me the answer, already! ), and it makes the book a poor reference guide (you can't open up to a random page and be sure what it says is correct).

8 However, that feeling of frustration is the sensation of learning. I don't know of a way around it. At various points you will encounter this: Exercise This is an exercise. Do try it. This is a traditional textbook exercise. It's something you need to do on your own. If you're using this book as part of a course, this may very well have been assigned as homework. 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 before you proceed. You must do this because this is actually an exercise, but the answer is already in the book most often in the text immediately following ( , in the part you're reading right now) or is something you can determine for yourself by running a 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.

9 In other words, these are additional, explicit attempts to encourage active learning. Ultimately, however, I can only encourage it; it's up to you to practice it. The language of This Book The main Programming language used in this book is Racket. Like with all operating systems, however, Racket actually supports a host of Programming languages, so you 7. must tell Racket which language you're Programming in. You inform the Unix shell by writing a line like #!/bin/sh at 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 #lang followed by the name of some language : by default, it's Racket (written as racket).

10 In this book we'll almost always use the In DrRacket v. , language go to language , then Choose language , and plai-typed select Use the language declared . When we deviate we'll say so explicitly, so unless indicated otherwise, put in the source . #lang plai-typed at the top of every file (and assume I've done the same). The Typed PLAI language differs from traditional Racket most importantly by be- ing statically typed. It also gives you some useful new constructs: define-type, type-case, and test. Here's an example of each in use. We can introduce new There are additional datatypes: commands for controlling the output of testing, (define-type MisspelledAnimal for instance. Be [caml (humps : number)] sure to read the [yacc (height : number)]) documentation for the language In You can roughly think of this as analogous to the following in Java: an abstract class DrRacket v.