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