Lab 3: P.S. It’s Just a Stack!¹

Assigned: Monday, January 24
Check-in Post: Before 9pm Thursday, January 27 (check-in forum)
Due: 9pm Monday, January 31
Collaboration: Partner assignment (groups of 2 people—you may also work alone)
Handout: starter project
Submit: Upload Interpreter.java to Lab 3.
Reference:
- Stacks & Queues
- Iterators

Overview

In this lab we will investigate a small portion of a stack-based language called PostScript. PostScript is a file format often used with printers. In fact, the file you send to your printer is a program that instructs your printer to draw the appropriate output. PostScript is stack-based: integral to the language is an operand stack. Each operation that is executed pops its operands from the stack and pushes on a result. There are other notable examples of stack-based languages, including forth, a language commonly used by astronomers to program telescopes. If you have an old Hewlett-Packard calculator, it likely uses a stack-based input mechanism to perform calculations. You will implement a some of the operators available in PostScript, including arithmetic, numerical comparisons, and defining symbols. For more about PostScript, see the Discussion section.

The goals for this lab are

Practice using stack operations to implement a subset of the stack-based language PostScript
Practice reading javadoc-style documentation to learn how to use classes you didn’t write
Practice breaking up a class implementation into methods

Preparatory Exercises

Read the rest of this writeup, paying particular attention to the Discussion section examples of how PostScript works. I also demo these in the video below.
Look over the documentation for the Token and Reader classes your PostScript interpreter will use.
Watch the introductory video. Follow along to get started on your processToken method and see how a switch statement is used.

Introductory Video

Panopto viewer link

Suggested Timeline

Preparatory Exercises and steps 1 through 3 of Procedure by Wednesday
Steps 4 through 7 of Procedure by Friday
Steps 8 through 11 of Procedure by Monday

Final Steps

Steps 12 and 13 will likely be challenging and are only worth 2 points of the final grade.

Discussion

To get a sense of how PostScript works, it will be helpful to see some examples:

The following program computes 1 + 1:
```
1 1 add pstack
```
Every item you type in is a token. Tokens include numbers, booleans, or symbols. Here, we’ve typed in two numeric tokens, followed by two symbolic tokens. Each number is pushed on the internal stack of operands. When the add token is encountered, it causes PostScript to pop off two values and add them together. The result is pushed back on the stack. (Other mathematical operations include sub, mul, and div.) The pstack command causes the entire stack to be printed, one value per line, from top to bottom. In this case prints 2.0.
Provided the stack contains at least one value, the pop operator can be used to remove it. Thus, the following computes 2 and prints nothing:
```
1 1 add pop pstack
```
The following program computes 1 + 3 * 4:
```
1 3 4 mul add pstack
```
The result printed here, 13, is different than what is computed by the following program:
```
1 3 add 4 mul pstack
```
In this case the addition is performed first, printing 16.
Some operations simply move values about. You can duplicate values—the following squares the number 10.1 using dup to push a second 10.1 onto the stack:
```
10.1 dup mul pstack pop
```
The exch operator to exchange two values, computing 1 − 3 with this program:
```
3 1 exch sub pstack pop
```
Comparison operations compute logical values:
```
1 2 eq pstack pop
```
tests for equality of 1 and 2, and puts false on the stack to be printed. The program
```
1 1 eq pstack pop
```
yields a value of true.
Symbols are defined using the def operation. To define a symbolic value we specify a escaped symbol (preceded by a slash) and the value, all followed by the operator def:
```
/pi 3.141592653 def
```
Once we define a symbol, we can use it in computations:
```
/radius 1.6 def
pi radius dup mul mul pstack pop
```
computes and prints the area of a circle with radius 1.6. After the pop, the stack is empty.

To help you implement your PostScript interpreter, the starter project includes three classes you will find useful:

Token (documentation). An immutable (constant) object that contains a double, boolean, or symbol. Different constructors allow you to construct different Token values. The class also provides methods to determine the type and value of a token.

Reader (documentation). A class that allows you to read Tokens from an input stream (either the terminal or a file). The typical use of a reader is as follows:

Reader r = new Reader();
while (r.hasNext()) {
    Token t = r.next();
    // only check for quit if token is a symbol:
    if (t.isSymbol() && t.getSymbol().equals("quit")) {
        break;  // break statement exits the current loop
    }
    // process token
}

Note the Reader implements the Iterator interface. next always returns a value of type Token.

SymbolTable (documentation). An object that allows you to keep track of String-Token associations. Here is an example of how to save and recall the value of π:

SymbolTable table = new SymbolTable();
// sometime later:
table.add("pi",new Token(3.141592653));
// sometime even later:
if (table.contains("pi")) {
    Token token = table.get("pi");
    System.out.println(token.getNumber());
}

You will use the SymbolTable to implement the PostScript command def (step 11 of Procedure).

Procedure

In this lab you will modify the Interpreter class to implement various PostScript commands.

Download the starter project (lab3-handout.zip). Unzip it and make sure the files are in their own folder. Open the folder in VS Code.
Implement the interpret method. The tests use this method, so you must implement it as it appears in the starter code. The method should be fairly short—it should loop over the tokens in reader until there are not more tokens or it encounters the token "quit", calling processToken on each one. The Introductory Video provides an implementation of this method.
For the rest of this procedure you’ll build processToken piece by piece, implementing a few PostScript operations at a time. If you put all the code for every operation in processToken, however, it could run to more than 100 lines of code and become quite unwieldy. Instead, as you implement various commands, create a method for each one and call that method from processToken. This will help keep your Interpreter.java nice and organized.
Start by implementing the pstack command. The Introductory Video walks through how to set up switch statements for processToken and if you followed along you should already have a case "pstack": and a call to a pstack() method. Write code in the pstack method to iterate over stack and print out each token. The testPstack test should now pass, assuming you are pushing non-symbol tokens to the stack as shown in the Introductory Video.
Implement the pop command. This should just be another switch case that calls a method. The testPop test should now pass.
Implement the arithmetic commands add, sub, mul, and div. Each one should pop two values off the stack and perform the appropriate operation (addition, subtraction, multiplication, division). It’s important to remember that tokens are not the same as the values stored in the tokens. The result should be pushed back on the stack (as a new Token). You’ll want to use the tokens’ getNumber method to get the double they store, and then construct a new Token from the result to push onto the stack. For sub and div, the first value popped off the stack is the right-hand value and the second is the left-hand value. That is, sub should compute second − first and div should compute second/first. All these operations can assume there are two numbers on the top of the stack—you don’t need to handle cases where a valid operation cannot be performed. The testArithemetic test should pass once you have implemented all four commands.
Implement the boolean commands lt, gt, eq and ne. Each one should pop two values off the stack and perform the appropriate operation (less than, greater than, equal, and not equal). The result should be pushed back on the stack (as a new Token). For lt and gt, the first value popped off the stack is the right-hand value and the second is the left-hand value. That is, ls should compute second < first and gt should compute second > first. All these operations can assume there are two values on the top of the stack—you don’t need to handle cases where a valid operation cannot be performed. The testBoolean test should pass once you have implemented all four commands.
Implement the dup command. It should push a new token on the stack that is the same as the current top token. This operation can assume there is a value on the top of the stack. The testDup test should now pass.
Implement the exch command. It should swap the two values on top of the stack. This operation can assume there is are two values on the top of the stack. The testExch test should now pass.
At this point, including style and check-in post, you have earned 25.5 of the 30 points for the lab. The remaining PostScript features in this procedure are likely to be more difficult than their contribution to the lab grade would suggest. By implementing the above steps you have accomplished the main goals for this lab. If you have other pressing responsibilities, it is perfectly fine to stop at this point. See Grading for the specific point breakdown.
Implement the def command. This has two parts. First, you’ll need to handle symbol tokens that are not one the PostScript commands. Symbols that begin with a slash (e.g., "/pi") should be pushed on the stack (these are called escaped symbols). For non-escaped symbols, your interpreter should retrieve the associated token from the symbol table (table.get) and process it (by calling processToken). The default case for switch statements will be useful here: default is the code that will be run if the value doesn’t match any other case. For example,
```
switch(token.getSymbol()) {
    case "add":
        ...
    case "pstack":
        ...
    ...
    default:
        // put code to handle escaped and non-escaped symbols here
}
```
You can detect an escaped symbol vs a non-escaped symbol with the startsWith method for Strings. Second, you need to implement the def command itself. It should pop two tokens off the stack and add an entry to the symbol table (table.add). The second token will be a symbol token holding the String that will be associated with the first token in the symbol table. You’ll need to remove the "/" from the string—substring is a convenient way to do this. def does not push anything back onto the stack. The testDef test should now pass.
Implement PostScript procedures. A procedure is a series of tokens surrounded by braces (e.g., { 2 add }). In this step you need to augment your interpreter to handle the definition of functions like area shown below:
```
/pi 3.141592653 def
/area { dup mul pi mul } def
1.6 area
9 area pstack
quit
```
Such a PostScript program defines a new procedure called area that computes πr² where r is the value found on the top of the stack when the procedure is called. The result of running this code would be
```
254.469004893
8.042477191680002
```
The Token class reads procedures and stores the procedure’s Tokens in a List. Procedure tokens are pushed and popped from the stack like any other, so no changes are needed there. This step is making the procedures execute when they are retrieved from the symbol table. In the previous step, you made it so when a non-command, non-escaped symbol token is processed, the token associated with that string in the symbol table is processed. You now want to add a special case if that token is a procedure: instead of processing the procedure token itself, process the list of tokens stored in the procedure token. The testProc test should now pass.
Implement the if command. if pops two values off the stack—a boolean and a token (usually a procedure)—and executes the token if the boolean is true. This would allow the definition of the absolute value function (given a less than operator, lt):
```
/abs { dup 0 lt { -1 mul } if } def
3 abs
-3 abs
eq pstack
```
The testCountTo10 and testFib tests should now pass.

Style

For this lab, there are two new checkstyle errors you are responsible for addressing. First, method and variable names should use camel case. This means starting with a lower-case letter and capitalizing each following word, as in doArithemeticOperation. Second, no method may be longer than 60 lines. If you have a method longer than that, try moving part of its functionality to another method and calling this second method in the original. You are expected to submit a Interpreter.java that contains no checkstyle errors.

It is ok to have checkstyle warnings in your submitted code, though I encourage you to fix them if you have time. Avoiding these warnings will become part of your grade on future labs.

Grading

This lab will be graded out of 30 points as shown below. While most of the points for this lab are associated with specific test cases, partial credit can be earned for test cases that don’t pass. It it possible to earn a passing graded even if your submission does not pass any tests. Partial credit will be awarded based on evidence of a good-faith effort to implement the related features. Comments explaining your approach can help earn partial credit.

Requirement	Points
`testPstack` passes	4 points
`testPop` passes	4 points
`testArithemetic` passes	4 points
`testBoolean` passes	4 points
`testDup` passes	2 points
`testExch` passes	2 points
`testDef` passes	2.5 points
`testProc` passes	1 point
`testCountTo10` passes	0.5 points
`testFib` passes	0.5 points
`Interpreter.java` does not have any `checkstyle` errors	3 points
Check-in post	1.5 points
`Interpreter.java` compiles without warnings	0.5 points
Correct submission format (a file named `Interpreter.java`)	0.5 points

Adapted from Laboratory 10.5 in Java Structures, Duane Bailey↩︎

Lab 3: P.S. It’s Just a Stack!1