CIS 505/705 Assignment 4

Use SML/NJ to write an interpreter for a simple pocket calculator that manipulates non-negative integers using Reverse Polish Notation, and which allows intermediate results to be stored in registers for later use.

Informal Language Description

For example, on the calculator, we may type

to compute 11, or type

to compute 4*(7+2) = 36. Also, we may type

to compute 40 + 28 + 28 = 96. In this example, the stack will evolve as follows (with the top to the right):

We may even manipulate the registers as a whole: the command CLR resets all the registers to zero, whereas a command SCALE-k will multiple all register values by the natural number k. For example,

will return 6 * 14 = 84.

Specification of Input and Output

Input to your program is given as a text string, with “E” to represent Enter and also to represent the end of arguments to STO, REC, and SCALE. The third example above would thus be represented as the string

Concerning operators, you should allow at least +, -, *, div, mod, and ^ (exponentiation).

Output from your program should be the final value of the computation, as well as a list tracing how the top of the stack has evolved. In the third example, the output would thus be (~1 represents an empty stack)

Your program should proceed in a number of stages.

Stage 1 (scanning)

is a lexical analyzer, converting the input into a list of tokens. For example, the above input string

should be converted into the list

Your program should have a function called Stage1 that takes the above input string and produces the above output, ie: val Stage1 = fn : string -> string list

Stage 2 (parsing)

converts each token into a pair of type int * int, of the form (code,i) where code encodes the operator in question, according to the scheme

• code = 0
  • an integer; i is its value
• code = 1
  • a store into location i
• code = 2
  • a recall from location i
• code = 3
  • scaling by factor i
• code = 4
  • register reset
• code = 5
  • addition
• code = 6
  • subtraction
• code = 7
  • multiplication
• code = 8
  • division
• code = 9
  • remainder (modulus)
• code = 10
  • exponentiation

i is arbitrary for code values greater than 3.

For example, the previous list should become

Similar to Stage 1, your program should have a function called Stage2 that takes the output of Stage1 (using the running example input) and produces the above output, ie: val Stage2 = fn : string list -> (int * int) list

Stage 3 (simulation)

executes the list generated by Stage 2, keeping track of the content of the stack, and of the registers. The output of this stage is the output of your program, ie, (96,[~1,4,7,28,~1,40,28,68,28,96]) for the example.

Similar to Stages 1 and 2, your program should have a function called Stage3 that takes the output of Stage2 and produces the final output, ie: val Stage3 = fn : (int * int) list -> int * int list

Comments

Your program should be initiated by a function Assignment4 which takes a string and returns the results of execution. That function should be defined as: fun Assignment4(input : string) = Stage3(Stage2(Stage1(input))); You should proceed incrementally, as there will be points associated with each stage as well as the final behavior.

You should discuss, in comments within your program, which kinds of errors can occur (is it for example OK to recall a register where nothing has been stored yet?) and how your interpreter should react in those cases.

Your programming style should not rely too much on library functions. You will of course need explode to explore the content of a string, and some basic List / String operations (I used List.drop, List.filter, Int.max and Int.fromString) but otherwise it should suffice to do basic pattern matching and list manipulation. You must use at least one each of map, filter, and fold (either foldl or foldr).

You may do this exercise solo or with a partner. (When you submit, both you and your partner will submit one and the same program.)

Submit to K-State Online an .sml-file containing the (3 stages of the) interpreter, and embed in that file:

• Comments explaining how your program handles errors
• Five test cases, which consist of
  • A call to Assignment4(...); and
  • Expected output (in comments, near the test case)

Additional Test Cases

Test case 1:

Test case 2:

---

Sam Procter (very slightly modified from Torben Amtoft’s original)