Transcript Introduction and Orientation: The World of Database Management

Machine Language
Building a Modern Computer From First Principles
www.nand2tetris.org
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language
slide 1
Usage and Copyright Notice:
Copyright © Noam Nisan and Shimon Schocken
This presentation contains lecture materials that accompany the textbook “The Elements of
Computing Systems” by Noam Nisan & Shimon Schocken, MIT Press, 2005.
We provide both PPT and PDF versions.
Our web site, www.nand2tetris.org ,features a set of presentations, one for each book chapter.
Each presentation is designed to support about 3 hours of classroom or self-study instruction.
You are welcome to use or edit this presentation as you see fit for instructional and noncommercial purposes.
If you use our materials, please include a reference to www.nand2tetris.org
If you have any questions or comments, please write us at [email protected]
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language
slide 2
Where we are at:
Human
Thought
Abstract design
Software
hierarchy
abstract interface
Chapters 9, 12
H.L. Language
&
Operating Sys.
Compiler
abstract interface
Chapters 10 - 11
Virtual
Machine
VM Translator
abstract interface
Chapters 7 - 8
Assembly
Language
Assembler
Chapter 6
abstract interface
Machine
Language
Computer
Architecture
abstract interface
Chapters 4 - 5
Hardware
Platform
Hardware
hierarchy
Gate Logic
abstract interface
Chapters 1 - 3
Chips &
Logic Gates
Electrical
Engineering
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language
Physics
slide 3
Machine language
Abstraction – implementation duality:
 Machine language ( = instruction set) can be viewed as a programmeroriented abstraction of the hardware platform
 The hardware platform can be viewed as a physical means for realizing
the machine language abstraction
Another duality:
 Binary version
 Symbolic version
Loose definition:
 Machine language = an agreed-upon formalism for manipulating
a memory using a processor and a set of registers
 Same spirit but different syntax across different hardware platforms.
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language
slide 4
Binary and symbolic notation
1010 0001 0010 1011
ADD R1, R2, R3
Evolution:
 Physical coding
 Symbolic documentation
 Symbolic coding
 Translation and execution
Jacquard loom
(1801)
 Requires a translator.
Augusta Ada King,
Countess of Lovelace
(1815-1852)
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language
slide 5
Lecture plan
 Machine languages at a glance
 The Hack machine language:

Symbolic version

Binary version
 Perspective
(The assembler will be covered in lecture 6).
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language
slide 6
Typical machine language commands (a small sample)
// In what follows R1,R2,R3 are registers, PC is program counter,
// and addr is some value.
ADD R1,R2,R3
// R1  R2 + R3
ADDI R1,R2,addr
// R1  R2 + addr
AND R1,R1,R2
// R1  R1 and R2 (bit-wise)
JMP addr
// PC  addr
JEQ R1,R1,addr
// IF R1 == R2 THEN PC  addr ELSE PC++
LOAD R1, addr
// R1  RAM[addr]
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 4: Machine Language
slide 7
The Hack computer
A 16-bit machine consisting of the following elements:
Data memory:
RAM – an addressable sequence of registers
Instruction memory:
Registers:
ROM – an addressable sequence of registers
D, A, M, where M stands for RAM[A]
Processing: ALU, capable of computing various functions
Program counter:
PC, holding an address
Control: The ROM is loaded with a sequence of 16-bit instructions, one per memory
location, beginning at address 0. Fetch-execute cycle: later
Instruction set: Two instructions: A-instruction, C-instruction.
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language
slide 8
The A-instruction
@value
// A  value
Where value is either a number or a symbol referring to some number.
Used for:
 Entering a constant value
( A = value)
 Selecting a RAM location
( register = RAM[A])
 Selecting a ROM location
( PC = A )
Coding example:
@17
D = A
@17
D = M
// A = 17
// D = 17
// A = 17
// D = RAM[17]
Later
@17
JMP
// A = 17
// fetch the instruction
// stored in ROM[17]
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language
slide 9
The C-instruction (first approximation)
dest = x + y
Exercise: Implement the following tasks
using Hack commands:
dest = x - y
dest = x
dest = 0
dest = 1

Set D to A-1

Set both A and D to A + 1

Set D to 19

Set both A and D to A + D

Set RAM[5034] to D - 1

Set RAM[53] to 171
dest = -1
x
y
=
=
dest
{A, D, M}
{A, D, M , 1}
=
{A, D, M, MD, A, AM, AD, AMD, null}

Add 1 to RAM[7],
and store the result in D.
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language
slide 10
The C-instruction (first approximation)
dest = x + y
Exercise: Implement the following tasks
using Hack commands:
dest = x - y

sum = 0

j = j + 1
dest = 1

q = sum + 12 – j
dest = -1

arr[7] = 0

Etc.
dest = x
dest = 0
x
y
=
=
dest
{A, D, M}
{A, D, M , 1}
=
{A, D, M, MD, A, AM, AD, AMD, null}
Symbol table:
j
sum
q
arr
17
22
21
16
(All symbols and values
in are arbitrary
examples)
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language
slide 11
Control (focus on the yellow chips only)
D
D register
a
ALU
A register
A
Mux
RAM
A/M
M
(selected
register)
In the Hack architecture:
 ROM = instruction memory
ROM
PC
(selected
register)
Instruction
 Program = sequence of 16-bit
numbers, starting at
ROM[0]
 Current instruction = ROM[PC]
 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 4: Machine Language
slide 12
Coding examples (practice)
Exercise: Implement the following
tasks using Hack commands:
Hack commands:
@value
// set A to value
dest = comp ; jump
// “dest = “ is optional
GOTO 50
// Where:

IF D == 0 GOTO 112
comp = 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 , M , !M , -M ,M+1, M-1 , D+M , D-M ,
M-D , D&M , D|M

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

IF RAM[12] > 0 GOTO 50

IF sum > 0 GOTO END

IF x[i] <= 0 GOTO NEXT.
All conditional jumps refer to the current value of D.
Symbol table:
sum
200
x
4000
i
151
END
50
NEXT
120
(All symbols and
values in are
arbitrary examples)
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language
slide 13
C-instruction syntax (final version)
dest = comp ; jump
// comp is mandatory
// dest and jump are optional
Where:
comp is one of:
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,
M,
!M,
-M,
M+1,
M-1,D+M,D-M,M-D,D&M,D|M
dest is one of:
null, M, D, MD, A, AM, AD, AMD
jump is one of:
null, JGT, JEQ, JGE, JLT, JNE, JLE, JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language
slide 14
IF logic – Hack style
High level:
if condition {
code block 1}
else {
code block 2}
code block 3
Hack:
D  not condition
@IF_TRUE
D;JEQ
code block 2
@END
0;JMP
Hack convention:

True is represented by -1

False is represented by 0
(IF_TRUE)
code block 1
(END)
code block 3
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language
slide 15
WHILE logic – Hack style
High level:
while condition {
code block 1
Hack:
(LOOP)
D  not condition)
}
@END
Code block 2
D;JEQ
code block 1
@LOOP
Hack convention:

True is represented by -1

False is represented by 0
0;JMP
(END)
code block 2
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language
slide 16
Side note
D
D register
a
ALU
A register
A
Mux
RAM
M
(selected
register)
ROM
PC
(selected
register)
A/M
Given the “multi-tasking” nature of the
A register:
 Command pairs like @100 followed by
D=M;JEQ make no sense
Instruction
 Best practice: in well-written Hack
programs, a C-instruction should
contain either a reference to M,
or a jump directive, but not both.
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language
slide 17
Complete program example
C:
Hack:
// Adds 1+...+100.
into i = 1;
into sum = 0;
while (i <= 100){
sum += i;
i++;
}
Hack assembly convention:

Variables: lower-case

Labels: upper-case

Commands: upper-case
Demo
CPU emulator
// Adds 1+...+100.
@i
// i refers to some memo. location
M=1
// i=1
@sum
// sum refers to some memo. location
M=0
// sum=0
(LOOP)
@i
D=M
// D = i
@100
D=D-A
// D = i - 100
@END
D;JGT
// If (i-100) > 0 got END
@i
D=M
// D = i
@sum
M=D+M
// sum += i
@i
M=M+1
// i++
@LOOP
0;JMP
// Got LOOP
(END)
@END
0;JMP
// Infinite loop
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language
slide 18
Lecture plan
 Symbolic machine language
 Binary machine language
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language
slide 19
A-instruction
Symbolic:
@value
// Where value is either a non-negative decimal number
// or a symbol referring to such number.
value (v = 0 or 1)
Binary:
0
v
v
v
v
v
v
v
v
v
v
v
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language
v
v
v
v
slide 20
C-instruction
Symbolic:
dest=comp;jump
// Either the dest or jump fields may be empty.
comp
Binary:
1
1
1
a
c1 c2 c3 c4
dest
c5 c6
d1 d2
jump
d3 j1 j2 j3
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language
slide 21
Symbols (user-defined)
 Label symbols: Used to label destinations
of goto commands. Declared by the pseudo
command (XXX). This directive defines
the symbol XXX to refer to the instruction
memory location holding the next command
in the program
 Variable symbols: Any user-defined symbol
xxx appearing in an assembly program that
is not defined elsewhere using the “(xxx)“
directive is treated as a variable, and is
assigned a unique memory address by the
assembler, starting at RAM address 16
 By convention, label symbols are uppercase and variable symbols are lower-case.
@R0
D=M
@INFINITE_LOOP
D;JLE
@counter
M=D
@SCREEN
D=A
@addr
M=D
(LOOP)
@addr
A=M
M=-1
@addr
D=M
@32
D=D+A
@addr
M=D
@counter
MD=M-1
@LOOP
D;JGT
(INFINITE_LOOP)
@INFINITE_LOOP
0;JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language
slide 22
Symbols (pre-defined)
 Virtual registers: R0,…, R15 are predefined
to be 0,…,15
 I/O pointers: The symbols SCREEN and KBD
are predefined to be 16384 and 24576,
respectively (base addresses of the screen
and keyboard memory maps)
 Predefined pointers: the symbols
SP, LCL, ARG, THIS, and THAT
are predefined to be 0 to 4, respectively.
@R0
D=M
@INFINITE_LOOP
D;JLE
@counter
M=D
@SCREEN
D=A
@addr
M=D
(LOOP)
@addr
A=M
M=-1
@addr
D=M
@32
D=D+A
@addr
M=D
@counter
MD=M-1
@LOOP
D;JGT
(INFINITE_LOOP)
@INFINITE_LOOP
0;JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language
slide 23
Perspective
 Hack is a simple machine language
 User friendly syntax: D=D+A instead of ADD D,D,A
 Hack is a “½-address machine”: it normally takes two commands to get
something done: A-command to address, C-command to process
 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 4: Machine Language
slide 24
End-note: a macro machine language (optional, can be implemented rather easily)
Assignment:
1. x = constant (e.g. x = 17)
2. x = y
3. x = 0 , x = 1, x = -1
Arithmetic / logical:
4. x = y op z
where y, z are variables or constants and
op is some ALU operation like +, -, and, or, etc.
Control:
5. GOTO s
6. IF cond GOTO s
where cond is an expression (x op y) {=|<|>|…} {0|1}
e.g. IF x+17 > 0 goto loop
White space or comments:
7. White space: ignore
8. // comment to the end of the line: ignore.
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language
slide 25