Skip to content

Latest commit

 

History

History
210 lines (141 loc) · 10.7 KB

0.md

File metadata and controls

210 lines (141 loc) · 10.7 KB
Raw

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. 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/Git 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.57.0 in a Linux environment. Make sure you have exactly that version.

You will develop and submit your assignment through GitHub. To start this process, first accept the assignment by visiting https://classroom.github.com/a/hll4LLyE (this will create a new private repository in which you should develop your solution). Clone the repository onto your local machine in order to begin working. Your last commit to this repository before the due date will count as your assignment submission. If you forget how to use Git and/or GitHub, read more online (e.g., https://product.hubspot.com/blog/git-and-github-tutorial-for-beginners).

Rust uses a build system and package manager called Cargo. For this assignment, you'll create three Cargo projects corresponding to the assignment's three parts by typing the following commands from within your GitHub repo for the assignment:

cargo init rpn      #Part I
cargo init analyze  #Part II
cargo init optimize #Part III

To compile the code for, e.g., Part I, cd into the rpn directory, then type cargo build. To run your code directly, do cargo run.

Part I: Reverse Polish Notation Calculator (rpn)

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]
op + [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 * + + done

and its associated trace of stack operations:

Operation Stack
push 1 [1]
push 2 [1; 2]
op + [3]
push 4 [3; 4]
op + [7]
push 5 [7; 5]
op - [2]
push 6 [2; 6]
push 7 [2; 6; 7]
push 8 [2; 6; 7; 8]
op * [2; 6; 56]
op + [2; 62]
op + [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

with stack trace:

Operation Main Stack Auxiliary Stack
push 7 [7] []
push 8 [7; 8] []
op + [15] []
save 15 [] [15]
push 0 [0] [15]
restore 15 [0, 15] []
op - [-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. Write a program, <your-repo>/rpn/src/main.rs, that reads RPN 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 RPN program are whitespace-separated.

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

  3. On valid RPN programs, your RPN interpreter should return exit code 0. On invalid RPN programs (those that attempt to perform operations without sufficient arguments for example), your interpreter should return with a non-zero exit code.

  4. On or before the due date, commit your final submission to your GitHub repo for this assignment.

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 (analyze)

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]
op + [3]
op + [?]

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, 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, <your-repo>/analyze/src/main.rs, that reads the same input as the program from Part I but instead outputs:

  • -1 if the RPN program on stdin was invalid according to the grammar or will attempt an operation with insufficient arguments on the stack; or
  • N if the the RPN 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
2 0 / done 2

Note that RPN programs containing division by zero are not considered invalid. Consider, for example, the program 2 1 1 - / done. It is not clear statically that a division by zero will occur; we must first evaluate 1 1 - in order to see it. In general, we must be willing to evaluate the entire program if we want to detect division by zero errors, and thus must maintain a main and auxiliary stack just as the RPN program does. By choosing not to detect division by zero errors, we can, in principle (and I would suggest that you do in practice), implement the analyzer using constant space (that is, without a stack that could grow linearly in the size of the program as the analyzer executes).

Specifics

  1. Write a program, <your-repo>/analyze/src/main.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.

  2. On or before the due date, commit your final submission to your GitHub repo for this assignment.

Part III: RPN Optimizer (optimize, EC, due at the same time as this PA)

This part is extra credit.

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, <your-repo>/optimize/src/main.rs, that reads an RPN program from stdin and prints to stdout a version of the program that uses as few stack slots as possible. The program you print out should be equivalent to the original program, but could perform different operations, possibly in a different order. You may assume that the input program contains no 'save' or 'restore' operations (and thus does not make use of the auxiliary stack), and the optimized program should also not use 'save' or 'restore'.

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

  3. Commit your program to your GitHub repo for this assignment.

Part IV: RPN Kata Translation (Extra Credit, due at the beginning of the exam week)

Submit a translation for https://www.codewars.com/kata/52f78966747862fc9a0009ae and get it accepted. (At most one transaction will be accepted. Note that you have to reach certain level before you can submit translations to CodeWars.)

Submission

Submit the URL of your github repo to Blackboard, which should include your Github ID. If not, make sure to identify your Github ID in submission comments.