Главная
Essentials of Programming Languages (The MIT Press)
Essentials of Programming Languages (The MIT Press)
Friedman, Daniel P., Wand, Mitchell
0 /
0
Насколько Вам понравилась эта книга?
Какого качества скаченный файл?
Скачайте книгу, чтобы оценить ее качество
Какого качества скаченные файлы?
A new edition of a textbook that provides students with a deep, working understanding of the essential concepts of programming languages, completely revised, with significant new material. This book provides students with a deep, working understanding of the essential concepts of programming languages. Most of these essentials relate to the semantics, or meaning, of program elements, and the text uses interpreters (short programs that directly analyze an abstract representation of the program text) to express the semantics of many essential language elements in a way that is both clear and executable. The approach is both analytical and handson. The book provides views of programming languages using widely varying levels of abstraction, maintaining a clear connection between the highlevel and lowlevel views. Exercises are a vital part of the text and are scattered throughout; the text explains the key concepts, and the exercises explore alternative designs and other issues. The complete Scheme code for all the interpreters and analyzers in the book can be found online through The MIT Press web site. For this new edition, each chapter has been revised and many new exercises have been added. Significant additions have been made to the text, including completely new chapters on modules and continuationpassing style. Essentials of Programming Languages can be used for both graduate and undergraduate courses, and for continuing education courses for programmers.
Год:
2008
Издание:
third edition
Издательство:
The MIT Press
Язык:
english
Страницы:
410 / 433
ISBN 13:
9780262062794
Файл:
PDF, 1,23 MB
Ваши теги:
Скачать (pdf, 1,23 MB)
 Открыть в браузере
 Checking other formats...
 Конвертировать в EPUB
 Конвертировать в FB2
 Конвертировать в MOBI
 Конвертировать в TXT
 Конвертировать в RTF
 Конвертированный файл может отличаться от оригинала. При возможности лучше скачивать файл в оригинальном формате.
 Пожалуйста, сначала войдите в свой аккаунт

Нужна помощь? Пожалуйста, ознакомьтесь с инструкцией как отправить книгу на Kindle
В течение 15 минут файл будет доставлен на Ваш email.
В течение 15 минут файл будет доставлен на Ваш kindle.
Примечание: Вам необходимо верифицировать каждую книгу, которую Вы отправляете на Kindle. Проверьте свой почтовый ящик на наличие письма с подтверждением от Amazon Kindle Support.
Примечание: Вам необходимо верифицировать каждую книгу, которую Вы отправляете на Kindle. Проверьте свой почтовый ящик на наличие письма с подтверждением от Amazon Kindle Support.
Возможно Вас заинтересует Powered by Rec2Me
Ключевые слова
exp^{1124}
value^{919}
cont^{705}
env^{687}
procedure^{622}
int^{552}
var^{548}
proc^{527}
exercise^{511}
val^{506}
language^{460}
lambda^{446}
class^{432}
method^{402}
program^{399}
module^{395}
define^{368}
apply^{359}
tenv^{323}
cps^{312}
exp1^{296}
continuation^{288}
environment^{278}
data^{276}
types^{265}
interface^{263}
zero^{261}
extend^{257}
variable^{248}
example^{243}
interpreter^{230}
bool^{220}
expval^{217}
procedures^{215}
object^{204}
write^{201}
representation^{194}
values^{176}
exp2^{167}
expressions^{166}
letrec^{165}
saved^{164}
argument^{161}
variables^{153}
cases^{153}
subst^{147}
returns^{147}
bound^{143}
programming^{142}
languages^{133}
num^{126}
grammar^{119}
val1^{116}
implementation^{116}
iface^{115}
syntax^{113}
decl^{108}
static^{107}
programs^{106}
rator^{106}
Связанные Буклисты
0 comments
Вы можете оставить отзыв о книге и поделиться своим опытом. Другим читателям будет интересно узнать Ваше мнение о прочитанных книгах. Независимо от того, пришлась ли Вам книга по душе или нет, если Вы честно и подробно расскажете об этом, люди смогут найти для себя новые книги, которые их заинтересуют.
1

2

Essentials of Programming Languages third edition Daniel P. Friedman and Mitchell Wand This book provides students with a deep, working understanding of the essential concepts of programming languages. Most of these essentials relate to the semantics, or meaning, of program elements, and the text uses interpreters (short programs that directly analyze an abstract representation of the program text) to express the semantics of many essential language elements in a way that is both clear and executable. The approach is both analytical and handson. The book provides views of programming languages using widely varying levels of abstraction, maintaining a clear connection between the highlevel and lowlevel views. Exercises are a vital part of the text and are scattered throughout; the text explains the key concepts, and the exercises explore alternative designs and other issues. The complete Scheme code for all the interpreters and analyzers in the book can be found online through The MIT Press website. For this new edition, each chapter has been revised and many new exercises have been added. Significant additions have been made to the text, including completely new chapters on modules and continuationpassing style. Essentials of Programming Languages can be used for both graduate and undergraduate courses, and for continuing education courses for programmers. “I’ve found the interpretersbased approach for teaching programming languages to be both compelling and rewarding for my students. Exposing students to the revelation that an interpreter for a programming language is itself just another program opens up a world of possibilities for problem solving. The third edition of Essentials of Programming Languages makes this approach of writing interpreters more accessible than ever.” —Marc L. Smith, Department of Computer Science, Vassar College The MIT Press Massachusetts Institute of Technology Cambridge, Massachusetts 02142 http://mitpress.mit.edu 9780262062794 Friedman and Wand “Having taught from; EOPL for several years, I appreciate the way it produces students who understand the terminology and concepts of programming languages in a deep way, not just from reading about the concepts, but from programming them and experimenting with them. This new edition has an increased emphasis on types as contracts for defining procedure interfaces, which is quite important for many students.” —Gary T. Leavens, School of Electrical Engineering and Computer Science, University of Central Florida THIRD EDITION MD DALIM 955472 3/22/08 CYAN MAG YELO BLACK “With lucid prose and elegant code, this book provides the most concrete introduction to the few building blocks that give rise to a wide variety of programming languages. I recommend it to my students and look forward to using it in my courses.” —Chungchieh Shan, Department of Computer Science, Rutgers University ESSENTIALS OF PROGRAMMING LANGUAGES THIRD EDITION Daniel P. Friedman is Professor of Computer Science at Indiana University and is the author of many books published by The MIT Press, including The Little Schemer (fourth edition, 1995), The Seasoned Schemer (1995), A Little Java, A Few Patterns (1997), each of these coauthored with Matthias Felleisen, and The Reasoned Schemer (2005), coauthored with William E. Byrd and Oleg Kiselyov. Mitchell Wand is Professor of Computer Science at Northeastern University. ESSENTIALS OF PROGRAMMING LANGUAGES computer science/programming languages Daniel P. Friedman and Mitchell Wand Essentials of Programming Languages third edition Essentials of Programming Languages third edition Daniel P. Friedman Mitchell Wand The MIT Press Cambridge, Massachusetts London, England © 2008 Daniel P. Friedman and Mitchell Wand All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher. MIT Press books may be purchased at special quantity discounts for business or sales promotional use. For information, please email special_sales@mitpress.mit.edu or write to Special Sales Department, The MIT Press, 55 Hayward Street, Cambridge, MA 02142. This book was set in LATEX 2ε by the authors, and was printed and bound in the United States of America. Library of Congress CataloginginPublication Data Friedman, Daniel P. Essentials of programming languages / Daniel P. Friedman, Mitchell Wand. —3rd ed. p. cm. Includes bibliographical references and index. ISBN 9780262062794 (hbk. : alk. paper) 1. Programming Languages (Electronic computers). I. Wand, Mitchell. II. Title. QA76.7.F73 2008 005.1—dc22 10 9 8 7 6 5 4 3 2 1 2007039723 Contents Foreword by Hal Abelson ix Preface xv Acknowledgments xxi 1 Inductive Sets of Data 1.1 Recursively Speciﬁed Data 1.2 Deriving Recursive Programs 1.3 Auxiliary Procedures and Context Arguments 1.4 Exercises 1 1 12 22 25 2 Data Abstraction 2.1 Specifying Data via Interfaces 2.2 Representation Strategies for Data Types 2.3 Interfaces for Recursive Data Types 2.4 A Tool for Deﬁning Recursive Data Types 2.5 Abstract Syntax and Its Representation 31 31 35 42 45 51 3 Expressions 3.1 Speciﬁcation and Implementation Strategy 3.2 LET: A Simple Language 3.3 PROC: A Language with Procedures 3.4 LETREC: A Language with Recursive Procedures 3.5 Scoping and Binding of Variables 3.6 Eliminating Variable Names 3.7 Implementing Lexical Addressing 57 57 60 74 82 87 91 93 vi Contents 4 State 4.1 Computational Effects 4.2 EXPLICITREFS: A Language with Explicit References 4.3 IMPLICITREFS: A Language with Implicit References 4.4 MUTABLEPAIRS: A Language with Mutable Pairs 4.5 ParameterPassing Variations 103 103 104 113 124 130 5 ContinuationPassing Interpreters 5.1 A ContinuationPassing Interpreter 5.2 A Trampolined Interpreter 5.3 An Imperative Interpreter 5.4 Exceptions 5.5 Threads 139 141 155 160 171 179 6 ContinuationPassing Style 6.1 Writing Programs in ContinuationPassing Style 6.2 Tail Form 6.3 Converting to ContinuationPassing Style 6.4 Modeling Computational Effects 193 193 203 212 226 7 Types 7.1 Values and Their Types 7.2 Assigning a Type to an Expression 7.3 CHECKED: A TypeChecked Language 7.4 INFERRED: A Language with Type Inference 233 235 238 240 248 8 Modules 8.1 The Simple Module System 8.2 Modules That Declare Types 8.3 Module Procedures 275 276 292 311 9 Objects and Classes 9.1 ObjectOriented Programming 9.2 Inheritance 9.3 The Language 9.4 The Interpreter 9.5 A Typed Language 9.6 The Type Checker 325 326 329 334 336 352 358 Contents vii A For Further Reading 373 B The SLLGEN Parsing System B.1 Scanning B.2 Parsing B.3 Scanners and Parsers in SLLGEN 379 379 382 383 Bibliography 393 Index 401 Foreword This book brings you facetoface with the most fundamental idea in computer programming: The interpreter for a computer language is just another program. It sounds obvious, doesn’t it? But the implications are profound. If you are a computational theorist, the interpreter idea recalls Gödel’s discovery of the limitations of formal logical systems, Turing’s concept of a universal computer, and von Neumann’s basic notion of the storedprogram machine. If you are a programmer, mastering the idea of an interpreter is a source of great power. It provokes a real shift in mindset, a basic change in the way you think about programming. I did a lot of programming before I learned about interpreters, and I produced some substantial programs. One of them, for example, was a large dataentry and informationretrieval system written in PL/I. When I implemented my system, I viewed PL/I as a ﬁxed collection of rules established by some unapproachable group of language designers. I saw my job as not to modify these rules, or even to understand them deeply, but rather to pick through the (very) large manual, selecting this or that feature to use. The notion that there was some underlying structure to the way the language was organized, and that I might want to override some of the language designers’ decisions, never occurred to me. I didn’t know how to create embedded sublanguages to help organize my implementation, so the entire program seemed like a large, complex mosaic, where each piece had to be carefully shaped and ﬁtted into place, rather than a cluster of languages, where the pieces could be ﬂexibly combined. If you don’t understand interpreters, you can still write programs; you can even be a competent programmer. But you can’t be a master. x Foreword There are three reasons why as a programmer you should learn about interpreters. First, you will need at some point to implement interpreters, perhaps not interpreters for fullblown generalpurpose languages, but interpreters just the same. Almost every complex computer system with which people interact in ﬂexible ways—a computer drawing tool or an informationretrieval system, for example—includes some sort of interpreter that structures the interaction. These programs may include complex individual operations— shading a region on the display screen, or performing a database search— but the interpreter is the glue that lets you combine individual operations into useful patterns. Can you use the result of one operation as the input to another operation? Can you name a sequence of operations? Is the name local or global? Can you parameterize a sequence of operations, and give names to its inputs? And so on. No matter how complex and polished the individual operations are, it is often the quality of the glue that most directly determines the power of the system. It’s easy to ﬁnd examples of programs with good individual operations, but lousy glue; looking back on it, I can see that my PL/I database program certainly had lousy glue. Second, even programs that are not themselves interpreters have important interpreterlike pieces. Look inside a sophisticated computeraided design system and you’re likely to ﬁnd a geometric recognition language, a graphics interpreter, a rulebased control interpreter, and an objectoriented language interpreter all working together. One of the most powerful ways to structure a complex program is as a collection of languages, each of which provides a different perspective, a different way of working with the program elements. Choosing the right kind of language for the right purpose, and understanding the implementation tradeoffs involved: that’s what the study of interpreters is about. The third reason for learning about interpreters is that programming techniques that explicitly involve the structure of language are becoming increasingly important. Today’s concern with designing and manipulating class hierarchies in objectoriented systems is only one example of this trend. Perhaps this is an inevitable consequence of the fact that our programs are becoming increasingly complex—thinking more explicitly about languages may be our best tool for dealing with this complexity. Consider again the basic idea: the interpreter itself is just a program. But that program is written in some language, whose interpreter is itself just a program written in some language whose interpreter is itself . . . Perhaps the whole distinction between program and programming language is a misleading idea, and Foreword xi future programmers will see themselves not as writing programs in particular, but as creating new languages for each new application. Friedman and Wand have done a landmark job, and their book will change the landscape of programminglanguage courses. They don’t just tell you about interpreters; they show them to you. The core of the book is a tour de force sequence of interpreters starting with an abstract highlevel language and progressively making linguistic features explicit until we reach a state machine. You can actually run this code, study and modify it, and change the way these interpreters handle scoping, parameterpassing, control structure, etc. Having used interpreters to study the execution of languages, the authors show how the same ideas can be used to analyze programs without running them. In two new chapters, they show how to implement type checkers and inferencers, and how these features interact in modern objectoriented languages. Part of the reason for the appeal of this approach is that the authors have chosen a good tool—the Scheme language, which combines the uniform syntax and dataabstraction capabilities of Lisp with the lexical scoping and block structure of Algol. But a powerful tool becomes most powerful in the hands of masters. The sample interpreters in this book are outstanding models. Indeed, since they are runnable models, I’m sure that these interpreters and analyzers will ﬁnd themselves at the cores of many programming systems over the coming years. This is not an easy book. Mastery of interpreters does not come easily, and for good reason. The language designer is a further level removed from the end user than is the ordinary application programmer. In designing an application program, you think about the speciﬁc tasks to be performed, and consider what features to include. But in designing a language, you consider the various applications people might want to implement, and the ways in which they might implement them. Should your language have static or dynamic scope, or a mixture? Should it have inheritance? Should it pass parameters by reference or by value? Should continuations be explicit or implicit? It all depends on how you expect your language to be used, which kinds of programs should be easy to write, and which you can afford to make more difﬁcult. Also, interpreters really are subtle programs. A simple change to a line of code in an interpreter can make an enormous difference in the behavior of the resulting language. Don’t think that you can just skim these programs— very few people in the world can glance at a new interpreter and predict xii Foreword from that how it will behave even on relatively simple programs. So study these programs. Better yet, run them—this is working code. Try interpreting some simple expressions, then more complex ones. Add error messages. Modify the interpreters. Design your own variations. Try to really master these programs, not just get a vague feeling for how they work. If you do this, you will change your view of your programming, and your view of yourself as a programmer. You’ll come to see yourself as a designer of languages rather than only a user of languages, as a person who chooses the rules by which languages are put together, rather than only a follower of rules that other people have chosen. Postscript to the Third Edition The foreword above was written only seven years ago. Since then, information applications and services have entered the lives of people around the world in ways that hardly seemed possible in 1990. They are powered by an ever—growing collection of programming languages and programming frameworks—all erected on an everexpanding platform of interpreters. Do you want to create Web pages? In 1990, that meant formatting static text and graphics, in effect, creating a program to be run by browsers executing only a single “print” statement. Today’s dynamic Web pages make full use of scripting languages (another name for interpreted languages) like Javascript. The browser programs can be complex, and including asynchronous calls to a Web server that is typically running a program in a completely different programming framework possibly with a host of services, each with its own individual language. Or you might be creating a bot for enhancing the performance of your avatar in a massive online multiplayer game like World of Warcraft. In that case, you’re probably using a scripting language like Lua, possibly with an objectoriented extension to help in expressing classes of behaviors. Or maybe you’re programming a massive computing cluster to do indexing and searching on a global scale. If so, you might be writing your programs using the mapreduce paradigm of functional programming to relieve you of dealing explicitly with the details of how the individual processors are scheduled. Foreword xiii Or perhaps you’re developing new algorithms for sensor networks, and exploring the use of lazy evaluation to better deal with parallelism and data aggregation. Or exploring transformation systems like XSLT for controlling Web pages. Or designing frameworks for transforming and remixing multimedia streams. Or . . . So many new applications! So many new languages! So many new interpreters! As ever, novice programmers, even capable ones, can get along viewing each new framework individually, working within its ﬁxed set of rules. But creating new frameworks requires skills of the master: understanding the principles that run across languages, appreciating which language features are best suited for which type of application, and knowing how to craft the interpreters that bring these languages to life. These are the skills you will learn from this book. Hal Abelson Cambridge, Massachusetts September 2007 Preface Goal This book is an analytic study of programming languages. Our goal is to provide a deep, working understanding of the essential concepts of programming languages. These essentials have proved to be of enduring importance; they form a basis for understanding future developments in programming languages. Most of these essentials relate to the semantics, or meaning, of program elements. Such meanings reﬂect how program elements are interpreted as the program executes. Programs called interpreters provide the most direct, executable expression of program semantics. They process a program by directly analyzing an abstract representation of the program text. We therefore choose interpreters as our primary vehicle for expressing the semantics of programming language elements. The most interesting question about a program as object is, “What does it do?” The study of interpreters tells us this. Interpreters are critical because they reveal nuances of meaning, and are the direct path to more efﬁcient compilation and to other kinds of program analyses. Interpreters are also illustrative of a broad class of systems that transform information from one form to another based on syntax structure. Compilers, for example, transform programs into forms suitable for interpretation by hardware or virtual machines. Though general compilation techniques are beyond the scope of this book, we do develop several elementary program translation systems. These reﬂect forms of program analysis typical of compilation, such as control transformation, variable binding resolution, and type checking. xvi Preface The following are some of the strategies that distinguish our approach. 1. Each new concept is explained through the use of a small language. These languages are often cumulative: later languages may rely on the features of earlier ones. 2. Language processors such as interpreters and type checkers are used to explain the behavior of programs in a given language. They express language design decisions in a manner that is both formal (unambiguous and complete) and executable. 3. When appropriate, we use interfaces and speciﬁcations to create data abstractions. In this way, we can change data representation without changing programs. We use this to investigate alternative implementation strategies. 4. Our language processors are written both at the very high level needed to produce a concise and comprehensible view of semantics and at the much lower level needed to understand implementation strategies. 5. We show how simple algebraic manipulation can be used to predict the behavior of programs and to derive their properties. In general, however, we make little use of mathematical notation, preferring instead to study the behavior of programs that constitute the implementations of our languages. 6. The text explains the key concepts, while the exercises explore alternative designs and other issues. For example, the text deals with static binding, but dynamic binding is discussed in the exercises. One thread of exercises applies the concept of lexical addressing to the various languages developed in the book. We provide several views of programming languages using widely varying levels of abstraction. Frequently our interpreters provide a very highlevel view that expresses language semantics in a very concise fashion, not far from that of formal mathematical semantics. At the other extreme, we demonstrate how programs may be transformed into a very lowlevel form characteristic of assembly language. By accomplishing this transformation in small stages, we maintain a clear connection between the highlevel and lowlevel views. Preface xvii We have made some signiﬁcant changes to this edition. We have included informal contracts with all nontrivial deﬁnitions. This has the effect of clarifying the chosen abstractions. In addition, the chapter on modules is completely new. To make implementations simpler, the source language for chapters 3, 4, 5, 7, and 8 assumes that exactly one argument can be passed to a function; we have included exercises that support multiargument procedures. Chapter 6 is completely new, since we have opted for a ﬁrstorder compositional continuationpassingstyle transform rather than a relational one. Also, because of the nature of tailform expressions, we use multiargument procedures here, and in the objects and classes chapter, we do the same, though there it is not so necessary. Every chapter has been revised and many new exercises have been added. Organization The ﬁrst two chapters provide the foundations for a careful study of programming languages. Chapter 1 emphasizes the connection between inductive data speciﬁcation and recursive programming and introduces several notions related to the scope of variables. Chapter 2 introduces a data type facility. This leads to a discussion of data abstraction and examples of representational transformations of the sort used in subsequent chapters. Chapter 3 uses these foundations to describe the behavior of programming languages. It introduces interpreters as mechanisms for explaining the runtime behavior of languages and develops an interpreter for a simple, lexically scoped language with ﬁrstclass procedures and recursion. This interpreter is the basis for much of the material in the remainder of the book. The chapter ends by giving a thorough treatment of a language that uses indices in place of variables and as a result variable lookup can be via a list reference. Chapter 4 introduces a new component, the state, which maps locations to values. Once this is added, we can look at various questions of representation. In addition, it permits us to explore callbyreference, callbyname, and callbyneed parameterpassing mechanisms. Chapter 5 rewrites our basic interpreter in continuationpassing style. The control structure that is needed to run the interpreter thereby shifts from recursion to iteration. This exposes the control mechanisms of the interpreted language, and strengthens one’s intuition for control issues in general. It also allows us to extend the language with trampolining, exceptionhandling, and multithreading mechanisms. xviii Preface Chapter 6 is the companion to the previous chapter. There we show how to transform our familiar interpreter into continuationpassing style; here we show how to accomplish this for a much larger class of programs. Continuationpassing style is a powerful programming tool, for it allows any sequential control mechanism to be implemented in almost any language. The algorithm is also an example of an abstractly speciﬁed sourcetosource program transformation. Chapter 7 turns the language of chapter 3 into a typed language. First we implement a type checker. Then we show how the types in a program can be deduced by a uniﬁcationbased type inference algorithm. Chapter 8 builds typed modules relying heavily on an understanding of the previous chapter. Modules allow us to build and enforce abstraction boundaries, and they offer a new kind of scoping. Chapter 9 presents the basic concepts of objectoriented languages, centered on classes. We ﬁrst develop an efﬁcient runtime architecture, which is used as the basis for the material in the second part of the chapter. The second part combines the ideas of the type checker of chapter 7 with those of the objectoriented language of the ﬁrst part, leading to a conventional typed objectoriented language. This requires introducing new concepts including interfaces, abstract methods, and casting. For Further Reading explains where each of the ideas in the book has come from. This is a personal walkthrough allowing the reader the opportunity to visit each topic from the original paper, though in some cases, we have just chosen an accessible source. Finally, appendix B describes our SLLGEN parsing system. The dependencies of the various chapters are shown in the ﬁgure below. Preface xix Usage This material has been used in both undergraduate and graduate courses. Also, it has been used in continuing education courses for professional programmers. We assume background in data structures and experience both in a procedural language such as C, C++, or Java, and in Scheme, ML, Python, or Haskell. Exercises are a vital part of the text and are scattered throughout. They range in difﬁculty from being trivial if related material is understood [], to requiring many hours of thought and programming work [ ]. A great deal of material of applied, historical, and theoretical interest resides within them. We recommend that each exercise be read and some thought be given as to how to solve it. Although we write our program interpretation and transformation systems in Scheme, any language that supports both ﬁrstclass procedures and assignment (ML, Common Lisp, Python, Ruby, etc.) is adequate for working the exercises. Exercise 0.1 [] We often use phrases like “some languages have property X.” For each such phrase, ﬁnd one or more languages that have the property and one or more languages that do not have the property. Feel free to ferret out this information from any descriptive book on programming languages (say Scott (2005), Sebesta (2007), or Pratt & Zelkowitz (2001)). This is a handson book: everything discussed in the book may be implemented within the limits of a typical university course. Because the abstraction facilities of functional programming languages are especially suited to this sort of programming, we can write substantial languageprocessing systems that are nevertheless compact enough that one can understand and manipulate them with reasonable effort. The web site, available through the publisher, includes complete Scheme code for all of the interpreters and analyzers in this book. The code is written in PLT Scheme. We chose this Scheme implementation because its module system and programming environment provide a substantial advantage to the student. The code is largely R5 RScompatible, and should be easily portable to any fullfeatured Scheme implementation. Acknowledgments We are indebted to countless colleagues and students who used and critiqued the ﬁrst two editions of this book and provided invaluable assistance in the long gestation of this third edition. We are especially grateful for the contributions of the following individuals, to whom we offer a special word of thanks. Olivier Danvy encouraged our consideration of a ﬁrstorder compositional continuationpassing algorithm and proposed some interesting exercises. Matthias Felleisen’s keen analysis has improved the design of several chapters. Amr Sabry made many useful suggestions and found at least one extremely subtle bug in a draft of chapter 9. Benjamin Pierce offered a number of insightful observations after teaching from the ﬁrst edition, almost all of which we have incorporated. Gary Leavens provided exceptionally thorough and valuable comments on early drafts of the second edition, including a large number of detailed suggestions for change. Stephanie Weirich found a subtle bug in the type inference code of the second edition of chapter 7. Ryan Newton, in addition to reading a draft of the second edition, assumed the onerous task of suggesting a difﬁculty level for each exercise for that edition. Chungchieh Shan taught from an early draft of the third edition and provided copious and useful comments. Kevin Millikin, Arthur Lee, Roger Kirchner, Max Hailperin, and Erik Hilsdale all used early drafts of the second edition. Will Clinger, Will Byrd, Joe Near, and Kyle Blocher all used drafts of this edition. Their comments have been extremely valuable. Ron Garcia, Matthew Flatt, Shriram Krishnamurthi, Steve Ganz, Gregor Kiczales, Marlene Miller, Galen Williamson, Dipanwita Sarkar, Steven Bogaerts, Albert Rossi, Craig Citro, Christopher Dutchyn, Jeremy Siek, and Neil Ching also provided careful reading and useful comments. xxii Acknowledgments Several people deserve special thanks for assisting us with this book. We want to thank Neil Ching for developing the index. Jonathan Sobel and Erik Hilsdale built several prototype implementations and contributed many ideas as we experimented with the design of the definedatatype and cases syntactic extensions. The Programming Language Team, and especially Matthias Felleisen, Matthew Flatt, Robby Findler, and Shriram Krishnamurthi, were very helpful in providing compatibility with their DrScheme system. Kent Dybvig developed the exceptionally efﬁcient and robust Chez Scheme implementation, which the authors have used for decades. Will Byrd has provided invaluable assistance during the entire process. Matthias Felleisen strongly urged us to adopt compatibility with DrScheme’s module system, which is evident in the implementation that can be found at http://mitpress.mit.edu/eopl3. Some have earned special mention for their thoughtfulness and concern for our wellbeing. George Springer and Larry Finkelstein have each supplied invaluable support. Bob Prior, our wonderful editor at MIT Press, deserves special thanks for his encouragement in getting us to attack the writing of this edition. Ada Brunstein, Bob’s successor, also deserves thanks for making our transition to a new editor so smoothly. Indiana University’s School of Informatics and Northeastern University’s College of Computer and Information Science have created an environment that has allowed us to undertake this project. Mary Friedman’s gracious hosting of several weeklong writing sessions did much to accelerate our progress. We want to thank Christopher T. Haynes for his collaboration on the ﬁrst two editions. Unfortunately, his interests have shifted elsewhere, and he has not continued with us on this edition. Finally, we are most grateful to our families for tolerating our passion for working on the book. Thank you Rob, Shannon, Rachel, Sara, and Mary; and thank you Rebecca and Joshua, Jennifer and Stephen, Joshua and Georgia, and Barbara. This edition has been in the works for a while and we have likely overlooked someone who has helped along the way. We regret any oversight. You see this written in books all the time and wonder why anyone would write it. Of course, you regret any oversight. But, when you have an army of helpers (it takes a village), you really feel a sense of obligation not to forget anyone. So, if you were overlooked, we are truly sorry. — D.P.F. and M.W. 1 Inductive Sets of Data This chapter introduces the basic programming tools we will need to write interpreters, checkers and similar programs that form the heart of a programming language processor. Because the syntax of a program in a language is usually a nested or treelike structure, recursion will be at the core of our techniques. Section 1.1 and section 1.2 introduce methods for inductively specifying data structures and show how such speciﬁcations may be used to guide the construction of recursive programs. Section 1.3 shows how to extend these techniques to more complex problems. The chapter concludes with an extensive set of exercises. These exercises are the heart of this chapter. They provide experience that is essential for mastering the technique of recursive programming upon which the rest of this book is based. 1.1 Recursively Speciﬁed Data When writing code for a procedure, we must know precisely what kinds of values may occur as arguments to the procedure, and what kinds of values are legal for the procedure to return. Often these sets of values are complex. In this section we introduce formal techniques for specifying sets of values. 1.1.1 Inductive Speciﬁcation Inductive speciﬁcation is a powerful method of specifying a set of values. To illustrate this method, we use it to describe a certain subset S of the natural numbers N = {0, 1, 2, . . .}. 2 1 Inductive Sets of Data Deﬁnition 1.1.1 A natural number n is in S if and only if 1. n = 0, or 2. n − 3 ∈ S. Let us see how we can use this deﬁnition to determine what natural numbers are in S. We know that 0 ∈ S. Therefore 3 ∈ S, since (3 − 3) = 0 and 0 ∈ S. Similarly 6 ∈ S, since (6 − 3) = 3 and 3 ∈ S. Continuing in this way, we can conclude that all multiples of 3 are in S. What about other natural numbers? Is 1 ∈ S? We know that 1 = 0, so the ﬁrst condition is not satisﬁed. Furthermore, (1 − 3) = −2, which is not a natural number and thus is not a member of S. Therefore the second condition is not satisﬁed. Since 1 satisﬁes neither condition, 1 ∈ S. Similarly, 2 ∈ S. What about 4? 4 ∈ S only if 1 ∈ S. But 1 ∈ S, so 4 ∈ S, as well. Similarly, we can conclude that if n is a natural number and is not a multiple of 3, then n ∈ S. From this argument, we conclude that S is the set of natural numbers that are multiples of 3. We can use this deﬁnition to write a procedure to decide whether a natural number n is in S. inS? : N → Bool usage: (inS? n) = #t if n is in S, #f otherwise (define inS? (lambda (n) (if (zero? n) #t (if (>= ( n 3) 0) (inS? ( n 3)) #f)))) Here we have written a recursive procedure in Scheme that follows the deﬁnition. The notation inS? : N → Bool is a comment, called the contract for this procedure. It means that inS? is intended to be a procedure that takes a natural number and produces a boolean. Such comments are helpful for reading and writing code. To determine whether n ∈ S, we ﬁrst ask whether n = 0. If it is, then the answer is true. Otherwise we need to see whether n − 3 ∈ S. To do this, we ﬁrst check to see whether (n − 3) ≥ 0. If it is, we then can use our procedure to see whether it is in S. If it is not, then n cannot be in S. 3 1.1 Recursively Speciﬁed Data Here is an alternative way of writing down the deﬁnition of S. Deﬁnition 1.1.2 Deﬁne the set S to be the smallest set contained in N and satisfying the following two properties: 1. 0 ∈ S, and 2. if n ∈ S, then n + 3 ∈ S. A “smallest set” is the one that satisﬁes properties 1 and 2 and that is a subset of any other set satisfying properties 1 and 2. It is easy to see that there can be only one such set: if S1 and S2 both satisfy properties 1 and 2, and both are smallest, then S1 ⊆ S2 (since S1 is smallest), and S2 ⊆ S1 (since S2 is smallest), hence S1 = S2 . We need this extra condition, because otherwise there are many sets that satisfy the remaining two conditions (see exercise 1.3). Here is yet another way of writing the deﬁnition: 0∈S n∈S (n + 3) ∈ S This is simply a shorthand notation for the preceding version of the definition. Each entry is called a rule of inference, or just a rule; the horizontal line is read as an “ifthen.” The part above the line is called the hypothesis or the antecedent; the part below the line is called the conclusion or the consequent. When there are two or more hypotheses listed, they are connected by an implicit “and” (see deﬁnition 1.1.5). A rule with no hypotheses is called an axiom. We often write an axiom without the horizontal line, like 0∈S The rules are interpreted as saying that a natural number n is in S if and only if the statement “n ∈ S” can be derived from the axioms by using the rules of inference ﬁnitely many times. This interpretation automatically makes S the smallest set that is closed under the rules. These deﬁnitions all say the same thing. We call the ﬁrst version a topdown deﬁnition, the second version a bottomup deﬁnition, and the third version a rulesofinference version. 4 1 Inductive Sets of Data Let us see how this works on some other examples. Deﬁnition 1.1.3 (list of integers, topdown) A Scheme list is a list of integers if and only if either 1. it is the empty list, or 2. it is a pair whose car is an integer and whose cdr is a list of integers. We use Int to denote the set of all integers, and ListofInt to denote the set of lists of integers. Deﬁnition 1.1.4 (list of integers, bottomup) The set ListofInt is the smallest set of Scheme lists satisfying the following two properties: 1. () ∈ ListofInt, and 2. if n ∈ Int and l ∈ ListofInt, then (n . l) ∈ ListofInt. Here we use the inﬁx “.” to denote the result of the cons operation in Scheme. The phrase (n . l) denotes a Scheme pair whose car is n and whose cdr is l. Deﬁnition 1.1.5 (list of integers, rules of inference) () ∈ ListofInt n ∈ Int l ∈ ListofInt (n . l) ∈ ListofInt These three deﬁnitions are equivalent. We can show how to use them to generate some elements of ListofInt. 1. () is a list of integers, because of property 1 of deﬁnition 1.1.4 or the ﬁrst rule of deﬁnition 1.1.5. 2. (14 . ()) is a list of integers, because of property 2 of deﬁnition 1.1.4, since 14 is an integer and () is a list of integers. We can also write this as an instance of the second rule for ListofInt. 14 ∈ Int () ∈ ListofInt (14 . ()) ∈ ListofInt 5 1.1 Recursively Speciﬁed Data 3. (3 . (14 . ())) is a list of integers, because of property 2, since 3 is an integer and (14 . ()) is a list of integers. We can write this as another instance of the second rule for ListofInt. 3 ∈ Int (14 . ()) ∈ ListofInt (3 . (14 . ())) ∈ ListofInt 4. (7 . (3 . (14 . ()))) is a list of integers, because of property 2, since 7 is a integer and (3 . (14 . ())) is a list of integers. Once more we can write this as an instance of the second rule for ListofInt. 7 ∈ Int (3 . (14 . ())) ∈ ListofInt (7 . (3 . (14 . ()))) ∈ ListofInt 5. Nothing is a list of integers unless it is built in this fashion. Converting from dot notation to list notation, we see that (), (14), (3 14), and (7 3 14) are all members of ListofInt. We can also combine the rules to get a picture of the entire chain of reasoning that shows that (7 . (3 . (14 . ()))) ∈ ListofInt. The treelike picture below is called a derivation or deduction tree. 14 ∈ N 3∈N 7 ∈ N () ∈ ListofInt (14 . ()) ∈ ListofInt (3 . (14 . ())) ∈ ListofInt (7 . (3 . (14 . ()))) ∈ ListofInt Exercise 1.1 [] Write inductive deﬁnitions of the following sets. Write each deﬁnition in all three styles (topdown, bottomup, and rules of inference). Using your rules, show the derivation of some sample elements of each set. 1. {3n + 2  n ∈ N } 2. {2n + 3m + 1  n , m ∈ N } 3. {(n , 2n + 1)  n ∈ N } 4. {(n , n2)  n ∈ N } Do not mention squaring in your rules. As a hint, remember the equation (n + 1)2 = n2 + 2n + 1. Exercise 1.2 [ ] What sets are deﬁned by the following pairs of rules? Explain why. 1. (0, 1) ∈ S (n , k) ∈ S (n + 1, k + 7) ∈ S 6 1 Inductive Sets of Data 2. (0, 1) ∈ S 3. (0, 0, 1) ∈ S (n , k) ∈ S (n + 1, 2k) ∈ S (n , i , j) ∈ S (n + 1, j, i + j) ∈ S 4. [ ] (0, 1, 0) ∈ S (n , i , j) ∈ S (n + 1, i + 2, i + j) ∈ S Exercise 1.3 [] Find a set T of natural numbers such that 0 ∈ T, and whenever n ∈ T, then n + 3 ∈ T, but T = S, where S is the set deﬁned in deﬁnition 1.1.2. 1.1.2 Deﬁning Sets Using Grammars The previous examples have been fairly straightforward, but it is easy to imagine how the process of describing more complex data types becomes quite cumbersome. To help with this, we show how to specify sets with grammars. Grammars are typically used to specify sets of strings, but we can use them to deﬁne sets of values as well. For example, we can deﬁne the set ListofInt by the grammar ListofInt ::= () ListofInt ::= (Int . ListofInt) Here we have two rules corresponding to the two properties in deﬁnition 1.1.4 above. The ﬁrst rule says that the empty list is in ListofInt, and the second says that if n is in Int and l is in ListofInt, then (n . l) is in ListofInt. This set of rules is called a grammar. Let us look at the pieces of this deﬁnition. In this deﬁnition we have • Nonterminal Symbols. These are the names of the sets being deﬁned. In this case there is only one such set, but in general, there might be several sets being deﬁned. These sets are sometimes called syntactic categories. We will use the convention that nonterminals and sets have names that are capitalized, but we will use lowercase names when referring to their elements in prose. This is simpler than it sounds. For example, Expression is a nonterminal, but we will write e ∈ Expression or “e is an expression.” Another common convention, called BackusNaur Form or BNF, is to surround the word with angle brackets, e.g. expression. • Terminal Symbols. These are the characters in the external representation, in this case ., (, and ). We typically write these using a typewriter font, e.g. lambda. 7 1.1 Recursively Speciﬁed Data • Productions. The rules are called productions. Each production has a lefthand side, which is a nonterminal symbol, and a righthand side, which consists of terminal and nonterminal symbols. The left and righthand sides are usually separated by the symbol ::=, read is or can be. The righthand side speciﬁes a method for constructing members of the syntactic category in terms of other syntactic categories and terminal symbols, such as the left parenthesis, right parenthesis, and the period. Often some syntactic categories mentioned in a production are left undeﬁned when their meaning is sufﬁciently clear from context, such as Int. Grammars are often written using some notational shortcuts. It is common to omit the lefthand side of a production when it is the same as the lefthand side of the preceding production. Using this convention our example would be written as ListofInt ::= () ::= (Int . ListofInt) One can also write a set of rules for a single syntactic category by writing the lefthand side and ::= just once, followed by all the righthand sides separated by the special symbol “  ” (vertical bar, read or). The grammar for ListofInt could be written using “  ” as ListofInt ::= ()  (Int . ListofInt) Another shortcut is the Kleene star, expressed by the notation {. . .}∗ . When this appears in a righthand side, it indicates a sequence of any number of instances of whatever appears between the braces. Using the Kleene star, the deﬁnition of ListofInt is simply ListofInt ::= ({Int}∗ ) This includes the possibility of no instances at all. If there are zero instances, we get the empty string. A variant of the star notation is Kleene plus {. . .}+ , which indicates a sequence of one or more instances. Substituting + for ∗ in the example above would deﬁne the syntactic category of nonempty lists of integers. Still another variant of the star notation is the separated list notation. For example, we write {Int}∗(c) to denote a sequence of any number of instances of the nonterminal Int, separated by the nonempty character sequence c. This includes the possibility of no instances at all. If there are zero instances, we get the empty string. For example, {Int}∗(,) includes the strings 8 1 Inductive Sets of Data 8 14, 12 7, 3, 14, 16 and {Int}∗(;) includes the strings 8 14; 12 7; 3; 14; 16 These notational shortcuts are not essential. It is always possible to rewrite the grammar without them. If a set is speciﬁed by a grammar, a syntactic derivation may be used to show that a given data value is a member of the set. Such a derivation starts with the nonterminal corresponding to the set. At each step, indicated by an arrow ⇒, a nonterminal is replaced by the righthand side of a corresponding rule, or with a known member of its syntactic class if the class was left undeﬁned. For example, the previous demonstration that (14 . ()) is a list of integers may be formalized with the syntactic derivation ListofInt ⇒ (Int . ListofInt) ⇒ (14 . ListofInt) ⇒ (14 . ()) The order in which nonterminals are replaced does not matter. Thus, here is another derivation of (14 . ()). ListofInt ⇒ (Int . ListofInt) ⇒ (Int . ()) ⇒ (14 . ()) Exercise 1.4 [] Write a derivation from ListofInt to (7 . (3 . (14 . ()))). Let us consider the deﬁnitions of some other useful sets. 1. Many symbol manipulation procedures are designed to operate on lists that contain only symbols and other similarly restricted lists. We call these lists slists, deﬁned as follows: Deﬁnition 1.1.6 (slist, sexp) Slist ::= ({Sexp}∗ ) Sexp ::= Symbol  Slist 1.1 Recursively Speciﬁed Data 9 An slist is a list of sexps, and an sexp is either an slist or a symbol. Here are some slists. (a b c) (an (((slist)) (with () lots) ((of) nesting))) We may occasionally use an expanded deﬁnition of slist with integers allowed, as well as symbols. 2. A binary tree with numeric leaves and interior nodes labeled with symbols may be represented using threeelement lists for the interior nodes by the grammar: Deﬁnition 1.1.7 (binary tree) Bintree ::= Int  (Symbol Bintree Bintree) Here are some examples of such trees: 1 2 (foo 1 (bar 1 (baz (bar (biz 2) (foo 1 2)) 1 (foo 1 2)) 4 5)) 3. The lambda calculus is a simple language that is often used to study the theory of programming languages. This language consists only of variable references, procedures that take a single argument, and procedure calls. We can deﬁne it with the grammar: Deﬁnition 1.1.8 (lambda expression) LcExp ::= Identiﬁer ::= (lambda (Identiﬁer) LcExp) ::= (LcExp LcExp) where an identiﬁer is any symbol other than lambda. 10 1 Inductive Sets of Data The identiﬁer in the second production is the name of a variable in the body of the lambda expression. This variable is called the bound variable of the expression, because it binds or captures any occurrences of the variable in the body. Any occurrence of that variable in the body refers to this one. To see how this works, consider the lambda calculus extended with arithmetic operators. In that language, (lambda (x) (+ x 5)) is an expression in which x is the bound variable. This expression describes a procedure that adds 5 to its argument. Therefore, in ((lambda (x) (+ x 5)) ( x 7)) the last occurrence of x does not refer to the x that is bound in the lambda expression. We discuss this in section 1.2.4, where we introduce occursfree?. This grammar deﬁnes the elements of LcExp as Scheme values, so it becomes easy to write programs that manipulate them. These grammars are said to be contextfree because a rule deﬁning a given syntactic category may be applied in any context that makes reference to that syntactic category. Sometimes this is not restrictive enough. Consider binary search trees. A node in a binary search tree is either empty or contains an integer and two subtrees Binarysearchtree ::= ()  (Int Binarysearchtree Binarysearchtree) This correctly describes the structure of each node but ignores an important fact about binary search trees: all the keys in the left subtree are less than (or equal to) the key in the current node, and all the keys in the right subtree are greater than the key in the current node. Because of this additional constraint, not every syntactic derivation from Binarysearchtree leads to a correct binary search tree. To determine whether a particular production can be applied in a particular syntactic derivation, we have to look at the context in which the production is applied. Such constraints are called contextsensitive constraints or invariants. 1.1 Recursively Speciﬁed Data 11 Contextsensitive constraints also arise when specifying the syntax of programming languages. For instance, in many languages every variable must be declared before it is used. This constraint on the use of variables is sensitive to the context of their use. Formal methods can be used to specify contextsensitive constraints, but these methods are far more complicated than the ones we consider in this chapter. In practice, the usual approach is ﬁrst to specify a contextfree grammar. Contextsensitive constraints are then added using other methods. We show an example of such techniques in chapter 7. 1.1.3 Induction Having described sets inductively, we can use the inductive deﬁnitions in two ways: to prove theorems about members of the set and to write programs that manipulate them. Here we present an example of such a proof; writing the programs is the subject of the next section. Theorem 1.1.1 Let t be a binary tree, as deﬁned in deﬁnition 1.1.7. Then t contains an odd number of nodes. Proof: The proof is by induction on the size of t, where we take the size of t to be the number of nodes in t. The induction hypothesis, IH(k), is that any tree of size ≤ k has an odd number of nodes. We follow the usual prescription for an inductive proof: we ﬁrst prove that IH(0) is true, and we then prove that whenever k is an integer such that IH is true for k, then IH is true for k + 1 also. 1. There are no trees with 0 nodes, so IH(0) holds trivially. 2. Let k be an integer such that IH(k) holds, that is, any tree with ≤ k nodes actually has an odd number of nodes. We need to show that IH(k + 1) holds as well: that any tree with ≤ k + 1 nodes has an odd number of nodes. If t has ≤ k + 1 nodes, there are exactly two possibilities according to the deﬁnition of a binary tree: (a) t could be of the form n, where n is an integer. In this case, t has exactly one node, and one is odd. (b) t could be of the form (sym t1 t2 ), where sym is a symbol and t1 and t2 are trees. Now t1 and t2 must have fewer nodes than t. Since t has ≤ k + 1 nodes, t1 and t2 must have ≤ k nodes. Therefore they are covered 12 1 Inductive Sets of Data by IH(k), and they must each have an odd number of nodes, say 2n1 + 1 and 2n2 + 1 nodes, respectively. Hence the total number of nodes in the tree, counting the two subtrees and the root, is (2n1 + 1) + (2n2 + 1) + 1 = 2(n1 + n2 + 1) + 1 which is once again odd. This completes the proof of the claim that IH(k + 1) holds and therefore completes the induction. The key to the proof is that the substructures of a tree t are always smaller than t itself. This pattern of proof is called structural induction. Proof by Structural Induction To prove that a proposition IH(s) is true for all structures s, prove the following: 1. IH is true on simple structures (those without substructures). 2. If IH is true on the substructures of s, then it is true on s itself. Exercise 1.5 [ ] Prove that if e ∈ LcExp, then there are the same number of left and right parentheses in e. 1.2 Deriving Recursive Programs We have used the method of inductive deﬁnition to characterize complicated sets. We have seen that we can analyze an element of an inductively deﬁned set to see how it is built from smaller elements of the set. We have used this idea to write a procedure inS? to decide whether a natural number is in the set S. We now use the same idea to deﬁne more general procedures that compute on inductively deﬁned sets. Recursive procedures rely on an important principle: The SmallerSubproblem Principle If we can reduce a problem to a smaller subproblem, we can call the procedure that solves the problem to solve the subproblem. 1.2 Deriving Recursive Programs 13 The solution returned for the subproblem may then be used to solve the original problem. This works because each time we call the procedure, it is called with a smaller problem, until eventually it is called with a problem that can be solved directly, without another call to itself. We illustrate this idea with a sequence of examples. 1.2.1 listlength The standard Scheme procedure length determines the number of elements in a list. > (length ’(a b c)) 3 > (length ’((x) ())) 2 Let us write our own procedure, called listlength, that does the same thing. We begin by writing down the contract for the procedure. The contract speciﬁes the sets of possible arguments and possible return values for the procedure. The contract also may include the intended usage or behavior of the procedure. This helps us keep track of our intentions both as we write and afterwards. In code, this would be a comment; we typeset it for readability. listlength : List → Int usage: (listlength l) = the length of l (define listlength (lambda (lst) ...)) We can deﬁne the set of lists by List ::= ()  (Scheme value . List) Therefore we consider each possibility for a list. If the list is empty, then its length is 0. listlength : List → Int usage: (listlength l) = the length of l (define listlength (lambda (lst) (if (null? lst) 0 ...))) 14 1 Inductive Sets of Data If a list is nonempty, then its length is one more than the length of its cdr. This gives us a complete deﬁnition. listlength : List → Int usage: (listlength l) = the length of l (define listlength (lambda (lst) (if (null? lst) 0 (+ 1 (listlength (cdr lst)))))) We can watch listlength compute by using its deﬁnition. (listlength ’(a (b c) d)) = (+ 1 (listlength ’((b c) d))) = (+ 1 (+ 1 (listlength ’(d)))) = (+ 1 (+ 1 (+ 1 (listlength ’())))) = (+ 1 (+ 1 (+ 1 0))) = 3 1.2.2 nthelement The standard Scheme procedure listref takes a list lst and a zerobased index n and returns element number n of lst. > (listref ’(a b c) 1) b Let us write our own procedure, called nthelement, that does the same thing. Again we use the deﬁnition of List above. What should (nthelement lst n) return when lst is empty? In this case, (nthelement lst n) is asking for an element of an empty list, so we report an error. What should (nthelement lst n) return when lst is nonempty? The answer depends on n. If n = 0, the answer is simply the car of lst. What should (nthelement lst n) return when lst is nonempty and n = 0? In this case, the answer is the (n − 1)st element of the cdr of lst. Since n ∈ N and n = 0 , we know that n − 1 must also be in N, so we can ﬁnd the (n − 1)st element by recursively calling nthelement. 15 1.2 Deriving Recursive Programs This leads us to the deﬁnition nthelement : List × Int → SchemeVal usage: (nthelement lst n) = the nth element of lst (define nthelement (lambda (lst n) (if (null? lst) (reportlisttooshort n) (if (zero? n) (car lst) (nthelement (cdr lst) ( n 1)))))) (define reportlisttooshort (lambda (n) (eopl:error ’nthelement "List too short by ~s elements.~%" (+ n 1)))) Here the notation nthelement : List × Int → SchemeVal means that nthelement is a procedure that takes two arguments, a list and an integer, and returns a Scheme value. This is the same notation that is used in mathematics when we write f : A × B → C. The procedure reportlisttooshort reports an error condition by calling eopl:error. The procedure eopl:error aborts the computation. Its ﬁrst argument is a symbol that allows the error message to identify the procedure that called eopl:error. The second argument is a string that is then printed in the error message. There must then be an additional argument for each instance of the character sequence ~s in the string. The values of these arguments are printed in place of the corresponding ~s when the string is printed. A ~% is treated as a new line. After the error message is printed, the computation is aborted. This procedure eopl:error is not part of standard Scheme, but most implementations of Scheme provide such a facility. We use procedures named report to report errors in a similar fashion throughout the book. Watch how nthelement computes its answer: = = = = (nthelement ’(a b c d (nthelement ’(b c d (nthelement ’(c d (nthelement ’(d d e) e) e) e) 3) 2) 1) 0) Here nthelement recurs on shorter and shorter lists, and on smaller and smaller numbers. 16 1 Inductive Sets of Data If error checking were omitted, we would have to rely on car and cdr to complain about being passed the empty list, but their error messages would be less helpful. For example, if we received an error message from car, we might have to look for uses of car throughout our program. Exercise 1.6 [] If we reversed the order of the tests in nthelement, what would go wrong? Exercise 1.7 [ ] The error message from nthelement is uninformative. Rewrite nthelement so that it produces a more informative error message, such as “(a b c) does not have 8 elements.” 1.2.3 removefirst The procedure removefirst should take two arguments: a symbol, s, and a list of symbols, los. It should return a list with the same elements arranged in the same order as los, except that the ﬁrst occurrence of the symbol s is removed. If there is no occurrence of s in los, then los is returned. > (removefirst (b c) > (removefirst (e f g) > (removefirst (c1 c1 a4) > (removefirst () ’a ’(a b c)) ’b ’(e f g)) ’a4 ’(c1 a4 c1 a4)) ’x ’()) Before we start writing the deﬁnition of this procedure, we must complete the problem speciﬁcation by deﬁning the set ListofSymbol of lists of symbols. Unlike the slists introduced in the last section, these lists of symbols do not contain sublists. ListofSymbol ::= ()  (Symbol . ListofSymbol) A list of symbols is either the empty list or a list whose car is a symbol and whose cdr is a list of symbols. 1.2 Deriving Recursive Programs 17 If the list is empty, there are no occurrences of s to remove, so the answer is the empty list. removeﬁrst : Sym × Listof(Sym) → Listof(Sym) usage: (removefirst s los) returns a list with the same elements arranged in the same order as los, except that the first occurrence of the symbol s is removed. (define removefirst (lambda (s los) (if (null? los) ’() ...))) Here we have written the contract with Listof(Sym) instead of ListofSymbol. This notation will allow us to avoid many deﬁnitions like the ones above. If los is nonempty, is there some case where we can determine the answer immediately? If the ﬁrst element of los is s, say los = (s s1 . . . sn−1 ), the ﬁrst occurrence of s is as the ﬁrst element of los. So the result of removing it is just (s1 . . . sn−1 ). removeﬁrst : Sym × Listof(Sym) → Listof(Sym) (define removefirst (lambda (s los) (if (null? los) ’() (if (eqv? (car los) s) (cdr los) ...)))) If the ﬁrst element of los is not s, say los = (s0 s1 . . . sn−1 ), then we know that s0 is not the ﬁrst occurrence of s. Therefore the ﬁrst element of the answer must be s0 , which is the value of the expression (car los). Furthermore, the ﬁrst occurrence of s in los must be its ﬁrst occurrence in (s1 . . . sn−1 ). So the rest of the answer must be the result of removing the ﬁrst occurrence of s from the cdr of los. Since the cdr of los is shorter than los, we may recursively call removefirst to remove s from the cdr of los. So the cdr of the answer can be obtained as the value of (removefirst s (cdr los)). Since we know how to ﬁnd the car and cdr of the answer, we can ﬁnd the whole answer by combining them with cons, using the expression (cons (car los) (removefirst s (cdr los))). With this, the complete deﬁnition of removefirst becomes 18 1 Inductive Sets of Data removeﬁrst : Sym × Listof(Sym) → Listof(Sym) (define removefirst (lambda (s los) (if (null? los) ’() (if (eqv? (car los) s) (cdr los) (cons (car los) (removefirst s (cdr los))))))) Exercise 1.8 [] In the deﬁnition of removefirst, if the last line were replaced by (removefirst s (cdr los)), what function would the resulting procedure compute? Give the contract, including the usage statement, for the revised procedure. Exercise 1.9 [ ] Deﬁne remove, which is like removefirst, except that it removes all occurrences of a given symbol from a list of symbols, not just the ﬁrst. 1.2.4 occursfree? The procedure occursfree? should take a variable var, represented as a Scheme symbol, and a lambdacalculus expression exp as deﬁned in deﬁnition 1.1.8, and determine whether or not var occurs free in exp. We say that a variable occurs free in an expression exp if it has some occurrence in exp that is not inside some lambda binding of the same variable. For example, > (occursfree? #t > (occursfree? #f > (occursfree? #f > (occursfree? #t > (occursfree? #t > (occursfree? #t ’x ’x) ’x ’y) ’x ’(lambda (x) (x y))) ’x ’(lambda (y) (x y))) ’x ’((lambda (x) x) (x y))) ’x ’(lambda (y) (lambda (z) (x (y z))))) We can solve this problem by following the grammar for lambdacalculus expressions LcExp ::= Identiﬁer ::= (lambda (Identiﬁer) LcExp) ::= (LcExp LcExp) 1.2 Deriving Recursive Programs 19 We can summarize these cases in the rules: • If the expression e is a variable, then the variable x occurs free in e if and only if x is the same as e. • If the expression e is of the form (lambda (y) e ), then the variable x occurs free in e if and only if y is different from x and x occurs free in e . • If the expression e is of the form (e1 e2 ), then x occurs free in e if and only if it occurs free in e1 or e2 . Here, we use “or” to mean inclusive or, meaning that this includes the possibility that x occurs free in both e1 and e2 . We will generally use “or” in this sense. You should convince yourself that these rules capture the notion of occurring “not inside a lambdabinding of x.” Exercise 1.10 [] We typically use “or” to mean “inclusive or.” What other meanings can “or” have? Then it is easy to deﬁne occursfree?. Since there are three alternatives to be checked, we use a Scheme cond rather than an if. In Scheme, (or exp1 exp2) returns a true value if either exp1 or exp2 returns a true value. occursfree? : Sym × LcExp → Bool usage: returns #t if the symbol var occurs free in exp, otherwise returns #f. (define occursfree? (lambda (var exp) (cond ((symbol? exp) (eqv? var exp)) ((eqv? (car exp) ’lambda) (and (not (eqv? var (car (cadr exp)))) (occursfree? var (caddr exp)))) (else (or (occursfree? var (car exp)) (occursfree? var (cadr exp))))))) This procedure is not as readable as it might be. It is hard to tell, for example, that (car (cadr exp)) refers to the declaration of a variable in a lambda expression, or that (caddr exp) refers to its body. We show how to improve this situation considerably in section 2.5. 20 1 Inductive Sets of Data 1.2.5 subst The procedure subst should take three arguments: two symbols, new and old, and an slist, slist. All elements of slist are examined, and a new list is returned that is similar to slist but with all occurrences of old replaced by instances of new. > (subst ’a ’b ’((b c) (b () d))) ((a c) (a () d)) Since subst is deﬁned over slists, its organization should reﬂect the deﬁnition of slists (deﬁnition 1.1.6) Slist ::= ({Sexp}∗ ) Sexp ::= Symbol  Slist The Kleene star gives a concise description of the set of slists, but it is not so helpful for writing programs. Therefore our ﬁrst step is to rewrite the grammar to eliminate the use of the Kleene star. The resulting grammar suggests that our procedure should recur on the car and cdr of an slist. Slist ::= () ::= (Sexp . Slist) Sexp ::= Symbol  Slist This example is more complex than our previous ones because the grammar for its input contains two nonterminals, Slist and Sexp. Therefore we will have two procedures, one for dealing with Slist and one for dealing with Sexp: subst : Sym × Sym × Slist → Slist (define subst (lambda (new old slist) ...)) substinsexp : Sym × Sym × Sexp → Sexp (define substinsexp (lambda (new old sexp) ...)) 1.2 Deriving Recursive Programs 21 Let us ﬁrst work on subst. If the list is empty, there are no occurrences of old to replace. subst : Sym × Sym × Slist → Slist (define subst (lambda (new old slist) (if (null? slist) ’() ...))) If slist is nonempty, its car is a member of Sexp and its cdr is another slist. In this case, the answer should be a list whose car is the result of changing old to new in the car of slist, and whose cdr is the result of changing old to new in the cdr of slist. Since the car of slist is an element of Sexp, we solve the subproblem for the car using substinsexp. Since the cdr of slist is an element of Slist, we recur on the cdr using subst: subst : Sym × Sym × Slist → Slist (define subst (lambda (new old slist) (if (null? slist) ’() (cons (substinsexp new old (car slist)) (subst new old (cdr slist)))))) Now we can move on to substinsexp. From the grammar, we know that the symbol expression sexp is either a symbol or an slist. If it is a symbol, we need to ask whether it is the same as the symbol old. If it is, the answer is new; if it is some other symbol, the answer is the same as sexp. If sexp is an slist, then we can recur using subst to ﬁnd the answer. substinsexp : Sym × Sym × Sexp → Sexp (define substinsexp (lambda (new old sexp) (if (symbol? sexp) (if (eqv? sexp old) new sexp) (subst new old sexp)))) Since we have strictly followed the deﬁnition of Slist and Sexp, this recursion is guaranteed to halt. Since subst and substinsexp call each other recursively, we say they are mutually recursive. The decomposition of subst into two procedures, one for each syntactic category, is an important technique. It allows us to think about one syntactic category at a time, which greatly simpliﬁes our thinking about more complicated programs. 22 1 Inductive Sets of Data Exercise 1.11 [] In the last line of substinsexp, the recursion is on sexp and not a smaller substructure. Why is the recursion guaranteed to halt? Exercise 1.12 [] Eliminate the one call to substinsexp in subst by replacing it by its deﬁnition and simplifying the resulting procedure. The result will be a version of subst that does not need substinsexp. This technique is called inlining, and is used by optimizing compilers. Exercise 1.13 [ ] In our example, we began by eliminating the Kleene star in the grammar for Slist. Write subst following the original grammar by using map. We’ve now developed a recipe for writing procedures that operate on inductively deﬁned data sets. We summarize it as a slogan. Follow the Grammar! When deﬁning a procedure that operates on inductively deﬁned data, the structure of the program should be patterned after the structure of the data. More precisely: • Write one procedure for each nonterminal in the grammar. The procedure will be responsible for handling the data corresponding to that nonterminal, and nothing else. • In each procedure, write one alternative for each production corresponding to that nonterminal. You may need additional case structure, but this will get you started. For each nonterminal that appears in the righthand side, write a recursive call to the procedure for that nonterminal. 1.3 Auxiliary Procedures and Context Arguments The FollowtheGrammar recipe is powerful, but sometimes it is not sufﬁcient. Consider the procedure numberelements. This procedure should take any list (v0 v1 v2 ...) and return the list ((0 v0 ) (1 v1 ) (2 v2 ) ...). A straightforward decomposition of the kind we’ve used so far does not solve this problem, because there is no obvious way to build the value of (numberelements lst) from the value of (numberelements (cdr lst)) (but see exercise 1.36). To solve this problem, we need to generalize the problem. We write a new procedure numberelementsfrom that takes an additional argument n 1.3 Auxiliary Procedures and Context Arguments 23 that speciﬁes the number to start from. This procedure is easy to write, by recursion on the list. numberelementsfrom : Listof(SchemeVal) × Int → Listof(List(Int, SchemeVal)) (numberelementsfrom ’(v0 v1 v2 ...) n) = ((n v0 ) (n + 1 v1 ) (n + 2 v2 ) ...) (define numberelementsfrom (lambda (lst n) (if (null? lst) ’() (cons (list n (car lst)) (numberelementsfrom (cdr lst) (+ n 1)))))) usage: Here the contract header tells us that this procedure takes two arguments, a list (containing any Scheme values) and an integer, and returns a list of things, each of which is a list consisting of two elements: an integer and a Scheme value. Once we have deﬁned numberelementsfrom, it’s easy to write the desired procedure. numberelements : List → Listof(List(Int, SchemeVal)) (define numberelements (lambda (lst) (numberelementsfrom lst 0))) There are two important observations to be made here. First, the procedure numberelementsfrom has a speciﬁcation that is independent of the speciﬁcation of numberelements. It’s very common for a programmer to write a procedure that simply calls some auxiliary procedure with some additional constant arguments. Unless we can understand what that auxiliary procedure does for every value of its arguments, then we can’t possibly understand what the calling procedure does. This gives us a slogan: No Mysterious Auxiliaries! When deﬁning an auxiliary procedure, always specify what it does on all arguments, not just the initial values. Second, the two arguments to numberelementsfrom play two different roles. The ﬁrst argument is the list we are working on. It gets smaller at every recursive call. The second argument, however, is an abstraction 24 1 Inductive Sets of Data of the context in which we are working. In this example, when we call numberelements, we end up calling numberelementsfrom on each sublist of the original list. The second argument tells us the position of the sublist in the original list. This need not decrease at a recursive call; indeed it grows, because we are passing over another element of the original list. We sometimes call this a context argument or inherited attribute. As another example, consider the problem of summing all the values in a vector. If we were summing the values in a list, we could follow the grammar to recur on the cdr of the list. This would get us a procedure like listsum : Listof(Int) → Int (define listsum (lambda (loi) (if (null? loi) 0 (+ (car loi) (listsum (cdr loi)))))) But it is not possible to proceed in this way with vectors, because they do not decompose as readily. Since we cannot decompose vectors, we generalize the problem to compute the sum of part of the vector. The speciﬁcation of our problem is to compute i=length(v)−1 ∑ vi i=0 where v is a vector of integers. We generalize it by turning the upper bound into a parameter n, so that the new task is to compute i=n ∑ vi i=0 where 0 ≤ n < length(v). This procedure is straightforward to write from its speciﬁcation, using induction on its second argument n. 25 1.4 Exercises partialvectorsum : Vectorof(Int) × Int → Int usage: if 0 ≤ n < length(v), then (partialvectorsum v n) = i=n ∑ vi i=0 (define partialvectorsum (lambda (v n) (if (zero? n) (vectorref v 0) (+ (vectorref v n) (partialvectorsum v ( n 1)))))) Since n decreases steadily to zero, a proof of correctness for this program would proceed by induction on n. Because 0 ≤ n and n = 0, we can deduce that 0 ≤ (n − 1), so that the recursive call to the procedure partialvectorsum satisﬁes its contract. It is now a simple matter to solve our original problem. The procedure partialvectorsum doesn’t apply if the vector is of length 0, so we need to handle that case separately. vectorsum : Vectorof(Int) → Int i=length(v)−1 usage: (vectorsum v) = ∑ vi i=0 (define vectorsum (lambda (v) (let ((n (vectorlength v))) (if (zero? n) 0 (partialvectorsum v ( n 1)))))) There are many other situations in which it may be helpful or necessary to introduce auxiliary variables or procedures to solve a problem. Always feel free to do so, provided that you can give an independent speciﬁcation of what the new procedure is intended to do. Exercise 1.14 [ ] Given the assumption 0 ≤ n < length(v), prove that partialvectorsum is correct. 1.4 Exercises Getting the knack of writing recursive programs involves practice. Thus we conclude this chapter with a sequence of exercises. In each of these exercises, assume that s is a symbol, n is a nonnegative integer, lst is a list, loi is a list of integers, los is a list of symbols, slist 26 1 Inductive Sets of Data is an slist, and x is any Scheme value; and similarly s1 is a symbol, los2 is a list of symbols, x1 is a Scheme value, etc. Also assume that pred is a predicate, that is, a procedure that takes any Scheme value and always returns either #t or #f. Make no other assumptions about the data unless further restrictions are given as part of a particular problem. For these exercises, there is no need to check that the input matches the description; for each procedure, assume that its input values are members of the speciﬁed sets. Deﬁne, test, and debug each procedure. Your deﬁnition should include a contract and usage comment in the style we have used in this chapter. Feel free to deﬁne auxiliary procedures, but each auxiliary procedure you deﬁne should have its own speciﬁcation, as in section 1.3. To test these procedures, ﬁrst try all the given examples. Then use other examples to test these procedures, since the given examples are not adequate to reveal all possible errors. Exercise 1.15 [] (duple n x) returns a list containing n copies of x. > (duple (3 3) > (duple ((ha ha) > (duple () 2 3) 4 ’(ha ha)) (ha ha) (ha ha) (ha ha)) 0 ’(blah)) Exercise 1.16 [] (invert lst), where lst is a list of 2lists (lists of length two), returns a list with each 2list reversed. > (invert ’((a 1) (a 2) (1 b) (2 b))) ((1 a) (2 a) (b 1) (b 2)) Exercise 1.17 [] (down lst) wraps parentheses around each toplevel element of lst. > (down ’(1 2 3)) ((1) (2) (3)) > (down ’((a) (fine) (idea))) (((a)) ((fine)) ((idea))) > (down ’(a (more (complicated)) object)) ((a) ((more (complicated))) (object)) 1.4 Exercises 27 Exercise 1.18 [] (swapper s1 s2 slist) returns a list the same as slist, but with all occurrences of s1 replaced by s2 and all occurrences of s2 replaced by s1. > (swapper ’a ’d ’(a b c d)) (d b c a) > (swapper ’a ’d ’(a d () c d)) (d a () c a) > (swapper ’x ’y ’((x) y (z (x)))) ((y) x (z (y))) Exercise 1.19 [ ] (listset lst n x) returns a list like lst, except that the nth element, using zerobased indexing, is x. > (listset ’(a b c d) 2 ’(1 2)) (a b (1 2) d) > (listref (listset ’(a b c d) 3 ’(1 5 10)) 3) (1 5 10) Exercise 1.20 [] (countoccurrences s slist) returns the number of occurrences of s in slist. > (countoccurrences ’x ’((f x) y (((x z) x)))) 3 > (countoccurrences ’x ’((f x) y (((x z) () x)))) 3 > (countoccurrences ’w ’((f x) y (((x z) x)))) 0 Exercise 1.21 [ ] (product sos1 sos2), where sos1 and sos2 are each a list of symbols without repetitions, returns a list of 2lists that represents the Cartesian product of sos1 and sos2. The 2lists may appear in any order. > (product ’(a b c) ’(x y)) ((a x) (a y) (b x) (b y) (c x) (c y)) Exercise 1.22 [ ] (filterin pred lst) returns the list of those elements in lst that satisfy the predicate pred. > (filterin number? ’(a 2 (1 3) b 7)) (2 7) > (filterin symbol? ’(a (b c) 17 foo)) (a foo) Exercise 1.23 [ ] (listindex pred lst) returns the 0based position of the ﬁrst element of lst that satisﬁes the predicate pred. If no element of lst satisﬁes the predicate, then listindex returns #f. > (listindex number? ’(a 2 (1 3) b 7)) 1 > (listindex symbol? ’(a (b c) 17 foo)) 0 > (listindex symbol? ’(1 2 (a b) 3)) #f 28 1 Inductive Sets of Data Exercise 1.24 [ ] (every? pred lst) returns #f if any element of lst fails to satisfy pred, and returns #t otherwise. > (every? number? ’(a b c 3 e)) #f > (every? number? ’(1 2 3 5 4)) #t Exercise 1.25 [ ] (exists? pred lst) returns #t if any element of lst satisﬁes pred, and returns #f otherwise. > (exists? number? ’(a b c 3 e)) #t > (exists? number? ’(a b c d e)) #f Exercise 1.26 [ ] (up lst) removes a pair of parentheses from each toplevel element of lst. If a toplevel element is not a list, it is included in the result, as is. The value of (up (down lst)) is equivalent to lst, but (down (up lst)) is not necessarily lst. (See exercise 1.17.) > (up ’((1 2) (3 4))) (1 2 3 4) > (up ’((x (y)) z)) (x (y) z) Exercise 1.27 [ ] (flatten slist) returns a list of the symbols contained in slist in the order in which they occur when slist is printed. Intuitively, flatten removes all the inner parentheses from its argument. > (flatten ’(a b c)) (a b c) > (flatten ’((a) () (b ()) () (c))) (a b c) > (flatten ’((a b) c (((d)) e))) (a b c d e) > (flatten ’(a b (() (c)))) (a b c) Exercise 1.28 [ ] (merge loi1 loi2), where loi1 and loi2 are lists of integers that are sorted in ascending order, returns a sorted list of all the integers in loi1 and loi2. > (merge (1 1 2 4 > (merge (3 35 62 ’(1 4) ’(1 2 8)) 8) ’(35 62 81 90 91) ’(3 83 85 90)) 81 83 85 90 90 91) 1.4 Exercises 29 Exercise 1.29 [ ] (sort loi) returns a list of the elements of loi in ascending order. > (sort ’(8 2 5 2 3)) (2 2 3 5 8) Exercise 1.30 [ ] (sort/predicate pred loi) returns a list of elements sorted by the predicate. > (sort/predicate < ’(8 2 5 2 3)) (2 2 3 5 8) > (sort/predicate > ’(8 2 5 2 3)) (8 5 3 2 2) Exercise 1.31 [] Write the following procedures for calculating on a bintree (deﬁnition 1.1.7): leaf and interiornode, which build bintrees, leaf?, which tests whether a bintree is a leaf, and lson, rson, and contentsof, which extract the components of a node. contentsof should work on both leaves and interior nodes. Exercise 1.32 [] Write a procedure doubletree that takes a bintree, as represented in deﬁnition 1.1.7, and produces another bintree like the original, but with all the integers in the leaves doubled. Exercise 1.33 [ ] Write a procedure markleaveswithreddepth that takes a bintree (deﬁnition 1.1.7), and produces a bintree of the same shape as the original, except that in the new tree, each leaf contains the integer of nodes between it and the root that contain the symbol red. For example, the expression (markleaveswithreddepth (interiornode ’red (interiornode ’bar (leaf 26) (leaf 12)) (interiornode ’red (leaf 11) (interiornode ’quux (leaf 117) (leaf 14)) which is written using the procedures deﬁned in exercise 1.31, should return the bintree (red (bar 1 1) (red 2 (quux 2 2))) 30 1 Inductive Sets of Data Exercise 1.34 [ ] Write a procedure path that takes an integer n and a binary search tree bst (page 10) that contains the integer n, and returns a list of lefts and rights showing how to ﬁnd the node containing n. If n is found at the root, it returns the empty list. > (path 17 ’(14 (7 () (12 () ())) (26 (20 (17 () ()) ()) (31 () ())))) (right left left) Exercise 1.35 [ ] Write a procedure numberleaves that takes a bintree, and produces a bintree like the original, except the contents of the leaves are numbered starting from 0. For example, (numberleaves (interiornode ’foo (interiornode ’bar (leaf 26) (leaf 12)) (interiornode ’baz (leaf 11) (interiornode ’quux (leaf 117) (leaf 14)) should return (foo (bar 0 1) (baz 2 (quux 3 4))) Exercise 1.36 [ ] Write a procedure g such that numberelements from page 23 could be deﬁned as (define numberelements (lambda (lst) (if (null? lst) ’() (g (list 0 (car lst)) (numberelements (cdr lst)))))) 2 2.1 Data Abstraction Specifying Data via Interfaces Every time we decide to represent a certain set of quantities in a particular way, we are deﬁning a new data type: the data type whose values are those representations and whose operations are the procedures that manipulate those entities. The representation of these entities is often complex, so we do not want to be concerned with their details when we can avoid them. We may also decide to change the representation of the data. The most efﬁcient representation is often a lot more difﬁcult to implement, so we may wish to develop a simple implementation ﬁrst and only change to a more efﬁcient representation if it proves critical to the overall performance of a system. If we decide to change the representation of some data for any reason, we must be able to locate all parts of a program that are dependent on the representation. This is accomplished using the technique of data abstraction. Data abstraction divides a data type into two pieces: an interface and an implementation. The interface tells us what the data of the type represents, what the operations on the data are, and what properties these operations may be relied on to have. The implementation provides a speciﬁc representation of the data and code for the operations that make use of that data representation. A data type that is abstract in this way is said to be an abstract data type. The rest of the program, the client of the data type, manipulates the new data only through the operations speciﬁed in the interface. Thus if we wish to change the representation of the data, all we must do is change the implementation of the operations in the interface. 32 2 Data Abstraction This is a familiar idea: when we write programs that manipulate ﬁles, most of the time we care only that we can invoke procedures that perform the open, close, read, and other typical operations on ﬁles. Similarly, most of the time, we don’t care how integers are actually represented inside the machine. Our only concern is that we can perform the arithmetic operations reliably. When the client manipulates the values of the data type only through the procedures in the interface, we say that the client code is representationindependent, because then the code does not rely on the representation of the values in the data type. All the knowledge about how the data is represented must therefore reside in the code of the implementation. The most important part of an implementation is the speciﬁcation of how the data is represented. We use the notation v for “the representation of data v.” To make this clearer, let us consider a simple example: the data type of natural numbers. The data to be represented are the natural numbers. The interface is to consist of four procedures: zero, iszero?, successor, and predecessor. Of course, not just any set of procedures will be acceptable as an implementation of this interface. A set of procedures will be acceptable as implementations of zero, iszero?, successor, and predecessor only if they satisfy the four equations (zero) = 0 #t n=0 #f n = 0 (successor n) = n + 1 (n ≥ 0) (predecessor n + 1) = n (n ≥ 0) (iszero? n) = This speciﬁcation does not dictate how these natural numbers are to be represented. It requires only that these procedures conspire to produce the speciﬁed behavior. Thus, the procedure zero must return the representation of 0. The procedure successor, given the representation of the number n, must return the representation of the number n + 1, and so on. The speciﬁcation says nothing about (predecessor (zero)), so under this speciﬁcation any behavior would be acceptable. 2.1 Specifying Data via Interfaces 33 We can now write client programs that manipulate natural numbers, and we are guaranteed that they will get correct answers, no matter what representation is in use. For example, (define plus (lambda (x y) (if (iszero? x) y (successor (plus (predecessor x) y))))) will satisfy (plus x y) = x + y, no matter what implementation of the natural numbers we use. Most interfaces will contain some constructors that build elements of the data type, and some observers that extract information from values of the data type. Here we have three constructors, zero, successor, and predecessor, and one observer, iszero?. There are many possible representations of this interface. Let us consider three of them. 1. Unary representation: In the unary representation, the natural number n is represented by a list of n #t’s. Thus, 0 is represented by (), 1 is represented by (#t), 2 is represented by (#t #t), etc. We can deﬁne this representation inductively by: 0 = () n + 1 = (#t . n) In this representation, we can satisfy the speciﬁcation by writing (define (define (define (define zero (lambda () ’())) iszero? (lambda (n) (null? n))) successor (lambda (n) (cons #t n))) predecessor (lambda (n) (cdr n))) 2. Scheme number representation: In this representation, we simply use Scheme’s internal representation of numbers (which might itself be quite complicated!). We let n be the Scheme integer n, and deﬁne the four required entities by (define (define (define (define zero (lambda () 0)) iszero? (lambda (n) (zero? n))) successor (lambda (n) (+ n 1))) predecessor (lambda (n) ( n 1))) 34 2 Data Abstraction 3. Bignum representation: In the bignum representation, numbers are represented in base N, for some large integer N. The representation becomes a list consisting of numbers between 0 and N − 1 (sometimes called bigits rather than digits). This representation makes it easy to represent integers that are much larger than can be represented in a machine word. For our purposes, it is convenient to keep the list with leastsigniﬁcant bigit ﬁrst. We can deﬁne the representation inductively by n = () (r . q) n=0 n = qN + r, 0 ≤ r < N So if N = 16, then 33 = (1 2) and 258 = (2 0 1), since 258 = 2 × 160 + 0 × 161 + 1 × 162 None of these implementations enforces data abstraction. There is nothing to prevent a client program from looking at the representation and determining whether it is a list or a Scheme integer. On the other hand, some languages provide direct support for data abstractions: they allow the programmer to create new interfaces and check that the new data is manipulated only through the procedures in the interface. If the representation of a type is hidden, so it cannot be exposed by any operation (including printing), the type is said to be opaque. Otherwise, it is said to be transparent. Scheme does not provide a standard mechanism for creating new opaque types. Thus we settle for an intermediate level of abstraction: we deﬁne interfaces and rely on the writer of the client program to be discreet and use only the procedures in the interfaces. In chapter 8, we discuss ways in which a language can enforce such protocols. Exercise 2.1 [] Implement the four required operations for bigits. Then use your implementation to calculate the factorial of 10. How does the execution time vary as this argument changes? How does the execution time vary as the base changes? Explain why. Exercise 2.2 [ ] Analyze each of these proposed representations critically. To what extent do they succeed or fail in satisfying the speciﬁcation of the data type? Exercise 2.3 [ ] Deﬁne a representation of all the integers (negative and nonnegative) as difftrees, where a difftree is a list deﬁned by the grammar Difftree ::= (one)  (diff Difftree Difftree) 2.2 Representation Strategies for Data Types 35 The list (one) represents 1. If t1 represents n1 and t2 represents n2 , then (diff t1 t2 ) is a representation of n1 − n2 . So both (one) and (diff (one) (diff (one) (one))) are representations of 1; (diff (diff (one) (one)) (one)) is a representation of −1. 1. Show that every number has inﬁnitely many representations in this system. 2. Turn this representation of the integers into an implementation by writing zero, iszero?, successor, and predecessor, as speciﬁed on page 32, except that now the negative integers are also represented. Your procedures should take as input any of the multiple legal representations of an integer in this scheme. For example, if your successor procedure is given any of the inﬁnitely many legal representations of 1, it should produce one of the legal representations of 2. It is permissible for different legal representations of 1 to yield different legal representations of 2. 3. Write a procedure difftreeplus that does addition in this representation. Your procedure should be optimized for the difftree representation, and should do its work in a constant amount of time (independent of the size of its inputs). In particular, it should not be recursive. 2.2 Representation Strategies for Data Types When data abstraction is used, programs have the property of representation independence: programs are independent of the particular representation used to implement an abstract data type. It is then possible to change the representation by redeﬁning the small number of procedures belonging to the interface. We frequently rely on this property in later chapters. In this section we introduce some strategies for representing data types. We illustrate these choices using a data type of environments. An environment associates a value with each element of a ﬁnite set of variables. An environment may be used to associate variables with their values in a programming language implementation. A compiler may also use an environment to associate each variable name with information about that variable. Variables may be represented in any way we please, so long as we can check two variables for equality. We choose to represent variables using Scheme symbols, but in a language without a symbol data type, variables could be represented by strings, by references into a hash table, or even by numbers (see section 3.6). 36 2 Data Abstraction 2.2.1 The Environment Interface An environment is a function whose domain is a ﬁnite set of variables, and whose range is the set of all Scheme values. Since we adopt the usual mathematical convention that a ﬁnite function is a ﬁnite set of ordered pairs, then we need to represent all sets of the form {(var1 , val1), . . . , (varn , valn)} where the vari are distinct variables and the vali are any Scheme values. We sometimes call the value of the variable var in an environment env its binding in env. The interface to this data type has three procedures, speciﬁed as follows: (emptyenv) (applyenv f var) (extendenv var v f ) = ∅ = f (var) = g, where g(var1) = v f (var1) if var1 = var otherwise The procedure emptyenv, applied to no arguments, must produce a representation of the empty environment; applyenv applies a representation of an environment to a variable and (extendenv var val env) produces a new environment that behaves like env, except that its value at variable var is val. For example, the expression > (define e (extendenv ’d 6 (extendenv ’y 8 (extendenv ’x 7 (extendenv ’y 14 (emptyenv)))))) deﬁnes an environment e such that e(d) = 6, e(x) = 7, e(y) = 8, and e is undeﬁned on any other variables. This is, of course, only one of many different ways of building this environment. For instance, in the example above the binding of y to 14 is overridden by its later binding to 8. As in the previous example, we can divide the procedures of the interface into constructors and observers. In this example, emptyenv and extendenv are the constructors, and applyenv is the only observer. 2.2 Representation Strategies for Data Types 37 Exercise 2.4 [ ] Consider the data type of stacks of values, with an interface consisting of the procedures emptystack, push, pop, top, and emptystack?. Write a speciﬁcation for these operations in the style of the example above. Which operations are constructors and which are observers? 2.2.2 Data Structure Representation We can obtain a representation of environments by observing that every environment can be built by starting with the empty environment and applying extendenv n times, for some n ≥ 0, e.g., (extendenv varn valn ... (extendenv var1 val1 (emptyenv))...) So every environment can be built by an expression in the following grammar: Envexp ::= (emptyenv) ::= (extendenv Identiﬁer Schemevalue Envexp) We could represent environments using the same grammar to describe a set of lists. This would give the implementation shown in ﬁgure 2.1. The procedure applyenv looks at the data structure env representing an environment, determines what kind of environment it represents, and does the right thing. If it represents the empty environment, then an error is reported. If it represents an environment built by extendenv, then it checks to see if the variable it is looking for is the same as the one bound in the environment. If it is, then the saved value is returned. Otherwise, the variable is looked up in the saved environment. This is a very common pattern of code. We call it the interpreter recipe: The Interpreter Recipe 1. Look at a piece of data. 2. Decide what kind of data it represents. 3. Extract the components of the datum and do the right thing with them. 38 2 Data Abstraction Env = (emptyenv)  (extendenv Var SchemeVal Env) Var = Sym emptyenv : () → Env (define emptyenv (lambda () (list ’emptyenv))) extendenv : Var × SchemeVal × Env → Env (define extendenv (lambda (var val env) (list ’extendenv var val env))) applyenv : Env × Var → SchemeVal (define applyenv (lambda (env searchvar) (cond ((eqv? (car env) ’emptyenv) (reportnobindingfound searchvar)) ((eqv? (car env) ’extendenv) (let ((savedvar (cadr env)) (savedval (caddr env)) (savedenv (cadddr env))) (if (eqv? searchvar savedvar) savedval (applyenv savedenv searchvar)))) (else (reportinvalidenv env))))) (define reportnobindingfound (lambda (searchvar) (eopl:error ’applyenv "No binding for ~s" searchvar))) (define reportinvalidenv (lambda (env) (eopl:error ’applyenv "Bad environment: ~s" env))) Figure 2.1 A datastructure representation of environments 39 2.2 Representation Strategies for Data Types Exercise 2.5 [] We can use any data structure for representing environments, if we can distinguish empty environments from nonempty ones, and in which one can extract the pieces of a nonempty environment. Implement environments using a representation in which the empty environment is represented as the empty list, and in which extendenv builds an environment that looks like saved−env saved−var saved−val This is called an alist or associationlist representation. Exercise 2.6 [] Invent at least three different representations of the environment interface and implement them. Exercise 2.7 [] Rewrite applyenv in ﬁgure 2.1 to give a more informative error message. Exercise 2.8 [] Add to the environment interface an observer called emptyenv? and implement it using the alist representation. Exercise 2.9 [] Add to the environment interface an observer called hasbinding? that takes an environment env and a variable s and tests to see if s has an associated value in env. Implement it using the alist representation. Exercise 2.10 [] Add to the environment interface a constructor extendenv*, and implement it using the alist representation. This constructor takes a list of variables, a list of values of the same length, and an environment, and is speciﬁed by (extendenv* (var1 ... vark ) (val1 ... valk ) f ) = g, if var = vari for some i such that 1 ≤ i ≤ k vali where g(var) = f (var) otherwise Exercise 2.11 [ ] A naive implementation of extendenv* from the preceding exercise requires time proportional to k to run. It is possible to represent environments so that extendenv* requires only constant time: represent the empty environment by the empty list, and represent a nonempty environment by the data structure saved−env saved−vars Such an environment might look like saved−vals 40 2 Data Abstraction backbone rest of environment (a b c) (11 12 13) (x z) (66 77) (x y) (88 99) This is called the ribcage representation. The environment is represented as a list of pairs called ribs; each left rib is a list of variables and each right rib is the corresponding list of values. Implement the environment interface, including extendenv*, in this representation. 2.2.3 Procedural Representation The environment interface has an important property: it has exactly one observer, applyenv. This allows us to represent an environment as a Scheme procedure that takes a variable and returns its associated value. To do this, we deﬁne emptyenv and extendenv to return procedures that, when applied, do the same thing that applyenv did in the preceding section. This gives us the following implementation. Env = Var → SchemeVal emptyenv : () → Env (define emptyenv (lambda () (lambda (searchvar) (reportnobindingfound searchvar)))) extendenv : Var × SchemeVal × Env → Env (define extendenv (lambda (savedvar savedval savedenv) (lambda (searchvar) (if (eqv? searchvar savedvar) savedval (applyenv savedenv searchvar))))) applyenv : Env × Var → SchemeVal (define applyenv (lambda (env searchvar) (env searchvar))) 2.2 Representation Strategies for Data Types 41 If the empty environment, created by invoking emptyenv, is passed any variable whatsoever, it indicates with an error message that the given variable is not in its domain. The procedure extendenv returns a new procedure that represents the extended environment. This procedure, when passed a variable searchvar, checks to see if the variable it is looking for is the same as the one bound in the environment. If it is, then the saved value is returned. Otherwise, the variable is looked up in the saved environment. We call this a procedural representation, in which the data is represented by its action under applyenv. The case of a data type with a single observer is less rare than one might think. For example, if the data being represented is a set of functions, then it can be represented by its action under application. In this case, we can extract the interface and the procedural representation by the following recipe: 1. Identify the lambda expressions in the client code whose evaluation yields values of the type. Create a constructor procedure for each such lambda expression. The parameters of the constructor procedure will be the free variables of the lambda expression. Replace each such lambda expression in the client code by an invocation of the corresponding constructor. 2. Deﬁne an apply procedure like applyenv above. Identify all the places in the client code, including the bodies of the constructor procedures, where a value of the type is applied. Replace each such application by an invocation of the apply procedure. If these steps are carried out, the interface will consist of all the constructor procedures and the apply procedure, and the client code will be representationindependent: it will not rely on the representation, and we will be free to substitute another implementation of the interface, such as the one we describe in section 2.2.2. If the implementation language does not allow higherorder procedures, then one can perform the additional step of implementing the resulting interface using a data structure representation and the interpreter recipe, as in the preceding section. This process is called defunctionalization. The derivation of the data structure representation of environments is a simple example of defunctionalization. The relation between procedural and defunctionalized representations will be a recurring theme in this book. 42 2 Data Abstraction Exercise 2.12 [] Implement the stack data type of exercise 2.4 using a procedural representation. Exercise 2.13 [ ] Extend the procedural representation to implement emptyenv? by representing the environment by a list of two procedures: one that returns the value associated with a variable, as before, and one that returns whether or not the environment is empty. Exercise 2.14 [ ] Extend the representation of the preceding exercise to include a third procedure that implements hasbinding? (see exercise 2.9). 2.3 Interfaces for Recursive Data Types We spent much of chapter 1 manipulating recursive data types. For example, we deﬁned lambdacalculus expressions in deﬁnition 1.1.8 by the grammar Lcexp ::= Identiﬁer ::= (lambda (Identiﬁer) Lcexp) ::= (Lcexp Lcexp) and we wrote procedures like occursfree?. As we mentioned at the time, the deﬁnition of occursfree? in section 1.2.4 is not as readable as it might be. It is hard to tell, for example, that (car (cadr exp)) refers to the declaration of a variable in a lambda expression, or that (caddr exp) refers to its body. We can improve this situation by introducing an interface for lambdacalculus expressions. Our interface will have constructors and two kinds of observers: predicates and extractors. The constructors are: varexp lambdaexp appexp : Var → Lcexp : Var × Lcexp → Lcexp : Lcexp × Lcexp → Lcexp The predicates are: varexp? lambdaexp? appexp? : Lcexp → Bool : Lcexp → Bool : Lcexp → Bool Finally, the extractors are 2.3 Interfaces for Recursive Data Types varexp>var lambdaexp>boundvar lambdaexp>body appexp>rator appexp>rand : : : : : 43 Lcexp → Var Lcexp → Var Lcexp → Lcexp Lcexp → Lcexp Lcexp → Lcexp Each of these extracts the corresponding portion of the lambdacalculus expression. We can now write a version of occursfree? that depends only on the interface. occursfree? : Sym × LcExp → Bool (define occursfree? (lambda (searchvar exp) (cond ((varexp? exp) (eqv? searchvar (varexp>var exp))) ((lambdaexp? exp) (and (not (eqv? searchvar (lambdaexp>boundvar exp))) (occursfree? searchvar (lambdaexp>body exp)))) (else (or (occursfree? searchvar (appexp>rator exp)) (occursfree? searchvar (appexp>rand exp))))))) This works on any representation of lambdacalculus expressions, so long as they are built using these constructors. We can write down a general recipe for designing an interface for a recursive data type: Designing an interface for a recursive data type 1. Include