/**************************/ /* */ /* Answers to worksheet 4 */ /* */ /**************************/ /* Exercise 4.1: Matching terms */ /* (a) f(X, g(b, c)) and f(Z, g(Y, c)) */ /* do match, with {X -> b, Y -> c} */ /* (b) f(X, g(b, c)) and f(Z, g(Z, c)) */ /* do match, with {X -> b, Z -> b} */ /* (c) f(c, g(b, c)) and f(Z, g(Z, c)) */ /* do not match: you cannot bind Z to c and b simultaneously */ /* (d) g(Z, f(X, a, Y), h(X, Y), a) and g(W, f(V, V, U), W, U) */ /* do match, with {U -> a, V -> a, X -> a, W -> h(a, a), Z -> h(a, a)} */ /* Exercise 4.2: Flights */ /* For these definitions to work, you have to load in facts such */ /* as those given in the file flights. */ connects(dep_city(D), arr_city(A), day(DY)) :- flight(from(name(FN), city(D)), to(name(TN), city(A)), day(DY)). connects(dep_city(D), arr_city(A), day(DY)) :- flight(from(name(FN), city(D)), to(name(Via_name), city(Via_city)), day(DY)), connects(dep_city(Via_city), arr_city(A), day(DY)). /* Obviously, if the flight facts were to define circuits between */ /* cities, then there will be an infinite number of connections: */ /* your passengers can endlesslly circle the globe. */ /* Exercise 4.3: The Monkey Puzzle */ /* a) Goal state is state(X, Y, Z, has) */ /* b) Move clauses */ move(state(under_banana, on_box, under_banana, has_not), grasp, state(under_banana, on_box, under_banana, has)). move(state(Place, on_floor, Place, H), climb, state(Place, on_box, Place, H)). move(state(Place1, on_floor, Place1, H), push(Place1, Place2), state(Place2, on_floor, Place2, H)). move(state(Place1, on_floor, B, H), walk(Place1, Place2), state(Place2, on_floor, B, H)). /* c) canget */ canget(state(X, Y, X, has)). canget(S1) :- move(S1, M, S2), canget(S2). /* d) The definition is nonterminating if the argument to */ /* canget is uninstantiated, largely because there is an */ /* infinite number of places in the room from which the */ /* monkey can begin walking or pushing. Similarly, if the */ /* order of the clauses is changed so that walk and/or push */ /* precede the simple actions of climbing and grasping, the */ /* search for a solution can become infinite because the */ /* monkey can, e.g., spend all its time walking around from */ /* one of the infinite number of positions in the room to */ /* another. Thus, these causes of non-full-polymodality are */ /* similar, but the consequences are more serious in the */ /* case due to the procedural semantics of Prolog, whereby */ /* clauses are tried in the order they apear in the program.*/ /* Exercise 4.4: lt(X, Y) ---less than */ lt(0, s(X)). lt(s(X), s(Y)) :- lt(X, Y). /* The program launches an infinite computation only when both */ /* arguments are uninstantiated. Otherwise, it terminates with a */ /* suitable answer. */ /* Exercise 4.5: lte(X, Y) ---less than or equal to */ lte(X, X). lte(0, s(X)). lte(s(X), s(Y)) :- lt(X, Y). /* Exercise 4.6: sub(X, Y, Z) ---subtraction */ sub(X, Y, Z) :- add(Y, Z, X). /* Exercise 4.7: incr(X, Y) ---increment */ incr(X, s(X)). /* Exercise 4.8: double(X, Y) ---integer doubling */ double(0, 0). double(s(X), s(s(Y))) :- double(X, Y). /* Note that you can use this for halving too, but only for even */ /* numbers. */ /* Exercise 4.9: factorial(X, Y) ---factorials */ factorial(0, s(0)). factorial(s(X), Y) :- factorial(X, Z), mult(s(X), Z, Y). /* Since mult launches an infinite computation when its second and */ /* third arguments are uninstantiated, if we had the call to mult */ /* coming leftmost, the most typical calls to factorial (i.e. calls */ /* in which the user instantiates the first argument and leaves the */ /* second argument uninstantiated) would launch infinite */ /* computations. This would be because such instantiation patterns */ /* would call mult with its second and third arguments */ /* uninstantiated, but this is a mode that, we have seen, launches */ /* infinite computations for mult. So, in order to get factorial to */ /* work for these most typical modes, we have had to ignore the */ /* rule of thumb about not putting recursive calls leftmost. */ /* Exercise 4.10: exp(X, Y, Z) ---exponentiation */ exp(0, s(X), 0). exp(s(X), 0, s(0)). exp(X, s(Y), Z) :- exp(X, Y, W), mult(W, X, Z). /* A similar comment about the ordering of subgoals applies here */ /* as the one that applied in the definition of factorial. */ /* Exercise 4.11: product(X, Y, Z) ---multiplication */ product(X, Y, Z) :- prod_aux(X, Y, 0, Z). prod_aux(0, Y, Z, Z). prod_aux(s(X), Y, Acc, Z) :- add(Y, Acc, NewAcc), prod_aux(X, Y, NewAcc, Z). /* These are the definitions given in the worksheet. */ derivative(0, 0). derivative(s(N), 0). derivative(x, s(0)). derivative(x^0, 0). derivative(x^s(N), s(N)*x^N). derivative(F+G, DF+DG) :- derivative(F, DF), derivative(G, DG). /* Exercise 4.12 */ /* a) sin x */ derivative(sin(x), cos(x)). /* b) cos x */ derivative(cos(x), -sin(x)). /* c) e^x */ derivative(e^x, e^x). /* d) log x */ derivative(log(x), s(0)/x). /* Subtraction */ derivative(U-V, DU-DV) :- derivative(U, DU), derivative(V, DV). /* f) Product */ derivative(U*V, V*DU+U*DV) :- derivative(U, DU), derivative(V, DV). /* g) Division */ derivative(U/V, (V*DU-U*DV)/(V*V)) :- derivative(U, DU), derivative(V, DV). /* Exercise 4.13 */ /* mult(?, +, ++), mult(++, ?, ++), mult(++, ++, ?) */ /* In the recursive rule, the call to add is made; its second */ /* argument, Int, will be a variable, since it does not appear in */ /* the head. One relevant mode for add is add(?, ?, ++) as this */ /* allows the second argument to be a variable; it allows the */ /* first argument to be a variable (so the second argument of */ /* mult can be a variable) but inists that its third argument is */ /* instantiated, thus insisting that the third argument of mult */ /* be instantiated (see the first and second modes above). */ /* Another relevant mode for add is add(++, ?, ?), again allowing */ /* the second to be a variable. This allows its third argument */ /* and hence the third argument of mult to be variables as long */ /* as its first argument and hence the second argument of mult is */ /* instantiated (see the third mode above). */ /* Combine these considerations with an argument exactly like the */ /* one we gave for add, and you get the three modes above. */