The Elements of Computing Systems: Building a Modern Computer from First Principles (25 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
4.61Mb size Format: txt, pdf, ePub
The stack version of other operations (subtract, multiply, etc.) are precisely the same. For example, consider the expression d=(2-x)*(y+5), taken from some high-level program. The stack-based evaluation of this expression is shown in figure 7.3.
Stack-based evaluation of Boolean expressions has precisely the same flavor. For example, consider the high-level command if (x<7) or (y=8) then.... The stack-based evaluation of this expression is shown in figure 7.4.
The previous examples illustrate a general observation: any arithmetic and Boolean expression—no matter how complex—can be systematically converted into, and evaluated by, a sequence of simple operations on a stack. Thus, one can write a compiler that translates high-level arithmetic and Boolean expressions into sequences of stack commands, as we will do in chapters 10-11. We now turn to specify these commands (section 7.2), and describe their implementation on the Hack platform (section 7.3).
7.2 VM Specification, Part I7.2.1 General
The virtual machine is stack-based: all operations are done on a stack. It is also function-based: a complete VM program is organized in program units called functions, written in the VM language. Each function has its own stand-alone code and is separately handled. The VM language has a single 16-bit data type that can be used as an integer, a Boolean, or a pointer. The language consists of four types of commands:
■
Arithmetic commands
perform arithmetic and logical operations on the stack.
Arithmetic commands
perform arithmetic and logical operations on the stack.
■
Memory access commands
transfer data between the stack and virtual memory segments.
Memory access commands
transfer data between the stack and virtual memory segments.
■
Program flow commands
facilitate conditional and unconditional branching operations.
Program flow commands
facilitate conditional and unconditional branching operations.
■
Function calling commands
call functions and return from them.
Function calling commands
call functions and return from them.
Figure 7.3
Stack-based evaluation of arithmetic expressions. This example evaluates the expression d = (2 - x) * (y + 5), assuming the initial memory state x = 5, y = 9.
Stack-based evaluation of arithmetic expressions. This example evaluates the expression d = (2 - x) * (y + 5), assuming the initial memory state x = 5, y = 9.
Figure 7.4
Stack-based evaluation of logical expressions. This example evaluates the Boolean expression (x < 7) or (y = 8), assuming the initial memory state x = 12, y = 8.
Stack-based evaluation of logical expressions. This example evaluates the Boolean expression (x < 7) or (y = 8), assuming the initial memory state x = 12, y = 8.
Building a virtual machine is a complex undertaking, and so we divide it into two stages. In this chapter we specify the
arithmetic
and
memory access
commands and build a basic VM translator that implements them only. The next chapter specifies the program flow and function calling commands and extends the basic translator into a full-scale virtual machine implementation.
arithmetic
and
memory access
commands and build a basic VM translator that implements them only. The next chapter specifies the program flow and function calling commands and extends the basic translator into a full-scale virtual machine implementation.
Program and Command Structure
A VM
program
is a collection of one or more files with a .vm extension, each consisting of one or more functions. From a compilation standpoint, these constructs correspond, respectively, to the notions of
program, class,
and method in an object-oriented language.
A VM
program
is a collection of one or more files with a .vm extension, each consisting of one or more functions. From a compilation standpoint, these constructs correspond, respectively, to the notions of
program, class,
and method in an object-oriented language.
Within a .vm file, each VM command appears in a separate line, and in one of the following formats:
command
(e.g., add),
command arg
(e.g., goto loop), or command
arg1 arg2
(e.g., push local 3). The arguments are separated from each other and from the
command
part by an arbitrary number of spaces. “//” comments can appear at the end of any line and are ignored. Blank lines are permitted and ignored.
7.2.2 Arithmetic and Logical Commandscommand
(e.g., add),
command arg
(e.g., goto loop), or command
arg1 arg2
(e.g., push local 3). The arguments are separated from each other and from the
command
part by an arbitrary number of spaces. “//” comments can appear at the end of any line and are ignored. Blank lines are permitted and ignored.
The VM language features nine stack-oriented arithmetic and logical commands. Seven of these commands are binary: They pop two items off the stack, compute a binary function on them, and push the result back onto the stack. The remaining two commands are unary: they pop a single item off the stack, compute a unary function on it, and push the result back onto the stack. We see that each command has the net impact of replacing its operand(s) with the command’s result, without affecting the rest of the stack. Figure 7.5 gives the details.
Three of the commands listed in figure 7.5 (eq, gt, lt) return Boolean values. The VM represents
true
and
false
as -1 (minus one, 0xFFFF) and 0 (zero, 0x0000), respectively.
7.2.3 Memory Access Commandstrue
and
false
as -1 (minus one, 0xFFFF) and 0 (zero, 0x0000), respectively.
So far in the chapter, memory access commands were illustrated using the pseudo-commands
pop
and
push x
, where the symbol
x
referred to an individual location in some global memory. Yet formally, our VM manipulates eight separate virtual memory segments, listed in figure 7.6.
pop
and
push x
, where the symbol
x
referred to an individual location in some global memory. Yet formally, our VM manipulates eight separate virtual memory segments, listed in figure 7.6.
Figure 7.5
Arithmetic and logical stack commands.
Arithmetic and logical stack commands.
Memory Access Commands
All the memory segments are accessed by the same two commands:
All the memory segments are accessed by the same two commands:
• push
segment index
Push the value of
segment
[
index
] onto the stack.
• pop
segment index
Pop the top stack value and store it in
segment
[
index
].
Figure 7.6
The memory segments seen by every VM function.
The memory segments seen by every VM function.
Figure 7.7
The virtual memory segments are maintained by the VM implementation.
The virtual memory segments are maintained by the VM implementation.
Where
segment
is one of the eight segment names and index is a non-negative integer. For example, push argument 2 followed by pop local 1 will store the value of the function’s third argument in the function’s second local variable (each segment’s index starts at 0).
segment
is one of the eight segment names and index is a non-negative integer. For example, push argument 2 followed by pop local 1 will store the value of the function’s third argument in the function’s second local variable (each segment’s index starts at 0).
The relationship among VM files, VM functions, and their respective virtual memory segments is depicted in figure 7.7.
In addition to the eight memory segments, which are managed explicitly by VM push and pop commands, the VM implementation manages two implicit data structures called
stack
and
heap
. These data structures are never mentioned directly, but their states change in the background, as a side effect of VM commands.
stack
and
heap
. These data structures are never mentioned directly, but their states change in the background, as a side effect of VM commands.
The Stack
Consider the commands sequence push argument 2 and pop local 1, mentioned before. The working memory of such VM operations is the stack. The data value did not simply jump from one segment to another—it went through the stack. Yet in spite of its central role in the VM architecture, the stack proper is never mentioned in the VM language.
Consider the commands sequence push argument 2 and pop local 1, mentioned before. The working memory of such VM operations is the stack. The data value did not simply jump from one segment to another—it went through the stack. Yet in spite of its central role in the VM architecture, the stack proper is never mentioned in the VM language.
The Heap
Another memory element that exists in the VM’s background is the
heap
. The heap is the name of the RAM area dedicated for storing objects and arrays data. These objects and arrays can be manipulated by VM commands, as we will see shortly.
7.2.4 Program Flow and Function Calling CommandsAnother memory element that exists in the VM’s background is the
heap
. The heap is the name of the RAM area dedicated for storing objects and arrays data. These objects and arrays can be manipulated by VM commands, as we will see shortly.
The VM features six additional commands that are discussed at length in the next chapter. For completeness, these commands are listed here.
Program Flow Commands
Other books
The Quicksilver Faire by Gillian Summers
Trail of the Twisted Cros by Buck Sanders
Disclosure of the Heart (The Heart Series) by Whitney, Mary
Circle of Deception by Swafford, Carla
The Pregnancy Shock by Lynne Graham
The Silent Girls by Ann Troup
Living by the Word by Alice Walker
Quid Pro Quo by Vicki Grant
Mexico City Noir by Paco Ignacio Taibo II
Carla Kelly by The Wedding Journey
