• SI 413
• Calendar
• Classes
• Labs
• Project
• Resources
• Grades
• Submit

Useful Links

• Caml language homepage. This has links to downloads (we are using version 3.11.2 of OCaml) and official documentation for the language.
• Wikipedia page
• The official ISO Developing Applications with OCaml, a French book translated into English and available for free online. Yes, there are students at universities in France that learn OCaml as their first language, from this book.
• 99 bottles of beer program.

How I will run your code

Save your program in a file called proj.ml in folders called proj1 and proj2 respectively for phases 1 and 2 of your project.

I will test your code in the same environment as the lab machines in MI 302, using the commands

  /usr/bin/ocaml proj.ml

Phase 2 Assignment

For phase 2 of your project, you will implement an interpreter for a simple RPN calculator language, described below. You should submit your program in a folder called proj2, and be sure that it runs as described above.

Specification

Your program will read characters from standard in, scan them into tokens, and interpret the tokens in the RPN language described below. There are only three tokens: numbers (which can include both floating-point numbers and integers, with or without - signs), variables (any string of letters, uppercase or lowercase), and operations (described below). You should use the built-in regular expression facilities of Ocaml to scan the input for these tokens. As usual, tokens can be separated by any amount of whitespace.

Your program will be an interpreter for a simple Reverse Polish Notation (RPN) calculator. The basic syntax of this language is that we have some operands, which for us will be either numbers or variable names, and operators, which will be detailed below. A program for this calculator is just a series of operands and operators.

RPN calculators work by maintaining a single stack of operands. Whenever the next token is an operand, we just push it onto the stack. If the next token is an operator, we pop off some elements of the stack, apply the operator, and push the result of the operation back onto the stack. You can Google RPN to get lots more information.

The operators in your RPN language will be as follows:

• p Prints the top element of the stack and removes it.
• + Adds the top two elements of the stack, replaces them with their sum.
• - Subtracts the top element of the stack from the second-to-top element, and replaces them with their difference.
• * Multiplies the top two elements of the stack, replaces them with their product.
• / Divides second-to-top element of the stack by the top element, and replaces them with their quotient.
• d Duplilcates the top element of the stack by removing it and then adding it back on twice.
• s Sets the variable, which should be second-to-the-top in the stack, with the value of the top element in the stack. These two elements are popped off of the stack and replaced by a single instance of the variable itself.
• < Tests whether the second-to-the top element is less than the top element. If so, these are replaced with the number 1, and of not, they are replaced with 0.
• > Tests whether the second-to-the top element is greater than the top element. If so, these are replaced with the number 1, and of not, they are replaced with 0.
• = Tests whether the second-to-the top element is equal to the top element. If so, these are replaced with the number 1, and of not, they are replaced with 0.
• ? This is the ternary "if" operator. If the element on top of the stack is nonzero, the top three elements are popped off and replaced with the second-to-the-top element. Otherwise, if the top is zero, the top three are popped and replaced with the third-to-the-top element.

To implement this, you will need regular expressions for all the token types, and you will also need to maintain a stack as usual for RPN calculators. Your stack will contain both numbers and variable names. To implement the variables, you will of course need to maintain a symbol table as well.

Tips

You are free to implement this in any way you wish. However, I recommend you proceed in the following steps.

1. For starters, forget about variables. First just tokenize integers from the input, and push them all onto a big stack. It is probably a good idea to print out the stack contents at every step along the way for debugging. (You should of course remove this debugging output for your final submission.)
2. Now start implementing the operations. Start with the easy ones like plus and minus. Get all the operations working with just numbers before you add the set operation or any variables.
3. Now add variables. This will require a change in your data structure for the stack. Namely, you will need to store variable names on the stack as well as integers. I recommend creating a new data type that can be either a number or a variable. This should have methods like getValue(), which will either return the number or look up the variable in the symbol table, and setValue(...), which will return an error if we have a number, and otherwise modify the symbol table accordingly.
4. Make sure you test your code extensively.

Style Requirements

You do not have to create your program in the exact way that I have suggested. However, for full credit your program should

• Be well-documented and easy to follow. Every helper function you create and every class should have documentation, and in general it should be easy for a non-Ocaml programmer to see how your program works.
• Use good style in Ocaml. The nice thing is about Ocaml is that it incorporates many different programming paradigms, so you have some flexibility here. But you should probably create and use some objects and otherwise stick mostly to the functional programming paradigm.

Example

After your RPN interpreter is working, I should be able to type in

5 2 + p

and your interpreter should print 7.

Here's a more complicated example:

2 3 d * d 4 + p - p

should print

13
-7