The Elements of Computing Systems: Building a Modern Computer from First Principles (30 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
2.54Mb size Format: txt, pdf, ePub
The VM language features three function-related commands:
■ function
f n
Here starts the code of a function named f that has n local variables;
■ call
f m
Call function
f
, stating that
m
arguments have already been pushed onto the stack by the caller;
■ return Return to the calling function.
8.2.3 The Function Calling Protocol
The events of calling a function and returning from a function can be viewed from two different perspectives: that of the calling function and that of the called function.
The calling function view:
■ Before calling the function, the caller must push as many arguments as necessary onto the stack;
■ Next, the caller invokes the function using the call command;
■ After the called function returns, the arguments that the caller has pushed before the call have disappeared from the stack, and a return value (that always exists) appears at the top of the stack;
■ After the called function returns, the caller’s memory segments argument, local, static, this, that, and pointer are the same as before the call, and the temp segment is undefined.
The called function view:
■ When the called function starts executing, its argument segment has been initialized with actual argument values passed by the caller and its local variables segment has been allocated and initialized to zeros. The static segment that the called function sees has been set to the static segment of the VM file to which it belongs, and the working stack that it sees is empty. The segments this, that, pointer, and temp are undefined upon entry.
■ Before returning, the called function must push a value onto the stack.
To repeat an observation made in the previous chapter, we see that when a VM function starts running (or resumes its previous execution), it assumes that it is surrounded by a private world, all of its own, consisting of its memory segments and stack, waiting to be manipulated by its commands. The agent responsible for building this virtual worldview for every VM function is the VM implementation, as we elaborate in section 8.3.
8.2.4 Initialization
A VM program is a collection of related VM functions, typically resulting from the compilation of some high-level program. When the VM implementation starts running (or is reset), the convention is that it always executes an argument-less VM function called Sys.init. Typically, this function then calls the main function in the user’s program. Thus, compilers that generate VM code must ensure that each translated program will have one such Sys.init function.
8.3 Implementation
This section describes how to complete the VM implementation that we started building in chapter 7, leading to a full-scale virtual machine implementation. Section 8.3.1 describes the stack structure that must be maintained, along with its standard mapping over the Hack platform. Section 8.3.2 gives an example, and section 8.3.3 provides design suggestions and a proposed API for actually building the VM implementation.
Some of the implementation details are rather technical, and dwelling on them may distract attention from the overall VM operation. This big picture is restored in section 8.3.2, which illustrates the VM implementation in action. Therefore, one may want to consult 8.3.2 for motivation while reading 8.3.1.
8.3.1 Standard VM Mapping on the Hack Platform, Part II
The Global Stack
The memory resources of the VM are implemented by maintaining a global stack. Each time a function is called, a new block is added to the global stack. The block consists of the arguments that were set for the called function, a set of pointers used to save the state of the calling function, the local variables of the called function (initialized to 0), and an empty working stack for the called function. Figure 8.4 shows this generic stack structure.
Figure 8.4
The global stack structure.
 
Note that the shaded areas in figure 8.4 as well as the ARG, LCL, and SP pointers are never seen by VM functions. Rather, they are used by the VM implementation to implement the function call-and-return protocol behind the scene.
How can we implement this model on the Hack platform? Recall that the standard mapping specifies that the stack should start at RAM address 256, meaning that the VM implementation can start by generating assembly code that sets SP=256. From this point onward, when the VM implementation encounters commands like pop, push, add, and so forth, it can emit assembly code that effects these operations by manipulating SP and relevant words in the host RAM. All this was already done in chapter 7. Likewise, when the VM implementation encounters commands like call, function, and return, it can emit assembly code that maintains the stack structure shown in figure 8.4 on the host RAM. This code is described next.
 
Function Calling Protocol Implementation
The function calling protocol and the global stack structure implied by it can be implemented on the Hack platform by effecting (in Hack assembly) the pseudo-code given in figure 8.5.
Recall that the VM implementation is a translator program, written in some high-level language. It accepts VM code as input and emits assembly code as output. Hence, each pseudo-operation described in the right column of figure 8.5 is actually implemented by emitting assembly language instructions. Note that some of these “instructions” entail planting label declarations in the generated code stream.
Figure 8.5
VM implementation of function commands. The parenthetical (return address) and (f ) are label declarations, using Hack assembly syntax convention.
 
Assembly Language Symbols
As we have seen earlier, the implementation of program flow and function calling commands requires the VM implementation to create and use special symbols at the assembly level. These symbols are summarized in figure 8.6. For completeness of presentation, the first three rows of the table document the symbols described and implemented in chapter 7.
Figure 8.6
All the special assembly symbols prescribed by the VM-on-Hack standard mapping.
 
Bootstrap Code
When applied to a VM program (a collection of one or more .vm files), the VM-to-Hack translator produces a single .asm file, written in the Hack assembly language. This file must conform to certain conventions. Specifically, the standard mapping specifies that (i) the VM stack should be mapped on location RAM[256] onward, and (ii) the first VM function that starts executing should be Sys.init (see section 8.2.4).
How can we effect this initialization in the .asm file produced by the VM translator? Well, when we built the Hack computer hardware in chapter 5, we wired it in such a way that upon reset, it will fetch and execute the word located in ROM[0]. Thus, the code segment that starts at ROM address 0, called bootstrap code, is the first thing that gets executed when the computer “boots up.” Therefore, in view of the previous paragraph, the computer’s bootstrap code should effect the following operations (in machine language):
Sys.init is then expected to call the main function of the main program and then enter an infinite loop. This action should cause the translated VM program to start running.
The notions of “program,” “main program,” and “main function” are compilation-specific and vary from one high-level language to another. For example, in the Jack language, the default is that the first program unit that starts running automatically is the main method of a class named Main. In a similar fashion, when we tell the JVM to execute a given Java class, say Foo, it looks for, and executes, the Foo.main method. Each language compiler can effect such “automatic” startup routines by programming Sys.init appropriately.
8.3.2 Example
The factorial of a positive number n can be computed by the iterative formula n! = 1 ·2·... ·(
n
- 1) ·
n
. This algorithm is implemented in figure 8.7.
Let us focus on the call mult command highlighted in the fact function code from figure 8.7. Figure 8.8 shows three stack states related to this call, illustrating the function calling protocol in action.
If we ignore the middle stack instance in figure 8.8, we observe that fact has set up some arguments and called mult to operate on them (left stack instance). When mult returns (right stack instance), the arguments of the called function have been replaced with the function’s return value. In other words, when the dust clears from the function call, the calling function has received the service that it has requested, and processing resumes as if nothing happened: The drama of mult’s processing (middle stack instance) has left no trace whatsoever on the stack, except for the return value.

Other books

Just One Look by Harlan Coben
The Bottom of Your Heart by Maurizio de Giovanni, Antony Shugaar
Dark Horse by Rhea Wilde
Our Lady of Darkness by Fritz Leiber
Falling for the Enemy by Samanthe Beck
The Remaining Voice by Elliott, Angela
Nightshade by John Saul
Sexual Solstice by Bradley, Tracey B.