Next let's talk about simulation which is a key concept in this room. Students asks this question all the time, is TOY real? Is there a real TOY machine? Well, how do you think we're debugged our TOY programs? We wrote a java program that simulates toy that takes the actions that we expect the TOY machine to make. And the thing is and as you're going to see in a minute, you could write a TOY simulator. It's actually, TOY is a simple machine, this is a simple program actually quite easy compared to other programs for other applications that maybe you've written. And in fact that's the way we designed TOY, was to take this Java code and continue refining it. You may find older versions of TOYs related to this core around, there's all kinds of possibilities but we just worked with this Java code. And this is just to indicate that actually nowadays all computers are designed in this way. People write simulators for the new computer before actually building the computer, and it brings up some interesting questions. So, you have a system like Android or IRS is that you consider that to be real? There's a billion Android devices out there. So, IoS similar and other systems, do you consider those devices to be real? There's no TOY devices out there. But on the other hand, you say well what about Java, is that real? Well, the android runs Java, we can run our TOY simulator on Android. So, there's a billion TOY devices out there. So TOY is every bit as real as Java or Android, and that's quite a provocative question and we'll just delve a little more into right now. First let's take a look at this Java program to simulate TOY. What we're going to do is take the program, the toy program from a file named in the command line, and then use Java standard in a standard out for TOYs standard and standard out. So, here's an example where we haveTOY code to add the integers on standard in. And all this code has to be loaded at x location 16 10 memory location 16. So that's the code, TOY code. And then if there's data this is maybe the contents of the paper tape, then if we invoke our simulator toward that Java or the Baykal is called TOY, then the first argument is the program and then the pipe take our input from data.text. This command will cause the simulator to simulate the operation I programmed which is to add the numbers on data.text, and then the resulted add goes to standard output. And it's the sum of those numbers 00f7. So let's take a look at what this code looks like. So, we're going to start at x location 10, and we have a variable called PC which is our program counter. Then we need 16 high registers for TOY, we'll just represent them in an array of size 16 called R and Java, and same for memory, we'll have an array of size 256 which will be the main memory. Then we use an input stream to read from the file that specified as the first argument, and we'll just stay in a for loop as long as the input string is not empty and we're less than location FF. We'll just load the memory with the integer that's found on the input string. Now we use parsing the way we usually do, in this case, we have a second argument to parse in which just says that we're expecting the number there to be base 16. And that's all built into Java to change from those strings that we use to represent X numbers into integers and that's what we store in the memory. And then what the simulator does is stay in a loop to read the next location. PC gives the address and the memory of the next instruction. We load that into the instruction register IR which is just the Java variable, and then increment the PC. And then in the next two slides, we look at the main function of the simulator which is to decode the instruction and then execute it, and we'll look at those in the next two slides. And that's the general structure of our program to simulate the TOY machine, and we'll look at all the code next. So, first thing is decoding, this is kind of how scheme, people call a bitwacking because we're tearing apart the instruction to look at different segments of it and extract those fields so that we can use them for later processing. There's a simple technique called shift and mask that works the same way in Java as it does in the machine language instructions for bitwise handing slips of boring and so forth. And after a few examples and you can read more detail in the book. So say we want to extract the destination register d from one 1CAB. So, that's what the instruction register looks like, we're just looking at the right 16 bits. What we do is shift that right eight positions, so now the bits that we're interested in are the right most for bits. Then we take the literal f 0 x f which is for once, and then we just AND that against the result of shifting the instruction register right. And 0 positions are all zero no matter what was in there, and then the one positions just copy the bits below the mask so that gives us our result which is the destination register C. So, the result of that Bitwise AND of the data and the mask is zero where the mass was zero and the data bit were mask is one. And that's a basic technique that we can use to get all the information that we want. So, after we fetch an increment, the instruction into the instruction register, then we can get the opcode by shifting right 12 and the ending with 0xF, we get the destination register that's the example that we just did. We can get the source register by going four bits and then the other source by not shifting it all just masking off the four rightmost bits. And then if it's an instruction that uses an address, we need eight bits so we mask it with zero 0xFF. And we compute all these things some of the instructions we'll use S and T some other instruction we use other, but we might as well compute them all. So that's the decode calculation that's bitwacking and TOY instruction to get the information that we need to simulate its operation. And then there's the execution. So, execution is the JAVA switch statement. Each instruction dictates simple state changes that's what the toy machine is, and all we have to do is change the values of the registers or the memory as dictated by the instruction. So if the opcode is zero, then we just break out of our loop, but otherwise we use the opcode in their cases for each value or the opcode. So, if case 1 it's an add instruction and that means our RD gets our vest plus RF [t] and so forth for all the arithmetic instructions. In fact, these cases look very much like the documentation the programmers card for the TOY machine. So that's a shift left that's a shift right, load address just set R [d] equals addr. And that's a store load instruction and a store instruction indirect load and store and then the branch instructions. The branch instructions might involve testing the value of a register and might involve changing the value of the PC. There's the case 14 and 15 instruction TANF, are about implementing functions where we can jump to an address given in a register and we can save the current address in the register, and you can read in the book about how to use those. And that's it. That's the state changes that are dictated by the definition of what the TOY machine's supposed to do. So that's the complete simulator putting together the code. There's the load part, load the program and then there's stay in a loop, there's the fetching command, there's the decode and there's the execute of the entire simulator fits on one slide, and in fact that was our main design goal for TOY, was to get the simulator to fit on a slide for this lecture. Now actually there's a few things that we emitted so, R [0] equals zero we have to put in a standard in, a standard out. We didn't put in this code. You need to check if the addr is FF and then go ahead and read from standard in or standard out if that's the case. There's some places where we didn't take care in this code where we have to do some casting and other things because TOY is 16 bit and Java is 32 bit. And we need a more flexible input format because sometimes, we want to load programs elsewhere in the memory. So you can see the full implementation TOY.java on the booksite. But this one here is fine for a lot of purposes. It runs any TOY program. It behaves exactly, precisely, as if TOY would. In fact, it is TOY. So, if we give the read-array program and then we give eves-tape, then we're going to get in an infinite loop just as if TOY would. And the really important thing to think about it is, if you want to design in other computer, all you have to do is change this program. Very easy to change the design. So, we really have three registers, so we had one register in memory. Which instructions do we want to include? You can design any kind of computer you want with a simple program like this. And by the way, we don't have a TOY machine but we developed lots of TOY code using this on another machine. So with our simulator, we can develop code for TOY even though TOY itself doesn't really exist. In fact, this program is so simple you could actually implement this program in TOY. So you could simulate TOY on itself. And that seems a little crazy but that's what people do with real computers. You write a program that simulates the next computer on this one. Here's another program that simulates the TOY machine. It's a graphical simulator so it includes all kinds of aides to program development, gives a full display of the state of the machine. It allows you to single step through programs. Lots of other features like that. There's a large number of simple programs included as part of the simulator. You can think of that as a paper tape library. And I was a student of this course that wrote it and you can go ahead and develop TOY software to whatever extent you want on this simulator. In a sense, the simulator is better than the actual machine because we can put all these programmed development tools in the simulator that don't exist on the real machine. And that's the approach that's used for all new systems nowadays. We build a software simulator in development environment and we use that to develop and test software for the actual machine. It's only when we're satisfied that the software for the actual machine is going to behave well and we know that by exercising it extensively on the simulator that we actually build and sell the hardware. So important concept to think about, and again, all enabled by the idea of a normal machine. Then that brings us to the idea of backward compatibility. So any point in history would say that we're working along fine on an old computer but we know that there's faster technology out there. So it's time to build a new computer. So what do we do about the old software? Well, one idea is to just rewrite it all for the new computer. But that can be very costly and time consuming and error prone and also nobody wants to do it. So instead, what people virtually always do is write a program that simulates the old computer on the new one. It's not very difficult to do that. In fact, usually, you already have a simulator that's very similar and so it's not a one-pager, it's a three-pager or something, a small program, but it's going to be actually more efficient than the old computer probably because it's only adding a little bit of overhead and it enables the use of all the old software. So it's a very powerful idea. As we can progress to a new computer, use the old software, still be a little bit faster. And then we can pick and choose which new software we want to develop. But as the decades roll on, so for example, in the 1980s, you had to buy a piece of hardware to play PacMan. And people still kind of enjoy the idea of owning one of these pieces of hardware. But even by the 2000s, you could run it on a laptop. And certainly, there's a simulator of PacMan on your mobile device. It's not new software. They're just running the old software in a simulator on whatever device. So the old software remains available and doesn't go away at all. Well, there is an idea though that is a little bit disturbing. It's actually, does anyone know how that old software actually works? It was developed under pretty severe conditions, small machines, not much memory, maybe written in machine language. And maybe, it's actually running through several layers of simulators. Maybe the mobile devices simulator is simulating a laptop and the laptop is simulating the machine. So, actually knowing how the old software works becomes more and more of an issue as it ages. Here's an urban legend about this, probably not true but it tells the story. So there was the rocket booster for the space shuttle. It needed to be transported by rail. So now, US railroads were built by English expats. And so, the standard rail gauge in the US is what it was in England, four feet, eight and a half inches. And that was chosen to match the ruts on the old country roads in England. And well, those ruts were made by Roman war chariots. And so, what was the distance between the wheels on Roman war chariots? It was determined by the width of a horse's back end. So, the end result is that this dimension of the space shuttle rocket was determined by the width of a war horse's back end. And the point of the story is that maybe backwards compatibility is not necessarily always a good thing. And there's a lot of software out there that seems to sometimes have this kind of characteristic. So, even broadcast TV has to be backward compatible, even though everything's digital now. It would be backwards compatible with the analog black and white. Lots of business software is written in COBOL which is a dead language. Nobody writes new programs in COBOL anymore but it's simulated by many, many layers of simulation. And people use it and there's no way of understanding it. Around the turn of the century, the Y2K problem was a big concern because there was no way to fix the software to know that the 00 was going to be year 2000, and that's going to be a later year than 99 which was 1999. Airline scheduling, that software was written in the 70's and is used over many layers of emulation, and it's hard to be confident that anybody really knows how it works. Documents, everybody's experienced this. You need sometimes an old version of document processing software to read a file that someone gave you. In web pages, real nightmare of web development is trying to maintain compatibility with all versions of all different browsers. And don't forget, the iPhone software as we've noticed is an unsafe language, but now it's done that way. And then, has new devices have to maintain compatibility with that unsafety. Really the sobering thought is that a great deal of our computational infrastructure was built in the 70's or 60's, 70's, 80's. Really a lot in the 70's, machines were not a lot different from TOY. So, maybe it's time to design and build something new for today's world. Computers, and software, and program environments that you have are way superior to the environments that we used to build the software that we use. And that means you know enough now to go out and do it. So, taking this to another level, let's look at the idea of virtual machines. So, nowadays, when people build anything, they simulate it to test it. And so, it's an issue that the simulation has to be really good. It might not reflect reality, and it might be too expensive, but it's not as expensive as the rocket blowing up. But for a computer, there's all kinds of advantages to simulation. First of all, the simulation is the definition of the new machine. The simulator is built when the hardware is built. It's tested against the simulator. The simulator is reality. And the other thing is the time-consuming difficult to engineer all the physical processes needed to create a computer. In the meantime, software can be developed using the simulator. And the other thing is we can simulate the machines that may never be built like TOY. It's a fine example, and there's lots of examples in today's world. So, for example, nowadays, most programming system use what's called virtual memory. Programs have the ability to address a huge amount of memory way more than can ever exist in a real machine, and the operating keeps track of mapping the memory that the program addresses to the real memory of the computer. And that's an idea called virtual memory that's been around for a long time, and it's quite useful as it makes programming a lot easier. Java Virtual Machine is another example. That's not a real machine, but simulators for that machine run on all and thousands and thousands of real devices, and it means quite a bit of software can be built on top of that without having to worry about the detail of all those devices. Then there's a thing called the cloud. Initially, the Amazon cloud, but now there's many out there. Well, there's a virtual machines of all different types that are available for use on the Web. All you need is a credit card number, and you can call up a virtual machine that will run your software of any configuration that you want. In fact, Internet commerce, and actually lots of software development is just moving to machines like this. If you're forming a startup, just use a virtual machine that's probably going to perform better than a real machine that you'd be able to afford. Just a decade ago, the big effort in forming a startup was getting the computer center going and getting it to compute whatever you needed, whatever you were selling. Whether it's photo processing, or messaging, or whatever else. Nowadays, startups don't need to do that. They just use virtual machines that are never going to exist. Computing is a utility like electricity using virtual machines. So, the whole idea is the idea of layers of abstraction, and we see that over and over again in computing, where we get something that we understand and we build something else on top of it. It's an extremely powerful idea. And again, TOY is real to the extent that your computer is real. If you're approaching a new problem, one good way to think about it is to create a language or a machine to help you express solution. Whether or not you actually build the machine, is an entirely separate issue. Maybe you can just run a simulator for that machine on some real machine. It's quite a powerful idea. All enabled by the idea of a von Neumann machine, and it's really opened up the opportunities that we still have before us today. So, I just want to finish by reminding people about Turing and von Neumann. In the theory lectures, we talk about Turing's theorem which says that you can have a single machine that can do any computable task. The idea was that this concept called Turing machine, a virtual machine, that is a way of encoding any task that we can do with computer. And then, we can have a particular virtual machine called the universal Turing machine that can simulate any Turing machine. And the whole concept of making this proof work, is the idea of a program as data. And von Neumann, very soon after creating the idea of a computer design that's got all the characteristics of computers that we're used to, and as a physical realization of the program as data concept. These two ideas together show us that the idea of a program as data has always stood at the foundation of computer science, and will continue to do so for some time to come.
