CS 201: Data Structures (Spring 2018)

HW09: Code interpreter

Due: Monday, 05/14 at 22:00

1. Goals

To implement an array-based structure and get experience working with a large body of preexisting code.

2. Setup

This is a pair programming assignment. You will continue with your same partner (unless I have told you otherwise).

Download the starter files and unzip.

You may find it helpful to review the Javadocs for Scanner, String, and Character classes when you do Step 3 (syntax checking).

3. Specification

Step 0: Checking out the starter code

This assignment is structured around modifying a relatively large, pre-existing code base (from the zip file). The program expressed in the code is a virtual machine (VM) simulator for a fake programming language. The code compiles and runs, with very limited capabilities, without any initial modification. So before you try writing any code of your own, you should first verify that you're starting from the right place.

  1. Compile all of the code from hw09.zip except for DequeTester.java.

    DequeTester.java should not compile, but everything else should compile with no errors. The only errors in DequeTester.java should be that the symbol CircularArrayDeque was not found (since you haven't created it!).

    If you run into any problems with this code before you start modifying it (that is, if anything goes wrong in an unexpected way), your development environment probably doesn't match the "supported" environment; that is, the Carleton lab machines. Try doing these steps on lab machines instead of your own computer to isolate any problems. The most likely issue is that your version of Java is older than ours. Update your version from Oracle's website, or just use the lab computers.

  2. Try running the MainWindow class as a Java application (that is, run java MainWindow on the command line). The VM Simulator window should appear. You should not get any error messages at this point.
  3. Open one of the given fake "programs" (that is, one of the files named program-XXXX.avaj in the fake-programs subdirectory of the starter archive) by using the Load button.

    • In the Status Information window, you should see a message like this:

      Syntax error in program-1.avaj:
Syntax checking not implemented!
Program not loaded.

      This is normal: you will implement syntax checking in Step 2.

    • On the command line (where you typed in the java command to run the program), you should see an error message that says:

      Cannot instantiate CallStack. Method calls won't work.
The CallStack class doesn't exist yet. (ClassNotFoundException)

      This is normal: you will fix it in Step 3.

Note that in the rest of this assignment, you will only need to edit three files:

  1. CircularArrayDeque.java where you write your implementation of the Deque ADT,
  2. Program.java in which you implement syntax checking, and
  3. CallStack.java where you extend your implementation.
If you'd like to take a look at the other code, you're welcome to, but you're not expected to understand it, you don't need to understand it to do this assignment, and really you should just ignore it. You will likely encounter this situation in other projects in the future; as projects get big, it's not possible for every person to understand every part of the code. Instead, comments can be used to guide you with finding what you need to know, and good abstraction means you only have to work with a small part of an existing code base.

Step 1: Your own Deque implementation

In order to do the next step (syntax checking), you'll need an implementation of the Stack ADT. To make this a little more interesting, we're going to follow the same design as Java and build an implementation of the Deque ADT. The steps below provide some tips for writing this implementation:

  1. Create a new class CircularArrayDeque that uses an array (not links!) to implement the included Deque interface. Your class should start with 
    public class CircularArrayDeque<E> implements Deque<E>
    to indicate that you're implementing a generic deque: it can store any type of object.
  2. You'll have an array as an instance variable in CircularArrayDeque. This array needs to hold generic objects. Unfortunately, Java makes it hard to construct generic arrays. Because of the way generics are actually implemented in the language, you can't say E[] array = new E[10];. (Try it: you'll see you get a compiler error!) Instead, you need to create an array of Objects and cast it to the generic type: 
    @SuppressWarnings("unchecked")
E[] tmp = (E[])new Object[10];
items = tmp;
    Here, items is an instance variable of type E[]. You've created an array of objects, and then told the compiler to treat that array as an array of objects of type E. The @SuppressWarnings("unchecked") is a way to tell the compiler that you don't want a warning about the cast from an Object array to an E array.

    Generally, you should only suppress warnings when you are very sure that there is not a better way to do what you're doing: the situation of creating a generic array is the only one I can remember where I've ever suppressed unchecked warnings.

    You may wish to read Segment 2.7 of the textbook for more on this.

  3. As implied by its name, you should treat the array as circular in your deque implementation. You should look back at your reading or class notes on queue implementations if you've forgotten what this means.

  4. When a client attempts to getFirst(), getLast(), removeFirst(), or removeLast() on an empty deque, throw a NoSuchElementException using the following code:

    throw new NoSuchElementException();
    You should import NoSuchElementException first from java.util.
  5. All of your methods in your implementation should run in O(1) time in the average case, although the add methods may occasionally take more time due to increasing the capacity of the deque.
  6. When you increase the size of your array, you should make an array that is a multiple of the current size (e.g., twice as long), not a constant amount bigger (e.g., not 10 items longer). Think about why this is more efficient: If you eventually store n items in the array, in Big Oh notation, how many calls does the former approach require versus the latter?
  7. DequeTester provides some tests of the methods you'll be writing. I encourage you to create the skeleton of your implementation first: just the method names with bodies that don't do anything or return some dummy value of an appropriate type. Then you should be able to compile DequeTester. The tests aren't completely segmented into parts that should work with just one part of the code done, but you're welcome to modify them in any way that would be helpful. I encourage you at the very least to use them when debugging your methods or trying to decide if your deque is really working properly.
  8. You may wish to write more tests, though you do not need to turn in your testing code this time.
(Bail out) Steps 2 and 3 below only rely on using your implementation as a stack. Specifically, we will be using addLast, removeLast, getLast, and isEmpty. As such, as long as you can get one side of your deque working (the back side), you will be able to continue with the rest of the assignment and get most of the points. If you go this route, have addFirst, removeFirst, and getFirst throw UnsupportedOperationException. If you are really stuck, talk to me and I will supply you with a .class file so you can continue with Steps 2 and 3.

Step 2: Syntax checking

The goal of this part is to write a method that can read through the lines of a text file and determine whether it has properly matching parentheses, square brackets, and curly braces. You'll use the Deque implementation that you just wrote to properly parse the syntax of a fake "Java-like" program.

I say "Java-like" because the "programs" that we'll be using are mostly just nonsense written in an extremely simplistic pseudocode version of Java. For now, we're only going to pay attention to the nesting of the three types of brackets, i.e., ()[]{}, in these "programs."

  1. Go into the Program class and edit the syntaxCheck(Scanner) method. Notice now that it currently just throws a SyntaxErrorException. Modify the method so that it returns true when the syntax is correct, and throws a SyntaxErrorException otherwise. Note that if you throw an exception, you do not also need to return something at that point: the method will pass the exception to the method that called it, and that method will decide what to do.
  2. Important: the only thing you should edit in the Program class is the syntaxCheck(Scanner) method. Do not change any other code.
  3. In class back in Week 3, we talked about how you can use a Stack to check for matching parentheses: this is your opportunity to implement that algorithm. You'll need to use your deque implementation, and go through the input character-by-character. You shouldn't use any stack or deque implementation other than the one you just wrote. You can implement any helper methods you want for syntaxCheck(Scanner) to call, but you shouldn't modify any other methods in this class that already exist.
  4. A switch statement might be helpful in structuring your code for this portion of the assignment, but it is not required. (Your textbook eschews switch statements.)
  5. You know how frustrating vague error messages are when you get them from the compiler or other programs? Well, now's your chance to be the change you want to see in the world! Make sure that the exceptions you throw contain helpful messages. The optional first argument to the exception constructor is a string containing the exception's message. Clearly identify in your exception the line number on which the error happened (keeping in mind that lines are traditionally counted starting from 1, not 0) and what the exact problem was. If the problem is that a bracket isn't closed, it's okay to just indicate the last line of the file as the problem.
Once you are confident in your syntax checker, try loading various fake programs with the VM Simulator. You should be able to "run" them by using the Run button. At this stage, "running" the program simply results in all the lines of the first method being printed to the status window.

Note: You must actually click the Run button in order to run programs: just loading the programs will not run them. On some operating systems, the run button doesn't appear as button-like as load, but it is still a button.

Step 3: A call stack to simulate function calls

We will create a class CallStack to simulate function calls.
  1. Create a new class CallStack that extends CircularArrayDeque<Method>. Specifically, your class must have the following signature: 
    public class CallStack extends CircularArrayDeque<Method>
    This means that CallStack is a subclass of your CircularArrayDeque that only stores Methods (just like your SortedLinkedList only stored ZooAnimals).
  2. Create a constructor for CallStack that takes a SimulationComponent as an argument, and saves a reference to the SimulationComponent as an instance variable.
  3. You'll actually be making this class behave like a stack, so you don't want the user to be able to add to the front, remove from the front, or look at the front (i.e., getFront). Thus, override each of these methods and make them simply throw an UnsupportedOperationException. This is a built-in Java exception in the package java.lang.
  4. This stack should behave like your original deque implementation for the remaining methods, except that when Methods are pushed to the stack, in addition to performing addLast (see below), you should call the addMethodToGraphicalStack(Method) method of your SimulationComponent instance, passing it the Method that was just added. Similarly, when Methods are removed from the stack, you should call the removeMethodFromGraphicalStack(Method) method of your SimulationComponent in addition to peforming the pop.
  5. In a subclass, you can call a super class method using super. For instance, if I wanted to call the addLast method in CircularArrayDeque inside of CallStack, I would write super.addLast(). This can be a great way to avoid duplicating code.
  6. Change (override) any methods you need to in order to make CallStack behave correctly as a stack that holds Methods and that adds or removes the relevant methods from the SimulationComponent when they are added or removed from the stack, respectively.
  7. Note that when making a subclass, you only have to override methods that you want to change. Thus, if any of your methods don't have to change, you don't have to—and indeed should not—write new versions of them. Step 3 actually requires very little code: you are simply delegating actions to other classes as appropriate.
Once it is fully working, you should be able to load and run programs, and watch as methods take up space in memory and use up a program's stack space. You should not need to write any additional code to get this working, as the program will automatically check for the existence of your call stack. (Note that as above you do need to click the Run button to run the programs.)

4. Code notes

5. Submission and grading

Submit to Moodle a zip archive containing:

Follow the previously established guidelines. In particular, do not include any other files.

Assignment requirements

This is a partial list of the things that we'll be looking for when evaluating your work (in addition to style):

Grading

This assignment modified from one designed by Andy Exley, Jadrian Miles, and Anna Rafferty.

Start early, have fun, and discuss questions on Moodle.