CSCI1300 Notes 1. A Semi-Historical Look at How Computers Work
Purpose: Understand some of the basics of how computer programs work.
Bits
Computer memory is made up of a large number of electronic gizmos called bits, each of which can hold a zero or a one, as you've thought about for Notes 0. A bit can be many different kinds of physical structures, for example tiny circuits that have currents flowing in them one way (representing a zero) or another way (representing a one), or little patches of magnetic material that can be magnetized two different ways, or whatever. Makes no difference except to the speed and possibly the reliability of the memory.
Here is a picture of core memory
for an old machine, from http://ed-thelen.org/comp-hist/BRL61-0625.jpg
... the name is still with us, though the technology, tiny donuts of magnetic
material, called cores, strung on a
grid of wires, is long gone.
Groups of bits are used to contain numbers and other information in the computer. We'll call a group of bits that's used to hold information an information holder. A more commonly used, but not as clear, term is variable.
A group of n bits can hold 2 to the power n different values. Can you see why?
The bits in an information holder are used in different ways depending on the form of information to be stored. Thus the bits are used differently to hold whole numbers, like 3 or -23, from the way they are used to hold numbers with decimal parts, like 3.4 or -124.675. They are used differently again to hold characters, like 'a' or '%'.
An Antique Computer
In this section I’m going to describe the parts and operation of a primitive computer. This example will be simple, but it will illustrate very well the basic principles of operation of every computer. Let’s call the computer FIDO (after my dog). FIDO is very loosely based on one of the first computers I programmed, the Lincoln Labs/MIT TX0, the first transistorized computer. (Yes, I’m that old, though when I worked on it, in1967-68, it was far from brand new. My boss, the late Paul Kolers, couldn’t afford to buy computer time on anything up to date.)
Here’s a picture of the TX0, from http://www.computerhistory.org/timeline/timeline.php?timeline_year=1956
, image courtesy of the
Here’s a bigger, but BW, picture from http://ed-thelen.org/comp-hist/BRL61-l.html#LINCOLN-TX-0 :
FIDO’s memory consists of 1000 groups of 12 bits. (The TX0 had 64K of 18 bit words.) Each of these groups has a number, from 0 to 999, called its address. As you’ll see, FIDO can use the address of a group to operate on the group.
The first three groups in FIDO’s memory have special features. The groups with addresses 0 and 1 each have 12 toggle switches attached to them, one for each bit. Using these switches you can put any values you want into these two groups. (No joke; the TX0 had this convenient if primitive feature.) The bits in the group with address 2 each have a little lamp attached to them. This lets you see what value is in that group at any time, by looking at the lamps: a lamp is on when its bit is 1, and off when it’s 0.
FIDO has two other groups of 12 bits, called the accumulator and the program counter.
FIDO’s circuits can execute any of 6 instructions, each of which has a numeric operation code (or opcode). Here are the instructions:
Clear accumulator.Opcode 0. Set all the bits in the accumulator to 0. Then add 1 to the program counter.
Add. Opcode 1. This opcode must be immediately followed by a number between 0 and 999, that is, an address. It adds the value of the group with that address to whatever value is in the accumulator. Then adds 2 to the program counter.
Subtract. Opcode 2. Just like add, only it subtracts rather than adds, and then adds 2 to the program counter.
Store accumulator: Opcode 3. Must be followed immediately by an address. Copies the value of accumulator into the group with that address, then adds 2 to the program counter.
Jump. Opcode 4. This also has to be followed by an address. Copy the address into the program counter.
Conditional jump. Opcode 5. This also has be followed by an address. If the accumulator is 0 it acts just like Jump. Otherwise it adds 2 to the program counter.
FIDO has a start button. When you press it, the value 3 is placed in the program counter, and FIDO starts executing. This means it goes through the following cycle:
Look at the group whose address is in the program counter.
If this group does not contain a valid opcode, stop.
If the group does contain a valid opcode, do the indicated operation.
Repeat. Note that the program counter will have been changed.
To program FIDO, we place opcodes and addresses into its memory, in such a way that the sequence of operations we want will be carried out when we press the start button. (We haven’t said how we would get these things into FIDO’s memory. Just assume for now there is a way.)
FIDO is capable of doing quite a bit. Just a few improvements would make it able to do pretty much anything a real computer can do.
Here’s an example program, that lets us put numbers into groups 0 and 1 and shows their sum in the lamps attached to group 2:
At address 3 we put: 0
Address 4: 1
Address 5: 0
Address 6: 1
Address 7: 1
Address 8: 3
Address 9: 2
Address 10: 99
To run this program, we use the toggle switches to put numbers into groups 0 and 1. Let’s say we toggle 2 into group 0 and 3 into group 1. Then we press start. FIDO starts executing instructions, beginning with the group with address 3 (that’s the address that’s put into the program counter when we hit start.) The opcode 0 tells FIDO to put 0 in the accumulator, and to increase the program counter to 4. The opcode there is 1, and it’s followed by the address 0, so the value of group 0 is copied into the accumulator, making the accumulator be 2. The program counter is increased to 6. There the opcode 1 is followed by the address 1, so we add the value of group 1 to what’s in the accumulator, making the accumulator 5. The program counter is increased to 8. The opcode there is 3, for store, and it’s followed by the address 2. So we copy the 5 from the accumulator into group 2. That makes the little lamps light up so we can see the answer. (Actually, the lamps were already lit in some pattern indicating whatever value happened to be left over in group 2, but now we know they are showing our answer.) The program counter is increased to 10. Now the opcode is 99, which is not valid, and FIDO stops.
Paul Kolesnikoff, a CSCI1300 student from summer, 2003, has provided a FIDO emulator on the Web, here. An emulator is a program that reads the opcodes of some computer that it “emulates” and does what the opcodes say to do. You can use Paul’s emulator to try out FIDO programs to see what they do.
Paul's emulator does not have a start button. Instead, you use two buttons, one that resets the program counter and one called "single step" that makes the emulator execute just one step. So to run a program you press the reset program counter button, which puts 3 in the program counter, and then you press the single step button over and over until you get tired or the program halts.
Use Paul’s emulator to try out the above program. As a convenience, if you press the Adder button under Examples in Paul's emulator it will load this example program into memory. Reset the program counter (if you need to) and then step through the program, being sure you understand what is happening. Then work on the exercise at the end of these notes. Come back later and read the rest of this.
You can see from this example, and from those in the exercise, that programming FIDO is a bear. This kind of programming has a name, absolute machine language programming, and every now and then you may find it useful to be able to do it for some machine. If you think about it, it’s very simple and concrete, just incredibly tedious and error prone.
After some years of programming this way, people started to find ways to simplify the programming process, and in fact to use the computer itself to help produce programs. The first big help was a program called an assembler. An assembler was (and is, you can learn to use one in a later course) a program that lets you use meaningful abbreviations for opcodes, called mnemonics, and addresses. An assembler would let you say something (roughly) like this:
Name group 0 input1
Name group 1 input2
Name group 2 output
CLA (a mnemonic for clear accumulator)
ADD input1
ADD input2
STO output
HALT
This assembler would translate all this into the corresponding opcodes and addresses, keeping track of where in memory each opcode should be put, and another program called a loader would put the opcodes and addresses into memory at the right places so that the program could be run.
Much better than having to write the opcodes and addresses yourself, though still pretty fiddly.
You may wonder how an assembler could possibly work on FIDO, since I haven’t said how FIDO could represent the letters that make up a program. Well, here’s how: each letter is represented by a number, and we just have to get the right sequence of numbers, representing our program, into FIDO’s memory, along with the assembler program itself, so the assembler can examine the letters in our program and translate it. To do this we could use a keyboard: when we press a key with a letter on it, the keyboard puts the corresponding number, called the character code, somewhere in FIDO’s memory, say in group 999. When we let up the key, some number we don’t use for any character code, say 0, appears in group 999. A program called an editor, which we load into FIDO as well, does the work of copying the character codes that the keyboard sticks into group 999 into consecutive groups in memory, somewhere where the assembler program expects to find them. The editor makes sure that group 999 changes to 0, indicating the key has been released, before it copies the next character code.
Do not worry if this account does not make complete sense. My purpose is just to convey to you that what happens when you use a computer is that a lot of individually very simple things happen, that together produce a complicated and useful result, like translating abbreviations into opcodes. And all of the things we’re talking about happening inside FIDO correspond to the things that happen inside your PC, or inside any computer.
Around 1957 a big breakthrough occurred. Various computer folks at IBM, at MIT, in the Navy (in a group headed by later admiral Grace Hopper) figured out that if a program could translate abbreviations into opcodes, a more complex program could translate more complex notations too. In a higher level language, of which C is an example, you write your program in a notation that includes fairly meaningful words, like IF and THEN, and mathematical expressions like foo+bar/3. A program called a compiler translates this notation into opcodes. ( The words “assemble” and “compile” were used to describe the process of putting together a collection of opcodes by hand, and these terms were carried over to describe the automated versions of these processes.) The name of one of the earliest higher level language, one that’s still in use today, is FORTRAN, which abbreviates FORMULA TRANSLATOR. That says pretty well what higher level languages are about.
End of historical interlude… now we return to the present, where you won’t be thinking of the machine, and its opcodes, but rather what notation the compiler is able to translate. You don’t really care, for most purposes, what opcodes it produces; you just assume they will be the right ones to represent your program.
But before we leave the past entirely, look back at that assembler example. Notice that it contains two kinds of lines. A line like “name group 0 input1” doesn’t generate any opcodes; it just tells the assembler something, in this case, that when you say “input1” you mean group 0. A line like “ADD input1” does generate an opcode (and an address to go with it.) It makes something happen when your program runs.
You’ll see the same distinction in your C programs, when we start on those. Some parts of your program just provide information the compiler needs to understand what you are writing, like how you will use a name. These are called declarations. Other parts, called executable statements, describe things you want to have happen when your program runs. Keeping track of this distinction will help you understand C more clearly.
Exercise 1-0. Write a FIDO program that subtracts the
number in group 1 from the one in group 0 rather than adding them. Use the Kolesnikoff
emulator to test out your program. This is a warmup
problem; you’ll see that Paul has included a solution to this as an example in
the emulator, so if you get stuck you can examine his solution. You do not need
to turn in your solution.
Exercise
1-1. Write a FIDO program
that swaps the values in addresses 0 and 1. For example, if group 0 contains 13
and group 1 contains 7, when your program finishes group 0 should contain 7 and
group 1 should contain 13.
What to turn in.
Type up your solution to Exercise 1-1, and send your work to clayton@cs.colorado.edu. Be absolutely sure you write CSCI1300 at the beginning of the subject line, with the first four letters in caps.
I encourage you to work with other students on this and other exercises, BUT I need an email submission from each person individually.
On your submission, include the following information, with the blanks filled in: “I started work on this assignment on ___(date), and I have spent ___ hours outside of class working on this. I also spent ___ hours working on _______, which is related to the course, since my last submission.”
Optional Exercises: Work on these if you are interested and have time.
1-O1. Write a FIDO program that multiplies two numbers. Hint: use repeated addition, using the jump and conditional jump instructions we haven’t used yet in our discussion of FIDO.
1-O2. If FIDO adds two 12 bit numbers, the answer may take more than 12 bits to represent. This is called an overflow. As defined, FIDO has no way to tell if this happens. Real computers have a special bit, called an overflow flag, that is set by an add operation to be 1 if an overflow happens and 0 if it does not. They also have an operation something like “jump on overflow” which jumps if the flag is 1 and does not if it is 0. Outline how you could use these features to write a program for FIDO that could add numbers bigger than 12 bits. (This is one of the things real computers have that FIDO does not.)
1-O3. The collection of operations a computer can carry out is called its instruction set. Do some research in the library or on the web and find the instruction set of one or more real computers. Describe one or more features these computers have that FIDO does not.
1-O4. Suppose we add opcodes 6 and 7, BOOP and BEEP, to FIDO. These make distinctive tones in a speaker, and add 1 to the program counter. A sequence like 6 7 6 7 6 7 will make an interesting sound, and you want to be able to make this sound happen at various places in a larger program. Of course you could put in the 6’s and 7’s in each place where you want the sound, but that seems wasteful of space. Can you think of a way to have 6 7 6 7 6 7 in just one place in memory, and yet execute it in several places in a larger program? If so, you will have invented the subroutine, or subprogram. Hint: it’s easy to put in a JUMP to the right place in memory, but how are you going to get back to carry on with the larger program when the 6’s and 7’s finish? Modern computers have special fancy instructions for doing this, but FIDO does not. Solutions are possible, though… can you find one? Hint: FIDO programs can modify themselves, for example by filling in where a JUMP will jump to.
1-O5. If by any chance you already can program in some language, write an emulator for FIDO. An emulator is a program that can read a FIDO program and do what it says. (Even though Paul Kolesnikoff has supplied a ready-built emulator you can use, you may find it interesting to write your own.)