Python James R. Parker An Introduction To Programming

User Manual: James-R.-Parker-Python-An-Introduction-to-Programming

Open the PDF directly: View PDF PDF.
Page Count: 534 [warning: Documents this large are best viewed by clicking the View PDF Link!]

PYTHON
LICENSE,DISCLAIMEROFLIABILITY,ANDLIMITEDWARRANTY
By purchasing or using this book (the “Work”), you agree that this license grants
permission to use the contents contained herein, but does not give you the right of
ownership to any of the textual content in the book or ownership to any of the
informationorproductscontainedinit.Thislicensedoesnotpermituploadingofthe
WorkontotheInternetoronanetwork(ofanykind)withoutthewrittenconsentofthe
Publisher. Duplication or dissemination of any text, code, simulations, images, etc.
contained herein is limited to and subject to licensing terms for the respective
products, and permission must be obtained from the Publisher or the owner of the
content,etc.,inordertoreproduceornetworkanyportionofthetextualmaterial(in
anymedia)thatiscontainedintheWork.
MERCURYLEARNINGANDINFORMATION(“MLI”or“thePublisher”)andanyoneinvolved
in the creation, writing, or production of the companion disc, accompanying
algorithms,code,orcomputerprograms(“thesoftware”),andanyaccompanyingWeb
siteorsoftwareoftheWork,cannotanddonotwarranttheperformanceorresultsthat
mightbeobtainedbyusingthecontentsoftheWork.Theauthor,developers,andthe
Publisherhave usedtheir besteffortstoinsure theaccuracy andfunctionality ofthe
textual material and/or programs contained in this package; we, however, make no
warrantyofanykind,expressorimplied,regardingtheperformanceofthesecontents
orprograms.TheWorkissold“asis”withoutwarranty(exceptfordefectivematerials
usedinmanufacturingthebookorduetofaultyworkmanship).
Theauthor,developers,andthepublisherofany accompanyingcontent,andanyone
involvedinthecomposition,production,andmanufacturingofthisworkwillnotbe
liable for damages of any kind arising out of the use of (or the inability to use) the
algorithms, source code, computer programs, or textual material contained in this
publication. This includes, but is not limited to, loss of revenue or profit, or other
incidental,physical,orconsequentialdamagesarisingoutoftheuseofthisWork.
Thesoleremedyintheeventofaclaimofanykindisexpresslylimitedtoreplacement
ofthebook,andonlyatthediscretionofthePublisher.Theuseof“impliedwarranty”
andcertain“exclusions”varyfromstatetostate,andmightnotapplytothepurchaser
ofthisproduct.
Companion disc files are available for download from the publisher by writing to
info@merclearning.com.
Copyright©2017byMERCURYLEARNINGANDINFORMATIONLLC.Allrightsreserved.
Thispublication,portionsofit,oranyaccompanyingsoftwaremaynotbereproduced
in any way, stored in a retrieval system of any type, or transmitted by any means,
media, electronic display or mechanical display, including, but not limited to,
photocopy,recording,Internet
postings,orscanning,withoutpriorpermissioninwritingfromthepublisher.
Publisher:DavidPallai
MERCURYLEARNINGANDINFORMATION
22841QuicksilverDrive
Dulles,VA20166
info@merclearning.com
www.merclearning.com
(800)232-0223
JamesR.Parker.PYTHON:AnIntroductiontoProgramming.
ISBN:978-1-9445346-5-3
The publisher recognizes and respects all marks used by companies, manufacturers,
and
developers as a means to distinguish their products. All brand names and product
names
mentionedinthisbookaretrademarksorservicemarksoftheirrespectivecompanies.
Anyomissionormisuse(ofanykind)ofservicemarksortrademarks,etc.isnotan
attempttoinfringeonthepropertyofothers.
LibraryofCongressControlNumber:2016915244
161718321PrintedintheUnitedStatesofAmerica
Thisbookisprintedonacid-freepaper.
Our titles are available for adoption, license, or bulk purchase by institutions,
corporations,etc.
For additional information, please contact the Customer Service Dept. at 800-232-
0223 (toll free).Digital versions of our titles are available at:
www.authorcloudware.comandothere-vendors.Allcompanionfilesareavailableby
writingtothepublisheratinfo@merclearning.com.
The sole obligation of MERCURY LEARNINGAND INFORMATION to the purchaser is to
replacethebookand/ordisc,basedondefectivematerialsorfaultyworkmanship,but
notbasedontheoperationorfunctionalityoftheproduct.
Contents
Prefacexv
Chapter0ModernComputers
0.1CalculationsbyMachine
0.2HowComputersWorkandWhyWeMadeThem
0.2.1Numbers
Example:Base
ConvertBinaryNumberstoDecimal
ConvertDecimalNumberstoBinary
ArithmeticinBinary
0.2.2Memory
0.2.3StoredPrograms
0.3ComputerSystemsAreBuiltinLayers
0.3.1AssemblersandCompilers
0.3.2GraphicalUserInterfaces(GUIs)
Widgets
0.4ComputerNetworks
0.4.1Internet
0.4.2WorldWideWeb
0.5Representation
0.6Summary
Chapter1ComputersandProgramming
1.1SolvingaProblemUsingaComputer
1.2ExecutingPython
1.3GuessaNumber
1.4Rock-Paper-Scissors
1.5SolvingtheGuessaNumberProblem
1.6SolvingtheRock-Paper-ScissorsProblem
1.6.1VariablesandValues–ExperimentingwiththeGraphicalUserInterface
1.6.2ExchangingInformationwiththeComputer
1.6.3Example1:DrawaCircleUsingCharacters
1.6.4Strings,Integers,andRealNumbers
1.6.5NumberBases
1.6.6Example2:ComputetheCircumferenceofanyCircle
1.6.7GuessaNumberAgain
1.7IFStatements
1.7.1Else
1.8Documentation
1.9Rock-Paper-ScissorsAgain
1.10TypesAreDynamic(Advanced)
1.11Summary
Chapter2Repetition
2.1TheWHILEStatement
2.1.1TheGuess-A-NumberProgramYetAgain
2.1.2ModifyingtheGame
2.2Rock-Paper-ScissorsYetAgain
2.2.1RandomNumbers
2.3CountingLoops
2.4PrimeorNon-Prime
2.4.1ExitingfromaLoop
2.4.2Else
2.5LoopsThatareNested
2.6DrawaHistogram
2.7LoopsinGeneral
2.8ExceptionsandErrors
2.8.1Problem:AFinalLookatGuessaNumber
2.9Summary
Chapter3Sequences:Strings,Tuples,andLists
3.1Strings
3.1.1ComparingStrings
Problem:DoesaCityName,EnteredattheConsole,Comebeforeorafterthe
NameDenver?
3.1.2Slicing–ExtractingPartsofStrings
Problem:Identifya“Print”StatementinaString
3.1.3EditingStrings
Problem:CreateaJPEGFileNamefromaBasicString
Problem:ChangetheSuffixofaFileName
Problem:ReversetheOrderofCharactersinaString
Problem:IsaGivenFileNameThatofaPythonProgram?
3.1.4StringMethods
3.1.5SpanningMultipleLines
3.1.6ForLoopsAgain
3.2TheTypeBytes
3.3Tuples
3.3.1TuplesinForLoops
Problem:PrinttheNumberofNeutronsinanAtomicNucleus
3.3.2Membership
Problem:WhatEvenNumbersLessthanorEqualto100areAlsoPerfect
Squares?
3.3.3Delete
Problem:DeletetheElementLithiumfromtheTupleAtoms,alongwithIts
AtomicNumber.
3.3.4Update
Problem:ChangetheEntryforLithiumtoanEntryforOxygen
3.3.5TupleAssignment
3.3.6Built-InFunctionsforTuples
3.4Lists
Problem:ComputetheAverage(Mean)ofaListofNumbers
3.4.1EditingLists
3.4.2Insert
3.4.3Append
3.4.4Extend
3.4.5Remove
3.4.6Index
3.4.7Pop
3.4.8Sort
3.4.9Reverse
3.4.10Count
3.4.11ListComprehension
3.4.12ListsandTuples
3.4.13Exceptions
Problem:DeletetheElementHeliumfromaList
Problem:DeleteaSpecifiedElementfromaList
3.5SetTypes
3.5.1Example:Craps
3.6Summary
Chapter4Functions
4.1FunctionDefinition:SyntaxandSemantics
4.1.1Problem:UsepoundntoDrawaHistogram
4.1.2Problem:GeneralizetheHistogramCodeforOtherYears
4.2FunctionExecution
4.2.1ReturningaValue
Problem:WriteaFunctiontoCalculatetheSquareRootofitsParameter
4.2.2Parameters
4.2.3DefaultParameters
4.2.4None
4.2.5Example:TheGameofSticks
4.2.6Scope
4.2.7VariableParameterLists
4.2.8VariablesasFunctions
Example:FindtheMaximumValueofaFunction
4.2.9FunctionsasReturnValues
4.3Recursion
4.3.1AvoidingInfiniteRecursion
4.4CreatingPythonModules
4.5ProgramDesignUsingFunctions–Example:TheGameofNim
4.5.1TheDevelopmentProcessExposed
4.6Summary
Chapter5Files:InputandOutput
5.1WhatIsaFile?ALittle“Theory”
5.1.1HowAreFilesStoredonaDisk?
5.1.2FileAccessisSlow
5.2KeyboardInput
5.2.1Problem:ReadaNumberfromtheKeyboardandDivideItby2
5.3UsingFilesinPython:LessTheory,MorePractice
5.3.1OpenaFile
FileNotFoundExceptions
5.3.2ReadingfromFiles
EndofFile
CommonFileInputOperations
CSVFiles
Problem:PrinttheNamesofPlanetsHavingFewerThanTenMoons
Problem:PlayJeopardyUsingaCSVDataSet
TheWithStatement
5.4WritingToFiles
Example:WriteaTableofSquarestoaFile
5.4.1AppendingDatatoaFile
Example:AppendAnother20SquarestotheTableofSquaresFile
5.5Summary
Chapter6Classes
6.1ClassesandTypes
6.1.1ThePythonClass–SyntaxandSemantics
6.1.2AReallySimpleClass
6.1.3Encapsulation
6.2ClassesandDataTypes
6.2.1Example:ADeckofCards
6.2.2ABouncingBall
6.2.3Cat-A-Pult
BasicDesign
DetailedDesign
6.3SubclassesandInheritance
6.3.1Non-TrivialExample:ObjectsinaVideoGame
6.4DuckTyping
6.5Summary
Chapter7Graphics
7.1IntroductiontoGraphicsProgramming
7.1.1Essentials:TheGraphicsWindowandColors
7.1.2PixelLevelGraphics
Example:CreateaPageofNotepaper
Example:CreatingaColorGradient
7.1.3LinesandCurves
Example:NotepaperAgain
7.1.4Polygons
7.1.5Text
7.1.6Example:AHistogram
7.1.7Example:APieChart
7.1.8Images
Pixels
Example:IdentifyingaGreenCar
Example:Thresholding
Transparency
7.1.9GenerativeArt
7.2Summary
Chapter8ManipulatingData
8.1Dictionaries
8.1.1Example:ANaiveLatin–EnglishTranslation
8.1.2FunctionsforDictionaries
8.1.3DictionariesandLoops
8.2Arrays
8.3FormattedText,FormattedI/O
8.3.1Example:NASAMeteoriteLandingData
8.4AdvancedDataFiles
8.4.1BinaryFile
Example:CreateaFileofIntegers
8.4.2TheStructModule
Example:AVideoGameHighScoreFile
8.4.3RandomAccess
Example:MaintainingtheHighScoreFileinOrder
8.5StandardFileTypes
8.5.1ImageFiles
8.5.2GIF
8.5.3JPEG
8.5.4TIFF
8.5.5PNG
8.5.6SoundFiles
WAV
8.5.7OtherFiles
HTML
EXE
8.6Summary
Chapter9Multimedia
9.1MouseInteraction
Example:DrawaCircleattheMouseCursor
Example:ChangeBackgroundColorUsingtheMouse
9.1.1MouseButtons
Example:DrawLinesUsingtheMouse
Example:AButton
9.2TheKeyboard
Example:Pressinga“+”CreatesaRandomCircle
Example:ReadingaCharacterString
9.3Animation
9.3.1ObjectAnimation
Example:ABallinaBox
Example:ManyBallsinaBox
9.3.2FrameAnimation
Example:ReadFramesandPlayThemBackasanAnimation
Example:SimulationoftheSpaceShuttleControlConsole(AClassThatWill
DrawanAnimationataSpecificLocation)
9.4RGBAColors–Transparency
9.5Sound
Example:PlayaSound
Example:ControlVolumeUsingtheKeyboard.PauseandUnpause
Example:PlayaSoundEffectattheRightMoment:Bounces
9.6Video
Example:Carclub–DisplaytheVideocarclub2.mpg(Annotated)
Exercise:ThresholdaVideo(ProcessingPixels)
9.7Summary
Chapter10BasicAlgorithms
10.1Sorting
10.1.1SelectionSort
10.1.2MergeSort
10.2Searching
10.2.1Timings
10.2.2LinearSearch
10.2.3BinarySearch
10.3RandomNumberGeneration
10.3.1LinearCongruentialMethod
10.4Cryptography
10.4.1One-TimePad
10.4.2PublicKeyEncryption(RSA)
Example:EncrypttheMessage“DepartatDawn”UsingRSA
10.5Compression
10.5.1HuffmanEncoding
10.5.2LZWCompression
10.6Hashing
djb2
10.6.1sdbm
10.7Summary
Chapter11ProgrammingfortheSciences
11.1FindingRootsofEquations
11.2Differentiation
11.3Integration
11.4Optimization:FindingMaximaandMinima
11.4.1NewtonAgain
11.4.2FittingDatatoCurves–Regression
11.4.3EvolutionaryMethods
11.5LongestCommonSubsequence(EditDistance)
11.5.1DeterminingLongestCommonSubsequence(LCS)
11.6Summary
Chapter12HowtoWriteGoodPrograms
12.1ProceduralProgramming–WordProcessing
12.1.1Top-Down
12.1.2Centering
12.1.3RightJustification
12.1.4OtherCommands
12.2ObjectOrientedProgramming–Breakout
12.3DescribingtheProblemasaProcess
12.3.1InitialCodingforaTile
12.3.2InitialCodingforthePaddle
12.3.3InitialCodingfortheBall
12.3.4CollectingtheClasses
12.3.5DevelopingthePaddle
12.3.6BallandTileCollisions
12.3.7BallandPaddleCollisions
12.3.8FinishingtheGame
12.4RulesforProgrammers
12.5Summary
Chapter13CommunicatingwiththeOutsideWorld
13.1Email
Example:SendanEmail
13.1.1ReadingEmail
Example:DisplaytheSubjectHeadersforEmailsinInbox
13.2FTP
Example:DownloadandDisplaytheREADMEFilefromanFTPSite
13.3CommunicationBetweenProcesses
Example:AServerThatCalculatesSquares
13.4Twitter
Example:ConnecttotheTwitterStreamandPrintSpecificMessages
13.5CommunicatingwithOtherLanguages
Example:FindTwoLargeRelativelyPrimeNumbers
13.6Summary
Chapter14ABriefGlibReference
14.1Glibtkinter
14.2Images
14.3DynamicGlib
14.4Video
14.5Audio
14.6Interaction
14.7Other
Index
Preface
This book is intended to teach introductory programming. Material is included for the
introductory computer science course, but also for students and readers in science and
other disciplines. I firmly believe that programming is an essential skill for all
professionalsandespeciallyacademicsinthe21stcenturyandhaveemphasizedthatinthe
contentdiscussedinthebook.
Thebookusesa“just-in-time”approach,meaningthatItrytopresentnewinformation
just before or just after the reader needs it. As a result, there are numerous examples,
carefullyselectedtofitintotheirproperplacesinthetext.Nottoosoon,andnottoolate.
Ibelieveinobject-orientedprogramming.Mymastersthesisinthelate1970swason
that subject, cut my teeth on Simula, was there when C++ was created, and knew the
creator of Java. I do not believe that object-oriented programming is the only solution,
though, and realized early that good objects can only be devised by someone who can
alreadyprogram. Iam thereforenot an“objects first”instructor, but a “whateverworks
best”instructor.
Manyoftheexamplesinvolvecomputergamesandgamedevelopment.Asweknow,
themajorityofundergraduatestudentsplaygames.Theyunderstandthembetterthan,say,
accountingorinventorysystems,whichhavebeenthetypicalearlyassignments.Ibelieve
inpresentingstudentsassignmentsthatareinteresting.
Idon’tthinkthatcateringtoanyparticularlanguageforminanintroductorytextserves
thestudentorthelanguage.Thestudent,ifsensible,willlearnotherlanguages.Bringing
Python idioms into play too soon may interfere with the generality of the ideas being
presentedandwillnotassistthestudentwhenlearningJava,C++,orRuby.
This book introduces a multimedia code module Glib that can assist the programmer
withgraphics,animation,sound,interaction,andvideo.Glibisincludedonthecompanion
discorcanbedownloadedfromthebook’swebsite.Thebasiclibrary,staticGlib,needs
nothingbutastandard3.4orbetterinstallationofPython.Itusestkinterasabasis,which
is distributed with the language. The expanded library uses pygame, and that is easily
downloaded and installed. The extended Glib, called dynamic Glib, allows exactly the
same interface as does static Glib, but extends it to also include sound, interface, and
video.Thus,ifstaticGlibcompilesandrunsaprogram,thendynamicGlibshouldtoo.
Thereisawikiconcerningthebookathttps://sites.google.com/site/pythonparker/andI
am happy to receive comments, code fixes, extensions, extra teaching material, and
general suggestions. I see a good textbook as a community, and encourage everyone –
especially first year students, the target audience of this book - to send me their
experiencesandideas.
Software(anycomputerprogram)isubiquitous.Cars,phones,refrigerators,television,
(and almost everything in our society) are computerized. Decisions made about how a
programistobebuilttendtosurvive,andevenaftermanymodifications,theycanaffect
how people use that device or system. Creating efficient software helps in achieving a
productiveandhappycivilization.
Python is a great language for beginning programmers. It is easy to write the first
programs,becausetheconceptualoverheadissmall.Thatis,there’snoneedtounderstand
what“void”or“public”meansattheoutset.Pythondoesmanythingsforaprogrammer.
Do you want something sorted? It’s a part of the language. Lists and hash tables
(dictionaries)areapartofthelanguage.Youcanwriteclasses,butdonothaveto,soitcan
be taught objectsfirst or not. The required indentation means that it is much harder to
placecodeincorrectlyinloopsorifstatements.TherearehundredsofreasonswhyPython
isagreatidea.
Anditisfree.Thisbookwaswrittenusingversion3.4,andwiththePyCharmAPI.The
modulesusedthatrequiredownloadarefew,butincludePyGameandtweepy.Allfree.
OverviewofChapters
Here’s a brief outline of the book. It can be used to teach computer science majors or
sciencestudentswhowishtohaveacompetencyinprogramming.
Chapter 0: Historical and technological material on computers. Binary numbers, the
fetch-excutecycle.Thischaptercanbeskippedinsomesyllabi.
Chapter 1: Problem solving witha computer; breaking a problem down so itcan be
solved. The Python system. Some simple programs involving games that introduce
variables,expressions,print,types,andtheifstatement.
Chapter 2: Repetition in programming: while and for statements. Random numbers.
Countingloops,nestedloops.Drawingahistogram.Exceptions(try-except).
Chapter3:Stringsandstringoperations.Tuples,theirdefinitionanduse.Listsandlist
comprehension. Editing, slices. The bytes type. And set types. Example: the game of
craps.
Chapter4:Functions:modularprogramming.Definingafunction,callingafunction.
Parameters,includingdefaultparameters,andscope.Returnvalues.Recursion.TheGame
ofSticks.Variableparameterlists,assigningafunctiontoavariable.Findthemaximumof
amathematicalfunction.Modules.GameofNim.
Chapter5:Files.Whatisafileandhowarefilesrepresented.Propertiesoffiles.File
exceptions.Input,output,append,open,close.Commaseparatedvalue(CSV)files.Game
ofJeopardy.Thewithstatement.
Chapter6:Classesandobjectorientation.Whatisanobjectandwhatisaclass?Types
andclasses.Pythonclassstructure.Creatinginstances,__init__andself.Encapsulation.
Examples: deck of playing cards; a bouncing ball; Cat-a-pult. Designing with classes.
Subclassesandinheritance.Videogameobjects.Ducktyping.
Chapter7:Graphics.TheGlibmodule.Drawingwindow;colorrepresentation,pixels.
Drawing lines, curves, and polygons. Filling. Drawing text. Example: Histogram, Pie
chart.Imagesandimagedisplay,gettingandsettingpixels.Thresholding.Generativeart.
Chapter 8: Data and information. Python dictionaries. Latin to English translator.
Arrays,formattedtext,formattedinput/output.Meteoritelandingdata.Non-textfilesand
thestructmodule.Highscorefileexample.Randomaccess.Imageandsoundfiletypes.
Chapter9:Digitalmedia:dynamicGlibmodule.Usingthemouseandthekeyboard.
Animation. Space shuttle control console example. Transparent colors. Sound: playing
soundfiles,volume,pause.Video:playandpositionavideo,accessingframesandpixels
inavideo.
Chapter 10: Basic algorithms in computer science. Sorting (selection, merge) and
searching (linear, binary). Timing code execution. Generating random numbers;
cryptography;datacompression(includingHuffmancodesandRLE);hashing.
Chapter 11: Programming for Science. Roots of equations; differentiation and
integration. Optimization (minimum and maximum) and curve fitting (regression).
Evolutionaryalgorithms.Longestcommonsubsequence,oreditdistance.
Chapter12:Writinggoodcode.Awalkthroughtwomajorprojects:awordprocessor
written as procedural code and a breakout game written as object oriented code. A
collectionofeffectiverulesforwritinggoodcode.
Chapter 13: Dealing with real world interfaces, which tend to defined for you.
ExamplesareEmail(sendandreceive),FTP,inter-processcommunication(client-server),
Twitter,callingotherlanguageslikeC++.
Chapter14:AreferenceforbothversionsofGlib.
ChapterCoverageforDifferentMajors
Acomputerscienceintroductioncouldusemostchapters,dependingonthebackground
ofthestudents,butChapters0,7,9,and/or11couldbeomitted.
Anintroductiontoprogrammingforsciencecouldomitchapters0,10,12.
Chapter13isalwaysoptional,butisinterestingasitexplainshowsocial
mediasoftwareworksundertheinterface.
Basicintroductiontoprogrammingfornon-scienceshouldinclude
Chapters0,1,2,3,4,5,and7.
CompanionFiles(Discincludedinphysicalbookorfiles
availablefordownloading)
Thecompanionfilescontainusefulmaterialforeachchapter:
•Selectedexercisesaresolved,includingworkingcodewhenthatisapartofthe
solution.
•AllsignificantprogrammingexamplesareprovidedasPythoncodefiles(over100),
thatcanbecompiledandexecuted,andthatcanbemodifiedasexercisesorclass
projects.Thisincludessampledatafileswhenappropriate.
•AnimportantaspectofthisbookistheuseofagraphicslibrarynamedGlib.Source
codeforthismoduleisprovidedonthediscandonline.Therearetwoversions:one
thatworkswiththebuilt-inmoduletkinterwhichallowsgraphics,andasecondthat
extendsthepreviousmoduleusing
pyGameandallowsvideos,interaction,andsound.
•Allfiguresareavailableasimages,infullcolor.
InstructorAncillaries
•Solutionstoalmostalloftheprogrammingexercisesgiveninthetext.
•MSPowerPointlecturesprovidedforanentiresemester(35files)includingsome
newexamplesandshortvideos.
•Likelythemostimportantaspectofthisbook,asidefromtheverypractical
viewpoint,istheprovisionoftheGlibgraphicsandmultimedialibrary.Thiscomes
intwoversions:auniversalversionthathandlesbasicgraphicsandthatcanexecute
withoutanyextrainstallationstep;andthefullmultimediaextensionthathandles
sound,video,andinteraction,butthatrequiresthatpyGamebeinstalled,whichisa
simpleprocess.
•AllofthePythoncodethatappearsinthebookshasbeenexecuted,andallcomplete
programsareprovidedas.pyfiles.Someofthenumerousprogrammingexamples
(over100)thatareexploredinthebookandforwhichworkingcodeisincluded:
oAninteractivebreakoutgame
oAtextformattingsystem
oPlottinghistogramsandpiecharts
oReadingTwitterfeeds
oPlayJeopardyUsingaCSVDataSet
oSendingandreceivingEmail
oAsimpleLatintoEnglishtranslator
oRock-Paper-Scissors
•HundredsofansweredmultiplechoicequizandexaminationquestionsinMSWord
filesthatcanbeeditedandusedinvariousways.
DedicatedWebSite
An online community has been started at https://sites.google.com/site/pythonparker/ for
comments, new exam questions and exercises, extra code, and as a place to report
problems.
Pleaseconsidercontributingmaterialtotheon-linecommunity,anddohavefun.Ifyou
don’t,thenyou’redoingitwrong.
J.Parker
October2016
CHAPTER0
MODERNCOMPUTERS
0.1CalculationsbyMachine
0.2HowComputersWorkandWhyweMadeThem
0.3ComputerSystemsareBuiltinLayers
0.4ComputerNetworks
0.5Representation
0.6Summary
Inthischapter
Humansaretoolmakersandtoolusers.Thisisnotuniqueintheanimalkingdom,butthe
facilitythathumanshavewithtoolsandthevarietyofapplicationswehaveforthemdoes
make us unique. Starting with mechanical tools (machines) like levers and wheels that
could lighten the physical effort of everyday life, more and more complex and specific
deviceshavebeencreatedtoassistwithallfacetsofourlives.Thiswasextendedinthe
twentiethcenturytoassistingwithmentalefforts,specificallycalculation.
Computers are devices that humans have built in order to facilitate complex
calculations.Earlycomputerswereusedtodosomeofthecomputationsneededtodesign
thefirstnuclearbombs,butnowcomputersseemtobeeverywhere,evenembeddedwithin
carsandkitchenappliances,andevenwithinourownbodies.Thesuccessofthesedevices
insuchawiderangeofapplicationareasisaresultoftheirabilitytobeprogrammed
thatis,thedeviceitselfisonlyapotentialwhenfirstbuiltandhasnospecificfunction.It
isdesignedtobeconfiguredtodoanytaskthatrequirescalculations,andtheconfiguring
processiswhatwecallprogramming.
Tosomeextentthishastakentheplaceofalotofothertooldevelopmentthatusedto
be done by engineers. When designing a complex machine like an automobile, for
example,there usedto be alot of mechanicalwork involved.The careful timingof the
currenttothesparkplugwasaccomplishedbyrotatingshaftswithsensors,andresultedin
thefiringofeachcylinderatthecorrectmoment.Theairtogasolinemixturefedintothe
enginewascontrolledbytubesandcablesandsprings.Nowallofthesethingsandmany
morearedoneusingcomputersthatsenseelectricand magneticevents,docalculations,
andsendelectricalcontrolsignalstoactuatorsintheengine.Thesamecomputercanbe
usedtocontrolarefrigerator,maketelephonecallsonacellularphone,changechannels
onatelevision,andwakeyouupinthemorning.Itistheflexibilityofthecomputerthat
has led to them becoming a dominant technology in human society, and the flexibility
comeslargelyfromtheirabilitytobeprogrammed.
0.1 CALCULATIONSBYMACHINE
People have been calculating things for thousands of years, and have always had
mechanicalaidstohelp.
Whensomeoneprogramsacomputer,theyarereallycommunicatingwithit.Itisavery
imperativeandprecisecommunicationtobesure.Imperativebecausethecomputerhasno
choice;itisbeingtoldwhattodo,andwilldoexactlythat.Precisebecauseacomputer
doesnotapplyanyinterpretationtowhatitisbeingtold.Humanlanguagesarevagueand
subject to interpretation and ambiguity. There are sentences that are legal in terms of
syntax that have no real meaning: “Which is faster, to Boston or by bus?” is a legal
sentence in English that has no meaning. Such things are not possible in a computer
language. Also, computers do not think and so can’t evaluate a command that would
amount to “expose the patient to a fatal dose of radiation” with any skepticism. As a
result,we,asprogrammers,mustbecarefulandpreciseinwhatweinstructthemachineto
do.
Whenhumanscommunicatewitheachotherweusealanguage.Similarly,humansuse
languagestocommunicatewithcomputers;itiseasyforus.Suchlanguagesareartificial
(humansinventedthemforthispurpose,allatonce),terse(therearefewifanymodifiers,
no way to express emotions or graduations of any feeling), precise (each item in the
language means one thing), and written (we do not speak to the computer in a
programminglanguage.Notyet,perhapsnever).
Computerlanguagesoperateatahighlevel,anddonotrepresentthewaythecomputer
actually works. For the purposes of learning to program there are a few fundamental
thingsthatneedtobeknownaboutcomputers.It’snotrequiredtoknowhowtheyoperate
electronically,buttherearebasicprinciplesthatshouldbeunderstoodinordertoputthe
processofusingcomputersinpracticalcontexts.
0.2 HOWCOMPUTERSWORKANDWHYWEMADE
THEM
Thereasonpeopleusecomputersisdifferentdependingonthepointinhistoryinwhich
one looks, but the military always seems to be involved. There have been many
calculating devices built and used throughout history, but the first one that would have
been programmable was designed by Charles Babbage. The military, as well as the
mathematiciansoftheday,wereinterestedinmoreaccuratemathematicaltables,suchas
those for logarithms. At the time these were calculated by hand, but the idea that a
machine could be built to compute more digits of accuracy was appealing. This would
havebeenamechanicaldeviceofgearsandshafts,butitwasnotcompletedduetobudget
andcontractingissues.
Babbage continued his work in design and created, on paper, a programmable
mechanicaldevicecalledtheanalyticalenginein1837.Whatdoesprogrammablemean?
Acalculationdeviceismanipulatedbytheoperatortoperformasequenceofoperations:
addthistothat,thensubtractthisanddividebysomethingelse.Onamoderncalculator
thiswouldbedoneusingasequenceofkeypresses,butonolderdevicesitmayinvolve
movingbeadsalongwiresorrotatinggearsalongshafts.Nowimaginethatthesequence
ofkeypressescanbeencodedonsomeothermedia:asetofcams,orplugsintosockets,
orholespunchedintocards.Thisisaprogram.
Suchasetofpunchedcardsorcamswouldbesimilartoasetofinstructionswrittenin
English and given to some human to calculate, but would instead be coded in a form
(language)thatthecomputingdevicecoulduseimmediately.Thedirectionsonthecards
could be changed so that something new could be computed as needed. The difference
enginewouldonlyfindlogarithmsandtrigonometricfunctions,butadevicethatcouldbe
programmedin this way could, intheory,calculateanything. The analytical enginewas
programmedbypunchingholesinstiffcards,anideathatwasderivedfromtheJacquard
loom of the day. The location of holes would indicate either an operation (e.g., add,
subtract,etc.)ordata(anumber).Asequenceofsuchcardswouldbeexecutedoneata
timeandyieldavalueattheend.
Althoughtheanalyticalenginewasnevercompleted,aprogramwaswrittenforit,but
notbyhim.Theworld’sfirstprogrammermayhavebeenawoman,AugustaAdaKing,
CountessofLovelace.SheworkedwithBabbageforafewyearsandwroteaprogramto
computeBernoullinumbers.Thisisthefirstalgorithmeverdesignedforacomputerandis
often claimed to be the first computer program ever written, although it was never
executed.
The very concept of programmability is a more important development than is the
developmentofthedifferenceoranalyticalengines.Theideathatamachinecanbemade
tododifferentthingsdependingonauser-definedsetofinstructionsistheverybasisofall
moderncomputers,whiletheuseofmechanicalcalculationhasbecomeobsolete;itistoo
slow,expensive,andcumbersome.Thisiswhereitbegan,though,andtheprogramming
conceptisthesametoday.
During World War II computers made the leap to being electrical. Work on breaking
codesandbuildingtheatomicbombrequiredlargeamountsofcomputing.Initiallysome
ofthiswasprovidedbyroomsfullofhumansoperatingmechanicalcalculators,butthey
couldnotkeepupwiththedemand,soelectroniccomputersweredesignedandbuilt.The
firstwasColossus,designedandbuiltbyTommyFlowersin1943.Itwascreatedtohelp
breakGermanmilitarycodes,andanupdatedversion(MarkII)wasbuiltin1944.
IntheUnitedStatestherewasaneedforcomputationalpowerinLosAlamoswhenthe
firstnuclearweapons werebeing built.Electro-mechanicalcalculators werereplaced by
IBMpunched-cardcalculators,originallydesignedforaccounting,andthesewerealittle
faster than the humans running calculators, but could run twenty-four hours a day and
made fewer errors. This computer was programmed by plugging wires into sockets to
createnewconnectionsbetweencomponents.
0.2.1 Numbers
Theelectroniccomputersdescribedsofar,andthoseofthe1940sgenerally,hadalmost
no storage for numbers. Input was through devices like cards, and they could have
numbersonthem.Theycouldbetransferredtothecomputationunit,thenmovedaheador
back,andperhapsreadagain.Memorywasaprimitivething,andvariousmethodswere
devisedtostorejustafewdigits.Asignificantadvancecamewhenengineersdecidedto
usebinarynumbers.Thiswillrequiresomeexplanation.
Electronicdevicesusecurrentandvoltagetorepresentinformation,suchassoundsor
pictures(radioand television).One ofthe simplestdevices isa switch,which canopen
and close a circuit and turn things like lights on and off. Electricity needs a complete
circuitorroutefromthesourceofelectrons,thenegativepoleofabatteryperhaps,tothe
sink,whichcouldbethepositivepole.Electrons,whichiswhatelectricityis,inasimple
sense,flowfromthenegativetothepositivepolesofabattery.Electricitycanbemadeto
do work by putting devices in the way of the flow of electrons. Putting a lamp in the
circuitcancausethelamptolightup,forexample.
A switch makes a break in the circuit, which stops the electrons from flowing; they
cannotjumpthegap.Thiscausesthelamptogodark.Thisseemsobvioustoanyonewith
electriclightsintheirhouse,butwhatmaynotbesoobviousisthatthiscreatestwostates
of the circuit, on and off. These states can be assigned numbers. Off could be 0, for
example,andoncouldbe1.Thisishowmostcomputersrepresentnumbers:ason/offor
1/0states. Tobe more clearabout this way ofrepresenting numbers, considerthe usual
way,whichiscalledpositionalnumbering.
Mosthumansocietiesnowuseasystemthatusestendigits:0,1,2,3,4,5,6,7,8,and
9.Thenumber123isacombinationofdigitsandpowersoften.Itisashorthandnotation
for100+20+3,or1×102+2*101+3*100.Eachdigitismultipliedbyapoweroften
andsummedtogetthevalueofthenumber.Anyonewhohasbeentoschoolacceptsthis
anddoesnotthinkaboutit,butreallythevalueusedasthebasisofthesystem,ten,isnot
magical.Itsimplyhappenstobethenumberofdigitshumanshaveontheirhands.Any
basewouldworkalmostaswell.
Example:Base
Numbersthatuse4asabasecanonlyhavethedigits0,1,2,and3.Eachpositioninthe
numberrepresentsapowerof4.Thusthenumber123is,inbase4,1×42+2*41+3*40,
whichis1×16+2*4+3=16+8+3=27intraditionalbase10representation.
This could get confusing, what with various bases and such, so numbers will be
considered to be in base 10 unless specific by a suffix. 1234 is 123 in base 4, whereas
1238is123inbase8,andsoon.
Binary numbers can have digits that are 1 or 0. The numbers are in base 2, and can
thereforeonly have the digits 0 and 1. These numbers can be representedby the on/off
stateofaswitchortransistor,whichisanelectronicswitch,whichiswhytheyareusedin
electroniccomputers.Moderncomputersrepresentalldataasbinarynumbersbecauseitis
easytorepresentthosenumbersinelectronicform;avoltageisarbitrarilyassignedto“0”
and to “1.” When a device detects a particular voltage, it can then be converted into a
digit,andviceversa.If2voltsisassignedtoa0and5voltsisassignedtoa1,thenthe
followingcircuitcouldsignala0or1dependingonwhatswitchwasselected:
ConvertBinaryNumberstoDecimal
Considerthebinarynumber110112.Itcanbeconvertedinbase10bymultiplyingeach
digitbyitscorrespondingpoweroftwoandthensummingtheresults.
Someobservations:
•Terminology:Adigitinabinarynumberiscalledabit(forbinarydigit)
•Anyevennumberhas0asthelowdigit,whichmeansthatoddnumbershave1asthe
lowdigit.
•Anyexactpoweroftwo,suchas16,32,64,andsoon,willhaveexactlyonedigit
thatisa1,andallotherswillbe0.
•Terminology:Abinarydigitorbitthatis1issaidtobeset.Abitthatis0issaidtobe
clear.
ConvertDecimalNumberstoBinary
Going from base 10 to base 2 is more complicated than the reverse. There are a few
waystodothecalculation,buthere’sonethatmanypeoplefindeasytounderstand.Ifthe
lowest digit (rightmost) is 1 then the number is odd, and otherwise it is even. If the
number 7310 is to be converted into binary the rightmost digit will be 1, because the
numberisodd.
Thenextstepistodividethenumberby2,eliminatingtherightmostbinarydigit,the
one that was just identified, from the number. 7310 / 210 = 3610, and there can be no
fractionalpart,soanysuchpartistobediscarded.Nowtheproblemistoconvert3610to
binaryandthenappendthepartalreadyconvertedtothat.Is3610evenorodd?Itiseven,
sothenextdigitis0.Thefinaltwodigitsof7310inbinaryare01.
Theprocessisrepeated:
Divide36by2toget18,whichiseven,sothenextdigitis0.
Divide18by2toget9,whichisodd,sothenextdigitis1.
Divide9by2toget4,whichiseven,sothenextdigitis0.
Divide4by2toget2,whichiseven,sothenextdigitis0.
Divide2by2toget1,whichisodd,sothenextdigitis1.
Divide1by2toget0.Whenthenumberbecomes0,theprocessiscomplete.
Theconversionprocessgivesthebinarynumbersinreverseorder(righttoleft)sothe
resultisthat7310=10010012.
Isthiscorrect?Convertthisbinarynumberintodecimalagain:
10010012=1×20+1*23+1*26=1+8+64=7310.
Asummaryoftheprocessforconvertingxintobinaryis:
Startatdigitn=0(rightmost)
repeat
Ifxiseven,thecurrentdigitnis0,otherwiseitis1
Dividexby2
Add1ton
Ifxiszero,thenendtherepetition
ArithmeticinBinary
Computers do all operations on data as binary numbers, so when two numbers are
added,forexample,thecalculationisperformedinbase2.Itturnsoutthatbase2iseasier
thanbase10forsomethings,andaddingisoneofthosethings.It’sdoneinthesameway
asinbase10butthereareonly2digits,andtwosarecarriedinsteadoftens.Forexample:
add010112to011102:
010112
011102
Startingthesumontherightasusual,thereisa0addedtoa1andthesumis1,justas
inbase10.
010112
011102
–––—
12
The next column in the sum contains two 1s. 1 + 1 is two, but in binary that is
representedas102.So,theresultof1+1is0withacarryof1:
1
010112
011102
–––—
012
Thenextcolumnhas1+0,butthereisacarryof1soitis1+0+1.That’s0witha1
carryagain:
1
010112
011102
–––—
0012
Nowthecolumnis1+1witha1carry,or1+1+1.Thisis1withacarryof1:
1
010112
011102
–––—
10012
Finally, the leading digits are 0 + 0 with a carry of 1, or 0 + 0 + 1. The answer is
110012.Isthiscorrect?Well,010112is1110and011102is142,and1110+1410=2510.
Theanswer110012is,infact,2510(confirmthis!)soitallworksout.
Binarynumberscanbesubjectedtothesameoperationsasanyotherformofnumber
(i.e.,multiplication,subtraction,division).Inaddition,theseoperationscanbeperformed
byelectroniccircuitsoperatingonvoltagesthatrepresentthedigits1and0.
0.2.2 Memory
Adding memory to computers was another huge step forward. A computer memory
mustholdsteadyacollectionofvoltagesthatrepresentdigits,andthedigitsarecollected
intosets,each ofwhich is anumber.A switchcan hold abinary digit,butswitches are
activated by people. Computer memory must store and recall (retrieve) numbers when
theyarerequiredbyacalculationwithouthumanintervention.
The first memories were rather odd things: acoustic delay lines store numbers as a
soundpassingthroughmercuryinatube.Thespeedofsoundallowsasmallnumberof
digits,around500,tobestoredintransitfromaspeakerononeendtoareceiveronthe
other. A phosphor screen can be built that is activated by an electric pulse and draws a
brightspotonascreenthatneedsnopowertomaintainit.Numberscanbesavedasbright
anddarkspots(1and0)andretrievedusinglightsensitivedevices.
Other devices were used in the early years, such as relays and vacuum tubes, but in
1947 the magnetic core memory was patented, in which bits were stored as magnetic
fieldsinsmalldonut-shapedelements.Thiskindofmemorywasfasterandmorereliable
than anything used before, and even held the data in memory without power being
applied,ahandythinginapowerfailure.Itwasalsoexpensive,ofcourse.
This kind of memory is almost never used anymore, but its legacy remains in
terminology:memoryisstillfrequentlyreferredtoascore,andacoredumpisstillwhat
manypeoplecallalistingofthecontentsofacomputermemory.
Currentcomputers use transistors tostore bitsand solidstate memoriesthat canhold
billionsofbits(Gigabits),butthewaytheyareusedinthecomputerisstillthesameasit
was.Bitsarecollectedintogroupsof8(abyte)andthengroupsofmultiplebytestofora
word. Words are collected into a linear sequence, each numbered starting at 0. These
numbersarecalledaddresses,andeachword,andsometimeseachbyte,canbeaccessed
by specifying the address of the data that is wanted. Acquiring the data element at a
particular location is called a fetch, and placing a number into a particular location is a
store.Acomputerprogramtoaddtwonumbersmightbespecifiedas:
Fetchthenumberatlocation21
Fetchthenumberatlocation433
Addthosetwonumbers
Storetheresultinlocation22
Thismayseemlikeaverbosewaytoaddtwonumbers,butrememberthatthiscanbe
accomplishedinatinyfractionofasecond.
Memoryisoftenpresentedtobeginningprogrammersasacollectionofmailboxes.The
addressisanumberidentifyingthemailbox,whichalsocontainsanumber.Thereissome
specialmemoryinthecomputerthathasnospecificaddress,andisreferredtoinvarious
ways.Whenafetchisperformed,thereisaquestionconcerningwherethevaluethatwas
fetchedgoes.Itcangotoanothermemorylocation,whichisamoveoperation,oritcango
intooneofthesespeciallocations,calledregisters.
Acomputercanhavemanyregistersorveryfew,buttheyareveryfastmemoryunits
that are used to keep intermediate results of computations. The simple program above
wouldnormallyhavetobemodifiedtogiveregistersthatareinvolvedintheoperations:
Fetchthenumberatlocation21intoregisterR0
Fetchthenumberatlocation433intoregisterR1
AddR1andR0andputtheresultintoR3
StoreR3(theresult)inlocation22
Thisisstillverbose,butmorecorrect.
0.2.3 StoredPrograms
The final critical step in creating the modern computer occurred in 1936 with Alan
Turing’s theoretical paperon the subject, butan actual computer toemploy the concept
was not built until 1948 when the Manchester Small-Scale Experimental Machine ran
whatisconsideredtobethefirststoredprogram.Ithasbeenthebasicmethodbywhich
computersoperateeversince.
Theideaistostoreacomputerprograminmemorylocationsinsteadofoncardsorin
some other way. Programs and data now coexist in memory, and this also means that
computerprogramshavetobeencodedasnumbers;everythinginacomputerisanumber.
Therearemanydifferentwaystodothis,andmanypossibledifferentinstructionsetsthat
have been implemented and various different configurations of registers, memory, and
instructions.Thecomputerhardwarealwaysdoesthesamebasicthing:firstitfetchesthe
next instruction to be executed, and then it decodes it and executes it. Executing an
instructioncouldinvolvemoreaccessestomemoryorregisters.
This repeated fetch then execute process is called, not surprisingly, the fetch-execute
cycle,andisattheheartofallcomputers.Thelocationoraddressofthenextinstruction
resides in a register called the program counter, and this register is incremented every
time an instruction is executed, meaning that instructions will be placed in consecutive
memorylocationsandwillbefetchedandexecutednaturallyinthatorder.Sometimesthe
instructionisfetchedintoaspecialregistertoo,calledtheinstructionregister, so that it
canbeexaminedquicklyforimportantcomponentslikedatavaluesoraddresses.Finally,
acomputerwillneedatleastoneregistertostoredata;thiswillbecalledtheaccumulator,
becausethat’susuallywhatsucharegisteriscalled.
Thestoredprogramconceptisactuallyprettydifficulttograsp,soadetailedexampleis
inorder.Imagineacomputerthathas12bitwordsasmemorylocationsandthatpossesses
theregistersdescribedabove.Thisisafictionalmachine,butitturnsouttohavesomeof
thepropertiesofanoldcomputerfromthe1960scalledthePDP-8.
Todemonstratetheexecutionofaprogramonastoredprogramcomputeraverysimple
program will be used: add 21 and 433, placing the answer in location 11. As an initial
assumption, assume that the value 21 is in location 9 and 433 is in location 10. The
programitselfwillresideinconsecutivememorylocationsbeginningataddress0.
The program should be described in English first. Note that it is very much like the
previous two examples, but in this case there is only one register to put data into, the
accumulator.Theprogramcouldperhapslooklikethis:
Fetchthecontentsofmemorylocation9intotheaccumulator
Addthecontentsofmemorylocation10totheaccumulator
Storethecontentsoftheaccumulatorintomemorylocation11
Theprogramisnowcomplete,andtheresult21+433shouldbefoundinlocation11.
Computerprogramsarenormallyexpressedintermsthatthe computercanimmediately
use,normallyasfairlyterseandprecisecommands.Thenextstageinthedevelopmentof
thisprogram is to use a symbolicform of the actual instructionsthat the computer will
use.
Thefirststepistomovethecontentsoflocation9totheaccumulator.Theinstruction
thatdoesthiskindofthingiscalledLoadAccumulator,shortedasthemnemonicLDA.
Theinstructionwouldbeinlocation0:
0:LDA9#Loadaccumulatorwithlocation9
The text following the “#” character is ignored by the computer, and is really a
commenttoremindtheprogrammerwhatishappening.Thenextinstructionistoaddthe
contents of location 10 to the accumulator; the instruction is ADD and it is placed in
address1:
1:ADD10#Addcontentsofaddress10totheaccumulator
Finally,the result, current in the accumulator register,will be savedinto the memory
locationataddress11.ThisisaStoreinstruction:
2:STO11#Answerintolocation11
Theprogramiscomplete.ThereisaHaltinstruction:
3:HLT#Endofprogram
If this program starts executing at address 0, and if the correct data is in the correct
locations,thentheresult454shouldendupinlocation11.Buttheseinstructionsarenot
yetinaformthecomputercanuse.Theyarecharacters,textthatahumancanread.Ina
stored program computer these instructions must be encoded as numbers, and those
numbersmustagreewiththeonesthecomputerwasbuilttoimplement.
Aninstructionmustbeabinarynumber,soallofthepossibleinstructionshavenumeric
codes.Aninstructioncanalsocontainamemoryaddress;theLDAinstructionspecifiesa
memorylocationfromwhichtoloadtheaccumulator.Boththeinstructioncodeandthe
addresshavetobeplacedintoonecomputerword.Thedesignersofthecomputerdecide
howthatwillbedone,andtheprogrammershavetolivewiththeresult.
This computer has 12 bit words. Imagine that the upper 3 bits indicate what the
instructionis.Thatis,atypicalinstructionisformattedlikethis:
Thereare9bitsatthelower(right)endoftheinstructionforanaddress,and3atthetop
endforthecodethatrepresentstheinstruction.ThecodeforLDAis3;thecodeforADD
is5andthecodeforSTOis6.HLTonmostcomputersthathavesuchaninstructionis
code0.Hereiswhattheprogramlookslikeasnumbers:
Code3Address9
Code5Address10
Code6Address11
Code0Address0
Thesehaveto bemade intobinary numbersto bestored in memory, butthat’spretty
easy.FortheLDAinstructionthecode310is0112andtheaddressis910=0000010012,
so the instruction as a binary number is 011 0000010012, where the space between the
codeandtheaddressisonlypresenttomakeitobvioustoapersonreadingit.
The ADD instruction has code 510, which is 1012, and the address is 10, which in
binaryis00010102.Theinstructionis1010000010102.
The STO instruction has code 6, which is 1102, and the address is 11, which is
0010112.Theinstructionis1100000010112.
TheHLTinstructioniscode0,orin12bitbinary0000000000002.
Thecodes aremade up bythe designersof the computer. Whenmemory is setup to
containthisprogramhere’swhatitlookslike:
Thisishowmemorylookswhentheprogrambegins.Theactofsettingupthememory
likethissothattheprogramcanexecuteiscalledloading.Thebinarynumbersinmemory
locations9and10are21and433respectively(checkthis!),whicharethenumberstobe
summed.
Of course there are more instructions than these in a useful computer. There is not
alwaysasubtractinstruction,butsubtractioncanbedonebymakinganumbernegative
andthenadding,sothereisoftenaNEGateinstruction.Settingtheaccumulatortozerois
acommonthingtodo,sothereisaCLA(ClearAccumulator)instruction;andthereare
manymore.
The fetch-execute cycle involves fetching the memory location addressed by the
programcounterintotheinstructionregister,incrementingtheprogramcounter,andthen
executingtheinstruction.Executioninvolvesfiguringoutwhatinstructionisrepresented
bythecodeandthensendingtheaddressordatathroughthecorrectelectroniccircuits,a
processbeyondanythingthischapterwilladdress.
Averyimportantinstructionthatthisprogramdoesnotuseisabranch.Theinstruction
BRA0willcausethenextinstructiontobeexecutedstartingatmemorylocation0.This
allows a program to skip over some instructions or to repeat some many times. A
conditional branch will change the current instruction if a certain condition is true. An
example would be Branch if Accumulator is Zero (BAZ), which will only perform a
branch if, as the instruction indicates, there is a value of zero in the accumulator. The
combinationofarithmeticandcontrolinstructionsmakesitpossibleforaprogrammerto
describeacalculationtobeperformedveryprecisely.
0.3 COMPUTERSYSTEMSAREBUILTINLAYERS
Enteringaprogramasbinarynumbersusingswitchesisaverytedious,time-consuming
process. Lacking a disk drive, the early computers depended on other kinds of storage:
punched cards again, or paper tape. It should be understood that because there was no
permanent storage, booting one of these machines often meant toggling a small “boot
loader”program,thenreadingapapertape.Nowthecomputerwouldrespondsensiblyto
itsperipheraldevices,likeaprinterorcardreader.Thepapertapecontainedaprimitive
“operating system” that would control the few devices available. That’s what operating
systemsdo:allocateresourcesandcontroldevices.
Thebootloader(bootstrapprogram)isthelowestlayerofsoftware.Itwasprovidedby
thecomputermanufacturer,buthastobeenteredbytheuser.Thepapertapesystemwas
the second layer, and the user did not have to write this program. Gradually more and
morelayerswerewrittensoastoprovidetheuserwithahighlevelofabstractionrather
than having to understand the entire machine. After all, physicists and engineers have
otherthingstodoratherthantendtothecomputer.
Whendiskdrivesbecameavailable,theoperatingsystemwouldbestoredonthem,and
abootstraploaderwouldbesavedinaspecialsectionofmemorythatcouldnotbeerased
(read only memory) so that when the computer was turned on it would run the loader,
which would load the operating system. Very convenient, and it is essentially what
happenstodayonWindows.
Thisoperating systemon the diskdrive is athird layerof software. Itprovides basic
hardwareallocationfunctionalityandalsogivestheuseraccesstosomeprogramstouse
forprintingandsavingthingsondisk—afilesystem.
0.3.1 AssemblersandCompilers
Programming a computer could still be a daunting task if done in binary, so the first
thing that was provided was an assembler. This was a program that would permit a
programmertoentera textprogramthatcould beconvertedinto abinaryexecutable.It
would allow memory locations to be named instead of using an absolute number as an
address,andwouldconverttextoperationcodesandaddressesintobinaryprograms.The
additionprogramfromtheprevioussectioncouldbewritteninassembleras:
LDAData1
ADDData2
STORes
HLT
Data1:21
Data2:433:
Res:0
Usuallyonelineoftextinanassemblercorrespondstoasingleinstructionormemory
location.It’sthesameprogrambutiseasierforaprogrammertounderstand because of
thenamedmemorylocationsandmnemonicinstructionnames.
Itismuchhardertodescribehowacompilerworks,butrelativelyeasytoexplainwhat
itdoes.Acompilertranslateshighlevellanguagestatementsintoassembler,whichinturn
convertsitintobinarycode.Compilerstranslatestatementslike:
A=21
B=433
C=A+B
into executable code. It is a very complex process, but essentially it allows the
programmer to declare that certain names represent integers, that values are to be
assigned,and that arithmeticcan be done. Thereare also more complexstatements like
conditionalexecutionofcodeandfunctioncallswithparameters,aswillbeseeninlater
chapters.
Compilersalsoimplementinputandoutputfromtheuser(readingfromakeyboardand
writing to the video screen), sophisticated data types, and mathematical functions. An
interpreter,whichiswhatthelanguagePythonis,doesapartofthecompilationprocess
but does not produce executable code. Instead, it simulates the execution of the code,
doingmostoftheworkinsoftware.TheJavalanguagedoesasimilarthinginmanycases.
Theprogramsthatsomeonewrites(software)createanotherlayerforsomeonetouse.
An example might be a database management system that gives a user access to a
computer that can query data for certain kinds of values. A graphics system gives a
programmeraccesstoasetofoperationsthatcandrawpictures.
0.3.2 GraphicalUserInterfaces(GUIs)
Mostcomputers now interfacewith their owners througha keyboard, one of thefirst
devicestobeinterfacedtoacomputer;amouse,thefirstdevicetopermit2Dnavigation
on a screen; and windows, a graphical construction that allows many independent
connectionstoacomputertoshareasinglevideoscreen.GUIsarepopularbecausethey
improve the users perception of what is happening on a computer. Previous computer
interfaceswerecompletelytextbased,soifsomethingwasgoingwronginaplacewhere
theuserwasnotlooking,thenitwouldprobablynotbenoticed.
Ontheotherhand,GUIsaremoredifficulttoprogram.Justopeninganewwindowina
Microsoft-basedoperatingsystemcanrequirescoresoflinesofC++codethatwouldtake
agreatdealoftimetounderstand.Naturally,itisthejobofaprogrammertobeabletodo
this, but it means that the average user could not create their own software that
manipulated the interface in any reasonable way. So, what is a window, and what’s
involvedinaGUI?
Awindow,intheoperatingsystemsense,isarectangleonthecomputerscreenwithin
which an exchange of information takes place between the user and the system. The
rectangle can generally be resized, removed from the screen temporarily (minimized),
moved,andclosed.Itcanbethoughtofasavirtualcomputerterminalinthateachonecan
dowhattheentirevideoscreenwasneededtodoinearlysystems.Whenthewindowis
active,ausercantypeinformationtobereceivedbytheprogramcontrollingit,andcan
manipulategraphicalobjectswithinthewindowusingamouseor,morerecently,byusing
their fingers on a touch screen. Without a mouse or something like it, a window-based
systemisprettymuchcrippled,sothetwoarealmostalwaysusedtogether.
The mouse is a variation on the tracker ball, and it is agreed that the German
engineeringcompanyTelefunkendevisedaworkingversionandwasthefirsttosellit.A
mouseislinkedthroughsoftwaretoacursoronthescreen,andleft-rightmotionsofthe
mousecauseleft-rightmotionsofthecursor;forwardandbackwardmotionsofthemouse
causethecursortomoveupanddownthescreen.Whenthecursorisinsideofawindow,
thenthatwindowisactive.Amousehasbuttons,andpressingamousebuttonactivates
whatever software object is related to the cursor position on the screen. This describes
thingsthatareobvioustoanyoneusedtocomputersbuiltsincethe1980s.
Widgets
Awidgetisagraphicalobjectdrawninawindoworotherwiseonacomputerscreen
thatcanbeselectedand/oroperatedusingthemouseandmousebuttons.Itisconnectedto
asoftwareelementthatwillbesentacontrolsignalornumericalparameterbyvirtueof
the widget being manipulated. That’s a pretty formal description, but a widget is
exemplifiedby the button, a very commonly used widget on web pages and interfaces.
Buttonscanbeusedtodisplayinformationaswellastocontrolaprogram.Somepopular
widgetsare:
Button:Whenthemousecursoriswithintheboundariesofthebuttononthescreen,
thebuttonissaidtobeactivated.Pressingamousebuttonwhenthebuttonwidgetis
activatedwillcausethesoftwareconnectedtothebuttontoperformitsfunction.
Radio Button: A set of two or more buttons used to select from a set of discrete
options.Onlyoneofthebuttonscanbeselectedatatime,meanthattheoptionsare
mutuallyexclusive.
CheckBox:Awaytoselectasetofoptionsfromalargerset.Thiswidgetconsistsof
acollectionofboxesorbuttonsthatcanbechosenbyclickingonthem.Whenchosen,
they indicate that fact by using a graphical change, sometimes a check mark but
sometimesacolororothervisualeffect.
Slider:Ahorizontalorverticalcontrolwithaselectiontoolthatcanbeslidalongthe
control.Therelativepositionofthecontroldictatesthevaluethatthewidgetprovides.
Thisvalueisoftendisplayedinatextbox,andtherangeisalsocommonlydisplayed.
Drop-downList: A box containing text that displays a complete set of options that
can be displayed when the mouse button is clicked within it. Then any one of the
optionscanbeselectedusingthemouseandthemousebutton.
Icon: An icon is a small graphical representation (pictogram) that represents the
functionofaprogramorfile.Whenselected,theprogramwillexecuteorthefilewill
beopened.
There are many other widgets and variations on the ones shown here. There are two
basicprinciplesatplay:
1.Thewidgetrepresentsanactivityusingacommonlyunderstoodsymbol,and
performsthatactivity,oronerelatedtothesymbol,whenselectedusingthemouse.
Thisisagraphicalandtactileoperationthatreplacesthetypingofacommandin
previouscomputersystems.
2.Thesoftwarethatimplementsthewidgetisamodule,apieceofsoftwarethatcan
bereusedandreconfiguredforvariouscircumstances.Abuttoncanbequickly
createdtoperformanynumberoftasksbecausetheprogramthatimplementsitis
designedforthatdegreeofflexibility.
0.4 COMPUTERNETWORKS
Schools, offices, and some homes are equipped with computer networks, which are
wiresthatconnectcomputerstogetherandsoftwareandspecialhardwarethatallowsthe
computers to communicate with each other. This allows people to send information to
eachotherthroughtheircomputers;alotofworkisdoneinacomputerreadableformin
anycase,anditisconvenienttoallowcomputerstoshareinformation.Buthowdoesthis
reallywork?
Computersuseelectricitytoperformcalculationsonbinarynumbers.Arbitraryvoltages
have been selected to represent 0 and 1, and so long as everyone agrees on that
representation, those voltages can be sent along a wire no matter how long and still be
numbersatthereceivingend.Aslongastwocomputersarebeingconnectedthisworks
fine,butiftwowiresareneededtoconnectanytwocomputersthensixareneededtofully
connectthreecomputerstoeachotherandtwelvetoconnectfourcomputers.Aroomwith
thirtynetworkedcomputerswouldbefullofwires(870toeachcomputer)!Theremustbe
abetterway.
Hawaiihasanunusualproblemwhenitcomestocomputernetworkcommunication.It
isacollectionofislands.Linkingthembycablesisanexpensiveproposition.Intheearly
1970sthefolksattheUniversityofHawaiihadagoodidea—tolinkthecomputersusing
radio. Radio transmission is really similar to wire transmission in many practical ways,
andallocating35radiofrequenciestoconnectonecomputeroneachislandtoallofthe
otherswouldhavebeenpossible,buttheirideawasbetter.Theyusedasingleradiolink
for all computers. When a computer wanted to send information along the network, it
wouldlistentoseeifanothercomputerwasalreadydoingso.Ifso,itwouldwait.Ifnot,it
would begin to send data to all of the other computers and would include in the
transmissionacodeforwhichcomputerwassupposedtoreceiveit.Allcouldhearit,but
allwouldknowwhichcomputerwasthecorrectdestinationsotheotherswouldignoreit.
ThissystemwascalledAlohanet.
There is a problem with this scheme. Two or more computers could try to send at
almost the same time, having noted that no other computer was sending when they
checked. This is called a collision, and is relatively easy to detect; the data received is
nonsense.Whenthathappenseachcomputerwaitsforarandomtime,checksagain,and
triesagaintosendthedata.Ananalogywouldbeameetingwheremanypeoplearetrying
tospeakatonce.
Obviously the busier the network is the more likely a collision will be, and the
retransmissions will make things worse. Still, this scheme works very well and is
functioningtodayintheformofthemostcommonnetworkingsysteminearth—Ethernet.
Ethernet is essentially Alohanet along a wire. It means that each computer has one
connectiontoit,ratherthanconnectionstoeachofthepossibledestinations,andcollisions
arepossible.Thereisanotherconsiderationthatmakesthisschemeworkbetter,andthatit
isuseofpackets.Informationalongthesenetworksissentinfixed-sizepackagesofafew
thousand bytes. In this way, the time needed to send a packet should be more or less
constant,andit’smoreefficientthansendingabitorabyteatatime.
Eachpacketcontainsasetofdatabytesintendedforanothercomputer,sowithinthat
packetshouldbesomeinformationaboutthedestination,thesender,andotherimportant
stuff.Forinstance,ifadatafileisbiggerthanapacket,thenithastobesplitupintoparts
tobesent.Thus,apartofthepacketisasequencenumberindicatingwhichpacketitis
(e.g.,number3of5).Ifaparticularpacketnevergetsreceivedforsomereason,thenthe
missing one is known, and the receiver can ask the sender for that packet to be resent.
Therearealsocodesthancanbeusedtodeterminewhetheranerrorhasoccurred.
0.4.1 Internet
The Internet is a computer network designed to communicate reliably over long
distances. It was originally created to be a reliable communications system that could
surviveanuclearattack,andwasfundedbythemilitary.Itisdistributed,inthatdatacan
besentfromonecomputertoanotherinachainuntilitreachesitsdestination.
Imagine a collection of a few dozen computers, and that each one is connected to
multiple others, but not directly to all others. Computer A wishes to send a message to
computerB,anddoessousingapacketthatincludesthedestination.ComputerAsends
themessagetoallcomputersthatitisconnectedto.Eachofthosecomputerssendsittoall
ofthecomputersthattheyareconnectedto,andsoonuntilthedestinationisreached.All
of the computers will receive every message, which is pretty inefficient, but so long as
thereexistssomepathfromAtoBthemessagewillbedelivered.
Itwouldbehardtotellwhentostopsendingamessageinthisscheme.Anotherwayto
do it is to have a table in each computer saying which computers in the network are
connectedtowhichothers.Amessagecanbesenttoacomputerknowntobeashortpath
to the destination, one computer at a time, and in this case not all computers see the
message,onlythe onesalong theroute do.Anewcomputer added to the networkmust
sendaspecialmessagetoalloftheotherstellingthemwhichoftheexistingcomputersit
isdirectlyconnectedto,andthismessagewillpropagatetoallmachines,allowingthemto
updatetheirmap.Thisisessentiallytheschemeusedtoday.
The Internet has a hierarchy of communication links and processors. First, all
computersontheInternethaveauniqueIP(InternetProtocol)addressthroughwhichthey
are reached. Because there are a lot of computers in the world, an IP address is a large
number.Anexamplewouldbe172.16.254.1(obtainedfromWikipedia).Whenacomputer
in,say,Portlandwantstosendamessageto,forexample,London,thePortlandcomputer
composes a packet that contains the message, its address, and the recipient’s address in
London.ThismessageissentalongtheconnectiontoitsInternetserviceprovider,which
isalocalcomputer,atarelativelowspeed,10megabitspersecondperhaps.Theservice
provider operates a collection of computers designed to handle network traffic. This is
calledaPointofPresence(POP)andcollectsmessagesfromalocalareaandconcentrates
themfortransmissionfurtherdowntheline.
Multiple POP sites connect to a Network Access Point (NAP) using much faster
connectionsthanusershavetoconnectwiththePOP.The NAPconcentratesevenmore
users, and provides a layer of addressing that can be used to send the data to the
destination. The NAP for the Portland user would have the message delivered to a
relativelylocalNAP,whichwouldsendittothenextNAPalongapathtothedestination
in London using an exceptionally fast (high bandwidth) data connection. The London
NAPwouldsendthemessagetotheappropriatelocalPOP,whichwouldinturnsenditto
thecorrectuser.
AnimportantconsiderationisthatthemessagecanbereadbyanyPOPnorNAPserver
alongtheroute.DatasentalongtheInternetispublicunlessitisproperlyencryptedbythe
users.
0.4.2 WorldWideWeb
The World Wide Web, or simply the Web, is in fact a layer of software above the
Internetprotocols.Itisawaytoaccessfilesanddataremotelythroughavisualinterface
provided by a program that runs on the users computer, a browser. When someone
accesses a web page, a file that describes that page is downloaded to the user and
displayed.Thatfileistextinaparticularformat,andthefilenameusuallyendsin“.html”
or“.htm.”Thefileholds adescriptionofhow todisplaythepage: whattexttodisplay,
whereimagescanbefoundthatarepartofthepage,howthepageisformatted,andwhere
otherconnectedpages(links)arefoundontheInternet.Oncethefileisdownloaded,allof
thehardworkconcernedwiththedisplayofthefile,suchasplayingsoundsandvideos
anddrawinggraphicsandtext,isdonebythelocal(receiving)computer.
TheWebisthebasisformostofthemodernadvancesinsocialnetworkingandpublic
dataaccess.TheInternetprovidestheunderlyingnetworkcommunicationsfacilitywhile
theWebusesthattofetchanddisplayinformationrequestedbytheuserinavisualand
auditory fashion. Podcasts, blogs, and wikis are simple extensions of the basic
functionality.
The Web demands the ability for a user in Portland to request a file from a user in
Londonandtohavethatfiledeliveredandmadeintoagraphicaldisplay,allwithasingle
click of a mouse button. Web pages are files that reside on a computer that has an IP
address, but the IP address is often hidden by a symbolic name called the Universal
Resource Locator (URL). Almost everyone has seen one of these:
http://www.facebook.com”isoneexample.Webpageseachhaveauniquepathoraddress
basedonaURL.Itisaprettyamazingfactthatanyonecancreateanewwebpagethat
usesitsveryownunambiguousURLatanytime,andthatmostoftheworldwouldbeable
toviewit.
TheWebisanexampleofwhatprogrammerscallaclient-serversystem.Theclientis
where the person requesting the web page lives, and is making a request. The server is
where the web page itself lives, and it satisfies the request. Other examples of such
systemswouldbeonlinecomputergames,Email,Skype,andSecondLife.
0.5 REPRESENTATION
Whenapplyingacomputertoataskorwritingaprogramtodealwithatypeofdata
thatseemstobenon-numeric,theissueofhowtorepresentthedataonthecomputerwill
invariably arise. Everything stored and manipulated on a computer has to be a number.
Whatifthedataisnotnumeric?
A fundamental example of this is character data. When a user types at the computer
keyboard,whatactuallyhappens?Eachkey,and some keycombinations(e.g.,shiftkey
and“1”helddownatthesametime),whenpressedwillresultinelectricalsignalsbeing
sent along a set of wires that connect to an input device on the computer, a USB port
perhaps. While knowing the details of USB and the keyboard hardware is beyond the
scopeofthisbook,itiseasytounderstandthatpressingakeycanresultinanidentifiable
combination of wires being given a voltage. This is in fact a representation of the
character, and one that underlies the one that will be used on the computer itself. As
describedpreviously,voltagescanbeusedtorepresentbinarynumbers.
Therepresentationofcharactersonacomputeramountstoanassignmentofanumber
toeachpossiblecharacter.Thisassignmentcouldbearbitrary,andforsomedataitis.The
valueoftheletter“a”couldbe1,“b”couldbe12,and“c”couldbe6.Thiswouldwork,
butitwouldbeapoorrepresentationbecausecharactersarenotinanarbitraryorder.The
letter“b”shouldbebetween“a”and“c”invaluebecauseitispositionedthereinthedata
set,thesetofcharacters.Inanycase,whencreatinganumericrepresentation,thefirstrule
is:
1.Iftherearearelativelysmallnumberofindividualdataitems,assignthem
consecutivevaluesstartingat0.Ifthereisapracticalreasontostartatsomeother
number,thendoso.
Thesecondruleconsiderstheexistingorderingoftheelements:
2.Incaseswheredataitemsareassignedconsecutivevalues,assigntheminamanner
thatmaintainsanypredefinedorderoftheelements.
Thismeansthatinadefinitionofcharacters,theletters“a,”“b,”and“c”should
appearinthatorder.
3.Incaseswheredataitemsareassignedconsecutivevalues,assigntheminamanner
thatmaintainsanypreexistingdistancebetweentheelements.
Thismeansthattheletters“a,”“b,”and“c”wouldbeadjacenttoeachotherinthe
numericrepresentationbecausetheyarenexttoeachotherinthealphabet.Italso
meansthatcharacterclasseswillstaytogether;theuppercaseletterswillbe
consecutive,thedigitswillalsohaveconsecutivecodessothatthecodefor“0”will
beadjacenttoandsmallerthanthecodefor“1”,andsoon.Thissetofthreerules
actuallycreatesaprettygoodmappingofcharacterstonumbers.However,thereare
morerulesformakingrepresentations.
4.Incaseswheredataitemsareassignedconsecutivevalues,assigntheminamanner
thatsimplifiestheoperationsthatarelikelytobeperformedonthedata.
Inthepresentexampleofcharacterdata,therearerelativelyfewplaceswherethis
rulewouldbeinvoked,butonewouldbewhencomparingcharacterstoeachother.
Acharacter“A”isusuallythoughttocomebefore“a,”sothismeansthatallofthe
uppercaseletterswillcomebeforealllowercaseones,inanumericalsense.
Similarly,“0”comesbefore“A,”soalldigitscomebeforealllettersinthe
representation.Aspacewouldcomebefore(i.e.,haveasmallervaluethan)any
characterthatprints.
Oneofthemostcommoncharacterrepresentations,namedtheAmericanStandard
CodeforInformationInterchangeorASCII,hasallofthesepropertiesandafew
others.ThestandardASCIIcharactersetlists128characterswithnumericalcodes
from0to127.Inthetablebelow,eachcharacterislistedwiththecodethat
representsit.Theyappearinnumericalorder.Thecharactersinorangeare
telecommunicationscharactersthatareneverusedbyatypicalcomputeruser;green
charactersarenon-printingcharactersthatareusedforformattingtextonapage;
lettersandnumbersforEnglisharered;specialcharacterslikepunctuationareblue.
Thespacecharacterisinsomesenseunique,andisblack.
Furtheronthesubjectofrepresentation,ifthereareaverylargenumberofpossible
datavalues,thenenumeratingthemwouldseemunreasonable.Thereareusually
otherwaystoattackthatsortofproblem.
5.Ifthedatacanbebrokenupintoenumerableparts,thentrytodothat.
Datescanbeanexampleofthiskindofdata.Therearetoomanydatestostoreas
discretevalues,asthereisnoactualday0andthereisnopracticalfinaldayinthe
generalcase.However,acommonwaytostateadateistogiveayear,amonth,and
aday.Thisisawkwardfromacomputerperspectivebecauseofthevariablenumber
ofdaysineachmonth,butworksprettywellforhumans.Eachcomponentis
enumerable,soapossiblerepresentationforadatewouldbeasthreenumbers:year,
month,day;itwouldbeYYYYMMDD,whereYYYYisafour-digityear,MMisa
numberbetween0(January)and11(December),andDDisanumberbetween0
and30,whichisthedayofthemonth.
Thisrepresentationshouldkeepthedatesinthecorrectsequence,soDec9,1957
(19571108)willcomeafterAug24,1955(19550723).However,anothercommon
operationondatesistofindthenumberofdaysbetweentwospecifieddates.Thisis
difficult,andtheonlyrepresentationthatwouldsimplifyitwouldbetostart
countingdaysatazeropoint.IfthatzeropointwereJan1,1900,thenthe
representationforthedateOct31,2017wouldbe43037.Thenumberofdays
betweentwodateswouldbefoundbysubtraction.However,printingthedateina
formforhumanstoreadisdifficult.Whenselectingarepresentation,themost
commonoperationsonthedatashouldbetheeasiestonestoperform.
Anotherexampleofthissortorrepresentationiscolor,whichwillbediscussedin
detailinalaterchapter.
6.Whenthedataispartofacontinuousstreamofrealvalues,thenitmaybepossible
tosamplethemand/orquantizethem.
Samplingmeanstorepresentasequencebyusingasubsetofthevalues.Imagineaset
ofnumberscomingfromaseismometer.Thenumbersequencerepresentsmeasurements
ofthemotionofthegroundcapturedcontinuouslybyamechanicaldevice.Itisnormally
OKtoignoresomeofthesevalues,knowingthatbetweenavalueof5.1(whateverthat
means)andavalueof6.3,thenumberswouldhavetakenonallpossiblevaluesbetween
thosetwo;that’swhatcontinuousmeans.
So instead of capturing an infinite number of values, which is not possible, why not
captureavalueeverysecond,ortenthofasecond,oratwhateverintervalmakessensefor
the data concerned. Some data will be lost. The important thing is not to lose anything
valuable.
The samething can bedone spatially. If someone is building a road, then it must be
surveyed.Aset ofheight values forpoints alongthearea tobe occupiedbythe roadis
collectedsothatamodelofthe3Dregioncanbebuilt.Butbetweenanytwopointsthat
can be sampled there is another point that could be sampled, on to infinity. Again, a
decisionismadetolimitthenumberofsamplessothatthemeasurementsaremadeevery
fewyards.Thislimitstheaccuracy,butnotinapracticalway.Theheightatsomespecific
pointmaynothavebeenmeasured,butitcanbeestimatedfromthenumbersaroundit.
The distance between two sample points is referred to casually as the resolution. In
spatial sampling it will be expressed in distance units and says something about the
smallestthingthatcanbepreciselyknown.Intimesamplingitisexpressedinseconds.
Quantization means how accurately each measurement is known. In high school
science,numbersthataremeasurementsaregiventosomenumberofsignificantfigures.
Measuringaweightas110.9881poundswouldseemimpossiblyaccurate,and111would
be a more reasonable number. Quantization in computer terms would be restricting the
numberofbitsusedtorepresentthevalue.Somethingthatisstoredasan8-bitnumbercan
have256distinctvalues,forexample.Iftheworld’stallestpersonisunder8feettall,then
using8bitstorepresentheightwouldmeanthat8feetwouldbebrokenupinto256parts,
whichis0.375inches;thatis,8feetx12inches/foot=96inches,anddividingthisinto
256parts=0.375.Thesmallestdifferenceinheightthatcouldbeexpressedwouldbethis
value,alittleoverathirdofaninch.
Quantization is reflected in the representation as a possible error in each value. The
greaterthenumberofbitspersamplethemoreaccuratelyeachoneisrepresented.Theuse
of sampling and quantization is very common, and is used when saving sounds (MP3),
images(JPEG),andvideos(AVI).
Thereareotherpossibleoptionsforcreatingarepresentationfordata,butthesixbasic
ideasherewillworkmostofthetime,aloneorincombination.Aprogrammerwillspend
mostofhisorhertimelivingwiththeconsequencesoftherepresentationstheychosefor
theirdata.Apoorchoicewillresultinmorecomplexcode,whichgeneratesmoreerrors
andlessoverallsatisfactionwiththeresult.Spendingalittleextratimeatthebeginning
analyzingthepossibilitiescansavealotofeffortlater.
0.6 SUMMARY
Computersaredevicesthathumanshavebuiltinordertofacilitatecomplexcalculations
and are tools for rapidly and accurately manipulating numbers. When humans
communicate with each other, we use a language. Similarly, humans use languages to
communicate with computers. A computer program can be thought of as a sequence of
operationsthatacomputercanperforminordertoaccomplishacalculation.Thekeyis
thatitmustbeexpressedintermsthatthecomputercando.
Early computers were mechanical, using gears to represent numbers. Electronic
computers usually use two electrical states or voltages to represent numbers, and those
numbersareinbinaryorbase2form.Electroniccomputershavememoriesthatcanstore
numbers, and everything stored in memory must be in numeric form. That includes the
instructionsthatthecomputercanexecute.
Computers have been around long enough to provide many layers of computer
programs that can assist in their effective use: graphical user interfaces, assemblers,
compilers for programming languages, web browsers, and accounting packages each
provideauserwithadifferentviewofacomputerandadifferentwaytouseit.Computers
can exchange data between each other using wires over short distances (computer
network) and long ones (Internet). The World Wide Web sits atop the Internet and
provides an easy and effective way for computers all over the world to exchange
informationinanyform.
Everythingstoredandmanipulatedonacomputerhastobeanumber.Whatifthedata
is not numeric? In that case a numeric representation has to be devised that effectively
characterizestheinformationwhilepermittingitsefficientmanipulation.
Exercises
1.Convertthefollowingbinarynumbersintodecimal:
a)0100000
b)0000100
c)0000111
d)0101010
e)0110100101
f)0111111
g)110110110
2.Convertthefollowingdecimalnumbersintobinary:
a)10
b)100
c)64
d)128
e)254
f)5
g)999
3.Corememorywouldnoteraseitselfwhenitspowersourcewasremoved.Give
reasonswhythisisavaluableproperty.
___________________________________________________
___________________________________________________
___________________________________________________
4.Specifyadevicethatisusedfor:
a)Outputonly
b)Inputonly
c)Bothinputandoutput
5.AdaCountessofLovelaceisgenerallyconsideredtobethefirstprogrammer,but
somecontraryinformationhascometolightrecently.Searchtheliteraturefortwo
articlesoneachsideoftheargumentandformulateaconclusion.Wasshe?
6.Whatisthedifferencebetweenacompilerandaninterpreter?Giveanexampleof
each.
7.IdentifyaGUIwidgetthatwasnotdiscussedinthischapter.Sketchitsappearanceand
describeitsoperation.Giveanexampleofasituationwhereitmightbeused.
8.GivetheASCIIcodesforthefollowingcharacters:
a)ꞌPꞌ
b)ꞌ;ꞌ
c)ꞌrꞌ
d)ꞌ,ꞌ
e)ꞌ=ꞌ
9.WhatisthevalueoftheASCIIcodeforthecharacter“1”minusthecodeforthe
character“0”?Whatis“2”-“0”?Whatdoesthissayaboutconvertingfromthe
characterformofanumberintoitsnumericvalueingeneral?
10.Considertheimaginarycomputerdevisedinthischapter.Ithasamemoryinwhich
eachlocationhas12binarydigits(bits)tostoreanumber.Inoneofthememory
locationsthevalue101000000000isseen.Whatisthis?Isitaninstruction,anumber,
acharacter,anaddress,orsomethingelse?Howcanthisbedetermined?
NotesandOtherResources
1.L.Carlitz.(1968).Bernoullinumbers,FibonacciQuarterly,6,71–85.
2.DigitalEquipmentCorporation.(1972).IntroductiontoProgramming,PDP-8
handbookseries,onlineversion
http://www.mirrorservice.org/sites/www.bitsavers.org/pdf/dec/pdp8/handbooks/IntroToProgramming1969.pdf
3.JamesEssinger.(2004).Jacquard’sWeb,OxfordUniversityPress,Oxford,ISBN
978-0-19-280578-2.
4.TonySale.TheColossusComputer1943–1996:HowItHelpedtoBreakthe
GermanLorenzCipherinWWII,M.&M.Baldwin,Kidderminster,2004,ISBN0-
947712-36-4.
5.StephenStephenson.(2013).AncientComputers,PartI-Rediscovery,2nd
Edition,ISBN1-4909-6437-1.
6.A.M.Turing.(1936).OnComputableNumbers,withanApplicationtothe
Entscheidungsproblem.
7.MichaelR.Williams.(1998).The“LastWord”onCharlesBabbage,IEEEAnnals
oftheHistoryofComputing,20(4),10–4,doi:10.1109/85.728225
8.JavierYanes.(2015).AdaLovelace:OriginalandVisionary,butNoProgrammer,
OpenMind,December9,2015,https://www.bbvaopenmind.com/en/ada-lovelace-
original-and-visionary-but-no-programmer/
CHAPTER1
COMPUTERSANDPROGRAMMING
1.1SolvingaProblemUsingaComputer
1.2ExecutingPython
1.3GuessaNumber
1.4Rock-Paper-Scissors
1.5SolvingtheGuessaNumberProblem
1.6SolvingtheRock-Paper-ScissorsProblem
1.7IFStatements
1.8Documentation
1.9Rock-Paper-ScissorsAgain
1.10TypesAreDynamic(Advanced)
1.11Summary
Inthischapter
The vast majority of computers that most people encounter are referred to as digital
computers. This refers to the fact that the computer works on numbers. Other kinds of
computersdoexistbutarenotascommon;analogcomputersoperateinanumberofother
ways, but are usually electrical—they manipulate electrical voltages and currents—or
mechanical—theyusegearsandshaftstocalculateamechanicalresponse.
Thefactthatanyproblemmustbeexpressedinnumericalformhaspresentedaproblem
to some potential programmers. I’m not good at math is a common complaint, and the
beliefthatcomputerprogrammingrequiresaknowledgeof
advancedmathematicsisusedasareasontonotstudyprogramming.Infact,thekindof
mathcommonlyneededwouldmoreproperlybecalledarithmetic,notmath.
Inorderforaproblemtobesolvedusingacomputer,theproblemmustbeexpressedin
a way that manipulates numbers, and the data involved must be numeric. This is often
accomplishedbysomekindofencodingofthedata.Itissocommonthattheprocessis
invisibleonmoderncomputers.Mostdatahaveavarietyofencodingsthathavebeenused
for years and are taken for granted: images in JPEG format or sounds in MP3 are
examplesofcommonlyusedencodingofdataintonumbers.
What can computers do with numbers? Addition, subtraction, multiplication, and
divisionarethebasicoperations,butcomputerscancomparethevalueofnumberstoo.
1.1 SOLVINGAPROBLEMUSINGACOMPUTER
Theprocessbeginswithaproblemtobesolved,andthefirststepistostatetheproblem
asclearlyaspossible.Thisfirststepiscriticallyimportantbecauseunlesstheproblemis
completely understood, its solution on a computer is impossible. Then the problem is
analyzedtodeterminemethodsbywhichitmaybesolved.Ascomputerscanonlydirectly
manipulatenumbers,itiscommonforsolutionsdiscussedatthisstagetobenumericalor
mathematicalandforthemtoinvolvedecidinguponrepresentationsforthedatathatwill
facilitatesolvingtheproblem.Thenasketchofthesolution,perhapsonpaperinahuman
languageandmath,iscreated.Thisistranslatedintocomputerlanguageandthentyped
intocomputerformusingakeyboard.Theresultingtextfileiscalledascript,sourcecode,
or more commonly the computer program. A program called a compiler takes this
programandconvertsitintoaformthatcanbeexecutedonthecomputer.Basically,all
programsareconvertedinto asetof numberscalledmachine code,whichthe computer
canexecute.
WearegoingtolearnalanguagecalledPython.Itwasdevelopedasageneralpurpose
programming language and is a good language for teaching because it makes a lot of
thingseasy.QuiteafewapplicationsarebuiltusingPython;forexample:thegamesEve
OnlineandCivilizationIV,BitTorrent,andDropboxtonameonlyafew.Itisabitlikea
lot of other languages in use these days in terms of structure (syntax) but has some
simplifyingideasthatwillbediscussedinlaterchapters.
Inordertouseaprogramminglanguage,therearesomebasicconceptsandstructures
thatneedtobeunderstoodatabasiclevel.Someoftheseconceptswillbeintroducedin
thischapter,andtherestofthebookwillteachyoutoprogrambyexample;inallcases,
codingexampleswillbeintroducedbystatingaproblemtobesolved.Theproblemstobe
solvedinthischapterinclude:asimpleguess-a-numbergameandthegameofrock-paper-
scissors.TheseproblemswillbethemotivationforlearningmoreabouteitherthePython
language itself or about methods of solving problems. Any computer programs in this
bookwillexecuteonacomputerrunninganymajoroperatingsystemoncethefreePython
languagedownloadhasbeeninstalled.
1.2 EXECUTINGPYTHON
InstallingPythonisnottoodifficult,andinvolvesdownloadingtheinstaller,runningit,
andperhapsconfiguringafewspecificdetails.Thisprocesscanbefoundonthenet.Once
installedthereareafewvariationsthatcanbeusedwithit,thesimplestprobablybeingthe
PythonGraphicalUserInterfaceorGUI.IfrunningPythononaWindowsPC,lookatthe
Start menu for Python and click; a link named “IDLE (Python GUI)” will be seen, as
showninFigure1.1.Clickonthisandtheuserinterfacewillopen.Clickthemouseinthe
GUIwindowsothatyoucanstarttypingcharactersthere.
PythoncanberuninteractivelyintheGUIwindow.Thecharacters“>>>”arecalleda
prompt, and indicate that Python is waiting for something to be typed at the keyboard.
AnythingtypedherewillbepresumedtobeaPythonprogram,oratleastpartofone.Asa
demonstration, type “1” followed by “Enter.” Python responds by printing “1.” Why?
When“1”wastypeditwasaPythonexpression,somethingtobeevaluated.Thevalueof
“1”issimply“1,”sothatwastheanswerPythoncomputed.
Nowtype“1+1.”Pythonrespondswith“2.”Pythoninputswhattheuser/programmer
types,evaluatesitasamathematical(inPythonform)expression,andprintstheanswer.
Thisisnotreallyprogrammingyet,becauseabasictwo-dollarcalculatorcandothis,butit
iscertainlyastart.
IDLEisgoodformanythings,buteventuallyamoresophisticatedenvironmentwillbe
needed,onethatcanindentautomatically,detectsomekindsoferrors,andallowprograms
toberunanddebuggedandsavedasprojects.Thiskindofsystemiscalledanintegrated
development environment, or IDE. There are many of these available for Python, some
costing quite a lot and some freely downloadable. The code in this book has been
compiledandtestedusingonecalledPyCharm,butmostIDEs outtherewouldbe fine,
anditislargelyamatterofpersonalpreference.BasicPyCharmisfree,andithasabigger
brotherthatcostsasmallamount.
AnadvantageofanIDEisthatitiseasytotypeinawholeprogram,runit,findthe
errors, fix them, and run it again. This process is repeated until the program works as
desired. Multiple parts of a large program can be saved as separate files and collected
togetherbytheIDE,andtheycanbeworkedonindividuallyandtestedtogether.Anda
good IDE uses color to indicate syntax features that Python understands and can show
somekindsoferrorwhilethecodeisbeingentered.
Tobeginprogrammingitmustbeunderstoodthatalanguagehasasyntaxorstructure,
andthatforcomputerlanguagesthisstructurecannotbevaried.Thecomputerwillalways
bethearbiterofwhatiscorrect,andifanyprogramhasasyntaxerrorinitorproduces
erroneousresults,thenitistheprogramandnotthecomputerthatisatfault.
Next, one should appreciate that the syntax is arbitrary. It was designed by a human
withattitudesand biasesand newideas, andwhile thesyntax mightsometimes beugly
andhardtorecall,itiswhatitis.Partsofitmightnotbeunderstoodatfirst,butaftera
whileandafterreadingandexecutingthefirstprogramsinthisbook,mostofitwillmake
sense.
A program, just like any sentence or paragraph in English, consists of symbols, and
ordermatters.Somesymbolsarespecialcharacterswithadefinedmeaning.Forexample,
“+”usuallymeansadd,and“-”usuallymeanssubtract.Somesymbolsarewords.Words
definedbythelanguage,likeif,while,andtrue,cannotalsobedefinedbyaprogrammer
—they mean what the language says they mean, and are called reserved words. Some
names have a definition given by the system but can be reused by a programmer as
needed.Thesearecalledpredefinednamesorsystemvariables.However,somewordscan
bedefinedbytheprogrammer,andarethenamesforthingstheprogrammerwantstouse
intheprogram:variablesandfunctionsareexamples.
1.3 GUESSANUMBER
Games that involve guessing are common, and are sometimes used to resolve minor
conflictssuchaswhogetsthenextpieceofcakeorwhogetsthefirstkickatafootball.
It’s also sometimes a way to occupy time, and can simply be fun. How can we write a
programtohavetheuserguessanumberthattheprogramhaschosen?
There are many variations on this simple game. In one the number is to be guessed
precisely.Oneperson(thechooser)hasselectedanumber,aninteger,inaspecifiedrange.
“Pickanumberbetweenoneandten”wouldbeatypicalproblem.Theotherperson,the
guesser,must choose anumberinthatrange.Iftheyselectthecorrectnumber,thenthe
guesserwins.Thisisaboringgameandisbiasedinfavorofthechooser.
Amoreinterestingvariationwouldbetostartwithoneguessandhavethechooserthen
saywhetherthetargetnumberisgreaterthanorlessthantheguessednumber.Theguesser
thenguessesagain,andtheprocesscontinuesuntilthenumberisguessedcorrectly.The
rolesofguesserandchoosercannowswitchandthegamestartsagain.Thebestguesseris
theonewhousesthefewestguesses.
Athirdalternativeisto havemultipleguessers.Allguessersmaketheirselectionand
theonewhohaschosenanumbernearestthecorrectnumberisthewinner.Thisisthebest
game for solving disputes, because it involves one guess from each person. Ties are
possible,inwhichcasethegamecanbeplayedagain.
1.4 ROCK-PAPER-SCISSORS
Althoughthisgameisusedbychildrentosettledisputes and makerandomdecisions
suchas “who goes first,” ithas beentaken moreseriously byadults. There areactually
competitions where money is at stake. A televised contest in Las Vegas had a prize of
$50,000.Thisgameisnotastrivialasitoncewas.
Inthisgameeachoftwoplayersselectsoneitemfromthelist[rock,paper,scissors]in
secret,andthenbothdisplaytheirchoicesimultaneously.Ifbothplayersselectedthesame
item,thentheytryagain.Otherwise,rockbeatsscissors,scissorsbeatspaper,andpaper
beatsrock.Thiscontestcanberepeatedfora“bestoutofN”competition.
Bothofthesegamesformthefirstproblemset,andserveas
themotivationforlearningtheelementsofthePythonlanguage.
1.5 SOLVINGTHEGUESSANUMBERPROBLEM
The simple version of the guessing program has two versions, depending on who is
guessing.Thecomputershouldpickthenumberandthehumanusershouldguess,because
theotherwayaroundcanusesomecomplexprogramming.Inthatcasehere’swhathasto
happen:
1.Thecomputerselectsanumber.
2.Thecomputeraskstheplayertoguess.
3.Theplayertypesanumberonthekeyboardandthecomputerreadsitin.
4.Thecomputercomparestheinputnumberagainsttheonethatitselected,andifthe
twoagree,thentheplayerwins.Otherwisethecomputerwins.
ThePythonfeaturesneededtodothisinclude:printingamessage,readinginanumber,
havingaplacetostoreanumber(avariable),havingawaytoselectanumber,andhaving
awaytocomparethetwonumbersandactdifferentlydependingontheresult.
Thesecondversionrequirestheabove,plusawaytorepeattheprocessincaseswhen
theguessiswronganduntilitiscorrect.Inthiscasethemethodbecomes:
1.Thecomputerselectsanumber.
2.Thecomputeraskstheplayertoguess.
3.Theplayertypesanumberonthekeyboardandthecomputerreadsitin.
4.Thecomputercomparestheinputnumberagainsttheonethatitselected,andifthe
twoagree,thentheplayerhasguessedcorrectly.ExittoStep7.
5.Thecomputerdetermineswhethertheguessishigherorlowerthantheactual
numberandprintsanappropriatemessage.
6.RepeatfromStep2.
7.Gameover.
Therepetitionmechanismistheonlynewaspecttothissolution,butitisanessential
componentofPythonandeveryotherprogramminglanguage.
1.6 SOLVINGTHEROCK-PAPER-SCISSORS
PROBLEM
The solution to this problem has no new requirements, but re-enforces the language
featuresoftheprevioussolutions.Onesolutiontothisproblemis:
1.Selectarandomchoiceformthethreeitemsrock,paper,orscissors.Savethis
choiceinavariablenamedchoice
2.Asktheplayerfortheirchoice.Useanintegervalue,where1=rock,2=paper,and
3=scissors
3.Readtheplayersselectionintoavariablenamedplayer
4.Ifplayerisequaltochoice
5.Printthemessage“Tie.We’lltryagain.”
6.RepeatfromStep1
7.Ifplayerisequaltorock
8.Ifchoiceisequaltoscissors,gotoStep17
9.ElsegotoStep18
10.Ifplayerisequaltopaper
11.Ifchoiceisequaltoscissors,gotoStep17
12.ElsegotoStep18
13.Ifplayerisequaltoscissors
14.Ifchoiceisequaltorock,gotoStep17
15.ElsegotoStep18
16.Printerrormessageandterminate
17.Print“Computerwins”andterminate
18.Print“Youwin”andterminate
Foreachplayerselection,oneofthealternateitemswillbeatitandonewilllosetoit.
Eachchoiceischeckedandthewin/losedecisionismadebasedontheknownoutcomes.
The solutions to both problems require similar language elements: a way to store a
value(avariable),awaytoexecutespecificpartsoftheprogramdependingonthevalue
ofavariableorexpression(anifstatement),awaytoreadavaluefromthekeyboard,a
waytoprintamessageonthescreen,andawaytoexecutecoderepeatedly(aloop).
1.6.1 VariablesandValues–ExperimentingwiththeGraphicalUser
Interface
Avariableisanamethattheprogrammercandefinetorepresentsomevalue,anumber
oratextstringgenerally.Itrepresentstheplacewherethecomputerstoresthatvalue;itis
a symbol in text form, something humans like, representing a value. Everything that a
computerdoesisultimatelydonewithnumbers,sothelocationofanythingisanumber
thatrepresentstheplaceincomputermemorywherethatthingisstored.It’slikeofficesin
a building. Each office has a number (its address) and usually has a name too (the
occupantorbusinessfoundthere).Additionally,theofficehascontents,andthosecontents
areoftendescribedbythenamegiven.InFigure1.2acollectionofofficesinaspecific
buildingcanbeseen.Inthismetaphortheofficenumbercorrespondstotheaddress,and
thename(variablename),beingmorehumanfriendly,ishowitisoftenreferredtobya
person(programmer).Inallcases,though,itisthecontentsoftheoffice(location)thatare
important.Thenumberandnamearewaystoaccessit.So,someonemightsayBringme
thePythonmanualfromtheServerRoom”or“BringmethePythonmanualfrom607”and
bothwouldbethesamething.Thecontentsoflocation607wouldbethePythonmanual.
Nowsomeonecouldsay“PutthisPythonmanualintheDigitalMediaLab,”whichwould
changethecontentsoflocation611.InactualPythontheactofretrievingavaluefroma
locationdoesnotchangethecontentsofthatlocation,butinsteadmakesacopy,butthe
basicmetaphorissound.
Notallstringsorcharacterscanbevariablenames.Avariablecannotbeginwithadigit,
for example, or with most non-alphabetic characters like “&” or “!,” although in some
casesbeginningwith“_”isacceptable.Avariablenamecancontainupper-orlowercase
letters,digits,and“_”.Uppercaseandlowercasearedistinct,sothevariablesHelloand
helloaredifferent.
Soavariablecanchangevaluesbut,unlikearealoffice,asimplevariablecanholdonly
onevalueatatime.Thenamechosendoesnothavetobesignificant.Programsoftenhave
variablesnamediorx.However,itisagoodideatoselectnamesthatrepresentthekind
of value that the variable it to contain so as to communicate that meaning to another
person,aprogrammerprobably.Forexample,thevalue3.1415926shouldbestoredina
variablenamedpi,becausethat’sthenameeveryoneelsegivestothisvalue.
IntheGUItypepi=3.1415926.Pythonrespondswithaprompt,whichindicatesthatit
is content with this statement, and that it has no value to print. If you now type pi,the
responsewillbe3.1415926;thevariablenamedpithatwasjustcreatednowhasavalue.
InthesyntaxofPython,thenamepiisavariable,thenumber3.1415926isaconstant,
but is also an expression, and the symbol = means assign to. In the precise domain of
computer language, pi = 3.1415926 is an assignment statement and gives the variable
namedpithespecifiedvalue.
Continuingwiththisexample,defineanewvariablenamedradiustobe10.0usingan
assignmentstatementradius=10.0.Ifyoutyperadiusand“enter,”Pythonrespondswith
10.0.Finally,weknowthatthecircumferenceofacircleis2prinmathterms,or2times
pi times the radius in English. Type 2*pi*radius into the Python GUI, and it responds
with62.831852, which is the correct answer. Now type circumference = 2*pi*radius,
andPythonassignsthevalueofthecomputationtothevariablecircumference.
Python defines a variable when it is given a value for the first time. The type of the
variableisdefinedatthatmomenttoo;thatis,ifanumberisassignedtoaname,thenthat
nameisexpectedtorepresentanumberfromthenon.Ifastringisassignedtoaname,
thenthatnamewillbeexpectedtobeastringfromthenon.Tryingtouseavariablebefore
ithasbeengivenavalueandatypeisanerror.Attemptingthecalculation:
area=side*side
is not allowed unless there is a variable named side already defined at this point. The
followingisOKbecauseitdefinessidefirst,andtheninturnisusedto
definearea:
side=12.0
area=side*side
Thetwolinesabovearecalledstatementsinaprogramminglanguage,andinPythona
statementusuallyendsattheendoftheline(the“enter”keywaspressed).Thisisabit
unusualinacomputerlanguage,andpeoplewhoalreadyknowJava orC++havesome
difficultywiththisideaatfirst.Inothercomputerlanguagesstatementsareseparatedby
semicolons,notbytheendoftheline.Infact,inmostlanguagestheindentingoflinesin
theprogramdoesnothaveanymeaningexcepttotheprogrammer.InPythonthat’snotthe
caseeither,aswillbeseenshortly.
Theexpressionsweuseinassignmentscanbepretty complicated,but arereallyonly
thingsthatwelearnedinhighschool.Add,subtract,multiply,anddivide.Multiplication
anddivisionareperformedbeforeadditionandsubtraction,whichiscalledaprecedence
rule,so3*2+1is7,not9;otherwise,evaluationisdonelefttoright,so6/3*2is4(dothe
divisionfirst)asopposedto1(ifthemultiplicationwasdonefirst).Thesearerulesthat
shouldbefamiliarbecauseitishowpeoplearetaughttodoarithmetic.Thesymbol**
meansexponentortothepowerof,so2**3is23whichis8,andthisoperatorhasahigher
precedence (i.e., is done before) than the others. Parentheses can be used to specify the
order of things. So, for example, (2+3)**2 is 25, because the expression within the
parenthesisisdonefirst,thentheexponent.
1.6.2 ExchangingInformationwiththeComputer
When using most programming languages, it is necessary to design communication
with the computer program. This goes two ways: the program will inform the user of
things,suchasthecircumferenceofacirclegivenaspecificradius,andtheusermaywant
totelltheprogramcertainthings,likethevalueoftheradiuswithwhichtocomputethe
circumference. We communicate with a program using text, which is to say characters
typedintoakeyboard.Whenacomputerispresentingresults,thattextisoftenintheform
ofhuman language, messages as sentences.“The circumference is62.831852” could be
suchamessage.Thesentenceisactuallycomposedbyaprogrammerandhasanumberor
collectionofnumbersembeddedwithinit.
Python allows a programmer to send a message to the screen, and hence to the user,
using a print directive. This is the word print followed by a characterstring, which is
oftenasetofcharactersinquotes.Anexample:
print(“Theanswerisyes.”)
Theparenthesesareusedtoencloseeverythingthatistobeprinted;suchastatement
canprintmanystringsiftheyareseparatedbycommas.Numberswillbeconvertedinto
stringsforprinting.Sothefollowingiscorrect:
print(“Thecircumferenceis“,62.831852)
Ifavariableappearsinthelistfollowingprint,thenthevalueofthatvariablewillbe
printed,notthenameofthevariable.So:
print(“Thecircumferenceis“,circumference)
isalsocorrect.
1.6.3 Example1:DrawaCircleUsingCharacters
Assumingthatitisdesiredtoprintacirclehavingaconstantpredefinedradius,thiscan
bedonewithafewprintstatements.Theplanningofthegraphicitself(thecircle)canbe
doneusinggraphpaper.Assumingthateachcharacterusesthesameamountofspace,a
circlecanbe approximatedusingsome skillfullyplaced“*”characters. Thenprinteach
rowofcharactersusingaprintstatement.Asamplesolutionis:
print(”***“)
print(”*********“)
print(”*************“)
print(”***************“)
print(”***************“)
print(”***************“)
print(”*************“)
print(”*********“)
print(”***“)
1.6.4 Strings,Integers,andRealNumbers
Computerprogramsdealmainlywithnumbers.Integers,orwholenumbers,andrealsor
floating point numbers, which represent fractions, are represented differently, and
arithmetic works differently on the two types of numbers. A Python variable can hold
eithertype,butifavariablecontainsanintegerthenitistreatedasaninteger,andifit’s
holdingafloatingpointnumberthenitistreatedasoneofthose.What’sthedifference?
First,there’sadifferenceinhowtheyareprintedout.Ifwemaketheassignmentvar=1
andthenprintthevalueofvar,itprintssimplyas1.Ifwemaketheassignmentvar=1.0
andthenprintvar,itprintsas1.0.Inbothcasesvarisarealorfloatingpointnumberand
willbetreatedassuch.Numericconstantswillbethoughtofasrealnumbers.However,a
variablecanbefirstonethingandthenanother.Itwillbethelastthingitwasassigned.
Arithmeticdiffersbetweenintegersandreals,buttheonlytimethatdifferenceisreally
apparentiswhendoingdivision.Integersarealwayswhole,non-fractionalnumbers.Ifwe
divide3by2,both3and2areintegersandsothedivisionmustresultinaninteger:the
resultis1.Thisisbecausethereisexactlyasingle2in3,orifyoulike,2goesinto3just
once,witharemainderof1.Thereisaspecificoperatorfordoingintegerdivision://.”
So,3//2 isequalto1. Theremainderpartcan’tbe handledandis discarded,butcanbe
foundseparatelyusingthe“%”operator.Forexample,8//5is1,and8%5istheremainder,
3.Thisexplanationisanapproximationtothetruth,andonethatcanbecleareduplater,
butitworksperfectlywellforpositivenumbers.
Ofcoursefractionsworkfineforrealnumbers,andwillbeprintedasdecimalfractions:
8.0/5.0 is 1.6, for example. What happens if we mix reals and integers? In those cases
things get converted into real, but now things get more complicated, because order can
mattera greatdeal.Theexpression7//2*2.0doesthedivision7//2first,whichis3, and
thenmultipliesthatby2.0,yieldingtheresult6.0;theresultof8/3*3.0wouldbe5.333.
Mixing integers and reals is not a good idea, but if done, the expressions should use
parenthesestospecifyhowtheexpressionshouldbeevaluated.
Arealcanbeusedinplaceofanintegerinmostplaces,buttheresultwillbereal.Thus,
2.0* 3 =6.0, not 6,and 6.0//2is 3.0, not3. There aresome exceptions. To convert an
integertoareal,thereisaspecialoperationnamedfloat:float(3)yields3.0.Ofcourseit’s
possibletosimplymultiplyby1.0andtheresultwillbefloattoo.Convertingfloatvalues
tointegersismorecomplicated,becauseofthefractionissue:whathappenstothedigits
totherightofthedecimal?Theoperationintwilltakeafloatingpointvalueandthrow
away the fraction. The value of int(3.5) will be 3, as a result. It is normal in human
calculations to round to the nearest integer, and the operation round(3.5) does that,
resultingin4.
1.6.5 NumberBases
In elementary school, perhaps grade 3 or 4, the idea of positional number systems is
taught. The number 216 is a way to write the value of 6 + 1*10 + 2*100. Not all
civilizations use such a scheme; Roman numerals are not positional,for example. Still,
most people are comfortable with the idea. What people are not as comfortable with is
changingthenumberbaseawayfrom10.InChapter0,thebinarysystem,orbase2,was
discussed,butanybasethatisapowerof2isofsomeinterest,especiallybase8andbase
16.
Humansuseabase10schemeprobablybecausewehave10fingers.Whatitmeansis
thatwehaveasymbolforeachofthe10digits,0through9,andeachdigitpositiontothe
leftofthefirstdigitismultipliedbythenextpowerof10.Thenumber216isreally2*102
+1*101+6*100.Thebaseis10,andeachdigitrepresentsapowerofthebasemultiplied
by a digit. What if the base is 8? In that case 216 is really 2*82 + 1*81 + 6. If the
arithmeticiscarriedout,thisnumberturnsouttobe128+8+6=142.
If multiple number bases are used, it is common to give the base as a subscript. The
number216inbase8iswrittenas2168.Thedefaultwouldbebase10.Inbase8thereare
only8digits,0through7.Thedigits8and9cannotappear.Inbaseslargerthan10more
symbolsareneeded.Acommonbasetobeusedoncomputersis16,orhexadecimal(hex
forshort).Inahexnumber16digitsareneeded,sotheregularonesareusedandthen“A”
represents10,“B”is11,“C”is12,“D”is13,“E”is14,and“F”is15.Thehexnumber
1216is1*16+2,or1810.Thenumber1A16is1*16+10=2610.
In Python numbers are given in decimal (base 10) by default. However, if a number
constantbegins with“0o” (zero followedby the letter“o”) Pythonassumes it isbase 8
(octal).Thenumber0o21,forexample,is218=1710.Anumberthatbeginswith“0x”is
hexadecimal.0x21is2116=3310.Thisappliesonlytointegers.
There is a number base that is the most important, because it lies under all of the
numbersonacomputer.Thatwouldbebase2.Allnumbersonamoderndigitalcomputer
arerepresentedinbase2,orbinary,intheirinternalrepresentation.Abinarynumberhas
onlytwodigits,0and1,andeachrepresentsapowerof2.Thus,11012is1*23+1*22+
0*21+1=8+4+1=1310.InPythonabinarynumberbeginswith“0b,”sothenumber
0b10101represents2110.
These number bases are important for many reasons, but base 2 is fundamental, and
bases8and16areimportantbecausetheyarepowersof2andsoconvertveryeasilyto
binarybuthavefewerdigits.Oneexampleoftheuseofhexisforcolors.InPythonthey
can represent a color, and on web pages they are certainly used that way. The number
0xFF0000isthecolorred,forexample,ifusedonawebpage.Butmoreofthatlater.
1.6.6 Example2:ComputetheCircumferenceofanyCircle
When humans send information into a computer program, the text tends to be in the
formofnumbers.ThePythoncodethatwaswrittentocalculatetheradiusofacircleonly
didthecalculationforasingleradius:10.That’snotasusefulasaprogramthatcomputes
thecircumferenceofanycircle,andthatwouldmeanallowingtheusertotelltheprogram
what radius to use. This should be easy to do, because it is something that is needed
frequently. Frequently needed things should always be easy. In the case of sending a
number into a program in Python, the word input can be used within a program. For
example:
radius=input()
willacceptanumberfromthekeyboard,typedbytheuser,andwillreturnitasastringof
characters.Thismakessensebecausetheusertypeditasastringofcharacters,butitcan’t
beusedinacalculationinthisform.Toconvertitintotheinternalformofanumber,we
mustspecificallyaskforthistobedone:
radius=input()
radius=float(radius)
willreadastringintoradius,thenconvertitintoafloatingpoint(real)numberandassign
ittothevariableradiusagain.Thiscanbedoneallinonestatement:
radius=float(input())
Now the variable radius can be used to calculate a circumference. This is a whole
computerprogramthatdoesausefulthing.Ifthevalueofradiuswastobeaninteger,the
codewouldread:
radius=int(input())
If the conversion to a number is not done, then Python will
giveanerrormessagewhenthecalculationisperformed,like:
Traceback(mostrecentcalllast):
File“<pyshell#13>”,line1,in<module>
circumference=2*pi*radius
TypeError:can'tmultiplysequencebynon-intof
type'float'
Thisisprettyuninformativetoabeginningprogrammer.WhatisaTraceback?What’s
pyshell?Therearecluesastowhatthismeans,though.Thelineofcodeatwhichtheerror
occursisgivenandthetermTypeErrorisdescriptive.Thiserrormeansthatsomethingthat
can’tbemultiplied(astring)wasusedinanexpressioninvolvingamultiplication.That
thing is the variable radius in this instance because it was a text string and was not
convertedtoanumber.
Alsonotethatint(input())canpresentproblemswhentheinputstringisnotinfactan
integer. If it is a floating point number, this results in an error. The expression
int(“3.14159”) could be interpreted as an attempt convert pi into an integer, and would
havethevalue3;infact,itisanerror.Thefunctionintwaspassedastringandthestring
containedafloat,notanint.ThisissomethingofaquirkofPython.Itisbettertoconvert
inputnumbersintofloats.
1.6.7 GuessaNumberAgain
The simple version of the guessing program can now nearly be written in Python.
Examiningthemethodofsolution,here’swhatcanbecodedsofar;versionsdependon
whoisguessing.Thecomputershouldpickthenumberandthehumanusershouldguess,
becausetheotherwayaroundcaninvolvesomecomplexprogramming.Inthatcasehere’s
whathastohappen:
1.Thecomputerselectsanumber.
choice=7
2.Thecomputeraskstheplayertoguess.
print(“Pleaseguessanumberbetween1and10:“)
3.Theplayertypesanumberonthekeyboardandthecomputerreadsitin.
playerchoice=input()
4.Thecomputercomparestheinputnumberagainsttheonethatitselected,
andifthetwoagree,thentheplayerwins.Otherwisethecomputerwins.
Itisthe finalstepthat isstillnot possiblewithwhat isknown.It isnecessary in this
program,asit isin mostcomputer programs,to makeadecision andto executecertain
code(i.e.,dospecificthings)conditionallybasedontheoutcomeofthatdecision.People
dothatsortofthingallofthetimeinreallife.Examplesinclude:
“Ifthelightisredthenstop,otherwisecontinuethroughtheintersection.”
“Ifalltellersarebusywhenyouarriveatthebank,thenstandinlineandwaitfor
thenextonetobecomeavailable.”
“Ifyouneedbreadormilk,thenstopatthegrocerystoreonthewayhome.”
“Ifitrains,thepicnicwillbecancelled.”
Notice that all of these examples use the word “if.” This word indicates a standard
conditionalsentenceinEnglish.Theconditioninthefirstcaseisthephrase“ifthelightis
red” (called in English the protaxis or antecedent) and the consequence to that is the
phrase“thenstop”(theapodosisorconsequent).Terminologyaside,theintentisclearto
an English speaker: on the condition that or in the event that the light is red, then the
necessary action is that the driver is to stop their car. The action is conditional on the
antecedent, which in Python will be called an expression or, more precisely, a logical
expression,whichhasthevalueTrueorFalse.
ThestructureorsyntaxofthissortofthinginPythonwouldbe:
ifthelightisred:
stop
ormoreexactly:
iflight==red:
#executewhatevercodemakesthecarstop
Thisiscalledanifstatement,andismoreprofoundwithamorecomplexsyntaxthan
canbeinferredfromthisexample.
1.7 IFSTATEMENTS
In Python an if statement begins with the word if, followed by an expression that
evaluatestoTrueorFalse,followedby acolon (:), then a series of statements that are
executed if the expression is true. The names True and False are constants having the
obvious meaning, and a variable that can take on these values is a logical or Boolean
(namedafterthemanwhoinventedtwostateorlogicalalgebra)variable.Theexpression
istheonlytrickypart.ItcanbeaconstantlikeTrue,oravariablethathasaTrueorFalse
value,orarelationalexpression(onethatcomparestwothings)oralogicalcombination
ofanyofthese—anythingthathasaresultthatistrueorfalse.
ifTrue: #Constant
ifflag: #Logicalvariable
ifa<b: #relationalexpression
ifa<bandc>d: #logicalcombination
Alogicalexpressioncanbeanyarithmeticexpressionsbeingcomparedusinganyofthe
followingoperators:
<Lessthan
>Greaterthan
<=Lessthanorequalto
>=Greaterthanorequalto
==Equalto
!=Notequalto
Logicalcombinationscanbe:
andEG:a==bandb==c
orEG:a==bora==c
notEG:not(a==b)#sameas!=
Thesyntaxissimpleandyetallowsahugenumberofcombinations.Forexample:
ifp==qandnotp==zandnotz==p:
ifpi**2<12:
if(a**b)**(c-d)/3<=z**3:
Theconsequent,ortheactionstobetakenifthelogicalexpressionistrue,followsthe
colon on the following lines. The next statement is indented more than the if, and all
statements that follow immediately that have the same indentation are a part of the
consequentandareexecutedifthecondition istrue, otherwisenone ofthemare. Asan
example,consider:
ifa<b:
a=a+1
b=b–1
c=a–b
Inthiscasethetwostatementsfollowingthe“:”areindentedby4morespacesthanis
theif.ThistellsPythonthattheyarebothapartoftheifstatement,andthatifthevalueof
aissmallerthanthevalueofb,then bothof thosestatements willbe executed.Python
callssuchagroupofstatementsasuite.Theassignmenttothevariablecisindentedtothe
samelevelastheif,soitwillbeexecutedinanycaseandisnotconditional.
The use of indentation to connect statements into groups is unusual in programming
languages. Most languages in use pretty much ignore spaces and line breaks altogether,
anduseastatementseparatorsuchasasemicolontodemarkstatements.So,intheJava
languagetheabovecodewouldlooklikethis:
if(a<b){
a=a+1;
b=b–1;
}
c=a–b;
Thebraces{…}enclosethesuite,whichwouldprobablybecalledablockinJavaor
C++. Notice that this code is also indented, but in Java this means nothing to the
computer.Indentationisusedforclarity,sothatsomeonereadingthecodelatercansee
moreclearlywhatishappening.
SemicolonsareusedinPythontoo,butmuchmorerarely.Ifitisdesiredtoplacemore
thanone statement on a singleline, then semicolons can be used to separate them. The
Pythonifstatementunderconsiderationherecouldbewrittenas:
ifa<b:
a=a+1;
b=b-1
c=a-b
Thisishardertocomprehendquicklyandisthereforelessdesirable.Therearetoomany
symbolsallgroupedtogether.Aprogramthatiseasytoreadisalsoeasiertomodifyand
maintain.Codeiswrittenforcomputerstoexecute,butitisalsoforhumanstoread.
There are some special assignment operators that can be used for incrementing and
decrementingvariables.Intheabovecodethestatementa=a+1couldbewrittenasa+=
1,andb=b–1canbewrittenasb-= 1.Thereisnorealadvantagetodoingthis,but
other languages permit it so Python adopted it too. There is another syntax that can be
used to simplify certain code in languages like Java and C, and that is the increment
operator“++”andthedecrementoperator“—.”Pythondoesnothavethese.However,an
effectofthewaythatPythondealswithvariablesandexpressionsisthat“++x”islegal;so
is“++++x.”Thevalueissimplyx.Theexpression“x++”isnotcorrect.
1.7.1 Else
An if statement is a two-way or binary decision. If the expression is true, then the
indicatedstatementsareexecuted.Ifitisnottrue,thenitispossibletoexecuteadistinct
setofstatements.Thisisneededforthepickanumberprogram.Inonecasethecomputer
wins,andintheotherthehumanwins.Anelseclauseiswhatwillallowthis.
Theelseisnotreallyastatementonitsown,becauseithastobeprecededbyanif,so
it’spartoftheifstatement.Itmarksthepartofthestatementthatisexecutedonlywhen
theconditionintheifstatementisfalse.Itconsistsofthewordelsefollowedbyacolon,
followedbyasuite(sequenceofindentedstatements).Soatrivialexampleis:
ifTrue:
print(“Theconditionwastrue”)
else:
print(“theconditionwasfalse”)
Theelseasaclauseisnotrequiredtoaccomplishanyspecificprogramminggoals,and
itcanbeimplementedusinganotherif.Thecode:
ifa<b:
print(“a<b”)
else:
print(“a>=b”)
couldalsobewrittenas:
ifa<b:
print(“a<b”)
ifnot(a<b):
print(“a>=b”)
Theelseisexpressive,efficient, and syntacticallyconvenient. It is expressive because it
representsawaythathumansactuallycommunicate.Thewordelsemeansprettymuchthe
samethinginPythonasitdoesinEnglish.Itisefficientbecauseitavoidsevaluatingthe
same expression twice, which costs something in terms of execution speed. And it is
syntactically convenient because it expresses an important element of the language in
fewersymbolsthanwhentwoifsareused.
ThefinalPythoncodeforthesimplesolutionoftheguessanumberprogramcannow
bewritten.Itis:
choice=7
print(“Pleaseguessanumberbetween1and10:“)
playerchoice=int(input())
ifchoice==playerchoice:
print(“Youwin!”)
else:
print(“Sorry,Youlose.”)
1.8 DOCUMENTATION
Therearesomeproblemswiththisprogram,butisdoeswork.Alargeproblemisthatit
alwayschoosesthesamenumbereverytimeitisexecuted(thatnumberbeing7).Thiswill
befixedlateron.Alesscriticalproblemisthatitisundocumented;thatis,thereareno
instructionstoaplayerconcerninghowtousetheprogramandthereisnodescriptionof
howtheprogramworksthatanotherprogrammermightuseifmodifyingthiscode.This
canbefixedbyprovidinginternalandexternaldocumentation.
Externaldocumentationislikeamanualfortheuser.Mostprogramshavesuchathing,
andeventhoughthisprogramisquitesimple,somedegreeof
documentation can be provided. In fact, it is brief enough that it could be printed
whenevertheprogramstartstorun.Forexample:
print(“Pick-a-numberisasimpleguessinggame.The”)
print(“computerwillselectanumberbetween1and10”).
print(“andyouareexpectedtoguesswhatitis.”)
print(“Whentheprogramdisplays'Pleaseguess”)
print(“anumberbetween1and10:'youtypein”)
print(“yourguessfollowedbythe<enter>key.Your“)
print(“guessmustbeanintegerintherange1to10.”)
print(“Thecomputerwilltellyouifyouwinorlose.)
For many more sophisticated programs, such as PowerPoint for example, the
documentationismanypagesandformsasmallbook.Itwouldbedistributedasabooklet
alongwiththesoftwareorprovidedasawebsite.
Internaldocumentationisintendedforprogrammerswhohaveaccesstothesourcecode
oftheprogram.Itcantaketheformofwrittendocumentstoo,butiscommonlyasetof
commentsthatappearsalongwiththecodeitself.High-levellanguageslikePythonallow
theprogrammertoaddhumanlanguagetexttothecodethatwillbecompletelyignoredby
the computer but that can be read by anyone looking at the code. These comments
describetheactionoftheprogram,themeaningofthevariables,detailsofcomputational
methodsused,andmanyotheritemsofinterest.
InPythonacommentbeginswiththecharacter“#”andendsattheendoftheline.
There are no rules for what can appear typed in a comment, but there are some
guidelines developed through years of programming practice. A comment should not
simplyrepeatwhatappearsinthecode;acommentshouldshedsomelightonanaspectof
theprogramthatmightnotbecleartoeveryonelookingatit,anditshouldbewrittenin
plain language. As an example, here is the guess-a-number program with comments
included:
#Thisprogramselectsanumberbetween1and
#10andallowsauser(player)toguesswhat
#itis.
choice=7#Thenumberselectedbythecomputer
#Prompttheuser,indicatingwhatisexpected
print(“Pleaseguessanumberbetween1and10:“)
#Readtheplayer'sinputfromthekeyboard
playerchoice=int(input())#convertfromstring
#Printtheoutcomeofthegame.
ifchoice==playerchoice:#Istheplayer'sguess
print(“Youwin!”)#correct?Playerwins!
else:#Otherwisethecomputerwins
print(“Sorry,Youlose.”)
All programsshould be documented, not after the factbut as they are being written.
Why?Becauserelativelyfewprogramsarewrittenallinonesitting.Thecommentsinthe
codeserve as reminders tothe programmer about what the variables representand why
particular code segments read the way they do. It also indicates the current state of
thinking about the design of the code. When the program is looked at again at the
beginningofanewworking(orschool)day,thecommentscanbeessentialinresuming
thework.
There is also something called a docstring that seems to do the same things as a
comment,butcoversmultiplelinesandisnotreallyacomment.Adocstringbeginsand
endswithatriplequote:
print(“Thiscodewillexecute”)
”””
print(“Thiscodeiswithinadocstring”)
”””
Adocstringisactuallyastring,notacomment,butbehaveslikeacommentandcanbe
usedinthatway.Itcanbeespeciallyusefulfortemporarilycommentingoutsmallsections
ofcodewhiletryingtofindoutwhereerrorsare.Therearealsoprogramsthatwillcollect
thedocstringsintoaseparatedocumentthatcanbeusedasadescriptionoftheprogram.
Forthat reasontheir intended useis to allowthe programmerto explain thepurpose of
certainsectionsofcode.
1.9 ROCK-PAPER-SCISSORSAGAIN
With what is now known about Python, it is time to look at the rock-paper-scissors
problem and see if it can be coded. It takes more steps, but it is really no more
complicatedthantheguess-a-numberprogram.Thecodeisthesame.
1.Selectachoicefromthethreeitemsrock,paper,orscissors.Savethischoiceina
variablenamedchoice.
Arepresentationforthethreeitemswaswhenthesolutionwasfirst
described,whereeachchoicewasaninteger.However,inputreadsstrings,soit
shouldbepossibletoavoidtheconversiontonumbersandusethestringsdirectly.
choice=“paper”#Computerchoosespaper.
2.Asktheplayerfortheirchoice.
Printaspromptmessage.
print(“Rock-paper-scissors:typeinyourchoice:“)
3.Readtheplayersselectionintoavariablenamedplayer.
Useinputaswedidbefore,butthistimereadastringandkeepitthatway.The
playermusttypeoneof“rock,”“paper,”or“scissors,”orelseanerrorwillbe
reported.
player=input()
4.Ifplayerisequaltochoice:
5.Printthemessage“Tie.We’lltryagain.”
Stringscanbecomparedagainsteachotherforequality,sothisstepisquitesimple:
ifplayer==choice:
print(“Gameisatie.Pleasetryagain.”)
6.Ifplayerisequaltorock
7.Ifchoiceisequaltoscissors,gotoStep17
Thewillbeno“gotoStep17,”butthatstepsimplysaysthattheplayerwins.Just
printthatmessagehere.
ifplayer==“rock”:
ifchoice==“scissors”:
print(“Congratulations.Youwin.”)
else:
print(“Sorry-computerwins.”)
8.Ifplayerisequaltopaper
9.Ifchoiceisequaltoscissors,gotoStep17
ifplayer==“paper”:
ifchoice==“scissors”:
print(“Sorry-computerwins.”)
else:
print(“Congratulations.Youwin.”)
10.Ifplayerisequaltoscissors
11.Ifchoiceisequaltorock,gotoStep17
ifplayer==“scissors”:
ifchoice==“rock”:
print(“Sorry-computerwins.”)
else:
print(“Congratulations.Youwin.”)
Thiscodeillustratesanewconcept,ifnotanewlanguagefeature.Ithasifstatements
thatarenestedonewithintheother.Again,it’snotnecessarytodothisbecausenon-nested
statementscanimplementthesamedecision.Forexample:
NestedIFs Non-nestedIFs
ifplayer==“scissors”: ifplayer==“scissorsand
choice==“rock”
ifchoice==“rock”: print(“Computerwins”)
print(“Computerwins.”) ifplayer==“scissors”and
choice!=“rock”
else: print(“Youwin”)
print(“Youwin.”) 
Nested if statements seem more expressive, and communicate the flow of the program
bettertoahumanprogrammerthandoesthenon-nestedcode.
ThereisanotherPythonlanguageelementthatcanbeusedhere.Lookingatthecode,
there is no indication when the user makes an error. For example, if the user enters
“ROCK”(i.e.,uppercase),thenitwillnotmatchanyofthechoices,andtheprogramwill
notindicatethis.Infact,itwon’tprintanythingatall.Whatisreallywantedisasequence
ofif-else-if-elsestatementssuchas:
ifplayer==“scissors”:
ifchoice==“rock”:
else:
ifplayer==“rock”:
ifchoice==paper:
else:
ifplayer==“scissors”:
##andsoon…
Pythonhasaspecialfeaturethatimplementsthisnestingofifandelse:theelif.Theelif
constructcombinesanelseandanif,andthisreducestheamountofindentingthathasto
bedone.Thefollowingcodesnippetsdothesamething:
ifa<b:ifa<b:
print(“a<b”)print(“a<b”)
elifa>b:else:
print(“a>b”)if(a>b):
else:print(“a>b”)
print(“a=b”)else:
else:print(“a=b”)
If too many nested if-else statements exist, then the indenting gets to be too much,
whereas the elif allows the same indent level and has the same meaning. In some
programs this is essential, and in general is easy to read. Using the elif statement the
programfortherock-paper-scissorsproblemlookslikethis:
choice=“paper”#Computerchoosespaper.
print(“Rock-paper-scissors:typeinyourchoice:“)
player=input()
ifplayer==choice:
print(“Gameisatie.Pleasetryagain.”)
ifplayer==“rock”:
ifchoice==“scissors”:
print(“Congratulations.Youwin.”)
else:
print(“Sorry-computerwins.”)
elifplayer==“paper”:
ifchoice==“scissors”:
print(“Sorry-computerwins.”)
else:
print(“Congratulations.Youwin.”)
elifplayer==“scissors”:
ifchoice==“rock”:
print(“Sorry-computerwins.”)
else:
print(“Congratulations.Youwin.”)
else:
print(“Error:Selectoneof:rock,paper,scissors”)
Nowallofthepossibleoutcomesarehandledbythecode.
1.10 TYPESAREDYNAMIC(ADVANCED)
ToprogrammerswhoonlyprogramusingPython,itwouldseemoddthataparticular
variablecouldhaveonly one typeandthatit wouldhavetobe initiallydefinedtohave
that type, but it is true. In Python the type associated with a variable can change. For
example,considerthestatements:
x=10#Xisaninteger
x=x*0.1#Xisfloatingpointnow
x=(x*10==10)#XisBoolean
Somefindthisperfectlylogical,andothersfinditconfusing.Thefactisthatsolongasthe
variableisusedaccordingtoitscurrenttype,allwillbewell.
ItisalsotruethatevenapparentlysimplePythontypescanbequitecomplexintermsof
their implementation. The point is that the programmer rarely needs to know about the
underlying details of types like integers. In many programming languages an integer is
simplyaoneortwo-wordnumber,andthelanguagesbuildoperationslike“+”fromthe
instructionsetofthecomputer.If,forexample,aone-wordintegerAisaddedtoanother
oneB,itcanbedoneusingasinglecomputerinstructionlikeADDA,B.Thisisveryfast
atexecutiontime.
Python was designed to be convenient for the programmer, not fast. An integer is
actuallyacomplexobjectthathasattributesandoperations.Thiswillbecomecleareras
morePython examples arewritten andunderstood, butas asimple casethink aboutthe
way that C++ represents an integer. It is a 32-bit (4 byte) memory location, which is a
fixedsizespaceinmemory.Thelargestnumberthatcanbestoredthereis232-1.Isthat
trueinPython?
Here’s a program that will answer that question, although it uses more advanced
features:
foriinrange(0,65):
print(i,2**i)
Evenanespeciallylongintegerwouldbelessthan65bits.Thefactisthatthisprogram
runssuccessfully,andevenratherquickly.IntegersinPythonhaveanarbitrarilylargesize.
So calculating 264 * 264 is possible and results in
340282366920938463463374607431768211456. This is very handy indeed from a
programmersperspective.
Thetypeofavariablecanbedeterminedbytheprogrammerastheprogramexecutes.
Thefunctiontype()willreturnthetypeofitsparameterasastring,andcanbeprintedor
tested.So,thecode:
z=1
print(type(z))
z=1.0
print(type(z))
willresultin:
<class'int'>
<class'float'>
Ifoneneededtoknowifzwasafloatataparticularmoment,then:
iftype(z)isfloat:
woulddothetrick.Type(z)doesnotreturnastring,itreturnsatype.Theprint()function
recognizesthatandprintsastring,justasitdoesforTrueandFalse.So:
iftype(z)==“<class'float'>”:
wouldbeincorrect.
In future chapters this malleability of types will be further described, and practical
methodsfortakingadvantageofitinPythonwillbeexamined.
1.11 SUMMARY
Acomputerisatoolforrapidlyandaccuratelymanipulatingnumbers.Itcanperform
tediousrepetitivetasksaccuratelyandquickly,butmustbetoldwhattodoandfollowsits
instructions very literally. A computer program is a set of instructions for performing a
task using a computer, and Python is one language that can be used for this purpose.
Pythonallowsaprogrammertodefinevariablesbysimplyusingthem, and associatesa
typewithavariablebasedonwhatitisgiven.Anifstatementallowspartsofaprogramto
be executed when a certain condition becomes true, and it can have an else part that is
executedwhentheconditionisfalse.Ifstatementscanbenested,andsometimestheelif
structureisagoodwaytoexpressasetofnestedconditionalcode.
Inthischapterthemainexamplesweretwoprograms,oneofwhichallowedauserto
guessanumber,whiletheotherwasthewell-knowngameofrock-paper-scissors.
Exercises
Inthefollowingexercisessomeof the expressionsmayresultin anerror.If so,explain
whytheerroroccurs.WhenaskedtowritecodeitshouldbePython3code.
1.Evaluatethefollowingexpressions:
a)3*3/2
b)3*3//2
c)3*3%2
d)(3*3)%2
e)3**3/3
f)(3+2)-(2-4)
g)(3+2)/(2-4)
2.Ifthestatements:
x=3
y=9
z=2.4
havebeenexecutedthenevaluatethefollowingexpressions.Ifanerroroccurs,state
why:
a)x/y
b)x//y
d)x%y
e)y/x*z
f)float(x)/float(z)
g)float(x)//float(z)
h)int(x)//int(z)
3.Giventhevariabledefinitionspresented,evaluatethefollowingexpressionsasbeing
TrueorFalse.
x=12
y=14
a)x>3
b)x>=12
c)x<y
d)x<yandy>14
e)x<yory>14
f)not(x==y)
g)not(x<y)andnot(y>14)
4.Whatwillbeprintedbythefollowingstatements?
a)print(int(“23”))
b)if3**2+4**2==5**2:
print(“345”)
elif3**2<4**2:
print(“34”)
else:
print(“5”)
c)if“toast”<“jam”:
print(“toast”)
else:
print(“jam”)
d)if“12”<“5”:
print(“12”)
else:
print(“5”)
e)a=12.3
b=100
c=0
ifa<b:a=a+1;b=b-1
c=c–b
print(a)
print(c)
f)a=100
b=200
c=300
ab=a<b
cd=(c==a+b)
ifabandcd:
print(“ABandCD”)
elifab:
print(“AB”)
else:
print(“Nope”)
5.TheUnitedStatesmeasurestemperatureinFahrenheitdegrees,whereasCanadauses
Celsius.Acompanyisdevelopinganapptoconvertbetweenthetwoforpeople
wantingtoskiinBanfforWhistler.TheformulatoconvertfromCelsiusdegreesCto
FahrenheitdegreesFis:
F=C*9/5+32
Writeaprogramthatwillbethebasisofthisapp:itwillreadatemperatureinCelsius,
convertittoFahrenheit,andprinttheresult.
6.Thenumericalvaluesofcoinshavebeenarrangedsothatthegreedyalgorithmwill
resultinthesmallestnumberofcoinswhenmakingchange.Thismeansthatthe
largestvaluedcoinistriedfirst,andasmanyofthosecoinsareusedaspossible.Then
thenextsmallerdenominationcoinisused,andsoonuntilthepenniesaredealtout.
Sofor84centsinchange,a50-centpiececouldbeused(leaving34cents),thena25-
centpiece(leaving9cents),a5centpiece(leaving4cents),and4pennies.Ifno50-
centpiecewasavailable,then25-centpieceswouldbeusedinitsplace:3quarters,
followedbyanickelandfourpennies.Writeaprogramthatreadsanumberbetween1
and99thatisanamountofchangetobegivenandprintsthecoinvaluesthatwouldbe
used.
7.Threefloatingpointvariablesa,b,andchavebeenreadinfromtheconsole.Writea
setofifstatementsthatprintstheseindescendingorder.
8.Ifthevalueof1.0/7.0isprinted,therearemanynumberstotherightofthedecimal
place.DeviseawaytoprintonlythreeplacesandwritesomePythoncodetotestthe
idea.
9.Calculateanapproximationtopi.ThereisaninfiniteseriescalledtheGregory-Leibniz
seriesthatsumstopi.Ofcourseitcanneverreachtheexactvaluebecausethereisno
suchthing,butitcancomputeasmanydigitsasaredesired.Theseriesis:
Π=4/1–4/3+4/5–4/7+4/9–4/11….
Writeaprogramthatcalculatestheresultofthefirst15termsofthisseries.Howmany
digitsofpiarecorrect?Addsixmoreterms.Howmanydigitsarecorrectnow?
10.AnotherseriesthatcancalculatepiistheNilakanthaseries.Itisalittlemore
complicatedtocalculate,butgetsclosetopimuchfasterthandoestheGregory-
LeibnizseriesofExercise9.TheNilakanthaseriesis:
Π=3+4/(2*3*4)–4/(4*5*6)+4/(6*7*8)–4/(8*9*10)…
Calculatethefirst15termsofthisseries.Howmanydigitsofpiarecorrect?
NotesandOtherResources
ManyteachingresourcesforPythonexist,bothinprintandontheInternet.
Hereisthedevelopmentenvironmentusedtotestthecodeforthisbook.
PyCharm.https://www.jetbrains.com/pycharm/
1.DavidBeazleyandBrianK.Jones.PythonCookbook,3rdEdition:Recipesfor
MasteringPython3,http://www.onlineprogrammingbooks.com/python-cookbook-
third-edition/
2.CodyJackson.LearningtoProgramUsingPython,
http://www.onlineprogrammingbooks.com/learning-program-using-python/
3.BradMiller.ProblemSolvingwithAlgorithmsandDataStructuresUsingPython,
http://www.onlineprogrammingbooks.com/problem-solving-with-algorithms-and-data-
structures/
4.HarryPercival.Test-DrivenDevelopmentwithPython,
http://www.onlineprogrammingbooks.com/test-driven-development-with-python/
5.LennartRegebro.PortingtoPython3:AnIn-DepthGuide,
http://www.onlineprogrammingbooks.com/porting-to-python-3-an-in-depth-guide/
6.ZedA.Shaw.LearnPythontheHardWay,http://learnpythonthehardway.org/book/
CHAPTER2
REPETITION
2.1TheWHILEStatement
2.2Rock-Paper-ScissorsYetAgain
2.3CountingLoops
2.4PrimeorNon-Prime
2.5LoopsThatareNested
2.6DrawaHistogram
2.7LoopsinGeneral
2.8ExceptionsandErrors
2.9Summary
Inthischapter
Oneofthethingsthatmakescomputersattractivetohumansistheirabilitytodotedious,
repetitivetasksaccurately and at high speedwithout gettingbored. Itis somethingthey
were designed to do. Humans have to do things repeatedly, and not all of them can be
doneforusbycomputers.Brushingourteeth,drivingtowork,cleaningthecarpet—allare
repeatedactions,andmanywouldbecalledchores.Inprogrammingtermssomemightbe
referredtoasloops.
Considerafactoryjobonanassemblyline.AccordingtoHenryFord,oneofthepeople
principallyconnectedwithdevisingtheassemblylineconcept,itismoreefficienttohave
eachworkerdoonejobwellandrepeatitmanytimesadaythantoteachworkershowto
buildentirethings,inhiscaseautomobiles.Eachworkerdoesonerelativelyshortjob,and
then the piece they are working on goes to the next station where the next person does
theirrelativelyshortjob.Onesuchjobcouldbetheinstallationoftheelectronicignition
modulebracket:
1.Acquireabracketandplaceoverattachmentholeswithwideendbelowthe
smallerend.
2.Placeatwo-inchboltintheupperleftboltholeandscrewintotwopoundsof
torque.
3.Placeafour-inchboltintheupperrightboltholeandscrewintotwopoundsof
torque.
4.Placeatwo-inchboltinthelowerleftboltholeandscrewintotwopoundsof
torque.
5.Placeaten-millimeternutovertheboltatthelowerrightandtightentotenpounds.
6.Re-tightentheboltstotenpoundsinthefollowingorder:upperleft,
upperright,lowerleft.
BeforeStep1aboveanewworkpiece(anengine,probably)isplacedinfrontofthe
worker, and after Step 6 the piece is moved to the next station. So from the workers
perspective,solongasorwhilethereisanengineattheirstationthatneedsabracket,they
repeat the steps. In a form that a computer might be able to understand this might be
writtenas:
whilethereisanengineattheirstationthatneedsabracket:
Acquireabracketandplaceoverattachmentholeswithwideendbelowthesmaller
end.
Place a two-inch bolt in the upper left bolt hole and screw in to two pounds of
torque.
Place a four-inch bolt in the upper right bolt hole and screw in to two pounds of
torque.
Place a two-inch bolt in the lower left bolt hole and screw in to two pounds of
torque.
Placeaten-millimeternutovertheboltatthelowerrightandtightentotenpounds.
Re-tighten the bolts to ten pounds in the following order: upper left, upper right,
lowerleft.
Alloftheactionsthatfollowthewhileareindentedtoindicatethattheyareapartof
theactivitiestoberepeated,justaswasdoneinaPythonifstatementtomarkthethings
thatweretobedoneiftheconditionwastrue.Thisexample
illustratesoneofthePythonrepetitionstructuresquiteaccurately:thewhilestatement.
2.1 THEWHILESTATEMENT
Whenusingthisrepetitionstatement,theconditionistestedatthetoporbeginningof
the loop. If upon that initial test the condition is true, then the body of the loop is
executed;otherwiseitisnot,andthestatementfollowingtheloopisexecuted.Thismeans
thatitispossiblethatthecodeintheloopisnotexecutedatall.Theconditiontestedisthe
samekindofexpressionthatisevaluatedinanifstatement:onethatevaluatestoTrueor
False.Itcouldbe,andoftenis,acomparisonbetweentwonumericorstringvalues,asitis
intheexampleofFigure2.1.
Whenthecodeinthebodyofthewhilestatementhasbeenexecuted,thenthecondition
istestedagain.Ifitisstilltrue,thenthebodyoftheloopisexecutedagain,otherwisethe
loopisexitedandthestatementfollowingtheloopisexecuted.Thereisanimplicationin
this description that the body of the loop must change something that is used in the
evaluationoftheloopcondition,otherwisetheconditionwillalwaysbethesameandthe
loopwillneverterminate.So,hereisanexampleofaloopthatisenteredandterminates:
a=0
b=0
whilea<10:
a=a+1
print(a)
Theconditiona<10istrueattheoutsetbecauseahasthevalue0,sothecodeinthe
loopisexecuted.Thelonestatementinthisloopincrementsa,sothatafterthefirsttime
theloopisexecuted,thevalueofais1.Nowtheconditionistestedand,again,a<10so
theloopexecutesagain.Inthefinaliterationoftheloop,thevalueofastartsoutas9,is
incrementedandbecomes10.Whentheconditionistesteditfails,becauseaisnolonger
lessthan10(itisequal)andsotheloopends.Thestatementfollowingtheloopisprint
(a)andthevalueprintedis10.Thisloopexplicitlymodifiesoneofthevariablesinthe
loopcondition,anditiseasytoseethattheloopwillendandwhatthevalueofawillbe
atthattime.
Hereisanexampleofaloopthatisenteredanddoesnotterminate:
a=0
b=0
whileb<10:
a=a+1
print(a)
Inthiscasethevalueofbislessthan10attheoutset,sotheloopisentered.Thebody
oftheloopincrementsaas before,butdoes notchangeb. The loop condition does not
dependona,onlyonb,sowhentheloopconditionistestedagainthevalueofbisstill0,
andtheloopexecutesagain.Thevalueofbwillalwaysbe0eachtimeitistested,sothe
loopconditionwillalwaysbetrueandtheloopwillneverend.Theprintstatementwill
neverbeexecuted.
When this program is executed, the computer will seem to become unresponsive. As
longastheloopisexecutingtheprogramcandonothingelse,andsotheonlyindication
that something is wrong is that nothing is happening. There are many reasons why a
programcanappeartobedoingnothing:whenwaitingfortheusertotypesomeinput,for
instance, or when performing an especially difficult calculation. However, in this case,
whichiscalledaninfiniteloop,theonlythingtodoistoterminatetheprogramandfixthe
loop.
Hereisanexampleofaloopthatisnotentered:
a=100
b=0
whilea<10:
a=a+1
print(a)
Theconditiona<10isfalseattheoutsetbecauseahasthevalue100,sothecodeinthe
loopisnotexecuted.Thestatementfollowingtheloopisexecutednext,whichistheprint
statement,andthevalueprintedis100.
Theseloopsaremerelyexamplesthatillustratethethreepossibilitiesforawhileloop
and do not calculate anything useful. The two examples from the previous chapter can
makepracticaluseofawhileloop,anditwouldbeusefultolookatthoseagain.
2.1.1 TheGuess-A-NumberProgramYetAgain
TheprogramasitwaswritteninChapter1is:
choice=7
print(“Pleaseguessanumberbetween1and10:“)
playerchoice=int(input())
ifchoice==playerchoice:
print(“Youwin!”)
else:
print(“Sorry,Youlose.”)
Thegamewouldbebetterifitallowedtheplayertoguessagain,perhapsuntilacorrect
guesswasachieved.Awhileloopcouldbeusedtoaccomplishthis.Thinkaboutwhatthe
condition might be. The loop should end when the player guesses the answer. Another
waytosaythisisthattheloopshouldcontinuesolongastheplayerhasnotguessedthe
answer. The condition is one for continuation of the loop, not termination, so the loop
mustbeconstructedinsuchawaythatitcontinueswhentheconditionistrue.Theloop
willbeginwiththis:
whilechoice!=playerchoice:
At the beginning of the loop the variables choice and playerchoice must be defined.
This means that before the while statement, there must be code that does this. The
programnowlookslikethis:
choice=7
print(“Pleaseguessanumberbetween1and10:“)
playerchoice=int(input())
whilechoice!=playerchoice:
If the player has guessed incorrectly, then the body of the loop will execute. What
shouldbedone?Oneofthevariablesintheconditionhastobechanged,firstofall,and
thegoaloftheprogrammustbekeptinmind.Inthiscase,becausetheplayerhasguessed
incorrectly,twothingsshouldhappen.First,theplayermustbetoldthattheyarewrong
and to make another guess. Next, the new guess must be read into the variable
playerchoice,thussatisfyingtherulethattheloopconditionmusthaveanopportunityto
becomeFalse.Theprogramisnow:
choice=7
print(“Pleaseguessanumberbetween1and10:“)
playerchoice=int(input())
whilechoice!=playerchoice:
print(“Sorry,notcorrect.Guessagain:“)
playerchoice=int(input())
When the player finally guesses the number the loop will exit; if the first guess is
correctthentheconditionfailsatthebeginning,andthisamountstothesamethinginthis
case.Thelastthingtodoistoprintamessagetotheplayer:
choice=7
print(“Pleaseguessanumberbetween1and10:“)
playerchoice=int(input())
whilechoice!=playerchoice:
print(“Sorry,notcorrect.Guessagain:“)
playerchoice=int(input())
print(“Youhaveguessedcorrectly.”)
Note that, as was true with the if statement and as is always true in Python, the
indentation indicates which statements are a part of the loop (the suite) and which are
outside.
2.1.2 ModifyingtheGame
Asimplemodificationofthegameinvolvestellingtheplayerwhethertheirguesswas
toolargeortoo small.This will helpthem shrinkthe possiblerange of valuesand thus
guess the right answer more quickly. A modification to the body of the loop will
accomplish this. If the value that the player guessed is smaller than the target, then a
messagetothateffectisprinted,andsimilarlyiftheplayerguessesavaluelargerthanthe
target.Theuseofanifstatementherewouldbeappropriate,andthatifstatementwould
benestedinsideofthewhileloop:
choice=7
print(“Pleaseguessanumberbetween1and10:“)
playerchoice=int(input())
whilechoice!=playerchoice:
if(playerchoice<choice):
print(“Sorry,yourguesswastoosmall.
Guessagain:“)
else:
print(“Sorry,yourguesswastoolarge.
Guessagain.”)
playerchoice=int(input())
print(“Youhaveguessedcorrectly.”)
This program illustrates a second level of indentation. The if-else are indented to
indicatetheyarepartofthewhilestatement.Theprintstatementsareindentedfurther,to
showthattheyarealsopartoftheifstatement.
Doing some printing inside of the loop is useful because an infinite loop will be
obvious.It willprint awhole lotof stuffand never stop.It’snotalways practicalto do
that,soadegreeofcarefulanalysisshouldalwaysbedonetoensurethattheloopcanand
willterminate.
2.2 ROCK-PAPER-SCISSORSYETAGAIN
Thisgamereallyneedsaloop,andthepreviousimplementationwasnotcomplete.If
there is a tie then the game has to be repeated, and a winner must be determined. This
meansthattheloopinthiscasewillbesomethinglike:
whilethereisnowinner:
Thishappensonlywhentheplayerandthecomputerselectthesameobject,andinthe
originalcodewashandledbythestatements:
ifplayer==choice:
print(“Gameisatie.Pleasetryagain.”)
Thecondition“nowinner”becomesplayer==choice.Thecompletesolutioninvolves
the while loop and another input from the user within the loop. Here is one possible
answer:
choice=“paper”#Computerchoosespaper.
print(“Rock-paper-scissors:typeinyourchoice:“)
player=input()
#–––Thenewsectionofcode–––––––
whileplayer==choice:#Repeatinputuntilthereisa
winner
print(“Gameisatie.Pleasetryagain.”)
player=input()
#––––––––––––––––––-
ifplayer==“rock”:
ifchoice==“scissors”:
print(“Congratulations.Youwin.”)
else:
print(“Sorry-computerwins.”)
elifplayer==“paper”:
ifchoice==“scissors”:
print(“Sorry-computerwins.”)
else:
print(“Congratulations.Youwin.”)
elifplayer==“scissors”:
ifchoice==“rock”:
print(“Sorry-computerwins.”)
else:
print(“Congratulations.Youwin.”)
else:
print(“Error:Selectoneof:rock,paper,scissors”)
Theterminationoftheloopdependsontheusersinputandthevalueofthecomputers
choice,whichcouldalso(andshould)changeinsidetheloop.Theprobabilityoftheloop
continuingafteroneiterationis1in3,andtheprobabilitythatitwillstillbeloopingafter
Niterationsis(1/3)N,sothereisaverysmallchanceofthelooprepeatingmorethan2or
3times.
2.2.1 RandomNumbers
Most games depend on an element of unpredictability or chance. Those that do not
might be more properly called puzzles (or sports—football and hockey ought to have a
certain degree of skill involved). Given that computers do calculations, and that
calculationsshouldhavethesameresulteverytime,howdoesoneproduceanythingthat
israndomusingacomputer?Theanswerispartlyinhowthetermrandomisdefined.The
discussion involves some mathematics or at least some basic ideas in probability and
statistics.
If integers in the range 1 through 10 inclusive are considered, what is the likelihood
(chance,probability)thatthenumber5willbeselectedatrandom?Theansweris1in10,
or 0.1. This is true each time that question is asked. So if the number 5 has just been
chosenandanothernumberistobechosen,whatisthechancethatitwillbea5?Same
answer:1in10.Theprincipleisthatthenextchoicedoesnotdependonthepreviousone;
it’sapartofwhatmakesthemrandom.
Perhapsthewrongquestionwasbeingasked.So,whatisthelikelihoodthatthenumber
5 will be selected twice in a row at random? The answer is 1 in 100, or 0.01. Why?
Becauseitdependsonthequestionasked.Togettwoinarow,thefirstonemustbea5(1
in10)andthesecondonemustalsobea5(also1in10)sotheresultinglikelihoodis1in
10*10or1in100.Buteachtimeanumberischosen,thenumber5hasa1in10chanceof
beingselected.Amathematicaldiscussionofrandomnessdependsontheaskingtheright
question,andonprobabilities.Ifsomeeventiscompletelyrandom,thenitshouldhavethe
sameprobabilityofhappeningastheotherpossibleevents,buteventscanbecollectedto
formmore complex events. Each cardin a deck of playing cardsshould have the same
probabilityofturningup,butifthequestionis“What’sthechanceofaflush,”thenthe
differentwaysthataflushcanbecomprisedhavetobetakenintoaccount.Itcanbeavery
complicatedandinterestingsubject.
Numbers,inparticular,arerandomonlywithrespecttoeachother.Isthenumber“6”
random?That’snotreallyagoodquestion.Isthesequence87394random?Perhapsatest
couldbedevisedtoanswerthat.Isthesequence66666random?Mostwouldsaynot,but
ithasthesameprobabilityofbeinggeneratedatrandomasdoes87354.Tocreategood
gamesandsimulations,itisnecessarytodevisewaystogeneratearandomnumberusing
a computer, and to test numbers to see if they are in fact random. Then it would be
possibletosimulatetheflippingofacoin,ortherollingofadie.
What is the 100th digit of pi? It can be found easily. Are consecutive digits of pi
effectively random? As it happens, the answer is not known, but it is a good question.
Whatis108763dividedby98581?Whatistheremainder?Calltheremainderx:whatis
108763dividedbyx?Arethesenumbersrandom?Thesearchforamethodforgenerating
really good random numbers continues, but there are some pretty good methods (See:
Chapter 10). In Python a random number created by a computer algorithm can be
requestedbyusingabuilt-infunction.
A built-in function is like a mathematical function, and is provided by the language
itself (and so is “built-in”). The language element print that has been used so much is
really a built-in function. So are int() and float(). The functions sine and square root
shouldbewellunderstoodbyanyonewhohasgraduatedfromhighschool,andarealso
built-infunctions.SuchfunctionsbelongtomodulesinPythonandhavetobespecifically
requested by the program so that they can be used. This means that the name of the
module has to be known as well as the names of the built-in functions within it. The
commonmathematicalfunctionsarelocatedwithinthemodulemathandcanbeusedby
requestingthemathmodulewiththestatement:
importmath
Using a function in the math module involves using the name math followed by a
period(“.”)followedbythenameofthefunction.The“.”opensthemodulesothatthe
nameswithincanbeused,becausetheremaybeotherbuilt-infunctionsorevenvariables
thathavethesamename.So,ifthestatements:
x=math.sqrt(64)
print(x)
are executed, the program will print the number 8, which is the square root of 64. The
expressionsqrt(64)iscalledafunctioncall,andexecutesthecodeneededtocalculatethe
squarerootof64.Thenamesqrtisthenameofthefunction,whichiscodeprovidedby
the Python language. This particular call will always return the value 8, because 8 is
alwaysthesquarerootof64.Itisverymuchlikethefunctionsthatarestudiedingrade
school mathematics, such as sine and cosine. A module can be thought of as a bag of
programs. Each bag contains a set of programs that do a particular class of things, like
mathematics or drawing. By specifying the name of the module, access to all of the
functionswithinis granted,and byspecifying thespecific nameof afunction, thecode
thatwewantisspecificallymadeavailable.
Bytheway,theimportstatementshouldbeattheverybeginningoftheprogram.
Nowimaginethatitispossibletohaveafunctionthatproducesarandomnumberasa
value.Itisinthemodulenamedrandom,andthefunctioncouldbecalledrandomtoo.
Forexample:
importrandom
print(random.random())
Everytime(wellalmosteverytime,becauseitisrandom,afterall)thefunctionisused
itwillgiveadifferentvalue,arandomvalue.Thisvaluecanbeusedtomakegamesmore
realistic,becausegameshavearandomaspect.
This code prints the value 0.07229650795715237. Why? Because random.random()
producesarandomnumberbetween0.0and1.0.Thisisthemostcommonexampleofa
randomnumberfunction,anditisreallyverygeneral.Increasingtherangeisdonesimply
by multiplying by the maximum value desired; random.random()*100 gives a random
numberbetween0and100,forinstance.
Whatiftheproblemistosimulatetherollofadie?Thebagofcodethatistherandom
modulecontainsotherfunctionsrelatedtothegenerationofrandomnumbers,andoneof
themisespeciallysuitedtothisproblem.Adierollwouldbeimplementedas:
random.randint(1,6)
Therandint function accepts two numbers, called parameters. The first is the lower
limit of the range of random integers to be produced and the second is the upper limit.
Specifying1asthelowerlimitand6astheupper,asintheexampleabove,meansthatit
willgeneratenumbersbetween1and6inclusive,whichiswhatwouldbeexpectedfrom
rollingadie.Theresultofrollingtwodicewouldbeanumberbetween2and12,foundby
random.randint(2,12).
Flipping a coin is a two-level choice, and could be done with random.randint(1,2).
Morecompletely:
if(random.randint(1,2)==1):
print(“Heads”)
else:
print(“Tails”)
Going back again to the number guessing game, a random choice for the computers
numberisnowpossible.Insteadofthefirstlineofcodebeing:
choice=7
itshouldnowbe:
choice=random.randint(1,10)
Every time the program executes, the program will select a new random number, as
opposedtothechoicealwaysbeing7.
The introduction of a random choice is a little more complicated for the rock-paper-
scissors program because the variable holding the players choice is a string. There are
threepossiblechoices,sotoselectoneatrandommightlooklikethis:
i=random.randint(1,3)
ifi==1:
choice=“rock”
elifi==2:
choice=“paper”
else:
choice=“scissors”
Many of the examples that will be developed will involvea game or puzzle of some
kind,sotheuseofrandomnumberswillbeaconsistentfeatureofthecodeshown.
2.3 COUNTINGLOOPS
Featuresofprogramminglanguagesareprovidedbecausethedesignersknowtheywill
beuseful.Thewhileloopisobviouslyuseful,andisinfacttheonlykindofloopthatis
required in order to implement any program. However, loops that involve counting a
certainnumberofiterationsareprettycommon,andaddingsyntaxforthiskindofthing
wouldbecertaintobevaluableforaprogrammer.Theideaisthatsometimesaloopthat
executes,forexample,tentimesoraloopthatiteratedNtimesforsomevariableNwould
bewanted.InPythonandmanyotherlanguages,thisiscalledaforloop.
Insomelanguagesaforloopinvolvesaspecialsyntax,butinPythonitinvolvesanew
type(aclassoftypes,really):atuple.Hereisanexampleofaforloop:
foriin(1,2,3,4,5):
printi
Thiswillprintthenumbers12345eachonaseparateline.Thevariableitakeson
eachofthevaluesinthecollectionprovidedinparentheses,andtheloopexecutesoncefor
eachvalue of i. Thecollection (1,2,3,4,5) iscalled a tuple, and can contain any Python
objectsinanyorder.It’sbasicallyjustasetofobjects.Thefollowingarelegaltuples:
(3,6,9,12)
(2.1,3.5,9.1,0,12)
(“green”,“yellow”,“red”)
(“red”,3,4.5,2,“blue”,i)#whereiisavariablewitha
value
Theforloophastheloopcontrolvariable(inthecaseaboveitisi)takeoneachofthe
valuesinthetuple,inlefttorightorder,andthenexecutestheconnectedsuite.Theloop
willthereforeexecutethesamethenumberoftimesasthereareelementsinthetuple.
Sometimesitmaybenecessarytohavetheloopexecuteagreatmanytimes.Iftheloop
wastoexecuteamilliontimes,itwouldbemorethanawkwardtorequireaprogramtolist
a million integers in a tuple. Python provides a function to make this more convenient:
range().Itreturnsatuplethatconsistsofalloftheintegersbetweenthetwoparametersit
isgiven,includingthelowerendpoint.So:
range(1,10)is(1,2,3,4,5,6,7,8,9)
range(-1,2)is(-1,0,1)
range(-1,-3)isnotaproperrange.
range(1,1000000)ifthesetofallintegersfrom1to
9999999
Ranges involving strings are not allowed, although tuples having strings in them are
certainlyallowed.Theoriginalexampleforloopcannowbewritten:
foriinrange(1,6):
printi
andtheloopthatistoexecuteamilliontimescouldbespecifiedas:
foriin(0,1000000):
printi
This would print the integers from 0 to 999999. If range() is passed only a single
argument,thentherangeisassumedtostartat0;thismeansthatrange(0,10)andrange
(10)arethesame.
2.4 PRIMEORNON-PRIME
Here’sagamethatcanillustratetheuseofaforloop,andsomeotherideasaswell.The
computerpresentstheplayerwithlargenumbers,oneatatime.Theplayerhastoguess
whethereachnumberisprimeornon-prime.Aprimenumberdoesnothaveanydivisors
except 1 and itself; 3, 5, 11, and 17 are prime numbers. The game ends either when a
specificnumberofguesseshavebeenmade,orwhentheplayermakesaspecificnumber
ofmistakes.
A key problem to solve in this game is to determine when a number is prime. The
computermust beable to determinewhether theplayer is correct,and so forany given
numbertheremustbeawaytofigureoutwhetheritisprime.
Otherwise,theprogramforthisgameisnotverycomplicated:
whilegameisnotover:
selectarandomintegerk
printkandasktheplayerifitisprime
readtheplayersanswer
ifplayersansweriscorrect:
print“Youareright”
else:
print“Youarewrong.”
The mysterious portion of this program is the if statement that asks if the players
answeriscorrect.Thisreallymeansthattheprogrammustdeterminewhetherornotthe
number K is prime and then see if the player agrees. How can it be determined that a
numberisprime?Aprimenumberhasnodivisors,soifonecanbefoundthenthenumber
isnotprime.Themodulooperator%canbeusedtotellifadivisionhasaremainder:ifk
%n=0thenthenumberndividesevenlyintok,andkisnotprime.
Sotofindoutwhetheranumberisprime,trydividingitbyallnumberssmallerthanit,
andifanyofthemhaveazeroremainderthenthenumberisnotprime.Thisisajobfora
forloop.Here’safirstdraft:
isprime=True
forninrange(1,K):
ifk%n==0:
isprime=False
Aftertheloophascompleted,thevariableisprimeindicateswhetherKisprimeornot.
Thisseemsprettysimple,iftedious.Itdoesalotofdivisions.Toomany,infact,becauseit
isnotpossibleforanynumberlargerthanK/2todivideevenlyintoK.Soaslightlybetter
programwouldbe:
isprime=True#IsthenumberKprime?
forninrange(1,int(k/2))#DivideKbyallnumbers<K/2
ifk%n==0:#Iftheremainderis0thenn
isprime=False#dividesevenlyintoK:not
#prime
#Ifisprimeisstilltrueherethenthenumberisprime.
Next,thissectionofprogramshouldbeincorporatedintoacompleteprogramthatplays
thegame.Ifthegameissupposedtoallow10guesses,thenthefirststepistorepeatthe
wholething10times:
importrandom
correct=0#Thenumberofcorrectguesses
foriterationinrange(0,10):#10guesses
Now select a number at random. It should be large enough so that it is hard to see
immediatelyifitisprime,althoughevennumbersareagiveaway:
K=random.randint(10000,1000000)#Generateanewnumber
Nextprintamessagetotheuseraskingfortheirguess,andreadit:
print(“PrimeorNot:Isthenumber“,K,”prime?(yesor
no)”)
answer=input()#Readtheuserꞌschoice
Theusertypesinastring,“yes”or“no,”astheirresponse.Thevariableisprimethat
was used in the program that determines whether K is prime is logical, being True or
False.Itcouldbemadeintoastringtoosothatitwasthesameaswhattheusertyped,and
thenitcouldbecompareddirectlyagainsttheusersinput:
isprime=“yes”
Nowcomesthecodefordeterminingprimalityascodedabove,exceptwithisprimeas
astring:
isprime=True#IsthenumberKprime?
forninrange(1,int(k/2))#DivideKbyallnumbers<K/2
ifk%n==0:#Iftheremainderis0thenn
isprime=“no”#dividesevenlyintoK:notprime
#Ifisprimeisstilltrueherethenthenumberisprime.
Atthispointthevariableisprimeiseither“yes”or“no,”dependingonwhetherKis
actually prime. The users guess is also “yes” or “no.” If they are equal then the user
guessedcorrectly.
ifisprime==answer:
print(“Youarecorrect!”)
correct=correct+1
else:
print(“Youareincorrect.”)
Finally, the outer loop is ended and the result is printed. The value of the variable
correctisthenumberofcorrectguessestheusermade,becauseitwasincrementedevery
timeacorrectanswerwasdetected.Thelaststatementis:
print(“Yougave“,correct,“rightanswersoutof10.”)
ThisprogramcanbefoundontheCDinthedirectory“primegame.”
2.4.1 ExitingfromaLoop
Acleverprogrammerwouldnoticeaprettyseriousinefficiencywiththeprimenumber
program.Whenithasbeendeterminedthatthenumberisnotprime,theloopcontinuesto
divide more numbers into k until k/2 of them have been tried. If k= 999992 then it is
knownafterthefirstiterationthatthenumberifnotprime;itiseven,soitcan’tbeprime.
But the program continues to try nearly another half million numbers anyway. What is
neededisawaytotelltheprogramthattheloopisover.Thereisawaytodothis.
Aloopcanbeexitedusingthebreakstatement.Itissimplythewordbreakbyitself.
Thecorrectwaytousethisintheprogramabovewouldbe:
forninrange(1,int(k/2))#DivideKbyallnumbers<K/2
ifk%n==0:#Iftheremainderis0thenn
isprime=“no”#dividesevenlyintoK:notprime
break
This loop terminates when the number k is known to be not prime. The statement
followingtheloopwillbeexecutednext.Thiscansavealotofcomputercycles,butdoes
notmaketheprogrammorecorrect—justfaster.
Avariationonthisisthecontinuestatement.Thiswillresultinthenextiterationofthe
loop being started without executing any more statements in the current iteration. This
avoids doing a lot of work in a loop after it is known it’s not necessary. For example,
doing some task for a bunch of names except for people named “Smith” could use a
continuestatement:
fornamein(Jones,Smith,Peters,Sinatra,Bohr,
Conrad):
print(name);
ifname==Smith:
continue
#Nowdoabunchofstuff…
Boththebreakandcontinuedothesamethinginbothwhileandforloops.
Modifying the loop variable will not change the number of iterations the loop will
execute.Infact,ithasnoeffect.Thisloopdemonstratesthat:
foriinrange(0,10):
print(“Before“,i)
i=i+1000
print(“After“,i)
Itprints:
Before0
After1000
Before1
After1001
...
andsoon.Itseemsthatthevalueofichangesaftertheassignmentfortheremainderof
the loop and then is set to what it should be for the next iteration. This makes sense if
Pythonistreatingtherangeasasetofelements(itis),anditassignsthenextonetoiat
thebeginningofeachiteration.Unlikeawhileloop,thereisnotatestforcontinuation.In
anycase,changingiheredoesnotalterthenumberofiterationsandcan’tbeusedinplace
ofabreak.
2.4.2 Else
Theideathattheloopcanbeexitedexplicitlymakesthenormalterminationoftheloop
something that should be detectable too. When a while or for loop exits normally by
exhaustingtheiterationsorhavingtheexpressionbecomeFalse,itissaidtohavefallen
through.Whentheforloopintheprimenumberprogramdetectsafactor,itnowexecutes
abreakstatement,thusexitingtheloop.
What if it never does that? In that case no factor exists, and the number isprime. The
programasitstandshasaflagthatindicatesthis,butitcouldbedonewithanelseclause
ontheloop.
Theelsepartofawhileorforloopisexecutedonlyiftheloopfallsthrough;thatis,
whenitisnotexitedthroughabreak.Thiscanbequiteuseful,especiallywhentheloopis
involvedinasearch,aswillbediscussedlater.Inthecaseoftheprimenumberprogram,
anelsecouldbeusedwhenthenumberisinfactprime,asfollows:
forninrange(1,int(k/2))#DivideKbyallnumbers<K/2
ifk%n==0:#Iftheremainderis0thenn
isprime=“no”#dividesevenlyintoK:not
#prime
break
else:
isprime=“yes”#Loopnotexited:itisprime
Anelseinawhileloopoccurswhentheconditionbecomesfalse.Consideraloopthat
readsfrominputuntiltheusertypes“end”andissearchingforthename“Smith”:
inp=input()
while(inp!=“Smith”):
s=input()
ifs==“end”:
break
else:
print(“Smithwasfound”)
#Whentheprogramreachesthispointitisno
#longerknownwhetherSmithwasfound.
Ofcourse,theelseisnotrequired,andsomeprogrammersbelieveitisevenharmful.
Therearealwaysotherwaystoaccomplishthesamething.
2.5 LOOPSTHATARENESTED
Just as it is possible to have if statements nested within other if statements, it is
possible,andevenlikely,tohavealoopnestedwithinanotherloop.Anexampleofnested
forloopswouldbe:
foriinrange(0,10)
forjinrange(0,10)
print(i,j)
Theprintinthisexamplewouldexecute100times.Eachtimetheouterloopexecutes
oncetheinneroneisexecuted10times,foratotalof10*10or100iterations.Loopscan
be nested to a greater depth if necessary, and while and for loops can be nested
interchangeably.Isiteverusefultodothis?Yes,veryoften.
Sincetherehasbeenarecentdiscussionofprimenumbersandfactoring,considerthe
problemoffindthenumberwithinagivenrangethathasthegreatestnumberofdifferent
factors.Leavingout1andthenumberitself,2hasnofactors,nordoes3;4hasone(=2),5
hasnone,and6hastwo(2and3).Whichnumberbetween0and1000hasthemost?
Fromtheprimenumbergameitisclearthatthefactorscanbefoundusingaloop.Ifthe
loopisnotexitedwhenoneisfound,allofthemcanbeidentifiedand,moreimportantly
forthisproblem,counted.Foragivennumberk,thefactors can beidentifiedusing the
followingloop:
count=0;
forninrange(1,int(k/2)):#DivideKbyallnumbers<K/2
ifk%n==0:#Iftheremainderis0thenn
count=count+1
#Thenumberkhascountnumbersthatdivideevenlyintoit.
Thestatementcount=count+1hasreplacedtheisprime=“no”statementfromthe
prime number game. When the loop ends the value of count will be the number of
divisors it has. If this number is 0, then the number k is prime, by the way. Okay, the
problemhasbeensolvedforanynumberk.Nowsolveitforallnumbersbetween1and
1000andidentifythenumberwiththelargestvalueofcount(i.e.,thelargestnumberof
divisors).Thisinvolvesanotherloopenclosingthisonethatcountsfrom1to1000.
Defineavariablemaxvwhichisatanygivenmomentthenumberthathasthegreatest
numberofdivisors,andanothervariablemaxcountwhichisthenumberofdivisorsthat
maxvhas.Initiallymaxvis1andmaxcountis0(i.e.,thenumber1hasnodivisors).Now
loop between 1 and 1000 and replace maxv and maxcount whenever a new number is
foundforwhichthenumberofdivisorsisgreaterthanmaxcount.Specifically:
maxv=1
maxcount=0
forkinrange(1,1000):#Countthedivisorsforarange
count=0;
forninrange(2,int(k/2)):#DivideKbyallnumbers
#<K/2
ifk%n==0:#Iftheremainderis0
#thenn
count=count+1#Countthisdivisor
ifcount>maxcount:#Anewmaximum
maxcount=count#Savethecount
maxv=k#andthevalueitself
print(“Themostdivisorsis“,maxv,”with“,maxcount)
Theresultfor1to1000is:
Themostdivisorsis840with30
Theresultfor1to10000:
Themostdivisorsis7560with62
Bytheway,thislastversionneeded10secondstoexecute.
2.6 DRAWAHISTOGRAM
A histogram is a kind of graph. It usually represents the frequency of occurrence of
certaindiscretevalues.Commonexamplesincludetemperatureasafunctionofmonthof
theyear,orhistogramsofincomeasafunctionofyear,age,race,orgender.Drawingone
involvesknowing howmany categoriesthere areand whatthe numericalvalues arefor
each category. Then the numbers are scaled so they fit in a particular area, and the
rectanglesaredrawnsothattheheightsreflectthe relative numerical values. Figure 2.3
showssometypicalexamples.
A company wishes to plota histogram oftheir income for each quarterof 2016. The
numerical values are stored in variables Q1,Q2,Q3, and Q4 and range between 0 and 1
million.Usingfancygraphicsisnotpossibleyet,sohowcansimplehistogramsbedrawn?
Byusingtext.Ifthehistogramisdrawnsothatthebarsarehorizontalinsteadofvertical,
thenthenumberofcharactersdrawninarowcanbeusedtorepresentthe“height”ofthe
histogrambar.Usingthe“#”character,avalueof20couldbedrawnas:
Q1:####################20
Thisisanothersituationwherealoopisnecessary.
Therearethreepartstothehistogrambarabove:thelabel,thebar,andthedatavalue.
Thelabeliseasytoprint,andintheexampletherearefourpossibilities;thesearesimply
printedatthebeginningofeachlinebeingdrawn.Thedatavalueisnotnecessary,butitis
useful for people looking at the graph to know what the exact number is. Each “#”
character drawn could represent a range of values. The histogram bar is the trick. If
numbersuptoamillionmustberepresented,thenthebarmustbescaledsothatitfitsona
line.If50charactersfitonaline,theneach“#”printedneedstorepresent1000000/50,or
20000dollars.Anotherwaytosaythisisthatevery$20000ofincomeresultsinone“#”
character being printed. How many “#” are printed for the first quarter? Q1/20000 of
them.
Aproblem:theprintfunctionprintsoutalineeverytimeitiscalled.Howcanmultiple
thingsbeprintedonaline?Happily,printhasaspecialparametertoallowthat.Thecall:
print(i,end=ꞌ!′)
willprintthevariableiandthenprintthe“!”stringfollowingthat,everytime.Normally
theprintwillplaceanendoflinecharacter(representedas“\n”)attheendofeveryline,
buttheend= clause allows the programmer to change this to whatever they like. If the
string provided is empty (contains no characters) then the print will not print anything
extra after each call, meaning specifically that no end of line will be printed. Thus, the
statement:
print(“#”,end=””)
printsone“#”characterbutnoendofline.Ifanother“#”isprinted,thenitwillcomeright
aftertheonejustprinted.Thisisexactlywhatisneededforthehistogramprogram.Aloop
thatwouldprintten“#”charactersononelinecannowbewrittenas:
foriinrange(0,10):
print(“#”,end=””)
Given that the value of the variable Q1 is between 0 and 1000000 and each 20000
shouldresultinasingle“#”characterbeingprinted,thefirstquarterhistogrambarcould
bedrawnbythefollowing:
print(“Q1:“,end=””)
forkinrange(0,int(Q1/20000)):
print(#,end=ꞌꞌ)
print(”“,q1)
Thisincludesallofthelabels,andtheoutputwouldlooklikethis:
Q1:########190000
A complete solution to the problem would draw the histogram for all four quarters
alongwithaheadingforthegraph.Theoutputmightlooklikethis:
EarningsforWidgetCorpfor2016
Dollarsforeachquarter
==============================
Q1:#########190000
Q2:#################340000
Q3:###########################################873000
Q4:#####################439833
Exercise5attheendofthechapterinvolvesfinishingthisprogram.
2.7 LoopsinGeneral
Theconceptofaloopinaprogramminglanguagehasbeendiscussedformanyyears
andhasalargedegreeofboththeoryandpracticeunderlyingit.Theoriginal“loop”wasa
branchorgoto,wherethetopoftheloopwasidentifiedwithanaddressorlabelandatthe
bottom there was a statement that said to “go to” or transfer control to that location.
Examplesofthisare:
label1:add1tox12x=x+1
subtract2fromminmin=min-2
branchtolabel1goto12
Branchesweretypicalofassemblylanguageprogramming,whereeachlineofcodewas
one actual computer instruction. The goto statement was introduced in the first real
programminglanguageFORTRAN,butwas quicklysupplementedbyamorestructured
loopconstruct,thedostatement.Bothbranchandgotostatementscanbeconditional.
Variouskindsofloophavebeendevelopedovertheyears,andthemostcommonlyused
variationisthewhileloop.Theorysaysthattheonlykindthatisneeded,andprobablythe
most general, is the loop statement as defined in the Ada language. It is essentially an
infinite loop that allows escapes at multiple and various pointson specified conditions.
Thebasicsyntaxis:
loop
exitwhencondition1;
Statements…
exitwhencondition2;
endloop;
Anexitatthetopoftheloopisawhileloop.Anexitattheendcouldbearepeat
until as in Pascal or C++, and it is a simple matter to declare and initialize a control
variableandtesttheconditiontoimplementaforloop.Everythingispossiblewiththis
loopsyntax.
When specifically using Python, a while loop is all that is needed. If the range is an
integerone,thentheloop:
foriinrange(a..b):
isthesameastheloop:
i=a
whilei<b:
i=i+1
This loop has an initialization, a condition, and an increment. As individual entities
thesearesomewhathiddeninPython,beingmaskedbythesyntax, but theloopcontrol
variabletakesonthefirstvaluethefirsttimetheloopisexecuted(initialization),iterates
throughtheselections(increment),andterminatesafteritselectsthefinalone(condition).
The loop control variable is not really what gets incremented; what is incremented is a
countthatindicateswhichoftheitemsinthetupleiscurrentlybeingused.Intheloop:
foriin(“red”,“yellow”,“green”):
thevariableitakesonthevalues“red,”“yellow,”and“green,”butwhatgetsincremented
eachtimethroughtheloopisanindicationofwhichpositioninthetupleisrepresentedby
i.Thevalue“red”is0,“yellow”is1,and“green”is2andacountimplicitlystartsat0and
stepsuntil2assigningvaluestoi.Thiskindofloopissimilartothatfoundinthelanguage
PHP,andisalevelofabstractionabovethoseinJavaandC++.
2.8 EXCEPTIONSANDERRORS
Computersdonot,asageneralrule,makemistakes.Likeotherhuman-designedand-
constructeddevicessuchascarsandstoves,computerscanbeawkwardtouse,canhave
designfeaturesthatdon’tturnoutasexpected,andcanevenbreakdowntooquickly.But
theydonotmakemistakes.Acomputerprogram,ontheotherhand,almostcertainlyhas
mistakesorbugscodedwithinit.Consumersdon’tusuallymakeadistinctionbetweenthe
computerandthesoftwarethatrunsonit,butprogrammersandengineersmust.Whena
computer program does not work properly, a programmer must exhaust all ways the
programcouldbewrongbeforelookingatanerrorinthecomputeritself.
Creatingacorrectprogramisdifficultformanyreasons.Firstofall,beforeanycodeis
written,theproblemtobesolvedmustbeclearlyunderstood,anditmustbethecorrect
problem.Solvingthe wrongproblem isa prettycommon error,but can’tbe detectedor
correctedbythecomputer.Commonexamplesofthissortoferrorcomefromstatingthe
problem in English (or a human language of any description) where errors in
understanding occur. “Find the average of the first ten integers,” for example, is a little
ambiguous. Is the first integer 0 or 1? What is meant by “average”—the mean or the
median? Computer programmers tend to be quite literal, and so what they think is the
answer will be written into the code, and then they will argue for that answer as being
correct.Itisveryimportanttorealizethat,whatevertheliterallycorrectansweris,thereal
correctanswerisbasedonthecorrectunderstandingoftheproblem.Sometimesitisstated
badly, but no matter whose fault the problem is, the job of fixing it will lie with the
programmer. Sometimes a little time at the beginning clarifying the question can save
moretimelater,andstickingwithanoverlypedanticinterpretationwillcauseproblemsin
thelongrun.
Acorrectprogramalsodependsontheprogrammerbeingabletoidentifyallpossible
circumstances that can occur and knowing how to deal with each of them. Failing to
handleonepossiblesituationisanerror,andtheprogramwillbehaveunpredictablyifthat
situation occurs in practice. Statements that handle errors appear all though real (in the
fieldorcommercial)code.Infact,itiscommonthattherearemorestatementsthatdetect
anddealwitherrorsthancodethatactuallycomputesananswer.Onethingthatshouldbe
remembered:alllinesofthecodeneedtobetested.Inverylargeprogramsthismaybe
impossible,buteverylineofcodethathasneverbeenexecutedisapotentialerror.Testas
manyaspossible,includingtheerrordetectioncode.
User input is a frequent cause of mistakes in programs. It’s not that the user is the
problem; the programmer must anticipate all possible ways that a user can enter data.
Thereisusuallyonecorrectwaybutmanyerroneousones,anditisimpossibletopredict
whatauserwillenterfromakeyboardinresponsetoanyrequest.Similarly,thecontents
of a file may not be what the programmer expects. File formats are standards, but
sometimes there are variations and at other times a user may have entered the data
improperly.Whilethemistakeisonthepartoftheuser,itisalsoaprogrammingmistake
if the error is not detected and is allowed to have an impact on the execution of the
program.
Programmerstendtomakeassumptionsabouttheproblem.Itisacommonmistaketo
think“thissituationcanneverhappen”andthenignoreit,howeverunlikelythesituation
seems. Testing every statement for everything that could possibly go wrong may be
impossible,buttestingforthegeneralsituationmaybepossible.Itwouldbegreattobe
abletosay“ifanystatementinthissectionofcodedividesbyzero,”or“ifanyvariables
inthiscodehavethewrongtype,”thendosomeparticularthing.
Sinceitisimpossibletowriteaprogramofanylengthwithouttherebeingcodingerrors
of some kind included, a step towards a solution may be to check all data before it is
operated on to ensure the pending operation is going to succeed. For instance, before
performingthedivisiona/b,testtomakesurethatbisnotzero.Thisdependsontheerror
being at least in principle predictable. Most modern languages, Python included, have
implemented a way to catch errors and permit the programmer to handle them without
havingtestsbeforeeachstatementorexpression.Thisfacilityiscalledtheexception.
The word exception communicates a way to think about how errors will be handled.
Somecodeislegalandcalculatesadesiredvalueexceptundercertaincircumstances,or
unless some particular thing happens. The way it works is that the program tries to
perform some operation and errors are allowed to occur. If one does, the computer
hardwareoroperatingsystemdetectsitandtellsPython.Theprogramcannotcontinuein
thewaythatwasplanned,whichiswhythisiscalledanexception.Theprogrammercan
tellPython whatto do if specific errorsoccur bywriting some codethat dealswith the
problem.Iftheprogrammerdidnotdothis,thenthedefaultisforPythontoprintanerror
messagethatdescribestheerrorandthenstopexecutingtheprogram.Errormessagescan
beseenasafailureonthepartoftheprogrammertohandleerrorscorrectly.
A simple exampleis the divide byzero error mentioned previously.If the expression
a/bistobeevaluated,thevalueofbcanbecheckedtomakesureitisnotzerobeforethe
divisionisdone:
ifb!=0:
c=a/b
Thiscanbetediousfortheprogrammerifalotofcalculationsarebeingdone,andcan
beerrorprone.Theprogrammermayforgettotestoneortwoexpressions,especiallyif
engagedinmodificationsortesting.Usingexceptionsisamatterofallowingtheerrorto
happenandlettingthesystemtestfortheproblem.Thesyntaxisasfollows:
try:
c=a/b
except:
c=1000000
The try statement begins a section of code within which certain errors are being
handledbytheprogrammerscode.Afterthatstatement,codeisindentedtoshowthatitis
partof the try region. Nearly any code can appear here, but the try statement must be
endedbeforetheprogramends.
Theexceptstatementconsistsofthekeywordexceptand,optionally,thenameofan
error.TheerrorsarenamedbythePythonsystem,andthecorrectnamehastobeused,but
if no error name is given as in this example, then any error will cause the code in the
exceptstatementtobeexecuted.Notspecifyinganamehereisanimplicitassumptionthat
eitheronlyonekindoferrorcouldpossiblyoccurorthatnomatterwhaterrorhappens,the
samecodewillbeusedtodealwithit.Specifyinganunrecognizednameisitselfanerror.
Thenamecanbeavariable,butthatvariablemusthavebeenassignedarecognizederror
namebeforetheerroroccurs.Thecodefollowingtheexceptkeywordisindentedtoo,to
showthatitispartoftheexceptstatement.Thisisreferredtobyprogrammersasanerror
handler,andisexecutedonlyifthespecifiederroroccurs.
Thisappearstobeevenmoreverbosethantestingb,butanynumberofstatementscan
appearbetweenthetryandtheexcept.Thissectionofcodeisnowprotectedfromdivide
byzeroerrors.Ifanyoccur,thencodefollowingtheexceptstatementwillbeexecuted,
otherwisethatcodewillnotexecute.Ifothererrorsoccur,thenthedefaultactionwilltake
place—anerrormessagewillbeprinted.
Testingspecificallyforthedividebyzeroerrorcanbedonebyspecifyingthecorrect
errornameintheexceptstatement:
try:
c=a/b
exceptZeroDivisionError:
c=1000000
Morethanonespecificerrorcanbecaughtinoneexceptstatement:
try:
c=a/b
except(ValueError,ZeroDivisionError):
c=1000000
Clearly (ValueError, ZeroDivisionError) is a tuple, and could be made longer and
couldbeassignedtoavariable.
Also,therecanbemanyexceptstatementsassociatedwithasingletry:
try:
c=a/b
exceptValueError:
c=0
exceptZeroDivisionError:
c=1000000
And,aswasmentioned,avariablecanholdthevalueoftheerrortobecaught:
k=ZeroDivisionError
try:
c=a/b
exceptk:
c=1000000
Finally,the exceptionnamecan be left outaltogether.Inthat caseany exceptionthat
occurswillbecaughtandtheexceptioncodewillbeexecuted:
try:
c=a/b
except:
c=0
2.8.1 Problem:AFinalLookatGuessaNumber
Thefinalversionoftheprograminvolvingguessinganumberlookslikethis:
choice=7
print(“Pleaseguessanumberbetween1and10:“)
playerchoice=int(input())
ifchoice==playerchoice:
print(“Youwin!”)
else:
print(“Sorry,youlose.”)
Usingexceptionsandwhathasbeendiscussedabouterrorchecking,thisprogramcan
beimproved.First,iftheuserenterssomethingthatisnotaninteger,itisanerror.This
should be caught using an exception. Also, rather than forcing the player to run the
programagain,aloopcanbeusedtoaskforanotherguess.Theinputshouldbewithin
the try statement. The except statement should print an error message, and the entire
collectionshouldbewithinaloopthatcontinuestoasktheusertoguessanumber.Hereis
abetterversion:
choice=7
guessed=False#Hastheuserguessedareasonable
number?
whilenotguessed:#Keeptryinguntiltheyhave
print(“Pleaseguessanumberbetween1and10:“)
try:#Catchpotentialinputerrors
playerchoice=int(input())
guessed=True#Successsofar
except:#Anerroroccurred.
print(“Sorry,yourguessmustbeaninteger.”)
ifchoice==playerchoice:#Correctguess?
print(“Youwin!”)
else:
print(“Sorry,youlose.”)
ThevariableguessedissettoTruewhenasuccessfulguessismade,andthisstopsthe
loopfromrepeating.Iftheuserentersarealnumberorastring,theexceptioniscaught
beforethathappens, theerror messageis printed,and theuser is askedto enteranother
guess.
Whatelseiswrongwiththiscode?Well,theuserisaskedtoenteranumberbetween1
and10,butthatvalueisnevercheckedtoseeifitisOK.True,ifitfallsoutsidetherange,
then it will always be an incorrect guess and the player will lose. It’s a penalty for not
payingattentiontotherules.Aprogramshouldwheneverpossiblegivetheuserasmuch
information as is reasonable, so it would be better to check the value of the variable
playerchoiceandgiveanerrormessageifitisoutofrange.Thebestwaytodothisisto
placethecheckaftertheexceptstatementatthebottomoftheloop,andsetthevariable
guessedtoFalseiftheguessisanimproperone.Thentheloopwillrepeatandtheplayer
willgetanotherguess.
Thisversionoftheprogramis:
choice=7
guessed=False
whilenotguessed:
print(“Pleaseguessanumberbetween1and10:“)
try:
playerchoice=int(input())
guessed=True
except:
print(“Sorry,yourguessmustbeaninteger.”)
ifplayerchoice<10orplayerchoice>10:#Istheguess
#in1..10?
print(“Yourguesswas”,playerchoice,”whichisoutofrange.”)
guessed=False#Nope.Guessagain
ifchoice==playerchoice:
print(“Youwin!”)
else:
print(“Sorry,youlose.”)
2.9 SUMMARY
Theabilitytorepeatacollectionofoperationsisanessentialpartofanyprogramming
language.Thewhileloophasaconditionatthebeginning,andsolongasthatconditionis
true,thestatementscomprisingtheloopwillbeexecutedrepeatedly.Theforloophasan
explicitlistofitemsforwhichtheloopwillbeexecuted,orarangeofnumericalvalues
thatdefinehowmanytimesthecodewillberepeated.
Most problems that are solved using a computer program have some degree of
repetitionimplicitintheimplementation,andsomecomputeralgorithmsarequiteexplicit
abouthowtheiterationsaretobesetupandhowmanyareneededtosolvetheproblem
(See:Exercises3and4).
CertainerrorsthatcanoccurinprogramcanbedetectedautomaticallybyPython.Ifthe
programmerdoesnotspecifyotherwise,thentheseerrorscauseamessageandpremature
program termination. The try-except statement allows the programmerto handle errors
withoutendingtheprogram, andpermitsbetter communicationofthekind oferrorthat
occurred,inthecontextoftheprogram,totheprogrammeroruser.
Exercises
1.Giventhefollowingdefinitions:
var1=12
var2=100
var3=-2
var4=0
Whatisprintedbythefollowingwhileloops:
a.whilevar1<var2:
print(var1)
var1=var1+30
b.whilevar1<var2:
print(var1)
var1=var1*2
c.whilevar1>0:
var4=var4+1
var1=var1–1
print(var1,var2)
d.whilevar1>0:
var4=var4+1
var1=var1–var4
print(var1,var2)
e.whilevar1<var3:
print(*,end=””)
var3=var3+2
f.whilevar2>var1*var4:
var1=var1+1
var4=var4+1
print(var1,var2)
2.Whatwouldbeprintedbythefollowingforloops:
a.foriinrange(1,10):
print(i)
b.foriin(1,10):
print(i)
c.foriin(“red,“green,“blue):
print(i)
d.foriinrange(0,10):
forjinrange(1,10):
ifi==j:
print(i)
e.foriinrange(0,10):
forjinrange(0,50):
ifi*i==j:
print(i)
f.foriin(0,10):
i=i*2
print(i)
g.foriinrange(1,10):
forjinrange(1,i):
print(j,end=””)
print()
h.oriinrange(0,10):
i=i+1
forjinrange(1,i):
print(j,end=””)
print()
3.TheGreekmathematicianZeno(c.450BCE)iscreditedwithcreatingtheparadoxof
theTortoiseandAchilles.AtortoisechallengedthegreatheroandathleteAchillestoa
footrace.Allthetortoiseaskedwasaten-yardheadstart.Theideawasthatoncethe
racebegan,Achillescouldruntheten-yardheadstartinasmalltime;however,inthat
sametimethetortoisewouldmoveforwardasmallamount,perhapsayard.When
Achillesmadeupthatyard,thetortoisewouldhavemovedaheadagainasmall
distance;andsoon.ThelogicwasthatAchillescouldnevercatchup.The
misunderstandinghereisthataninfinitelylongseriesofnumberscanadduptoafinite
value.WriteasmallPythonprogramthatsumsthenumbers½,¼,,1/16,andsoon
for20iterationsandsuggestwhatthesumwouldbeifitwerecarriedtoaninfinite
numberofiterations.
4.OnewaytocalculatethesquarerootofanumberistouseNewton’smethod.This
startswithaninitialguess:ifthesquarerootofxisbeingcomputed,thenafairinitial
guessgwouldbex/2.Successiveestimatesaregivenbytheexpression:
newg=(g+x/g)/2
Successiveestimatesarenearerandnearertotheactualsquareroot.Writeaprogramto
computethesquarerootofanumberthatisenteredfromthekeyboard.
5.CompletetheprogramthatdrawsahistogramfortheearningsofWidgetCorpforfour
quartersof2016.Earningsare:
a.190000
b.340000
d.873000
d.439833
6.ModifytheprograminExercise5sothatthedataforthefourquartersisreadfromthe
terminal(i.e.,enteredbytheuserfromthekeyboard).Testitforthevalues:
a.900000
b.874000
d.200000
d.439000
7.ModifythesolutiontoExercise6inChapter1(makingchange)sothatitmakes
effectiveuseofaforloop.Theprogramshouldstillreadanumberbetween1and99,
whichisanamountofchangetobegiven,andprintthecoinvaluesthatwouldbe
used.Modifyittonotuse50-centpieces,becausenobodyhasthoseanymore.
8.Convertthefollowingforloopsintotheequivalentwhileloop:
a.foriinrange(1,10):
print(i,i*i)
b.sum=0
foriin(range(10,0,-1):
sum=sum+i
print(i,sum)
9.AgoodsolutiontoExercise4above(squareroot)woulddetectnegativenumbersand
printamessagetotheeffectthatsquarerootsofnegativenumbersdonotexist(notas
realnumbers,anyway).ModifythesolutiontoExercise4touseanexceptiontodeal
withthatsituation,andhandleotherpotentialerrors.
NotesandOtherResources
Online tutorial on Python loops:
http://www.tutorialspoint.com/python/python_loops.htm
Cornell University summary of if statements and loops:
http://www.cs.cornell.edu/courses/cs1130/2012sp/1130selfpaced/module2/module2part1/ifloop.html
Sthurlow.com,Loops,loops,loops…,http://sthurlow.com/python/lesson04/
1.HenryFordandSamuelCrowther.(1922).MyLifeandWork,GardenCity
Publishing,GardenCity,NY,http://www.gutenberg.org/ebooks/7213
2.DavidBeazleyandBrianK.Jones.PythonCookbook,3rdEdition:Recipesfor
MasteringPython3,http://www.onlineprogrammingbooks.com/python-cookbook-
third-edition/
CHAPTER3
SEQUENCES: