C Compiler for Nand2Tetris' Hack computer possible?

[Manu T.]

As the Hack computer has no concept of unsigned types and lacks certain Flags like the "Sign Flag" and the "Overflow Flag", that are used by the x86 architecture to treat signed and unsigned numbers differently, is it even possible to implement a C-to-Hack compiler.

The following two C snippets only differ in the type of the variable. Once it's unsigned int, then just int.

// Snippet One \\

unsigned int a = 0x7FFF; // Expecting int be 16 Bits on the Hack platform.
if (a+1 > 0) {
  a = 0;
}

// Snippet Two \\

int a = 0x7FFF;
if (a+1 > 0) {
  a = 0;
}

On a x86 computer, snippet one will be converted to a row of assembler/machine instructions, using the ja (jump if above) instruction to represent the comparison. While snippet 2 will use the jg (jump if greater) instruction. jg is dependent on the Sign Flag and the Overflow Flag, additionally to the Zero Flag.

As far as my understanding goes, a C-to-Hack compiler could not compile C code with usage of unsigned types. Is this correct, would the C language need to be reduced to a subset language in order to be compatible to Hack?

[cadet1620]

It would be possible to write a C compiler for Hack.

Using the compiler / VM translator scheme, the compiler would simply use new VM commands to do unsigned comparisons, sat ult and ugt. It would be the VM translator's job to write appropriate ASM to do the unsigned compares.

(Note that the simple ASM code that students usually write for gt and lt is not true signed comparison; the D=x, D=D-y, D;JGT code fails if abs(x-y) >= 32768.)

Assuming that the VM translator writes correct signed compare code for gt and lt that handles full input range, it is possible to write unsigned compares in Jack:

function boolean ugt (/*unsigned*/ int ux, /*unsigned*/ int uy) {
    int INT_MIN;
    let INT_MIN = ~32767;   // 0x8000
    return (ux-INT_MIN) > (uy-INT_MIN);
}

Likewise, you can do tricky things to get around not having carry and sign status bits. For instance, here's a double-word left shift and a right rotate:

    int MSW, LSW;
    boolean sign;

    // left shift MSW:LSW
    let MSW = MSW+MSW-(LSW<0);  // Yes, that's a minus
    let LSW = LSW+LSW;

    // left rotate LSW
    let sign = (LSW < 0);
    let LSW = LSW+LSW-sign;

At one point when I was between contracts I got bored and wrote a floating point class in Jack.  A bit later I write a Trigonometry class using Float.

--Mark