Get Your Free Goodie Box here

Programming Languages: Application and Interpretation by Shriram Krishnamurthi - HTML preview

PLEASE NOTE: This is an HTML preview only and some elements such as links or page numbers may be incorrect.
Download the book in PDF, ePub, Kindle for a complete version.

Programming Languages:

Application and Interpretation

Shriram Krishnamurthi

Brown University

Copyright c 2003, Shriram Krishnamurthi

This work is licensed under the

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License.

If you create a derivative work, please include the version information below in your attribution.

This book is available free-of-cost from the author’s Web site.

This version was generated on 2007-04-26.

ii

Preface

The book is the textbook for the programming languages course at Brown University, which is taken pri-

marily by third and fourth year undergraduates and beginning graduate (both MS and PhD) students. It

seems very accessible to smart second year students too, and indeed those are some of my most successful

students. The book has been used at over a dozen other universities as a primary or secondary text. The

book’s material is worth one undergraduate course worth of credit.

This book is the fruit of a vision for teaching programming languages by integrating the “two cultures”

that have evolved in its pedagogy. One culture is based on interpreters, while the other emphasizes a survey

of languages. Each approach has significant advantages but also huge drawbacks. The interpreter method

writes programs to learn concepts, and has its heart the fundamental belief that by teaching the computer to

execute a concept we more thoroughly learn it ourselves.

While this reasoning is internally consistent, it fails to recognize that understanding definitions does

not imply we understand consequences of those definitions. For instance, the difference between strict

and lazy evaluation, or between static and dynamic scope, is only a few lines of interpreter code, but the

consequences of these choices is enormous. The survey of languages school is better suited to understand

these consequences.

The text therefore melds these two approaches. Concretely, students program with a new set of features

first, then try to distill those principles into an actual interpreter. This has the following benefits:

• By seeing the feature in the context of a real language, students can build something interesting with

it first, so they understand that it isn’t an entirely theoretical construct, and will actually care to build

an interpreter for it. (Relatively few students are excited in interpreters for their own sake, and we

have an obligation to appeal to the remainder too.)

• Students get at least fleeting exposure to multiple languages, which is an important educational at-

tribute that is being crushed by the wide adoption of industrially fashionable languages. (Better still,

by experimenting widely, they may come to appreciate that industrial fashions are just that, not the

last word in technological progress.)

• Because they have already programmed with the feature, the explanations and discussions are much

more interesting than when all students have seen is an abstract model.

• By first building a mental model for the feature through experience, students have a much better

chance of actually discovering how the interpreter is supposed to work.

iii

iv

PREFACE

In short, many more humans learn by induction than by deduction, so a pedagogy that supports it is much

more likely to succeed than one that suppresses it. The book currently reflects this design, though the survey

parts are done better in lecture than in the book.

Separate from this vision is a goal. My goal is to not only teach students new material, but to also change

the way they solve problems. I want to show students where languages come from, why we should regard

languages as the ultimate form of abstraction, how to recognize such an evolving abstraction, and how to

turn what they recognize into a language. The last section of the book, on domain-specific languages, is a

growing step in this direction.

Design Principles

• Concepts like design, elegance and artistic sensibility are rarely manifest in computer science courses;

in the name of not being judgmental, we may be running the risk of depriving our students of judg-

ment itself. We should reverse this trend. Students must understand that artificial objects have their

own aesthetic; the student must learn to debate the tradeoffs that lead to an aesthetic. Programming

languages are some of the most thoroughly designed artifacts in computer science. Therefore, the

study of programming languages offers a microcosm to study design itself.

• The best means we have to lead students to knowledge is through questions, not answers. The best

education prepares them to assess new data by confronting it with questions, processing the responses,

and iterating until they have formed a mental model of it. This book is therefore structured more like

a discussion than a presentation. It leads the reader down wrong paths (so don’t blindly copy code

from it!). It allows readers to get comfortable with mistaken assumptions before breaking them down

systematically.

• The programming languages course is one of the few places in the curriculum where we can tease

out and correct our students’ misconceptions about this material. They are often misled on topics

such as efficiency and correctness. Therefore, material on compilation, type systems and memory

management should directly confront their biases. For instance, a presentation of garbage collection

that does not also discuss the trade-offs with manual memory management will fail to address the

prejudices students bear.

Background and Prerequisite

This book assumes that students are comfortable reasoning informally about loop invariants, have modest

mathematical maturity, and are familiar with the existence of the Halting Problem. At Brown, they have all

been exposed to Java but not necessarily to any other languages (such as Scheme).

Supplementary Material

There is some material I use in my course that isn’t (currently) in this book:

preparation in Scheme For the first week, I offer supplementary sessions that teach students Scheme. The

material from these sessions is available from my course Web pages. In addition, I recommend the

v

use of a simple introduction to Scheme, such as the early sections of The Little Schemer or of How to

Design Programs.

domain-specific languages I discuss instances of real-world domain-specific languages, such as the access-

control language XACML. Students find the concepts easy to grasp, and can see why the language is

significant. In addition, it is one they may themselves encounter (or even decide to use) in their

programming tasks.

garbage collection I have provided only limited notes on garbage collection because I feel no need to offer

my own alternative to Paul Wilson’s classic survey, Uniprocessor Garbage Collection Techniques. I

recommend choosing sections from this survey, depending on student maturity, as a supplement to

this text.

model checking I supplement the discussion of types with a presentation on model checking, to show

students that it is possible to go past the fixed set of theorems of traditional type systems to systems

that permit developers to state theorems of interest. I have a pre-prepared talk on this topic, and would

be happy to share those slides.

Web programming Before plunging into continuations, I discuss Web programming APIs and demonstrate

how they mask important control operators. I have a pre-prepared talk on this topic, and would

be happy to share those slides. I also wrap up the section on continuations with a presentation on

programming in the PLT Scheme Web server, which natively supports continuations.

articles on design I hand out a variety of articles on the topic of design. I’ve found Dan Ingalls’s dissection

of Smalltalk, Richard Gabriel’s on Lisp, and Paul Graham’s on both programming and design the

most useful. Graham has now collected his essays in the book Hackers and Painters.

logic programming The notes on logic programming are the least complete. Students are already familiar

with unification from type inference by the time I arrive at logic programming. Therefore, I focus on

the implementation of backtracking. I devote one lecture to the use of unification, the implications

of the occurs-check, depth-first versus breadth-first search, and tabling. In another lecture, I present

the implementation of backtracking through continuations. Concretely, I use the presentation in Dorai

Sitaram’s Teach Yourself Scheme in Fixnum Days. This presentation consolidates two prior topics,

continuations and macros.

Exercises

Numerous exercises are sprinkled throughout the book. Several more, in the form of homework assignments

and exams, are available from my course’s Web pages (where year is one of 2000, 2001, 2002, 2003,

2004 and 2005):

http://www.cs.brown.edu/courses/cs173/ year /

In particular, in the book I do not implement garbage collectors and type checkers. These are instead

homework assignments, ones that students generally find extremely valuable (and very challenging!).

vi

PREFACE

Programs

This book asks students to implement language features using a combination of interpreters and little com-

pilers. All the programming is done in Scheme, which has the added benefit of making students fairly

comfortable in a language and paradigm they may not have employed before. End-of-semester surveys re-

veal that students are far more likely to consider using Scheme for projects in other courses after taking this

course than they were before it (even when they had prior exposure to Scheme).

Though every line of code in this book has been tested and is executable, I purposely do not distribute

the code associated with this book. While executable code greatly enhances the study of programming

languages, it can also detract if students execute the code mindlessly. I therefore ask you, Dear Reader, to

please type in this code as if you were writing it, paying close attention to every line. You may be surprised

by how much many of them have to say.

Course Schedule

The course follows approximately the following schedule:

Weeks

Topics

1

Introduction, Scheme tutorials, Modeling Languages

2–3

Substitution and Functions

3

Laziness

4

Recursion

4

Representation Choices

4–5

State

5–7

Continuations

7–8

Memory Management

8–10

Semantics and Types

11

Programming by Searching

11–12

Domain-Specific Languages and Metaprogramming

Miscellaneous “culture lecture” topics such as model checking, extensibility and future directions consume

another week.

An Invitation

I think the material in these pages is some of the most beautiful in all of human knowledge, and I hope any

poverty of presentation here doesn’t detract from it. Enjoy!

Acknowledgments

This book has a long and humbling provenance. The conceptual foundation for this interpreter-based ap-

proach traces back to seminal work by John McCarthy. My own introduction to it was through two texts I

read as an undergraduate, the first editions of The Structure and Interpretation of Computer Programs by

Abelson and Sussman with Sussman and Essentials of Programming Languages by Friedman, Wand and

Haynes. Please read those magnificent books even if you never read this one.

My graduate teaching assistants, Dave Tucker and Rob Hunter, wrote and helped edit lecture notes that

helped preserve continuity through iterations of my course. Greg Cooper has greatly influenced my thinking

on lazy evaluation. Six generations of students at Brown have endured drafts of this book.

Bruce Duba, Corky Cartwright, Andrew Wright, Cormac Flanagan, Matthew Flatt and Robby Findler

have all significantly improved my understanding of this material. Matthew and Robby’s work on DrScheme

has greatly enriched my course’s pedagogy. Christian Queinnec and Paul Graunke inspired the presentation

of continuations through Web programming, and Greg Cooper created the approach to garbage collection,

both of which are an infinite improvement over prior approaches.

Alan Zaring, John Lacey and Kathi Fisler recognized that I might like this material and introduced me to

it (over a decade ago) before it was distributed through regular channels. Dan Friedman generously gave of

his time as I navigated Essentials. Eli Barzilay, John Clements, Robby Findler, John Fiskio-Lasseter, Kathi

Fisler, Cormac Flanagan, Matthew Flatt, Suresh Jagannathan, Gregor Kiczales, Mira Mezini, Prabhakar

Ragde, Marc Smith, and Éric Tanter have provided valuable feedback after using prior versions of this text.

The book’s accompanying software has benefited from support by several generations of graduate as-

sistants, especially Greg Cooper and Guillaume Marceau. Eli Barzilay and Matthew Flatt have also made

excellent, creative contributions to it.

My chairs at Brown, Tom Dean and Eli Upfal, have permitted me to keep teaching my course so I

could develop this book. I can’t imagine how many course staffing nightmares they’ve endured, and ensuing

temptations they’ve suppressed, in the process.

My greatest debt is to Matthias Felleisen. An early version of this text grew out of my transcript of his

course at Rice University. That experience made me realize that even the perfection embodied in the books

I admired could be improved upon. This result is not more perfect, simply different—its outlook shaped by

standing on the shoulders of giants.

vii

viii

ACKNOWLEDGMENTS

Thanks

Several more people have made suggestions, asked questions, and identified errors:

Ian Barland, Hrvoje Blazevic, Daniel Brown, Greg Buchholz, Lee Butterman, Richard Cobbe, Bruce Duba,

Stéphane Ducasse, Marco Ferrante, Dan Friedman, Mike Gennert, Arjun Guha, Roberto Ierusalimschy,

Steven Jenkins, Eric Koskinen, Neel Krishnaswami, Benjamin Landon, Usman Latif, Dan Licata, Alice Liu,

Paulo Matos, Grant Miner, Ravi Mohan, Jason Orendorff, Klaus Ostermann, Pupeno [sic], Manos Renieris,

Morten Rhiger, Bill Richter, Peter Rosenbeck, Amr Sabry, Francisco Solsona, Anton van Straaten, Andre

van Tonder, Michael Tschantz, Phil Wadler, Joel Weinberger, and Greg Woodhouse.

In addition, Michael Greenberg instructed me in the rudiments of classifying flora.

Contents

Preface

iii

Acknowledgments

vii

I

Prelude

1

1

Modeling Languages

3

1.1

Modeling Meaning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.2

Modeling Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.3

A Primer on Parsers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.4

Primus Inter Parsers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

II

Rudimentary Interpreters

11

2

Interpreting Arithmetic

13

3

Substitution

15

3.1

Defining Substitution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

3.2

Calculating with with . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

3.3

The Scope of with Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

3.4

What Kind of Redundancy do Identifiers Eliminate? . . . . . . . . . . . . . . . . . . . . . .

23

3.5

Are Names Necessary? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

4

An Introduction to Functions

27

4.1

Enriching the Language with Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

4.2

The Scope of Substitution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

4.3

The Scope of Function Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

5

Deferring Substitution

33

5.1

The Substitution Repository

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

5.2

Deferring Substitution Correctly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

ix

x

CONTENTS

5.3

Fixing the Interpreter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

6

First-Class Functions

41

6.1

A Taxonomy of Functions

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

6.2

Enriching the Language with Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

6.3

Making with Redundant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

6.4

Implementing Functions using Deferred Substitutions . . . . . . . . . . . . . . . . . . . . .

45

6.5

Some Perspective on Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

6.5.1

Filtering and Sorting Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

6.5.2

Differentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

6.5.3

Callbacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

50

6.6

Eagerness and Laziness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

6.7

Standardizing Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

III

Laziness

57

7

Programming with Laziness

59

7.1

Haskell

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

7.1.1

Expressions and Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

7.1.2

Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

7.1.3

Polymorphic Type Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

62

7.1.4

Laziness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

64

7.1.5

An Interpreter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

68

7.2

Shell Scripting

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

8

Implementing Laziness

73

8.1

Implementing Laziness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

73

8.2

Caching Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

77

8.3

Caching Computations Safely

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

79

8.4

Scope and Evaluation Regimes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

82

IV

Recursion

87

9

Understanding Recursion

89

9.1

A Recursion Construct . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

90

9.2

Environments for Recursion

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

91

9.3

An Environmental Hazard

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

95

10 Implementing Recursion

97

CONTENTS

xi

V

Intermezzo

103

11 Representation Choices

105

11.1 Representing Environments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

11.2 Representing Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

11.3 Representing Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

11.4 Types of Interpreters

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

11.5 Procedural Representation of Recursive Environments . . . . . . . . . . . . . . . . . . . . . 109

VI

State

115

12 Church and State

117

13 Mutable Data Structures

119

13.1 Implementation Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

13.2 Insight . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

13.3 An Interpreter for Mutable Boxes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

13.3.1 The Evaluation Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

13.3.2 The Interpreter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

13.4 Scope versus Extent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

14 Variables

133

14.1 Implementing Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

14.2 Interaction Between Variables and Function Application

. . . . . . . . . . . . . . . . . . . 135

14.3 Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

VII

Continuations

145

15 Some Problems with Web Programs

147

16 The Structure of Web Programs

149

16.1 Explicating the Pending Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

16.2 A Better Server Primitive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

16.3 Testing Web Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

16.4 Executing Programs on a Traditional Server . . . . . . . . . . . . . . . . . . . . . . . . . . 154

17 More Web Transformation

157

17.1 Transforming Library and Recursive Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

17.2 Transforming Multiple Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

17.3 Transforming State . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

17.4 The Essence of the Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

17.5 Transforming Higher-Order Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

xii

CONTENTS

17.6 Perspective on the Web Transformation

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

18 Conversion into Continuation-Passing Style

169

18.1 The Transformation, Informally

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169

18.2 The Transformation, Formally . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

18.3 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

19 Programming with Continuations

177

19.1 Capturing Continuations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

19.2 Escapers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

19.3 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

19.4 Web Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

19.5 Producers and Consumers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

19.6 A Better Producer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186

19.7 Why Continuations Matter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192

20 Implementing Continuations

193

20.1 Representing Continuations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

20.2 Adding Continuations to the Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

20.3 On Stacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199

20.4 Tail Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200

20.5 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202

VIII

Memory Management

207

21 Automatic Memory Management

209

21.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209

21.2 Truth and Provability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

IX

Semantics

215

22 Shrinking the Language

217

22.1 Encoding Lists

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218

22.2 Encoding Boolean Constants and Operations . . . . . . . . . . . . . . . . . . . . . . . . . . 219

22.3 Encoding Numbers and Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220

22.4 Eliminating Recursion

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223

23 Semantics

231

CONTENTS

xiii

X

Types

235

24 Introduction

237

24.1 What Are Types? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239

24.2 Type System Design Forces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240

24.3 Why Types? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240

25 Type Judgments

243

25.1 What They Are . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243

25.2 How Type Judgments Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246

26 Typing Control

249

26.1 Conditionals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249

26.2 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250

26.3 Termination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252

26.4 Typed Recursive Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253

27 Typing Data

255

27.1 Recursive Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255

27.1.1 Declaring Recursive Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255

27.1.2 Judgments for Recursive Types

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 256

27.1.3 Space for Datatype Variant Tags . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258

28 Type Soundness

261

29 Explicit Polymorphism

265

29.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265

29.2 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266

29.3 The Type Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269

29.4 Evaluation Semantics and Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270

29.5 Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271

30 Type Inference

273

30.1 Inferring Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273

30.1.1 Example: Factorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274

30.1.2 Example: Numeric-List Length . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275

30.2 Formalizing Constraint Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276

30.3 Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277

30.4 Example: Using First-Class Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279

30.5 Solving Type Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280

30.5.1 The Unification Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280

30.5.2 Example of Unification at Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280

30.5.3 Parameterized Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281

30.5.4 The “Occurs” Check . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282

xiv

CONTENTS

30.6 Underconstrained Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282

30.7 Principal Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283

31 Implicit Polymorphism

285

31.1 The Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285

31.2 A Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286

31.3 A Better Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287

31.4 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288

31.5 A Significant Subtlety . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288

31.6 Why Let and not Lambda? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289

31.7 The Structure of ML Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289

31.8 Interaction with Effects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290

XI

Programming by Searching

291

32 Introduction

293

33 Programming in Prolog

295

33.1 Example: Academic Family Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295

33.2 Intermission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301

33.3 Example: Encoding Type Judgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302

33.4 Final Credits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305

34 Implementing Prolog

307

34.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307

34.1.1 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308

34.1.2 Satisfaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308

34.1.3 Matching with Logic Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310

34.2 Subtleties and Compromises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311

34.3 Future Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311

XII

Domain-Specific Languages and Metaprogramming

313

35 Domain-Specific Languages

315

35.1 Language Design Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315

35.2 Languages as Abstractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315

35.3 Domain-Specific Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316

36 Macros as Compilers

319

36.1 Language Reuse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319

36.1.1 Example: Measuring Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319

36.1.2 Example: Local Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322

CONTENTS

xv

36.1.3 Example: Nested Local Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 323

36.1.4 Example: Simple Conditional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324

36.1.5 Example: Disjunction

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325

36.2 Hygiene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327

36.3 More Macrology by Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328

36.3.1 Loops with Named Iteration Identifiers . . . . . . . . . . . . . . . . . . . . . . . . 329

36.3.2 Overriding Hygiene: Loops with Implicit Iteration Identifiers . . . . . . . . . . . . . 330

36.3.3 Combining the Pieces: A Loop for All Seasons . . . . . . . . . . . . . . . . . . . . 333

36.4 Comparison to Macros in C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334

36.5 Abuses of Macros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334

36.6 Uses of Macros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335

37 Macros and their Impact on Language Design

337

37.1 Language Design Philosophy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337

37.2 Example: Pattern Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338

37.3 Example: Automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341

37.3.1 Concision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345

37.3.2 Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347

37.4 Other Uses

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348

37.5 Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348

XIII

What’s Next?

349

38 Programming Interactive Systems

351

39 What Else is Next

355

xvi

CONTENTS

Part I

Prelude

1

Chapter 1

Modeling Languages

A student of programming languages who tries to study a new language can be overwhelmed by details.

Virtually every language consists of

• a peculiar syntax,

• some behavior associated with each syntax,

• numerous useful libraries, and

• a collection of idioms that programmers of that language use.

All four of these attributes are important to a programmer who wants to adopt a language. To a scholar,

however, one of these is profoundly significant, while the other three are of lesser importance.

The first insignificant attribute is the syntax. Syntaxes are highly sensitive topics,1 but in the end, they don’t tell us very much about a program’s behavior. For instance, consider the following four fragments:

1. a [25]

2. (vector-ref a 25)

3. a [25]

4. a [25]

Which two are most alike? The first and second, obviously! Why? Because the first is in Java and the

second is in Scheme, both of which signal an error if the vector associated with a has fewer than 25 entries;

the third, in C, blithely ignores the vector’s size, leading to unspecified behavior, even though its syntax is

exactly the same as that of the Java code. The fourth, in ML or Haskell, is an application of a to the list

containing just one element, 25: that is, it’s not an array dereference at all, it’s a function appliction!

That said, syntax does matter, at least inasmuch as its brevity can help programmers express and under-

stand more by saying less. For the purpose of our study, however, syntax will typically be a distraction, and

1Matthias Felleisen: “Syntax is the Viet Nam of programming languages.”

3

4

CHAPTER 1. MODELING LANGUAGES

will often get in the way of our understanding deeper similarities (as in the Java-Scheme-C example above).

We will therefore use a uniform syntax for all the languages we implement.

The size of a language’s library, while perhaps the most important characteristic to a programmer who

wants to accomplish a task, is usually a distraction when studying a language. This is a slightly tricky

contention, because the line between the core of a language and its library is fairly porous. Indeed, what one

language considers an intrinsic primitive, another may regard as a potentially superfluous library operation.

With experience, we can learn to distinguish between what must belong in the core and what need not. It

is even possible to make this distinction quite rigorously using mathematics. Our supplementary materials

will include literature on this distinction.

Finally, the idioms of a language are useful as a sociological exercise (“How do the natives of this lin-

guistic terrain cook up a Web script?”), but it’s dangerous to glean too much from them. Idioms are funda-

mentally human, and therefore bear all the perils of faulty, incomplete and sometimes even outlandish human

understanding. If a community of Java programmers has never seen a particular programming technique—

for instance, the principled use of objects as callbacks—they are likely to invent an idiom to take its place,

but it will almost certainly be weaker, less robust, and less informative to use the idiom than to just use

callbacks. In this case, and indeed in general, the idiom sometimes tells us more about the programmers

than it does about the language. Therefore, we should be careful to not read too much into one.

In this course, therefore, we will focus on the behavior associated with syntax, namely the semantics

of programming languages. In popular culture, people like to say “It’s just semantics!”, which is a kind of

put-down: it implies that their correspondent is quibbling over minor details of meaning in a jesuitical way.

But communication is all about meaning: even if you and I use different words to mean the same thing, we

understand one another; but if we use the same word to mean different things, great confusion results. In

this study, therefore, we will wear the phrase “It’s just semantics!” as a badge of honor, because semantics

leads to discourse which (we hope) leads to civilization.

Just semantics. That’s all there is.

1.1

Modeling Meaning

So we want to study semantics. But how? To study meaning, we need a language for describing meaning.

Human language is, however, notoriously slippery, and as such is a poor means for communicating what are

very precise concepts. But what else can we use?

Computer scientists use a variety of techniques for capturing the meaning of a program, all of which rely

on the following premise: the most precise language we have is that of mathematics (and logic). Tradition-

ally, three mathematical techniques have been especially popular: denotational, operational and axiomatic

semantics. Each of these is a rich and fascinating field of study in its own right, but these techniques are

either too cumbersome or too advanced for our use. (We will only briefly gloss over these topics, in sec-

tion 23.) We will instead use a method that is a first cousin of operational semantics, which some people

call interpreter semantics.

The idea behind an interpreter semantics is simple: to explain a language, write an interpreter for it. The

act of writing an interpreter forces us to understand the language, just as the act of writing a mathematical

description of it does. But when we’re done writing, the mathematics only resides on paper, whereas we can

run the interpreter to study its effect on sample programs. We might incrementally modify the interpreter

1.2. MODELING SYNTAX

5

if it makes a mistake. When we finally have what we think is the correct representation of a language’s

meaning, we can then use the interpreter to explore what the language does on interesting programs. We can

even convert an interpreter into a compiler, thus leading to an efficient implementation that arises directly

from the language’s definition.

A careful reader should, however, be either confused or enraged (or both). We’re going to describe

the meaning of a language through an interpreter, which is a program. That program is written in some

language. How do we know what that language means? Without establishing that first, our interpreters

would appear to be mere scrawls in an undefined notation. What have we gained?

This is an important philosophical point, but it’s not one we’re going to worry about much in practice.

We won’t for the practical reason that the language in which we write the interpreter is one that we under-

stand quite well: it’s succint and simple, so it won’t be too hard to hold it all in our heads. (Observe that

dictionaries face this same quandary, and negotiate it successsfully in much the same manner.) The supe-

rior, theoretical, reason is this: others have already worked out the mathematical semantics of this simple

language. Therefore, we really are building on rock. With that, enough of these philosophical questions for

now. We’ll see a few other ones later in the course.

1.2

Modeling Syntax

I’ve argued briefly that it is both futile and dangerous to vest too much emotion in syntax. In a platonic

world, we might say

Irrespective of whether we write

• 3 + 4

(infix),

• 3 4 +

(postfix), or

• (+ 3 4)

(parenthesized prefix),

we always mean the idealized action of adding the idealized numbers (represented by) “3” and

“4”.

Indeed, each of these notations is in use by at least one programming language.

If we ignore syntactic details, the essence of the input is a tree with the addition operation at the root

and two leaves, the left leaf representing the number 3 and the right leaf the number 4. With the right data

definition, we can describe this in Scheme as the expression

(add (num 3) (num 4))

and similarly, the expression

• (3 − 4) + 7

(infix),

• 3 4 - 7 +

(postfix), or

• (+ (- 3 4) 7)

(parenthesized prefix)

6

CHAPTER 1. MODELING LANGUAGES

would be represented as

(add (sub (num 3) (num 4))

(num 7))

One data definition that supports these representations is the following:

(define-type AE

[num (n number?)]

[add (lhs AE?)

(rhs AE?)]

[sub (lhs AE?)

(rhs AE?)])

where AE stands for “Arithmetic Expression”.

Exercise 1.2.1 Why are the lhs and rhs sub-expressions of type AE rather than of type num? Provide sample

expressions permitted by the former and rejected by the latter, and argue that our choice is reasonable.

1.3

A Primer on Parsers

Our interpreter should consume terms of type AE, thereby avoiding the syntactic details of the source lan-

guage. For the user, however, it becomes onerous to construct terms of this type. Ideally, there should be a

program that translates terms in concrete syntax into values of this type. We call such a program a parser.

In more formal terms, a parser is a program that converts concrete syntax (what a user might type) into

abstract syntax. The word abstract signifies that the output of the parser is idealized, thereby divorced from

physical, or syntactic, representation.

As we’ve seen, there are many concrete syntaxes that we could use for arithmetic expressions. We’re

going to pick one particular, slightly peculiar notation. We will use a prefix parenthetical syntax that, for

arithmetic, will look just like that of Scheme. With one twist: we’ll use {braces} instead of (parentheses), so

we can distinguish concrete syntax from Scheme just by looking at the delimiters. Here are three programs

employing this concrete syntax:

1. 3

2. {+ 3 4}

3. {+ {- 3 4} 7}

Our choice is, admittedly, fueled by the presence of a convenient primitive in Scheme—the primitive

that explains why so many languages built atop Lisp and Scheme look so much like Lisp and Scheme (i.e.,

they’re parenthetical), even if they have entirely different meanings. That primitive is called read.

Here’s how read works. It consumes an input port (or, given none, examines the standard input port).

If it sees a sequence of characters that obey the syntax of a number, it converts them into the corresponding

number in Scheme and returns that number. That is, the input stream

1 7 2 9 <eof>

1.3. A PRIMER ON PARSERS

7

(the spaces are merely for effect, not part of the stream) would result in the Scheme number 1729. If the

sequence of characters obeys the syntax of a symbol (sans the leading quote), read returns that symbol: so

c s 1 7 3 <eof>

(again, the spaces are only for effect) evaluates to the Scheme symbol ’cs173. Likewise for other primitive

types. Finally, if the input is wrapped in a matched pair of parenthetical delimiters—either (parentheses),

[brackets] or {braces}—read returns a list of Scheme values, each the result of invoking read recursively.

Thus, for instance, read applied to the stream

(1 a)

returns (list 1 ’a), to