Fri, 6th Oct 2017, 00:28 programming
My students, I got some disturbing news from one of my TAs after the discussion session saying that several of you are completely lost when it comes to how to go about programming. ...and that, in fact, some of you don't know what some of the instructions do. I do not know yet how many of you fit into this category of "completely lost" but I want that number to drop to zero. Therefore, I am starting with this email. It is a long email, but if you are lost, I am hoping this will get you unlost. If you are okay with the program and do not need this, feel free to just disregard it. In any case, for those who need it, I hope this helps. What is a program and what does it do? ===================================== A computer executes programs, and a program is a sequence of instructions that direct the computer to carry out a sequence of instructions to solve a problem. In class, we looked at a problem: How can I get the computer to multiply two numbers A and B if the computer does not have a multiply instruction? Our task was to write a program to multiply two numbers. Again, a program is a sequence of instructions. When a computer processes each instruction, it changes the state of the computer. The state of the computer at the start of every instruction consists of all the values in memory and in registers, the contents of the PC, and the values of the condition codes (N,Z,P). As a result of executing an instruction, the computer is in a new state. The first instruction of the program takes the state of the computer before any instruction is executed and produces a new state. The second instruction takes the new state produced by the first instruction and produces a third state. The third instruction takes the third state and produces a fourth state. This continues until the computer stops, and the result is part of the final state. Your job is to figure out what you want the computer to do, instruction by instruction, to carry out the work that will solve the problem you have been given, by changing the state of the computer, one step at a time until the state contains the result. Let's back up for a moment, and consider an analogy. A program to cook deep-fried chicken strips. =========================================== Suppose someone gives you a large piece of chicken, some breading, and a pot containing hot oil cooking on the stove, and says: Give your younger brother instructions for making a dinner of deep fried chicken strips. The instructions you give your brother is the program. Your brother is the computer, carrying out these instructions. The beginning state is what the kitchen looks like right now: Hot oil cooking on the stove, a large piece of chicken on the table, a dish of breading on the table. Your first instruction to your brother: cut the large piece of chicken into n strips. Your brother does that, creating a new state: Hot oil cooking on the stove, n strips of chicken on the table, a dish of breading on the table. Your second instruction: take a strip of chicken, coat it with breading, and put it in the hot oil. Your brother does that, creating a new state: Hot oil with one strip of breaded chicken cooking in the oil, n-1 strips of chicken on the table, a dish of breading on the table. And so on. The point is that the program (your sequence of instructions to your brother) changes the state of your kitchen one step at a time until you end up with a plate of deep-fried chicken strips on the table, ready to be eaten. Again: each instruction starts with the state of your kitchen and produces a new state of your kitchen. Now back to the computer, and in particular the individual instructions. ======================================================================= Your job in writing a program is to figure out what sequence of instructions will step by step change the state of the computer until the computer stops, and the answer will be part of the final state of the computer. To do this, of course you need to know the new state that will result because of the execution of an instruction. And you will need to know this for all 15 LC-3 instructions, since you may need to use them to create the states that are necessary to end up with the final state containing the answer. Back to chicken: If you did not know what would happen if you asked your brother to cut up the chicken into n strips, there is no way you could get him, instruction by instruction, to produce the plate of fried chicken strips. So you need to be sure of what happens as a result of the computer executing each instruction. The computer program we wrote in class ====================================== We started with the initial state of the computer: The PC contains x3000, the registers contain values that we do not use, locations x3000 to x300A will contain the program you will write to multiply A and B. location x3008 contains A and location x3009 contains B, the two values to be multiplied. I said I wanted the first intruction to get x3008 into R1. Why did I want that? Because I knew I needed to get A into R2, and the simplest way to do that would be using LDR R2,R1,x0000 if I had x3008 in R1. I know that LEA calculates an address and loads that address into the register we specify. That calculation takes the PC and adds it to the SEXT offset of bits[8:0] of the instruction. Since the PC has been incremented to x3001 and since I want the result of executing the instruction to have x3008 in R1, I know the offset in the instruction must be x0007. After LEA R1,x0007 is executed, the new state is different from the initial state in that now R1 contains x3008. Now I can tell the computer to execute LDR R2,R1,x00. The computer takes the current state, which includes R1 containing x3008, adds zero to it, and loads the contents of that address (x3008) into R2. The new state is the same as the state before this instruction except now R2 contains A. And, the program continues, first changing the state to R3 containing B, next changing the state to have R4 contain x0000, and after that, instruction by instruction changing the state for continually adding A to R4 and subtracting 1 from R3, until the final state, when R4 contains AxB and R3 contains 0. One more point. ============== A successful program directs the computer from state to state (because of instruction to instruction) until the final state is reached. It is not enough to know the tasks that need to be done, one must also know the ORDER in which the state changes must occur. Take the chicken example. You did not tell your younger brother to first put the large piece of chicken into the hot oil, and then cut it into pieces. He could have ended up with third degree burns. Writing a program is all about knowing the sequence of instructions needed so as to change the state of the computer step by step until you get to the answer. Finally, ======= The job of writing a program is figuring out, step by step, what needs to be done (i.e., what instruction needs to execute next) to change the state of the computer until finally when the program ends, the answer is part of the state of the computer at that time. Sorry this was so long. Hope it helps. Good luck. Yale Patt