Home | Notes | Languages | Programs | Homework |
Program Assignment 4 |
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
In_Vars
Result
Out_Vars
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 |