How To Design Programs - An Introduction to Computing and Programming.pdf

HowtoDesignProgramsAnIntroductiontoComputingandProgrammingMatthiasFelleisenRobertBruceFindlerMatthewFlattShriramKrishnamurthiTheMITPressCambridge,MassachusettsLondon,EnglandBookDescriptionThisintroductiontoprogrammingplacescomputerscienceinthecoreofaliberalartseducationUnlikeotherintroductorybooks,itfocusesontheprogramdesignprocessThisapproachfostersavarietyofskillscriticalreading,analyticalthinking,creativesynthesis,andattentiontodetailthatareimportantforeveryone,notjustfuturecomputerprogrammersThebookexposesreaderstotwofundamentallynewideasFirst,itpresentsprogramdesignguidelinesthatshowthereaderhowtoanalyzeaproblemstatementhowtoformulateconcisegoalshowtomakeupexampleshowtodevelopanoutlineofthesolution,basedontheanalysishowtofinishtheprogramandhowtotestEachstepproducesawelldefinedintermediateproductSecond,thebookcomeswithanovelprogrammingenvironment,thefirstoneexplicitlydesignedforbeginnersTheenvironmentgrowswiththereadersastheymasterthematerialinthebookuntilitsupportsafullfledgedlanguageforthewholespectrumofprogrammingtasksAllthebook'ssupportmaterialsareavailableforfreeontheWebTheWebsiteincludestheenvironment,teacherguides,exercisesforalllevels,solutions,andadditionalprojectsTEAMFLYTEAMFLYPRESENTSContentsPrefaceWhyEveryoneShouldLearntoProgramDesignRecipesTheChoiceofSchemeandDrSchemeThePartsoftheBookAcknowledgmentsIProcessingSimpleFormsofDataStudents,Teachers,andComputersNumbers,Expressions,SimpleProgramsNumbersandArithmeticVariablesandProgramsWordProblemsErrorsDesigningProgramsProgramsareFunctionPlusVariableDefinitionsComposingFunctionsVariableDefinitionsFingerExercisesonComposingFunctionsConditionalExpressionsandFunctionsBooleansandRelationsFunctionsthatTestConditionsConditionalsandConditionalFunctionsDesigningConditionalFunctionsSymbolicInformationFingerExerciseswithSymbolsCompoundData,Part:StructuresStructuresExtendedExercise:DrawingSimplePicturesStructureDefinitionsDataDefinitionsDesigningFunctionsforCompoundDataExtendedExercise:MovingCirclesandRectanglesExtendedExercise:HangmanTheVarietiesofDataMixingandDistinguishingDataDesigningFunctionsforMixedDataComposingFunctions,RevisitedTEAMFLYTEAMFLYPRESENTSExtendedExercise:MovingShapesInputErrorsIntermezzo:SyntaxandSemanticsTheSchemeVocabularyTheSchemeGrammarTheMeaningofSchemeErrorsBooleanExpressionsVariableDefinitionsStructureDefinitionsIIProcessingArbitrarilyLargeDataCompoundData,Part:ListsListsDataDefinitionsforListsofArbitraryLengthProcessingListsofArbitraryLengthDesigningFunctionsforSelfReferentialDataDefinitionsMoreonProcessingSimpleListsMoreonProcessingListsFunctionsthatProduceListsListsthatContainStructuresExtendedExercise:MovingPicturesNaturalNumbersDefiningNaturalNumbersProcessingNaturalNumbersofArbitrarySizeExtendedExercise:CreatingLists,TestingFunctionsAlternativeDataDefinitionsforNaturalNumbersMoreontheNatureofNaturalNumbersComposingFunctions,RevisitedAgainDesigningComplexProgramsRecursiveAuxiliaryFunctionsGeneralizingProblems,GeneralizingFunctionsExtendedExercise:RearrangingWordsIntermezzo:ListAbbreviationsIIIMoreonProcessingArbitrarilyLargeDataMoreSelfreferentialDataDefinitionsStructuresinStructuresExtendedExercise:BinarySearchTreesListsinListsExtendedExercise:EvaluatingSchemeTEAMFLYTEAMFLYPRESENTSMutuallyReferentialDataDefinitionsListsofStructures,ListsinStructuresDesigningFunctionsforMutuallyReferentialDefinitionsExtendedExercise:MoreonWebPagesDevelopmentthroughIterativeRefinementDataAnalysisDefiningDataClassesandRefiningThemRefiningFunctionsandProgramsProcessingTwoComplexPiecesofDataProcessingTwoListsSimultaneously:CaseProcessingTwoListsSimultaneously:CaseProcessingTwoListsSimultaneously:CaseFunctionSimplificationDesigningFunctionsthatConsumeTwoComplexInputsExercisesonProcessingTwoComplexInputsExtendedExercise:EvaluatingScheme,PartEqualityandTestingIntermezzo:LocalDefinitionsandLexicalScopeOrganizingProgramswithlocalSyntaxoflocalSemanticsoflocalPragmaticsoflocal,PartPragmaticsoflocal,PartPragmaticsoflocal,PartLexicalScopeandBlockStructureIVAbstractingDesignsSimilaritiesinDefinitionsSimilaritiesinFunctionsSimilaritiesinDataDefinitionsFunctionsareValuesSyntaxandSemanticsContractsforAbstractandPolymorphicFunctionsDesigningAbstractionsfromExamplesAbstractingfromExamplesFingerExerciseswithAbstractListFunctionsAbstractionandaSinglePointofControlExtendedExercise:MovingPictures,AgainNote:DesigningAbstractionsfromTemplatesDesigningAbstractionswithFirstClassFunctionsFunctionsthatProduceFunctionsDesigningAbstractionswithFunctionsasValuesAFirstLookatGraphicalUserInterfacesTEAMFLYTEAMFLYPRESENTSMathematicalExamplesSequencesandSeriesArithmeticSequencesandSeriesGeometricSequencesandSeriesTaylorSeriesTheAreaUnderaFunctionTheSlopeofaFunctionIntermezzo:DefiningFunctionsontheFlySyntaxoflambdaScopeandSemanticsoflambdaPragmaticsoflambdaVGenerativeRecursionANewFormofRecursionModelingaBallonaTableSortingQuicklyDesigningAlgorithmsTerminationStructuralversusGenerativeRecursionMakingChoicesVariationsonaThemeFractalsFromFilestoLines,fromListstoListsofListsBinarySearchNewton'sMethodExtendedExercise:GaussianEliminationAlgorithmsthatBacktrackTraversingGraphsExtendedExercise:Checking(on)QueensIntermezzo:TheCostofComputingandVectorsConcreteTime,AbstractTimeTheDefinitionof``ontheOrderof''AFirstLookatVectorsVIAccumulatingKnowledgeTheLossofKnowledgeAProblemwithStructuralProcessingAProblemwithGenerativeRecursionDesigningAccumulatorStyleFunctionsRecognizingtheNeedforanAccumulatorAccumulatorStyleFunctionsTransformingFunctionsintoAccumulatorStyleTEAMFLYTEAMFLYPRESENTSMoreUsesofAccumulationExtendedExercise:AccumulatorsonTreesExtendedExercise:MissionariesandCannibalsExtendedExercise:BoardSolitaireIntermezzo:TheNatureofInexactNumbersFixedsizeNumberArithmeticOverflowUnderflowDrScheme'sNumbersVIIChangingtheStateofVariablesMemoryforFunctionsAssignmenttoVariablesSimpleAssignmentsatWorkSequencingExpressionEvaluationsAssignmentsandFunctionsAFirstUsefulExampleDesigningFunctionswithMemoryTheNeedforMemoryMemoryandStateVariablesFunctionsthatInitializeMemoryFunctionsthatChangeMemoryExamplesofMemoryUsageInitializingStateStateChangesfromUserInteractionsStateChangesfromRecursionFingerExercisesonStateChangesExtendedExercise:ExploringPlacesIntermezzo:TheFinalSyntaxandSemanticsTheVocabularyofAdvancedSchemeTheGrammarofAdvancedSchemeTheMeaningofAdvancedSchemeErrorsinAdvancedSchemeVIIIChangingCompoundValuesEncapsulationAbstractingwithStateVariablesPracticewithEncapsulationMutableStructuresStructuresfromFunctionsMutableFunctionalStructuresMutableStructuresTEAMFLYTEAMFLYPRESENTSMutableVectorsChangingVariables,ChangingStructuresDesigningFunctionsthatChangeStructuresWhyMutateStructuresStructuralDesignRecipesandMutation,PartStructuralDesignRecipesandMutation,PartExtendedExercise:MovingPictures,aLastTimeEqualityExtensionalEqualityIntensionalEqualityChangingStructures,Vectors,andObjectsMorePracticewithVectorsCollectionsofStructureswithCyclesBacktrackingwithStateEpilogueComputingProgrammingMovingOnIndexTEAMFLYTEAMFLYPRESENTSPrefaceItgoesagainstthegrainofmoderneducationtoteachchildrentoprogramWhatfunisthereinmakingplans,acquiringdisciplineinorganizingthoughts,devotingattentiontodetailandlearningtobeselfcriticalAlanPerlis,EpigramsinProgrammingManyprofessionsrequiresomeformofcomputerprogrammingAccountantsprogramspreadsheetsandwordprocessorsphotographersprogramphotoeditorsmusiciansprogramsynthesizersandprofessionalprogrammersinstructplaincomputersProgramminghasbecomearequiredskillYetprogrammingismorethanjustavocationalskillIndeed,goodprogrammingisafunactivity,acreativeoutlet,andawaytoexpressabstractideasinatangibleformAnddesigningprogramsteachesavarietyofskillsthatareimportantinallkindsofprofessions:criticalreading,analyticalthinking,creativesynthesis,andattentiontodetailWethereforebelievethatthestudyofprogramdesigndeservesthesamecentralroleingeneraleducationasmathematicsandEnglishOr,putmoresuccinctly,everyoneshouldlearnhowtodesignprogramsOnonehand,programdesignteachesthesameanalyticalskillsasmathematicsBut,unlikemathematics,workingwithprogramsisanactiveapproachtolearningInteractingwithsoftwareprovidesimmediatefeedbackandthusleadstoexploration,experimentation,andselfevaluationFurthermore,designingprogramsproducesusefulandfunthings,whichvastlyincreasesthesenseofaccomplishmentwhencomparedtodrillexercisesinmathematicsOntheotherhand,programdesignteachesthesameanalyticalreadingandwritingskillsasEnglishEventhesmallestprogrammingtasksareformulatedaswordproblemsWithoutcriticalreadingskills,astudentcannotdesignprogramsthatmatchthespecificationConversely,goodprogramdesignmethodsforceastudenttoarticulatethoughtsaboutprogramsinproperEnglishTheDesignRecipeforFunctionsProblemAnalysisDataDefinitionContract,PurposeEffectStatements,HeaderExamplesFunctionTemplateFunctionDefinitionTestsFigure:ThebasicstepsofaprogramdesignrecipeThisbookisthefirstbookonprogrammingasthecoresubjectofaliberalartseducationItsmainfocusisthedesignprocessthatleadsfromproblemstatementstowellorganizedsolutionsTEAMFLYTEAMFLYPRESENTSitdeemphasizesthestudyofprogramminglanguagedetails,algorithmicminutiae,andspecificapplicationdomainsOurdesiretofocusonthedesignprocessrequirestworadicalinnovationsforintroductorycoursesThefirstinnovationisasetofexplicitdesignguidelinesExistingcurriculatendtoprovidevagueandilldefinedsuggestions,suchas``designfromtoptobottom''or``maketheprogramstructural''WehaveinsteaddevelopeddesignguidelinesthatleadstudentsfromaproblemstatementtoacomputationalsolutioninstepbystepfashionwithwelldefinedintermediateproductsIntheprocesstheylearntoread,toanalyze,toorganize,toexperiment,tothinkinasystematicmannerThesecondinnovationisaradicallynewprogrammingenvironmentInthepast,textsonprogrammingignoredtheroleoftheprogrammingenvironmentinthelearningprocesstheysimplyassumedthatstudentshadaccesstoaprofessionalenvironmentThisbookprovidesaprogrammingenvironmentforbeginnersItalsogrowswiththestudentsastheymastermoreandmoreofthematerialuntilitsupportsafullfledgedlanguageforthewholespectrumofprogrammingtasks:largescaleprogrammingaswellasscriptingOurguidelinesareformulatedasanumberofprogramdesignrecipesAdesignrecipeguidesabeginningprogrammerthroughtheentireproblemsolvingprocessWithdesignrecipes,abeginneralmostneveragainstaresatablankpieceofpaperorablankcomputerscreenInstead,thestudentwillcheckthedesignrecipeandusethequestionandanswerguidelinestomakesomeprogressWecreatedthedesignrecipesbyidentifyingcategoriesofproblemsTheidentificationofaproblemcategoryisbasedontheclassesofdatathatareusedtorepresenttherelevantinformationStartingfromthestructureofthisclassdescriptionstudentsderivetheprogramswithachecklistFigureshowsthebasicsixstepsofadesignrecipechecklistEachstepproducesawelldefinedintermediateproduct:thedescriptionoftheclassofproblemdatatheinformalspecificationofaprogram'sbehaviortheillustrationofthebehaviorwithexamplesthedevelopmentofaprogramtemplateorlayoutthetransformationofthetemplateintoacompletedefinitionandthediscoveryoferrorsthroughtestingThemajordifferenceconcernstherelationshipofstepsandDesignrecipeshelpbeginnersandteachersalikeTeacherscanusetherecipestoinspectabeginner'sproblemsolvingskills,todiagnoseweaknesses,andtosuggestspecificremedialstepsAfterall,eachstageofthedesignrecipeyieldsawelldefined,checkableproductIfabeginnerisstuck,ateachercaninspecttheintermediateproductsanddeterminewhattheproblemisBasedonthisanalysis,theteachercanthenprovideguidanceforaspecificstepintherecipe,raiseappropriatequestions,andrecommendadditionalpracticeexercisesWhyEveryoneShouldLearntoProgramAndasimaginationbodiesforthTheformsofthingstounknown,andthepoet'spenTurnsthemtoshapes,andgivestoairynothingAlocalhabitationandanameTEAMFLYTEAMFLYPRESENTSShakespeare,AMidsummerNight'sDreamV(i)Ourclaimthateveryoneprogramsorshouldlearntoprogrammightappearstrangeconsideringthat,atfirstglance,fewerandfewerpeopleseemtoprogramthesedaysInstead,themajorityofpeopleuseapplicationpackages,whichdon'tseemtorequireanyprogrammingEvenprogrammersuse``programgenerators,''packagesthatcreateprogramsfrom,say,businessrulesSowhyshouldanyonelearntoprogramTheanswerconsistsoftwopartsFirst,itisindeedtruethattraditionalformsofprogrammingareusefulforjustafewpeopleBut,programmingaswetheauthorsunderstanditisusefulforeveryone:theadministrativesecretarywhousesspreadsheetsaswellasthehightechprogrammerInotherwords,wehaveabroadernotionofprogramminginmindthanthetraditionaloneWeexplainournotioninamomentSecond,weteachourideaofprogrammingwithatechnologythatisbasedontheprincipleofminimalintrusionHenceournotionofprogrammingteachesproblemanalysisandproblemsolvingskillswithoutimposingtheoverheadoftraditionalprogrammingnotationsandtoolsTogetabetterunderstandingofmodernprogramming,takeacloserlookatspreadsheets,oneoftoday'spopularapplicationpackagesAuserentersformulasintoaspreadsheetTheformulasdescribehowacellAdependsonanothercellBThen,astheuserentersanumberintoB,thespreadsheetautomaticallycalculatesthecontentsofcellAForcomplicatedspreadsheets,acellmaydependonmanyothercells,notjustoneOtherapplicationpackagesrequiresimilaractivitiesConsiderwordprocessorsandstylesheetsAstylesheetspecifieshowtocreatea(partofa)documentfromyettobedeterminedwordsorsentencesWhensomeoneprovidesspecificwordsandastylesheet,thewordprocessorcreatesthedocumentbyreplacingnamesinthestylesheetwithspecificwordsSimilarly,someonewhoconductsaWebsearchmaywishtospecifywhatwordstolookfor,whatwordsshouldbenexttoeachother,andwhatwordsshouldnotoccurinthepageInthiscase,theoutputdependsonthesearchengine'scacheofWeb