CSE 331: Section 5 — Exceptions + Subtyping (Solutions)

Task 1 - A Square and a Rectangle Walk Into a bar()...

Consider the following classes.

public class Rectangle {
  private int width;
  private int height;

  public int getWidth() { ... }
  public int getHeight() { ... }

  // @effects this.width = w
  public void setWidth(int w) { ... }

  // @effects this.height = h
  public void setHeight(int h) { ... }
}

public class Square {
  private int side;

  public int getWidth() { ... }
  public int getHeight() { ... }

  // @effects this.side = w
  public void setWidth(int w) { ... }

  // @effects this.side = h
  public void setHeight(int h) { ... }
}

public class ImmutableRectangle {
  private int width;
  private int height;

  public int getWidth() { ... }
  public int getHeight() { ... }
}

public class ImmutableSquare {
  private int side;

  public int getWidth() { ... }
  public int getHeight() { ... }
}

For each comparison below, answer Yes or No and briefly justify your answer.

Task 2 - Try and Catch Me

What if we added a new command?

/*
 *   s          swaps the top two numbers
 */

static void step(CalcStack stack, String token) {
  ⋮
  } else if (token.equals("s")) {
    int a = stack.pop();
    int b = stack.pop();
    stack.push(a);
    stack.push(b);
  }
  ⋮
}

1. Assume stack starts empty. What happens when we run 6 s p?

   1. 6 is pushed onto the stack

   2. s runs the swap implementation:

      a. a = 6, the first pop() returns 6 and removes it

      b. The second pop() throws a StackEmptyException

      c. Main catches the exception and prints it

   3. p prints the empty stack

2. Which method spec was violated by which method?

   step() violated its own spec!

   The stack changed, but the spec promised to leave it unchanged. A called method, such as pop(), can satisfy its spec while its caller breaks its own.

3. How could you repair the swap behavior?

   static void step(CalcStack stack, String token) {
     ⋮
     } else if (token.equals("s")) {
       if (stack.size() < 2) {
           throw new CalcStack.TooFewOperandsException(
               "need two numbers to swap");
       }
       int a = stack.pop();
       int b = stack.pop();
       stack.push(a);
       stack.push(b);
     }
     ⋮
   }
   

Task 3 - Don’t Take It Parse-onally

1. Why does parse catch one exception only to throw another? What does this accomplish and how does it affect main?

   Converts NumberFormatException into CalcException.

   Translates parsing failures into user-friendly calculator errors.

   main catches CalcException to handle expected errors uniformly.

2. What if parse did not catch? What would happen in main? Consider if we ran abc.

   static int parse(String token) {
       return Integer.parseInt(token);
   }
   

   Integer.parseInt("abc") throws NumberFormatException.

   Calculator.parse() does not catch it.

   Calculator.step() does not catch it.

   The catch type in Calculator.main() does not match.

   The program terminates with uncaught exception and stack trace!

3. What if we broadened what was caught in main?

   try {
       step(stack, token);
   } catch (Exception e) {
       System.out.println("error: " + e.getMessage());
   }
   

   Pros:

   NumberFormatException is a subtype of Exception. Now our main would catch the exception from Integer.parseInt("abc").

   Cons:

   Unexpected exceptions could be printed as ordinary user errors. This hides implementation bugs and allows unsafe program continuation.

   The original version of the try-catch block is what we want. This allows us to separate intended user errors from actual bugs.

Task 4 - Testing Coverage Review

1. If we write a test that never reaches a for/while loop conditional, does this count as zero loop iterations?

   No.

   Zero loop iteration coverage means we have to reach the loop conditional but never go inside the body.

2. What if the spec does not allow inputs such that we can write a test that covers 0 iterations of the loop?

   We only test on inputs allowed by the spec, so this is acceptable.

3. Consider the following method:

   /**
    * Replaces duplicate elements in an array with 0.
    *
    * @requires arr != null and every element in arr is positive.
    * @modifies arr
    * @effects For every index i, if arr[i] originally appeared at
    * an earlier index, then arr[i] is replaced with 0. Otherwise,
    * arr[i] remains unchanged. For either case, the array's
    * length does not change.
    */
   
   public static void removeDuplicates(int[] arr) {
       for (int i = 0; i < arr.length; i++) {
           boolean duplicate = false;
   
           for (int j = 0; j < i; j++) {
               if (arr[i] == arr[j]) {
                   duplicate = true;
                   break;
               }
           }
   
           if (duplicate) {
               arr[i] = 0;
           }
       }
   }
   

   Use the testing heuristics from lecture to write a test suite for the following method:

   // 0 iterations for outer loop
   // inner loop is never reached
   
   @Test
   public void emptyArray() {
       int[] arr = {};
       removeDuplicates(arr);
       assertArrayEquals(new int[]{}, arr);
   }
   
   // 1 iteration for outer loop
   // 0 iterations for inner loop
   // outer if false branch
   
   @Test
   public void singleElement() {
       int[] arr = {7};
       removeDuplicates(arr);
       assertArrayEquals(new int[]{7}, arr);
   }
   
   // 2+ iterations for outer loop
   // 1 and 2+ iterations for inner loop
   // inner if true and false branches
   // outer if true and false branches
   
   @Test
   public void repeatedDuplicates() {
       int[] arr = {4, 4, 4, 2, 2};
       removeDuplicates(arr);
       assertArrayEquals(new int[]{4, 0, 0, 2, 0}, arr);
   }
   

Task 5 - Proofs, Proofs, and More Proofs

1. Explain how P implies Q.

   {{ P: exp > 0 and base > 1 and temp = base^(exp - 1) }}
   
   {{ Q: base * temp > 1 }}
   

   base * temp = base * base^(exp - 1)    since temp = base^(exp - 1)
               = base ^ exp
               > 1 ^ 0                   since base > 1 and exp > 0
               = 1
   

   Ensure that you are not skipping the substitution of base > 1. Notice that if base < 0, and if exp is an odd number, base * temp can be < 0.

2. Explain how P implies Q.

   {{ P: 0 <= count_0 <= capacity and requested >= 0 and
          0 <= added <= requested and this.count = count_0 + added
          and this.count <= capacity and remaining = requested - added
          and (remaining = 0 or this.count = capacity) }}
   
   {{ Q: added = min(requested, capacity - count_0)
          and this.count <= capacity }}
   

   From P, we know that either remaining = 0 or this.count = capacity. We consider both cases.

   Case 1: remaining = 0

   Since remaining = requested - added, we know that added = requested. From P, we also know that this.count = count_0 + added and this.count <= capacity, which gives added <= capacity - count_0. Substituting added = requested, we get requested <= capacity - count_0. Therefore, requested is the smaller of the two values, so added = min(requested, capacity - count_0).

   Case 2: this.count = capacity

   Since this.count = count_0 + added, substituting gives capacity = count_0 + added. Subtracting count_0 from both sides gives added = capacity - count_0. From P, we also know that added <= requested, meaning capacity - count_0 <= requested. Thus, added = min(requested, capacity - count_0).

   Finally, this.count <= capacity is already given in P. Therefore, both conditions in Q hold, proving that P implies Q.

Calculator Reference

/*
 * Commands:
 *   a number   push it onto the stack
 *   +          pop two numbers, push their sum
 *   -          pop two numbers, push (second - first)
 *   *          pop two numbers, push their product
 *   /          pop two numbers, push (second / first), int div
 *   p          print the whole stack
 *   .          pop the top number and print it
 *   t          print the top number without removing it
 *   q          quit
 */

import java.util.Scanner;

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    CalcStack stack = new ListStack();
    while (true) {
        System.out.print("> ");
        if (!in.hasNextLine()) {
            break;
        }
        String line = in.nextLine();
        for (String token : line.split("\\s+")) {
            if (token.equals("")) {
                continue;
            } else if (token.equals("q")) {
                return;
            }
            try {
                step(stack, token);
            } catch (CalcStack.CalcException e) {
                System.out.println("error: " + e.getMessage());
            }
        }
    }
}

/**
 * Carries out one command.
 * @modifies stack, System.out
 * @effects carries out the command token stands for, as the class
 * comment lists them, printing what the command prints
 * @throws CalcStack.CalcException if the command cannot be carried
 * out, with a message for the user, and leaves the stack unchanged
 */
static void step(CalcStack stack, String token) {
    if (token.equals("p")) {
        System.out.println(stack.numbers());
    } else if (token.equals(".")) {
        System.out.println(stack.pop());
    } else if (token.equals("t")) {
        System.out.println(stack.top());
    } else if (token.equals("+")) {
        stack.add();
    } else if (token.equals("-")) {
        stack.subtract();
    } else if (token.equals("*")) {
        stack.multiply();
    } else if (token.equals("/")) {
        stack.divide();
    } else {
        stack.push(parse(token));
    }
}

/**
 * @return the integer that token spells
 * @throws CalcStack.CalcException if token does not spell an
 *     integer
 */
static int parse(String token) {
    try {
        return Integer.parseInt(token);
    } catch (NumberFormatException e) {
        throw new CalcStack.CalcException(
            "don't understand '" + token + "'");
    }
}

public interface CalcStack {
    /**
     * @modifies this
     * @effects pushes value onto the top of the stack
     */
    void push(int value);

    /**
     * @modifies this
     * @effects removes the top number from the stack
     * @return the number removed
     * @throws StackEmptyException if the stack is empty, and leaves
     *     the stack unchanged
     */
    int pop();

    /**
     * A command the calculator cannot carry out.
     */
    public class CalcException extends RuntimeException {
        public CalcException(String message) {
            super(message);
        }
    }

    /** A pop on an empty stack. */
    public class StackEmptyException extends CalcException {
        public StackEmptyException(String message) {
            super(message);
        }
    }

    /** An operation on a stack with fewer than two numbers. */
    public class TooFewOperandsException extends CalcException {
        public TooFewOperandsException(String message) {
            super(message);
        }
    }

    /** A divide whose divisor, the top number, is zero. */
    public class DivideByZeroException extends CalcException {
        public DivideByZeroException(String message) {
            super(message);
        }
    }
}