From Nand to Tetris

Building a Modern Computer from First Principles

Lecture 4

Machine Language

These slides support chapter 4 of the book

The Elements of Computing Systems
By Noam Nisan and Shimon Schocken
MIT Press, 2021

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 1
Nand to Tetris Roadmap: Hardware

abstraction

machine
language
In previous projects we’ve built
developing the computer’s ALU and RAM
an assembler

abstraction
hardware platform
building a
computer abstraction
p2 p3
computer building p1
ALU, RAM abstraction
chips building
elementary
logic gates gates

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 2
Nand to Tetris Roadmap: Hardware

abstraction

machine p4
language
We will now integrate these
modules into a programmable,
developing general-purpose computer
an assembler

p5 hardware platform
abstraction
building a
computer abstraction
p2 p3
computer building p1
ALU, RAM abstraction
chips building
elementary
logic gates gates

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 3
Nand to Tetris Roadmap: Hardware

To get started, we’ll treat the computer

abstraction
as an abstraction, and learn how to use
machine
language
p4 it through its interface: the computer’s
machine language.
developing
an assembler

abstraction
hardware platform
building a
computer abstraction
p2 p3
computer building p1
ALU, RAM abstraction
chips building
elementary
logic gates gates

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 4
Nand to Tetris Roadmap: Hardware

We’ll start with a broad overview of:

abstraction

machine • Computer architectures

language
• Machine languages
developing
an assembler

abstraction
hardware platform
building a
computer abstraction
p2 p3
computer building p1
ALU, RAM abstraction
chips building
elementary
logic gates gates

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 5
Computer systems are flexible and versatile

Same hardware can run many different programs (software)

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 6
Computer systems are flexible and versatile

Same hardware can run many different programs (software)

Ada Lovelace Early symbolic program

(1843) Landmark “proof of concept” that a fixed computer
can be programmed to perfom different tasks

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 7
Computer systems are flexible and versatile

Same hardware can run many different programs (software)

Alan Turing Universal Turing Machine

(1936) Landmark paper, describing a theoretical
general-purpose computer

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 8
Computer systems are flexible and versatile

Same hardware can run many different programs (software)

John Von Neumann Landmark general-purpose computer

(1945) ENIAC, University of Pennsylvania

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 9
Computer architecture
Memory CPU

program

ALU
input output

data
registers

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 10
Computer architecture
Memory CPU
0 0101110011100110 instruction
1 1100000010010001
2 1110001011111100
instructions
... ...

ALU
input output
1100101010010101
1100100101100111 data value
0011001010101011
data ...
registers

Stored program concept

• The computer memory can store A fundamental idea in the
programs, just like it stores data history of computer science
• Programs = data.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 11
Lecture plan

Overview Symbolic programming

• Machine language • Control
• The Hack computer • Variables
• The Hack instruction set • Labels
• The Hack CPU Emulator

Programming examples The Hack Language

• Basic • Symbolic
• Iteration • Binary
• Pointers • Output
• Input
• Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 12
Machine Language

Memory CPU
Computer 0 12
1 615
(conceptual definition): 2 8828
3 3 ALU
A processor (CPU) that ... -5
manipulates a set of registers:
• CPU-resident registers
(few, accessed directly, by name) Registers
R1 10
• Memory-resident registers 136 955
(many, accessed by address) 137 20 R2 5
138 -523 


... A 137

Machine language
A formalism for accessing and manipulating registers.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 13
Registers

Memory CPU
Data registers
0 12
Hold data values 1 615
2 8828
3 3 ALU
... -5
Address register
Holds an address

Registers
Instruction register R1 10
136 955
137 20 R2 5
Holds an instruction
138 -523 


... A 137

• All these registers are… registers (containers that hold bits)

• The number and bit-width of the registers vary from one computer to another.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 14
Typical operations (using, for example, a RISC syntax)

Memory CPU
// R1  R1 + R2 0 12
add R1, R2 1 615
2 8828
// R1  R1 + 73 3 3 ALU
addi R1, 73 ... -5

// R1  R2
mov R1, R2
Registers
// R1  Memory[137]
R1 10
load R1, 137 136 955
137 20 R2 5
// if R1>0 goto 15 138 -523 


... A 137
jgt R1, 15

The syntax of machine languages varies across computers

The semantics is the same: Manipulating registers.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 15
Typical operations

Memory CPU
Which instruction should be 0 1110111100001010

executed next? 1 1100000011111110

current
2 0110111100001010 instruction
• By default, the CPU executes 3 1100000011111110
ALU
the next instruction ... 0101100011100110

• Sometimes we want to “jump”

to execute another instruction
Registers
R1 000000000010010
136 0001100011011100

137 1100000011111110 R2 0000000000000101

138 0101110010001110 


... A 00000010110000

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 16
Typical operations
Branching
• Execute an instruction other than the next one
• Example: Embarking on a new iteration in a loop

Basic version Symbolic version

... ...
// Adds 1 to R1, repetitively // Adds 1 to R1, repetitively
13 addi R1,1 (LOOP)
addi R1,1
... ...
• Line numbers ... • No line numbers
27 goto 13
goto LOOP
... ... • Physical addresses • Symbolic addresses
...

Programs with symbolic references are …

• Easier to develop
• Readable
• Relocatable.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 17
Typical operations
Conditional branching
Sometimes we want to “jump” to execute an instruction,
but only if a certain condition is met

Symbolic program
// Sets R2 to abs(R1)
// R2 ← R1
mov R2,R1
// if (R2 > 0) goto cont
jgt R2,CONT
// R2 ← –R1
movi R2,0
sub R2,R1
CONT:
// Here R2 = abs(R1)
...

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 18
Program translation
Translation
Before it can be executed, a symbolic program must be translated into binary
instructions that the computer can decode and execute.

Symbolic program Binary code

// Sets R2 to abs(R1) 0101111100111100
// R2 ← R1 1010101010101010 load and
mov R2,R1 translate 1100000010101010 execute
// if (R2 > 0) goto cont 1011000010000001
jgt R2,CONT ...

// R2 ← –R1
movi R2,0
sub R2,R1
CONT:
// Here R2 = abs(R1)
...

Assembly Assembler
(language) (tool)
Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 19
Machine Language

Overview Symbolic programming

• Machine language • Control
• The Hack computer • Variables
• The Hack instruction set • Labels
• The Hack CPU Emulator

Programming examples The Hack Language

• Basic • Symbolic
• Iteration • Binary
• Pointers • Output
• Input
• Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 20
The Hack computer
Data memory Instruction memory
0 0000110011100111 0 0010101010110110
1 1000110000110000 1 1111100100101011
2 0000010011111100 2 0011101001011011
... ...
RAM ROM
address out address out

... ... (Conceptual, partial view of the

32766 32766 Hack computer architecture)
32767 0000011100110010 32767 1110011001011001

Address register Data register

A 0001101001101111 D 1001000011110101

Hack: a 16-bit computer, featuring two memory units

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 21
Memory
Data memory Instruction memory
0 0000110011100111 0 0010101010110110
1 1000110000110000 1 1111100100101011
2 0000010011111100 2 0011101001011011
... ...
RAM ROM
address out address out
0000111100110010

... ... (Conceptual, partial view of the

M 32766 Hack computer architecture)
32766
32767 0000011100110010 32767 1110011001011001

Address register Data register

A 0001101001101111 D 1001000011110101

RAM
• Read-write data memory
• Addressed by the A register
• The selected memory location, RAM[A],
is referred to as M

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 22
Memory
Data memory Instruction memory
Loaded with a sequence of
0 0000110011100111 0 0010101010110110
1 1000110000110000 1 1111100100101011
16-bit Hack instructions
2 0000010011111100 2 0011101001011011
... ...
RAM ROM
address out address out
0000111100110010 1001111100011001

... ... (Conceptual, partial view of the

M 32766 Hack computer architecture)
32766
32767 0000011100110010 32767 1110011001011001

Address register Data register

A 0001101001101111 D 1001000011110101

RAM ROM
• Read-write data memory • Read-only instruction memory
• Addressed by the A register • Addressed by the (same) A register
• The selected memory location, RAM[A], • The selected memory location, ROM[A],
is referred to as M contains the current instruction
Should we focus on RAM[A], or on ROM[A]?
Depends on the current instruction (later)

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 23
Registers
Data memory Instruction memory
0 0
1 1
2 2
... ...
RAM ROM

address out address out

M instruction
... ... (Conceptual, partial view of the
32766 32766 Hack computer architecture)
32767 32767

Address register Data register

A D

D: data register
A: address register
M: selected RAM register

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 24
Machine Language

Overview Symbolic programming

• Machine language • Control
• The Hack computer • Variables
• The Hack instruction set • Labels
• The Hack CPU Emulator

Programming examples The Hack Language

• Basic • Symbolic
• Iteration • Binary
• Pointers • Output
• Input
• Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 25
Hack instructions
Instruction set
• A - instruction (address)
• C - instruction (compute)

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 26
Hack instructions
Instruction set
• A - instruction (address)
• C - instruction (compute)

Syntax: Example Semantics

@ xxx
@ 19 A ← 19
where xxx is a
non-negative integer Side effects:
• RAM[A] (denoted M) becomes selected
• ROM[A] becomes selected

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 27
Hack instructions
Instruction set
• A - instruction (address)
• C - instruction (compute)

Syntax:

reg = {0 | 1 | –1} reg1 = reg2 reg = reg1 op reg2

where reg = {A | D | M} where reg1 = {A | D | M} where reg, reg1 = {A | D | M}

reg2 = [–] {A | D | M} reg2 = {A | D | M | 1}
op = {+ | – | & | I}
Examples:

D=0 D=A D=D+M

A=–1 D=M A=A–1 (Complete / formal
M=1 M=–M M=D+1 syntax, later).
... ... ...

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 28
Hack instructions
Typical instructions:
@ constant (A ← constant)

D=1 D=D+A M=D

D=A D=M D=D+A
D=D+1 M=0 M=M–D
... ... ...

Examples:
// D ← 2
The game: We show a subset of Hack instructions (top left),
? and practice writing code examples that use these instructions.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 29
Hack instructions
Typical instructions:
@ constant (A ← constant)

D=1 D=D+A M=D

D=A D=M D=D+A
D=D+1 M=0 M=M–D
... ... ...

Use only the above instructions

Examples:
// D ← 2 // D ← 1954
Use only the instructions
D=1
D=D+1 ? shown above

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 30
Hack instructions
Typical instructions:
@ constant (A ← constant)

D=1 D=D+A M=D

D=A D=M D=D+A
D=D+1 M=0 M=M–D
... ... ...

Examples:
// D ← 2 // D ← 1954 // D ← D + 23
Use only the instructions
D=1 @1954
D=D+1 D=A ? shown above

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 31
Hack instructions
Typical instructions:
@ constant (A ← constant)

D=1 D=D+A M=D

D=A D=M D=D+A
D=D+1 M=0 M=M–D
... ... ...

Examples:
// D ← 2 // D ← 1954 // D ← D + 23
D=1 @1954 @23
D=D+1 D=A D=D+A

Observation
• In all these examples, we used both D and A as a data registers:
• The addressing side-effects of A are ignored.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 32
Hack instructions
Typical instructions:
@ constant (A ← constant)

D=1 D=D+A M=D

D=A D=M D=D+A
D=D+1 M=0 M=M–D
... ... ...

More examples:
// RAM[100] ← 0 // RAM[100] ← 17
@100 @17
M=0 D=A
@100
M=D
• First pair of instructions:
A is used as a data register
• Second pair of instructions:
A is used as an address register

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 33
Hack instructions
Typical instructions:
@ constant (A ← constant)

D=1 D=D+A M=D

D=A D=M D=D+A
D=D+1 M=0 M=M–D
... ... ...

More examples:
// RAM[100] ← 0 // RAM[100] ← 17 // RAM[100] ← RAM[200]
@100 @17
M=0 D=A
@100 ?
M=D

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 34
Hack instructions
Typical instructions:
@ constant (A ← constant)

D=1 D=D+A M=D

D=A D=M D=D+A
D=D+1 M=0 M=M–D
... ... ...

More examples:
// RAM[100] ← 0 // RAM[100] ← 17 // RAM[100] ← RAM[200]
@100 @17 @200
M=0 D=A D=M
@100 @100
M=D M=D

When we want to operate on a memory location, we use a pair of instructions:

• A-instruction: Selects a memory location
• C-instruction: Operates on the selected location.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 35
Hack instructions
Typical instructions:
@ constant (A ← constant)

D=1 D=D+A M=D

D=A D=M D=D+A
D=D+1 M=0 M=M–D
... ... ...

Use only the above instructions

// RAM[3] ← RAM[3] – 15

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 36
Hack instructions
Typical instructions:
@ constant (A ← constant)

D=1 D=D+A M=D

D=A D=M D=D+A
D=D+1 M=0 M=M–D
... ... ...

Use only the above instructions

// RAM[3] ← RAM[3] – 15 // RAM[3] ← RAM[4] + 1

@15
D=A
@3
M=M–D
?

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 37
Hack instructions
Typical instructions:
@ constant (A ← constant)

D=1 D=D+A M=D

D=A D=M D=D+A
D=D+1 M=0 M=M–D
... ... ...

Use only the above instructions

// RAM[3] ← RAM[3] – 15 // RAM[3] ← RAM[4] + 1

@15 @4
D=A D=M+1
@3 @3
M=M–D M=D

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 38
Hack instructions
Typical instructions:
@ constant (A ← constant)

A=1 A=M A=D-A

D=–1 D=M D=D+A
M=0 M=D D=D+M
... ... ...

Add.asm
// Computes: RAM[2] = RAM[0] + RAM[1] + 17

? Use only the

above instructions

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 39
Hack instructions
Typical instructions:
@ constant (A ← constant)

A=1 A=M A=D-A

D=–1 D=M D=D+A
M=0 M=D D=D+M
... ... ...

Add.asm
// Computes: RAM[2] = RAM[0] + RAM[1] + 17
// D = RAM[0]
@0
D=M
// D = D + RAM[1] Use only the
@1
above instructions
D=D+M
// D = D + 17
@17
D=D+A
// RAM[2] = D
@2
M=D

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 40
Hack instructions
Typical instructions:
@ constant (A ← constant)

A=1 A=M A=D-A

D=–1 D=M D=D+A
M=0 M=D D=D+M
... ... ...

Add.asm
// Computes: RAM[2] = RAM[0] + RAM[1] + 17
// D = RAM[0]
@0 How can we tell that a given program
D=M
// D = D + RAM[1]
actually works?
@1
D=D+M • Testing / simulating
// D = D + 17
@17 • Formal verification
D=D+A
// RAM[2] = D
@2
M=D

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 41
Machine Language

Overview Symbolic programming

• Machine language • Control
• The Hack computer • Variables
• The Hack instruction set • Labels
• The Hack CPU Emulator

Programming examples The Hack Language

• Basic • Symbolic
• Iteration • Binary
• Pointers • Output
• Input
• Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 42
The CPU emulator
• Software that emulates the Hack CPU
• Part of the Nand to Tetris IDE
load/exec controls

screen

code

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 43
The CPU emulator

Add.asm (example)
// Computes: RAM[2] = RAM[0] + RAM[1] + 17
// D = RAM[0]
@0
D=M
// D = D + RAM[1]
@1
D=D+M
// D = D + 17
@17
D=D+A
// RAM[2] = D
@2
M=D

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 44
The CPU emulator

Binary
Add.asm (example)
0000000000000000
// Computes: RAM[2] = RAM[0] + RAM[1] + 17
1000010010001101
// D = RAM[0] 0000000000000001
@0 1010011001100001
D=M Load into the 0000000000010001
Execute in the
// D = D + RAM[1] CPU emulator 1001111100110011 CPU emulator
@1 0000000000000010
D=D+M 1110010010010011
// D = D + 17
@17
D=D+A When loading a symbolic program
// RAM[2] = D
into our CPU emulator, the emulator
@2
M=D translates it into binary code (using a
built-in assembler).

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 45
The CPU emulator

CPU emulator

demo

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 46
Machine Language

Overview Symbolic programming

• Machine language • Control
• The Hack computer • Variables
• The Hack instruction set • Labels
• The Hack CPU Emulator

Programming examples The Hack Language

• Basic • Symbolic
• Iteration • Binary
• Pointers • Output
• Input
• Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 47
Loading a program

Data memory Instruction memory Hack program

0 0 instruction
1
2 1 instruction
... RAM 2
ROM load instruction
... instruction
instruction
M instruction
instruction
instruction
instruction

Address register Data register

A D

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 48
Loading a program

Data memory Instruction memory Hack program

0 0 instruction instruction
1
2 1 instruction instruction
... RAM 2 instruction load instruction
... instruction instruction
instruction instruction
M instruction
instruction
instruction
instruction instruction
instruction instruction

Convention:
Address register Data register The first instruction is
A D loaded into address 0,
the next instruction into
address 1, and so on.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 49
Executing a program

Data memory Instruction memory

0 0 instruction
1
2 1 instruction
... RAM 2 instruction
... instruction
instruction
M instruction
instruction
instruction

Address register Data register

A D

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 50
Executing a program

Data memory Instruction memory

0 0 instruction
1
2 1 instruction
... RAM 2 instruction
... instruction
instruction
M instruction
instruction
instruction

Address register Data register

A D

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 51
Executing a program

Data memory Instruction memory

0 0 instruction
1
2 1 instruction
... RAM 2 instruction
... instruction
instruction
M instruction
instruction
instruction

Address register Data register

A D

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 52
Executing a program

Data memory Instruction memory

0 0 instruction
1
2 1 instruction
... RAM 2 instruction
... instruction
instruction
M instruction
instruction
instruction

Address register Data register

A D

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 53
Executing a program

Data memory Instruction memory

0 0 instruction
1
2 1 instruction
... RAM 2 instruction
... instruction
instruction
M instruction
instruction
instruction

Address register Data register

A D

• The default: Execute the next instruction

• Suppose we wish to execute another instruction;
• How to specify branching?

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 54
Branching

Unconditional branching
example (pseudocode)

0 instruction
1 instruction
2 instruction
Flow of control:
3 instruction 0,1,2,3,4,
4 goto 7 7,8,9,
5 instruction
2,3,4,
6 instruction
7 instruction 7,8,9,
8 instruction 2,3,4,
9 goto 2 ...
10 instruction
11 ...

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 55
Branching

Unconditional branching
example (pseudocode)

0 instruction
In Hack:
1 instruction
2 instruction
3 instruction …
// goto 7 Syntax:
4 goto 7
5 instruction @7 • Use an A-instruction to select an address
6 instruction 0;JMP • Use a C-instruction to jump to that address
7 instruction …
8 instruction Semantics of 0;JMP
9 goto 2 Jump to execute the instruction stored in ROM[A]
10 instruction (the 0; prefix is a syntax convention)
11 ...

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 56
Branching

Conditional branching
example

Pseudocode In Hack Typical branching instructions:

0 instruction D;JGT // if D > 0 jump

1 instruction …
2 if (D > 0) goto 6 // if (D > 0) goto 6
3 instruction @6 to the
D;JGT instruction
4 instruction
… stored in
5 instruction
ROM[A]
6 instruction
7 instruction
... ...

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 57
Branching

Conditional branching
example

Pseudocode In Hack Typical branching instructions:

0 instruction D;JGT // if D > 0 jump

1 instruction …
D;JGE // if D ≥ 0 jump
2 if (D > 0) goto 6 // if (D > 0) goto 6
@6 D;JLT // if D < 0 jump to the
3 instruction
D;JGT D;JLE // if D ≤ 0 jump instruction
4 instruction
… stored in
5 instruction D;JEQ // if D = 0 jump ROM[A]
6 instruction
7 instruction D;JNE // if D ≠ 0 jump
... ... 0;JMP // jump

D can be replaced with any ALU computation: D+1, D-1, etc.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 58
Branching
Typical instructions:
@ constant (A ← constant)

A=1 A=M D=D-A

D=-1 D=A A=A-1
M=0 M=D M=D+1
... ... ...

Use only the above instructions

Typical branching instructions:
// if )D = 0( goto 300 D;JGT // if D > 0 jump
D;JGE // if D ≥ 0 jump
? D;JLT // if D < 0 jump to the
D;JLE // if D ≤ 0 jump instruction
stored in
D;JEQ // if D = 0 jump ROM[A]
D;JNE // if D ≠ 0 jump
0;JMP // jump

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 59
Branching
Typical instructions:
@ constant (A ← constant)

A=1 A=M D=D-A

D=-1 D=A A=A-1
M=0 M=D M=D+1
... ... ...

Use only the above instructions

Typical branching instructions:
// if )D = 0( goto 300 D;JGT // if D > 0 jump
@300 D;JGE // if D ≥ 0 jump
D;JEQ
D;JLT // if D < 0 jump to the
D;JLE // if D ≤ 0 jump instruction
stored in
D;JEQ // if D = 0 jump ROM[A]
D;JNE // if D ≠ 0 jump
0;JMP // jump

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 60
Branching
Typical instructions:
@ constant (A ← constant)

A=1 A=M D=D-A

D=-1 D=A A=A-1
M=0 M=D M=D+1
... ... ...

Use only the above instructions

Typical branching instructions:
// if (RAM[3] < 100) goto 12 D;JGT // if D > 0 jump
D;JGE // if D ≥ 0 jump
? D;JLT // if D < 0 jump to the
D;JLE // if D ≤ 0 jump instruction
stored in
D;JEQ // if D = 0 jump ROM[A]
D;JNE // if D ≠ 0 jump
0;JMP // jump

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 61
Branching
Typical instructions:
@ constant (A ← constant)

A=1 A=M D=D-A

D=-1 D=A A=A-1
M=0 M=D M=D+1
... ... ...

Use only the above instructions

Typical branching instructions:
// if (RAM[3] < 100) goto 12 D;JGT // if D > 0 jump
// D = RAM[3] – 100 D;JGE // if D ≥ 0 jump
@3
D;JLT // if D < 0 jump to the
D=M
D;JLE // if D ≤ 0 jump instruction
@100
stored in
D=D–A D;JEQ // if D = 0 jump ROM[A]
// if (D < 0) goto 12
D;JNE // if D ≠ 0 jump
@12
D;JLT 0;JMP // jump

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 62
Machine Language

Overview Symbolic programming

• Machine language • Control
• The Hack computer • Variables
• The Hack instruction set • Labels
• The Hack CPU Emulator

Programming examples The Hack Language

• Basic • Symbolic
• Iteration • Binary
• Pointers • Output
• Input
• Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 63
The A - instruction

• A - instruction
• C - instruction

Syntax: Examples: Semantics:

@ xxx @ 19 A ← 19

where xxx is either a constant, or

@ sym A ← the number that sym is bound to
a symbol bound to a constant

This idiom can be used for realizing:

• Variables
• Labels

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 64
Variables
Pseudocode (example) Hack assembly
... ...
i=1 // i = 1
sum = 0
... write
sum = sum + i
i=i+1
...

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 65
Variables
Pseudocode (example) Hack assembly
... ... Symbolic programming
i=1 // i = 1 • The code writer is allowed to create and
sum = 0 @i use symbolic variables, as needed
... write M=1
• We assume that there is an agent who
sum = sum + i // sum = 0
knows how to bind these symbols to
i=i+1 @sum
sensible RAM addresses
... M=0
... • This agent is the assembler
// sum = sum + i
@i For example
D=M
@sum
• If the assembler will bind i and sum
M=D+M
to, say, 16 and 17, every instruction
@i and @sum will end up selecting
// i = i + 1
RAM[16] and RAM[17]
@i
M=M+1 • Invisible to the code writer
... • The result: a powerful, low-level,
variables abstraction.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 66
Variables
Typical instructions:
@ constant A ← constant

@ symbol A ← the constant which is bound to symbol

D=0 D=M D=D+A

M=1 A=M D=A+1
D=–1 M=D D=D+M
M=0 D=A M=M–1
... ... ...

Use only the above instructions

// sum = 0 // x = 512 // n = n – 1 // sum = sum + x

? ? ? ?

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 67
Variables
Typical instructions:
@ constant A ← constant

@ symbol A ← the constant which is bound to symbol

D=0 D=M D=D+A

M=1 A=M D=A+1
D=–1 M=D D=D+M
M=0 D=A M=M–1
... ... ...

Use only the above instructions

// sum = 0 // x = 512 // n = n – 1 // sum = sum + x

@sum @512 @n @sum
M=0 D=A M=M–1 D=M
@x @x
M=D D=D+M
@sum
M=D

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 68
Variables
Pre-defined symbols in the Hack language
RAM
symbol value
0 R0
R0 0 1 R1 16 “built-in variables” named R0…R15
R1 1 2 R2
... ...
Sometimes referred to as “virtual registers”
R2 2
15 R15
... ...
16
R15 15 17
...
32767

Example:

// Sets R1 to 2 * R0
// Usage: Enter a value in R0
@R0
D=M
@R1 The use of R0, R1, … (instead of physical addresses 0, 1, …)
M=D makes Hack code more readable.
M=D+M

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 69
Machine Language

Overview Symbolic programming

• Machine language • Control
• The Hack computer • Variables
• The Hack instruction set • Labels
• The Hack CPU Emulator

Programming examples The Hack Language

• Basic • Symbolic
• Iteration • Binary
• Pointers • Output
• Input
• Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 70
Labels
Example (pseudocode) Hack assembly
i = 1000 // i = 1000
Label declaration in the Hack
LOOP: @1000 assembly language:
if (i = 0) goto CONT D=A
(sym)
i = i - 1 @i
goto LOOP M=D Results in binding sym to the
write (LOOP) address of the next instruction
CONT:
... // if (i = 0) goto CONT
@i
D=M In this example:
@CONT
D;JEQ
LOOP is bound to 4
// i = i - 1 CONT is bound to 12
@i
(done by the assembler;
M=M-1
// goto LOOP
The code writer doesn’t care
@LOOP about these numbers)
0;JMP
(CONT)
...

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 71
Machine Language

Overview Symbolic programming

• Machine language • Control
• The Hack computer • Variables
• The Hack instruction set • Labels
• The Hack CPU Emulator

Programming examples The Hack Language

• Basic • Symbolic
• Iteration • Binary
• Pointers • Output
• Input
• Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 72
Program example 1: Add

Add.asm
// Sets R2 to R0 + R1 + 17
// D = R0
@R0
D=M
// D = D + R1
@R1
D=D+M
// D = D + 17
@17
D=D+A
// R2 = D
@R2
M=D

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 73
Program example 2: Signum
Pseudocode Signum.asm
// if R0 >= 0 then R1 = 1 // if R0 >= 0 then R1 = 1 Best practice
// else R1 = –1 // else R1 = –1
// if R0 >= 0 goto POS
When writing a (non-trivial)
if (R0 ≥ 0) goto POS
@R0 assembly program, start by
R1 = –1
goto END
D=M writing pseudocode;
write @POS
POS: D;JGE Then translate the pseudo
R1 = 1 // R1 = –1 instructions into assembly.
END: @R1
M=–1
// goto END
@END
0;JMP
(POS)
// R1 = 1
@R1
M=1
(END)

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 74
Program translation
Pseudocode Signum.asm Memory
// if R0 >= 0 then R1 = 1 // if R0 >= 0 then R1 = 1 0 @0
// else R1 = –1 // else R1 = –1 The assembler 1 D=M
if (R0 ≥ 0) goto POS // if R0 >= 0 goto POS replaces all the
@R0 symbols with 2 @8
R1 = –1
D=M physical addresses
goto END 3 D;JGE
@POS
POS: D;JGE 4 @1
R1 = 1 // R1 = –1
5 M=–1
END: @R1 Assembler /
M=–1 6 @10
// goto END loader
7 0;JMP
@END
0;JMP 8 @1
(POS) (the assembler
9 M=1
// R1 = 1 generates binary
@R1 instructions; 10
M=1 Here we show their
11
(END) symbolic versions,
for readability) 12

13

14

...

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 75
Watch out for loose ends
Pseudocode Signum.asm Memory
// if R0 >= 0 then R1 = 1 // if R0 >= 0 then R1 = 1 0 @0
// else R1 = –1 // else R1 = –1
1 D=M
if (R0 ≥ 0) goto POS // if R0 >= 0 goto POS
@R0 2 @8
R1 = –1
D=M
goto END 3 D;JGE
@POS
POS: D;JGE 4 @1
R1 = 1 // R1 = –1
5 M=–1
END: @R1
M=–1 6 @10
// goto END
7 0;JMP
@END
0;JMP 8 @1
(POS) 9 M=1
// R1 = 1
@R1 10
M=1 11
(END)
12

13

14

...

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 76
Watch out for loose ends
Pseudocode Signum.asm Memory
// if R0 >= 0 then R1 = 1 // if R0 >= 0 then R1 = 1 0 @0
// else R1 = –1 // else R1 = –1
1 D=M
if (R0 ≥ 0) goto POS // if R0 >= 0 goto POS
@R0 2 @8
R1 = –1
D=M
goto END 3 D;JGE
@POS
POS: D;JGE 4 @1
R1 = 1 // R1 = –1
5 M=–1
END: @R1
M=–1 6 @10
// goto END
7 0;JMP
@END
0;JMP 8 @1
(POS) 9 M=1
// R1 = 1
@R1 10 0111111000111110
M=1 11 1010101001011110
(END)
12 0100100110011011

13 1110010011111111
The memory is 14 0101011100110111
never empty
...

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 77
Watch out for loose ends
Pseudocode Signum.asm Memory
// if R0 >= 0 then R1 = 1 // if R0 >= 0 then R1 = 1 0 @0
// else R1 = –1 // else R1 = –1
1 D=M
if (R0 ≥ 0) goto POS // if R0 >= 0 goto POS
@R0 2 @8
R1 = –1
D=M
goto END 3 D;JGE
@POS
POS: D;JGE 4 @1
R1 = 1 // R1 = –1
5 M=–1
END: @R1
M=–1 Program 6 @10
// goto END execution:
7 0;JMP
@END
0;JMP 8 @1
(POS) 9 M=1
// R1 = 1
@R1 10 0111111000111110
M=1 11 1010101001011110
(END)
12 Malicious

13 Code

14 0101011100110111

...

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 78
Watch out for loose ends
Pseudocode Signum.asm Memory
// if R0 >= 0 then R1 = 1 // if R0 >= 0 then R1 = 1 0 @0
// else R1 = –1 // else R1 = –1
1 D=M
if (R0 ≥ 0) goto POS // if R0 >= 0 goto POS
@R0 2 @8
R1 = –1
D=M
goto END 3 D;JGE
@POS
POS: D;JGE 4 @1
R1 = 1 // R1 = –1
5 M=–1
END: @R1
M=–1 Program 6 @10
// goto END execution:
7 0;JMP
@END
0;JMP 8 @1
(POS) 9 M=1
// R1 = 1
@R1 10 0111111000111110
M=1 11 1010101001011110
(END)
12 Malicious

13 Code

14 0101011100110111

...

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 79
Terminating programs properly
Pseudocode Signum.asm
// if R0 >= 0 then R1 = 1 // if R0 >= 0 then R1 = 1
// else R1 = –1 // else R1 = –1
if (R0 ≥ 0) goto POS // if R0 >= 0 goto POS
@R0
R1 = –1
D=M
goto END
@POS
POS: D;JGE
R1 = 1 // R1 = –1
END: @R1
M=–1
// goto END
@END
0;JMP
(POS)
// R1 = 1
@R1
M=1
(END)

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 80
Terminating programs properly
Pseudocode Signum.asm
// if R0 >= 0 then R1 = 1 // if R0 >= 0 then R1 = 1
// else R1 = –1 // else R1 = –1
if (R0 ≥ 0) goto POS // if R0 >= 0 goto POS
@R0
R1 = –1
D=M
goto END
@POS
POS: D;JGE
R1 = 1 // R1 = –1
END: @R1
M=–1
// goto END
@END
0;JMP
(POS)
// R1 = 1
@R1
M=1
(END)
@END Infinite loop
0;JMP

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 81
Terminating programs properly
Pseudocode Signum.asm Memory
// if R0 >= 0 then R1 = 1 // if R0 >= 0 then R1 = 1 0 @0
// else R1 = –1 // else R1 = –1
1 D=M
if (R0 ≥ 0) goto POS // if R0 >= 0 goto POS
@R0 2 @8
R1 = –1
D=M
goto END 3 D;JGE
@POS
POS: D;JGE 4 @1
R1 = 1 // R1 = –1
5 M=–1
END: @R1
M=–1
Assembler / 6 @10
// goto END
@END loader 7 0;JMP
0;JMP 8 @1
(POS) 9 M=1
// R1 = 1
@R1 10 @10
M=1 11 0;JMP
(END)
12 0100100110011011
@END Infinite loop
0;JMP 13 1110010011111111

14 0101011100110111

...

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 82
Terminating programs properly
Pseudocode Signum.asm Memory
// if R0 >= 0 then R1 = 1 // if R0 >= 0 then R1 = 1 0 @0
// else R1 = –1 // else R1 = –1
1 D=M
if (R0 ≥ 0) goto POS // if R0 >= 0 goto POS
@R0 2 @8
R1 = –1
D=M
goto END 3 D;JGE
@POS
POS: D;JGE 4 @1
R1 = 1 // R1 = –1
5 M=–1
END: @R1
M=–1 6 @10
Program
// goto END
@END
execution: 7 0;JMP
0;JMP 8 @1
(POS) 9 M=1
// R1 = 1
@R1 10 @10
M=1 11 0;JMP
(END)
12 0100100110011011
@END
0;JMP 13 1110010011111111

14 0101011100110111

...

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 83
Terminating programs properly
Pseudocode Signum.asm Memory
// if R0 >= 0 then R1 = 1 // if R0 >= 0 then R1 = 1 0 @0
// else R1 = –1 // else R1 = –1
1 D=M
if (R0 ≥ 0) goto POS // if R0 >= 0 goto POS
@R0 2 @8
R1 = –1
D=M
goto END 3 D;JGE
@POS
POS: D;JGE 4 @1
R1 = 1 // R1 = –1
5 M=–1
END: @R1
M=–1 6 @10
Program
// goto END
@END
execution: 7 0;JMP
0;JMP 8 @1
(POS) 9 M=1
// R1 = 1
@R1 10 @10
M=1 11 0;JMP
(END)
12 0100100110011011
@END
0;JMP 13 1110010011111111

14 0101011100110111

...

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 84
Terminating programs properly
Pseudocode Signum.asm Memory
// if R0 >= 0 then R1 = 1 // if R0 >= 0 then R1 = 1 0 @0
// else R1 = –1 // else R1 = –1
1 D=M
if (R0 ≥ 0) goto POS // if R0 >= 0 goto POS
@R0 2 @8
R1 = –1
D=M
goto END 3 D;JGE
@POS
POS: D;JGE 4 @1
R1 = 1 // R1 = –1
5 M=–1
END: @R1
M=–1 6 @10
Program
// goto END
@END
execution: 7 0;JMP
0;JMP 8 @1
(POS) 9 M=1
// R1 = 1
@R1 10 @10
M=1 11 0;JMP
(END)
12 0100100110011011
@END
0;JMP 13 1110010011111111

14 0101011100110111

...

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 85
Terminating programs properly
Pseudocode Signum.asm Memory
// if R0 >= 0 then R1 = 1 // if R0 >= 0 then R1 = 1 0 @0
// else R1 = –1 // else R1 = –1
1 D=M
if (R0 ≥ 0) goto POS // if R0 >= 0 goto POS
@R0 2 @8
R1 = –1
D=M
goto END 3 D;JGE
@POS
POS: D;JGE 4 @1
R1 = 1 // R1 = –1
5 M=–1
END: @R1
M=–1 6 @10
Program
// goto END
@END
execution: 7 0;JMP
0;JMP 8 @1
(POS) 9 M=1
// R1 = 1
@R1 10 @10
M=1 11 0;JMP
(END)
12 0100100110011011
@END
0;JMP 13 1110010011111111

14 0101011100110111

...

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 86
Terminating programs properly
Pseudocode Signum.asm Memory
// if R0 >= 0 then R1 = 1 // if R0 >= 0 then R1 = 1 0 @0
// else R1 = –1 // else R1 = –1
1 D=M
if (R0 ≥ 0) goto POS // if R0 >= 0 goto POS
@R0 2 @8
R1 = –1
D=M
goto END 3 D;JGE
@POS
POS: D;JGE 4 @1
R1 = 1 // R1 = –1
5 M=–1
END: @R1
M=–1 6 @10
// goto END
7 0;JMP
@END
0;JMP 8 @1
(POS) 9 M=1
// R1 = 1
Best practice @R1 10 @10
M=1 11 0;JMP
Terminate every (END)
assembly program with 12 0100100110011011
@END
an infinite loop. 0;JMP 13 1110010011111111

14 0101011100110111

...

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 87
By the way…
Pseudocode
// if R0 >= 0 then R1 = 1
// else R1 = –1
if (R0 ≥ 0) goto POS
R1 = –1
goto END
POS:
R1 = 1
END:

Better:
// if R0 >= 0 then R1 = 1 Best practice
// else R1 = –1
R1 = -1 Optimize your pseudocode before
if (R0 < 0) goto END writing it in machine language.
R1 = 1
END:

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 88
Program example 3: Max
Pseudocode Max2.asm
// R2 = max(R0,R1) //// You do it
// if (R0 > R1) then R2 = R0
// else R2 = R1
...
write

• Start by writing the pseudocode

• Write the assembly code in a text file named Max2.asm
• Load Max2.asm into the CPU emulator
• Put some values in R0 and R1
• Run the program, one instruction at a time
• Inspect the result, R2.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 89
Machine Language

Overview Symbolic programming

• Machine language • Control
• The Hack computer • Variables
• The Hack instruction set • Labels
• The Hack CPU Emulator

Programming examples The Hack Language

• Basic • Symbolic
• Iteration • Binary
• Pointers • Output
• Input
• Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 90
Iterative processing
Example: Compute 1 + 2 + 3 + ... + N
Pseudocode
// Program: Sum1ToN (R0 represents N)
// Computes R1 = 1 + 2 + 3 + ... + R0
// Usage: put a value >= 1 in R0
i = 1
sum = 0
LOOP:
if (i > R0) goto STOP
sum = sum + i
i = i + 1
goto LOOP
STOP:
R1 = sum

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 91
Iterative processing
Example: Compute 1 + 2 + 3 + ... + N
Pseudocode Hack assembly (code continues here)
// Program: Sum1ToN (R0 represents N) // Program: Sum1ToN (R0 represents N) (STOP)
// Computes R1 = 1 + 2 + 3 + ... + R0 // Computes R1 = 1 + 2 + 3 + ... + R0 // R1 = sum
// Usage: put a value >= 1 in R0 // Usage: put a value >= 1 in R0 @sum
i = 1 // i = 1 D=M
@i @R1
sum = 0
M=1 M=D
LOOP: // sum = 0 // infinite loop
if (i > R0) goto STOP @sum (END)
sum = sum + i M=0 @END
(LOOP) 0;JMP
i = i + 1
// if (i > R0) goto STOP
goto LOOP @i
STOP: D=M
R1 = sum @R0
D=D-M
@STOP
D;JGT
// sum = sum + i
@sum
D=M
@i
D=D+M
@sum
M=D
// i = i + 1
@i
M=M+1
// goto LOOP
@LOOP
0;JMP

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 92
Machine Language

Overview Symbolic programming

• Machine language • Control
• The Hack computer • Variables
• The Hack instruction set • Labels
• The Hack CPU Emulator

Programming examples The Hack Language

• Basic • Symbolic
• Iteration • Binary
• Pointers • Output
• Input
• Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 93
Pointers
Example 1: Set the register at address addr to –1 RAM
0 1015 R0
Input: R0 holds addr 1 R1
2 R2
... ...
// Sets RAM[R0] to –1 15 R15
// Usage: Put some non-negative value in R0 16
17
@R0 ...
255
A=M
256
M=-1 ...
1012
1013
1014
In Hack, pointer-based access is realized by setting 1015 -1
desired
1016 result
the address register to the address that we want to ...
access, using the instruction:
A=…
example:
addr = 1015

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 94
Pointers
Example 2: Get the value of the register at address addr RAM
0 1013 R0
Input: R0 holds addr 1 75 R1 desired
2 R2 result
... ...
// Gets R1 = RAM[R0] 15 R15
// Usage: Put some non-negative value in R0 16
17
...

? 255
256
...
1012 512
1013 75
1014 19
1015 -17
1016 256
...

example:
addr = 1013

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 95
Pointers
Example 2: Get the value of the register at address addr RAM
0 1013 R0
Input: R0 holds addr 1 75 R1 desired
2 R2 result
... ...
// Gets R1 = RAM[R0] 15 R15
// Usage: Put some non-negative value in R0 16
17
@R0 ...
255
A=M
256
D=M ...
1012 512
@R1 1013 75
M=D 1014 19
1015 -17
1016 256
...

example:
addr = 1013

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 96
Pointers
Example 3: Set the first n words RAM
of the memory block beginning in 0 300 R0 base
address base to –1 1 5 R1 n
2 R2
Inputs: R0 (base) and R1 (n)
... ...
15 R15
16
17
...
255
256
...
300 –1
301 –1
302 –1
desired
303 –1 output
304 –1
305
...

example:
base = 300
n=5

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 97
Pointers
Example 3: Set the first n words RAM
of the memory block beginning in 0 300 R0 base
address base to –1 1 5 R1 n
2 R2
Inputs: R0 (base) and R1 (n)
... ...
15 R15
16
17
...
255
256
...
300
301
302
303
304
305
...

example:
base = 300
n=5

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 98
Pointers
Example 3: Set the first n words RAM
of the memory block beginning in 0 300 R0 base
address base to –1 1 5 R1 n
2 R2
Inputs: R0 (base) and R1 (n)
... ...
15 R15
16 0 i
17
...
255
256
...
300
301
302
303
304
305
...

example:
base = 300
n=5

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 99
Pointers
Example 3: Set the first n words RAM
of the memory block beginning in 0 300 R0 base
address base to –1 1 5 R1 n
2 R2
Inputs: R0 (base) and R1 (n)
... ...
15 R15
16 0 i
17
...
255
256
...
300 –1
301
302
303
304
305
...

example:
base = 300
n=5

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 100
Pointers
Example 3: Set the first n words RAM
of the memory block beginning in 0 300 R0 base
address base to –1 1 5 R1 n
2 R2
Inputs: R0 (base) and R1 (n)
... ...
15 R15
16 1 i
17
...
255
256
...
300 –1
301
302
303
304
305
...

example:
base = 300
n=5

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 101
Pointers
Example 3: Set the first n words RAM
of the memory block beginning in 0 300 R0 base
address base to –1 1 5 R1 n
2 R2
Inputs: R0 (base) and R1 (n)
... ...
15 R15
16 1 i
17
...
255
256
...
300 –1
301 –1
302
303
304
305
...

example:
base = 300
n=5

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 102
Pointers
Example 3: Set the first n words RAM
of the memory block beginning in 0 300 R0 base
address base to –1 1 5 R1 n
2 R2
Inputs: R0 (base) and R1 (n)
... ...
15 R15
16 2 i
17
...
255
256
...
300 –1
301 –1
302
303
304
305
...

example:
base = 300
n=5

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 103
Pointers
Example 3: Set the first n words RAM
of the memory block beginning in 0 300 R0 base
address base to –1 1 5 R1 n
2 R2
Inputs: R0 (base) and R1 (n)
... ...
15 R15
16 2 i
17
...
255
256
...
300 –1
301 –1
302 –1
303
304
305
...

example:
base = 300
n=5

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 104
Pointers
Example 3: Set the first n words RAM
of the memory block beginning in 0 300 R0 base
address base to –1 1 5 R1 n
2 R2
Inputs: R0 (base) and R1 (n)
... ...
15 R15
16 3 i
17
...
255
256
...
300 –1
301 –1
302 –1
303
304
305
...

example:
base = 300
n=5

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 105
Pointers
Example 3: Set the first n words RAM
of the memory block beginning in 0 300 R0 base
address base to –1 1 5 R1 n
2 R2
Inputs: R0 (base) and R1 (n)
... ...
15 R15
16 3 i
17
...
255
256
...
300 –1
301 –1
302 –1
303 –1
304
305
...

example:
base = 300
n=5

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 106
Pointers
Example 3: Set the first n words RAM
of the memory block beginning in 0 300 R0 base
address base to –1 1 5 R1 n
2 R2
Inputs: R0 (base) and R1 (n)
... ...
15 R15
16 4 i
17
...
255
256
...
300 –1
301 –1
302 –1
303 –1
304
305
...

example:
base = 300
n=5

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 107
Pointers
Example 3: Set the first n words RAM
of the memory block beginning in 0 300 R0 base
address base to –1 1 5 R1 n
2 R2
Inputs: R0 (base) and R1 (n)
... ...
15 R15
16 4 i
17
...
255
256
...
300 –1
301 –1
302 –1
303 –1
304 –1
305
...

example:
base = 300
n=5

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 108
Pointers
Example 3: Set the first n words RAM
of the memory block beginning in 0 300 R0 base
address base to –1 1 5 R1 n
2 R2
Inputs: R0 (base) and R1 (n)
... ...
15 R15
16 5 i
17
...
255
256
...
300 –1
301 –1
302 –1
303 –1
304 –1
305
...

example:
base = 300
n=5

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 109
Pointers
Example 3: Set the first n words RAM
of the memory block beginning in 0 300 R0 base
address base to –1 1 5 R1 n
2 R2
Inputs: R0 (base) and R1 (n)
... ...
15 R15
Pseudocode 16 5 i
// Program: PointerDemo.asm 17
// Starting at the address stored in R0, ...
// sets the first R1 words to –1 255
i=0 256
LOOP: ...
if (i == R1) goto END 300 –1
RAM[R0 + i] = -1 301 –1
i = i+1 302 –1
303 –1
goto LOOP
304 –1
END:
305
...

example:
base = 300
n=5

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 110
Pointers
Assembly code
Example 3: Set the first n words RAM
// Program: PointerDemo.asm
of the memory block beginning in 0 300 R0 base
// Starting at the address stored in R0,
address base to –1 // sets the first R1 words to –1
1 5 R1 n
2 R2
Inputs: R0 (base) and R1 (n) // i = 0
... ...
@i
15 R15
Pseudocode M=0
(LOOP) 16 5 i
// Program: PointerDemo.asm // if (i == R1) goto END 17
// Starting at the address stored in R0, @i ...
// sets the first R1 words to –1 D=M 255
i=0 @R1 256
LOOP: D=D-M ...
if (i == R1) goto END @END 300 –1
RAM[R0 + i] = -1 D;JEQ 301 –1
// RAM[R0 + i] = -1 302 –1
i = i+1
@R0 303 –1
goto LOOP D=M 304 –1
END: @i 305
A=D+M ...
M=-1
// i = i + 1
@i example:
M=M+1 base = 300
// goto LOOP
@LOOP n=5
0;JMP
(END)
@END
0;JMP
Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 111
Sneak preview to compilation: Handling arrays
High-level code (Java example) RAM
... 0 R0
// Variable declarations 1 R1
int[] arr = new int[5]; 2 R2
int sum = 0; ... ...
... 15 R15
16 5034 arr
// Enters some values into the array
17 0 sum
// (code omitted) Memory state just ...
... before executing the 75
// Sums up the array elements for loop: 76
for (int j = 0; j < 5; j++) { ...
sum = sum + arr[j]; 255
} 256
...
...
5034 100
5035 50
5036 200
5037 2
5038 7
5036
...

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 112
Sneak preview to compilation: Handling arrays
High-level code (Java example) RAM
... 0 R0
// Variable declarations 1 R1
int[] arr = new int[5]; 2 R2
int sum = 0; ... ...
... 15 R15
16 5034 arr
// Enters some values into the array
17 359 sum
// (code omitted) Memory state just ... 5 j
... after executing the 75
// Sums up the array elements for loop: 76
for (int j = 0; j < 5; j++) { ...
sum = sum + arr[j]; 255
} 256
...
...
5034 100
5035 50
5036 200
5037 2
5038 7
5036
...

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 113
Sneak preview to compilation: Handling arrays
High-level code (Java example) Hack assembly RAM
... ... 0 R0
// Variable declarations // sum = sum + arr[j] 1 R1
int[] arr = new int[5]; @arr 2 R2
int sum = 0; D=M ... ...
... 15 R15
@j
16 5034 arr
// Enters some values into the array A=D+M
17 359 sum
// (code omitted) D=M ... 5 j
... @sum 75
// Sums up the array elements M=M+D 76
Compiler ... ...
for (int j = 0; j < 5; j++) {
sum = sum + arr[j]; 255
} 256
...
...
5034 100
5035 50
5036 200
5037 2
5038 7
5036
...

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 114
Sneak preview to compilation: Handling arrays
High-level code (Java example) Hack assembly RAM
... ... 0 R0
// Variable declarations // sum = sum + arr[j] 1 R1
int[] arr = new int[5]; @arr 2 R2
int sum = 0; D=M ... ...
... 15 R15
@j
16 5034 arr
// Enters some values into the array A=D+M
17 359 sum
// (code omitted) D=M ... 5 j
... @sum 75
// Sums up the array elements M=M+D 76
Compiler ... ...
for (int j = 0; j < 5; j++) {
sum = sum + arr[j]; 255
} 256
...
...
5034 100
// Increments each array element 5035 50
for (int j = 0; j < 5; j++) { 5036 200
arr[j] = arr[j] + 1 5037 2
} 5038 7
5036
...
...

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 115
Sneak preview to compilation: Handling arrays
High-level code (Java example) Hack assembly RAM
... ... 0 R0
// Variable declarations // sum = sum + arr[j] 1 R1
int[] arr = new int[5]; @arr 2 R2
int sum = 0; D=M ... ...
... 15 R15
@j
16 5034 arr
// Enters some values into the array A=D+M
17 359 sum
// (code omitted) D=M ... 5 j
... @sum 75
// Sums up the array elements M=M+D 76
Compiler ... ...
for (int j = 0; j < 5; j++) {
sum = sum + arr[j]; 255
// arr[j] = arr[j] + 1
} 256
...
...
// Increments each array element
? 5034
5035
100
50
for (int j = 0; j < 5; j++) { 5036 200
arr[j] = arr[j] + 1 5037 2
} 5038 7
5036
...
...

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 116
Sneak preview to compilation: Handling arrays
High-level code (Java example) Hack assembly RAM
... ... 0 R0
// Variable declarations // sum = sum + arr[j] 1 R1
int[] arr = new int[5]; @arr 2 R2
int sum = 0; D=M ... ...
... 15 R15
@j
16 5034 arr
// Enters some values into the array A=D+M
17 359 sum
// (code omitted) D=M ... 5 j
... @sum 75
// Sums up the array elements M=M+D 76
Compiler ... ...
for (int j = 0; j < 5; j++) {
sum = sum + arr[j]; 255
// arr[j] = arr[j] + 1
} 256
@arr
...
... D=M 5034 100
// Increments each array element @j 5035 50
for (int j = 0; j < 5; j++) { A=D+M 5036 200
arr[j] = arr[j] + 1 M=M+1 5037 2
} ... 5038 7
5036
...
...

Every high-level array access arr[expression] in any programming language can

be compiled into Hack code that realizes the access using the low-level idiom
A = arr + expression

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 117
Machine Language

Overview Symbolic programming

• Machine language • Control
• The Hack computer • Variables
• The Hack instruction set • Labels
• The Hack CPU Emulator

Programming examples The Hack Language

• Basic • Symbolic
• Iteration • Binary
• Pointers • Output
• Input
• Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 118
The A-instruction
Instruction set
• A - instruction
• C - instruction

Syntax: Semantics:
@ xxx • Sets the A register to the xxx
• Side effects:
where xxx is either a constant, or RAM[A] becomes the selected RAM location
a symbol bound to a constant
ROM[A] becomes the selected ROM location

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 119
The C-instruction
Instruction set
• A - instruction
• C - instruction

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 120
The C-instruction
Syntax: dest = comp ; jump “dest =” and “; jump” are optional
where:
0, 1, –1, D, A, !D, !A, –D, –A, D+1, A+1, D–1, A–1, D+A, D–A, A–D, D&A, D|A
comp = M, !M, –M, M+1, M–1, D+M, D–M, M–D, D&M, D|M

dest = null, M, D, DM, A, AM, AD, ADM M stands for RAM[A]

jump = null, JGT, JEQ, JGE, JLT, JNE, JLE, JMP

Semantics
Computes the value of comp and stores the result in dest;
If (comp jump 0), branches to execute ROM[A]

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 121
The C-instruction
Syntax: dest = comp ; jump “dest =” and “; jump” are optional
where:
0, 1, –1, D, A, !D, !A, –D, –A, D+1, A+1, D–1, A–1, D+A, D–A, A–D, D&A, D|A
comp = M, !M, –M, M+1, M–1, D+M, D–M, M–D, D&M, D|M

dest = null, M, D, DM, A, AM, AD, ADM M stands for RAM[A]

jump = null, JGT, JEQ, JGE, JLT, JNE, JLE, JMP

Semantics
Computes the value of comp and stores the result in dest;
If (comp jump 0), branches to execute ROM[A]

Examples:
// Sets the D register to -1
D=-1

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 122
The C-instruction
Syntax: dest = comp ; jump “dest =” and “; jump” are optional
where:
0, 1, –1, D, A, !D, !A, –D, –A, D+1, A+1, D–1, A–1, D+A, D–A, A–D, D&A, D|A
comp = M, !M, –M, M+1, M–1, D+M, D–M, M–D, D&M, D|M

dest = null, M, D, DM, A, AM, AD, ADM M stands for RAM[A]

jump = null, JGT, JEQ, JGE, JLT, JNE, JLE, JMP

Semantics
Computes the value of comp and stores the result in dest;
If (comp jump 0), branches to execute ROM[A]

Examples:
// Sets D and M to the value of the D register, plus 1
DM=D+1

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 123
The C-instruction
Syntax: dest = comp ; jump “dest =” and “; jump” are optional
where:
0, 1, –1, D, A, !D, !A, –D, –A, D+1, A+1, D–1, A–1, D+A, D–A, A–D, D&A, D|A
comp = M, !M, –M, M+1, M–1, D+M, D–M, M–D, D&M, D|M

dest = null, M, D, DM, A, AM, AD, ADM M stands for RAM[A]

jump = null, JGT, JEQ, JGE, JLT, JNE, JLE, JMP

Semantics
Computes the value of comp and stores the result in dest;
If (comp jump 0), branches to execute ROM[A]

Examples:
// If (D-1 = 0) jumps to execute the instruction stored in ROM[56]
@56
D-1;JEQ

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 124
The C-instruction
Syntax: dest = comp ; jump “dest =” and “; jump” are optional
where:
0, 1, –1, D, A, !D, !A, –D, –A, D+1, A+1, D–1, A–1, D+A, D–A, A–D, D&A, D|A
comp = M, !M, –M, M+1, M–1, D+M, D–M, M–D, D&M, D|M

dest = null, M, D, DM, A, AM, AD, ADM M stands for RAM[A]

jump = null, JGT, JEQ, JGE, JLT, JNE, JLE, JMP

Semantics
Computes the value of comp and stores the result in dest;
If (comp jump 0), branches to execute ROM[A]

Examples:
// goto LOOP
@LOOP
0;JMP // The 0; prefix is a syntax convention

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 125
Recap: A-instructions and C-instructions
They normally come in pairs:

// RAM[5] = RAM[5] - 1
@5 To set up for a C-instruction that operates on M,
M=M-1
Use an A-instruction to select the target address

// if D=0 goto 100

@100 To set up for a C-instruction that specifies a jump,
D;JEQ Use an A-instruction to select the target address

Observation: It makes no sense that a C-instruction will use the same address to
access the data memory and the instruction memory simultaneously;
Best practice rule
A C-instruction should specify either M, or a jump directive, but not both
Syntax convention: A C-instruction that mentions M should not have
a jump directive, and vice versa

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 126
Machine Language

Overview Symbolic programming

• Machine language • Control
• The Hack computer • Variables
• The Hack instruction set • Labels
• The Hack CPU Emulator

Programming examples The Hack Language

• Basic • Symbolic
• Iteration • Binary
• Pointers • Output
• Input
• Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 127
Hack machine language specification
Two versions
• Symbolic
• Binary

The binary specification is not intended for writing low-level programs;

It is intended for writing assemblers (chapter 6).
We describe it here, for completeness.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 128
The Hack language specification
Symbolic: @xxx (xxx is a decimal value ranging from 0 to 32767,
A instruction or a symbol bound to such a decimal value)
Binary: 0 vv vvv vvv vvv vvv v (vv ... v = 15-bit value of xxx)

Symbolic: dest = comp; jump (comp is mandatory.

C instruction If dest is empty, the = is omitted;
If jump is empty, the ; is omitted)
Binary: 11 1ac ccc ccd ddj jj

comp c c c c c c dest d d d Effect: store comp in:

0 1 0 1 0 1 0 null 0 0 0 the value is not stored
1 1 1 1 1 1 1 M 0 0 1 RAM[A]
Predefined symbols: –1 1 1 1 0 1 0 D 0 1 0 D register (reg)
symbol value D 0 0 1 1 0 0 DM 0 1 1 RAM[A] and D reg
R0 0 A M 1 1 0 0 0 0 A 1 0 0 A reg
R1 1 !D 0 0 1 1 0 1 AM 1 0 1 A reg and RAM[A]
R2 2 !A !M 1 1 0 0 0 1 AD 1 1 0 A reg and D reg
... ...
–D 0 0 1 1 1 1 ADM 1 1 1 A reg, D reg, and RAM[A]
R15 15
–A -M 1 1 0 0 1 1
SP 0 jump j j j Effect:
D+1 0 1 1 1 1 1
LCL 1 null 0 0 0 no jump
A+1 M+1 1 1 0 1 1 1
ARG 2 JGT 0 0 1 if comp > 0 jump
THIS 3 D–1 0 0 1 1 1 0
A–1 M–1 1 1 0 0 1 0 JEQ 0 1 0 if comp = 0 jump
THAT 4
SCREEN 16384 D+A D+M 0 0 0 0 1 0 JGE 0 1 1 if comp ≥ 0 jump
KBD 24576 D–A D–M 0 1 0 0 1 1 JLT 1 0 0 if comp < 0 jump
A–D M–D 0 0 0 1 1 1 JNE 1 0 1 if comp ≠ 0 jump
D&A D&M 0 0 0 0 0 0 JLE 1 1 0 if comp ≤ 0 jump
D|A D|M 0 1 0 1 0 1 JMP 1 1 1 unconditional jump
a == 0 a == 1
Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 129
Machine Language

Overview Symbolic programming

• Machine language • Control
• The Hack computer • Variables
• The Hack instruction set • Labels
• The Hack CPU Emulator

Programming examples The Hack Language

• Basic • Symbolic
• Iteration • Binary
• Pointers • Output
• Input
• Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 130
Input / output
Screen: used to
display outputs
instruc- data
tions
ROM CPU RAM

Keyboard: used
to enter inputs

High-level I/O handling (later in the course):

I/O libraries for handling text, graphics, audio, video, …

Low-level I/O handling:

Manipulating bits directly, using memory resident bitmaps.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 131
Bitmaps
RAM
0
...
15
16
...
255
256
...
2047
2048
...
16383
SCREEN = 16384 screen
... memory
24575 map
24576
...
32767
Screen memory map:
An 8K memory block, dedicated to representing a black-and-white display unit
Base address: SCREEN = 16384 (predefined symbol)
Output is rendered by writing bits in the screen memory map.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 132
Bitmaps
Physical screen

...
...
...

...

...

Screen shots of computer games

developed on the Hack computer

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 133
Bitmaps
Physical screen

...
...
...

...

...

Screen shots of computer games

developed on the Hack computer

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 134
Bitmaps
Physical screen

...
...
...

...

...

Screen shots of computer games

developed on the Hack computer

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 135
Bitmaps
Screen Memory Map Physical screen
16384 0 0000000010101111 0 1 2 3 4 5 6 7 8 ... 511
= 1 0000000000000000 0 ...
SCREEN row 0
... 1 ...
base address
of the screen 31 1000000000000000
memory map 32 0000000001110000
33 0000000000000000
row 1 refresh ... ...
...
63 0000000000000000
... ...
8159 0000000010101101 ...
255
8160 0000000000000000
row 255
...
8191 0000000000000000

Mapping
The (row, col) pixel in the physical screen is represented by
the (col % 16 ) th bit in RAM address SCREEN + 32 * row + col / 16

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 136
Bitmaps
Screen Memory Map Physical screen
16384 0 0000000010101111 0 1 2 3 4 5 6 7 8 ... 511
= 1 0000000000000000 0 ...
SCREEN row 0
... 1 ...
base address
of the screen 31 1000000000000000
memory map 32 0000000001110000
33 0000000000000000
row 1 refresh ... ...
...
63 0000000000000000
... ...
8159 0000000010101101 ...
255
8160 0000000000000000
row 255
...
8191 0000000000000000

To set the (row , col) pixel to black or white: Not to worry...

Cool Bitmap Editor coming up
addr ← SCREEN + 32*row + col /16
word ← RAM[addr]
Set the ( col % 16 ) th bit of word to 0 or 1
RAM[addr] ← word

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 137
Bitmaps
Screen Memory Map Physical screen
16384 0 0000000010101111 0 1 2 3 4 5 6 7 8 ... 511
= 1 0000000000000000 0 ...
SCREEN row 0
... 1 ...
base address
of the screen 31 1000000000000000
memory map 32 0000000001110000
33 0000000000000000
row 1 refresh ... ...
...
63 0000000000000000
... ...
8159 0000000010101101 ...
255
8160 0000000000000000
row 255
...
8191 0000000000000000

Examples of simple patterns that can be easily drawn:

// Sets the first (left) 16 pixels
// of the top row to black
@SCREEN
M=-1 // –1 = 1111111111111111

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 138
Bitmaps
Screen Memory Map Physical screen
16384 0 0000000010101111 0 1 2 3 4 5 6 7 8 ... 511
= 1 0000000000000000 0 ...
SCREEN row 0
... 1 ...
base address
of the screen 31 1000000000000000
memory map 32 0000000001110000
33 0000000000000000
row 1 refresh ... ...
...
63 0000000000000000
... ...
8159 0000000010101101 ...
255
8160 0000000000000000
row 255
...
8191 0000000000000000

Examples of simple patterns that can be easily drawn:

// Sets the first (left) 16 pixels // Sets the first 16 pixels
// of the top row to black // of row 2 to black
@SCREEN
M=-1 // –1 = 1111111111111111
?
Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 139
Bitmaps
Screen Memory Map Physical screen
16384 0 0000000010101111 0 1 2 3 4 5 6 7 8 ... 511
= 1 0000000000000000 0 ...
SCREEN row 0
... 1 ...
base address
of the screen 31 1000000000000000
memory map 32 0000000001110000
33 0000000000000000
row 1 refresh ... ...
...
63 0000000000000000
... ...
8159 0000000010101101 ...
255
8160 0000000000000000
row 255
...
8191 0000000000000000

Examples of simple patterns that can be easily drawn:

// Sets the first (left) 16 pixels // Sets the first 16 pixels
// of the top row to black // of row 2 to black
@SCREEN @64
M=-1 // –1 = 1111111111111111 D=A
@SCREEN
A=A+D
M=-1

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 140
Bitmaps
Screen Memory Map Physical screen
16384 0 0000000010101111 0 1 2 3 4 5 6 7 8 ... 511
= 1 0000000000000000 0 ...
SCREEN row 0
... 1 ...
base address
of the screen 31 1000000000000000
memory map 32 0000000001110000
33 0000000000000000
row 1 refresh ... ...
...
63 0000000000000000
... ...
8159 0000000010101101 ...
255
8160 0000000000000000
row 255
...
8191 0000000000000000

Examples of simple patterns that can be easily drawn:

// Sets the first (left) 16 pixels // Sets the first 16 pixels // Sets the entire screen
// of the top row to black // of row 2 to black // to black / white
@SCREEN @64
M=-1 // –1 = 1111111111111111 D=A
@SCREEN (Project 4)
A=A+D
M=-1

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 141
Bitmaps
Screen Memory Map Physical screen
16384 0 0000000010101111 0 1 2 3 4 5 6 7 8 ... 511
= 1 0000000000000000 0 ...
SCREEN row 0
... 1 ...
base address
of the screen 31 1000000000000000
memory map 32 0000000001110000
33 0000000000000000
row 1 refresh ... ...
...
63 0000000000000000
... ...
8159 0000000010101101 ...
255
8160 0000000000000000
row 255
...
8191 0000000000000000

Drawing
Rectangle
Rectangle
Drawing
Simple
graphics
program:

demo
demo

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 142
Bitmap Editor
0000111111100000 = 4064
0001100000110000 = 6192
0001001010010000 = 4752
...

Bitmap editor (web-based tool)

The developer draws a pixeled image on a 2D grid;
The tool generates assembly code that draws the
image in the RAM;
The generated code can be copy-pasted into the
developer’s code.

...
0111111011111100 = 32508

Note: The editor generates either Jack code or Hack assembly code –
see the radio buttons at the very bottom of the editor’s GUI.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 143
Machine Language

Overview Symbolic programming

• Machine language • Control
• The Hack computer • Variables
• The Hack instruction set • Labels
• The Hack CPU Emulator

Programming examples The Hack Language

• Basic • Symbolic
• Iteration • Binary
• Pointers • Output
• Input
• Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 144
Input
RAM
0
High-level input handling (later in the course) ...
15
readInt, readString, ... 16
...
255
Low-level input handling 256
...
Read bits.
2047
2048
...
16383
16384
... screen
24575
24576 keyboard
...
32767

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 145
Input
RAM
0
...
15
16
...
255
256
...
2047
2048
...
16383
16384
...
24575
kbd = 24576 keyboard
...
32767
Keyboard memory map
A single 16-bit memory location, dedicated to representing the keyboard.
Base address: KBD = 24576 (predefined symbol)
Reading inputs is affected by probing this register.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 146
The Hack character set
key code key code key code key code key code
(space) 32 0 48 A 65 a 97 newline 128
! 33 1 49 B 66 b 98 backspace 129
“ 34 … … C … c 99 left arrow 130
# 35 9 57 … … … … up arrow 131
$ 36 Z 90 z 122 right arrow 132
: 58
% 37 down arrow 133
; 59 [ 91 { 123
& 38 home 134
< 60 / 92 | 124
‘ 39 end 135
= 61 ] 93 } 125
( 40 Page up 136
> 62 ^ 94 ~ 126
) 41 Page down 137
? 63 _ 95
* 42 insert 138
@ 64 ` 96
+ 43 delete 139
, 44 esc 140
- 45 f1 141
. 46 (Subset of Unicode) ... ...
/ 47 f12 152

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 147
Memory mapped input

RAM
24576 0000000000000000
=
KBD
base address
of the keyboard
memory map

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 148
Memory mapped input

RAM
24576 0000000000000000
0000000001001011 k
=
KBD
base address
of the keyboard
memory map

code('k') = 75

When a key is pressed on the keyboard,

the key’s character code appears in the keyboard memory map.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 149
Memory mapped input

RAM 4
0000000000110100
24576 0000000000000000
=
KBD
base address
of the keyboard
memory map

code('4') = 52

When a key is pressed on the keyboard,

the key’s character code appears in the keyboard memory map.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 150
Memory mapped input

RAM
0000000010000011
24576 0000000000000000
= 
KBD
base address
of the keyboard
memory map

code('') = 131

When a key is pressed on the keyboard,

the key’s character code appears in the keyboard memory map.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 151
Memory mapped input

RAM
24576 0000000000100000
0000000000000000
=
KBD space
base address
of the keyboard
memory map

code(' ') = 32

When a key is pressed on the keyboard,

the key’s character code appears in the keyboard memory map.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 152
Memory mapped input

RAM
24576 0000000000000000
=
KBD
base address
of the keyboard
memory map

When no key is pressed, the resulting code is 0.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 153
Reading inputs

RAM
24576 0000000000000000
0000000001001011 k
=
KBD
base address
of the keyboard
memory map

code('k') = 75

Examples:
// Set D to the character code of
// the currently pressed key

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 154
Reading inputs

RAM
24576 0000000000000000
0000000001001011 k
=
KBD
base address
of the keyboard
memory map

code('k') = 75

Examples:
// Set D to the character code of // If the currently pressed key is 'q', goto END
// the currently pressed key @KBD
@KBD D=M
D=M @113 // 'q'
D=D-A
@END
D;JEQ

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 155
Machine Language

Overview Symbolic programming

• Machine language • Control
• The Hack computer • Variables
• The Hack instruction set • Labels
• The Hack CPU Emulator

Programming examples The Hack Language

• Basic • Symbolic
• Iteration • Binary
• Pointers • Output
• Input
• Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 156
Project 4
Objectives
Gain a hands-on taste of:
• Low-level programming
• Assembly language
• The Hack computer

Tasks
• Write a simple algebraic program: Mult
• Write a simple interactive program: Fill
• Get creative: Define and write some program of your own (optional).

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 157
Mult: a program that computes R2 = R0 * R1

code:
Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 158
Mult: a program that computes R2 = R0 * R1

The supplied test script sets

up and executes several
tests of the Mult program.

code:
Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 159
Mult: a program that computes R2 = R0 * R1

Multiplication algorithm
• Repetitive addition (simple, inefficient)
• Bitwise multiplication (sophisticated, efficient)
Either approach is fine for this project.

code:
Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 160
Fill: a simple interactive program

When the user presses a

keyboard key (any key), the
entire screen becomes black

code:
Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 161
Fill: a simple interactive program

The screen remains black as

long as the key is pressed.

code:
Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 162
Fill: a simple interactive program

When the user releases the

key, the screen is cleared

code:
Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 163
Fill: a simple interactive program

code:
Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 164
Fill: a simple interactive program

Etc...

code:
Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 165
Fill: a simple interactive program

Etc...

code:
Project 4

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 166
Fill: a simple interactive program

Algorithm
• Execute an infinite loop that listens to the keyboard input
• When a key is pressed (any key),
execute code that writes "black" in every pixel
• When no key is pressed, execute code that writes "white" in every pixel

Tip: This program requires working with pointers.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 167
Task 3: Define and write a program of your own

Any ideas?
It’s your call!

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 168
Implementation notes
Well-written low-level code is
• Compact
• Efficient
Tips
• Elegant
• Use symbolic variables and labels
• Self-describing
• Use sensible documentation
• Use sensible variable and label names
• Variables: lower-case
• Labels: upper-case
• Use indentation
• Start by writing pseudocode.

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 169
Nand to Tetris Roadmap: Hardware

abstraction

machine Writing low-level This lecture introduced:

p4
language programs
• The Hack computer / instruction set
• Low-level programming
developing • Assembly / assembler
an assembler

abstraction
hardware platform
building a
computer abstraction
p2 p3
computer building p1
ALU, RAM abstraction
chips building
elementary
logic gates gates

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 170
Nand to Tetris Roadmap: Hardware

abstraction

machine Writing low-level

p4
language programs

developing
an assembler

abstraction
p5 hardware platform
building a
computer abstraction
p2 p3
computer building p1
ALU, RAM abstraction
chips building
elementary
logic gates gates

Next lecture:
Build the computer

Nand to Tetris / www.nand2tetris.org / Chapter 4 / Copyright © Noam Nisan and Shimon Schocken Slide 171