Virtual Machine

Part I: Stack Arithmetic

Building a Modern Computer From First Principles

www.nand2tetris.org

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 1
Where we are at:

Human Abstract design Software

abstract interface
Thought hierarchy
Chapters 9, 12
H.L. Language Compiler
& abstract interface
Chapters 10 - 11
Operating Sys.
Virtual VM Translator
abstract interface
Machine Chapters 7 - 8

Assembly
Language

Assembler

Chapter 6

abstract interface
Computer
Machine Architecture
abstract interface
Language
Chapters 4 - 5
Hardware Gate Logic
abstract interface
Platform Chapters 1 - 3 Electrical
Chips & Engineering
Hardware Physics
Logic Gates
hierarchy

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 2
Motivation

Jack code (example) Hack code

0000000000010000
0000000000010000
class
class Main
Main {{ 1110111111001000
1110111111001000
static
static int
int x;
x; Our ultimate goal: 0000000000010001
0000000000010001
1110101010001000
1110101010001000
function
function void
void main()
main() {{ Translate high-level 0000000000010000
0000000000010000
// programs into 1111110000010000
// Inputs
Inputs and
and multiplies
multiplies two
two numbers
numbers 1111110000010000
var int a, b, x; 0000000000000000
0000000000000000
var int a, b, x; executable code. 1111010011010000
let
let aa == Keyboard.readInt(“Enter
Keyboard.readInt(“Enter aa number”);
number”); 1111010011010000
0000000000010010
0000000000010010
let b = Keyboard.readInt(“Enter a number”);
let b = Keyboard.readInt(“Enter a number”); 1110001100000001
1110001100000001
let
let xx == mult(a,b);
mult(a,b); 0000000000010000
return;
return;
Compiler 0000000000010000
1111110000010000
1111110000010000
}} 0000000000010001
0000000000010001
}} 0000000000010000
0000000000010000
1110111111001000
1110111111001000
0000000000010001
0000000000010001
//
// Multiplies
Multiplies twotwo numbers.
numbers. 1110101010001000
1110101010001000
function
function int mult(int x,
int mult(int x, int
int y)
y) {{ 0000000000010000
0000000000010000
var
var int
int result,
result, j;j; 1111110000010000
let 1111110000010000
let result
result == 0;
0; let
let jj == y;
y; 0000000000000000
0000000000000000
while ~(j = 0)
while ~(j = 0) { { 1111010011010000
1111010011010000
let
let result
result == result
result ++ x;x; 0000000000010010
0000000000010010
let j = j – 1;
let j = j – 1; 1110001100000001
1110001100000001
}} 0000000000010000
0000000000010000
return 1111110000010000
return result;
result; 1111110000010000
}} 0000000000010001
0000000000010001
}} ...
...

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 3
Compilation models

direct compilation: 2-tier compilation:

language 1 language 2 ... language n language 1 language 2 ... language n

intermediate language

hardware
platform 1
hardware
platform 2
... hardware
platform m
hardware hardware ... hardware
platform 1 platform 2 platform m
.
requires n m translators requires n + m translators

Two-tier compilation:

First compilation stage: depends only on the details of the source language

Second compilation stage: depends only on the details of the target language.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 4
The big picture
The intermediate code:
Some
language
... Some Other
language
... Jack
language
The interface between
the 2 compilation stages
Some Jack
Must be sufficiently
compiler Some Other
compiler compiler general to support many
<high-level language,
machine-language>
Intermediate code pairs

Can be modeled as the
VM
VM imp. language of an abstract
implementation VM imp.
over CISC over RISC
VM over the Hack virtual machine (VM)
emulator platform
platforms platforms

Can be implemented in
several different ways.

CISC RISC written in Hack

machine
language
machine
language
... a high-level
language
machine
language

... ...
CISC RISC other digital platforms, each equipped Any Hack
machine machine with its own VM implementation computer computer

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 5
Focus of this lecture (yellow):
Some
language
... Some Other
language
... Jack
language
Book chapters and
Course projects:

Some Jack 9, 10, 11, 12

Some Other
compiler
compiler compiler

VM language

VM
VM imp.
implementation VM imp. VM over the Hack 7, 8 (this and the
over CISC over RISC
platforms platforms
emulator platform next lecture)

CISC RISC written in Hack

machine
language
machine
language
... a high-level
language
machine
language

1, 2, 3, 4, 5, 6
... ...
CISC RISC other digital platforms, each equipped Any Hack
machine machine with its VM implementation computer computer

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 6
The VM model and language
Perspective:
From here till the end of the next lecture we describe the VM model used in the
Hack-Jack platform
Other VM models (like Java’s JVM/JRE and .NET’s IL/CLR) are similar in spirit
but differ in scope and details.

Several different ways to think about the notion of a virtual machine:

Abstract software engineering view:
the VM is an interesting abstraction that makes sense in its own right

Practical software engineering view:
the VM code layer enables “managed code” (e.g. enhanced security)

Pragmatic compiler writing view:
a VM architecture makes writing a compiler much easier
(as we’ll see later in the course)

Opportunistic empire builder view:
a VM architecture allows writing high-level code once and have it run on many target
platforms with little or no modification.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 7
Yet another view (poetic)

“programmers are creators of

universes for which they alone are
responsible. Universes of virtually
unlimited complexity can be
created in the form of computer
programs.”
(Joseph Weizenbaum)

Our VM model + language are an example of one such universe.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 8
Lecture plan
Goal: Specify and implement a VM model and language:

Arithmetic
Arithmetic//Boolean
Booleancommands
commands Program
Programflow
flowcommands
commands
add
add label
label (declaration)
(declaration)
sub
sub
goto
goto (label)
(label)
neg
neg
eq if-goto
if-goto (label)
(label)
eq
gt
gt This lecture Next lecture
lt
lt Function
Functioncalling
callingcommands
commands
and
and
or
or function
function (declaration)
(declaration)
not
not call
call (a(afunction)
function)
Memory
Memoryaccess
accesscommands
commands
pop
pop xx (pop
(popinto
intox,x,which
whichisisaavariable)
variable) return
return (from
(fromaafunction)
function)
push
push yy (y(ybeing
beingaavariable
variableororaaconstant)
constant)

Our game plan: (a) describe the VM abstraction (above)

(b) propose how to implement it over the Hack platform.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 9
Our VM model is stack-oriented

 All operations are done on a stack

 Data is saved in several separate memory segments
 All the memory segments behave the same
 One of the memory segments m is called static, and we will use it
(as an arbitrary example) in the following examples:

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 10
Data types

Our VM model features a single 16-bit data type that can be used as:

an integer value (16-bit 2’s complement: -32768, ... , 32767)

a Boolean value (0 and -1, standing for true and false)

a pointer (memory address)

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 11
Memory access operations

push
static 2

(before) (after)

pop
static 0

The stack:
 A classical LIFO data structure
 Elegant and powerful
 Several hardware / software implementation options.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 12
Evaluation of arithmetic expressions
VM code (example)
//
// z=(2-x)-(y+5)
z=(2-x)-(y+5)
push
push 22
(suppose that
push
push xx x refers to static 0,
sub
sub
push y refers to static 1, and
push yy
push
push 55 z refers to static 2)
add
add
sub
sub
pop
pop zz

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 13
Evaluation of Boolean expressions
VM code (example)
//
// (x<7)
(x<7) or
or (y=8)
(y=8)
push x
push x
(suppose that
push
push 77 x refers to static 0, and
lt
lt
push y refers to static 1)
push yy
push
push 88
eq
eq
or
or

(actually true and false

are stored as 0 and -1,
respectively)

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 14
Arithmetic and Boolean commands in the VM language (wrap-up)

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 15
The VM’s Memory segments

A VM program is designed to provide an interim abstraction of a program

written in some high-level language

Modern OO high-level languages normally feature the following variable kinds:

Class level:

Static variables (class-level variables)

Private variables (aka “object variables” / “fields” / “properties”)

Method level:

Local variables

Argument variables

When translated into the VM language,

The static, private, local and argument variables are mapped by the compiler on
the four memory segments static, this, local, argument
In addition, there are four additional memory segments, whose role will be
presented later: that, constant, pointer, temp.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 16
Memory segments and memory access commands
The VM abstraction includes 8 separate memory segments named:
static, this, local, argument, that, constant, pointer, temp

As far as VM programming commands go, all memory segments look and behave the same
To access a particular segment entry, use the following generic syntax:

Memory
Memoryaccess
accessVM
VMcommands:
commands:



pop
popmemorySegment
memorySegment index
index



push
pushmemorySegment
memorySegment index
index
Where memorySegmentisisstatic
WherememorySegment static, ,this
this, ,local
local, ,argument
argument, ,that
that, ,constant
constant, ,pointer
pointer, ,or
ortemp
temp
And indexisisaanon-negative
Andindex non-negativeinteger
integer

Notes:
(In all our code examples thus far, memorySegment was static)
The different roles of the eight memory segments will become relevant when we’ll talk
about the compiler
At the VM abstraction level, all memory segments are treated the same way.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 17
VM programming

VM programs are normally written by compilers, not by humans

However, compilers are written by humans ...

In order to write or optimize a compiler, it helps to first understand the spirit of

the compiler’s target language – the VM language

So, we’ll now see an example of a VM program

The example includes three new VM commands:

function functionSymbol //
function functionSymbol //function
functiondeclaration
declaration




label
label labelSymbol
labelSymbol //
//label
labeldeclaration
declaration




if-goto labelSymbol //
if-goto labelSymbol // pop
pop xx
//
//ififx=true,
x=true,jump
jumptotoexecute
executethe
thecommand
commandafter
after labelSymbol
labelSymbol
//
// else proceed to execute the next command in theprogram
else proceed to execute the next command in the program
For
Forexample,
example,to
toeffect
effectif
if(x
(x>>n)
n) goto loop, ,we
gotoloop wecan
canuse
usethe
thefollowing
followingVM
VMcommands:
commands:
push
push xx
push
push nn
gt
gt
if-goto
if-goto loop
loop //
//Note
Notethat
thatx,x,n,n,and
andthe
thetruth
truthvalue
valuewere
wereremoved
removedfrom
fromthe
thestack.
stack.
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 18
VM programming (example)
High-level code VM code (first approx.) VM code
function function
function mult(x,y) function
function mult
mult 22
function multmult (x,y)
(x,y) {{ mult(x,y)
int push
push 00 push
push constant
constant 00
int result,
result, j; j;
result pop
pop result pop
pop local
local 00
result == 0; 0; result
jj == y; push
push yy push
push argument
argument 11
y;
while pop
pop jj pop
pop local
local 11
while ~(j~(j == 0)0) {{
result label
label loop label
label loop
loop
result == result
result ++ x;
x; loop
jj == jj -- 1; push
push jj push
push local
local 11
1;
}} push
push 00 push
push constant
constant 00
return eq eq
eq
return result;
result; eq
}} if-goto
if-goto end
end if-goto
if-goto end
end
push result
push result push
push local
local 00
push
push xx push
push argument
argument 00
add
add add
add
pop
pop result
result pop
pop local
local 00
push
push jj push
push local
local 11
push
push 11 push
push constant
constant 11
sub
sub sub
sub
pop
pop jj pop
pop local
local 11
goto
goto loop
loop goto
goto loop
loop
label end
label end label
label end
end
push
push result
result push
push local
local 00
return
return return
return

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 19
VM programming: multiple functions
Compilation:

A Jack application is a set of 1 or more class files (just like .java files).

When we apply the Jack compiler to these files, the compiler creates a set of 1 or
more .vm files (just like .class files). Each method in the Jack app is translated
into a VM function written in the VM language

Thus, a VM file consists of one or more VM functions.

Execution:

At any given point of time, only one VM function is executing (the “current
function”), while 0 or more functions are waiting for it to terminate (the functions
up the “calling hierarchy”)

For example, a main function starts running; at some point we may reach the
command call factorial, at which point the factorial function starts running;
then we may reach the command call mult, at which point the mult function starts
running, while both main and factorial are waiting for it to terminate

The stack: a global data structure, used to save and restore the resources (memory
segments) of all the VM functions up the calling hierarchy (e.g. main and factorial).
The tip of this stack if the working stack of the current function (e.g. mult).
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 20
Lecture plan
Goal: Specify and implement a VM model and language:

Arithmetic
Arithmetic//Boolean
Booleancommands
commands Program
Programflow
flowcommands
commands
add
add label
label (declaration)
(declaration)
sub
sub
goto
goto (label)
(label)
neg
neg
eq if-goto
if-goto (label)
(label)
eq
gt
gt This lecture Next lecture
lt
lt Function
Functioncalling
callingcommands
commands
and
and
or
or function
function (declaration)
(declaration)
not
not call
call (a(afunction)
function)
Memory
Memoryaccess
accesscommands
commands
pop
pop xx (pop
(popinto
intox,x,which
whichisisaavariable)
variable) return
return (from
(fromaafunction)
function)
push
push yy (y(ybeing
beingaavariable
variableororaaconstant)
constant)

Method: (a) specify the abstraction (stack, memory segments, commands)

(b) propose how to implement the abstraction over the Hack platform.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 21
Implementation
VM implementation options:

 Software-based (e.g. emulate the VM model using Java)

 Translator-based (e. g. translate VM programs into the Hack machine language)

 Hardware-based (realize the VM model using dedicated memory and registers)

Two well-known translator-based implementations:

JVM: Javac translates Java programs into bytecode;

The JVM translates the bytecode into
the machine language of the host computer

CLR: C# compiler translates C# programs into IL code;

The CLR translated the IL code into
the machine language of the host computer.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 22
Software implementation: Our VM emulator (part of the course software suite)

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 23
VM implementation on the Hack platform
The stack: a global data structure, used to save
and restore the resources of all the VM
functions up the calling hierarchy.
The tip of this stack if the working stack of the
current function
Host
static, constant, temp, pointer:
RAM Global memory segments, all functions
see the same four segments
local,argument,this,that:
these segments are local at the function level;
each function sees its own, private copy of
each one of these four segments
The challenge:
represent all these logical constructs on the
same single physical address space -- the host
RAM.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 24
 VM implementation on the Hack platform
SP 0 Basic idea: the mapping of the stack and the
LCL 1
global segments on the RAM is easy (fixed);
the mapping of the function-level segments is
ARG 2
dynamic, using pointers
THIS 3

THAT 4
The stack: mapped on RAM[256 ... 2047];
5
Host The stack pointer is kept in RAM address SP
TEMP ... RAM static: mapped on RAM[16 ... 255];
12 each segment reference static i appearing in a
13
VM file named f is compiled to the assembly
General
language symbol f.i (recall that the assembler further
14 maps such symbols to the RAM, from address 16 onward)
purpose
15
local,argument,this,that: these method-level
16
segments are mapped somewhere from address
... Statics 2048 onward, in an area called “heap”. The base
255 addresses of these segments are kept in RAM
256 addresses LCL, ARG, THIS, and THAT. Access to
... Stack the i-th entry of any of these segments is
2047 implemented by accessing RAM[segmentBase + i]
2048 constant: a truly a virtual segment:
... Heap access to constant i is implemented by
supplying the constant i.
pointer: discussed later.
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 25
 VM implementation on the Hack platform
SP 0 Practice exercises
LCL 1
Now that we know how the memory segments are
ARG 2 mapped on the host RAM, we can write Hack
THIS 3 commands that realize the various VM commands.
THAT 4 for example, let us write the Hack code that
5
Host implements the following VM commands:
TEMP ... RAM
push constant 1
12
pop static 7 (suppose it appears in a VM file named f)
13

push constant 5
General 14
purpose
add
15

pop local 2
16

... Statics
eq
255 Tips:
256
... 1. The implementation of any one of these VM
Stack
2047
commands requires several Hack assembly
commands involving pointer arithmetic
2048
... (using commands like A=M)
Heap
2. If you run out of registers (you have only two ...),
you may use R13, R14, and R15.
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 26
Proposed VM translator implementation: Parser module
Parser: Handles the parsing of a single .vm file, and encapsulates access to the input code. It reads VM commands,
parses them, and provides convenient access to their components. In addition, it removes all white space and comments.
Routine Arguments Returns Function

Input file / Opens the input file/stream and gets ready to

Constructor --
stream parse it.

hasMoreCommands -- boolean Are there more commands in the input?

Reads the next command from the input and
makes it the current command. Should be called
advance -- --
only if hasMoreCommands is true.
Initially there is no current command.

C_ARITHMETIC, C_PUSH,
Returns the type of the current VM command.
C_POP, C_LABEL, C_GOTO,
commandType --
C_IF, C_FUNCTION, C_ARITHMETIC is returned for all the arithmetic
C_RETURN, C_CALL commands.

Returns the first arg. of the current command.

In the case of C_ARITHMETIC, the command itself
arg1 -- string
(add, sub, etc.) is returned. Should not be called
if the current command is C_RETURN.
Returns the second argument of the current
command. Should be called only if the current
arg2 -- int
command is C_PUSH, C_POP, C_FUNCTION, or
C_CALL.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 27
Proposed VM translator implementation: CodeWriter module
CodeWriter: Translates VM commands into Hack assembly code.

Routine Arguments Returns Function

Constructor Output file / stream -- Opens the output file/stream and gets ready to
write into it.

setFileName fileName (string) -- Informs the code writer that the translation of a
new VM file is started.

writeArithmetic command (string) -- Writes the assembly code that is the translation
of the given arithmetic command.

WritePushPop command (C_PUSH or -- Writes the assembly code that is the translation
C_POP), of the given command, where command is either
C_PUSH or C_POP.
segment (string),

index (int)
Close -- -- Closes the output file.

Comment: More routines will be added to this module in the next lecture / chapter 8.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 28
 Some
language
... Some Other
language
. . . Jack

Perspective Some
compiler Some Other
compiler
compiler

VM language
VM
implementation VM imp.
VM
over CISC over RISC
emulator Translator
 In this lecture we began the process of
platforms platforms

building a compiler CISC

machine
RISC
machine ...
written in
a high-level Hack
language language language

... ...
 Modern compiler architecture:

 Front-end (translates from a high-level language to a VM language)

 Back-end (translates from the VM language to the machine
language of some target hardware platform)
 Brief history of virtual machines:
 1970’s: p-Code
 1990’s: Java’s JVM
 2000’s: Microsoft .NET
 A full blown VM implementation typically also includes a common software library
(can be viewed as a mini, portable OS).
 We will build such a mini OS later in the course.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 29
The big picture

JVM
CLR
VM
7, 8

Java
C#
Jack
9

Java compiler
C# compiler
Jack compiler
10, 11

JRE
.NET base
Mini OS
12

class library
(Book chapters and
Course projects)

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 7: Virutal Machine, Part I slide 30