6.4   TOY Virtual Machine

This section under major construction.


. Suppose we are interested in designing a new machine or microprocessor. We could test it out by building a prototype machine and run various programs on it. A different approach would be to write a program on an existing machine that would simulate the behavior of the new machine. This has two main advantages. First it would be easy to extend the simulator to add extra flexibility, e.g., add debugging tools or experiment with a different ISA. Second, it is much cheaper than building a prototype for a new machine.

Designing a simulator can have other benefits. Suppose our TOY machine becomes obsolete by the more powerful NOTATOY machine. But, we have written thousands of programs in the TOY language and are reluctant to rewrite them for NOTATOY. Instead, we could build a simulator for the TOY machine on NOTATOY. Now, we can run all of our existing programs on NOTATOY by running them on our TOY simulator. As you might suspect, this extra layer of simulation will slow down our code somewhat. Many ancient programs are currently still running on today's computers, under several layers of simulation. For example, it is still possible to run the Apple IIe game Lode Runner under Microsoft Windows XP.

A TOY simulator in Java. Program TOY.java is a TOY simulator written in Java. It reads in a TOY program and simulates the behavior of the TOY machine. The Java program uses arrays to store the registers and main memory. It also stores the program counter. The Java program reads in the TOY program and alters the appropriate contents of registers, memory, and the program counter, in exactly the same way that the TOY machine would modify its registers, memory, and program counter. Any program written for the TOY machine could ultimately be used on the TOY simulator, and any program written for the TOY simulator could be used on the TOY machine, were it to be built.

The simulator needs two streams of input - one for the TOY program and one for TOY standard input. We associate the operating system's standard input with TOY's standard input, and read in the TOY program directly from a file. To do this, our program takes one command line argument to specify the name of the file. Then, we use the library In.java to read in data from the file, one line at a time. We use regular expressions to parse the input file. We discuss regular expressions in detail in Chapter 7. The program also uses to helper functions toHex and fromHex to convert from hexadecimal strings to integers and vice versa.

Java virtual machine. The Java compiler javac compiles your Java program into a machine language program for an imaginary machine known as the Java Virtual Machine Specification (JVM). This abstract machine has 229 opcodes, including add, divide, shift, XOR, load, and store. When you run java, you are simulating the behavior of the JVM on your computer.

Translators. It is possible to translate any particular TOY program into a Java program. That is, given a TOY program (e.g., insertion sort), write a corresponding Java program that does the same thing. This is analogous to translating a book from French into Spanish. Note that simulation is not the same as translation. A simulator mimics the behavior of the original machine exactly line-by-line, whereas a translator needs to generate code that produces the same output given the same input. In principle, it is also possible, but somewhat tedious, to translate a Java program into TOY.

Bootstrapping. We now consider a mind-bending idea with great practical significance. Since it is always possible to translate a Java program into TOY, let's translate our TOY simulator (written in Java) into a program written in the TOY language! That is, we create a TOY program that simulates the TOY machine itself. Now, we could modify the TOY simulator, e.g., to add debugging tools, or to simulate variants of the TOY machine. The resulting TOY simulator program is "more powerful" than the original TOY machine. This idea is called bootstrapping, where once we build one machine, we can use it to simulate "more powerful" machines. This fundamental idea is now used in the design of all new computers. According to Apple's web site "Seymour Cray, founder of Cray Research and father of several generations of supercomputers, heard that Apple had bought a Cray to simulate computer design. Cray was amused, remarking, Funny, I am using an Apple to simulate the Cray-3."


Duality between code and data.

Code = Print this. Data = Hello, World. Result = prints "Hello, World."

Code = Print this. Data = Print this. Result = prints "Print this."

Code = Print this twice. Data = Print this twice. Result = Print this twice. Print this twice.

Self-reproducing program! Duality and self-reproduction encoded in biology: gene = signifier, protein = signified.



Creative Exercises