HW5 - Prolog Programming Project
You will define a relation infix_postfix which is true when
two lists representing expressions in the two little languages
described below are ``equivalent'', meaning that they describe the
same operations. The signature is infix_postfix(-,+).
infix_postfix(+,-). In other words, it can translate in both
directions.
The two little languages are called I and P, which stands for
``infix'' and ``postfix''. In each language you can express some
simple arithmetic operations on one-character variables and numbers.
Tokens and representation
To simplify processing, we will represent an expression in each
language as a list of tokens, so we will feed Prolog the list
[a,*,'(',b,+,1,')'] for the expression a*(b+1) in I.
Note that quotes have been used to allow parenthesis tokens to be
represented.
Language I
The language I uses infix arithmetic notation. It has binary
operators +, *, /, and -, and unary operators sin, cos, tan, and -.
Note that - is both a binary and a unary operator. The language I has
numbers, parenthesis, and 26 legal variables a, b, ..., z.
The precedence rules are described by example, by showing an
expression in I on the left, and then an equivalent one with extra
parenthesis on the right. Basically, the trig unary operators bind most
tightly, the binary operators * and / bind tighter than + and -, and
binary operators associate to the right. The unary - binds looser
than * and / but tighter than the binary operators + and -.
a+b+c+d+e | (((a+b)+c)+d)+e
|
a*b*c*d*e | (((a*b)*c)*d)*e
|
a-b+c+d-e | (((a-b)+c)+d)-e
|
sin a+b | (sin a)+b
|
a+b*c+d | (a+(b*c))+d
|
Language P
The language P uses postfix arithmetic notation. It has binary
operators +, *, /, - and unary operators sin, cos, tan, and ~.
Note that - is binary, and ~ is unary. The ~ operators corresponds to
unary negation. It also has numbers and the 26 variables. (You can
think of it as a stack language, where numbers and variables push
values onto the stack, and operators consume either one or two values
from the stack and push on their result. A valid expression leaves
one value on the stack, and never underflows the stack.)
There are no parenthesis and no precedence rules are needed.
The following are valid P expressions:
a b +
a b c * +
a 1 + sin
a ~ sin
denoted in Prolog as lists, eg [a,'~',sin].
Equivalence
The following are true:
infix_postfix([a,+,b], [a,b,+]).
infix_postfix([a,+,'(',b,')'], [a,b,+]).
infix_postfix([sin,a,+,b], [a,sin,b,+]).
These three, plus some more, using a less cumbersome and therefore
more readable syntax as above:
in I | in P
|
a + b | a b +
|
a + ( b ) | a b +
|
sin a + b | a sin b +
|
a - b + c + d - e | a b - c + d + e -
|
a + b * c + d | a b c * + d +
|
a * sin - b * 12 | a b 12 * ~ sin *
|
(((x))) | x
|
- a | a ~
|
a + - b | a b ~ +
|
a - - b | a b ~ -
|
a - ( - b ) | a b ~ -
|
Suggestions
To get warmed up you should define a relation to accept expressions in
I, and another to accept expressions in P. Use CFGs and difference
lists. The tricky part is to get things to parse correctly in I, so
precidence is working. This should be easier to do in isolation. You
might want to try a simplified I with just +, *, and parens, to get
started. And you'll want to consider the no-comma-expression trick
for making a grammar for C expressions, as discussed in class.
Then you'll want to get to work on the real thing. Perhaps by
starting with simplified I and P, that have only + and *. Then add
parens. Then ...
Grading
Please comment your code so we can see what is going on.
Use proper variable names and names for relations.
Make a solution plan and type it in as a block comment before you
start hacking.
Write a test suite (positive and negative) and include it in what you
hand in.
Points will be taken off for any of the following:
- poorly commented,
- badly indented or bad layout,
- hard to read due to lack of white space,
- no description of overall plan,
- mysterious (to us) variables and relations,
- poor test suite.
Handing in your solution
Your file should contain everything necessary for the assignment. Do
not run the script several times to hand in different portions of the
assignment.
Please be sure your file loads and runs properly on
swiprolog
as installed on the CS machines. Turn it in by running eg
~bap/bin/handin hw5.pl
on a regular UNM CS machine.
Due: 3:30pm, Mon Oct 29.
Barak Pearlmutter <bap@cs.unm.edu>
Shawn Stoffer <storm@cs.unm.edu>