The Elements of Computing Systems: Building a Modern Computer from First Principles (26 page)
Read The Elements of Computing Systems: Building a Modern Computer from First Principles Online
Authors: Noam Nisan,Shimon Schocken
BOOK: The Elements of Computing Systems: Building a Modern Computer from First Principles
6.49Mb size Format: txt, pdf, ePub
Function Calling Commands
(In this list of commands,
function Name
is a symbol and
nLocals
and
nArgs
are non-negative integers.)
7.2.5 Program Elements in the Jack-VM-Hack Platformfunction Name
is a symbol and
nLocals
and
nArgs
are non-negative integers.)
We end the first part of the VM specification with a top-down view of all the program elements that emerge from the full compilation of a typical high-level program. At the top of figure 7.8 we see a Jack program, consisting of two classes (Jack, a simple Java-like language, is described in chapter 9). Each Jack class consists of one or more methods. When the Jack compiler is applied to a directory that includes n class files, it produces n VM files (in the same directory). Each Jack method xxx within a class Yyy is translated into one
VM
function
called Yyy.xxx within the corresponding VM file.
VM
function
called Yyy.xxx within the corresponding VM file.
Figure 7.8 Program elements in the Jack-VM-Hack platform.
Next, the figure shows how the
VM translator
can be applied to the directory in which the VM files reside, generating a single assembly program. This assembly program does two main things. First, it emulates the virtual memory segments of each VM function and file, as well as the implicit stack. Second, it effects the VM commands on the target platform. This is done by manipulating the emulated VM data structures using machine language instructions—those translated from the VM commands. If all works well, that is, if the compiler and the VM translator and the assembler are implemented correctly, the target platform will end up effecting the behavior mandated by the original Jack program.
7.2.6 VM Programming ExamplesVM translator
can be applied to the directory in which the VM files reside, generating a single assembly program. This assembly program does two main things. First, it emulates the virtual memory segments of each VM function and file, as well as the implicit stack. Second, it effects the VM commands on the target platform. This is done by manipulating the emulated VM data structures using machine language instructions—those translated from the VM commands. If all works well, that is, if the compiler and the VM translator and the assembler are implemented correctly, the target platform will end up effecting the behavior mandated by the original Jack program.
We end this section by illustrating how the VM abstraction can be used to express typical programming tasks found in high-level programs. We give three examples: (i) a typical arithmetic task, (ii) typical array handling, and (iii) typical object handling. These examples are irrelevant to the VM implementation, and in fact the entire section 7.2.6 can be skipped without losing the thread of the chapter.
The main purpose of this section is to illustrate how the compiler developed in chapters 10-11 will use the VM abstraction to translate high-level programs into VM code. Indeed, VM programs are rarely written by human programmers, but rather by compilers. Therefore, it is instructive to begin each example with a high-level code fragment, then show its equivalent representation using VM code. We use a C-style syntax for all the high-level examples.
A Typical Arithmetic Task
Consider the multiplication algorithm shown at the top of figure 7.9. How should we (or more likely, the compiler) express this algorithm in the VM language? First, high-level structures like for and while must be rewritten using the VM’s simple “goto logic.” In a similar fashion, high-level arithmetic and Boolean operations must be expressed using stack-oriented commands. The resulting code is shown in figure 7.9. (The exact semantics of the VM commands function, label, goto, if-goto, and return are described in chapter 8, but their intuitive meaning is self-explanatory.)
Consider the multiplication algorithm shown at the top of figure 7.9. How should we (or more likely, the compiler) express this algorithm in the VM language? First, high-level structures like for and while must be rewritten using the VM’s simple “goto logic.” In a similar fashion, high-level arithmetic and Boolean operations must be expressed using stack-oriented commands. The resulting code is shown in figure 7.9. (The exact semantics of the VM commands function, label, goto, if-goto, and return are described in chapter 8, but their intuitive meaning is self-explanatory.)
Let us focus on the virtual segments depicted at the bottom of figure 7.9. We see that when a VM function starts running, it assumes that (i) the stack is empty, (ii) the argument values on which it is supposed to operate are located in the argument segment, and (iii) the local variables that it is supposed to use are initialized to 0 and located in the local segment.
Let us now focus on the VM representation of the algorithm. Recall that VM commands cannot use symbolic argument and variable names—they are limited to making 〈
segment index
〉 references only. However, the translation from the former to the latter is straightforward. All we have to do is map x, y, sum and j on argument 0, argument 1, local 0 and local 1, respectively, and replace all their symbolic occurrences in the pseudo code with corresponding 〈
segment index
〉 references.
segment index
〉 references only. However, the translation from the former to the latter is straightforward. All we have to do is map x, y, sum and j on argument 0, argument 1, local 0 and local 1, respectively, and replace all their symbolic occurrences in the pseudo code with corresponding 〈
segment index
〉 references.
To sum up, when a VM function starts running, it assumes that it is surrounded by a private world, all of its own, consisting of initialized argument and local segments and an empty stack, waiting to be manipulated by its commands. The agent responsible for staging this virtual worldview for every VM function just before it starts running is the VM implementation, as we will see in the next chapter.
Figure 7.9
VM programming example.
VM programming example.
Array Handling
An array is an indexed collection of objects. Suppose that a high-level program has created an array of ten integers called bar and filled it with some ten numbers. Let us assume that the array’s base has been mapped (behind the scene) on RAM address 4315. Suppose now that the high-level program wants to execute the command bar[2]=19. How can we implement this operation at the VM level?
An array is an indexed collection of objects. Suppose that a high-level program has created an array of ten integers called bar and filled it with some ten numbers. Let us assume that the array’s base has been mapped (behind the scene) on RAM address 4315. Suppose now that the high-level program wants to execute the command bar[2]=19. How can we implement this operation at the VM level?
In the C language, such an operation can be also specified as *(bar+2)=19, meaning “
set
the RAM location whose address is (bar+2) to 19.” As shown in figure 7.10, this operation lends itself perfectly well to the VM language.
set
the RAM location whose address is (bar+2) to 19.” As shown in figure 7.10, this operation lends itself perfectly well to the VM language.
It remains to be seen, of course, how a high-level command like bar [2]= 19 is translated in the first place into the VM code shown in figure 7.10. This transformation is described in section 11.1.1, when we discuss the code generation features of the compiler.
Object Handling
High-level programmers view objects as entities that encapsulate data (organized as
fields,
or
properties
) and relevant code (organized as
methods
). Yet physically speaking, the data of each object instance is serialized on the RAM as a list of numbers representing the object’s field values. Thus the low-level handling of objects is quite similar to that of arrays.
High-level programmers view objects as entities that encapsulate data (organized as
fields,
or
properties
) and relevant code (organized as
methods
). Yet physically speaking, the data of each object instance is serialized on the RAM as a list of numbers representing the object’s field values. Thus the low-level handling of objects is quite similar to that of arrays.
For example, consider an animation program designed to juggle some balls on the screen. Suppose that each Ball object is characterized by the integer fields x, y, radius, and color. Let us assume that the program has created one such Ball object and called it b. What will be the internal representation of this object in the computer?
Like all other object instances, it will be stored in the RAM. In particular, whenever a program creates a new object, the compiler computes the object’s size in terms of words and the operating system finds and allocates enough RAM space to store it (the exact details of this operation are discussed in chapter 11). For now, let us assume that our b object has been allocated RAM addresses 3012 to 3015, as shown in figure 7.11.
Figure 7.10
VM-based array manipulation using the pointer and that segments.
VM-based array manipulation using the pointer and that segments.
Suppose now that a certain method in the high-level program, say resize, takes a Ball object and an integer r as arguments, and, among other things, sets the ball’s radius to r. The VM representation of this logic is shown in figure 7.11.
When we set pointer 0 to the value of argument 0, we are effectively setting the base of the virtual this segment to the object’s base address. From this point on, VM commands can access any field in the object using the virtual memory segment this and an index relative to the object’s base-address in memory.
But how did the compiler translate b.radius=17 into the VM code shown in figure 7.11? And how did the compiler know that the radius field of the object corresponds to the third field in its actual representation? We return to these questions in section 11.1.1, when we discuss the code generation features of the compiler.
7.3 ImplementationThe virtual machine that was described up to this point is an abstract artifact. If we want to use it for real, we must implement it on a real platform. Building such a VM implementation consists of two conceptual tasks. First, we have to emulate the VM world on the target platform. In particular, each data structure mentioned in the VM specification, namely, the stack and the virtual memory segments, must be represented in some way by the target platform. Second, each VM command must be translated into a series of instructions that effect the command’s semantics on the target platform.
This section describes how to implement the VM specification (section 7.2) on the Hack platform. We start by defining a “standard mapping” from VM elements and operations to the Hack hardware and machine language. Next, we suggest guidelines for designing the software that achieves this mapping. In what follows, we will refer to this software using the terms
VM
implementation or
VM
translator interchangeably.
7.3.1 Standard VM Mapping on the Hack Platform, Part IVM
implementation or
VM
translator interchangeably.
If you reread the virtual machine specification given so far, you will realize that it contains no assumption whatsoever about the architecture on which the VM can be implemented. When it comes to virtual machines, this platform independence is the whole point: You don’t want to commit to any one hardware platform, since you want your machine to potentially run on all of them, including those that were not built yet.
Other books
The Space Between by Brenna Yovanoff
Jeanne G'Fellers - Sister Lost, Sister Found by Jeanne G'Fellers
Me and Mr Jones by Lucy Diamond
Taste of Darkness by Katie Reus
The Porcelain Dove by Sherman, Delia
Unconditional surrender by Evelyn Waugh
Long Division by Taylor Leigh
Shadows of Asphodel by Kincy, Karen
The Wolf Sacrifice by Rosa Steel
Finding the Way Back by Jill Bisker
