Out of print; available for free at http://www.gustavus.edu/+max/concrete-abstractions.html (cid:67)(cid:111)(cid:110)(cid:99)(cid:114)(cid:101)(cid:116)(cid:101) (cid:65)(cid:98)(cid:115)(cid:116)(cid:114)(cid:97)(cid:99)(cid:116)(cid:105)(cid:111)(cid:110)(cid:115) Copyright © 1999 by Max Hailperin, Barbara Kaiser, and Karl Knight Out of print; available for free at http://www.gustavus.edu/+max/concrete-abstractions.html Copyright © 1999 by Max Hailperin, Barbara Kaiser, and Karl Knight Out of print; available for free at http://www.gustavus.edu/+max/concrete-abstractions.html (cid:67)(cid:111)(cid:110)(cid:99)(cid:114)(cid:101)(cid:116)(cid:101) (cid:65)(cid:98)(cid:115)(cid:116)(cid:114)(cid:97)(cid:99)(cid:116)(cid:105)(cid:111)(cid:110)(cid:115) (cid:65)(cid:110) (cid:73)(cid:110)(cid:116)(cid:114)(cid:111)(cid:100)(cid:117)(cid:99)(cid:116)(cid:105)(cid:111)(cid:110) (cid:116)(cid:111) (cid:67)(cid:111)(cid:109)(cid:112)(cid:117)(cid:116)(cid:101)(cid:114) (cid:83)(cid:99)(cid:105)(cid:101)(cid:110)(cid:99)(cid:101) (cid:85)(cid:115)(cid:105)(cid:110)(cid:103) (cid:83)(cid:99)(cid:104)(cid:101)(cid:109)(cid:101) Max Hailperin GustavusAdolphusCollege Barbara Kaiser GustavusAdolphusCollege Karl Knight GustavusAdolphusCollege An Imprint of Brooks/Cole Publishing Company ® An International Thomson Publishing Company † † † † † † PacificGrove Albany Belmont Bonn Boston Cincinnati Detroit † † † † † Johannesburg London Madrid Melbourne MexicoCity NewYork † † † † Paris Singapore Tokyo Toronto Washington Copyright © 1999 by Max Hailperin, Barbara Kaiser, and Karl Knight Out of print; available for free at http://www.gustavus.edu/+max/concrete-abstractions.html SponsoringEditor:SuzanneJeans CoverDesign:VernonT.Boes MarketingTeam:NathanWilbur,MicheleMootz CoverPhoto:CraigCowan.CourtesyofCouturierGallery, EditorialAssistant:KathrynSchooling LosAngeles,CA ProductionManager:MarleneThom ProjectManagementandTypesetting: ManuscriptEditor:LindaThompson IntegreTechnicalPublishingCo.,Inc. InteriorDesign:MerryObrechtSawdey PrintingandBinding:Webcom,Ltd. COPYRIGHT(cid:211) 1999byBrooks/ColePublishingCompany AdivisionofInternationalThomsonPublishingInc. TheITPlogoisaregisteredtrademarkusedhereinunderlicense. JavaTMisatrademarkofSunMicrosystems,Inc.Allotherproductsusedhereinareusedforidentificationpurposesonly,andmay betrademarksorregisteredtrademarksoftheirrespectiveowners. Formoreinformation,contact: BROOKS/COLEPUBLISHINGCOMPANY InternationalThomsonEditores 511ForestLodgeRoad Seneca53 PacificGrove,CA93950 Col.Polanco USA 11560Me´xico,D.F.,Me´xico InternationalThomsonPublishingEurope InternationalThomsonPublishingGmbH BerkshireHouse168–173 Ko¨nigswintererStrasse418 HighHolborn 53227Bonn LondonWC1V7AA Germany England InternationalThomsonPublishingAsia ThomasNelsonAustralia 221HendersonRoad 102DoddsStreet #05–10HendersonBuilding SouthMelbourne,3205 Singapore0315 Victoria,Australia InternationalThomsonPublishingJapan NelsonCanada HirakawachoKyowaBuilding,3F 1120BirchmountRoad 2-2-1Hirakawacho Scarborough,Ontario Chiyoda-ku,Tokyo102 CanadaM1K5G4 Japan Allrightsreserved.Nopartofthisbookmaybereproduced,storedinaretrievalsystem,ortranscribed,inanyformorbyany means—electronic,mechanical,photocopying,recording,orotherwise—withoutthepriorwrittenpermissionofthepublisher, Brooks/ColePublishingCompany,PacificGrove,California93950. PrintedinCanada 10 9 8 7 6 5 4 3 2 1 LibraryofCongressCataloginginPublicationData Hailperin,Max. Concreteabstractions:anintroductiontocomputerscienceusing Scheme/MaxHailperin,BarbaraKaiser,KarlKnight. p. cm. ISBN0-534-95211-9(alk.paper) IW..1K)..aiCsIeoIrIm,.BpTauirttbleear.rsaci(eBnacreb.ara2K..A).bstIrIa.ctKdnaigtahtt,ypKeasrl(C(Koamrlputerscience) THIS BOOK IS PRINTED ON Q00A57.163.H032—96dc211997 98-34C08IP0 ACID-FREE RECYCLED PAPER Copyright © 1999 by Max Hailperin, Barbara Kaiser, and Karl Knight Out of print; available for free at http://www.gustavus.edu/+max/concrete-abstractions.html (cid:67)(cid:111)(cid:110)(cid:116)(cid:101)(cid:110)(cid:116)(cid:115) (cid:80)(cid:114)(cid:101)(cid:102)(cid:97)(cid:99)(cid:101) (cid:105)(cid:120) (cid:80)(cid:65)(cid:82)(cid:84) (cid:73) (cid:80)(cid:114)(cid:111)(cid:99)(cid:101)(cid:100)(cid:117)(cid:114)(cid:97)(cid:108) (cid:65)(cid:98)(cid:115)(cid:116)(cid:114)(cid:97)(cid:99)(cid:116)(cid:105)(cid:111)(cid:110) (cid:67)(cid:72)(cid:65)(cid:80)(cid:84)(cid:69)(cid:82) (cid:49) (cid:67)(cid:111)(cid:109)(cid:112)(cid:117)(cid:116)(cid:101)(cid:114) (cid:83)(cid:99)(cid:105)(cid:101)(cid:110)(cid:99)(cid:101) (cid:97)(cid:110)(cid:100) (cid:80)(cid:114)(cid:111)(cid:103)(cid:114)(cid:97)(cid:109)(cid:109)(cid:105)(cid:110)(cid:103) (cid:51) 1.1 What’s It All About? / 3 Sidebar:ResponsibleComputerUse / 5 1.2 Programming in Scheme / 5 1.3 An Application: Quilting / 15 (cid:67)(cid:72)(cid:65)(cid:80)(cid:84)(cid:69)(cid:82) (cid:50) (cid:82)(cid:101)(cid:99)(cid:117)(cid:114)(cid:115)(cid:105)(cid:111)(cid:110) (cid:97)(cid:110)(cid:100) (cid:73)(cid:110)(cid:100)(cid:117)(cid:99)(cid:116)(cid:105)(cid:111)(cid:110) (cid:50)(cid:50) 2.1 Recursion / 22 Sidebar:Exponents / 28 2.2 Induction / 28 2.3 Further Examples / 34 2.4 An Application: Custom-Sized Quilts / 40 (cid:67)(cid:72)(cid:65)(cid:80)(cid:84)(cid:69)(cid:82) (cid:51) (cid:73)(cid:116)(cid:101)(cid:114)(cid:97)(cid:116)(cid:105)(cid:111)(cid:110) (cid:97)(cid:110)(cid:100) (cid:73)(cid:110)(cid:118)(cid:97)(cid:114)(cid:105)(cid:97)(cid:110)(cid:116)(cid:115) (cid:52)(cid:56) 3.1 Iteration / 48 3.2 Using Invariants / 54 3.3 Perfect Numbers, Internal Definitions, and Let / 58 3.4 Iterative Improvement: Approximating the Golden Ratio / 61 3.5 An Application: The Josephus Problem / 65 Copyright © 1999 by Max Hailperin, Barbara Kaiser, and Karl Knight v vi Contents (cid:67)(cid:72)(cid:65)(cid:80)(cid:84)(cid:69)(cid:82) (cid:52) (cid:79)(cid:114)(cid:100)(cid:101)(cid:114)(cid:115) (cid:111)(cid:102) (cid:71)(cid:114)(cid:111)(cid:119)(cid:116)(cid:104) (cid:97)(cid:110)(cid:100) (cid:84)(cid:114)(cid:101)(cid:101) (cid:82)(cid:101)(cid:99)(cid:117)(cid:114)(cid:115)(cid:105)(cid:111)(cid:110) (cid:55)(cid:53) 4.1 Orders of Growth / 75 Sidebar:SelectionSort / 77 Sidebar:MergeSort / 78 Sidebar:Merging / 79 Sidebar:Logarithms / 82 4.2 Tree Recursion and Digital Signatures / 83 Sidebar:ModularArithmetic / 87 4.3 An Application: Fractal Curves / 95 (cid:67)(cid:72)(cid:65)(cid:80)(cid:84)(cid:69)(cid:82) (cid:53) (cid:72)(cid:105)(cid:103)(cid:104)(cid:101)(cid:114)(cid:45)(cid:79)(cid:114)(cid:100)(cid:101)(cid:114) (cid:80)(cid:114)(cid:111)(cid:99)(cid:101)(cid:100)(cid:117)(cid:114)(cid:101)(cid:115) (cid:49)(cid:48)(cid:57) 5.1 Procedural Parameters / 109 5.2 Uncomputability / 113 Sidebar:AlanTuring / 116 5.3 Procedures That Make Procedures / 118 5.4 An Application: Verifying ID Numbers / 120 (cid:80)(cid:65)(cid:82)(cid:84) (cid:73)(cid:73) (cid:68)(cid:97)(cid:116)(cid:97) (cid:65)(cid:98)(cid:115)(cid:116)(cid:114)(cid:97)(cid:99)(cid:116)(cid:105)(cid:111)(cid:110) (cid:67)(cid:72)(cid:65)(cid:80)(cid:84)(cid:69)(cid:82) (cid:54) (cid:67)(cid:111)(cid:109)(cid:112)(cid:111)(cid:117)(cid:110)(cid:100) (cid:68)(cid:97)(cid:116)(cid:97) (cid:97)(cid:110)(cid:100) (cid:68)(cid:97)(cid:116)(cid:97) (cid:65)(cid:98)(cid:115)(cid:116)(cid:114)(cid:97)(cid:99)(cid:116)(cid:105)(cid:111)(cid:110) (cid:49)(cid:51)(cid:51) 6.1 Introduction / 133 6.2 Nim / 135 6.3 Representations and Implementations / 143 Sidebar:NimProgram / 144 Sidebar:GameStateADTImplementation / 152 6.4 Three-Pile Nim / 153 6.5 An Application: Adding Strategies to Nim / 156 Sidebar:TypeChecking / 157 (cid:67)(cid:72)(cid:65)(cid:80)(cid:84)(cid:69)(cid:82) (cid:55) (cid:76)(cid:105)(cid:115)(cid:116)(cid:115) (cid:49)(cid:54)(cid:55) 7.1 The Definition of a List / 167 7.2 Constructing Lists / 169 7.3 Basic List Processing Techniques / 172 7.4 List Processing and Iteration / 179 7.5 Tree Recursion and Lists / 182 Contents vii 7.6 An Application: A Movie Query System / 187 Sidebar:IsThereMoretoIntelligenceThantheAppearanceof Intelligence? / 202 (cid:67)(cid:72)(cid:65)(cid:80)(cid:84)(cid:69)(cid:82) (cid:56) (cid:84)(cid:114)(cid:101)(cid:101)(cid:115) (cid:50)(cid:49)(cid:50) 8.1 Binary Search Trees / 212 8.2 Efficiency Issues with Binary Search Trees / 220 Sidebar:PrivacyIssues / 225 8.3 Expression Trees / 226 8.4 An Application: Automated Phone Books / 229 (cid:67)(cid:72)(cid:65)(cid:80)(cid:84)(cid:69)(cid:82) (cid:57) (cid:71)(cid:101)(cid:110)(cid:101)(cid:114)(cid:105)(cid:99) (cid:79)(cid:112)(cid:101)(cid:114)(cid:97)(cid:116)(cid:105)(cid:111)(cid:110)(cid:115) (cid:50)(cid:52)(cid:51) 9.1 Introduction / 243 9.2 Multiple Representations / 244 9.3 Exploiting Commonality / 253 9.4 An Application: Computer Graphics / 262 (cid:67)(cid:72)(cid:65)(cid:80)(cid:84)(cid:69)(cid:82) (cid:49)(cid:48) (cid:73)(cid:109)(cid:112)(cid:108)(cid:101)(cid:109)(cid:101)(cid:110)(cid:116)(cid:105)(cid:110)(cid:103) (cid:80)(cid:114)(cid:111)(cid:103)(cid:114)(cid:97)(cid:109)(cid:109)(cid:105)(cid:110)(cid:103) (cid:76)(cid:97)(cid:110)(cid:103)(cid:117)(cid:97)(cid:103)(cid:101)(cid:115) (cid:50)(cid:55)(cid:56) 10.1 Introduction / 278 10.2 Syntax / 279 Sidebar:TheExpressivenessofEBNF / 285 10.3 Micro-Scheme / 289 10.4 Global Definitions: Mini-Scheme / 303 10.5 An Application: Adding Explanatory Output / 311 (cid:80)(cid:65)(cid:82)(cid:84) (cid:73)(cid:73)(cid:73) (cid:65)(cid:98)(cid:115)(cid:116)(cid:114)(cid:97)(cid:99)(cid:116)(cid:105)(cid:111)(cid:110)(cid:115) (cid:111)(cid:102) (cid:83)(cid:116)(cid:97)(cid:116)(cid:101) (cid:67)(cid:72)(cid:65)(cid:80)(cid:84)(cid:69)(cid:82) (cid:49)(cid:49) (cid:67)(cid:111)(cid:109)(cid:112)(cid:117)(cid:116)(cid:101)(cid:114)(cid:115) (cid:119)(cid:105)(cid:116)(cid:104) (cid:77)(cid:101)(cid:109)(cid:111)(cid:114)(cid:121) (cid:51)(cid:51)(cid:51) 11.1 Introduction / 333 11.2 An Example Computer Architecture / 333 11.3 Programming the SLIM / 340 Sidebar:WhatCanBeStoredinaLocation? / 342 Sidebar:SLIM’sInstructionSet / 348 11.4 Iteration in Assembly Language / 349 11.5 Recursion in Assembly Language / 357 11.6 Memory in Scheme: Vectors / 361 11.7 An Application: A Simulator for SLIM / 367 viii Contents (cid:67)(cid:72)(cid:65)(cid:80)(cid:84)(cid:69)(cid:82) (cid:49)(cid:50) (cid:68)(cid:121)(cid:110)(cid:97)(cid:109)(cid:105)(cid:99) (cid:80)(cid:114)(cid:111)(cid:103)(cid:114)(cid:97)(cid:109)(cid:109)(cid:105)(cid:110)(cid:103) (cid:51)(cid:55)(cid:57) 12.1 Introduction / 379 12.2 Revisiting Tree Recursion / 380 12.3 Memoization / 388 12.4 Dynamic Programming / 398 12.5 Comparing Memoization and Dynamic Programming / 406 12.6 An Application: Formatting Paragraphs / 406 (cid:67)(cid:72)(cid:65)(cid:80)(cid:84)(cid:69)(cid:82) (cid:49)(cid:51) (cid:79)(cid:98)(cid:106)(cid:101)(cid:99)(cid:116)(cid:45)(cid:98)(cid:97)(cid:115)(cid:101)(cid:100) (cid:65)(cid:98)(cid:115)(cid:116)(cid:114)(cid:97)(cid:99)(cid:116)(cid:105)(cid:111)(cid:110)(cid:115) (cid:52)(cid:50)(cid:48) 13.1 Introduction / 420 13.2 Arithmetic Expressions Revisited / 421 13.3 RA-Stack Implementations and Representation Invariants / 432 Sidebar:StringsandCharacters / 433 13.4 Queues / 446 13.5 Binary Search Trees Revisited / 453 13.6 Dictionaries / 472 (cid:67)(cid:72)(cid:65)(cid:80)(cid:84)(cid:69)(cid:82) (cid:49)(cid:52) (cid:79)(cid:98)(cid:106)(cid:101)(cid:99)(cid:116)(cid:45)(cid:111)(cid:114)(cid:105)(cid:101)(cid:110)(cid:116)(cid:101)(cid:100) (cid:80)(cid:114)(cid:111)(cid:103)(cid:114)(cid:97)(cid:109)(cid:109)(cid:105)(cid:110)(cid:103) (cid:52)(cid:56)(cid:54) 14.1 Introduction / 486 14.2 An Object-orientedProgram / 487 14.3 Extensions and Variations / 511 14.4 Implementing an Object-orientedProg. System / 517 14.5 An Application: Adventures in the Land of Gack / 543 (cid:67)(cid:72)(cid:65)(cid:80)(cid:84)(cid:69)(cid:82) (cid:49)(cid:53) (cid:74)(cid:97)(cid:118)(cid:97)(cid:44) (cid:65)(cid:112)(cid:112)(cid:108)(cid:101)(cid:116)(cid:115)(cid:44) (cid:97)(cid:110)(cid:100) (cid:67)(cid:111)(cid:110)(cid:99)(cid:117)(cid:114)(cid:114)(cid:101)(cid:110)(cid:99)(cid:121) (cid:53)(cid:55)(cid:55) 15.1 Introduction / 577 15.2 Java / 578 15.3 Event-Driven Graphical User Interfaces in Applets / 599 15.4 Concurrency / 616 Sidebar:NestedCallstoSynchronizedMethodsandDeadlock / 625 15.5 An Application: Simulating Compound Interest / 632 (cid:65)(cid:80)(cid:80)(cid:69)(cid:78)(cid:68)(cid:73)(cid:88) (cid:78)(cid:111)(cid:110)(cid:115)(cid:116)(cid:97)(cid:110)(cid:100)(cid:97)(cid:114)(cid:100) (cid:69)(cid:120)(cid:116)(cid:101)(cid:110)(cid:115)(cid:105)(cid:111)(cid:110)(cid:115) (cid:116)(cid:111) (cid:83)(cid:99)(cid:104)(cid:101)(cid:109)(cid:101) (cid:54)(cid:52)(cid:53) (cid:66)(cid:105)(cid:98)(cid:108)(cid:105)(cid:111)(cid:103)(cid:114)(cid:97)(cid:112)(cid:104)(cid:121) (cid:54)(cid:52)(cid:57) (cid:73)(cid:110)(cid:100)(cid:101)(cid:120) (cid:54)(cid:53)(cid:51) (cid:80)(cid:114)(cid:101)(cid:102)(cid:97)(cid:99)(cid:101) At first glance, the title of this book is an oxymoron. After all, the term abstraction referstoanideaorgeneraldescription,divorcedfromphysicalobjects.Ontheother hand, something is concrete when it is a particular object, perhaps something that you can manipulate with your hands and look at with your eyes. Yet you often deal with concrete abstractions. Consider, for example, a word processor. When you use a word processor, you probably think that you have really entered a document into thecomputerandthatthecomputerisamachinewhichphysicallymanipulatesthe words in the document. But in actuality, when you “enter” the document, there is nothing new inside the computer—there are just different patterns of activity of electrical charges bouncing back and forth. Moreover, when the word processor “manipulates” the words in the document, those manipulations are really just more patternsofelectricalactivity.Eventheprogramthatyoucalla“wordprocessor”isan abstraction—it’sthewaywehumanschoosetotalkaboutwhatis,inreality,yetmore electrical charges. Still, although these abstractions such as “word processors” and “documents”aremerelyconvenientwaysofdescribingpatternsofelectricalactivity, they are also things that we can buy, sell, copy, and use. As you read through this book, we will introduce several abstract ideas in as concrete a way as possible. As you become familiar and comfortable with these ideas, you will begin to think of the abstractions as actual concrete objects. Having already gone through this process ourselves, we’ve chosen to call computer science “the discipline of concrete abstractions”; if that seems too peculiar to fathom, we invite you to read the book and then reconsider the notion. This book is divided into three parts, dealing with procedural abstractions, data abstractions, and abstractions of state. A procedure is a way of abstracting what’s calledacomputationalprocess.Roughlyspeaking,aprocessisadynamicsuccession of events—a happening. When your computer is busy doing something, a process ix x Preface is going on inside it. When we call a process a computational process, we mean that we are ignoring the physical nature of the process and instead focusing on the information content. For example, consider the problem of conveying some information to a bunch of other people. If you think about writing the message on paper airplanes and tossing it at the other people, and find yourself considering whethertheairplaneshaveenoughlifttoflyfarenough,thenyouareconsideringa mechanical process rather than a computational one. Similarly, if you think about usingthephone,andfindyourselfworryingaboutthecurrentcarryingcapacityofthe copper wire, you are considering an electrical process rather than a computational one. On the other hand, if you find yourself considering the alternative of sending your message (whether by phone or paper airplane) to two people, each of whom send it to two more, each of whom send it to two more, and so forth, rather than directly sending the message to all the recipients, then you are thinking about a computational process. Whatdocomputerscientistsdowithprocesses?Firstofall,theywritedescriptions of them. Such descriptions are often written in a particular programming language andarecalledprocedures.Theseprocedurescanthenbeusedtomaketheprocesses happen. Procedures can also be analyzed to see if they have been correctly written or to predict how long the corresponding processes will take. This analysis can then be used to improve the performance or accuracy of the procedures. In the second part of the book, we look at various types of data. Data is the information processed by computational processes, not only the externally visible information, but also the internal information structures used within the processes. First, we explore exactly what we mean by the term data, concentrating on how we use data and what we can do with it. Then we consider various ways of gluing small pieces of atomic data (such as words) into larger, compound pieces of data (such as sentences). Because of our computational viewpoint, we write procedures to manipulate our data, and so we analyze how the structure of the data affects the processes that manipulate it. We describe some common data structures that are used in the discipline,and show how to allow disparatestructures to be operatedon uniformly in a mix-and-match fashion. We end this part of the book by looking at programs in a programming language as data structures. That way, carrying out the computational processes that a program describes is itself a process operating on a data structure, namely the program. We start the third part of the book by looking at computational processes from the perspective of the computer performing the computation. This shows how pro- cedurally described computations actually come to life, and it also naturally calls attention to the computer’s memory, and hence to the main topic of this part, state. State is anything that can be changed by one part of a computation in order to have an effect on a later part of the computation. We show several important uses for state: making processes model real-world phenomena more naturally, making processes that are more efficient than without state, and making certain programs