USA: +1(669)289-8683 
Sign in
5/2/23, 10:35 AMQuiz: Final Exam
Final Exam
Started: May 2 at 10:30am
Quiz Instructions
Question 1
1 pts
In the VM language, functions are declared using the command “function functionName n”. The integer n stands for
the number of this function’s
local variables
local and static variables
arguments
static variables
none of the above
Question 2
1 pts
Suppose that the function foo pushes two arguments and calls the function bar. After bar returns, the two argument
values have disappeared, and the stack’s top value is the value returned by bar. Who is responsible for removing the
arguments from the stack?
https://canvas.fau.edu/courses/134662/quizzes/424192/take
1/9
5/2/23, 10:35 AM
Quiz: Final Exam
The foo function
The bar function
The VM implementation
None of the above
Question 3
1 pts
Consider the global stack with SP = 305, LCL = 300, ARG = 292. Suppose the current running function is foo, and foo
hasn’t pushed or popped anything yet. How many local variables does foo have?
4
5
6
0
none of the above
Question 4
1 pts
The implementation of the VM return command starts with two commands that, taken together, store the return address
in the temporary variable retAddr. Which is correct?
https://canvas.fau.edu/courses/134662/quizzes/424192/take
2/9
5/2/23, 10:35 AM
Quiz: Final Exam
This is done to make the code more readable.
This is done to comply with the standard mapping.
This is done since, if the function has no arguments, the next command, which is *ARG = pop(), will override the return address.
None of the above.
Question 5
1 pts
When we execute a Jack program, the first subroutine that starts running is
Main.main
main.Main
It depends on which function is executed.
main.main
Main.Main
None of the above.
Question 6
1 pts
Suppose a = 6 and b = 11. What will be the value of c after the following commands: push 2, push a, sub, push b, push
9, add, add, pop c.
https://canvas.fau.edu/courses/134662/quizzes/424192/take
3/9
5/2/23, 10:35 AM
Quiz: Final Exam
16
24
20
None of the above.
Question 7
1 pts
Suppose LCL = 1231. Where in RAM will local 3 be mapped?
1231
1232
1233
None of the above.
Question 8
1 pts
The control bits to the Hack CPU are zx = 0, nx = 0, zy = 1, ny = 0, f = 1, no = 0. The output is:
0
x+y
https://canvas.fau.edu/courses/134662/quizzes/424192/take
4/9
5/2/23, 10:35 AM
Quiz: Final Exam
x
–x
None of the above.
Question 9
1 pts
Suppose the state of the RAM is: RAM[256] = 22, RAM[257] = 31, RAM[258] = 200, RAM[259] = 28. What is the
content of RAM[258] after the following sequence of instructions is performed: p1 = 256, p1 = p1 + 3, *p1 = *p1 + 3, p2
= p1 – 2, p1– –,
*(p2 + 1) = *p1 + *p2.
230
231
232
211
None of the above
Question 10
1 pts
Suppose the state of the RAM is RAM[0] = 3, RAM[1] = 2, RAM[2] = 0, RAM[3] = 6, RAM[4] = 5, RAM[5] = 1, RAM[6] =
4. What is stored in RAM[4] after execution of the following sequence of statements: @1, A = M, A = M, A = M, D = M,
https://canvas.fau.edu/courses/134662/quizzes/424192/take
5/9
5/2/23, 10:35 AM
Quiz: Final Exam
@4, M = D.
6
5
3
0
None of the above
Question 11
3 pts
Write an assembly language program to push constant 5 onto the stack.
Edit
12pt
View
Insert
Format
Tools
Table
Paragraph
https://canvas.fau.edu/courses/134662/quizzes/424192/take
6/9
5/2/23, 10:35 AM
Quiz: Final Exam
p
0 words
Question 12
3 pts
Write a Hack computer program to set RAM[1] to the value RAM[0] + 4.
Edit
12pt
View
Insert
Format
Tools
Table
Paragraph
p
https://canvas.fau.edu/courses/134662/quizzes/424192/take
0 words
7/9
5/2/23, 10:35 AM
Quiz: Final Exam
Question 13
4 pts
The logical steps to implement the command pop argument 2 are: addr = ARG + 2, SP––, *addr = *SP. Write the
assembly language code that implements this logic.
Edit
12pt
View
Insert
Format
Tools
Table
Paragraph
p
https://canvas.fau.edu/courses/134662/quizzes/424192/take
0 words
8/9
5/2/23, 10:35 AM
Quiz: Final Exam
Quiz saved at 10:35am
https://canvas.fau.edu/courses/134662/quizzes/424192/take
Submit Quiz
9/9
3/12/23
The Road Ahead
Jack
Program
compiler
Jack
Program
VM code
VM Translator
Assembly
code
assembler
VM code
assembler
load
Machine
code
Hack
computer
1
Program Compilation
• Write once, run everywhere
• 2-tier compilation
High-level
program
compiler
VM code
This
computer
That
computer
This device
That device
2
1
3/12/23
Program Compilation
Jack
program
Jack
compiler
VM code
VM emulator
Your PC
VM translator
Hack
computer
3
The Stack
•
•
•
•
Like a stack of plates
Push – add a plate to the top of the stack
Pop – remove top plate of the stack
Can only access the top of the stack
•
pu
4
2
3/12/23
The stack
SP – stack pointer – the next available location on the stack
Empty stack
SP
SP
Push 12
Stack
Stack
12
12
3
Push 3
SP
5
The Stack
Stack
RAM
Stack
12
!
12
3
SP
x
7
push x
3
!
y 14
!
7
SP
RAM
!
x
7
!
y 14
!
6
3
3/12/23
The Stack
Stack
RAM
Stack
RAM
12
!
12
!
x
3
7
pop y
SP
x
!
SP
7
!
y 14
y
!
3
!
7
The Stack
• Apply f on the stack:
•
F
•
pu
• Pop arguments from the stack
• Compute f of arguments
• Push result onto the stack
8
4
3/12/23
Stack Arithmetic
Stack
12
3
Stack
12
add
10
Stack
SP
7
12
neg
−10
SP
SP
9
Stack Logic
Stack
Stack
False
5
5
False
EQ
True
True
OR
SP
SP
SP
10
5
3/12/23
Stack Manipulation
• High-level
x = 17 + 19
• Lower-level push 17
•
push 19
add
pop x
pu
11
Stack Arithmetic
• VM code:
•
// d = (2 – x) + (y + 9)
push 2
push x
sub
push y
push 9
add
add
pop d
pu
12
6
3/12/23
Stack Arithmetic
Stack
RAM
!
x
Stack
Stack
2
SP
2
push 2 SP
7
push x
y 12
7
Stack
sub
−5
SP
SP
!
!
Stack
Stack
−5
−5
push y
Stack
push 9
12
−5
add
12
9
SP
Stack
21
16
add
SP
SP
SP
13
Stack Arithmetic
Stack
Stack
16
SP
RAM
!
SP
pop d
x
7
y 12
!
d 16
!
14
7
3/12/23
Stack Logic
// (x < 7) OR (y == 8) RAM
!
push x
x 10
push 7
y 8
LT
!
push y
!
push 8
EQ
OR
push y
8
Stack
10
push x SP
10
push 7
7
SP
Stack
Stack
False
False
SP
Stack
Stack
Stack
LT
Stack
SP
False
False
push 8
8
SP
8
Stack
EQ
True
True
OR SP
SP
SP
15
Arithmetic/Logic Commands
Command Return value Return type
add
x+ y
int
sub
x− y
int
neg
−y
int
EQ
x==0
bool
GT
x> y
bool
LT
x< y
bool
AND
x AND y
bool
OR
x OR y
bool
NOT
NOT y
bool
Any arithmetic/Logic expression may be expressed and evaluated by
applying a sequence of the above operators on a stack
16
8
3/12/23
Memory Segments
LOCAL
ARGUMENT
THIS
THAT
CONSTANT
STATIC
POINTER
TEMP
17
Memory Segments
Source code:
VM translator
Class Foo{
static int s1, s2
function int Bar(int x, int y){
var int a, b, c
…
let c = s1 + y
…
argument
}
x
0
}
0
y
VM code:
Final VM code:
…
push s1
push y
add
pop c
…
…
push static 0
push argument 1
add
pop local 2
…
local
static
constant
a
0
s1
0
s2
0
1
b
1
1
1
2
2
c
2
2
2
3
3
3
3
3
1
Variable types:
• Argument variables: x, y
• Local variables: a, b, c
• Static variables: s1, s2
18
9
3/12/23
Memory Segments
• Syntax: push/pop segment i
• Push constant 17
• Pop local 2
• Pop static 5
• Push argument 3
• Syntax: push segment i
• Where segment is: argument, local, static, constant, this, that,
pointer, temp
• i is a non-negative integer
• Syntax: pop segment i
•
• Where segment is: argument, local, static, this, that, pointer,
temp (not constant)
• i is a non-negative integer
pu
19
Memory Segments
• Write the assembly code:
Stack
•
52
−3
SP
argument
pu
7
local
static
constant
−3
0
2
0
1 12
1 982
1
2
2
0
3
5
0
3
54
let static 2 = argument 1
0
54
1
1
2 171
2
2
3 9862
3
3
or
push argument 1
pop static 2
Stack
SP
argument
local
static
constant
52
0
7
0
−3
0
2
0
−3
1
12
1 982
1
54
1
1
2
5
2
54
2
12
2
2
3 9862
3
3
3
3
0
20
10
3/12/23
The Stack
257
p
1 1024
q
0
2
1765
!
!
256
19
257
23
258
903
!
!
1024
5
1025
12
Pseudo assembly code:
D = *p // D becomes 23
p -- // decrement p
D = *p // D becomes 19
*q = 9 // RAM[1024] becomes 9
q++ // increment q
1026 −3
!
21
The Stack
• Notation
•
pu
*p // the memory location that p points at
x++ // increment: x = x + 1
x-- // decrement: x = x – 1
22
11
3/12/23
The Stack
• Abstraction:
•
pu
Stack
Stack
12
5
12
push constant 17
5
17
SP
SP
• Assumptions: SP is stored in RAM[0]
• Stack base address = 256
23
The Stack
• Implementation
RAM
0
258
1
!
SP
2
0
259
1
!
2
push constant 17
!
!
256
12
256
257
5
257
5
258
17
258
•
Logic: *SP = 17, SP++
RAM
12
pu
SP
Hack assembly code:
@17 // D = 17
D =A
@SP // *SP = D
A=M
M=D
@SP // SP++
M=M+1
24
12
3/12/23
The Stack
VM code:
push constant i
VM translator
Assembly code:
*SP = i, SP++
–or–
@i // D = i
D =A
@SP // *SP = D
A=M
M=D
@SP // SP++
M=M+1
25
Memory Segments
• Syntax: push/pop local i
RAM
0
258
SP
local
1
1015
LCL
12
7
2
!
5
−91
!
!
Stack
SP
•
256
12
3
257
5
!
258
Address following
address
stack’s top value
Base address of
local segment
pu
!
!
1015
7
1016
−91
1017
3
!
!
26
13
3/12/23
Memory Segments
• Abstraction
Stack
Stack
12
12
5
Pop local 2
local
SP
0
!
1
!
2
SP
5
!
•
pu
27
Memory Segments
RAM
RAM
0
258
SP
0
257
SP
1
1015
LCL
1
1015
LCL
2
!
2
!
!
!
!
!
256
12
256
12
257
5
257
5
258
Pop local 2
258
!
!
!
!
1015
!
1015
!
1016
!
!
1016
1017 !
1017
5
!
!
!
!
28
14
3/12/23
Memory Segments
• Just replace 2 by i
• Implementation: addr = LCL + i
SP-*addr = *SP
• VM code:
pop local i
push local i
•
VM translator
addr = LCL + i, SP--, *addr = *SP
addr = LCL + i, *SP = *addr, SP++
pu
29
Memory Segments
• Syntax: push/pop segment i
Stack
12
pop
5
SP
•
pu
local
argument
this
that
push
30
15
3/12/23
Memory Segments
• When translating high-level code of some
method into VM code, the compiler:
• Maps the method’s local and argument
variables onto the local and argument segments
• Maps the object fields and array entries that the
method is currently processing onto the this and
that segments
31
•
pu
Memory Segments
pop segment i
push segment i
VM translator
addr = segmentPointer + i, SP--, *addr = *SP
addr = segmentPointer + i, *SP = *addr, SP++
segment = {local, argument, this, that}
RAM
0
!
1
!
LCL
2
!
ARG
3
!
THIS
4
!
THAT
SP
Segment pointers holding
base addresses of segments
32
16
3/12/23
Memory Segments
• Constant segment:
VM code:
VM translator
push constant i
(no pop constant i)
*SP = i, SP++
33
Memory Segments
• Static segment:
VM code:
// file foo.vm
…
pop static 5
…
pop static 2
…
static i
VM translator
VM translator
RAM
SP
0
…
// D = stack.pop
@foo.5
M=D
…
// D = stack.pop
@foo.2
M=D
…
1
LCL
2
ARG
3
THIS
4
THAT
5
!
!
16
17
!
static variables
255
256
foo.i
Mapped toRAM[16]
34
17
3/12/23
Memory Segments
• Temp segment:
We sometimes need temporary storage
We provide 8 temporary variables
RAM
0
SP
1
LCL
2
ARG
3
THIS
4
THAT
5
VM code: VM translator Assembly code:
! !
push temp i
addr = 5 + i, *SP = *addr, SP++ 12
13
pop temp i
addr = 5 + i, SP--, *addr = *SP !
TEMP segment
255
256
35
Memory Segments
• Pointer segment:
Accessing pointer 0 results in accessing THIS
Accessing pointer 1 results in accessing THAT
VM code: VM translator Assembly code:
push pointer 0/1
*SP = THIS/THAT, SP++
pop pointer 0/1
SP--, THIS/THAT= *SP
36
18
3/12/23
VM Emulator
Jack
program
Jack
compiler
VM code
VM
emulator
VM
translator
Your PC
Hack
computer
37
VM Implementation
VM code:
push constant 2
push local 0
sub
push local 1
push constant 5
add
sub
pop local 2
…
VM translator
Assembly code:
// push constant 2
@2
D =A
@SP
A=M
M=D
@SP
M=M+1
// push local 0
…
38
19
3/12/23
Standard VM Mapping
RAM
0
SP
1
LCL
2
ARG
3
THIS
4
THAT
5
!
TEMP segment
12
13
!
15
General
purpose
registers
16
!
Static
variables
255
256
!
Stack
2047
39
VM Translator Implementation
VM translator
VM code
…
push constant 17
push local 2
add
pop argument 1
…
Assembly code
…
// push constant 17
@17
D =A
…
// push local 2
…
// add
…
// pop argument 1
40
20
3/12/23
VM Translator Implementation
• Design: 3 classes
• Parser – parses commands into lexical elements
• CodeWriter – writes assembly code implementing parsed command
• Main – drives the process (VM translator)
41
VM Translator Implementation
• Main (VM translator)
Input: filename.vm
Output: filename.asm
• Main logic
• Constructs Parser to handle input file
• Constructs CodeWriter to handle output file
• Marches through input file, parsing each line and generating
code from it
42
21
3/12/23
VM Translator Implementation
• Parser
• Handles parsing of a single .vm file
• Reads a VM command, parses into lexical components, provides
access to these to these components
• Ignores whitespace and comments
43
VM Translator Implementation
• Parser
Routine
Arguments
Returns
Function
Opens input file/stream and
prepares to parse it
Constructor
Input file/stream
–
hasMoreCommands
–
boolean
More commands in input?
Advance
–
–
Reads next command and makes
it the current command, called
only if hasMoreCommands is True
commandType
–
C_arithmetic
C_push, C_pop, etc.
Returns a constant representing the
type of current command
Argument 1
–
string
Returns first argument of current
command
Argument 2
–
int
Returns second argument of current
command
44
22
3/12/23
VM Translator Implementation
• Code Writer
Routine
Arguments
Return
Function
Constructor
output file/stream
–
Opens output file/stream and
prepares to write
writeArithmetic command (string)
–
Writes to output the assembly code
implementing arithmetic command
writePushPop
command
–
Writes assembly code implementing
push or pop
Close
–
–
Closes output file
45
23
4/6/23
Program Control
• Flow of control in a program needn’t be linear
(step-by-step)
• Could branch to a new location in the code
• Using goto commands (unconditional
branching)
• Using if-goto commands (conditional
branching)
•
pu
1
Program Control
• The basic language can be extended at will
• User-defined functions
•
pu
2
1
4/6/23
Program Control
• Consider the formula:
x = −b + b2 − 4 ⋅ a ⋅ c
• In a high-level language:
x = −b + sqrt(power(b, 2)–4*a*c))
x = −b + sqrt(power(b, 2) − 4*a*c)
• Define a function:
•
pu
x = −b + sqrt(disc(a, b, c))
3
Program Control
• Functions: sqrt, power, disc are abstractions;
not part of the basic language
• How are they implemented?
•
pu
4
2
4/6/23
Program Control
High-level code:
If (a != 0)
x = (–b + sqrt(disc(a, b, c)))/2*a;
Else
x = –c/b;
// code continues
VM pseudo code:
push a
push 0
eq
not
if-goto A_NEQ_ZERO
push c
neg
push b
call div
pop x
goto CONTINUE
label A_NEQ_ZERO
// we get here if !(a == 0)
push b
!
!
neg
push a
push b
push c
call disc
call sqrt
add
push 2
push a
call mult
call div
pop x
label CONTINUE
// code continues
5
Program Control
• Branching commands:
goto label
if-goto label
label label
• Function commands:
call functionName nVars
function functionName nArgs
return
6
3
4/6/23
Branching
• goto, if-goto, label
compiler
High-level program:
Pseudo VM code:
generates labels
// Returns x*y
function mult(x, y)
int mult(int x, int y){
push 0
int sum = 0
pop sum
int n = 1
push 1
// sum = sum + x, y times
pop n
while !(n > y){
label LOOP
sum += x
push n
n++}
push y
return sum}
gt
if-goto ENDLOOP
push sum
!
push x
add
pop sum
push n
push 1
add
pop n
goto LOOP
label ENDLOOP
push sum
return
!
7
Branching
• Compiler introduces two labels
• Unconditional branching: goto label
Jumps to execute command just after label
• Conditional branching: if-goto label
cond = pop i
If cond jump to execute command just after label
Requires pushing condition onto stack just before if-goto command
8
4
4/6/23
Branching
• goto label
Jump to command just after label
• if-goto label
cond = pop i; if cond jump to command just after label
Requires pushing a condition onto the stack just before the if-goto
command
• label label
Label declaration command
Implementation is
simple; assembly
language has similar
commands
9
Functions: Abstraction
• High-level language may be extended using
functions
• Functions: functions, subroutines,
procedures, methods, etc.
10
5
4/6/23
Functions: Abstraction
High-level program:
sqrt(x – 17 + x*5)
compiler
Pseudo VM code:
…
push x
push 17
sub
push x
push 5
call Math.multiply
add
call Math.sqrt
…
11
Functions: Abstraction
push x
SP
x
push 17
x
sub
17
SP
x – 17
SP
SP
push x
x – 17
push 5
x
x – 17
call Math.multiply
x*5
x
5
SP
x – 17
SP
SP
add
x – 17 + x*5
SP
call Math.sqrt
sqrt(x – 17 + x*5)
SP
12
6
4/6/23
Functions: Abstraction
High-level program:
compiler
// Returns x*y
int mult(int x, int y){
int sum = 0;
int n = 1;
// sum = sum + x, y times
while !(n > y){
sum += x;
n++;}
return sum}
Pseudo VM code:
function mult(x, y)
push 0
pop sum
push 1
pop n
label LOOP
push n
push y
gt
if-goto END
push sum
!
!
push x
add
pop sum
push n
push 1
add
pop n
goto LOOP
label END
push sum
return
13
Functions: Abstraction
Number of local variables
Final VM code:
local
!
function mult 2 // 2 local variables
0
sum
push argument 0
1
n
push constant 0 // sum = 0
add
pop local 0
pop local 0
push constant 1 // n = 1
push local 1 // n++
argument
pop local 1
push
constant
1
0
x
label LOOP
y
1
add
push local 1 // if !(n > y) goto END
pop local 1
push argument 1
goto LOOP
gt
label END
if-goto END
push local 0 // return sum
push local 0
return
!
14
7
4/6/23
Functions: Abstraction
// computes 3 + 5*8
of
function main 0 Number
local variables
1
push constant 3
2
push constant 8
3
push constant 5
4
call mult 2 Number of
5
add
arguments
6
pushed onto stack
return
0
“Caller”
“Callee”
// Computes the product of two arguments
function mult 2
1
push constant 0
pop local 0
2
3
push constant 1
4
pop local 1
5 label LOOP
6
push local 1
7
push argument 1
// computes the product into local 0
19 label END
20
push local 0
21
return
0
15
Functions: Abstraction
“Main view”
“Mult view”
After line 3 of main is executed:
stack
After line 0 of mult is executed:
local
stack
argument
3
8
5
0
1
After line 4 of main is executed:
stack
3
40
replaces arguments
on return
After line 5 of main is executed:
stack
43
8
5
0
0
0
1
After line 7 of mult is executed:
stack
argument
1
0
5
1
8
5
local
0
1
0
1
After line 20 of mult is executed:
stack
40
argument
0
1
8
5
local
0
1
40
6
16
8
4/6/23
Functions: Abstraction
• VM language features
• Primitive operations (fixed)
add, sub, etc.
• Abstract operations (extensible)
multiply, sqrt, etc.
• Abstract operations have the same “look and
feel”
• Push arguments onto stack; call function;
arguments disappear, result appears on top of
stack
17
Functions: Abstraction
• Implementation
For each function call, the implementation has to:
• Pass parameters from the caller to the callee (arguments)
• Determine the return address in the caller’s code
• Save the caller’s return address, stack, memory segments (caller’s state)
• Jump to execute the called function
For each function return, the implementation has to:
• Return to the caller the value computed by the callee (callee must push
a return value)
• Recycle memory resources used by callee
• Reinstate the caller’s stack and memory segments (caller’s state)
• Jump to the return address in the caller’s code
18
9
4/6/23
Call and Return: Preview
• Calling chain: foo > bar > sqrt > …
• Each function must maintain the function’s state
Compiler
• During run-time each function uses working stack and memory
segments
• Working stack and some segments should be:
•
•
•
Created when the function starts running
Maintained while the function is executing
Recycled when the function returns
• Calling pattern is “LIFO” (last-in first-out) like a stack
19
Call and Return: Preview
Caller:
function main 0
push constant 3
push constant 8
call mult 2
add
return
Callee:
function mult 2
push constant 0
pop local 0
Compiler
…
label LOOP
push local 1
// computes product
label END
push local 0
return
20
10
4/6/23
Call and Return: Preview
Caller
Callee
stack
memory segments
stack
push
push
pop
SP
memory segments
pop
SP
21
Call and Return: Preview
• Example: compute mult(17, 212)
• “Big picture”
Caller’s stack before
Caller’s stack after
stack
stack
value
value
value
Call mult 2
value
…
…
17
3604
212
SP
SP
• Effect: the function’s arguments are
replaced by the function’s value
22
11
4/6/23
Call and Return: Preview
Call foo nArgs
stack
value
value
…
Working stack
of caller
value
ARG
value
nArgs
argument 0
argument 1
…
VM implementation:
• Sets ARG (pointer, base address of
segment)
• Saves caller’s frame (stack and
memory segments)
• Jumps to execute foo
return address
saved LCL
saved ARG
saved THIS
saved frame
of caller
saved THAT
SP
23
Call and Return: Preview
…
states of other functions
up the calling chain
…
value
value
…
ARG
Many similar “blocks”
Up chain
working stack of
caller
argument 0
argument 1
value
value
…
nArgs
return address
saved LCL
saved ARG
saved THIS
saved frame of
caller
saved THAT
0
0
LCL
…
“block”
nVars
…
value
copy to argument 0
(arguments replaced
by return value)
working stack of
callee
VM implementation:
• Sets up the local segment
of the called function
return value
SP
24
12
4/6/23
Call and Return: Preview
Function foo nVars
VM implementation
• Sets up local segment of called function – push nVars zeros onto stack
Return VM implementation
• Copy return value onto argument 0
• Restore segment pointers of caller
Abstraction:
• Clears the stack
call foo ( x1, x2,…)
• Sets SP for caller (just after argument 0)
stack
stack
• Jump to return address in caller’s code
foo ( x1, x2,…)
x1
x2
SP
…
…
SP
25
Call and Return: Simulation
Recursion: the factorial function
// Tests the factorial function Pseudo VM code:
call factorial
function main
int main(){
call mult
push 3
return factorial(3);
return
call factorial
}
return
label BASECASE
// Returns n!
function factorial(n) push 1
int factorial(int n){
return
push n
if (n == 1)
function mult(a, b)
push 1
return 1;
// code omitted
eq
else
if goto BASECASE
return n*factorial(n – 1);
push n
}
push n
push 1
sub
VM program:
function main 0
push constant 3
call factorial 1
return
function factorial 0
push argument 1
push constant 1
eq
if goto BASECASE
push argument 0
push argument 0
push constant 1
sub
call factorial 1
call mult 2
return
label BASECASE
push constant 1
return
function mult 2 // code omitted
26
13
4/6/23
Call and Return: Simulation
Recursion: the factorial function
function main 0
call factorial 1
+ return
function factorial 0
push argument 0
push constant 1
eq
if goto BASECASE
push argument 0
push argument 0
push constant 1
sub
call factorial 1
× ∗ call mult 2
return
label BASECASE
push constant 1
return
main: 3
saved
+
main
frame
f(3): 3
f(3): 2
saved
f(3)
frame
f(2): 2
f(2): 1
saved
f(2)
frame
f(1): 1
argument 0
argument 0+
argument 0 ∗
27
Call and Return: Simulation
Recursion: the factorial function
main: 3
saved
+
main
frame
f(3): 3
f(3): 2
saved
f(3)
frame
f(2): 2
f(2): 1
saved
f(2)
frame
f(1): 1
argument 0
argument 0+
argument 0+
argument 0 ∗
main: 3
saved
main
frame
f(3): 3
f(3): 2
saved
f(3)
frame
f(2): 2
argument 0
argument 0+
main: 3
saved
main
frame
f(3): 3
f(3): 2
argument 0
argument 0+
main: 3
saved
main
frame
6
argument 0
6
copy
copy
get
return
address
Caller:
• Pushed 3
• Called factorial
• Got 6
28
14
4/6/23
Call and Return: Implementation
caller
VM code:
function Foo.main 4
// Computes –(19*(local 3))
push constant 19
VM translator
push local 3
call Bar.mult 2
neg
callee
…
function Bar.mult 2
// returns product of 2 arguments
// result in local 1
…
push local 1
return
VM commands:
• call functionName nArgs
• function functionName nVars
• return
(Foo.main)
// assembly code handling setup for function’s execution
…
// assembly code handling push constant 19
// assembly code handling push local 3
// assembly code saving caller’s state
// setup for function call
goto Bar.mult // in assembly
(Foo$ret.1)
// assembly code handling neg
…
(Bar.mult)
// assembly code handling function execution
…
// assembly code handling push local 1
// assembly code moving return value to caller
// reinstate caller’s state
goto Foo$ret.1 // in assembly
29
Call and Return: Implementation
Caller’s view:
• Before calling, push as many arguments as the function expects to get
• Next, invoke the function using call function nArgs
• After called function returns, arguments disappear from the stack and the return value
(mandatory) appears on the top of the stack
• After call returns, all memory segments are exactly the same as before the call (except
that temp is undefined and some values in the static segment may have changed)
Callee’s view:
• Before executing, argument segment has been initialized with argument values passed
by caller
• Local segment is allocated and initialized to zeros
• Static segment is set to static segment of VM file (segments for THIS, THAT, pointer,
and temp are undefined)
• Working stack is empty
• Before returning, must push a value onto the stack
30
15
4/6/23
Call and Return: Implementation
VM command: call functionName nArgs – calls function
functionName where nArgs arguments are pushed onto the stack
Assembly code:
push returnAddress // using label declared below
push LCL // save LCL of caller
push ARG // save ARG of caller
push THIS // save THIS of caller
push THAT // save THAT of caller
ARG = SP–5*nArgs // reposition ARG
LCL = SP // reposition LCL
goto functionName // transfer control to called function
(returnAddress) // declares a label for the return address
31
Call and Return: Implementation
ARG
SP
return value
States of functions
up the call chain
value
value
…
value
value
…
return addr
Saved LCL
Saved ARG
Saved THIS
Saved THAT
SP
0
0
LCL
argument 0
argument 1
nArgs
local 0
recycled
Copy return value
local 1
…
value
value
…
working stack
of callee
value
return value
SP
32
16
4/6/23
Call and Return: Implementation
Handling Function
VM command: function functionName nVars
(here starts a function with nVars local variables)
Assembly code
(functionName) // declares a label for function entry
repeat nVars times: // nVars is number of local variables
push 0 // initialize local variables to zero
33
Call and Return: Implementation
Handling Return
VM command: return
Assembly code
enddFrame = LCL // endFrame is a temporary variable
returnAddr = *(endFrame – 5) // gets return address
*ARG = pop() // repositions return value for caller
SP = ARG + 1 // repositions SP of caller
THAT = *(endFrame – 1) // restores THAT of caller
THIS = *(endFrame – 2) // restores THIS of caller
ARG = *(endFrame – 3) // restores ARG of caller
LCL = *(endFrame – 4) // restores LCL of caller
goto returnAddr // goto return address in caller’s code
34
17
4/6/23
VM Implementation: the Hack Platform
myProg directory
myProg directory
Foo.jack
Foo.vm
class Foo{
function main{…}
method bla{…}
}
function Foo.main
…
function Foo.bla
…
compiler
Bar.jack
class Bar{
constructor new{…}
method bla{…}
}
Bar.vm
function Bar.new
…
function Bar.bla
…
myProg directory
myProg.asm
(Foo.main)
…
(Foo.bla)
…
VM translator (Bar.new)
…
(Bar.bla)
…
35
VM Implementation: the Hack Platform
Ø JackCompiler directoryName – compiling a program directory
Ø VMTraslator diectoryName – translating a program directory
VM programming convention
One file in any VM program is expected to be named Main.vm;
one VM function in this file is expected to be named main
VM implementation convention
When the VM implementation starts running, or is reset, it starts
executing the argument-less OS function Sys.init;
Sys.init then calls Main.main and enters an infinite loop
36
18
4/6/23
VM Implementation: the Hack Platform
Hardware platform convention
The code below should be put in Hack ROM starting at address 0
// Bootstrap code (should be written in assembly)
SP = 256
call Sys.init
37
VM Implementation: the Hack Platform
Standard mapping
0
!
0
SP
1
LCL
2
ARG
3
THIS
4
THAT
5
!
temporary
segment
12
13
14
15
!
general
purpose
registers
!
!
!
255
static
variables
VM
implementation
256
!
stack
2048
!
heap
16383
static
variables
16384
!
24576
256
2047
16
2047
16
255
15
pointers
and
registers
stack
24577
!
32767
memory
mapped
I/O
unused
memory
space
38
19
4/6/23
VM Implementation: the Hack Platform
Proposed VM Translator Implementation
Three classes:
• Parser – parses eachVM command into its lexical elements
• CodeWriter – writes the assembly code that implements the parsed
command
• Main – drives the process
39
20
3/15/23
Jack Language
• In a nutshell:
•
• A simple Java-like language
• Object oriented, no inheritance
• Multi-purpose
• Lends itself to interactive apps
• Easily learned
pu
• How high-level languages:
•
• Are designed
• Handle primitive types and class types
• Create, represent, dispose objects
• Deal with strings, arrays, lists
• Interface with the host OS
pu
1
Jack Language
• Example: Hello world
•
pu
/** Hello world program */
Class Main{
function void main(){
/* Prints some text using the standard library */
do Output.printString(“Hello world!”);
do Output.println(); // New line
return;
}
}
2
1
3/15/23
Jack Language
• Comments
•
pu
/** API block comment */
/* Block comment */
// In-line comment
White-space: ignored
3
Jack Language
• Example: procedural processing
• Input numbers and compute their average
•
pu
class Main{
function void main(){
var Array a;
var int length;
var int i, sum;
let length = Keyboard.readInt(“How many numbers? “);
let a = Array.new(length); // constructs the array
let i = 0;
let sum = 0;
while (i < length){
let a[i] = Keyboard.readInt(“Enter a number: “);
let sum = sum + a[i];
let i = i + 1;
}
do Output.printString(“The average is “);
do Output.printInt(sum / length);
return;
}
4
2
3/15/23
Jack Language
• A Jack program is a collection of one or more
Jack classes, one of which must be named Main
• The Main class must have at least one function
named main
• Program’s entry point is Main.main
•
pu
5
Jack Language
• Features:
•
pu
Flow control:
If, if-else, while, do
Arrays:
Implemented as part of standard class library, not typed
Data types:
Primitive – int, char, boolean; Class types – OS provides
OS services:
Include Keyboard.readInt, Output.printString, Output.println
6
3
3/15/23
Object-Based Programming
• Example: Fractions
•
pu
class Fraction{
/** Constructs a reduced fraction from given numerator and denominator */
constructor Fraction new(int x, int y)
/** Accessors */
method int getNumerator()
method int getDenominator()
/** Returns the sum of this fraction and the other one */
method Fraction plus(Fraction other)
/** Disposes this fraction
method void dispose()
/** Prints this fraction in the format x / y */
method void print()
}
7
Object-Based Programming
• Example: Fractions
•
pu
// Computes and prints the sum of 2/3 and 1/5
class Main{
function void main(){
var Fraction a, b, c;
let a = Fraction.new(2, 3);
let b = Fraction.new(1, 5);
let c = a.plus(b);
do print();
return;
}
}
8
4
3/15/23
Object-Based Programming
• Example: Fractions
•
pu
/** Represents the fraction type and related operations */
class Fraction{
Field, or property, or member variable
field int numerator, denominator;
/** Accessors */
method int getNumerator(){
The only way to access field values from outside
return numerator;
the class is through accessors
}
method int getDenominator(){
return denominator;
}
// More fraction methods follow
}
9
Object-Based Programming
• Example: Fractions
•
pu
Class Foo{
…
var Fraction x;
Not allowed!
let x = Fraction.new(5, 17);
do Output.printInt(x.numerator);
OK
do Output.printInt(x.getNumerator());
…
10
5
3/15/23
Object-Based Programming
• Jack subroutines:
• – methods
• – constructors
• – functions (like static methods)
•
pu
11
Object-Based Programming
• Fractions
•
pu
Class Fraction{
field int numerator, denominator;
/** Constructs a reduced fraction from given numerator and denominator */
constructor Fraction new(int x, int y){
let numerator = x;
let denominator = y;
do reduce(); // reduces the fraction
return this; // returns the base address of the new object
}
…
this is a reference to the current object (base address);
A constructor must return the base address of the newly-created object
12
6
3/15/23
Object-Based Programming
• Fractions
•
pu
Class Fraction Continued
…
// Reduces this fraction
method void reduce(){
var int g;
let g = Fraction.gcd(numerator, denominator);
if (g > 1){
let numerator = numerator / g;
let denominator = denominator / g;
}
return;
A subroutine must terminate with a return command
}
13
Object-Based Programming
• Fractions
•
pu
Class Fraction Continued
…
function gcd(int a, int b){
var int r;
while(~(b = 0)){ // apply Euclid’s algorithm
let r = a – (b*(a / b)); // r is the remainder of integer division a / b
let a = b;
let b = r;
}
return a;
}
14
7
3/15/23
Object-Based Programming
• Fractions
•
pu
class Fraction{
field int num, denom;
/** Returns the sum of this fraction and the other one */
method Fraction plus(Fraction other){
let sumNumerators = (num*other.getDenominator()) + (other.getNumerator()*denom);
return Fraction.new(sumNumerators, denom*other.getDenominator());
} // More methods follow
}
15
Object-Based Programming
• Fractions
•
pu
class Fraction{
field int num, denom;
/** Prints fraction in the format x / y */
method void print(){
do Output.printInt(num);
do Output.printString(“/”);
do Output.printInt(denom);
return;
}
}
16
8
3/15/23
Object-Based Programming
• Fractions
•
pu
class Fraction{
field int num, denom;
/** Disposes this fraction */
method void dispose(){
do Memory.dealloc(this); // uses an OS routine to recycle the object’s memory
return;
}
}
17
Object-Based Programming
• Garbage collection:
• Jack has no garbage collection
• Objects must be disposed explicitly
•
pu
18
9
3/15/23
Object-Based Programming
• Client
code:
…
•
!
256
pu
!
var Fraction a, b;
…
let a = Fraction.new(2, 3);
let b = Fraction.new(1, 5);
!
4112
4113
2
stack
num denom
b
1
3
1
5
!
pu
a
b
!
• Client view:
num denom
a
4112
2047
2048
…
•
15087
15087
15088
5
!
heap
2
3
16383
19
List Processing
• List definition:
•
• The atom null, or
• An atom, followed by a list
pu
• Notation: (atom, list)
• Atoms: int
•
pu
str
arr
list
• Examples:
•
pu
null
()
(5, null)
(5)
(3, (5, null))
(3, 5)
(2, (3, (5, null))) (2, 3, 5)
20
10
3/15/23
List Processing
• Linked list:
•
v
pu
data
next
data
next
3
2
data next
5
v = (2, (3, (5, null))) = (2, 3, 5)
21
List Processing
• List API:
•
pu
/** Represents a linked list of integers */
class List{
/** Creates a list */
constructor List.new(int car, List cdr)
/** Prints this list */
method void print(){ }
/** Disposes this list */
method void dispose() { }
}
22
11
3/15/23
List Processing
• List API:
•
pu
// Builds, prints, and disposes a list
class Main{
function void main() {
// Creates and manipulates the list (2, (3, (5, null))) or (2, 3, 5)
var List v;
let v = List.new(5, null);
let v = List.new(3, v);
let v = List.new(2, v);
do v.print();
do v.dispose();
return;
}
}
23
List Processing
• List class:
•
pu
/** Represents a linked list of integers */
Class List{
field int data; // A list consists of a data field
field List next; // followed by a list
/** Creates a list */
constructor List new(int car, int cdr) {
let data = car;
let next = cdr;
return this;
}
}
24
12
3/15/23
List Processing
• Client code:
•
v
pu
Var List v;
Let v = List.new(5, null);
Let v = List.new(3, v);
Let v = List.new(2, v);
Equivalent to:
Var List v;
Let v = List.new(5, null);
Let v = List.new(2, List.new(3, v));
data next
v
v
v
5
data next
data next
3
5
data next
data next
data next
2
3
5
25
List Processing
• Sequential access:
•
pu
class List{
…
method void print() { // prints this list
var List current; // Creates a List variable and
let current = this; // initializes it to the first item of this list
while(~(current == null)){
do Output.printInt(current.getData());
do Output.printChar(32); // prints a space
do current = current.getNext();
}
return;
}
26
13
3/15/23
List Processing
• Recursive access:
•
pu
method dispose(){
if (~(next == null)){
do next.dispose();
}
// uses an OS routine to recycle this list
do Memory.dealloc(this);
return;
}
27
List Processing
• The RAM
•
pu
!
256
!
5267
!
2047
2048
!
3108
3109
!
5267
5268
!
14017
14018
!
v
stack
5
null
2
14017
heap
3
3108
!
16383
28
14
