Structure and Interpretation of Computer Programs second edition Unofficial Texinfo Format 2.andresraba5.3 Harold Abelson and Gerald Jay Sussman with Julie Sussman, foreword by Alan J. Perlis ©1996byeMassachusesInstituteofTechnology StructureandInterpretationofComputerPrograms, secondedition HaroldAbelsonandGeraldJaySussman withJulieSussman,forewordbyAlanJ.Perlis isworkislicensedunderaCreativeCommons Aribution-ShareAlike3.0UnportedLicense (3.0).Basedonaworkatmitpress.mit.edu. ePress Cambridge,Massachuses London,England McGraw-HillBookCompany NewYork,St.Louis,SanFrancisco, Montreal,Toronto UnofficialTexinfoFormat2.andresraba5.3(April6,2014), basedon2.neilvandyke4(January10,2007). Contents UnofficialTexinfoFormat ix Dedication xii Foreword xiii PrefacetotheSecondEdition xix PrefacetotheFirstEdition xxi Anowledgments xxv 1 BuildingAbstractionswithProcedures 1 1.1 eElementsofProgramming . . . . . . . . . . . . . . 6 1.1.1 Expressions . . . . . . . . . . . . . . . . . . . . 7 1.1.2 NamingandtheEnvironment . . . . . . . . . . 10 1.1.3 EvaluatingCombinations . . . . . . . . . . . . 12 1.1.4 CompoundProcedures . . . . . . . . . . . . . . 15 1.1.5 eSubstitutionModelforProcedureApplication 18 1.1.6 ConditionalExpressionsandPredicates . . . . 22 1.1.7 Example:SquareRootsbyNewton’sMethod . . 28 iii 1.1.8 ProceduresasBlack-BoxAbstractions . . . . . 33 1.2 ProceduresandtheProcesseseyGenerate . . . . . . 40 1.2.1 LinearRecursionandIteration . . . . . . . . . 41 1.2.2 TreeRecursion . . . . . . . . . . . . . . . . . . 47 1.2.3 OrdersofGrowth . . . . . . . . . . . . . . . . . 54 1.2.4 Exponentiation . . . . . . . . . . . . . . . . . . 57 1.2.5 GreatestCommonDivisors . . . . . . . . . . . 62 1.2.6 Example:TestingforPrimality . . . . . . . . . 65 1.3 FormulatingAbstractions withHigher-OrderProcedures . . . . . . . . . . . . . . 74 1.3.1 ProceduresasArguments . . . . . . . . . . . . 76 1.3.2 ConstructingProceduresUsingLambda . . . . . 83 1.3.3 ProceduresasGeneralMethods . . . . . . . . . 89 1.3.4 ProceduresasReturnedValues . . . . . . . . . 97 2 BuildingAbstractionswithData 107 2.1 IntroductiontoDataAbstraction . . . . . . . . . . . . . 112 2.1.1 Example:ArithmeticOperations forRationalNumbers . . . . . . . . . . . . . . . 113 2.1.2 AbstractionBarriers . . . . . . . . . . . . . . . 118 2.1.3 WhatIsMeantbyData? . . . . . . . . . . . . . 122 2.1.4 ExtendedExercise:IntervalArithmetic . . . . . 126 2.2 HierarchicalDataandtheClosureProperty . . . . . . . 132 2.2.1 RepresentingSequences . . . . . . . . . . . . . 134 2.2.2 HierarchicalStructures . . . . . . . . . . . . . . 147 2.2.3 SequencesasConventionalInterfaces . . . . . 154 2.2.4 Example:APictureLanguage . . . . . . . . . . 172 2.3 SymbolicData . . . . . . . . . . . . . . . . . . . . . . . 192 2.3.1 otation . . . . . . . . . . . . . . . . . . . . . 192 iv 2.3.2 Example:SymbolicDifferentiation . . . . . . . 197 2.3.3 Example:RepresentingSets . . . . . . . . . . . 205 2.3.4 Example:HuffmanEncodingTrees . . . . . . . 218 2.4 MultipleRepresentationsforAbstractData . . . . . . . 229 2.4.1 RepresentationsforComplexNumbers . . . . . 232 2.4.2 Taggeddata . . . . . . . . . . . . . . . . . . . . 237 2.4.3 Data-DirectedProgrammingandAdditivity . . 242 2.5 SystemswithGenericOperations . . . . . . . . . . . . 254 2.5.1 GenericArithmeticOperations . . . . . . . . . 255 2.5.2 CombiningDataofDifferentTypes . . . . . . . 262 2.5.3 Example:SymbolicAlgebra . . . . . . . . . . . 274 3 Modularity,Objects,andState 294 3.1 AssignmentandLocalState . . . . . . . . . . . . . . . 296 3.1.1 LocalStateVariables . . . . . . . . . . . . . . . 297 3.1.2 eBenefitsofIntroducingAssignment . . . . 305 3.1.3 eCostsofIntroducingAssignment . . . . . . 311 3.2 eEnvironmentModelofEvaluation. . . . . . . . . . 320 3.2.1 eRulesforEvaluation . . . . . . . . . . . . . 322 3.2.2 ApplyingSimpleProcedures . . . . . . . . . . . 327 3.2.3 FramesastheRepositoryofLocalState . . . . 330 3.2.4 InternalDefinitions . . . . . . . . . . . . . . . . 337 3.3 ModelingwithMutableData . . . . . . . . . . . . . . . 341 3.3.1 MutableListStructure . . . . . . . . . . . . . . 342 3.3.2 Representingeues . . . . . . . . . . . . . . . 353 3.3.3 RepresentingTables . . . . . . . . . . . . . . . 360 3.3.4 ASimulatorforDigitalCircuits . . . . . . . . . 369 3.3.5 PropagationofConstraints . . . . . . . . . . . 386 3.4 Concurrency:TimeIsoftheEssence. . . . . . . . . . . 401 v 3.4.1 eNatureofTimeinConcurrentSystems . . 403 3.4.2 MechanismsforControllingConcurrency . . . 410 3.5 Streams . . . . . . . . . . . . . . . . . . . . . . . . . . . 428 3.5.1 StreamsAreDelayedLists . . . . . . . . . . . . 430 3.5.2 InfiniteStreams . . . . . . . . . . . . . . . . . . 441 3.5.3 ExploitingtheStreamParadigm . . . . . . . . . 453 3.5.4 StreamsandDelayedEvaluation . . . . . . . . 470 3.5.5 ModularityofFunctionalPrograms andModularityofObjects . . . . . . . . . . . . 479 4 MetalinguisticAbstraction 487 4.1 eMetacircularEvaluator . . . . . . . . . . . . . . . . 492 4.1.1 eCoreoftheEvaluator . . . . . . . . . . . . 495 4.1.2 RepresentingExpressions . . . . . . . . . . . . 501 4.1.3 EvaluatorDataStructures . . . . . . . . . . . . 512 4.1.4 RunningtheEvaluatorasaProgram . . . . . . 518 4.1.5 DataasPrograms . . . . . . . . . . . . . . . . . 522 4.1.6 InternalDefinitions . . . . . . . . . . . . . . . . 526 4.1.7 SeparatingSyntacticAnalysisfromExecution . 534 4.2 VariationsonaScheme—LazyEvaluation . . . . . . . 541 4.2.1 NormalOrderandApplicativeOrder . . . . . . 542 4.2.2 AnInterpreterwithLazyEvaluation . . . . . . 544 4.2.3 StreamsasLazyLists . . . . . . . . . . . . . . . 555 4.3 VariationsonaScheme—NondeterministicComputing 559 4.3.1 AmbandSearch . . . . . . . . . . . . . . . . . 561 4.3.2 ExamplesofNondeterministicPrograms . . . . 567 4.3.3 ImplementingtheAmbEvaluator . . . . . . . . 578 4.4 LogicProgramming . . . . . . . . . . . . . . . . . . . . 594 4.4.1 DeductiveInformationRetrieval . . . . . . . . 599 vi 4.4.2 HowtheerySystemWorks . . . . . . . . . 615 4.4.3 IsLogicProgrammingMathematicalLogic? . . 627 4.4.4 ImplementingtheerySystem . . . . . . . . 635 4.4.4.1 eDriverLoopandInstantiation . . 636 4.4.4.2 eEvaluator . . . . . . . . . . . . . 638 4.4.4.3 FindingAssertions byPaernMatching . . . . . . . . . 642 4.4.4.4 RulesandUnification . . . . . . . . . 645 4.4.4.5 MaintainingtheDataBase . . . . . . 651 4.4.4.6 StreamOperations . . . . . . . . . . 654 4.4.4.7 erySyntaxProcedures . . . . . . . 656 4.4.4.8 FramesandBindings . . . . . . . . . 659 5 ComputingwithRegisterMaines 666 5.1 DesigningRegisterMachines . . . . . . . . . . . . . . . 668 5.1.1 ALanguageforDescribingRegisterMachines . 672 5.1.2 AbstractioninMachineDesign . . . . . . . . . 678 5.1.3 Subroutines . . . . . . . . . . . . . . . . . . . . 681 5.1.4 UsingaStacktoImplementRecursion . . . . . 686 5.1.5 InstructionSummary . . . . . . . . . . . . . . . 695 5.2 ARegister-MachineSimulator . . . . . . . . . . . . . . 696 5.2.1 eMachineModel . . . . . . . . . . . . . . . . 698 5.2.2 eAssembler . . . . . . . . . . . . . . . . . . 704 5.2.3 GeneratingExecutionProcedures forInstructions . . . . . . . . . . . . . . . . . . 708 5.2.4 MonitoringMachinePerformance . . . . . . . 718 5.3 StorageAllocationandGarbageCollection . . . . . . . 723 5.3.1 MemoryasVectors . . . . . . . . . . . . . . . . 724 5.3.2 MaintainingtheIllusionofInfiniteMemory . . 731 vii 5.4 eExplicit-ControlEvaluator . . . . . . . . . . . . . . 741 5.4.1 eCoreoftheExplicit-ControlEvaluator . . . 743 5.4.2 SequenceEvaluationandTailRecursion . . . . 751 5.4.3 Conditionals,Assignments,andDefinitions . . 756 5.4.4 RunningtheEvaluator . . . . . . . . . . . . . . 759 5.5 Compilation . . . . . . . . . . . . . . . . . . . . . . . . 767 5.5.1 StructureoftheCompiler . . . . . . . . . . . . 772 5.5.2 CompilingExpressions . . . . . . . . . . . . . . 779 5.5.3 CompilingCombinations . . . . . . . . . . . . 788 5.5.4 CombiningInstructionSequences . . . . . . . . 797 5.5.5 AnExampleofCompiledCode . . . . . . . . . 802 5.5.6 LexicalAddressing . . . . . . . . . . . . . . . . 817 5.5.7 InterfacingCompiledCodetotheEvaluator . . 823 References 834 ListofExercises 844 ListofFigures 846 Index 848 Colophon 855 viii Unofficial Texinfo Format isisthesecondedition book,fromUnofficialTexinfoFormat. YouareprobablyreadingitinanInfohypertextbrowser,suchasthe InfomodeofEmacs.YoumightalternativelybereadingitTEX-formaed on your screen or printer, though that would be silly. And, if printed, expensive. e freely-distributed official -and- format was first con- vertedpersonallytoUnofficialTexinfoFormat()version1byLytha AythduringalongEmacslovefestweekendinApril,2001. e  is easier to search than the  format. It is also much more accessible to people running on modest computers, such as do- nated ’386-based PCs. A 386 can, in theory, run Linux, Emacs, and a Scheme interpreter simultaneously, but most 386s probably can’t also run both Netscape and the necessary X Window System without pre- maturelyintroducingbuddingyoungunderfundedhackerstothecon- cept of thrashing. UTF can also fit uncompressed on a 1.44 floppy diskee, which may come in handy for installing UTF on PCs that do nothaveInternetorLANaccess. e Texinfo conversion has been a straight transliteration, to the extentpossible.LiketheTEX-to-conversion,thiswasnotwithout someintroductionofbreakage.InthecaseofUnofficialTexinfoFormat, ix figureshavesufferedanamateurishresurrectionofthelostartof . Also,it’squitepossiblethatsomeerrorsofambiguitywereintroduced duringtheconversionofsomeofthecopioussuperscripts(‘ˆ’)andsub- scripts (‘_’). Divining which has been le as an exercise to the reader. But at least we don’t put our brave astronauts at risk by encoding the greater-than-or-equal symbolas<u>&gt;</u>. Ifyoumodifysicp.texitocorrecterrorsorimprovetheart, thenupdatethe@set utfversion utfversionlinetoreflectyourdelta. For example, if you started with Lytha’s version 1, and your name is Bob,thenyoucouldnameyoursuccessiveversions1.bob1,1.bob2,::: 1.bobn. Also update utfversiondate. If you want to distribute your version on the Web, then embedding the string “sicp.texi” somewhere inthefileorWebpagewillmakeiteasierforpeopletofindwithWeb searchengines. It is believed that the Unofficial Texinfo Format is in keeping with the spirit of the graciously freely-distributed  version. But you neverknowwhensomeone’sarmadaoflawyersmightneedsomething to do, and get their shorts all in a knot over some benign lile thing, so think twice before you use your full name or distribute Info, , PostScript,or formatsthatmightembedyouraccountormachine name. Peath,LythaAyth Addendum:Seealsothe videolecturesbyAbelsonandSussman: at  or . SecondAddendum:Aboveistheoriginalintroductiontothe from 2001.Tenyearslater,hasbeentransformed:mathematicalsymbols andformulasareproperlytypeset,andfiguresdrawninvectorgraph- ics. e original text formulas and  art figures are still there in x