Bibliographic record and links to related information available from the Library of Congress catalog.

Note: Contents data are machine generated based on pre-publication provided by the publisher. Contents may have variations from the printed book or be incomplete or contain other coding.

```Contents
Foreword . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxv
1 Inductive Sets of Data . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Recursively Specified Data . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Deriving Recursive Programs . . . . . . . . . . . . . . . . . . . . 20
1.3 Auxiliary Procedures and Context Arguments . . . . . . . . . . 37
1.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2 Data Abstraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.1 Specifying Data via Interfaces . . . . . . . . . . . . . . . . . . . . 51
2.2 Representation Strategies for Data Types . . . . . . . . . . . . . . 58
2.3 Interfaces for Recursive Data Types . . . . . . . . . . . . . . . . . 68
2.4 A Tool for Defining Recursive Datatypes . . . . . . . . . . . . . . 74
2.5 Abstract Syntax and its Representation . . . . . . . . . . . . . . . 84
3 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.1 Specification and Implementation Strategy . . . . . . . . . . . . 91
3.2 LET: A simple language . . . . . . . . . . . . . . . . . . . . . . . 95
3.3 PROC: A language with procedures . . . . . . . . . . . . . . . . 117
3.4 LETREC: A language with recursive procedures . . . . . . . . . 131
3.5 Scoping and Binding of Variables . . . . . . . . . . . . . . . . . . 138
3.6 Eliminating Variable Names . . . . . . . . . . . . . . . . . . . . . 144
3.7 Implementing Lexical Addressing . . . . . . . . . . . . . . . . . 148
DRAFT iii August 3, 2007 9:51
iv Contents
4 State . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
4.1 Computational Effects . . . . . . . . . . . . . . . . . . . . . . . . 161
4.2 EXPLICIT-REFS: A language with explicit references . . . . . . . 163
4.3 IMPLICIT-REFS: a language with implicit references . . . . . . . 180
4.4 MUTABLE-PAIRS: a language with mutable pairs . . . . . . . . 192
4.5 Parameter-Passing Variations . . . . . . . . . . . . . . . . . . . . 200
5 Continuation-Passing Interpreters . . . . . . . . . . . . . . . . . . . 215
5.1 A Continuation-Passing Interpreter . . . . . . . . . . . . . . . . . 219
5.2 An Imperative Interpreter . . . . . . . . . . . . . . . . . . . . . . 244
5.3 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
5.4 Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
6 Continuation-Passing Style . . . . . . . . . . . . . . . . . . . . . . . 289
6.1Writing programs in continuation-passing style . . . . . . . . . . 290
6.2 Tail Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
6.3 Converting to Continuation-Passing Style . . . . . . . . . . . . . 318
6.4 Modeling computational effects . . . . . . . . . . . . . . . . . . . 335
7 Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
7.1 Values and their types . . . . . . . . . . . . . . . . . . . . . . . . 350
7.2 Assigning a type to an expression . . . . . . . . . . . . . . . . . . 355
7.3 CHECKED: A Type-Checked Language . . . . . . . . . . . . . . 359
7.4 INFERRED: a Language with Type Inference . . . . . . . . . . . 370
8 Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
8.1 The Simple Module System . . . . . . . . . . . . . . . . . . . . . 413
8.2 Modules that declare types . . . . . . . . . . . . . . . . . . . . . . 438
8.3 Module Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 467
9 Objects and Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
9.1 Object-Oriented Programming . . . . . . . . . . . . . . . . . . . 491
9.2 Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495
9.3 The Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501
9.4 The Interpreter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
9.5 A Typed Language . . . . . . . . . . . . . . . . . . . . . . . . . . 531
9.6 The Type Checker . . . . . . . . . . . . . . . . . . . . . . . . . . . 539
A The SLLGEN Parsing System . . . . . . . . . . . . . . . . . . . . . . 567
```

Library of Congress Subject Headings for this publication:

Programming languages (Electronic computers).