This page details how to Trace a Prolog Program and create the Hypergraph from the Trace Output. This is not the answer to the Course Work, but it will allow it to be worked out, now that the corrections to the notes from last weeks lecture have been included!

Prolog Blocks World Assertions

	on(a,b)					/* o.1 */
	on(a,c)					/* o.2 */
	on(b,t)					/* o.3 */
	on(c,t)					/* o.4 */

	above(X,Y) :- on(X,Y)			/* a.1 */
	above(X,Y) :- on(X,Z), above(Z,Y)	/* a.2 */

Prolog Trace of Query: above(a,t)

above(a,t).
   Call:  (  5) rl_add_history([97, 98, 111, 118, 101, 40, 97, 44, 116, 41, 46]) ? creep
   Exit:  (  5) rl_add_history([97, 98, 111, 118, 101, 40, 97, 44, 116, 41, 46]) ? creep
   Call:  (  7) above(a, t) ? creep		/* test using a.1 			*/
   Call:  (  8) on(a, t) ? creep		/* test o.1 to o.4 using on(a,t) 	*/
   Fail:  (  8) on(a, t) ? creep		/* Fail 				*/
   Redo:  (  7) above(a, t) ? creep		/* test using a.2 			*/
   Call:  (  8) on(a, _L145) ? creep		/* test o.1 to o.4 using on(a,Z1) 	*/
   Exit:  (  8) on(a, b) ? creep		/* success on o.1, now try above(Z1,t) 	*/
   Call:  (  8) above(b, t) ? creep		/* substitute b for Z1 			*/
   Call:  (  9) on(b, t) ? creep		/* test o.1 to o.4 using on(b,t)	*/
   Exit:  (  9) on(b, t) ? creep		/* success on o.3 			*/
   Exit:  (  8) above(b, t) ? creep		/* b is above t				*/
   Exit:  (  7) above(a, t) ? creep		/* therefor a is above t		*/

Yes

Don't forget that the Clause a.2 is an AND of two Clauses and both parts are investigated by prolog. Both parts must be true for the whole Clause to be true. I have used the variable Z1 in the Prolog comments and the Hypergraph picture, but the Prolog Trace output uses the variable _L145 instead.

Hypergraph of Clause: above(a,t)

The names on the lines (o.3, a.1 etc.) are the Prolog Clauses being tested Each node in the graph is the attempted Clause, with appropriate values substituted Substitution values are shown under the lines Yes or Fail indicates the success of the attempt

Coursework 2 Part b

This is the trace of the Prolog Clause route(b,b) which is for part b of the second coursework. I have commented all the lines with the names of the sub-clauses visited during the run. This makes it easier to create the Hypergraph.

route(b,b).
   Call:  (  6) rl_add_history([114, 111, 117, 116, 101, 40, 98, 44, 98, 41, 46]) ? creep
   Exit:  (  6) rl_add_history([114, 111, 117, 116, 101, 40, 98, 44, 98, 41, 46]) ? creep
   Call:  (  8) route(b, b) ? creep		/* test using r.1			*/
   Call:  (  9) path(b, b) ? creep		/* test p.1 to p.5			*/
   Fail:  (  9) path(b, b) ? creep		/* fail					*/
   Redo:  (  8) route(b, b) ? creep		/* test using r.2			*/
   Call:  (  9) path(b, _L145) ? creep		/* test p.1 to p.5			*/
   Exit:  (  9) path(b, c) ? creep		/* success p.3 (b links to c)		*/
   Call:  (  9) route(c, b) ? creep		/* test using r.1			*/
   Call:  ( 10) path(c, b) ? creep		/* test p.1 to p.5			*/
   Fail:  ( 10) path(c, b) ? creep		/* fail					*/
   Redo:  (  9) route(c, b) ? creep		/* test using r.2			*/
   Call:  ( 10) path(c, _L157) ? creep		/* test p.1 to p.5			*/
   Exit:  ( 10) path(c, a) ? creep		/* success p.4 (c links to a)		*/
   Call:  ( 10) route(a, b) ? creep		/* test using r.1			*/
   Call:  ( 11) path(a, b) ? creep		/* test p.1 to p.5			*/
   Exit:  ( 11) path(a, b) ? creep		/* success p.2				*/
   Exit:  ( 10) route(a, b) ? creep		/* success (a links to b)		*/
   Exit:  (  9) route(c, b) ? creep		/* success (c links to b)		*/
   Exit:  (  8) route(b, b) ? creep		/* success (b therefor links to b)	*/

Yes

This is the Hypergraph I managed to create for the above Trace. Take a look and let me know if you think this is okay.

This is a downloadable ZIP file of the completed Coursework 2 document.