Pasifika C++ AIDANDELANEY,ALLENB.DOWNEY,NARENDRASISODIYA, TIRTHAP.CHATTERJEE PasifikaC++ AidanDelaney,AllenB.Downey,NarendraSisodiya,TirthaP.Chatterjee 2 Contents 1 WhyStudyComputing? 7 1.1 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3 WhatisProgramming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3.1 Formalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4 WhatcanComputersDo? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.5 WhatComputersCan’tDo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.6 WhyC++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.7 Whatwecandonow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2 HelloWorld 17 2.1 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 TheConsole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3 FirstProgram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3.1 AStylisticNoteonWhitespace. . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4 Whatwecannowdo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3 intandOtherTypes 23 3.1 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2 SimpleTypes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3 TypeErrors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.4 StorageBoxes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.5 Whatwecannowdo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4 Functions 27 4.1 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2 SimpleFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.3 Signaturebeforeuse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.4 MultipleParameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.5 TestingFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.5.1 TestHarness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3 PasifikaC++ 4.6 voidreturn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.7 Whatwecannowdo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5 InputandOutput 33 5.1 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.2 Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.3 Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.4 TestingInput . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.5 Whatwecannowdo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 6 BranchingComputation 39 6.1 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6.2 StaticStructure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6.3 TracingExecution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.4 Conditionalexecution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 6.5 Alternativeexecution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 6.6 Whatwecannowdo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 7 Iteration 47 7.1 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 7.2 Multipleassignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 7.3 Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 7.3.1 Thewhilestatement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 7.4 forloops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 7.5 Whatwecannowdo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 8 Lists 55 8.1 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 8.2 Avector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 8.3 Accessingelements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 8.4 BetterIteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 8.5 Copyingvectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 8.6 Vectorsize. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 8.7 Vectorfunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 8.8 Whatwecannowdo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 8.9 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 8.10 Determinsm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 8.11 Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 8.11.1 Vectorofrandomnumbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 AidanDelaney,AllenB.Downey,NarendraSisodiya,TirthaP.Chatterjee 4 PasifikaC++ 8.11.2 Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 8.11.3 Checkingtheothervalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 8.11.4 Ahistogram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 8.11.5 Asingle-passsolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 8.12 Randomseeds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 8.13 Whatwecandonow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 9 Provenance 69 9.1 Licence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 9.2 GNUGENERALPUBLICLICENSE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 9.2.1 Preamble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 9.2.2 TERMSANDCONDITIONSFORCOPYING,DISTRIBUTIONANDMODIFICATION . 70 9.2.3 NOWARRANTY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 10 PacifikaC++ 75 10.1 Building . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 AidanDelaney,AllenB.Downey,NarendraSisodiya,TirthaP.Chatterjee 5 PasifikaC++ AidanDelaney,AllenB.Downey,NarendraSisodiya,TirthaP.Chatterjee 6 1 Why Study Computing? 1.1 Objective Inthischapterwemotivatewhywestudycomputerprogramming. 1.2 Background Therearealotofinterestingthingsoutthereintheworld. Youcouldlearnaboutmagicalrealism inliteraturefromBorges’writingsthroughtoDelToro’sexcellentmoviePan’sLabyrinth.Ormaybe you’reinterestedinhowEinstein’stheoriesofrelativityledtoQuantumMechanics. Amidstallof theseinterestingtopicswhychoosetostudycomputerprogramming?Ihavemultiple,andsometimes contradictoryviews,onwhyIlikeprogramming.It’sessentiallyreductionist,todoitcorrectlyrequires greatsocialskillsanditrepresentsabout50%ofmydailyuniverse.I’llexplaineachoftheseclaimsin turn. Computerprogrammingisreductionist.Westudyaproblemandreducetheproblemtoit’sbarebones. Asanexample,wereduceeverythingtonumbers–wecan’trepresentthedepthandbreadthhow muchyoumightloveapet,butwecanrepresentitonascalefrom0to100!Afterreducingtheproblem, wethenproduceacomputerprogramthatsolvestheproblemfromverybasiccomponents.Eachtime youwriteaprogramit’slikewalkingintoaworkshopcontainingabunchofsteelpipesandafurnace andbeingtoldthatyouhavetobuildamotorbike.Wegenerallylookaproblemsfromthebottom-up; howcanwesolvetheproblemwiththesmallnumberofcomponentsthatareavailabletous. Bycontrast,thepeoplewhowantustowriteprograms–employers,family,friendsandwidersociety – look at things from a top-down perspective. They need to automate some systems in order to solveareal-worldproblem. Youremployermightwantaprogramtocalculatetheirannualtaxbill, andthenautomaticallytransferthetaxpaymentdirectlytothetaxauthorities1.Theperspectivesof suchstakeholdersisalmosttheoppositeofreductionist.Itrequiresthinkingaboutanentiresystem. Moreoversolvingreal-worldproblemsdevelopsexcellentcommunicationskillsinordertoteaseout therealissuesthestakeholderwantstosolve.OftenstakeholdersaskforaprogramtodoXwhenthey 1Thisdoesn’tapplyinVanuatuasthereisnoincometaxorcorporationtax,buttheyarebeingintroducedinthenearfuture. 7 PasifikaC++ reallywanttosolveproblemY.Programmershavetheirownlanguagefordescribingsuchthings.We callittheXYProblem. Sofarwe’veconsideredareductionistbottom-upreasontostudyprogramming.We’vealsobriefly discussedhowyoualsohowprogrammingcanhelpyoutodevelopgreatcommunicationskills.My thirdreasonforstudyingprogrammingisanargumentmadebySimonPeytonJones.Hearguesthat inthe20thCenturyweintroducedthenaturalsciencesintoschools–thatisphysics,chemistryand biology–sothatalladultswouldhaveagoodunderstandingofthephysicalworldinwhichwelive.In the21stCenturywelivemuchofourdayoutsidethephysicalworldandinsidethevirtualworld2.Many ofourrelationshipsaremediatedbysocialnetworks–IhavegoodfriendswhoI’veneverseen.Other simplethingsinlifearealsodigital,banktransferscanbeorganisedthroughawebbrowserandavoid standinginlineinaphysicalbank.Therearegrowingtrendswhereweusesoftwaretosolvetransport issues,negatingthereasonstocoughup$14konasecond-handToyota.Thevirtualworldhassucha hugeimpactonourreal-worldthatitisusefultostudyprogrammingsothatwecanunderstandthe buildingblocksofthevirtualworld. Sotherearethreereasonstostudyprogramming;thefirstbecauseit’sabigboxoflegofromwhich youcanbuildreallyinterestingthings,thesecondbecauseitsolvesinteresting(andnotsointeresting) real-worldproblemsthatrequirealotofcommunicationandthethirdreasonisbecauseitgiveyoua goodunderstandingofthevirtualuniverseinwhichwespendmuchofourdailylife. 1.3 WhatisProgramming Ifyou’restillreadingyou’reeitherconvincedbyoneofmythreereasonsforstudyingprogrammingor youneedthecoursecreditgivenbypassingaprogrammingclass.Hopefullyit’stheformerasintrinsic motivationismorelikelytodriveyoutosuccessthanextrinsicmotivation.Inbothcasesyouknowwhy you’restudyingprogramming,thequestionnowbecomes“whatisprogramming?”. Inoneview,aprogramisanunambiguouslistofinstructions.Eachtimeyoufollowthelistofinstruc- tions,youwillachievethesameresult.Thecomparisonisoftenmadewithcooking,whererecipesare oftensharedasalistofinstructions.Takeforexampletheinstructionsformakingachickenlovoor umu.Inthecaseoflovoyoumightgettheinstructionsto: 1. Digapit, 2. Buildafire, 3. Carefullyplacelavarocksoverthefire, 4. Lightthefireandletitburndowntoembers, 5. Seasonthechicken, 2Ifyoudon’tbelievemeonthis,thenhavealookaroundandseehowmanystudentsthinkIcan’tseethemtextingundera deskinyournextclass. AidanDelaney,AllenB.Downey,NarendraSisodiya,TirthaP.Chatterjee 8 PasifikaC++ 6. Wrapthechickeninbananaleaves, 7. Putthewrappedchickenonthehotstones, 8. Coverthefoodwithearth 9. Wait2hours,removechickenandeat! Tomostpeople,theaboveinstructionsareenoughtomakeagreatdinner.Howevertheseinstructions areambiguous. Theydon’tsayhowdeeporwidetobuildthepit. Theydon’tsayhowhighthefire shouldbewithinthepit.Howlargeshouldthelavarocksbe?Orwhatdoweseasonthechickenwith? Moreover,ifyou’veevermadealovoorumuyouknowit’salotofeffort.Toomuchefforttocooka singlechickensomaybeweshouldalsoplacetaroandfishalongsidethechicken.Thereasonthatthe instructionscanbeambiguousisbecauseyou,dearreader,areintelligentenoughtofillintheblanks. Computers,ofcourse,arenotintelligent. Theycannotfillinanyblanksinanexplanation. Sowe needtopresentthemwithalistofinstructionswritteninanunambiguouslanguage.Theprocessof producingunambiguousexplanationsiscalledproof bymathematicians,butwe’llcallitprogramming. 1.3.1 Formalisation Inordertoremoveambiguityfromtheinterpretationofsentenceswe’regoingtoabandontheuse ofnaturallanguage.Wewon’ttrytowriteourinstructionsinEnglish,FrenchorBislama.Theseare fantasticlanguagesinwhichtoexpressloveorrevolution.However,theveryfactthattheselanguages allowustoexpressanddiscusspoorlydefinedconceptsistheveryreasonthattheyareunsuitablefor providingunambiguousinstructionstoamachine.Toprogramacomputerweneedaformallanguage, oneinwhicheachwordandsentencehasawell-definedmeaning. Bywritinginstructionsinaformallanguageweremoveambiguityfromtheinstructions. It’salso importanttonotethatwealsoloosesomethingintranslation.Abunchofinstructionsthatdescribe makingatraditionallovocanbereadandunderstoodbyanyliterateperson.Lovoinstructionswritten inanunambiguouslanguagearelikelytobeverydifficulttoread.InordertoillustratethisIneedto introduceaproblemthatismuchmorestraightforwardthanmakingalovo.Let’sconsiderthekids gamehangman. Thegamehangmanisplayedbykidsinschoolsallovertheworld.Onestudentchoosesasecretword andwritesanumberofdashesonapieceofpaper. Thereisonedashforeachletterofthesecret word.Thesamepersonalsodrawsagallows3.Afriendthenguesseslettersofthesecretword.Ifthey correctlyguessaletterofthewordthentheletteriswrittenonadashinanappropriateposition.If theydonotguesscorrectlythenabitofastickmanisdrawnhungonthegallows.Thefriendwinsthe gameiftheycorrectlyrevealallthelettersofthewordbeforethefullstickmanisdrawnonthepage. 3Thenamehangmananddrawingagallowsareprettyawful,butthenagainmostkidsareawful! AidanDelaney,AllenB.Downey,NarendraSisodiya,TirthaP.Chatterjee 9 PasifikaC++ Ourpreviousparagraphisareasonableexplanationofthegame.Again,likeourlovoexample,you’re probablyabletofillinthebitswhereI’veexplaineditpoorly.Whatifwehadtowritetheinstructionsof thegameinawaythattheycouldn’tbemisinterpreted?Legalpeoplecommonlywritesuchinstructions: Thegameofhangman,hereinreferredtoasTHEGAME,isagamefortwopartiesreferredto asTHEPLAYERandTHEJUDGE. (a) THEJUDGEwilldrawonpaperagallowsandbelowthegallowsaseriesofdasheswhere thereisonedashforeachletterofasecretword. • THEJUDGEwillnotprima-faciarevealthesecretwordtoTHEPLAYER (b) THEPLAYERwillguessaletterofthesecretwordand • iftheguessedletterisoneormorelettersinthesecretword,thenTHEJUDGEwrites theguessedlettersontopofadashthatisatthesamepositionintheseriesasthe guessedletterinthesecretword. • otherwiseTHEJUDGEwilldrawthenextbodypartofastickmanonthegallows. (c) thebodypartsofastickmanaredrawninprogression,onperturn,startingwithahead, abody,aleftleg,arightleg,aleftarmandarightarm. (d) THEJUDGEwinsthegameifthestickmanisdrawnbeforethesecretwordisrevealed. Thelegalcodeforhangmanisusefulwhentwoplayersneedtoargueabouttheimplementationofa rule.Wecanstillargueabouttheinterpretationofsomeoftherules;shouldthejudgedrawthearmas anupperarmandlowerarm? Cantheplayerguesstwolettersatatime?4 Inourcasewewantour ruletobeinterpretedbyamachinethatcan’targueabouthowtoimplementarule. Weknowour machineshavenointelligence.Theycansimplyreplacesymbolswithothersymbols Hopefullyyounowagreethatournaturallanguages,evenwhenrestrictedtolegallanguage,arenot preciseenoughtoinstructadumbcomputer.Weneedlanguagesthatareun-natural.Weneedformal languagesthataresuitedtodescribinghowtomanipulatesymbolsand“move”symbolsaround.Such alanguageisgoingtobedifficulttoreadbecauseofitslackofexpressiveness. Itdoesn’thavethe expressivebandwidthofanaturallanguage. Inamoreformallanguagedesignedforcomputation–aprogramminglanguage–wehavetowritea lotofinstructionstodescribehangman.Theinstructionsmightlooksomethinglike: 1 start program 2 run instructions to construct gallows 3 run instructions to input secret word 4 repeat run instructions to take a turn until the game is over 5 end program 4Asolicitorcouldwritetheserulesinadifferentway.Theycouldfirstformalisethedefinitionofaturnandthendescribe theprogressofthegameasaseriesofturns.Inanycasetheformalisationintolegallanguageaddsmorecomplexity thantheinformalexplanation. AidanDelaney,AllenB.Downey,NarendraSisodiya,TirthaP.Chatterjee 10