Question 1

1. When placing the literal value -34 into the Hack machine's D register
   1. first the literal value -34 must be placed in the A register.
   2. first the literal value +34 must be placed in the A register.
   3. the A register is not required.
   4. the D register is loaded from the Program Counter.
2. In the Tecs stack-based Virtual Machine
   1. the stack is used to store global data and function arguments.
   2. the stack is used to store local data and object variables.
   3. operands for logic and arithmetic operations come from the stack only.
   4. every function must be recursive, as the VM is stack based.
3. The Jack language has the keywords var, let and do
   1. as the language is object-oriented.
   2. as these closely match specific features in the VM.
   3. to remove semantic ambiguities in the language.
   4. so that it is easy for a recursive decent parser to recognise the language.
   Comment: The `var', 'let' and 'do' are not needed, as a parser can still work out the meaning of the input without these keywords (e.g consider Java as a language). But it makes the writing of a parser by hand much easier.
4. For any given Hack machine instruction,
   1. there is exactly one access to RAM/ROM memory.
   2. there is between one and two accesses to RAM/ROM memory.
   3. there is between one and three accesses to RAM/ROM memory.
   4. there is between two and four accesses to RAM/ROM memory.
   Comment: Consider the instruction M=M+1. First, the instruction is fetched from ROM (1 ROM access), then the value in RAM[A] is fetched (1 RAM access). The ALU adds 1, and the result is stored back into RAM[A] (1 RAM access).
5. Given ( zx,nx,zy,ny,f,no ) = ( 1,1,1,1,1,0 ), the Hack ALU will produce the result
   1. -x + -y
   2. 0
   3. -1
   4. -2
   Comment: zx=1 sets the x-input to 0, and nx=1 does a bitwise inversion, resulting in the twos-complement value of -1. The same is done for y, resulting in -1 there. f=1 means perform addition, so the result is -2. no=0 means do not bitwise invert the output, so the final result is -2.

Question 2

1. What layer or layers in the Tecs hardware/software architecture could be augmented so that modulo arithmetic is provided to the programmer?
2. For each layer named above, describe in some detail how modulo arithmetic would be performed at that layer.

Answer to Question 2

1. Modulo could be implemented as a library function. It would be written in Jack, and it would be available to Jack programmers as a named function, e.g. function int modulo(int numerator, int denominator). Thus, modulo(7,3) would return 1.
2. Modulo could be implement in Jack as a library function, but the Jack language could be modified to place a call to the modulo() function when the % operator is used.
3. The Jack language could be modified to have the % operator. When it is invoked, the compiler would generate the right VM code to actually perform the modulo operation.
4. Both the jack language and VM could be modified to define the % operator in Jack and the mod command in VM. The actual modulo operation could be implemented as an assembly language function. When VM sees a mod command, it would output the assembly code to call the modulo function, or even just spit out the assembly code to do the modulo.
5. A new ALU operator could be defined to perform modulo. This would allow a new set of Hack instructions like A=A % D. The ALU would have to be modified to have the gate logic to do the modulu operation on the two arguments.

Question 3

1. In the Jack language, arrays cannot be passed as arguments to a function? Referring to the Jack grammar attached to the end of this paper, explain why arrays cannot be passed as arguments.
2. Create modifications to the Jack grammar which would allow arrays to be passed as arguments to a function. You can write your answer either in BNF notation, or using the notation as used in the provided Jack grammar.

Answers to Question 3

parameterList: ( (type varName) (',' type varName)*)?

subroutine( type [] varName, .....)

  paramList: param
           | param ',' paramList ;

  param:  type '[' ']' varName
        | type varName ;

Question 4

  class Add
  {
    static int result;

    // Jack function to find the biggest of 2 numbers
    function void biggest(int a, int b)
    {
      if ( a > b ) { result= a; }
      else { result= b; }
    }
  }

1. Translate the Jack code into equivalent Tecs VM instructions.
2. Assuming that the ARG and THIS memory locations point at the arguments and the base of the static memory area for the class, write equivalent Hack assembly code to find the highest value in a or b and put the value into result. Do not translate the VM code into assembly code.
3. In your opinion, will the hand-written assembly code to find the biggest of two numbers be more or less efficient than the VM code once it is translated into assembly code? Justify your opinion.

Answers to Question 4

1. Firstly, we have not done classes in Jack, so we only need to translate the function. Also note that result is the only static variable, a is argument 0 and b is argument 1. Here is the resulting VM code:

     push argument 0
     push argument 1
     gt                      # Test if a is greater than b
     if-goto IF_TRUE0        # Jump to IF_TRUE0 or IF_FALSE0
     goto IF_FALSE0
     label IF_TRUE0
     push argument 0
     pop static 0            # set result= a
     goto IF_END0
     label IF_FALSE0
     push argument 1         # set result= b
     pop static 0
     label IF_END0
   
   
2. Let us assume that ARG has the value 1000, i.e. a is at memory address 1000 and b is at memory address 1001. Also assume that THIS has value 2000, i.e. result is at memory address 2000. The values are not relevant, but the idea that ARG and THIS both point at locations in memory is important. Here's my answer:

        // Get the value of a, and store it in the D register
        @ARG
        A=M		// Remember, we want the value that ARG points at
        D=M
        // Get the value of b into the A register
        @ARG
        A=A+1
        A=M
        // Subtract a-b, store result into the D register
        D=D-A
        // Jump to the FALSE label when a is not > b
        @FALSE
        D;JLE
     (TRUE)
        // Get the value of a, and store it in the D register
        @ARG
        A=M
        D=M
        // Get the location which THIS points to
        @THIS
        A=M
        // Overwrite the value with a, which is in the D register
        M=D
        // Jump past the FALSE code
        @END
        0;JMP
     (FALSE)
        // Get the value of b into the D register
        @ARG
        A=A+1
        D=M
        // Get the location which THIS points to
        @THIS
        A=M
        // Overwrite the value with a, which is in the D register
        M=D
     (END)
   
   
3. Each VM instruction will be translated into a number of Hack assembly instructions; let's say an average of 4-5 Hack instructions. That means 13 * 4-5 or 52-65 Hack instructions. The hand-written equivalent Hack code is only 23 instructions. Therefore, the hand-written code will be more time efficient than the translated VM code, given that each instruction takes 1 clock tick; the hand-written code will also occupy less RAM and so it will be more space efficient.