Logical operations

[Nick DeMonner]

Hi there,

I'm at a loss on how to implement eq, gt, and lt for my VM translator. I know I'm missing something really simple, but I can't see it. Any hints (no answers please!) would be appreciated.

[Shimon Schocken]

Nick hi: I assume that you implement the VM Translator by writing a program that translates VM language code into Hack assembly code. If that is the case, you handle logical operations just like arithmetic operations -- which I assume you know how to handle (you did not mention them in your post).  Just like the arithmetic operations, each logical operation (say, "and") pops its operand(s) from the stack, computes the result (say and(operand1,operand2)) and pushes this result onto the stack.

Note that both the operands and the results of these logical operations are always constant -1 (minus 1) or constant 0, representing true and false, respectively.

Your translator has to take such a logical operation (say "and") as input and generate from it the Hack code that affects the same operation as output. The generated Hack code, when executed (after further translation using the assembler), will end up manipulating SP, the stack pointer, and so on and so forth (once again -- this is exactly the same as handling "add", "sub", and so on). Let us know if this helps -- Shimon

[Nick DeMonner]

Hi Shimon,

Thanks for the response. I've actually already implemented the almost all of the Project 7 translator, but I'm unsure about the code that eq (and gt and lt) should be generating (I've got all of the rest of operations working). Should it insert some branches based on jumps, or is there some direct combination of bitwise or arithmetic operations that result in 0 or -1 being outputted from the CPU for determining if two numbers are equal?

Basically, I'm having trouble figuring out what assembly to generate for the comparative operations.

P.S. I'm using Ruby as my high-level language for writing the translator--its metaprogramming facilities make writing stuff like this fun. :)

[Shimon Schocken]

Suppose you have a "not" operation at the VM level.  Following VM translation and assembly, this operation will be translated into some Hack commands that start by popping an argument from the stack (i.e. doing this by direct manipulation of the RAM, using SP).  If the original program is valid at the VM level, it must be that the popped value will be either 0 or -1.  So, your translated code should push onto the stack either -1 or 0, respectively.  Note that these constants, -1 and 0, are built-into the assembly language.  You can write commands like M = 0, M = -1.  -- Shimon

[Jacek Dabrowski]

Nick DeMonner wrote

Thanks for the response. I've actually already implemented the almost all of the Project 7 translator, but I'm unsure about the code that eq (and gt and lt) should be generating (I've got all of the rest of operations working). Should it insert some branches based on jumps, or is there some direct combination of bitwise or arithmetic operations that result in 0 or -1 being outputted from the CPU for determining if two numbers are equal?

I think that the tip you are looking for is that you need to calculate x-y and use three of the jump commands to set the result to -1 or 0.

Can it be done with less than two labels per each eq/gt/lt command? (I know in eq it should be doable with one).

[RED]

I do not know how to handle this.
Does it require to use new label each time I use logical operation?

[Jacek Dabrowski]

Each logical operation will require a jump to a separate location (or two locations). So my guess is they need to have separate labels (there are no relative jumps on HACK platform).

[culchie]

I am confused about implementing eq, gt and lt.
I am fairly certain I can see how to do it using labels and jumps in assembly.
Obviously these labels would have to be globally unique.
In Ch 8 however the trouble is taken to explain how to make labels globally unique when discussing
program flow.
It just strikes me as odd that they would bother doing that there if they had previously expected the
readers to come up with a similar scheme by themselves in Ch 7.
So I'm thinking that maybe we're expected to achieve the translation of eq, gt and lt to assembly
without the use of labels.
I've been trying to do just that without getting very far. For instance for lt I can write assembly to evaluate to  -1
if X-Y < 0 but I can't guarantee the same code to evaluate to 0 if X-Y >= 0.
It seems impossible to me without the use of jumps and hence labels.
Is this right?

Also in a post above Shimon Schocken says
>>Note that the both the operands and the results of these logical operations
>>are always constant -1 (minus 1) or constant 0, representing true and
>>false, respectively

Is this suggesting that using just ANDs ORs NOTs you can implement eq, lt and gt without using labels?

It's the getting from any 2 numbers X,Y to just 0 or -1 without the use of labels that seems impossible to me.


 

[culchie]

OK this answer to a question I asked on Stackoverflow seems to prove that it is impossible to
implement eq, lt and gt in assembly without the use of jumps. Apparently it would be possible
if there was a right shift operator in asm or if the carry was not lost when there is an overflow
in addition.

[culchie]

If anyone is interested, the partial vm to asm translator I wrote for Ch 7 results in 22 lines of assembly (inc label) for each of eq, lt and gt. I'd like to hear how many lines others got.

[Steve G]

Thank you for digging into this.  I couldn't figure out if there was a way to implement the comparisons without jumps either.  I thought I was missing something.

I got 20 lines of hack assembly for a gt, but that doesn't include loading the stack:

[Code removed by admin.]

[culchie]

Thanks for putting up your code.
Yours is 2 steps quicker than mine because in 2 places I did
M=M-1
A=M

while you have
AM=M-1

which now seems the obvious thing to do but totally passed me by!

After changing this mine takes the same number of steps as yours but the code is quite different which I found interesting. Your code uses 2 labels while mine uses 1.
So I looked at it some more and now I'm fairly sure that it can be done in 17 steps.


PS It's great to see someone else's code, looking at yours gave me a fresh perspective however I think we're not supposed to post code here.
My revised code is a bit of a cheat but seems to work. If you're interested I'll email it to you.

[Steve G]

Thanks, culchie.

Just knowing that the comparison can be done with one label makes it clear how you did it.  Obvious in retrospect, but clever of you to figure it out.

Sorry about posting code.  I didn't know the forum etiquette.

Have fun. I'm really enjoying this book.

[Devo]

The above question is one I've been wrestling with as well - can gt/lt be implemented without labels? If not, it seems like we need a means of generating unique labels for each call to gt/lt by the VM program. My VMtranslator passes all the tests, but I'm troubled by the fact that it generates non-unique labels for gt/lt commands.

Perhaps the authors felt this issue was outside the scope of this book and so just wrote test files that wouldn't require multiple calls to gt/lt? It looks like the files for chapter 8 are similar and don't have multiple gt/lt calls.

Maybe another option would be to implement gt/lt as functions and push a return address onto the stack, etc.

Has anyone figured this out yet? :)

[culchie]

It was a few months ago since I looked at this so it's fading .... but I'm surprised that the tests passed when the labels weren't unique, could it be that the tests are not exhaustive enough?
It puzzled me at the time why it wasn't hinted to us in Ch. 7 to make the labels unique. Maybe they they don't need to be but I can't see how that could be. However your tests passing certainly points in that direction.
Anyway I didn't take any chances and I used a global variable that was incremented after each use as part of my labels' names to ensure uniqueness.
Otherwise for instance I'd suspect that jumps to the second label would risk getting directed to the first on looking up the symbol table (during the assembly process).

[Devo]

Exactly - it looks like the tests are set up so that there's never more than one call to gt or lt, so the potential problem is avoided. I figured the solution was implement a counter like you did, but since nothing was mentioned in the book I've just been wondering if I was missing something obvious. Thanks!!

[Earl]

You can do the same thing the assembler does, calculate the PC relative address of a jump, its easy if
the jump is not too far.

So it can be done with no labels.

[Dano]

I am afraid you can not. HACK jumps are always to an absolute address, never relative. There is no way to read PC register, you can only either write arbitrary value to it or increment it.

[cadet1620]

Many assemblers have a special variable, for instance "$", that represents the current instruction address so that PC relative addresses are easy to code. For example "JMP $+3".

It might make an interesting Chapter 13 project to add this to the Hack assembler. Note that you will also need to add arithmetic expression evaluation. You can reuse some of the expression parsing from your Jack compiler.

You'd be able to write something like

    @x      // D = x>y
    D=M
    @y
    D=D-M
    @$+5
    D;JGT
    D=0
    @$+3
    0;JMP
    D=-1

--Mark

[dlk]

Regarding the 'gt' and 'lt' VM operations, should the arguments on the stack be treated as
unsigned 16-bit integers or signed 16-bit integers in the comparison?

Or are 'gt' and 'lt' intended to ignore the possibility of overflow in the subtraction and simply return a result based upon whether the ALU result of the subtraction is negative / positive as a signed 16-bit integer, which doesn't agree with treating the arguments as either signed or unsigned?

For instance, with unsigned 16-bit integers:

    0 < 0xffff  is true
    but 0 - 0xffff is ALU positive
    0x7fff < 0x8000 is true
    and 0x7fff - 0x8000 is ALU negative

With signed 16-bit integers:

    0 < 0xffff is false
    and 0 - 0xffff is ALU positive
    0x7fff < 0x8000 is false
    but 0x7fff - 0x8000 is ALU negative