0.md

PA0: Intro. to Rust

Your goal in this assignment is to familiarize yourself with Rust, the programming language we'll be using for much of this course (I may give you some freedom in later assignments). To do so, you'll implement a couple small programs, first a Reverse Polish Notation calculator (about which more below); then a second program that analyzes the space complexity of RPN programs.

Part 0: Set Up Your Rust Environment

Before you get started, make sure you've completed the reading for the first two weeks of the course -- Chapters 1-6 and 8 of The Rust Book.

Follow the instructions at Starting with Rust or those in Chapter 1 of The Rust Book to install Rust on your local machine. When we run your code, we'll be using Rust version 1.31.1 in a Linux environment. Make sure you have exactly that version.

Part I: Reverse Polish Notation Calculator

A Reverse Polish Notation (RPN) calculator uses a stack to perform arithmetic operations expressed in so-called post-fix style -- the operation to be performed appears after, or post, the operands on which the operation is executed.

For example, here's a valid input to an RPN calculator like the one you'll be building in this assignment:

1 2 + done

the result of which is 3. At the level of an underlying stack operation of an RPN calculator, this program executes roughly the following pseudocode:

Operation	Stack
push 1	[1]
push 2	[1; 2]
y = pop	[1]
x = pop	[]
push (x + y)	[3]

The Stack column depicts the stack (with head to the right) after the Operation listed directly to the left.

Here's a slightly longer RPN program

1 2 + 4 + 5 - 6 7 8 * + + 

and its associated trace of stack operations:

Operation	Stack	Variables
push 1	[1]
push 2	[1; 2]
y = pop, x = pop	[]	x = 1, y = 2
push (1 + 2)	[3]
push 4	[3; 4]
y = pop, x = pop	[]	x = 3, y = 4
push (x + y)	[7]
push 5	[7; 5]
y = pop, x = pop	[]	x = 7, y = 5
push (x - y)	[2]
push 6	[2; 6]
push 7	[2; 6; 7]
push 8	[2; 6; 7; 8]
y = pop, x = pop	[2; 6]	x = 7, y = 8
push (x * y)	[2; 6; 56]
y = pop, x = pop	[2]	x = 6, y = 56
push (x + y)	[2; 62]
y = pop, x = pop	[]	x = 2, y = 62
push (x + y)	[64]

Your Task

Implement a calculator for arithmetic programs written in RPN style, as specified by the following grammar:

Binary Operators
b ::= + | - | * | /
 
Terms
t ::= n       //32-bit signed integers, e.g., -1, 2, 256, 0, ...
    | b       //Binary operator
    | save    //Pop from the main stack, pushing the value onto an auxiliary stack 
    | restore //Pop from the auxiliary stack, pushing the value onto the main stack

RPN Programs
p ::= t_0 t_1 ... t_n done

That is, a valid RPN program is a series of n terms, t_0 t_1 ... t_n, followed by the keyword done. Both the example programs given above are valid according to this grammar.

The special commands save and restore allow the programmer to save values from the calculator's main stack onto an auxiliary stack for later computation. Here's a program that calculates the sum of two numbers, then uses save and restore to subtract the result from 0.

7 8 + save 0 restore - done

In the stack trace for this program below, I've left out the pops and variables to make things a bit more concise.

Operation	Main Stack	Auxiliary Stack
push 7	[7]	[]
push 8	[7; 8]	[]
push (7 + 8)	[15]	[]
save 15	[]	[15]
push 0	[0]	[15]
restore 15	[0, 15]	[]
push (0 - 15)	[-15]	[]

The special term done must appear at the end of every valid RPN program, and has the effect of printing out the top value on the main stack (if any), then terminating the program. It's an error if done is encountered with no values on the stack.

Note: If there is anything after the keyword done, the program should compile and run, it will just ignore everything after done.

Examples

Program	Result
1 2 3 done	3
1 2 + 3 + 4 + 5 + done	15
1 2 3 4 5 + + + + done	15
1 2 + save 3 restore + done	6
1 2 + done 3 4 5 done	3
10 2 / save 7 restore - done	2

Specifics

1. Construct a test-case RPL program, then post it to Piazza under the label pa0. Ensure that your test program is valid according to the grammar above and unique (i.e., that it wasn't previously posted by another student -- note that this policy encourages you to post your test case early, before many other students have already posted). Posting a novel test case is worth roughly 10% of your grade on this part.

2. Write a program, rpl.rs, that reads RPL programs on stdin and prints their results on stdout, assuming the keyword done is encountered. Your program may assume, as in the grammar above, that the terms in each RPL program are whitespace-separated.

3. When printing the result of a valid RPL program, include no newline characters (hint: use print! instead of println!).

4. On valid RPL programs, your RPL interpreter should return exit code 0. On invalid RPL programs (those that attempt to perform operations without sufficient arguments for example), your interpreter should return exit code 1.

5. On or before the due date, submit your program rpl.rs on Blackboard.

Errors

The following are errors on which your interpreter should exit with a non-zero error code:

• Performing an operation, like *, with insufficient integers on the stack
• Attempting to save when there are no values on the main stack
• Attempting to restore when there are no values on the auxiliary stack
• Performing done when there are no values on the main stack

Part II: RPN Analyzer

Certain RPN programs are ill-formed, like the following which attempts to perform an addition operation with too few integers on the stack:

1 2 + + done

Operation	Main Stack
push 1	[2]
push 2	[1; 2]
push (1 + 2)	[3]
push (3 + ?)	[?]

In the second part of this assignment, you'll implement a program that analyzes an RPN program to determine (1) whether it is well formed (won't produce errors when run) and (2) if it is well formed, how large a stack the program will require to run.

In general, RPN programs may require stacks that scale with the size of the program being executed. For example:

1 2 3 4 5 6 7 8 ... N + ... + + + + + + + done

pushes a bunch of integers, from 1 to N for some large N, then repeatedly adds the results until only the sum of all the values 1 to N is left on the stack.

Your Task

Write a program, analyze.rs, that reads the same input as rpl.rs from Part I but instead outputs:

• -1 if the RPL program on stdin was invalid according to the grammar; or
• N if the the RPL program on stdin was valid, where N is the maximum number of stack slots required total, in both the main and auxiliary stacks, to execute the program.

Examples

Program	Result	Reason
1 2 3 done	3
1 2 3	-1	Missing done
1 2 + 3 + 4 + 5 + done	2
1 2 3 4 5 + + + + done	5
1 2 + save 3 restore + done	3	Main stack 2 + auxiliary stack 1
1 2 + done 3 4 5 done	2	All code after the first done is ignored

Specifics

1. Post a test case for Part II to Piazza. Make sure to include both a test RPN program and the analyzer's expected output.

2. Write a program, analyze.rs, that reads RPN programs on stdin and outputs either -1 or N on stdout, where N is the number of stack slots required to execute the program and -1 indicates an invalid RPN program as described above. In the cases where the program outputs -1, you should still use panic!() as to prevent your program from reaching a bad state.

3. Submit your program on Blackboard on or before the due date.

Part III: RPN Optimizer

Certain RPN programs, like 1 2 3 4 5 + + + + done, can be rewritten to save space (an equivalent program that uses only two stack slots is 1 2 + 3 + 4 + 5 + done). For a small amount of extra credit:

1. Implement a third program, optimize.rs, that reads an RPN program from stdin and prints to stdout a version of the program that uses the minimum possible number of stack slots. The program you print out should perform exactly the same operations read but possibly in a different order.

2. In a comment at the top of your program, explain your optimization strategy or algorithm.

3. Submit your program optimize.rs on Blackboard on or before the due date.