Homework: BugsWorld Virtual Machine ByteCode Generator and Interpreter

This homework is necessary preparation for the lab. Make sure you type your code and bring the file to the lab so that you will not have to waste time entering it during the lab.

1. Translate the following four BL programs into their executable form in the tables next to each example using the code generation "patterns" discussed in class in Slides 30-47 in Code Generation. Use only the primitives: MOVE, TURNLEFT, TURNRIGHT, INFECT, SKIP, and HALT; unconditional jump: JUMP; and the conditional jumps: JUMP_IF_NOT_NEXT_IS_EMPTY, JUMP_IF_NOT_NEXT_IS_NOT_EMPTY, etc.) Note that the tables may be bigger than the actual length of the generated code.

PROGRAM Example1 IS
BEGIN
    IF next-is-wall THEN
        turnright
        turnright
        infect
    END IF
END Example1

PROGRAM Example2 IS
BEGIN
    IF next-is-wall THEN
        turnright
        turnright
        infect
    ELSE
        infect
        move
    END IF
END Example2

PROGRAM Example3 IS
BEGIN
    WHILE next-is-not-empty DO
        IF next-is-wall THEN
            turnright
            turnright
            infect
        ELSE
            infect
            move
        END IF
    END WHILE
END Example3

PROGRAM Example4 IS

  INSTRUCTION TurnBackAndInfect IS
        turnright
        turnright
        IF next-is-enemy THEN
            infect
        END IF
  END TurnBackAndInfect

BEGIN
    WHILE true DO
        TurnBackAndInfect
    END WHILE
END Example4

2. Complete the body of the following public static method. A discussion of the BugsWorld virtual machine and its instruction set and of Java enumerated types is in the Code Generation slides. Review your code carefully and trace it on some examples.

   /**
    * Returns the location of the next primitive instruction to execute in
    * compiled program {@code cp} given what the bug sees {@code wbs} and
    * starting from location {@code pc}.
    *
    * @param cp
    *            the compiled program
    * @param wbs
    *            the {@code CellState} indicating what the bug sees
    * @param pc
    *            the program counter
    * @return the location of the next primitive instruction to execute
    * @requires <pre>
    * [cp is a valid compiled BL program]  and
    * 0 <= pc < cp.length  and
    * [pc is the location of an instruction byte code in cp, that is, pc
    *  cannot be the location of an address]
    * </pre>
    * @ensures <pre>
    * [return the address of the next primitive instruction that
    *  should be executed in program cp given what the bug sees wbs and
    *  starting execution at address pc in program cp]
    * </pre>
    */
   public static int nextPrimitiveInstructionAddress(int[] cp, CellState wbs,
           int pc) {...}
   

   In implementing nextPrimitiveInstructionAddress, you will need the following enum type and two methods that will be provided for you (i.e., you do not need to implement them yourself):

   /**
    * BugsWorld possible cell states.
    */
   enum CellState {
       EMPTY, WALL, FRIEND, ENEMY;
   }
   
   /**
    * Returns whether the given integer is the byte code of a BugsWorld virtual
    * machine primitive instruction (MOVE, TURNLEFT, TURNRIGHT, INFECT, SKIP,
    * HALT).
    *
    * @param byteCode
    *            the integer to be checked
    * @return true if {@code byteCode} is the byte code of a primitive
    *         instruction or false otherwise
    * @ensures <pre>
    * isPrimitiveInstructionByteCode =
    *  [true iff byteCode is the byte code of a primitive instruction]
    * </pre>
    */
   private static boolean isPrimitiveInstructionByteCode(int byteCode) {...}
   
   /**
    * Returns the value of the condition in the given conditional jump
    * {@code condJump} given what the bug sees {@code wbs}. Note that if
    * {@code condJump} is the byte code for the conditional jump
    * JUMP_IF_NOT_condition, the value returned is the value of the "condition"
    * part of the jump instruction.
    *
    * @param wbs
    *            the {@code CellState} indicating what the bug sees
    * @param condJump
    *            the byte code of a conditional jump
    * @return the value of the conditional jump condition
    * @requires [condJump is the byte code of a conditional jump]
    * @ensures <pre>
    * conditionalJumpCondition =
    *  [the value of the condition of condJump given what the bug sees wbs]
    * </pre>
    */
   private static boolean conditionalJumpCondition(CellState wbs, int condJump) {...}