Chapter 4, Metalinguistic Abstraction

Exercise 4.68


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
;;; Query input:

(assert! (rule (reverse () ())))

Assertion added to data base.

;;; Query input:

(assert! (rule (reverse (?x . ?y) ?r)
			   (and (reverse ?y ?ry)
					(append-to-form ?ry (?x) ?r))))

Assertion added to data base.

;;; Query input:

(reverse (1 2 3) ?x)

;;; Query results:
(reverse (1 2 3) (3 2 1))

;;; Query input:
(reverse (1) ?x)

;;; Query results:
(reverse (1) (1))

;;; Query input:

This (reverse (1 2 3) ?x) won’t work as it generates an infinite loop when the rule reverse is evaluated recursively. This happens because the recursive evaluation have both variables unbound and there is nothing to bound those variables in the recursive evaluations that happen later. Thus we keep evaluating the same rule again and again!

Suppose if I try to remedy this problem by writing the rule:

1
(assert! (rule (reverse ?x ?r) (reverse ?r ?x)))

This is similar to the way, book tries to fix the rule marriage.

Thus similar to the reasoning in book, it will go to infinite loop and this time both versions (reverse ?x (1 2 3)) as well as (reverse (1 2 3) ?x) can lead to infinite loop.

At this point I have postponed the previous exercise for detecting loop. Perhaps that solution would have fixed this and the above fix might have worked.