100 Points
Due: 10/24/01 at the start of class

Problem

In the first program assignment, you wrote a program that "compiled" simple arithmetic expressions into sequences JVM-like assembly commands. For this assignment, you are to write an interpreter for this same vocabulary of JVM assembly commands.

Implementation Language

For this assignment, the implementation language is Scheme. You will be programming in a "functional" style, as described in Chapter 14 of the text book. Since this program must be written in Scheme, appropriate use of functional language features is expected. Hence,

• You must use recursion rather than iteration.
• No assignment is permitted. Assignment is an imperative concept, based on the model of a stored memory machine, and it does not exist in pure functional languages. Scheme does have some imperative features, and those are the ones to avoid: set!, setcar!, setcdr!, and all other operations with named ending in "!" are not allowed.
• Do not use global variables--bound names with values that change over the life of your program. In fact, none of your bound names, whether global or local, should change in value over time. Global constants, with a value that never changes, are fine. For local names, think of them as names for common subexpressions that you wish to use in more than one place.
• The control structures you cannot use are do and begin. That still leaves you with plenty of control structures to work with, though. Here are some suggestions:
  • For selection, use cond or if. The if function is a special case of cond. If you only use cond, you'll probably never miss begin.
  • For iteration, use a named let. That means using recursion in spirit whenever you need to repeat a series of actions. Alternatively, you can define a separate recursive function if you prefer.
  • For grouping a series of expressions into one sequence, use let (instead of begin). This most commonly arises if you use an if instead of cond, which is one reason that cond is often preferred.

Input Format

Write your program as a Scheme function called JVM-interpret. Your function should take two arguments: a list of symbols corresponding to the assembly instructions to be interpreted, and a list of 26 integers representing the current variable values. For example, you might invoke your interpreter with the following S-expression:

    (JVM-interpret
     '(iconst 2  iconst 57  iconst 3  imul  iadd  ireturn)
     '(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
    )

Your JVM-interpret function should print out the "answer" produced by evaluating the given list of JVM commands, and then return as its result a new list of 26 integers representing the final values of all variables.

This setup differs slightly from Program 1, in that you are no longer responsible for reading from standard input or splitting a line into individual tokens (words).

A more precise description of the possible sequences of JVM commands that may be passed to your program is given by the following grammar:

    <JVM-sequence>        --> ireturn
                           |  <JVM-command> <JVM-sequence>
    <JVM-command>         --> <JVM-opcode>
                           |  <JVM-opcode-with-arg> <integer>
    <JVM-opcode>          --> iadd  | isub   | imul   | idiv
                           |  irem  | ineg   | pop    | dup    | swap
    <JVM-opcode-with-arg> --> iload | istore | iconst

Output Format

When called, your JVM-interpret function will be given one command sequence and the current variable state. Your function should attempt to evaluate the commands in order, starting out with an empty "data stack" to hold values. Your function will print out on stdout one line containing the "answer" for this command sequence, and then produce as its return value a list of 26 variable values. There are eight different cases for the kind of answer that should be produced (the "Output->" tags are only used to mark each case, and are not part of the output produced by your program):

Output->    Input contains invalid command(s).

Print this error message if the input contains symbols that are not part of the set of tokens in our command language.

Output->    Incorrect command syntax.

Print this message if the input contains only valid tokens but fails to conform to the command sequence grammar in this assignment (e.g., missing the argument to iload, failing to terminate the sequence with ireturn, argument out of range for iload or istore, and so on).

Output->    Stack underflow.

Print this message if, in evaluating the input, the data stack becomes empty.

Output->    Attempt to divide by zero.

Print this message if the command sequence parses successfully and is grammatically correct, but evaluating it requires the application of idiv or irem where the second argument (the denominator) on the stack is zero.

Output->    value

Print out value as the answer if the command sequence parses successfully, evaluates successfully, leaves exactly one value on the data stack, and that value is a whole number.

Output->    numerator/denominator = value

If the command sequence parses successfully, evaluates successfully, leaves exactly one value on the data stack, and that value is not a whole number, your program should print out that value both as a rational expression (where numerator and denominator are both integers representing the value as a rational number in lowest terms) and as a floating point value.

Output->    value (Failure to fully reduce stack.)

If your function completely evaluates the entire command sequence, and when done the data stack contains more than one value, but that top value is a whole number, your program should print the topmost value in the stack as well as this error message.

Output->    numerator/denominator = value (Failure to fully reduce stack.)

If your function completely evaluates the entire command sequence, and when done the data stack contains more than one value, and that top value is not a whole number, your program should print the topmost value in the stack both as a rational expression (where numerator and denominator are both integers representing the value as a rational number in lowest terms) and as a floating point value, and then follow it with this error message.

In any case where an error occurs, the return value produced by JVM-interpreter should be identical to the sequence of variable values passed in as a parameter--in other words, if there is any kind of error, none of the commands in the sequence should be executed.

Submitting Your Program

Your Scheme implementation is to be organized in a single file. All documentation and identifying information should be placed in comments within the single source file. The comments at the beginning of the file should identify the assignment and give your full name. Every Scheme function should be preceded by comments explaining its purpose, calling sequence, and implementation.

Your program will be submitted electronically through the Curator for automatic grading against a randomly generated test suite. To submit your program, login to the Curator using your PID and password. Be sure to select the 91312-CS 3304 Edwards 2:30-3:45 MW section when logging in. Click on "Submit", choose 2-Scheme from the project drop-down list, click "Browse" to specify your solution, and then click "Upload."

In addition, you must also turn in a printed version of your program source in class according to the rules specified in the syllabus, which also describes the late policy. Your hardcopy printout must match the highest-scoring submission sent to the Curator earliest. In other words, you may not submit your program until it works, go back and add comments and documentation, and then make a final submission of the printable version of your program. Once you receive full credit from the Curator on a submission, that is the version you must print and hand in.

Home  |   Notes  |   Languages  |   Programs  |   Homework