Lecture #4:
Machine
Language
From Nand to Tetris
www.nand2tetris.org
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 1
Where we are at:
Human Abstract design Software
abstract interface
Thought hierarchy
Chapters 9, 12
H.L. Language Compiler
& abstract interface
Chapters 10 - 11
Operating Sys.
Virtual VM Translator
abstract interface
Machine Chapters 7 - 8
Assembly
Language
Assembler
Chapter 6
abstract interface
Computer
Machine Architecture
abstract interface
Language
Chapters 4 - 5
Hardware Gate Logic
abstract interface
Platform Chapters 1 - 3 Electrical
Chips & Engineering
Hardware Physics
Logic Gates
hierarchy
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 2
High-Level vs. Low-Level
Programming Languages
• Goal of Low-Level Language:
– Code low-level programs as a series of machine
instruc:ons
• Command processor to do logic/arithme:c
• Fetch and store values from/to memory
• Move values between registers
• Test boolean condi:ons
• Etc.
– Basically: direct execu:on + total control of hardware
– Fine line between hardware and soFware meet
• Goal of High-Level:
– Generality and power of expression
– Everything else you’ve learned about Java/C++
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 3
Machine language
Abstrac:on – implementa:on duality:
• Machine language ( = instruc:on set) can be viewed as a programmer-oriented
abstrac:on of the hardware plaOorm
• The hardware plaOorm can be viewed as a physical means for realizing the
machine language abstrac:on Another duality:
n Binary version 1010 0011 0001 1001
n Symbolic version ADD R3, R1, R9
Loose definition:
n Machine language = an agreed-upon formalism for
manipulating
a memory using a processor and a set of
registers
n Same spirit but different syntax across different hardware
platforms.
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 4
Joseph-Marie
Jacquard
• 1801 = Automa:c Loom (controlled by
punch cards)
– Automa:cally controlled the warp
and weF threads on a silk loom
• Recorded paVerns of holes in a
string of cards
– Start of “punch cards”
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 5
Punched Cards
• Needles went through where there were holes
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 6
Charles Babbage
• “Father of Compu:ng”
• 2 major contribu:ons
– Difference Engine (1822)
• First Mechanical Computer
• Never Finished
• un:l 2002: 8000 parts, 2 tons, 11 feet
– Analy:cal Engine
• First programmed computer
– Could handle condi:onal jumps
– Used Jacquards “Punch Card” idea
• Powered by 6 steam engines
• Never completed
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 7
Ada Lovelace
• Friend of Charles Babbage
• Educated in Math
• Described programs that
would work on Babbage’s
Analy:cal Engine
• First Programmer
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 8
Binary and symbolic notation
1010 0001 0010 1011 ADD R1, R2, R3
Evolu:on:
• Physical coding
• Symbolic documenta:on
• Symbolic coding
• Transla:on and execu:on
• Requires a translator.
Jacquard loom Augusta Ada King,
(1801) Countess of Lovelace
(1815-1852)
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 9
Lecture plan
• Machine languages at a glance
• The Hack machine language:
– Symbolic version
– Binary version
• Perspec:ve
(The assembler will be covered later).
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 10
Typical machine language commands
(a small sample)
// In what follows R1,R2,R3 are registers, PC is program counter,
// and addr is some value.
// Arithmetic + Logic Operations
ADD R1,R2,R3 // R1 ß R2 + R3
ADDI R1,R2,addr // R1 ß R2 + addr (immediate addressing)
AND R1,R1,R2 // R1 ß R1 and R2 (bit-wise)
// Flow of Control Commands
JMP addr // PC ß addr unconditional jump
JEQ R1,R2,addr // IF R1 == R2 THEN PC ß addr ELSE PC++ cond. jmp
// Memory Access Commands
LOAD R1, addr // R1 ß RAM[addr] (direct addressing)
STORE R1, addr // RAM[addr] ß R1
NOP // Do nothing
// Etc. – some 50-300 command variants
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 11
The Hack computer
A 16-bit machine consis:ng of the following elements:
Data memory: RAM – an addressable sequence of registers
Instruc:on memory: ROM – an addressable sequence of registers
Registers: D, A, M, where M stands for RAM[A]
D stands for data register
A stands for data/address’s register
Processing: ALU, capable of compu:ng various func:ons
Program counter: PC, holding an address
Control: The ROM is loaded with a sequence of 16-bit instruc:ons, one per memory
loca:on, beginning at address 0. Fetch-execute cycle: later
Instruc:on set: Two instruc:ons: A-instruc:on (Address), C-instruc:on (Compute).
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 12
The A-instruction
@value // A ß value
Where value is either a number or a symbol referring to some number.
Note: Every operation involving a memory location requires two Hack commands
Coding example:
Used for:
• Entering a constant value @17 // A = 17
( A = value) D = A // D = 17
n Selecting a RAM location @17 // A = 17
( register = RAM[A]) D = M // D = RAM[17]
Later
n Selecting a ROM location @17 // A = 17
( PC = A ) JMP // fetch the instruction
// stored in ROM[17]
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 13
The C-instruction dest = x + y
(Some) allowed values: dest = x - y
• Used for: x = {A, D, M} dest = x
– Calcula:ons: y = {A, D, M , 1} dest = 0
• Arithme:c dest = {A, D, M} dest = 1
• Logic dest = -1
– Jumping Later
– Manipula:ng RAM[A] (M): @17
M = 0
// A = 17
//
// RAM[17]
RAM[17] == 00
• Gegng value (if M on right side)
• Changing value (if M on leF side) @17 // A = 17
A = M //
// AA == RAM[17]
RAM[17]
– Manipula:ng A and D registers
• Gegng value (on the right) @17 // A = 17
D = D + M //
// added
added RAM[17]
RAM[17] to
to DD
• Changing value (on the leF)
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 14
The C-instruction (first approximation)
Exercise: Implement the following tasks
dest = x + y
using Hack commands:
Allowed values:
dest = x - y
x = {A, D, M} 1) Set D to A-1
dest = x
y = {A, D, M , 1}
dest = 0 2) Set both A and D to A + 1
dest = {A, D, M, MD,
dest = 1 AM, AD, AMD, 3) Set D to 19
null}
dest = -1
4) Set both A and D to A + D
5) Set RAM[5034] to D - 1
6) Set RAM[543] to 171
7) Add 1 to RAM[7],
and store the result in D.
8) Add 3 to RAM[12],
and store the result in D.
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 15
The C-instruction (first approximation)
dest = x + y
Exercise: Implement the following tasks
dest = x - y using Hack commands:
dest = x
1) sum = 0
dest = 0
dest = 1 2) j = j + 1
dest = -1 3) q = sum + 12 – j
x = {A, D, M} [PAUSE] Array review!
y = {A, D, M , 1}
4) arr[3] = -1
dest = {A, D, M, MD, A, AM, AD, AMD, null}
Symbol table: 5) arr[j] = 0
(All symbols and values
j 3012 are arbitrary examples)
sum 4500 6) arr[j] = 17
q 3812 NOTE: these are
arr 20561 variable names on the
left! Which means?
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 16
Control (focus on the yellow chips only)
D register D
a-bit
ALU
A
A register
A/M
Mux
address RAM M
input
(selected
register)
In the Hack architecture:
n ROM = instruction memory
n Program = sequence of 16-bit
address ROM numbers, starting at
input Instruction
PC ROM[0]
(selected
register) n Current instruction = ROM[PC]
n To select instruction n from the ROM, we
set A to n, using the instruction @n
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 17
Coding examples Hack commands:
(practice)
Exercise: Implement the following A-command: @value // set A to value
tasks using Hack commands: C-command: dest = comp ; jump // dest = and ;jump
// are op:onal
1) goto 50 Where:
comp = 0 , 1 , -1 , D , A , !D , !A , -D , -A , D+1 ,
2) if D==0 goto 112 A+1 , D-1, A-1 , D+A , D-A , A-D , D&A ,
D|A , M , !M , -M ,M+1, M-1 , D+M , D-M ,
M-D , D&M , D|M
3) if D<9 goto 507
dest = M , D , MD , A , AM , AD , AMD, or null
jump = JGT , JEQ , JGE , JLT , JNE , JLE , JMP, or null
4) if RAM[12] > 0 goto 50
In the command dest = comp; jump, the jump materialzes
if (comp jump 0) is true. For example, in D=D+1,JLT,
5) if sum>0 goto END we jump if D+1 < 0.
6) if x[i]<=0 goto NEXT. Symbol table:
sum 2200
x 4000
(All symbols and
Hack convention: i 6151 values in are
END 50 arbitrary examples)
q CAPS naming is
NEXT 120
for (LABELS)
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 18
IF logic – Hack style
High level: Hack:
if condition { D ß not condition
code block 1} @IF_TRUE
else { D;JEQ
code block 2}
code block 2
code block 3
@END
0;JMP
(IF_TRUE)
Hack convention: code block 1
q True is represented by -1 (END)
q 1111 1111 1111 1111 code block 3
q False is represented by 0
q 0000 0000 0000 0000
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 19
WHILE logic – Hack style
High level: Hack:
while condition { (LOOP)
code block 1 D ß not condition)
} @END
Code block 2
D;JEQ
code block 1
@LOOP
0;JMP
Hack convention:
(END)
q True is represented by -1 code block 2
q False is represented by 0
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 20
Side note (focus on the yellow chip parts only)
D register D
a-bit
ALU
A
A register
A/M
Mux
address RAM M
input
(selected
register)
In the Hack architecture, the A register
addresses both the RAM and the ROM,
simultaneously. Therefore:
n Command pairs like @addr followed by
address ROM D=M;someJumpDirective make no sense
input Instruction
PC n Best practice: in well-written Hack
(selected
register)
programs, a C-instruction should contain
q either a reference to M, or
q a jump directive,
n but not both.
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 21
Complete program example
C language code: Hack assembly code:
// Adds 1+...+100. // Adds 1+...+100.
int i = 1; @i // i refers to some RAM location
int sum = 0; M=1 // i=1
while (i <= 100){ @sum // sum refers to some RAM location
M=0 // sum=0
sum += i;
(LOOP)
i++;
@i
} D=M // D = i
@100
D=D-A // D = i - 100
Hack assembly convention: @END
D;JGT // If (i-100) > 0 goto END
q Variables: lower-case @i
D=M // D = i
q Labels: upper-case @sum
M=D+M // sum += i
q Commands: upper-case @i
M=M+1 // i++
@LOOP
0;JMP // Got LOOP
Demo
CPU emulator (END)
@END
0;JMP // Infinite loop
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 22
Symbols in Hack assembly // Typical symbolic
programs
// Hack code, meaning
// not important
@R0
Symbols created by Hack programmers and code generators: D=M
@INFINITE_LOOP
• Label symbols: Used to label des:na:ons of goto commands. Declared by the
D;JLE
pseudo command (XXX). This direc:ve defines the symbol XXX to refer to the
@counter
instruc:on memory loca:on holding the next command in the program (within the
M=D
program, XXX is called “label”)
@SCREEN
• Variable symbols: Any user-defined symbol xxx appearing in an assembly program D=A
that is not defined elsewhere using the (xxx) direc:ve is treated as a variable, @addr
and is “automa:cally” assigned a unique RAM address, star:ng at RAM address 16 M=D
• By conven:on, Hack programmers use lower-case and upper-case leVers for (LOOP)
@addr
variable names and labels, respec:vely.
A=M
Predefined symbols: M=-1
• I/O pointers: The symbols SCREEN and KBD are “automa:cally” predefined to refer @addr
to RAM addresses 16384 and 24576, respec:vely (base addresses of the Hack D=M
plaOorm’s screen and keyboard memory maps) @32
D=D+A
• Virtual registers: covered in future lectures. @addr
• VM control registers: covered in future lectures. M=D
@counter
Q: Who does all the “automatic” assignments of symbols to RAM addresses?
MD=M-1
A: The assembler, which is the program that translates symbolic Hack @LOOP
D;JGT
programs into binary Hack program. As part of the translation process,
(INFINITE_LOOP)
the symbols are resolved to RAM addresses. (more about this in future lectures)
@INFINITE_LOOP
0;JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 23
SCREEN + KBD
• SCREEN is a pointer to memory
16,384 to 24,575 (inclusive)
= 8,192 registers at 16 bits each
= 131,072 bits, each represents a pixel
0 = white
1 = black
= 512 columns x 256 rows = screen resolu:on
• KBD is a pointer to keyboard register
– 24,576 stores current value of key pressed
• if nothing pressed, value is 0
• else value is key pressed
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 24
Perspective
• Hack is a simple machine language
• User friendly syntax: D=D+A instead of ADD D,D,A
• Hack is a “½-address machine”: any opera:on that needs to operate on the RAM
must be specified using two commands: an A-command to address the RAM, and a
subsequent C-command to operate on it
• A Macro-language can be easily developed
• A Hack assembler is needed and will be discusses and developed later in the
course.
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 25
