|
|
|
|
This post was updated on .
After coming back to N2T after many years, I decided to have some fun with it and actually optimize the hell out of it. Or at least, try to. However, I ran into a small problem. As far as I can tell from the JACK specification the only loops we should be able to do are 'while' loops. This means 'for' and 'do until' loops shouldn't exist.
HOWEVER! In chapter 8 we have the ProgramFlow folder containing 2 tests: FibonacciSeries and BasicLoop.
As far as I can tell, FibonacciSeries employs a 'while' loop. No problems there. BasicLoop on the other hand uses, to my understanding, a 'do until'.
The difference between these two being that 'while' loops run 0 or more times, and 'do until' runs at least once.
This is the BasicLoop VM code:
push constant 0
pop local 0 // sum = 0
label LOOP
push argument 0
push local 0
add
pop local 0 // sum = sum + n
push argument 0
push constant 1
sub
pop argument 0 // n--
push argument 0
if-goto LOOP // if n > 0, goto LOOP
push local 0 // else, pushes sum to the stack's top
I know this is only a test file. But seeing this is bothering me somewhat as I'm messing with (and restructuring) program flow. And this little guy is giving me a headache.
|
|
Administrator
|
There a few points that can be made here that might relieve any anxiety you might be having over this.
First, Chapter 8 has nothing to do with Jack, which is a high-level, object-oriented programming language. Chapter 8 has to do with implementing a translator to convert programs written in an intermediate-level language (that I don't recall the authors giving a specific name to, other than just referring to it as a stack-oriented virtual machine language). That language has a set of virtual machine commands and you are tasked with writing a translator that can translate all of them to Hack assembly language.
Later, you will write a compiler that compiles Jack source code into a program written in the virtual machine language. But you could also write a compiler to compile a C or Java program into that virtual machine language, or you could write your programs directly in that language.
In general, you will find that you can write code in a lower-level language that you can't represent in a particular high-level language. The reverse, of course, needs to not be the case since the whole point is to transform the code from a higher-level language into a lower-level language. It is very easy to write code in Hack assembly language that you could not write a matching VM program for, and it is easy to write a VM program that you can't write a matching Jack language for. This is part of the tradeoff we are choosing to make -- we give up the power and efficiency of the lower-level language in order to gain the expressiveness, writability, readability, and maintainability of the higher-level language.
On another front, you can convert any of the looping structures, while(), for(), do...while(), do...until(), and a few other variants, into any of the others -- they have equal power. Some programming languages support more than one variant because different variants are a better match for different problems in terms of making it easier for humans to turn an algorithm for that problem into code. But, really, a given language only needs to support a single one of them, and the rest are effectively "syntactic sugar". In fact, some simple compilers will, say, convert for() and do...while() loops into equivalent while() loops and then compiler the while() loops. Many compilers will actually take this in a different direction and compiler a loop written in the high-level language into an equivalent VM or assembly language code in which the code jumps into the middle of the loop body because it recognized that the some of same code that appears before the loop as part of initialization also appears at the end of the loop body, so by doing this it eliminates some redundant code.
Jack only supports the while() in order to reduce the burden on you when you write your compiler. But you could write your compiler to recognize patterns consistent with the other looping structures and then translate those into more efficient VM code segments that are a better match for each pattern.
|
|
|
The given VM test code is not generated by the Jack Compiler, I presume it was handwritten. It is however completely valid.
The specification of the Jack language and the specification of the VM are independent from each other. Both are defining a different level of abstraction. For example, nothing would prevent you from writing a C Compiler (frontend) that generates VM Code and afterwards your VM translator (backend) will generate valid and working Hack ASM Code - as long as you stick to the specification of the VM language. Since the C language has a do while loop, the VM Code generated by that C Compiler might look similar to the one in the test file.
This is the beauty of abstraction and it is also the standard way how modern compilers work (though in a very simplified way in this case): You have a frontend (in the book referred to as Compiler) which translates the source language into some intermediate format (in this case the VM language) and you have a totally independent backend (VM translator) which converts the intermediate language into machine or assembly language for a target platform. This structure allows you to add support for more languages in a simplified way: you don't need to bother about the real architecture of the target platform, the process is the same regardless of whether the program should run on the Hack Computer or any other device. Similarly, when you have one or many frontends for programming languages, you don't need to port each of these languages to other platforms separately, it is enough to write only one new backend for the platform that translates the VM language - and not port every programming language separately.
|
|
|
short answer :
- Hack CPU can do for loops - or another loop you like. For it its: test, do something, jump back
- VM language can do any loops you like. Same model for vm engine as CPU
- Jack language *could* do other loops, but it doesnt. It would be fairly straightforward to add them (I am sure there is text to that effect in the book). You would have to modify the syntax and make it generate the relevant VM code
|
|
|
WBahn wrote
But you could also write a compiler to compile a C or Java program into that virtual machine language, or you could write your programs directly in that language.
I sort of forgot the whole point of the compiler being able to compile any arbitrary high level language into the VM language. I was focused on jack only. So you got me there.
As a curiosity, how would you translate BasicLoop into jack?
The best I can think of is:
function F(arg) {
lcl = 0
lcl += arg
arg -= 1
while(arg> 0) {
lcl += arg
arg -= 1
}
}Which to me looks a little odd. Completely functional though. So I guess it's hardly invalid after all. Just quirky.
Altering code flow to make some magic happen really is a pain in the ass. Fun though!
|
|
|
Your Jack code looks functionally equivalent. Generally every do...while can be converted to a while by duplicating the code inside the body of the loop as follows:
do {
<body>
} while (cond);
->
<body>
while (cond) {
<body>
}
|
|
|
>>But you could also write a compiler to compile a C or Java program into that virtual machine language
I am working on a c compiler (based on tinycc) that compiles directly to hack. machine code
>>Generally every do...while can be converted to a while by duplicating the code inside the body of the loop as follows:
Those two loops are not equivalent. The do while will always execute the body once
|
|
|
pm100 wrote
>>Generally every do...while can be converted to a while by duplicating the code inside the body of the loop as follows:
Those two loops are not equivalent. The do while will always execute the body once
They are equivalent. Please note that the <body> part appears twice, once before the while loop which ensures it is executed once and again inside the while loop.
|
|
|
yup my bad, brain not turned on yet
|
|
Locked
