Transcription
Programming Languages: Application andInterpretationVersion Second EditionShriram KrishnamurthiApril 14, 20171
Contents1Introduction1.1 Our Philosophy . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.2 The Structure of This Book . . . . . . . . . . . . . . . . . . . . . . .1.3 The Language of This Book . . . . . . . . . . . . . . . . . . . . . .2Everything (We Will Say) About Parsing2.1 A Lightweight, Built-In First Half of a Parser2.2 A Convenient Shortcut . . . . . . . . . . . .2.3 Types for Parsing . . . . . . . . . . . . . . .2.4 Completing the Parser . . . . . . . . . . . . .2.5 Coda . . . . . . . . . . . . . . . . . . . . . .101010111213A First Look at Interpretation3.1 Representing Arithmetic .3.2 Writing an Interpreter . . .3.3 Did You Notice? . . . . . .3.4 Growing the Language . .13141415164A First Taste of Desugaring4.1 Extension: Binary Subtraction . . . . . . . . . . . . . . . . . . . . .4.2 Extension: Unary Negation . . . . . . . . . . . . . . . . . . . . . . .1617185Adding Functions to the Language5.1 Defining Data Representations5.2 Growing the Interpreter . . . .5.3 Substitution . . . . . . . . . .5.4 The Interpreter, Resumed . . .5.5 Oh Wait, There’s More! . . . .367.7777.191921222325From Substitution to Environments6.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 . . .2526272930303131Functions Anywhere7.1 Functions as Expressions and Values7.2 Nested What? . . . . . . . . . . . .7.3 Implementing Closures . . . . . . .7.4 Substitution, Again . . . . . . . . .7.5 Sugaring Over Anonymity . . . . .3132353738392
89Mutation: Structures and Variables8.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 Boxes8.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 . . . . . . . . . . . . . . . . .41414142434446484954575757585960Recursion and Cycles: Procedures and Data9.1 Recursive and Cyclic Data . . . . . . . .9.2 Recursive Functions . . . . . . . . . . . .9.3 Premature Observation . . . . . . . . . .9.4 Without Explicit State . . . . . . . . . . .6262646566.67676869697071717272737575767878797911 Memory Management11.1 Garbage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11.2 What is “Correct” Garbage Recovery? . . . . . . . . . . . . . . . . .81818110 Objects10.1 Objects Without Inheritance . . . . .10.1.1 Objects in the Core . . . . . .10.1.2 Objects by Desugaring . . . .10.1.3 Objects as Named Collections10.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.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 . . . . . . .3.
11.3 Manual Reclamation . . . . . . . . . . . . . .11.3.1 The Cost of Fully-Manual Reclamation11.3.2 Reference Counting . . . . . . . . . . .11.4 Automated Reclamation, or Garbage Collection11.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 Decisions12.1 Changing Representations12.2 Errors . . . . . . . . . . .12.3 Changing Meaning . . . .12.4 One More Example . . . .8282838484848586878787898990.13 Desugaring as a Language Feature13.1 A First Example . . . . . . . . . . . . . .13.2 Syntax Transformers as Functions . . . .13.3 Guards . . . . . . . . . . . . . . . . . . .13.4 Or: A Simple Macro with Many Features13.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 . . . . . .90. 91. 92. 94. 95. 95. 97. 98. 99. 101. 10114 Control Operations14.1 Control on the Web . . . . . . . . . . . . . . . . .14.1.1 Program Decomposition into Now and Later14.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 . . . . . . . . . . . . 3125125
14.6.3 Defining Threads . . . . . . . . . . . . . . . . . . . . . . . .14.6.4 Better Primitives for Web Programming . . . . . . . . . . . .15 Checking Program Invariants Statically: Types15.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.4 Recursion in Data . . . . . . . . . . . .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.2 Type Inference . . . . . . . . . . . . .15.3.3 Union Types . . . . . . . . . . . . . . .15.3.4 Nominal Versus Structural Systems . . .15.3.5 Intersection Types . . . . . . . . . . . .15.3.6 Recursive Types . . . . . . . . . . . . .15.3.7 Subtyping . . . . . . . . . . . . . . . .15.3.8 Object Types . . . . . . . . . . . . . 16816917017117516 Checking Program Invariants Dynamically: Contracts16.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 . . . . . . . . . . . . . . . . . . . . . . . . .17717918018118518618718718818917 Alternate Application Semantics17.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 Words17.2.3 The Alternative: Reactive Languages .1931941941951961971991991992002012025.
17.2.4 Implementing Transparent Reactivity . . . . . . . . . . . . . . 20317.3 Backtracking Application . . . . . . . . . . . . . . . . . . . . . . . . 20517.3.1 Searching for Satisfaction . . . . . . . . . . . . . . . . . . . . 2056
11.1IntroductionOur PhilosophyPlease watch the video on YouTube. Someday there will be a textual description hereinstead.1.2The 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 because this is the best way for you to learn.Including 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’rereading.At 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 it.At various points you will encounter this:ExerciseThis 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 ashomework. 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 an exercise, but the answeris already in the book—most often in the text immediately following (i.e., 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 it.1.3The Language of This BookThe main programming language used in this book is Racket. Like with all operatingsystems, however, Racket actually supports a host of programming languages, so you7
must tell Racket which language 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 4.01//EN" . Similarly, Racket asks that you declare which language you will be using. Racket languages 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 every Racket program begins with #lang followed by the name of some language: bydefault, it’s Racket (written as racket). In this book we’ll almost always use thelanguageplai-typed. When we deviate we’ll say so explicitly, so unless indicated otherwise, put#lang plai-typedat the top of every file (and assume I’ve done the same).The Typed PLAI language differs from traditional Racket most importantly by being 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 newdatatypes:(define-type MisspelledAnimal[caml (humps : number)][yacc (height : number)])You can roughly think of this as analogous to the following in Java: an abstract classMisspelledAnimal and two concrete sub-classes caml and yacc, each of which hasone numeric constructor argument named humps and height, respectively.In this language, we construct instances as follows:(caml 2)(yacc 1.9)As the name suggests, define-type creates a type of the given name. We can use thiswhen, for instance, binding the above instances to names:(define ma1 : MisspelledAnimal (caml 2))(define ma2 : MisspelledAnimal (yacc 1.9))In fact you don’t need these particular type declarations, because Typed PLAI will infertypes for you here and in many other cases. Thus you could just as well have written(define ma1 (caml 2))(define ma2 (yacc 1.9))but we prefer to write explicit type declarations as a matter of both discipline andcomprehensibility when we return to programs later.8In DrRacket v. 5.3,go to Language,then ChooseLanguage, andselect “Use thelanguage declaredin the source”.There are additionalcommands forcontrolling theoutput of testing,for instance. Besure to read thedocumentation forthe language InDrRacket v. 5.3, goto Help, then HelpDesk, and in theHelp Desk searchbar, type“plai-typed”.
The type names can even be used recursively, as we will see repeatedly in this book(for instance, section 2.4).The language provides a pattern-matcher for use when writing expressions, such asa function’s body:(define (good? [ma : MisspelledAnimal]) : boolean(type-case MisspelledAnimal ma[caml (humps) ( humps 2)][yacc (height) ( height 2.1)]))In the expression ( humps 2), for instance, humps is the name given to whatevervalue was given as the argument to the constructor caml.Finally, you should write test cases, ideally before you’ve defined your function,but also afterwards to protect against accidental changes:(test (good? ma1) #t)(test (good? ma2) #f)When you run the above program, the language will give you verbose output tellingyou both tests passed. Read the documentation to learn how to suppress most of thesemessages.Here’s something important that is obscured above. We’ve used the same name,humps (and height), in both the datatype definition and in the fields of the patternmatch. This is absolutely unnecessary because the two are related by position, notname. Thus, we could have as well written the function as(define (good? [ma : MisspelledAnimal]) : boolean(type-case MisspelledAnimal ma[caml (h) ( h 2)][yacc (h) ( h 2.1)]))Because each h is only visible in the case branch in which it is introduced, the twohs do not in fact clash. You can therefore use convention and readability to dictateyour choices. In general, it makes sense to provide a long and descriptive name whendefining the datatype (because you probably won’t use that name again), but shorternames in the type-case because you’re likely to use use those names one or moretimes.I did just say you’re unlikely to use the field descriptors introduced in the datatypedefinition, but you can. The language provides selectors to extract fields without theneed for pattern-matching: e.g., caml-humps. Sometimes, it’s much easier to use theselector directly rather than go through the pattern-matcher. It often isn’t, as whendefining good? above, but just to be clear, let’s write it without pattern-matching:(define (good? [ma : MisspelledAnimal]) : boolean(cond[(caml? ma) ( (caml-humps ma) 2)][(yacc? ma) ( (yacc-height ma) 2.1)]))9
Do Now!What happens if you mis-apply functions to the wrong kinds of values?For instance, what if you give the caml constructor a string? What if yousend a number into each version of good? above?2Everything (We Will Say) About ParsingParsing is the act of turning an input character stream into a more structured, internalrepresentation. A common internal representation is as a tree, which programs canrecursively process. For instance, given the stream23 5 - 6we might want a tree representing addition whose left node represents the number 23and whose right node represents subtraction of 6 from 5. A parser is responsible forperforming this transformation.Parsing is a large, complex problem that is far from solved due to the difficulties ofambiguity. For instance, an alternate parse tree for the above input expression might putsubtraction at the top and addition below it. We might also want to consider whetherthis addition operation is commutative and hence whether the order of arguments canbe switched. Everything only gets much, much worse when we get to full-fledgedprogramming languages (to say nothing of natural languages).2.1A Lightweight, Built-In First Half of a ParserThese problems make parsing a worthy topic in its own right, and entire books, tools,and courses are devoted to it. However, from our perspective parsing is mostly a distraction, because we want to study the parts of programming languages that are notparsing. We will therefore exploit a handy feature of Racket to manage the transformation of input streams into trees: read. read is tied to the parenthetical form of thelanguage, in that it parses fully (and hence unambiguously) parenthesized terms intoa built-in tree form. For instance, running (read) on the parenthesized form of theabove input—( 23 (- 5 6))—will produce a list, whose first element is the symbol ’ , second element is thenumber 23, and third element is a list; this list’s first element is the symbol ’-, secondelement is the number 5, and third element is the number 6.2.2A Convenient ShortcutAs you know you need to test your programs extensively, which is hard to do when youmust manually type terms in over and over again. Fortunately, as you might expect, theparenthetical syntax is integrated deeply into Racket through the mechanism of quotation. That is, ’ expr —which you saw a moment ago in the above example—acts asif you had run (read) and typed expr at the prompt (and, of course, evaluates tothe value the (read) would have).10
2.3Types for ParsingActually, I’ve lied a little. I said that (read)—or equivalently, using quotation—willproduce a list, etc. That’s true in regular Racket, but in Typed PLAI, the type it returnsa distinct type called an s-expr
DrRacket v. 5.3, go to Help, then Help Desk, and in the Help Desk search bar, type “plai-typed”. datatypes: (define-typeMisspelledAnimal [caml(humps:number)] [yacc(height:number)]) You can roughly think of this as analogous to the following in Java: an abstract class MisspelledAnimal and two concrete sub-classes caml and yacc, each of which has
