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.

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

3 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. Recursive and Cyclic Data .. 62. Recursive Functions .. 64. Premature Observation .. 65. Without Explicit State.

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

5 84. Overview .. 84. Truth and Provability .. 84. Central Assumptions .. 85. Convervative Garbage Collection .. 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.

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

7 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. Contracts as Predicates .. 179. Tags, Types, and Observations on Values.

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

9 203. Backtracking Application .. 205. Searching for Satisfaction .. 205. 6. 1 Introduction Our Philosophy Please watch the video on YouTube. 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.

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