SICP Solutions

Chapter 4, Metalinguistic Abstraction

Exercise 4.77

Interesting but it took almost the whole day!

Few points to understand the solution:

• Implementing only for the queries like not and lisp-value. As suggested in problem we can call them filters.
• A filter always need all the values to be bounded(like not or lisp-value, unlike unique)
• The result of a filter, when applied to a frame, never adds anything to the resulting frame. The filter either returns the frame without any change or it returns 'failed.
• Ofcourse filter internally might add items in the frame but the returned result won’t contain any change.
• Modified the frame to contain promise as well as bindings. Added selectors for the same.
• Modifying frame might look a big change but abstraction of frame(via selectors) enabled me to easily carry out this task by modifying the frame selectors.
• There can be more than one promises(because of multiple not or multiple lisp-value in the query).
• The order in which the promised not or lisp-value are evaluated does not effect the result. It may change the order of result but number of results and individual items won’t change.
• My implementation does not guarantee any order in which promises for not or lisp-value would be evaluated.
• Since, the requirement is to evaluate the promise as soon as possible. The best place to try to evaluate a promise is when we extend a frame by a new variable!
• A promise is a pair of two things
1. list of variables in the query which is delayed/promised.
2. procedure to execute when the above variables become available to check the filter condition. Note that this procedure is just a predicate.
• keeping list of variables in a promise is a small optimization so that we need not to extract variables from the pattern every time we check if the all variables are bounded or not.
• The bounded? procedure is implemented to work for any pattern and thus can work for list of variables. Note that we need to recursively check for bounds for cases like ?x bound to (a ?y) where ?y might not be bounded.
• When evaluating a promise, make sure the frame does not contain any old promises else we can go into a loop of evaluating promises. Check comment in procedure execute-promises. This took me quite some time to debug.
• When printing force evaluate all the promises.
• My changes are on top of the changes done in loop-detector.

Code

Here are the main changes/additions for this exercise. Complete code is presented at the bottom of this page.