NAND2GO Chapter 7. VM Ⅰ:Stack Arithmetic
| 1. Context |
| ||
| 2. Goal |
| ||
| 3. Measurable Effects |
Write a VM language- Hack assembly language Translator and pass all of the test scripts in nand2tetris. | ||
| 4. Outputs | 5. Process | 6. Inputs | |
|
A translator |
|
| |
| 7. External Factors | |||
Introduction
In Chapter7&8 you need to write a VM Translator which can translate Virtual Machine language into Assembly language.As to Chapter7, you should achieve the stack architecture and memory access, while in Chapter 8, you are supposed to complete the left part and achieve this Translator based on the project of Chapter7.
Why need Virtual Machine
{{Template:content |content= In current computer architecture, a high-level language (such as Java) is not directly interfaced with the low-level language or machine language, instead, it will become an intermediate language(called bytecode) and runs on the virtual machine (such as Java Virtual Machine) , then the bytecode is translated into low-level language or machine language on the specific platform.That is why Java programs can be compiled only once in any case, but can run on all platforms.Virtual machine makes high-level languages do not have to be compatible with all platforms, but only to be able to apply to virtual machines. In this case we can reduce the workload of engineering development.
Fig 7.1 Structure without virtual machine
Fig 7.2 Structure with virtual machine
Stack
What is the stack?
A stack is a linear data structure which looks like a container with an opening at one end.There are two kinds of operations based on stack, ‘push’ and ‘pop’. If we regard the open end as the top of the stack, ‘push’ is putting an element on the top of the stack while ‘pop’ means that the top element of the stack is popped out of the stack.
Fig 7.3 Stack Pop
Fig 7.4 Stack Push
Hack assembly language
Hack assembly language has 3 registers(A,M and D).A register is used to store address, D is used to store data, M is used to store memory.There are two kinds of instructions, one is A-instruction, the other is C-instruction. Besides, there is a kind of sentences named symbol declaration.
A-instruction
A-instruction is in a certain format:
- @xxx
If xxx is a number, the address xxx will be store in A register; otherwise there is a symbol, if this symbol is new, a mapping will be built between this symbol and an available RAM, and then the symbol is equivalent to the address of the RAM.
C-instruction
C-instruction has two format
- dest=comp
- comp;jump
symble declaration
- (xxx)
It plays a role of destination in jump.
Hack assembly language is not the key point in this Chapter, if you want to know more, please turn to Chapter 4.
VM language
Types of memorysegment
There are 8 kinds of memorysegment, which are static, this, local, argument, that, constant, pointe and temp.
- static, constant, temp, pointer:
They are global memorysegments.The four segments are the same for all functions.
- local, argument, this, that:
Values of RAM[1~4] respectively represent the places of these memorysegments’ beginning. In different functions, you need to set these for parameters. Therefore, they are private and different for each function.
Stack
Stack locates in RAM[256~2047], RAM[0] is the pointer pointing at the top of the stack (SP).When execute push operatio, SP will increase by 1, but for pop, SP will decrease by 1. What is more, it is necessary to set SP as 256 at the beginning of every programs.
Types of sentences
{{Template:content |content= VM language has three kinds of sentences-pus, pop, and compute.
- push segment index
Place the value stored in a certain RAM at the top of the stack.
- pop segment index
Pop out the element at the top of the stack and stored it in a certain RAM.
Fig 7.5 VM stack pop&push(Picture reference from nand2tetris)
compute
pop out the two elements of the top of the stack and place the result of these two elements on the top of the stack after a certain operation.
Project
An advice before beginning
Because the CPUEmulator provide in nand2tetris is complicated, it is difficult to debug your program.Therefore, you’d better write a CPUEmulator by yourself.
The difficulty and its solution
difficulty:
Hack assembly language only give us 3 registers (A,M and D). In fact, A and M are synchronous. When we are doing the project, we will find out that it is impossible to finish this project only use these 3 registers.
solution
We can select several memories which are not related to the actual operation in the memory pool as an additional registers, so that we can solve the problem of lacking registers.
translation strategy
push
First, calculate the RAM address corresponding to the top of the stack, and store it in an additional register. Then calculate the address of the element which is going to be pushed in stack and store in another register. Last, do the push operation.
Fig 7.6 Sample push
pop
It is similar to push.
compute
It is easy to achieve add, sub, neg, and, or and not, the only thing you need to do is to find out the address of the top of stack. As for eq, gt and lt, you need to get the address of the top of the stack first, then do the subtraction on the top two elements and use jump sentence in Hack assembly language to achieve the function of if-else sentence. But, you have to use two jump sentences at least to achieve if- else.
Fig 7.7 Sample if-else
References
Description: References are divided into books, journal articles, audio recordings, videos, web pages, research reports, etc. Please select the appropriate template for reference according to your needs.
- Nand2Tetris, Temporary link failure, chapter4 & 7