Chapter 1 The Way of The Program

• Computer science includes
  • mathematics - formal notations, logic
  • engineers - building systems, designing
  • scientists - observe, make hypotheses, test
• Computer scientists must be good at problem solving
  • state problems clearly
  • think of solutions (including "thinking out of the box")
  • state solution clearly
• Algorithms
  • Algorithms are step by step list of instructions to solve a problem
  • better to make a _general_ solution then write it in a programming language so the computer can do it
  • Example (Euclid's Algorithm for GCD):
    • Finding the greatest common divisor, one of the 1st known algorithms
      1. Get two numbers, call them num1 and num2
      2. While num2 is not zero
      3.      If num1 > num2, num1 = num1 - num2
      4.      otherwise num2 = num2 - num1
      5. Show num1 as the GCD
• Hardware terms to know (NOT in the textbook)
  • programs are processed step by step in the CPU (central processing unit)
  • primary memory = RAM
    • RAM is volatile! (loses contents if power interrupted)
    • RAM is fast! (nanoseconds)
    • RAM is expensive! per megabyte or per gigabyte
  • secondary storage = Hard drive, CD, DVD, solid state (memory stick)
    • secondary storage is not volatile
    • secondary storage is a million times slower than RAM (milliseconds)
    • secondary storage is cheaper per gigabyte
  • Units used in talking about computers
    • Capacity (space in RAM or on HD or memory stick)
      • byte
      • 1 Kilobyte = 1 KB = 1024 bytes = 2 to the 10th bytes
      • 1 Megabyte = 1 MB = 1024 KB = 2 to the 20th bytes
      • 1 Gigabyte = 1 GB = 1024 MB = 2 to the 30th bytes
      • 1 Terabyte = 1 TB = 1024 GB = 2 to the 40th bytes
      • 1 Petabyte = 1 PB = 1024 TB = 2 to the 50th bytes
      • 1 Exabyte = 1 EB = 1024 PB = 2 to the 60th bytes
    • Speed (how many processing cycles a CPU can perform in a second)
      • Hertz = 1 Hz = 1 cycle per second
      • Megahertz = 1,000,000 Hz = 1 million cycles per second
      • Gigahertz = 1,000,000,000 Hz = 1 billion cycles per second
• Programming Languages in History (not in textbook)
  • The first computers were glorified calculators
    • they had a "store" which held data to work on
    • Instructions had to be entered manually in front panel, switches or cables
    • Very slow (but more accurate than humans)
  • John Von Neumann had an idea - why not put instructions in "store" = RAM?
    • that way the computer could access them as fast as mechanically possible
    • suddenly computers were faster
    • suddenly computers were multi-purpose
    • change the program in memory and change the behavior of the machine!
    • it was such an insight that all machines built since are called "von Neumann machines"
    • both instructions and data are in RAM when processed!
• High Level languages vs. low level languages
  • Python is a high level language (some others are C++, Java, PHP, Perl)
  • low-level language = machine language or assembly language
    • machine language = binary = patterns of 1 and 0
    • very close to how the machine hardware works, many many small steps
  • easier to write in High Level Language (HLL) - they work more like people think
  • HLL are portable (easily moved from one type of machine to another, because they aren't written in a particular machine's machine language)
• Example of language levels - telling a Robot to get out of a room
  • Machine language: take a step, raise arm, grasp knob, turn knob...
  • Assembly language: Leave through Door
  • High-level language: Get outta here!
• Interpreters and compilers translate HLL to low-level languages
  • Compiler takes source code to object code (executable) - the _compiler_ does NOT execute the code! it just creates the code. You tell the Operating system later that you want to run it
  • Interpreter reads a little source code, translates it to machine code, and executes it (book does not say translates), then reads a little more, translates it, executes it, etc.
  • Interpreters considered easier to develop with
    • can get faster feedback on code, try things out more easily than a compiled language
  • most HLLs have IDEs - Visual Studio, IDLE, WingIDE - not in textbook
    • components of IDE - editor, translator (that is, either an interpreter or compiler), debugger, shell (or command line), linker, loader
      • editor lets you enter program source, with colorization, indents, find/replace, etc.
      • translator = interpreter or compiler (sometimes both)
      • shell (with interpreter) allows for entry of small amounts of code to try out, also is where input and output happen for standard devices (print, input)
      • linker connects code from libraries with your code to make one executable
      • loader brings in executable code from storage to RAM (remember von Neumann!)
      • debugger helps you step through code, shows you variables and flow of execution
• Python Versions
  • Most software is usually numbered with versions, from 1.0 to 2.0 to 3.0...
  • major revisions cause first number to change, minor revisions cause right hand numbers to change
  • Python community decided to go from 2.5 to 3.0
  • Those two versions were very incompatible
  • Some people decided to stay with 2.5 (had large legacy programs and didn't want to convert!)
  • Now there are two branches of Python - 2.5, 2.6, 2.7 and 3.0, 3.1, 3.2, 3.3
  • we use 3.x in this class!
• Creator of Python - Guido van Rossum http://www.python.org/~guido/
• Python named after "Monty Python's Flying Circus"
• Python has two modes
  • shell mode: is immediate execution
  • program mode: is an editor, lets you type in code for later translation and execution
• Shell mode
  • example with Shell
  • prompt >>>
  • only good for short pieces of code
• codelens
  • codelens in textbook LIKE debugger
    • step by step execution of program
    • shows variables as changed
    • only works for preprogrammed examples
• More About Programs
  • a program is a sequence of instructions of how to perform a computation
  • kinds of instructions
    • input
    • output
    • math +, -, /, *
    • logic operators like >, <, and, or
    • control structures
      • conditional execution (if)
      • repetition (loop)
      • subprogram (function)
  • to use these to write a program, have to reduce the problem to small pieces
  • programs are more specific than algorithms
• What is Debugging?
  • what is a bug?
    • syntax errors
    • runtime errors
    • semantic errors
  • syntax errors
    • A program only runs if it has no syntax errors
    • syntax = rules about the structure of a program
    • English syntax (e.e. cummings)
    • interpreter will find them in a programming language
    • will not run until you fix the syntax errors
  • runtime errors
    • happens during running of the program
    • for example, file is missing that you try to open,
    • for example, user gives you wrong type of data for input
    • for example, dividing by a value which is zero
    • called an "exception" - Python interpreter gives big red message
  • Semantic errors (also called logic errors)
    • errors in meaning
    • runs but gives incorrect results
    • testing with known inputs and outputs is the only way to find these
  • Experimental Debugging
    • every program has to be tested to find out if it has bugs
    • we will doing test cases (a test plan) for each program
• Formal and Natural Languages
  • natural languages = human languages
  • formal languages - artificial (notations) strict in syntax, have to be precisely stated
  • natural languages are ambiguous, formal languages are not (or are not supposed to be)
  • natural languages are redundant - formal languages are not
• A Typical First Program
  • hello world
  • go through the tutorial of using editor instead of shell
• Comments
  • # totally ignored by interpreter
  • only marks off one line as a comment, the line with the # on it
  • used to explain the actions to a reader
  • if you don't comment your code, we assume you don't understand it
  • required in this class!
  • another form uses ''' (three single quotes) to start and end a comment - the comment can be as many lines long as you like
• Difference between a compiler and an interpreter
  • you have a recipe for cake, written in Russian - you don't read Russian
  • an Interpreter
    • you hire a translator to come in and translate it for you
    • they translate the first step, you do it
    • they translate the next step, you do it
    • by the end of the recipe, you have a cake
    • if you want to bake another cake with the same recipe, you must hire the translator again
  • a Compiler
    • you hire a translator
    • they read the whole recipe, and write it down in English on another piece of paper
    • they give you the paper
    • their job is done
    • you can bake as many cakes with that recipe as you like, you don't need the translator to be around at all
    • paper is the executable form of the recipe
• Ethics
  • Responsibility comes with knowledge
  • Don't do hacking!
  • Don't do piracy!
  • Don't do data theft
  • Protect data privacy
  • You have a responsibility to develop programs without errors or at least let the users know there are flaws
  • See ACM Code of Ethics