Essentials of Programming Languages Daniel P. Friedman …

1 Essentials OF Programming LANGUAGESD aniel P. Friedman and Mitchell WandTHIRD EDITIONESSENTIALS OFPROGRAMMING LANGUAGESTHIRD EDITIONF riedman and WandMD DALIM 955472 3/22/08 CYAN MAG YELO BLACK computer science/ Programming languagesEssentials of Programming Languagesthird editionDaniel P. Friedman and Mitchell Wand This book provides students with a deep, working understanding of the essential concepts of program-ming 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.

2 The approach is both analytical and hands-on. The book provides views of program-ming Languages using widely varying levels of abstraction, maintaining a clear connection between the high-level and low-level 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.

3 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 continuation-passing style. Essentials of Programming Languages can be used for both graduate and un-dergraduate courses, and for continuing education courses for 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.

4 Byrd and Oleg Kiselyov. Mitchell Wand is Professor of Computer Science at Northeastern University. With lucid prose and elegant code, this book provides the most concrete introduction to the few build-ing 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. Chung-chieh Shan, Department of Computer Science, Rutgers University 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.

5 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 I ve found the interpreters-based approach for teaching Programming Languages to be both compelling and rewarding for my students. Exposing students to the revelation that an interpreter for a program-ming language is itself just another program opens up a world of possibilities for problem solving.

6 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 CollegeThe MIT PressMassachusetts Institute of TechnologyCambridge, Massachusetts 02142 ofProgrammingLanguagesthird editionEssentials ofProgrammingLanguagesthird editionDaniel P. FriedmanMitchell WandThe MIT PressCambridge, MassachusettsLondon, England 2008 Daniel P. Friedman and Mitchell WandAll rights reserved. No part of this book may be reproduced in any form by anyelectronic or mechanical means (including photocopying, recording, or informationstorage and retrieval) without permission in writing from the Press books may be purchased at special quantity discounts for business or salespromotional use.

7 For information, please email orwrite to Special Sales Department, The MIT Press, 55 Hayward Street, Cambridge,MA book was set in LATEX2 by the authors, and was printed and bound in the UnitedStates of of Congress Cataloging-in-Publication DataFriedman, Daniel of Programming Languages / Daniel P. Friedman , MitchellWa n d . 3rd bibliographical references and 978-0-262-06279-4 (hbk. : alk. paper)1. Programming Languages (Electronic computers). I. Wand,Mitchell. II. dc22200703972310987654321 ContentsForeword by Hal AbelsonixPrefacexvAcknowledgmentsxxi1 Inductive Sets of Recursively Specified Deriving Recursive Auxiliary Procedures and Context Exercises252 Data Specifying Data via Representation Strategies for Data Interfaces for Recursive Data A Tool for Defining Recursive Data Abstract Syntax and Its Representation513 Specification and Implementation LET: A Simple PROC: A language with LETREC.

8 A language with Recursive Scoping and Binding of Eliminating Variable Implementing Lexical Addressing93viContents4 Computational EXPLICIT-REFS: A language with Explicit IMPLICIT-REFS: A language with Implicit MUTABLE-PAIRS: A language with Mutable Parameter-Passing Variations1305 Continuation-Passing A Continuation-Passing A Trampolined An Imperative Threads1796 Continuation-Passing Writing Programs in Continuation-Passing Tail Converting to Continuation-Passing Modeling Computational Values and Their Assigning a Type to an CHECKED: A Type-Checked INFERRED.

9 A language with Type Inference2488 The Simple Module Modules That Declare Module Procedures3119 Objects and Object-Oriented The The A Typed The Type Checker358 ContentsviiA For Further Reading373B The SLLGEN Parsing Scanners and Parsers in SLLGEN383 Bibliography393 Index401 ForewordThis book brings you face-to-face with the most fundamental idea in com-puter Programming :The interpreter for a computer language is just another sounds obvious, doesn t it? But the implications are profound. If youare a computational theorist, the interpreter idea recalls G del s discoveryof the limitations of formal logical systems, Turing s concept of a universalcomputer, and von Neumann s basic notion of the stored-program you are a programmer, mastering theidea of an interpreter is a source ofgreat power.

10 It provokes a real shift in mindset, a basic change in the wayyou think about did a lot of Programming before I learned about interpreters, and I pro-duced some substantial programs. One of them, for example, was a largedata-entry and information-retrieval system written in PL/I. When I imple-mented my system, I viewed PL/I as a fixed collection of rules establishedby some unapproachable group of language designers. I saw my job as notto modify these rules, or even to understand them deeply, but rather to pickthrough the (very) large manual, selecting this or that feature to use.