CPSC 312 Functional and Logic Programming March 2021
Question One
(a) Write a program
Non- Assignment Six: Functions and Relations
No submission. Just for fun!
deriv(E,X,DE)
which is true when the DE is the derivative of expression E with respect to algebraic variable X, where an algebraic variable is just a constant. DE does not need to be in a simplified form. You can assume that E is an arithmetic expression consisting of (at least) numbers, algebraic variables, addition and multiplication. You can assume that E and X are ground (contain no logical variables) when called.
For example:
?- deriv(7+3*x, x, D).
D = 0+(3*1+x*0) .
?- deriv(x+3*x+6*x*y+ 11*x*x*y*y, x, D).
D = 1+(3*1+x*0)+(6*x*0+y*(6*1+x*0))+(11*x*x*y*0+y*(11*x*x*0+y*(11*x*1+x*(11*1+x*0)))).
You can only use the built-in predicates atomic (where atomic(X) is true when X does not involve a function symbol, e.g., atomic(fun) is true and atomic(ff+gg) is false), and dif , where dif(X,Y) means X ̸= Y .
Hint: if your program become much more complicated than the solution for eval in the previous assignment, you are on the wrong track.
(b) Define the relation:
simplify(Exp, Exp1)
which is true when Exp1 is a simplified version of expression Exp, where it simplifies multi- plying by 0, adding zero and multiplying by 1, and carrying out arithmetic that only involves numbers.
For example:
?- simplify(y*1+(0*x + x*0),E). E=y
?- simplify(y*(2*10+3),E).
E = y*23
?- simplify(1+ (3*1+x*0)+ (6*x*0+y* (6*1+x*0))+ (11*x*1+x* (11*1+x*0)), E).
E= 4+y*6+(11*x+x*11)
?- diff(x+3*x+6*x*y+ 11*x*x*y*y, x, Dx), diff(Dx,y,Dxy), simplify(Dxy,S).
…
S = 6+(y*(11*x+x*11)+y*(11*x+x*11))
You may only use the built-in predicates number, atomic, is and dif .
It is okay if the program finds less simplified forms on backtracking (but all of the answers should be correct).
1
Question Two
The Dutch national flag problem is a Problem due to Dijkstra (in his insightful book A Discipline of Programming). Given a list of elements, where for each element e, either red(e) is true, white(e) is true or blue(e) is true, return another list with the elements rearranged so that the red elements come before the white elements, which come before the blue elements, and otherwise the elements are in the same order.
Write a program dutch flag(L,D) such that D contains the same elements as L, but where the red elements come before the white elements which come before the blue elements. The ordering of the elements of the same colour should be preserved.
For example given:
red(E) :- E < 10.
white(10).
blue(E) :- E>10.
The query:
:- dutch_flag([4,9,17,3,88,10,33,0],D).
Should return:
D = [4,9,3,0,10,17,88,33]
(a) Implement the dutch flag problem using append.
(b) Implement the dutch flag problem without using append, but using difference lists. Don’t use
any built-in predicates.
(c) Write a variant of the dutch flag using difference lists, where the elements in each colour are in the reverse direction. It should only go though the list once and not create more data structures than necessary. Hint: think about how reverse works using difference lists. Don’t use any built-in predicates, and only use one helper predicate.
Note: the solutions I found using Google were terrible. It is easier to write it yourself than to try to understand these. There is a solution to this problem in Prolog that is much more straightforward than in other languages!
2