CPS 125

Alexander Ferworn

Week 1

Main Topics
Note: In this document everywhere you see a -- it means double quotation mark.

Why Bother?

Motivation: Computers and programming are important because they let people do what they like to do best--NOTHING!

Example: 1981 U of T Chemistry lab, taking reading for 4 hours in 15 second increments...bet a computer would have helped.

Example: Get off of unwanted mailing lists. Auto-reply mail message written in a programming language called PERL.

To: <Goof who sent me junk mail>

From: aferworn@on.bell.ca

Subject: In reply to your offer of making me rich by purchasing <Stupid product name>

Greetings and Salutations,

Thank you for your generous offer of making me rich by the simple purchase of <Stupid product name>. Unfortunately I must pass this time. But, I was so pleased about being on your mailing list that I am sending you a 25 Megabyte Quicktime movie titled --The best of PeeWee Herman--. Thank you for your attention,

Alex Ferworn

Problems: problems are challenges you experience in your life.

Example:

Problem: You wake up and you are hung over and would really, really like to visit your bathroom down the hall. What do you do?

Potential Solutions:

Algorithms: An algorithm is a step-by-step set of instructions for executing a particular task for communication to a human.

Algorithms have the following characteristics

Here is a toilet algorithm

1) Open your eyes

2) Stand up

3) Walk to the door

4) Open the door

5) Walk to the toilet

6) Spew your guts out

7) Stop

Computers and Programs: A program is an algorithm described to a computer. A computer is a device which is capable of executing a program.

Computers have the following characteristics of interest

Binary and Machine Codes

Of course, binary digits (bits) can only be on or off, so some clever guy thought it might be fun to group more than 1 bit with another. Now you can encode more than two thing in this way (Why is that you can only encode 2 things with 1 bit?).

Suppose you had two bits grouped together. You could represent 4 things. For example we could encode how well you are doing in this course.

Example

00 = Excellent work

01 = Good work

10 = Poor woork

11 = Considering Macdonald&Atildes University

So, we could encode everything as grouped 1&Atildes and 0&Atildes.

The standard is to group 8 bits into something called a byte. 8 bits give you the possibility to represent 256 things (0 to 255).

To confuse things a bit more, each byte can represent either a number (data) or an instruction. Forget this for the moment and we will assume each byte is a number representing an instruction.

Language Interpretation

These byte codes are called Machine Codes or Machine Language. Computers like them because they can be executed directly by the machine. It just reads a code, interprets what it means and does that action.

If you make the bytes represent words you can tell a computer about your algorithm. So, here is an example dictionary of bytes/words (this is not a real machine language just an Alex example).

Example

00000000 = OPEN

00000001 = EYES

00000010 = STAND

00000011 = WALK

00000100 = OPEN

00000101 = DOOR

00000110 = TOILET

00000111 = SPEW

00001000 = STOP

We could tell the computer our algorithm

00000000 00000001

00000010

00000011 00000101

00000100 00000101

00000011 00000110

00000111

00001000

Assembly Language

Well this is all well and good but there must be an easier way...who can remember all those codes. So the bright guys got to work and they created something called assembly language which shortened all the commands into assembly codes and grouped some of the related stuff together.

OPEN(EYES)

STAND

WALK(DOOR)

OPEN(DOOR)

WALK(TOILET)

SPEW

STOP

Translation and Interpretation

Computers can almost execute this stuff directly (interpret it) since only a simple translation is required from the mnemonic (English-like command).

High-Level languages

This was fine but it soon became clear that if there was a complex problem the program would be horrendous to write. That&Atildes where higher level languages come in.

Higher level languages hide some of the obscurity of the machine. In Machine Code and Assembly Language the programmer must specify everything. This is a problem because many times the same code is written again and again which could lead to errors as things are mistyped.

Higher level languages (like C) avoid this problem by making each command group together a whole bunch of lower-level machine code--you don&Atildet have to keep repeating these codes yourself--possibly introducing more errors (since you never learned how to type).

#define EYES 0

#define DOOR 1

#define TOILET 1

#include <stdio.h>

void main()

{

open(EYES);

stand();

open(DOOR);

walk(TOILET);

printf(SPEW);

}

There are of course even higher level languages--the higher you go, the more stuff is done for you. The repetitious stuff now happens in the background.

Compilation, linking and executing

Computers cannot interpret high level languages directly because the codes are more complex and rely on functions which may be hidden someplace either in the depths of the language or in a library of common routines. The computer must now go through several steps;

A Computer Architecture

Introduction

There are only three things you need to worry about when baby sitting kids...

  1. Can you communicate with them?
  2. Can they remember what you said?
  3. What are they going to do about it?

They do this with their;

  1. Ears, eyes, nose, mouth, gestures, etc
  2. memory
  3. brain

Computers are like small children because there are essentially only three things to worry about.

Input/Output peripherals

These are the things that allow you to tell the computer things and let it tell you things. Sometimes a device (physical piece of hardware) will perform both functions at different times (disk drive).

Memory

Computer memories are capable of storing bits over time. The memory of a computer is not a single entity (although in many cases you can think of it that way). It is a collection of units dispersed in space and function with a spectrum of speeds, capacities and costs.

You may have seen this yourself,

Memory can only store bits because the tiny circuitry that makes up each spot in memory only knows how to be on or off (1 or 0).

Primary memory refers to memory that is typically on-board the circuit board that is your CPU board. Secondary memory is everything else.

If you forget all that, you can think of memory as a long narrow sheet of paper. You can only write one thing on each line of the paper and then you must go to the next line. The same is true for reading it. So , to get from any one line to any other you just need to add or subtract an integer value from where you are to where you want to go....you can jump around in memory.

Processing Unit

The Central Processing Unit (CPU) is responsible for executing the programs that you write and that are resident in your computer already (like the operating system which is also a program that runs your program). To do this it needs a number of things

Program Counter (PC): A location in memory that contains the location of the next instruction to execute. Because the chunk of memory is accessed so often, you want it to be done quickly so the PC is in an area of faster memory. Things in this space are called registers.

Instruction Register (IR): Got to put the instruction some place so it can be interpreted...this is where it goes.

To do any complex math, like adding one to something, the CPU uses a special math processor called the arithmetic/logic unit (ALU). This device is capable of doing math.

What the CPU does:

  1. Get the contents of memory pointed to by the PC and put it in the IR
  2. Increment the PC
  3. Figure out what the instruction means and get anything else needed (operands)
  4. Execute the command (with the help of the ALU, other register and memory)
  5. Go back to 1.

Hooking the whole thing up

All these devices share data across a bunch of wires called a bus. The width of a bus is the amount of bits that it can carry in parallel at once. So, a 16 bit bus can carry 16 bits at once.

 The C Language

C was created by Dennis M. Ritchie, in 1971 as the successor to the language `B'. The first dialect of C is now called `common C' or `classic C' and differs slightly from the new ANSI (American National Standards Institute) C standard which was adopted in 1983. C is a very fast and efficient yet flexible language often used for programs where speed and developer control are vital.  In 1973, the UNIX OS was written almost entirely in C and the language remains closely linked to this OS. The flexibility of C comes with a price since it does not enforce good style and type checking the way that other high level languages like Pascal, BASIC of Java.  This means that C is more error prone and more difficult to `debug'. Despite these drawbacks, C was the most widely used programming language during the past three decades and is only now losing favour to object oriented languages such as C++ and Java.

C forms the basis of its object oriented successor C++ which was created in 1991 Bjarne Stroustrup. Since C++ is very nearly a superset of C.