计算的本质 深入剖析程序和计算机(Understanding Computation) O'reilly英文原版0积分

计算的本质-深入剖析程序和计算机（Understanding Computation）-O'reilly英文原版，0积分Understanding ComputationTom stuart○ REILLYBeijing· Cambridge: Farnham·Koln· Sebastopol· TokyoUnderstanding computationby Tom StuartCopyright C 2013 Tom Stuart. All rights reservedPrinted in the United States of americaPublished by O'Reilly Media, Inc, 1005 Gravenstein Highway North, Sebastopol, CA 95472O' Reilly books may be purchased for educational, business, or sales promotional use Online editionsarealsoavailableformosttitles(http://my.safaribooksonline.com).Formoreinformationcontactourcorporate/institutionalsalesdepartment800-998-9938orcorporate@oreilly.comEditors: Mike Loukides and Nathan JepsonIndexer: Lucie haskinsProduction Editor: Christopher HearseCover Designer: Randy ComerCopyeditor: Rachel LeachInterior Designer: David FutatoProofreader: Linley dolbIllustrator: Rebecca DemarestMay 2013First editionRevision history for the first Edition2013-05-10 First release2013-05-31Second releaseSeehttporeillycom/catalog/errata.cspisbn=9781449329273forreleasedetailsNutshell Handbook, the Nutshell Handbook logo, and the O'Reilly logo are registered trademarks oO'Reilly media, Inc. Understanding computation, the image of a bear paw clam, and related trade dressare trademarks of O'Reilly Media, IncMany of the designations used by manufacturers and sellers to distinguish their products are claimed astrademarks. Where those designations appear in this book, and O Reilly mediawas aware of atrademark claim, the designations have been printed in caps or initial capsWhile every precaution has been taken in the preparation of this book, the publisher and authors assumeno responsibility for errors or omissions, or for damages resulting from the use of the information con-tained hereinISBN:978-1-449-32927-31369775863Table of contentsPreface1. Just Enough RubyInteractive Ruby shellValBasic dataData structuresControl flowObjects and MethodsClasses and modulesMiscellaneous featuresLocal variables and assignmentString InterpolationInspecting objects456778889Printing StringsVariadic methodsBlocksEnumerable10StructMonkey patchingDefining constantsRemoving ConstantsPart 1. Programs and machines2. The Meaning of ProgramsThe meaning of"Meaning18yntaxOperational Semantics20Small-Step semantics21Big-Step semanticsDenotational semanticsXpressions49Statements52Applications54Formal semantics in practiceFormality55Finding Meaning56AlternatiⅤesImplementing Parsers583. The SimplestDeterministic finite automata63States, Rules, and Input63Output64DeterminismSimulationNondeterministic Finite automata69Nondeterminism70Free moves76Regular expressionsSyntaxSemantics83arsing92Equivalence944. Just add power105Deterministic Pushdown automata108Storage108RIules110Determinism111Simulation112Nondeterministic Pushdown Automata118Simulation122nonequivalence125Parsing with Pushdown Automata125Lexical analysis126Syntactic Analysis128Practicalities132How Much power?5. the ultimate machineDeterministic Turing Machines135iv Table of ContentsStorage136R138Determinism141Simulation141Nondeterministic Turing machines147Maximum power148Internal Storage148Subroutines151Multiple tapes153Multidimensional tape154General-Purpose machines154Encoding156Simulation157Part computation and computabilityProgramming with Nothing161Impersonating the Lambda Calculus162Working with Procs163The proble166BooleansPredicates172Pairs173Numeric Operations174Lists180Strings184The solution186Advanced Programming Techniques191Implementing the Lambda calculus197Semantics199Parsin2047. Universality ls EverywhereLambda calculus207Partial recursive functions210SKI Combinator calculus215224g227Cyclic Tag Systems235Conway's Game of Life245Table of contentsRule 110247Wolfram's 2, 3 Turing machine2518. Impossible programs253The Facts of life254Universal Systems Can Perform algorithms254Programs Can Stand In for Turing machines257Code is data258Universal Systems Can Loop Forever259Programs Can Refer to Themselves264Decidability269The Halting Problem271Building a Halting Checker271It ll Never Work274Other Undecidable problems277Depressing implications280Why Does This Happen?282Coping with Uncomputability2839. Programming in toyland285Abstract Interpretation286Route Planning286Abstraction: Multiplying Signs287Safety and Approximation: Adding Signs290Static semantics295Implementation296Benefits and limitations303Applications305Afterword∴,307Index309I Table of ContentsPrefaceWho should read this book?This book is for programmers who are curious about programming languages and thetheory of computation, especially those who don' t have a formal background in math-ematics or computer scienceIf you're interested in the mind-expanding parts of computer science that deal withprograms, languages, and machines, but are discouraged by the mathematical languagethats often used to explain them, this book is for you. Instead of complex notationwe'll use working code to illustrate theoretical ideas and turn them into interactiveexperiments that you can explore at your own paceThis book assumes that you know at least one modern programming language likeRuby, Python, JavaScript, Java, or C#. All of the code examples are in Ruby, but ifknow another language you should still be able to follow along. However, this bookisn't a guide to best practices in Ruby or object-oriented design. The code is intendedto be clear and concise, but not necessarily to be easy to maintain; the goal is alwaysto use ruby to illustrate the computer science, not vice versa. It's also not a textbookor an encyclopedia, so instead of presenting formal arguments or watertight proofs,this book tries to break the ice on some interesting ideas and inspire you to learn aboutem in more deptConventions Used in this bookThe following typographical conventions are used in this bookⅠ talicIndicates new terms. URLs. email addresses. filenames. and file extensionsConstant widthUsed for program listings, as well as within paragraphs to refer to program elementssuch as variable or function names, databases data types, environment variablesstatements, and keywordsConstant width boldShows commands or other text that should be typedy by the user.onstant width italicShows text that should be replaced with user-supplied values or by values deter-mined by contextThis icon signifies a tip, suggestion, or general noteThis icon indicates a warning or cautionUsing Code ExamplesThis book is here to help you get your job done. In general, if this book includes codeexamples, you may use the code in your programs and documentation. You do notneed to contact us for permission unless you' re reproducing a significant portion of thecode. For example, writing a program that uses several chunks of code from this bookdoes not require permission. Selling or distributing a CD-ROM of examples fromO'Reilly books does require permission. Answering a question by citing this book andquoting example code does not require permission Incorporating a significant amountof example code from this book into your products documentation does require permIssionWe appreciate, but do not require, attribution. An attribution usually includes the titleauthor, publisher, and iSBN. For example: Understanding Computation by Tom Stuart(O'Reilly). Copyright 2013 Tom Stuart, 978-1-4493-2927-3If you feel your use of code examples falls outside faifeel tree to contact us at permissions(@oreilly core r use or theon given above,Safari books onlineSafariSafariBooksOnline(www.safaribooksonline.com)isanon-demanddigitallibrary that delivers expert content in both book and video form from theworld's leading authors in technology and businessTechnology professionals, software developers, web designers, and business and creative professionals use Safari Books Online as their primary resource for researchproblem solving, learning, and certification training.ⅶ ii Preface