SICP Solutions

Chapter 4, Metalinguistic Abstraction

Exercise 4.76

This did not work exactly as the old and. Because it has changed the and behaviour from procedural style to more mathematical logic style.

Few points to note for implementation:

• if a variable in frame1 is bound in frame2 then they should be compatible. To check compatibility, I think that here we can just use equal? on the values of these variables instead of checking compatibility by unificiation process.
• I still used the extend-if-possible which internally does unify match for compatibility instead of simply using equal? for the values bounded. Well, just being lazy to implement :)

I tested this with few rules from previous example but it did not work for many of them!

Let’s first see an example where it worked:

But, it did not work for many of the previous exercises.(i tried reverse, unique, and few microshaft exercises which use and).

The problem is because this has changed the and query to behave more in a mathematical logic style and less in the procedural style! Now the variables which may get bound in earlier clauses of and won’t be bound and any rule based on it might not work. It can even get into infinite loop for some case and for cases like not or lisp-value won’t work at all.

The merging of frame does not solve the problem of infinite loop of rule evaluation or constructs like not and list-value. Because the former(infinite loop) happens even before the merging of frame! And the latter case, like not returns empty stream which merging frames can’t fix.

When I implemented this i simply tried it with the last example i worked with containing and. It came from previous exercise (and (job ?x ?j) (unique (job ?anyone ?j))). And it did not worked!

The reason is j is not bounded!

Looking ahead at the next exercise, probably the problem with not and lisp-value might get fixed.

Note that the infinite loop problem can not be fixed even by the loop-detector of ex-4.67 too. The reason is loop-detector only stops the infinite loop but don’t solve the problem of unbounded values.