prolog

CO884, Assessment 2, Prolog For this assessment you will be dealing with the “datatype” of arithmetic expressions that is

restricted to: addition, subtraction, variables, and constants. As “variables” we do not use Prolog

variables, but Prolog atoms.

We can, in fact, specify in Prolog what an expression is:

is_expression(X):- var(X), !, fail.

is_expression(X):- atom(X); number(X).

is_expression(X+Y):- is_expression(X), is_expression(Y).

is_expression(X-Y):- is_expression(X), is_expression(Y).

The first (failing) rule is there to emphasize that Prolog variables themselves are not expressions.

Without that rule a query is_expression(_) would actually fail to terminate, rather than just

failing.

1. Write a predicate no_atoms/1 which succeeds iff its argument is an expression without

any atoms. For example, no_atoms(5-(3+x)) should fail, no_atoms((12+8)-7)

should succeed.

2. In this question we aim for an alternative representation of these expressions that is the

same for expressions with the same meaning, e.g. x+(5-x+y)+y-1 and (2-z)+(y+y)+(2+z) mean

the same thing: 2*y+4.

a. First, write a predicate number_part/2 which combines all the numbers

occurring in the expression (first argument) into one number. For example,

number_part(5-(3+x),N) should succeed with N=2 and number_part(5-

(x-3)) should succeed with N=8.

b. Second, write a predicate variable_part/2 which combines all the non-

numbers in the expression (first argument) and condenses them into a list (second

argument). All the elements of the list should have the form Atom*Number, the

Number should be non-0, and the list should be sorted. The ideas is: if the list is,

say, [v*(-1),w*2,y*1] then the original expression would be equivalent to

N-v+w+w+y, where N is the number part of the expression. Note that the ‘*’ here

in the list are not evaluated, it is just forming a pair of the atom and a number telling

us how often it occurs semantically. Note that x occurs 0 times semantically in x+(5-

x+y)+y-1, because the two occurrences of x cancel each other.

c. As auxiliary predicates for variable_part/2 it is useful to have auxiliary predicates

that add/subtract these lists of variable/value pairs. Write predicates add_list/3

and subtract_list/3 that takes two of these variable parts and add (subtract)

them, with the result in the third parameter. For example,

subtract_list([x*6,y*2,z*(-1)],[b*1,x*1,y*2,z*3],XS) should

give us XS=[b*(-1),x*5,z*(-4)].

3. We can use the predicates from question 2 to solve equations in variables. An equation is a

Prolog structure A=B where A and B are expressions. For the solution it is permitted to use

generalised expressions that also use multiplication (‘*’) and division (‘/’). Write a predicate

solve_equation/3 where its first argument is a (non-generalised) expression, its second

an atom for which we want to solve the equation, and the third the solution (a generalised

expression). For example, solve_equation(x+x+y+3+x=x+y+y-1,x,R) should succeed with

R=(y*3-4)/2. In the case that the equation does not depend on the atom for which we solve

then we either have the result being arbitrary (there are solutions, but the value for x does

not matter) or the call should fail. For example, solve_equation(x+1=x+2,x,R) should fail and

solve_equation(x+1=1+x,x,R) should succeed but leave R uninstantiated.

Note: you can use predicates from the swipl library if that helps (select/3 might be useful). You

can define auxiliary predicates if you want.

Marks: q1: 20, q2a: 20, q2b:15, q2c: 15, q3: 30.