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:

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>