WIXLIB

Introduction toComputingExplorations inLanguage, Logic, and MachinesDavid EvansUniversity of Virginia

For the latest version of this book and supplementary materials, visit:http://computingbook.orgVersion: August 19, 2011Attribution-Noncommercial-Share Alike 3.0 United States License

Contents1 Computing1.1 Processes, Procedures, and Computers . .1.2 Measuring Computing Power . . . . . . .1.2.1 Information . . . . . . . . . . . . .1.2.2 Representing Data . . . . . . . . .1.2.3 Growth of Computing Power . . .1.3 Science, Engineering, and the Liberal Arts1.4 Summary and Roadmap . . . . . . . . . .12338121316Part I: Defining Procedures2 Language2.1 Surface Forms and Meanings2.2 Language Construction . . . .2.3 Recursive Transition Networks2.4 Replacement Grammars . . .2.5 Summary . . . . . . . . . . . .1919202226323 Programming3.1 Problems with Natural Languages . . . .3.2 Programming Languages . . . . . . . . .3.3 Scheme . . . . . . . . . . . . . . . . . . .3.4 Expressions . . . . . . . . . . . . . . . . .3.4.1 Primitives . . . . . . . . . . . . .3.4.2 Application Expressions . . . . .3.5 Definitions . . . . . . . . . . . . . . . . .3.6 Procedures . . . . . . . . . . . . . . . . .3.6.1 Making Procedures . . . . . . . .3.6.2 Substitution Model of Evaluation3.7 Decisions . . . . . . . . . . . . . . . . . .3.8 Evaluation Rules . . . . . . . . . . . . . .3.9 Summary . . . . . . . . . . . . . . . . . .35363739404041444545464850524 Problems and Procedures4.1 Solving Problems . . . . . . . . . . . . . .4.2 Composing Procedures . . . . . . . . . . .4.2.1 Procedures as Inputs and Outputs4.3 Recursive Problem Solving . . . . . . . . .4.4 Evaluating Recursive Applications . . . . .4.5 Developing Complex Programs . . . . . .4.5.1 Printing . . . . . . . . . . . . . . . .5353545556646768.

4.5.2 Tracing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 Data5.1 Types . . . . . . . . . . . . . . . . . . .5.2 Pairs . . . . . . . . . . . . . . . . . . . .5.2.1 Making Pairs . . . . . . . . . . .5.2.2 Triples to Octuples . . . . . . .5.3 Lists . . . . . . . . . . . . . . . . . . . .5.4 List Procedures . . . . . . . . . . . . .5.4.1 Procedures that Examine Lists .5.4.2 Generic Accumulators . . . . .5.4.3 Procedures that Construct Lists5.5 Lists of Lists . . . . . . . . . . . . . . .5.6 Data Abstraction . . . . . . . . . . . . .5.7 Summary of Part I . . . . . . . . . . . .6973.75. 75. 77. 79. 80. 81. 83. 83. 84. 86. 90. 92. 102.1051061081091111141161181237 Cost7.1 Empirical Measurements . . . . . . . .7.2 Orders of Growth . . . . . . . . . . . .7.2.1 Big O . . . . . . . . . . . . . . .7.2.2 Omega . . . . . . . . . . . . . .7.2.3 Theta . . . . . . . . . . . . . . .7.3 Analyzing Procedures . . . . . . . . . .7.3.1 Input Size . . . . . . . . . . . .7.3.2 Running Time . . . . . . . . . .7.3.3 Worst Case Input . . . . . . . .7.4 Growth Rates . . . . . . . . . . . . . . .7.4.1 No Growth: Constant Time . .7.4.2 Linear Growth . . . . . . . . . .7.4.3 Quadratic Growth . . . . . . . .7.4.4 Exponential Growth . . . . . . .7.4.5 Faster than Exponential Growth7.4.6 Non-terminating Procedures .7.5 Summary . . . . . . . . . . . . . . . . 49149Part II: Analyzing Procedures6 Machines6.1 History of Computing Machines6.2 Mechanizing Logic . . . . . . .6.2.1 Implementing Logic . .6.2.2 Composing Operations .6.2.3 Arithmetic . . . . . . . .6.3 Modeling Computing . . . . . .6.3.1 Turing Machines . . . .6.4 Summary . . . . . . . . . . . . .8 Sorting and Searching1538.1 Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1538.1.1 Best-First Sort . . . . . . . . . . . . . . . . . . . . . . . . . . 1538.1.2 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . 157

8.1.3 Quicker Sorting . . .8.1.4 Binary Trees . . . . .8.1.5 Quicksort . . . . . . .8.2 Searching . . . . . . . . . . .8.2.1 Unstructured Search8.2.2 Binary Search . . . .8.2.3 Indexed Search . . .8.3 Summary . . . . . . . . . . .1581611661671681681691789 Mutation9.1 Assignment . . . . . . . . . . . . . . . . . . . . . . .9.2 Impact of Mutation . . . . . . . . . . . . . . . . . .9.2.1 Names, Places, Frames, and Environments9.2.2 Evaluation Rules with State . . . . . . . . .9.3 Mutable Pairs and Lists . . . . . . . . . . . . . . . .9.4 Imperative Programming . . . . . . . . . . . . . . .9.4.1 List Mutators . . . . . . . . . . . . . . . . . .9.4.2 Imperative Control Structures . . . . . . . .9.5 Summary . . . . . . . . . . . . . . . . . . . . . . . .17917918118218318618818819119310 Objects10.1 Packaging Procedures and State .10.1.1 Encapsulation . . . . . . .10.1.2 Messages . . . . . . . . . .10.1.3 Object Terminology . . . .10.2 Inheritance . . . . . . . . . . . . .10.2.1 Implementing Subclasses10.2.2 Overriding Methods . . .10.3 Object-Oriented Programming .10.4 Summary . . . . . . . . . . . . . .Part III: Improving Expressiveness.19519619619719920020220420720911 Interpreters11.1 Python . . . . . . . . . . . . . . . . .11.1.1 Python Programs . . . . . . .11.1.2 Data Types . . . . . . . . . . .11.1.3 Applications and Invocations11.1.4 Control Statements . . . . . .11.2 Parser . . . . . . . . . . . . . . . . . .11.3 Evaluator . . . . . . . . . . . . . . . .11.3.1 Primitives . . . . . . . . . . .11.3.2 If Expressions . . . . . . . . .11.3.3 Definitions and Names . . . .11.3.4 Procedures . . . . . . . . . . .11.3.5 Application . . . . . . . . . .11.3.6 Finishing the Interpreter . . .11.4 Lazy Evaluation . . . . . . . . . . . .11.4.1 Lazy Interpreter . . . . . . . .11.4.2 Lazy Programming . . . . . 32.

11.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235Part IV: The Limits of Computing12 Computability12.1 Mechanizing Reasoning . . . . . . . . .12.1.1 Gödel’s Incompleteness Theorem12.2 The Halting Problem . . . . . . . . . . .12.3 Universality . . . . . . . . . . . . . . . .12.4 Proving Non-Computability . . . . . . .12.5 Summary . . . . . . . . . . . . . . . . . .237237240241244245251Indexes253Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253People . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256List of Guessing Numbers . . . . . . . .Twenty Questions . . . . . . . . .Power of Language Systems . . .Square Roots . . . . . . . . . . . .Recipes for π . . . . . . . . . . . .Recursive Definitions and GamesPascal’s Triangle . . . . . . . . . .Pegboard Puzzle . . . . . . . . . .Multiplying Like Rabbits . . . . .Searching the Web . . . . . . . .Virus Detection . . . . . . . . . .Busy Beavers . . . . . . . . . . . .782962697191931271772462491.1 Using three bits to distinguish eight possible values. . . . . . . . . . .6List of Figures2.12.22.32.42.52.62.72.82.9Simple recursive transition network. . . . . . . . .RTN with a cycle. . . . . . . . . . . . . . . . . . . .Recursive transition network with subnetworks. .Alternate Noun subnetwork. . . . . . . . . . . . . .RTN generating “Alice runs”. . . . . . . . . . . . . .System power relationships. . . . . . . . . . . . . .Converting the Number productions to an RTN. .Converting the MoreDigits productions to an RTN.Converting the Digit productions to an RTN. . . .222324242530313132

3.1 Running a Scheme program. . . . . . . . . . . . . . . . . . . . . . . . .394.14.24.34.44.5.54545758725.1 Pegboard Puzzle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .936.16.26.36.46.56.6A procedure maps inputs to an output.Composition. . . . . . . . . . . . . . .Circular Composition. . . . . . . . . .Recursive Composition. . . . . . . . .Cornering the Queen. . . . . . . . . . .Computing and with wine. . . . . . . . . . . . . . . . . . . .Computing logical or and not with wine . . . . . . . . . . .Computing and3 by composing two and functions. . . . .Turing Machine model. . . . . . . . . . . . . . . . . . . . . .Rules for checking balanced parentheses Turing Machine. .Checking parentheses Turing Machine. . . . . . . . . . . .1101111121191211217.1 Evaluation of fibo procedure. . . . . . . . . . . . . . . . . . . . . . . . 1287.2 Visualization of the sets O( f ), Ω( f ), and Θ( f ). . . . . . . . . . . . . . 1307.3 Orders of Growth. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1318.1 Unbalanced trees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1659.19.29.39.49.59.6Sample environments. . . . . . . . . . . . . . . . . . . . . .Environment created to evaluate (bigger 3 4). . . . . . . . .Environment after evaluating (define inc (make-adder 1)).Environment for evaluating the body of (inc 149). . . . . . .Mutable pair created by evaluating (set-mcdr! pair pair). .MutableList created by evaluating (mlist 1 2 3). . . . . . . .18218418518618718710.1 Environment produced by evaluating: . . . . . . . . . . . . . . . . . . 19710.2 Inheritance hierarchy. . . . . . . . . . . . . . . . . . . . . . . . . . . . 20110.3 Counter class hierarchy. . . . . . . . . . . . . . . . . . . . . . . . . . . 20612.1 Incomplete and inconsistent axiomatic systems. . . . . . . . . . . . . 23912.2 Universal Turing Machine. . . . . . . . . . . . . . . . . . . . . . . . . . 24512.3 Two-state Busy Beaver Machine. . . . . . . . . . . . . . . . . . . . . . 249

Image CreditsMost of the images in the book, including the tiles on the cover, were generatedby the author.Some of the tile images on the cover are from flickr creative commons licensesimages from: ell brown, Johnson Cameraface, cogdogblog, Cyberslayer, dmealiffe, Dunechaser, MichaelFitz, Wolfie Fox, glingl, jurvetson, KayVee.INC, michaeldbeavers, and Oneras.The Van Gogh Starry Night image from Section 1.2.2 is from the Google ArtProject. The Apollo Guidance Computer image in Section 1.2.3 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 picture of Grace Hopper in Chapter 3 is from the Computer History Museum. Theplaying card images in Chapter 4 are from iStockPhoto. The images of Gauss,Heron, and Grace Hopper’s bug are in the public domain. The Dilbert comic inChapter 4 is licensed from United Feature Syndicate, Inc. The Pascal’s triangleimage in Excursion 5.1 is from Wikipedia and is in the public domain. The imageof Ada Lovelace in Chapter 6 is from the Wikimedia Commons, of a painting byMargaret Carpenter. The odomoter image in Chapter 7 is from iStockPhoto, as isthe image of the frustrated student. The Python snake charmer in Section 11.1 isfrom iStockPhoto. The Dynabook images at the end of Chapter 10 are from AlanKay’s paper. The xkcd comic at the end of Chapter 11 is used under the creativecommons license generously provided by Randall Munroe.

PrefaceThis book started from the premise that Computer Science should be taught asa liberal art, not an industrial skill. I had the privilege of taking 6.001 from GerrySussman when I was a first year student at MIT, and that course awakened meto the power and beauty of computing, and inspired me to pursue a career asa teacher and researcher in Computer Science. When I arrived as a new facultymember at the University of Virginia in 1999, I was distraught to discover thatthe introductory computing courses focused on teaching industrial skills, andwith so much of the course time devoted to explaining the technical complexities of using

a liberal art, not an industrial skill. I had the privilege of taking 6.001 from Gerry Sussman when I was a first year student at MIT, and that course awakened me to the power and beauty of computing, and inspired me to pursue a career as a teacher and researcher in Computer Science. When I arrived as a new faculty member at the University of Virginia in 1999, I was distraught to discover .