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.
- 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. - 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: 2y+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 nonnumbers in the expression (first argument) and condenses them into a list (second argument). All the elements of the list should have the form AtomNumber, the
Number should be non-0, and the list should be sorted. The ideas is: if the list is,
say, [v(-1),w2,y1] 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([x6,y2,z(-1)],[b1,x1,y2,z3],XS) should give us XS=[b(-1),x5,z(-4)]. - 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=(y3-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.
