NAND2GO Chapter 8. VM Ⅱ:Program Control
| 1. Context |
After chapter 7,we have just learned some basic VM commands and the concept of the core of VirtuaMachine,Stack. A simple VM compiler has been implemented yet. | ||
| 2. Goal |
To write a fully functional VM compiler. | ||
| 3. Measurable Effects |
You can write a VM compiler could transfer every VM code on earth to assembly language precisely. Have clear concept about functions. Know the function is abstraction of every program. Could implment another function if you could handle another assembly language. | ||
| 4. Outputs | 5. Process | 6. Inputs | |
|
A Virtual Machine. |
Learn concept and features of function, write pseudo codes. On the base of project 7, add code to parse and generate code about program control and function. |
Nand2Tetris (Nisan & Schocken, 2008b) Chapter 8 (and what you have learned from Chapters 1-7 ,Lectures of Chapter 8 and A high-level language. | |
| 7. External Factors | |||
Introduction
After Chapter 7 you must have learned the basic grammar of VM language and be able to translate simple VM Language into assembly language. But, a complex computer program is inevitably composed of branches and loops. Also, we would discuss function and class. What's a function and a class? And how these abstract structure be implemented on the assembly code? You would be get familiar with those important concepts complete a fully functional Virtual Machine compiler!
Program flow commands in VM language
goto command
From all the perspective, VM language is simpler than assembly language. Since VM language serves as an intermediate language that doesn't need to neither take care of complex registers and memory, nor become easy to use by programmer. As you've learned Chapter 7, you would find out that the whole VM language is based on an abstract data structure,which is stack. This is true of VM language's program Control commands.
Unlike the sophisticated assembly C-instruction, which contains 9 types of jumping commands.The VM language's program control is composed of only 2 basic commands,goto and if-goto, and a label to specify where to jump. Goto command ,like JMP in assembly language, is used to unconditionally jump to some label in the program.The grammar of goto is as follows.
goto labelname
labelname is the label you declared in some place in the program. The declaration of label is not necessarily before use. The label declaration should be write as below:
labelname:
program block
You may have a question that how can I know where to jump, when the declaration is after the use of labelname. Well, it's a pretty simple question that you can just write a same label in assembly language and hand the problem to the Project 6, the assembler.
Warning: Same label names
You need to be very careful that your label names in assembly language do have the chances that appears to the same. Its not a usual condition but when it happen, the program will be in such a mess, causing unpredictable result. This is often occurs when functions, which will be introduced later is of course involved in jumping ,is involved. For example: In VM language, functions and labels are two totally diff erent stuff . But if the function name is same with another label name. And you didn't take any precautions, the program will be messed. A common way to solve this problem is to use a prefix/ suffix on the function names. For example, Var: and function function Var 1 seems diff erent in VM language. But they were same in assembly lable names. But you can add a prefix like 'function' to all the functions. In that case, the function Var's entry label would be 'functionVar', which could be different from label name 'Var'. But you may still come into a very rare but interesting situation, that some guy gives a label name like 'functionVar:'. It may sounds ridiculous but it's still could happen. To make sure this situation would not be a problem. We could also add another prefi x like 'label' to all label names in VM languages. So the label name would be 'labelfunctionVar. Different from 'functionVar', huh! Wait! When you try to solve this, you've just learned an important concept in computational thinking, 'namespace'! The namespace is a common solution to organize objects of various kinds, like label names and functions. When namespace management was implemented as above. Some kind of reuse of name will be allowed! And you just need to make sure there are no absurdity in the same kind of object, or the same namespace. This is crucial when you design a big system, which will signifi cantly reduce your burden of giving name and the risk of name problem.
if-goto command
After talking about unconditional jumping, let's turn to conditional jumping. In VM language, conditional jumping language is only the if-goto command. The if-goto command is still with only one parameter like goto,which is the destination of jumping. So the if-goto command often comes as below:
if-goto labelnames
Wow, you must have raised a doubt whether this simple command could represent every kind of conditional jumping! Let's see how it works. When if-goto was executed, data on the top of stack is popped first, then if this data is 0, then the jump will not happen, otherwise,the program will be jumped to destination. So, as you may have find out, if-goto command is often cooperate with other stack arithmetic commands. For example, if(x>5) then jump to label should be write as follows.
push x
push 5
gt
if-goto
A basic rule to follow when it comes to conditional jumping is that calculate the result first, then use the 'if- goto' command.
The contract of a function
The functions are the most common component that forms a program. Functions are a series of instructions that could complete a specifi c task. It's one of subroutines in the program. Design your program with many sub routines is important and useful.It could divide a sophiscated program into several modules. After modulation, you can focus on the smaller subroutines,a simpler system, instead of complex system itself. In test-dr iven design(TDD), every implementation or process has a contract, which gives the outline and principles of what you are to design. Let's defi ning function by a series test and laws!
A function should be assigned to a name
A function must be callable to other parts of program, and could be called more than once
A function could accept 0 or a fixed number of parameters and return no more than 1 return value
A function should run independently
A function should have private space to store variables used only by the function itself
A call to function should not disturb other part of program's process, except for the return value
From those laws, you can gets your own understanding about what's a function. You will see those laws again and again when we implement a function. Keep those laws in your mind. The contract is a guide,that could tell your how to implement way. And the contract is also a series of test, that could tell you whether your implementation is right.
Back to Stack! Functions on the stack
We meet stack again! After chapter 7 ,you must know what's a stack, and why computer use the stack as its fundamental memory structure. So? why the functions also use stacks?
Calling Stack and Recursion
Let's imagine this situation. If you are going to calculate Fib(n),Fib means Fibonacci series. You write a function that add two numbers together. If you are gonna calculate Fib(n), you need to call Fib(n-1) and Fib(n-2) to calculate Fib(n-1) and Fib(n-2),so that you can sum them up. But you will meet another problem, that you need Fib(n-3) to calculate Fib(n-1).It's obvious that you'll constantly call Fib() Function until you get a result. We can draw this process in a stack form. It seems that you're constantly push functions into that stack.
Finally, your call comes to Fib(0) and Fib(1). Finally, you gets the real result for the first time! Fib(0) returns 0 and Fib(1) returns 1. With those functions gives the return value and complete their mission. Everything seems easy. The function that calls Fib(0) and Fib(1), which is Fib(2), gets its result that Fib(2)= Fib(1)+Fib(0). And the same for Fib(3), Fib(4) ... You would find out that these process, if presented on the stack, is many pop processes from the stack! Finally, after you pop all other functions, you gets your ultimate goal Fib(n)!
As examples above, call to a function could be described as push operation and return could be described as pop operation. This is called "the Calling stack". You would find out that we can easily implement this stack on to our RAM,
Note: the example process is called recursion, which means call itself again and again to gets its final result. This is a typical way to design computer programs! The recursion always contains a set of rules that reduce all other cases toward the base case and some base cases to stop the recursion. You would meet recursion when you write Jack compiler.
Functions in the memory
As mentioned above the functions are called as stack. What's this stack is like? And how can we implement functions into RAM?
To solve this program, we must return to the contract of function. From the perspective of function, A function must done the these things.
- 1.Gets parameters passed by the calling function
- 2.Save the return address and before-calling condition to make sure that the program flow could be returned to the calling site.
- 3.Make spaces for variables in the function
- 4.Gets instructions in the functions done
- 5.Pass return value to the calling function
So, with some analysis, we can easily illustrated what should be contained in the functions' memory.
- before-calling condition backup and return address
- Passed parameters''
- Spaces for variables inside the function
- Return value
- Functions private stack
Warning:: Stack Overflow
When stack is abstract. It seems could be with unlimited size, which means you can push as many things as you want! But all stacks on every the computer has a limit. In our little hack computer, the stack is limited to RAM[] to RAM[].When you push too much things into the stack, especially in the recursion, you would change things that shouldn't be changed. This is called Stack Overflow. Stack Overflow is one of the most appeared programming problems. And basically, no one can save your ass! So ,when you are writing recursion, watch out stack overflow!
Call Implementation
Now it comes to the exciting part! Implementation!
Between the call and function
Before we start, we must be clear the responsibility between the calling function and called function! When you call a function, the program flow is sequenced. It's hard to tell which part should be done by the calling function/ called function. I will introduced a way to distinguish these instructions. Of course, you can have your own understanding and implementation. But this way is the most common way to do so.
In this way, the calling function is responsible for pass arguments, save the return address, preserve the state of caller and set variables for the callee. The called function is only responsible for give spaces for its variables. Pass arguments and save the return address is of course caller's job. Because the callee can't know what's the arguments and who called him. But why preservation and set variables for the callee is also the caller's job? This is because of the stack. Arguments is data belongs to the function, so it’s data on top of caller’s stack. Local variables need space, but the callee’s stack needs unpredictable space. So the locals are needed to be at the bottom of the stack. Without the caller tells the callee that where the stack bottom is, It may cause unpredictable act.
Call
So with analysis in 8.4.1, there are three things are needed to do in the call command.
- Save the return address
- Preserve the environment variables
- Jump to the function
So we can write a pseudo code. So we can abstract this complex process in to a more readable way.
- Push returnaddress
- Push LCL
- Push ARG
- Push THIS
- Push THAT
- ARG=SP-nARGS-5
- LCL=SP
- Goto g
- Return address:
Note: You can use a symbol to represent return address. In that case, you need to be very careful about those names, you can try to use the knowledge of name space. Or you can just calculate the return address, since the call process is fixed. If you got it right, it’s more reliable. You can try to use the modulation way to simplify your process by using those VM commands in Chapter 7.
Function Implementation
After so many preparation take place in the call command. The function commands’ job is relatively easy. The only thing it should do is to give spaces to the local arguments. Because the caller doesn’t have an idea about how many variables the function need. It’s of course the callees’ job. We can just set the SP over the memory segments for locals. But it’s unsafe that variables may be in unpredictable value without initialized. So we initialized those variables in the function to 0. We can describe this process in the pseudo code below:
- For nVars time:
- Push 0
After this process, you can clearly see that what’s on the stack when a function is in process.
Fig 8.1 Stack after function(Image source: nand2tetires lecture 7)
Return Implementation
Return means to end the function and restore everything of the caller. The return value should have been on the top of the stack, which is obvious when stack arithmetic is implemented. To restore every thing, we can design a pseudo code as below:
Temp0=LCL
Temp1=*(temp0-5) //To get the return address
- ARG=pop //To pass back the return value
SP=ARG+1
THAT=*(temp0-1)
THIS=*(temp0-2)
ARG=*(temp0-3)
LCL=*(temp0-4)
Goto temp1
Question: Is that order could be modifi ed?
Bootstrapping
After function is implemented, we can make every program into a function. But what’s the base function and how we start it? Well we can simply set SP=256 and call an important function Sys.init. This process is called bootstrapping. However, we need to make the last piece of our VM translator. The class!
Files in vm language
For high level languages translated into VM language. The complex program will be divided several classes. You can now just think that class is a high level subprogram that contains several programs. A class is put into one VM fi les. To support this feature, we can just put those VM fi les all together and translate every function(it should be called method in this situation) into assembly language. Nothing would be a problem except ,again, the names! You should give different namespaces for every class! This is the only thing you need to focus.
Sys.init and Mai
So how the Bootstrapping process going on. Technically, this is for now none of your business. You could just let SP=256 and call the sys.init. But it’s important to know what the Sys.init and another important function, main. Sys.init is a prepare function to set variables and call the main. You can tell that Sys.init seems to belong the system. Yes ,it’s a system function to get every thing prepared to run another program. Main function is the entry of every program. Every program contains a main function. It belongs to the program and may do some real calculation.
Refinement
It’s clear that an assembly language translated from VM language is signifi cantly lower than hand-writing assembly language. For example, if we ‘re going to add 2 numbers in VM language. In VM way, you need push those two numbers into the stack, get the result and pop it. But you can do it faster by just get those two variables and add them in the register, then directly put it into the memory. It’s obviously more faster. So how can we improve the effi ciency of the program?
I have a crazy idea to do this. By not translate VM languages command by command, I tried let the translator just read the VM program and directly write the assembly code. The fi rst idea is to try every possible combination, which is an impossible mission since each line of assembly language has hundreds of possibilities. Several lines later it will beyond the computational ability of every computer on earth. So we need to do some disbranching process. I’ve tried to use MCTS and RNN neural network to solve this problem. It doesn’t work right know. Do you have better ideas?
Glossary
Function
Call
Return
Bootstrapping
Sys.init
main
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.
- coursera, https://www.coursera.org/learn/nand2tetris2, Nisan, N. S. & Schocken, S. (2008a). Build a Modern Computer from First Principles: From Nand to Tetris (Project-Centered Course).
- Nand2Tetris, http://nand2tetris.org/, Nisan, N. S. & Schocken, S. (2008c). The Elements of Computing Systems: Building a Modern Computer from First Principles.
- Hinton G E., 1986, Learning Distributed Representations of Concepts[C], Proceedings of the 8th Annual Conference of the Cognitive Science Society, ? (Number of Issues).doi: (Number of Issues).doi: ,
- Elman, J. L., Finding structure in time, CRL Technical Report 8801, Center for Research in Language, University
of California, San Diego, 1998
- Schuster M, Paliwal K K., 1997, Bidirectional recurrent neural networks[J], Signal Processing, 45(11): (Number of Issues).doi: , 2673-2681
- Graves A, Mohamed A R, Hinton G., 2013, Speech Recognition with Deep Recurrent Neural Networks[J], Acoustics Speech & Signal Processing, (Number of Issues).doi: , 6645 - 6649
- Jaeger H, Haas H., 2004, Harnessing nonlinearity: Predicting chaotic systems and saving energy in wireless communication[J], Science, 304(5667) (Number of Issues).doi: , 78-80
- Cho K, Van Merrienboer B, Gulcehre C, et al., 2014, Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation[J], Eprint Arxiv, (Number of Issues).doi: ,
- Hochreiter S, Schmidhuber J., 1997, Long short-term memory.[J], Neural Computation, 9(8) (Number of Issues).doi: , 1735-1780
- Chung J, Gulcehre C, Cho K H, et al., 2014, Empirical evaluation of gated recurrent neural networks on sequence modeling[J], arXiv preprint arXiv, 1412 (Number of Issues).doi: , 35-55
- Jan Koutnik, Klaus Greff, Faustino Gomez, Juergen Schmidhuber, 2014, A Clockwork RNN[J], Proceedings of The 31st International Conference on Machine Learning, (Number of Issues).doi: , 1863–1871
- Sutskever, Ilya, Martens, James, Dahl, George E., and Hinton, Geoffrey E.In Dasgupta, Sanjoy and Mcallester, David (eds.), , On the importance of initialization and momentum in deep learning, Proceedings of The 31st International Conference on Machine Learning(ICML-13), 28 (Number of Issues).doi: , 1139–1147