For the latest version of this book and supplementary materials, visiVersion: August 19, 20ca creativeIonsAttribution-Noncommercial-Share Alike 3
0 United States License
Computinghistory of mankinEdsger Dijkstra, 1972 Turing Award Lectureit harder We have developed tools that amplify physical force by the trillionsby thdeveloped tools to amplify their physical abilities, only humans have developedellectual abilitiesthat have enabled humans to dominate the planet The first key intellect amplifier was language Language provided the ability to transmit our thoughts toothers, as well as to use our own minds more effectively
The next key intellectme and distanceComputing is the ultimate mening Computing has changed the world more than any other invention of thepast hundred years, and has come to pervade nearly all hiYewe are just at the beginning of the computing revolution; todaya glimpse of the potentialThere are twoons why everyone should study computingNearly all of the most exciting adriveportant technologies, arts, and sci- Ag forms ar theUnderstanding computing illuminates deep insights and questions intohe natureculture, andIverseeye surwho has submitted a query to Google, watched Tooy Story, had LASIK teach them to readurgery, used a smartphone, seen a Cirque Du Soleil show, shopped with aose of allowingcard, or microwaved a pizza should be convinced of the first reason Nonef these would be possible without the tremendous advances in computingne past half centuideasLockhartAlthough this book will touch onon some exciting applications of computing,our primary focus is on the seceason, which may seem more surprising
Processes, Procedures, and ComputersComputing changes how we think about problems and how we understand theTheof this book is1 Processes, Procedures, and Computersnformation Computer science is the study of information processes A process is a sequenceprocesses of steps Each step changes the state of the world in some small way, and thesult of all the steps produces some goal state For example, baking a cake,iling a letter, and planting a tree are all processes Because they involve physcomprgs like sugar and dirt, however, they are not pure information processesson processes tholve abstract information ratherthan physical thingsThe boundaries between the physical world and pure information processes,however, are often fuzzy Real computers operate in the physical world: thes(eg, a user pressing a key on a keyboarage displayed on a screen) By focusing on abstractphysical ways of representing and manipulating informaticbetter enable understanding and reasoningprocedure A procedure is a description of a process
A simple process can be describedust by listing the steps The list of steps is the procedure: the act of followingthem is the process A palgorithmre that can be followed without any re that isd a mechanical procedure an algorithm is a mechanical procedure that isteed tolally finishFor example, here is a procedure for making coffee, adapted from the actualcian is directions that coErdosClose the lidPlace the empty decanter on thePress the on biDescribing processes by just listing steps like this has many limitations First,turald ambires knowing lots of unstated assumptions For example, step threees the operator understands the difference betweds andfinished coffee, and can infer that this use of coffee"refers toeoundssince the end goal of this process is to make drinkable coffee Other steps asaker is plugged in and sittingOne could, of course, add lots more details to our procedure and make the language more precise than this Even when a lot of effort is put into writing preabiguous This is why the United States tax code is 3 4 million words long, butweyers canpend years arguing over whaeally meansnother problem with this way of describing a procedure is that the size of the
C3description is proportional to the number of steps in the process This is fithat can be executed by humansf time, but theses we want to execute on computers involve trillions ofeps Thiss we need more efficient ways to describe them than just listingd toolallow us to describenctly Since thedures are carried out by a machine, everyep needs to be describedense"(for example, to know how to fill the coffeemaker with water without explaining that water comes from a faucet, and how to turn the faucet on) Instead,we need mechanical procedures that can be followed without any thinkingachine that cand be entered by a human typing at a keyboard,eceived over a network, or provided automatically by sensors attached toheExecute a mechanical procedure, that is, a procedure where each stee executed withoProduce output Output could be data displayed to a human, but it coulder such astrical signals that control how a device operatesComputers exist in a wide range of forms, and thousands of computers areen devices wday but don 't think ofhones, TVs, microwave ovens, and access cards Our primary focus is on uniersal computers, whieperform all possibleal computations on discrete inputs except for practical limits on space and mind andhngys"chetime
the next section eat it discrete inputs means: Chapexplore more deeply what it means for a computer to be univers2 Measuring Computing poweral machines, we can compare the power of different machineseasuring the amount of mechanical work they can perform within a givenamount of time This power can be captured with units like hwatt Physical power is not a very useful measure of computing phieved for thegreatly Energy is consumed when a corcomputerputer operates, but constIwo properties that measure the power of a computing machineHow much informationHow fast cae defer considering the second property until Part Il, but consider the first121 InformationInformally, we use information to mean knowledge But to understand informa- informationtion quantitatively, as something we can measure, we need a more precise wayo think abou
1 2 Measuring Computing PowerThe way computer scientists measure information is based on how what is knownobtaining the infobit tion is a bit One bit of information halves the amount ofuncertainty It is equivng the answer, there is obinary question
Since a bite perform a fatoss but do not reveal the resultHalf of the time the coin will land"heads", and the other half of the time thetails" without krcorrect answer are One bit of informationeither heads"or"tails" we caSimilarly one bit can distinguish between the values 0 andYthTheredentify the actual number, since one bit can only distinguish bnot enoughd use fivThis is quite inefficient, though, since we need up to five questions to identifythe value(and on average, expect to need 33 questions) Can we identify the
COur goal is to identify questions where the"yes"and"no" answers are equallyovides the most infore thisot the case if we start with, "Is the value 6? " since that answer is expected to bee timealue at least 42 Herexpect theequally likely If the answer is"yes", we knowult is 4, 5, or 6 With two more bits, we can distinguish between thesalues(note that two bits is actually enough to distinguish among fourme information is wasted here) Similarly, if thefirst question is no, we know the result is 1, 2, or 3 We need two morebits to distinguish which of the three values it is Thus, with three bits, we cadistinguish all six possible outcomes5Three bits can convey more information that just sixe binary question tree, there are some questions where the answeot equally likely to be"yes"and"no"(for example, we expect the answer tothe value 3be " yese out of three times) Hence, we are nobtaining a full bit ofbits we can distinguish between 2* 2*2-8 possibilities
In general, withwe can distinguish between 2 possibilities Conversely, distinguishing among kssible values requires logogarithm is defined such that if a= b logarithmthen loghSince each bit hasbilities, we use theto determine the number of bitsto distinguish among a set of distinctbinary questions But, questions are discrete: we can't ask 058 of a question, soinary queTrees Figure 11 depicts a structure of binary questions flong eight values We call this structure a binary tree We will see many useful binary trees of tree-Computer scientists draw trees upside down, The root is the top of the tree, andthe leaves are the numbers at the bottom(o) There is a unique paththe tree to each leaf Thus, we can describe each of the eigl
1 2 Measuring Computing Povible values using thers to the questions down the tree fNo",“No",and“Neaf 5 Since theall this a binary treeWe can describe any non-negativethis way, by just addingadditional levelse tree Foed to distinguish between6 possibluld add a newumbers between 0 and 7 if the answer is"Yesimilar to theath The depth of a tree is the length of theth from theeaf Theexample tree has depth three
A binary tree of depth d can distinguish up to 2ere0357Figure ll Usin
g three bits to distinguish eight possible valuesUnits of Information One byte is defined as eight bits Hence, one byte ofinformation corresponds to eight binary quesand can distinguish among28(256)different values For larger amounts of information, we use metric prefixes, but instead of scaling by factors of 1000 theyf20(1024lence, one kilobyte is 1024 bytes; one megabyte is 24(approximatelyon) bytes; one gigabyte is 2(approximately one billion) bytes; and one ter-abyte is 240(approximately one trillion) bytesExercise 1 1 Draw a binary tree with the minimum possible depth toths of the yearCExercise 12 How many bits are neededhumd To uniquely identify any atom in the observable universe?Exercise 13 The examples all use binary questions for which there are twossible answers Suppose insteadg our decisions on bits we baseon trits where one trit can distinguish between three equally likely values Foach trit we can askernary qu(a question with three possible answersany trits are needed to distinguishconvincing answer would show a ternary tree with the questions and answersIsb* Devise a general formula for converting between bits and trits
How manyExploration 11: GuesTheer(the chooser) pickingber between I and 100 (inclusive)and secretly writing it down The other playere guesser)attempts to guess the number After each guess, the choosersponds with"correct"(the guesser guessed the number and the game is over)higher"(the actual number is higher than theower"(theExplain why the gslightlye bit of informatib Assuming the chooser picks theer randomly(that is, all values betweenI and 100 are equally likely), what are the best first guesses? Explain whyhese guesses are better than any other guess(Hint: there are two equallyc What is the maximum number of guesses the second player should needfind the numbd what is the average number of guesses needed (assuming the chooser pickse* Suppose instead of picking randomly, the chooser picks the number withthe goal ofizing the number of guesses the second player will needld she pick?fHow should the guesser adjust her strategy if sheIsking adversariallyg ** What are the best strategies for both players in the adversarial guess-anumber game where choosers goal is to pick a starting number that maxmizes the number of guesses the guesser needs, and the guesser's goal is to
Contents22 Representing Data23 Growth of Computing Powerg, and the liberal Arts22 Language Constructio990223 Recursive Transition Networks3 1 Problems with Natural languages32 Programming Languages33 Scheme341 Primitives3
42 Application Expressions4 Problems and Procedures41 Solving ProblemsProcedure21 Procedures as Inputs and Outputs43 Recursive problem solving44 Evaluating Recursive Applications45 Developing Complex Program451Pri
452 Tracing46Si5 Data52 Pairs521 Making Pairse lists43 Procedures that Construct Lists5
6 Data AbstractionPart II: Analyzing ProceduresHistory of Computing Machines62 Mechanizing Logic622Cg Operations1163 Mode64 Summary7 1 Empirical Measurements222n3311222233336674444dratic growther than Exponential Growth33344444446 Non-terminating proceduresSorting and searching153
813 Quicker Sorting588 1 4 Binary Trees815 QuicksortUnstructured search6788dexed SearchPart Ill: Improving Expressiveness9 Mutation2 Impact of MutationNames, Places, Frames, and Environments922 Evaluation Rules with State93 Mutable pairs and Lists9 4 Imperative pr942 Imperative Control Structures0 Objects0
1 Packaging Procedures and State66668688980 1 1 Encapsulation10 1, 2 Messages0 2 1 Implementing SubclassesOverriding methods03 Object-Oriented ProgrammingPython ProgramsIs and Invocations4 Control Statements3 Evaluator33 Definitions and Names35 Application36 Finishing the Interprete4 Lazy evaluati1 41 Lazy Interpreter4 2 Lazy Programming
5 SummaPart IV: The Limits of Computing2C2 1 Mechanizing reasoningdels incompleteness theorey24022 The halting proble2
4 Proving Non-Computability4525 SummaryIne53253List of explorationsPower of Language Systemsrecipes for丌3 Recursive definitions and games5board puzzleWebDetList of Figurespletransition networkn network with subnetworks5 RTNting“ Alice runs26 System power relationshipsroduc8 Converting the MoreDigits productions to an rTN
3 1 Running a Scheme program4e maps inputs to an outpu42 Composition43 Circular Composi44 Recursive Composition5 Corneri5 1 Pegboard PuzzleComputing and with wine62 Comig logical or and not with wine63 Computing and3 by composing two and functions65 Rules for checking balanced parentheses Turing Machine66 Checking parer7
1 Evaluation of fibo7 2 Visualization of the sets O(), Q(), and O()73 Orders of growth91 Sarenvironments92 Envirbigger 3 493 Environment after evaluating(define inc(make- adder 1))9 4 Envirent for ee body of (inc 149)95 Mutable pair created by evaluating(set-mcdr! pair pair9 6 Mutablelistby evaluating(mlist 1 2 3)6770 1 Environment produced by evaluating02 Inheritance hierarch103 Counter class hierar21 Incote and inconsistent axiomatic23 Two-state Busy beaver Machine
st of the images in the book, including the tiles on the cover, were generatedSome of the tile images on the cover are from flickr creative commons licensesfe, Dunechaser, MichaelFitz, Wolfie Fox, glingl, jurvetson, KayVee INC, michaeldThe Van Gogh Starry Night image from Section 122 is fromoogle ArtProject The Apollo Guidance Computer image in Section 1 23 was released byNASA and is in the public domain The traffic light in Section 2
1 is from iStockPhoto, and the rotary traffic signal is from the wikimedia Commons The pice of Grace Hopper in Chapter 3 is from the Computer History Museplaying card images in Chapter 4 are from iStockPhoto The images of GaussHeron, and Grace HoppChapter 4 is licensed from United Feature Syndicate, Inc The Pascal's trianglof Ada Lovelace in Chapter 6 is from the Wikimedia Commons, of a painting byThe odometer image in Chapter 7 is from iStockPhethe image of the frustrated student The Python snake charmer in Section 111 ism iStockPhoto The Dynabook images at theof chapter lfrom alanay's paper The xked comic at the end of Chapter 1l is used under the creativeRandall mi
PrefaceThis book started from the premise that Computer Science should be taught asliberal art, not an industrial skill, I had the privilege of taking 6001 from GerrySussman when I was a first year student at MIT, and that course awakened mthe power and beautyg, and inspired me to pursue ad researcher in Computer Science When I arrived as a new facultyf vidistraught to discover thatthe introductory computing courses focused on teaching industrial skills, andtime devoted to explaining the technical complexiany, time left to get acrossng Fellowship and National Sdation grantsed a new introductory computer science course, tarfirst offered in Spring 2002, with the help of an extraordinary group of AssistantCoaches
because of somepuonthe firsthalf the studend the course but a small, intrepidis thanks to their efforts that this book existshat course, and the next several offerings, used abelson Sussmans outstandg Structure and Interpretation of Computer Programs(SICP) textbook alongDouglas Hofstadters Godel, Escher, Bach: An Eternal Golden braid鷙Hargaictor Clay Yountront: Grace Deng, Rachel Dada, Jon Erdman (Assistant Coachalone in thinking SICP is perhaps the greatest textbook ever writteo it was with much trepidation that I endeavored to develop a newhope the resulting book captures the spirimutinyified by SICP, but better suited to an introductory course for studentspics not included in SICPnalysis, objects, andability, Althoughis book is designed around a one semester introductory course, it should alsobe suitable for self-study students and for people with substantial programminexperience but without similar computer science knowledge
I am indebted to many people who helped develop this course and book Wesey weithe first person to teachthingbling this bookand his thorough and insightful feedback led to improvements throughout
GregHumphreys, Paul Reynolds, and Mark Sherriff have also taughtankful to all of the assitant Coaches over the years, especially Sarah Bergkuist (2004), Andrew Connors(2004), Rachel Dada(2003), Paul DiOrio(2an(2002), Ethan Fast(2009), David Faulkner(2005), Jacques Fournier(2003)chard Hsu(2007), Rachel Lathbury (2009), Michael Lew(2009), Stephen Lia2002), Dan Marcus(2007), Rachel Rater(2009), Spencer Stockdale(2003), DanUpton(2005), Portman Wills(2002), Katie Winstanley(2003 and 2004), and Rebecca Zapfel (2009) William Aiello, Anna Chefter, Chris Frost, Jonathan grierThad Hughes, Alan Kay, Tim Koogle, Jerry McGann, Gary McGraw, Radhika NagShawn O'Hargan, Mike Peck, and Judith Shatin also made important conu, y deepest thanks are to my wife, Nora, who is a constantally, my thanks to all past, present, and future students who use this bookAugust 201