CIS 505, Programming-Language Paradigms, Fall 2010.

Assignment #4 (10 points). Due on Friday, October 22, 2010, 11pm

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 
  4 Enter 7 +
to compute 11, or type 
  4 Enter 7 Enter 2 + *
to compute 4*(7+2) = 36. Also, we may type 
  4 Enter 7 * STO-2 40 REC-2 + REC-2 +
to compute 40 + 28 + 28 = 96. In this example, the stack will evolve as follows (with the top to the right): 
   []
   [4]
   [4,7]
   [28]
   []        (* 28 is being stored in register 2 *)
   [40]
   [40,28]
   [68]
   [68,28]
   [96]
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, 
  3 STO-1 7 STO-2 SCALE-2 REC-1 REC-2 *
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 
4E7*STO2E40REC2E+REC2E+
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) 

   (96,[~1,4,7,28,~1,40,28,68,28,96])
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 
4E7*STO2E40REC2E+REC2E+
should be converted into the list 
  ["4","7","*","STO2","40","REC2","+","REC2","+"]

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,5,6,7,...
register reset, addition, subtraction, multiplication,... (i is arbitrary)
For example, the previous list should become 
  [(0,4),(0,7),(7,0),(1,2),(0,40),(2,2),(5,0),(2,2),(5,0)]

Stage 3 (simulation)

executes the list generated by Stage 2, keeping track of the content of the stack, and of the registers.

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, but otherwise it should suffice to do basic pattern matching and list manipulation. Try to use higher-order functions, such as map, as much as possible.

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. You should also construct at least 5 test cases, and include a text-file log of those and their outputs.

Torben Amtoft