Lab 6: PostScript

In this week’s lab (described in Section 10.5 of Bailey), we will implement a small portion of PostScript, the stack-based programming language. PostScript was designed to describe graphical images. When you print to a PostScript printer, your computer converts your document into a program written in this language. Your printer then interprets that program in order to render the image on paper.

PRE-LAB: Step 0

Due Monday, 4/1 by 5pm.

Partner preference form. We will assign you a partner for this lab. If you would like to opt out of certain pairings (up to 3), fill out the following Google Form. If you are happy to be partnered with any classmate, you need not fill out the form.

PRE-LAB: Step 1

Before lab, please do the following:

Read the Javadoc for the Token, Reader, and SymbolTable starter files. These classes will be helpful in your implementation.
For more implementation details, skim the Token.java, Reader.java, and SymbolTable.java source files (also in your private repository) before coming to lab.
Prepare a design document for the program before lab so that you can start working right away. Please bring two copies of your document to lab so that you can give us a copy.

Lab Assignment

Complete Laboratory Assignment 10.5, which begins on page 247 of Bailey.

In addition, answer the following questions on page 246 of Bailey in a file called PROBLEMS.md, and submit it with the rest of your code this week. Note that we have added additional text in italics below to help clarify the questions.

10.3 Suppose you wish to fill a stack with a copy of another, maintaining the order of elements. Using only Stack operations, describe how this would be done. How many additional stacks are necessary? (Note: the original stack and its contents should be preserved. After completing the steps that you describe, there should be two identical stacks. You may create copies of elements.)
10.4 Suppose you wish to reverse the order of elements of a stack. Using only Stack operations, describe how this would be done. Assuming you place the result in the original stack, how many additional stacks are necessary?
10.5 Suppose you wish to copy a queue into another, preserving the order of elements. Using only Queue operations, describe how this would be done. Also, indicate the number of additional queues needed.

Helpful Notes

The starter files can be found online and in your private GitHub repository. We have also posted Javadoc documentation on the lab webpage. In addition to starter Java files, we have included several sample PostScript programs that will be useful for testing your code. PostScript files end with the .ps file extension.
Make use of the functionality of the classes that you are given. Be careful not to spend time developing code that is already there! Pay careful attention to the different class constructors, and ask questions if you have any.
Name your interpreter class Interpreter. You should only need to modify the Interpreter class and nothing else.
Your program should read commands from standard input. You can also redirect input from a file. For example, you can read thebasics.ps in the samples directory into your Interpreter program by using a command like:
```
  $ java Interpreter < samples/basics.ps
```
Make your main method very short. All it should do is create an Interpreter object and tell that object to process the PostScript program provided as standard input. Create a method interpret that takes a single parameter of type Reader and processes the PostScript tokens returned by that Reader.
Develop your interpret method incrementally. Get your simple push, pop, and pstack operations working, then move on to the arithmetic operators, and finally the definition and usage of symbols. Decompose the program into small, manageable helper methods as you go!
Your program should report errors when it encounters invalid input, and these should contain meaningful error messages. You can use Assert.condition() and Assert.fail() for this, or use the Java assert statement. Think about the different operations that may share preconditions. Can you create helper methods that meaningfully handle multiple operations?
Implementing the basic operations (pstack, add, sub, mul, div, dup, exch, eq, ne, lt, def, pop, quit, and ptable) will allow you to earn 18 out of 20 points. You can earn the last two points by implementing the extensions outlined in thought questions 3 and 4 from the book. In particular, you should implement procedure definitions and calls, and you should implement the if instruction. These extensions may require a little thought, but ought to be straightforward to implement if you have designed your interpreter well.
You can use the gs interpreter on the computers in the lab if you want to try out the commands yourself. Type the command
```
  $  gs -dNODISPLAY
```
This will give you a text-only PostScript interpreter. You can type commands at the prompt as they appear in the lab assignment. Type quit to exit the interpreter.

Lab Deliverables

By the start of lab, you should see a new private repository called cs136lab06_PostScript-{USERNAMES} in your GitHub account (where USERNAMES is replaced by your usernames).

For this lab, please submit the following:

cs136lab06_postscript-{USERNAMES}/
    README.md
    PROBLEMS.md
    MISTAKES.md
    Interpreter.java
    Reader.java
    SymbolTable.java
    Token.java
    samples/...

The Reader.java, SymbolTable.java, and Token.java files contain starter code. Interpreter.java should contain your well-documented source code.

Recall in previous labs that you had a Java file that contained a convenient main method pre-populated with a variety of helpful tests. It is always a good practice to create a small set of tests to facilitate development, and you are encouraged to do so here.

As in all labs, you will be graded on design, documentation, style, and correctness. Be sure to document your program with appropriate comments, a general description at the top of the file, and a description of each method with pre- and post-conditions where appropriate. Also, use comments and descriptive variable names to clarify sections of the code which may not be clear to someone trying to understand it.

Whenever you see yourself duplicating functionality, consider moving that code to a helper method. There are several opportunities in this lab to simplify your code by using helper methods.

Submitting Your Lab

As you complete portions of this lab, you should commit your changes and push them. Commit early and often. When the deadline arrives, we will retrieve the latest version of your code. If you are confident that you are done, please use the phrase "Lab Submission" as the commit message for your final commit. If you later decide that you have more edits to make, it is OK. We will look at the latest commit before the deadline.

Be sure to push your changes to GitHub.
Verify your changes on Github. Navigate in your web browser to your private repository on GitHub. It should be available at https://github.com/williams-cs/cs136lab06_postscript-USERNAMES. You should see all changes reflected in the files that you push. If not, go back and make sure you have both committed and pushed.

We will know that the files are yours because they are in your git repository. Do not include identifying information in the code that you submit. We grade your lab programs anonymously to avoid bias. In your README.md file, please cite any sources of inspiration or collaboration (e.g., conversations with classmates). We take the honor code very seriously, and so should you. Please include the statement "We are the sole authors of the work in this repository." in the comments at the top of your Java files.

The squeaky wheel gets the grease

We are always looking to make our labs better. Please submit answers to the following questions using the anonymous feedback form for this class:

How difficult was this assignment on a scale from 1 to 5 (1 = super easy, …, 5 = super hard).
Do you think that you will take another programming class after this one? If not, we’d love to know your reasons.

Bonus: Mistakes

Did you find any mistakes in this writeup? If so, add a file called MISTAKES.md to your GitHub repository and describe the mistakes using bullets. For example, you might write

* Where it says "bypass the auxiliary sensor" you should have written "bypass the primary sensor".
* You spelled "college" wrong ("collej").
* A quadrilateral has four edges, not "too many to count" as you state.

You will receive 1 bonus point on this assignment for each mistake we are able to validate.