# SICP Solutions

### Chapter 4, Metalinguistic Abstraction

#### Exercise 4.67

(I implemented this solution after doing ex-4.76)

This took me quite some time but the solution turned out quite simple.

This solution can be optimized further. As this took me already quite some time, I will just leave it at this.

Let me first write the way I arrived at the solution:

• Check how the bindings are happening by considering the “marriage” rule example of infinite loop given in the book.
• Loop is possible only by rule application.
• Think of rule application as procedure invocation.
• The loop occurs when the procedure/rule is called with same values for the formal-arguments/variables!

• (This point is specific to my solution)Store every time the procedure/rule is invoked with the binding of the variables/args of the rule/procedure. Thus store the rule/procedure conclusion/declaration with its arguments.
• (Specific to my solution)Maintain history similar to frames. Pass history by adding items in the beginning of history thus no need for assignments or history removal when rule gets applied.

Solution:

Just maintain the history of instantiated rule conclusions and replace the variables which are left after instantiation by ‘??.

#### Possible Optimization

Instead of storing instantiated pattern, story the conclusion with variables. Store a list for each conclusion whose each element contains the list of values/arguments of the variables for each invocation.

I started this but stopped because of problems with assignments. Check a partial solution in the complete code(commented - present under optimized heading in the code).

The problem is to revert the assignment, thus inside the apply-a-rule, when the rule evaluation completes, i should remove the history also that was added because of rule evaluation.