This course introduces the broader discipline of computer science to people having basic familiarity with Java programming. It covers the second half of our book Computer Science: An Interdisciplinary Approach (the first half is covered in our Coursera course Computer Science: Programming with a Purpose, to be released in the fall of 2018). Our intent is to demystify computation and to build awareness about the substantial intellectual underpinnings and rich history of the field of computer science. First, we introduce classic algorithms along with scientific techniques for evaluating performance, in the context of modern applications. Next, we introduce classic theoretical models that allow us to address fundamental questions about computation, such as computability, universality, and intractability. We conclude with machine architecture (including machine-language programming and its relationship to coding in Java) and logic design (including a full CPU design built from the ground up). The course emphasizes the relationships between applications programming, the theory of computation, real computers, and the field's history and evolution, including the nature of the contributions of Boole, Shannon, Turing, von Neumann, and others.
Machine language programming
Loading...
Из курса от партнера Princeton University
Computer Science: Algorithms, Theory, and Machines
51 оценки
Из урока
A COMPUTING MACHINE
Every programmer needs understand the basic characteristics of the underlying computer processor being used. Fortunately, the fundamental design of computer processors has changed little since the 1960s. In this lecture, we provide insights into how your Java code actually gets its job done by introducing an imaginary computer that is similar to both the minicomputers of the 1960s and the microprocessor chips found in today's laptops and mobile devices.
Познакомьтесь с преподавателями
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Kevin WayneSenior Lecturer
Computer Science
Next I want to convince you that really you can do
much more than just adding two numbers even with TOY,
and with switches and lights.
So, the basic concept is,
that even the few instructions that we've given for TOY,
support the same basic programming constructs that Java does.
So we have primitive data types,
we've got the arithmetic operations and we've got the bitwise operations.
We have things like assignments,
statements and some math loading stuff in the registers and implementing things.
We have conditionals and loops and we'll talk about that.
We can do arrays,
that's what opcodes AMB are for and we'll talk about that in the next lecture.
We're going to talk about standard input and output in just a minute,
and we have advanced programming constructs as well.
We can do functions in libraries,
that's what opcodes E and F are about.
And there's plenty of discussion in the text,
in the book about that,
we're not taking the time to do it in lecture.
In linked structures as well.
In fact, in the book there's a TOY program that uses binary search trees
to do an input that with no limit on its length.
It's kind of amazing that you might think that you can
perform these kinds of functions with the very few instructions that we have.
But actually if you take the time to do it,
you'll see that really the TOY program for
binary search trees is in some ways easier to understand than the Java program.
And lots of these things are done with TOY programs that
only use 10 to 20 or 30 instructions.
Not very many instructions are all to do really a lot.
It's really quite amazing and it's worthwhile to take the time
to look at machine language programs that do familiar tasks,
and there's plenty of examples of this on the book side and in the book.
So, let's look at conditionals and loops to start.
So, there's instructions, a few instructions within TOY that change the value of the PC,
and that's how we control the flow of instruction execution.
We test the registers value and change the PC depending on the value.
So that's opcodes C and opcode D branch if zero,
and branch if positive.
So these instructions take a register and an address,
and they test that register and depending on the result,
they change the PC to that address.
So, just a really simple program that computes
the absolute value of the number in register A.
D A 12 so D is opcode branch if positive,
check if A is positive,
if it's positive then set the PC to memory location 12.
This instruction is at 10,
next instruction is 11 and then so 12 would be skipping the next instruction.
And what's the next instruction?
It's opcode 2 which is subtract,
and the operands are zero which is zero by convention and register A,
so it subtracts register A from zero.
So if it was negative that'll make it positive and then puts the result into register A.
So that's a two instruction program that computes the absolute value.
So that's a conditional.
And a typical loop works as follows.
Let's assume that register one has the value one in it,
the opcode C it's branch is zero,
and then we test the value of register A if it's zero,
we go to 15 that's branching out of the loop.
Then we have whatever our loop instructions might be
and then would have somewhere subtract instruction which says,
"Two is subtract, one has the value 0 0 1."
A's got some value subtract one from it and put
the result back in A that's decrementing register A by one.
And then after you do that,
do a branch if zero on register zero which always succeeds and sets the PC to 10.
So you can see that's how we can implement
a while loop that decrements register until zero.
Just those few instructions we can go ahead and implement the kinds
of constructs that we use all the time in a higher level languages like Java.
And we'll give the example of a program that does this in just a minute.
So that's the kind of Java-ish expression of the same code.
And I will try to document our programs like that without being
too persnickety about the correspondence.
And as we saw it when we first programmed in the second lecture once we got to loop,
we realized that all of a sudden that gives us the capability to do way,
way, way more than we could do without being able to control the flow.
That doesn't take much,
just a couple of TOY instructions to get us there.
But the other thing is as input and output.
It's one thing to implement a program with switches and lights,
but to input data with switches and lights,
people knew right away is just not going to work.
So one of the very first things that
happened and there are all the earliest computers was
to have some way to get data from the outside world into the machine.
And just to give an idea,
we're going to talk about paper tape,
and that's actually the method that I use for a couple of years.
And what they literally did was on the side of the machine they bolted
some I/O devices that could read and write a paper tape.
And we're going to talk about them in terms of standard in and
standard out that are familiar to you.
What is paper tape?
It would come in rolls or sometimes it would
come in what's called fan folded, it will be folded.
And it's paper and
we think of it as unbounded in length you could read as much as you want.
And it's got holes punched in it.
We encode our 16-bit words in two rows on the tape.
So this is a 16-bit word where the first eight bits are zero
then 0 0 1 1 and then 0 1 1 1.
And then there's little holes in the middle there
sprockets that are used to drive the tape through the tape reader.
So to write a word,
there's a little thing that can punch the holes and it would
just punch a hole corresponding to each one.
And to read a word,
basically the device would shine a light
behind the tape and then on the other side it would sense the holes,
and then it'd know what's supposed to be zero,
what's supposed to be one.
And That's it. Very simple device.
And how do we access this with a TOY program?
Well, what we're going to do is just connect this thing to memory location FF,
and so memory location FF is not really a memory location.
If you store something to memory location FF instead of storing that in the memory,
it would activate the paper tape punch to punch
the holes corresponding to the values of the word that you said you'd store.
And to read, you'd do the same thing.
When you load from FF,
then the device that would be a signal to
device not to go ahead and read a word and provide that,
put that in as if it was came from memory.
Very simple device, and actually the paper tape hardware itself is not really significant
with because very quickly that was replaced by
magnetic tape which could hold way way more data and go a lot faster.
But from the point of view of the programs no change at all.
It's like standard input and standard output.
I think of the input stream and the output stream is infinite.
Within my program I don't have any bound I just write FF or just read from FF.
So, that changes quite a bit what we can do with TOY programs,
and we'll talk about the impact of this in the next lecture.
But just as an example,
let's look at this is a real program
that illustrates the flow of control in standard output.
So what this program does is print on paper tape the Fibonacci numbers.
And it's kind of a TOY example although,
I have to say with early computers,
you have to imagine doing the stuff with pencil and paper,
and the excitement of being able to actually compute things that you didn't know.
Like really large Fibonacci numbers or other basic mathematical properties of integers,
people were very excited to write programs like this and be able
to learn things really about math.
And so lots of the early programs were of this form.
But if you want, you can think well this is scientific data of
some kind that is going onto the paper tape for later processing.
And certainly, there was quite a bit of that as well.
But let's look at the example.
Just I think you'll see after this example,
there's lots of things you could do with this computer.
This is just a 13 instructions to get this job done.
So let's look at what it does.
So our convention is to put the value one in register one,
and I haven't talked about instruction seven that's a load address instruction.
And what that does is take the value of the address and put it in
the register and then clear out the upper bits of the register with zero.
So that's a quick way to get a value into a register.
And then we start out with our register A and register B and we set them to one
and then register nine is going to get the location of whatever's in memory location 4C.
If you look down at 4C it's got the value A.
So that's data for this program it says,
"We want to punch out 10 Fibonacci numbers."
And we're just putting 10 for this example we could
put a of course a much larger number if we wanted.
So that's going to be a counter for our loop that's in.
And register nine is our index for
our loop or that corresponds to i in the pseudo code right.
So now we test if i is zero or register nine is zero.
This is our while loop construct.
C means branches zero,
nine means register nine and then 4B is down at the halt instruction.
So this is going to be our loop.
It's not zero of course,
and now it says,
"Just write register A standard out.
"That's just 9 A F F and we execute that.
We punch out a one.
Now, Fibonacci numbers.
So, it's A and B are the two previous.
So, we add them,
put the result in C,
and then, move B to A and C to B.
Those are going to be our two previous,
they we'll always keep track of.
And then, decrement register 9.
And now, we'll just show what happens every time through the loop.
We go on and decrement register 9,
and C is the sum of the two previous.
And then, we update the two previous.
So, very simple program,
and again, we could make that a hundred,
or a thousand, or all the way up to 32,000 things that we could punch out.
And it could be a much more complicated number than the Fibonacci.
And then, finally we come to the halt instruction.
So with that sample program,
and the slide which is called the TOY reference card,
you can already, I'm sure,
imagine writing code to solve many,
many of the computational problems that we addressed early on in Java.
If it involves slow of control,
and it falls integer bitwise operations,
there's really a lot you can do.
You'll find plenty of examples in the book.
And the other thing to remember about this card is,
that it is a complete specification of what happens in the computer.
Any 16 bit of value can be decoded using this card,
and the pseudo-code in blue on the right,
it specifies exactly what TOY will do if you get that instruction.
I will describe a few more in the next lecture,
and they're all described with examples on the book site, and in the book.
But this is a complete description of what goes on in TOY.
And real computers, for many years had programmers carry
these cards in their pocket as
a full description of what you needed to know while programming.
Sometimes, the cards got really quite detailed.
There were computers that had 256 instructions of the card folder,
and there was lots and lots of information on it.
But that's something that every programmer had to know,
and had to have quick reference to when they looked at what's in the memory.
They had to know exactly what the computer would
do if it happened to interpret that thing as an instruction.
Or when you're crafting a program,
this is what you have to work with.
It's your manual. So TOY programming is interesting intellectual challenge,
and I encourage everybody to learn more about it.
And so, the kind of thing though,
that you have to know to be sure that you really understand what's going on,
you have to be able to answer questions of this sort.
So, I give you a 16 bit number.
What is that number if it's interpreted as a TOY instruction?
Or as a two's compliment integer value for all different kinds of numbers.
So, while 1A75, that's easy,1 is add instruction,
A is the result.
We're going to add register 7 and 5, put the result in A.
Two's complement integer value.
Well, that's a 1, it's positive.
So, we can use hex to do it if
1 times 16 cube plus 10 times 16 squared plus 7 times 16 plus 5.
And actually, this kind of conversion is an easy programming exercise.
And in the book and the book site,
you can see a general purpose program for doing
these kinds of conversions where you could write a TOY program to do it even.
So, what about 0FFF?
Well, the card says if the initial four bits are zero,
that's a halt instruction.
And that's it, rest of it's ignore.
What about as a two's compliment?
Well, it's easy way to compute that is,
if you have 1,000,
that's 16 cube and subtract 1,16 cube 4,096 subract 1 and get 4,095.
8888, well, 8 is load instruction.
Next, 8 means register 8,
and 88 means memory location 88.
And as a two's complement integer value.
Well, you can do it by converting to binary and so forth, reverting back.
But actually, the idea of flipping all the bits and adding 1 works in any number system.
And so actually, you get this by subtracting all from 15 and then adding 1,
1 less than the base.
So these types of questions,
short answer question that you might find on a quiz or exam on this material.
You want to be able to know what every 16 bit value means as a TOY instruction,
or as a data value.
So, just as a trick,
how do you flip all the bits in a TOY register?
Well, if you XOR with all ones then,
XOR with the 1 flips bits,
and that's kind of programming trick that every programmer knows.
Everybody who programs at this level knows.
And then, you should be able to figure out what small programs do.
And that might seem amazing to you but this programming model is really simple.
It's much simpler than Java,
and it won't take you long to figure out.
Just by studying this program,
just by the examples that we've seen,
that what this thing does is go through a loop 10 times,
doubling the value in register 2,
and that so, it computes 1024.
So, that's another type of question that anybody can answer after seeing this lecture.
So, how does TOY really relate to your actual computer?
They're totally different computing machines,
but they both implement basic data types,
conditionals, loops, and other low level constructs.
They both can have functions,
arrays, and other high level constructs.
They both have infinite input and output streams.
Really, the whole programming model that we talked about for Java,
TOY implements just as well as your laptop does.
You might say well, but 256 words,
is that really enough to do anything useful at all?
It's such a small computer.
And again, we keep it small to keep the scope small that you
can understand what goes on inside the computer,
and actually, we'll talk next time that absolutely 256 words is enough.
In fact, all our sample programs and books should cover a big range,
all fit in the same memory.
And we'll talk more about this next time.
And then, if you seen the theory lectures or when you see the Turing lectures,
you'll know that actually,
if you just change the I/O device to both read and write, which you can do,
it's nothing about the machine that says that,
then TOY becomes a Turing machine.
It means you can compute anything that any computer can compute.
So, TOY is a very strong sense equivalent to your laptop.
And really, all the computers that have been
developed in the last 50 years have all of these same characteristics.
It's really, really quite amazing phenomenon.
Now, yes, we want a faster one,
and we want more memory when we can afford it.
And that's another aspect of the history of computing,
is that that's always true.
You want a faster laptop with more memory.
People wanted that with TOY and the last 50 years
have been a continuous development of providing that.
But what the computer does basically, not much change.
That's what we're going to look at more next time.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
