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

Problem

In the second program assignment, you wrote an interpreter for a small vocabulary of JVM assembly commands, the set of commands generated by your "expression compiler" from the first program assignment. Here, you will repeat the process of implementing this interpreter, but in a logic programming language.

Implementation Language

For this assignment, your program must be written in Prolog. You will be programming in a "logic programming" style, as described in Chapter 15 of the text book. Since this program must be written in Prolog, appropriate use of logic programming language features is expected. In particular, you may not use any versions of assert, retract, record, erase, flag, or any of the other database features of Prolog.

As with prior programs, your solution must adhere to good programming style, including correct use of parameter passing, identifier naming, predicate length, commenting, headers for each predicate, etc.

Input Format

Write your program as a Prolog predicate called jvm_interpret. Your predicate should take four arguments:

Commands

is a list of atoms corresponding to the assembly instructions to be interpreted.

In_Vars

is a list of 26 ratios representing the current variable values.

Result

is an unbound variable that should be bound to the result produced by the interpreter.

Out_Vars

is an unbound variable that should be bound to a list of 26 ratios representing the new variable values after interpretation of the giveninstruction sequence.

For example, you might invoke your interpreter with the following goal:

  ?- jvm_interpret(
       [iconst, 2,  iconst, 57,  iconst, 3,  imul,  iadd,  ireturn],
       [ratio(0, 1), ratio(0, 1), ratio(0, 1), ratio(0, 1), ratio(0, 1),
        ratio(0, 1), ratio(0, 1), ratio(0, 1), ratio(0, 1), ratio(0, 1),
        ratio(0, 1), ratio(0, 1), ratio(0, 1), ratio(0, 1), ratio(0, 1),
        ratio(0, 1), ratio(0, 1), ratio(0, 1), ratio(0, 1), ratio(0, 1),
        ratio(0, 1), ratio(0, 1), ratio(0, 1), ratio(0, 1), ratio(0, 1),
        ratio(0, 1)],
       Result,
       Out_Vars
     ).

Your jvm_interpret predicate is not responsible for printing any information--all of its results are communicated via its parameters. It should always succeed, binding the Result parameter to the "answer" produced by evaluating the given list of JVM commands, and binding the Out_Vars parameter to a new list of 26 integers representing the final values of all variables. This setup differs slightly from Program 2.

The valid sequences of JVM commands are exactly the same as in Program 2.

Prolog Structures

At this point, you may be asking yourself: "Hey, what is ratio, and why is it being used inside that list?" Here, we are not using ratio as a predicate, we are instead using it as the name for a Prolog structure we have made up for this assignment.

Structures are a Prolog feature that is analogous to records in imperative languages. A structure is just a functor name (i.e., ratio) that we apply to a fixed number of arguments to "group" those arguments into a logical whole. In this case, we can say that a ratio is a structure that contains two pieces, or elements: its numerator and its denominator. Ratios are not a built-in type supported by Prolog, the way they are in Scheme, so in this assignment you'll have to write your own predicates to manipulate ratios.

For example, to add two ratios together, you might write a 3-argument predicate called add that takes three ratios as arguments:

add( ratio( N1, D ),
     ratio( N2, D ),
     ratio( N3, D ) ) :- N3 is N1 + N2.

This rule for add handles the case where all three ratios have the same denominator. We can also write a rule for add when the denominators are different:

add( ratio( N1, D1 ),
     ratio( N2, D2 ),
     Answer  /* Here, Answer will match an entire ratio--we
                do not need to talk about its parts separately,
                so we can just use one name for the whole thing. */
   ) :-
     /* Let's use N3/D3 as the parts of a ratio holding intermediate
        results from our calculation. */
     D3 is D1 * D2,
     N3 is (N1 * D2) + (N2 * D1),
     simplify( ratio( N3, D3 ), Answer ).

Here, presumably one has already defined simplify, which takes one rational number and returns an equivalent value in simplest terms. The definition of simplify, and the other support you will need to manage rational numbers, is part of your work in solving this programming assignment.

In all the cases above, you'll notice that we used ratio in a context where data was expected, rather than a context where an executable goal was expected--for example, in parameter positions in the head of a rule, or in parameter values in subgoals in the body of a rule. Terms (named functors applied to values) in those contexts are interpreted as structures instead of as predicate applications.

In this respect, Prolog is similar to Scheme. Terms (functors applied to values) can be data or the can be commands, depending on context, just as S-expressions can be either data or commands, depending on context. Also as in Scheme, Prolog's write predicate and its relatives can easily print out complex terms, including structures, lists of structures, and everything else you might come up with.

Implementing irem

Implementing most of the arithmetic commands on ratios is straightforward. The one exception is implementing irem. Fortunately, Prolog does have a mod command:

    ?- X is 10 mod 3.

Prolog also has a round function that rounds floating point values:

    ?- Y = 9.5, Z is round(Y).

By using these functions in combination, you can compute irem on two ratios A and B by using division to convert each ratio to an equivalent floating point number, rounding both, then applying mod.

Output Format

When called, your jvm_interpret predicate will be given one command sequence and the current variable state. Your predicate should attempt to evaluate the commands in order, starting out with an empty "data stack" to hold values. Your predicate will return its results via the Result and Out_Vars parameters. There are six different cases for the kind of answer that should be produced:

Result = 'Input contains invalid command(s).'

Produce this Result, together with unmodified variable values, if the input contains symbols that are not part of the set of tokens in our command language.

Result = 'Incorrect command syntax.'

Produce this Result, together with unmodified variable values, if the input contains only valid tokens but fails to conform to the command sequence grammar in program assignment 2 (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).

Result = 'Stack underflow.'

Produce this Result, together with unmodified variable values, if the data stack becomes empty while evaluating the input.

Result = 'Attempt to divide by zero.'

Produce this Result, together with unmodified variable values, 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.

Result = 'Failure to fully reduce stack.'

Produce this Result, together with unmodified variable values, if the data stack contains more than one value after you have completely evaluated the entire command sequence.

Result = ratio(numerator, denominator)

Produce this Result, together with new variable values, if the command sequence parses successfully, evaluates successfully, and leaves exactly one value on the data stack. The given Result must be a simplified rational number

In any case where an error occurs, the Out_Vars variable list produced by jvm_interpret should be identical to the sequence of variable values passed in as In_Vars--in other words, if there is any kind of error, none of the commands in the sequence should be executed.

Submitting Your Program

Your Prolog 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 Prolog predicate should be preceded by comments explaining its purpose and implementation.

Your program will be submitted electronically through the Curator for automatic grading. 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 4-Prolog 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