# SICP Solutions

### Chapter 4, Metalinguistic Abstraction

#### Exercise 4.78

Interesting! Learned a few subtle details of the non-deterministic computing from the previous section.

Apart from these subtle details, the solution is not difficult. Perhaps, if i have learned these few subtle things in the previous section itself than this could have turned out much easier.

So, here goes the approach:

• Since, non-deterministic evaluator itself tries out all the possibilities, we only need to handle one frame in every procedure.

• Instead of marking frame as 'failed, mark it as dead end using (amb) and which will cause evaluator to try other possible paths.

• Install all the host language immutable procedures used in the logic evaluator(like 'assoc, 'string=? etc) as primitive procedures in the non-deterministic evaluator.

• Mutable procedures are more subtle and can not be directly used as primitive procedures. For eg:
• primitve set! won’t work
• we already implemented it as special form but it’s important to understand why we can’t use the primitive form.
• the variable we are changing is defined in our environment not in the host language.
• we can not roll back to previous value.
• primitve set-car! and set-cdr won’t work because we can not roll back to previous value.

• primitive display won’t work because it does not return any value. The way non-deterministic evaluator is written, we always need a value to pass into success procedure!
• For display, we can implement a display in the code of non-deterministic evaluator which returns a value like 'ok.

• Note that while executing a program in the non-deterministic evaluator, the program won’t try any other paths unless an amb expression is encountered.

• Thus all the procedures and initialization code for microshaft database will work as in a normal evaluator implemented in the first section.

• Since all the mutations happen in initialization code for microshaft database, we can even choose to implement set-car! as permanent-set-car!. But for consistency, it might be better to support rollback.

• This example explains why not to use define for variable(here aa or bb) definitions(procedure will work) and instead use let:

This problem won’t occur with using let.

• To support interleaving, I considered using ramb(implemented in previous section ex-4.50) but it won’t work as once it chooses a path then it first generates all the values from that path and then it chooses the other path. For example:

We can solve this using let but it has its own problem. We get duplicates because it tries all combinations(remember distinct!):

Keeping track of duplicates, might solve this by providing a special form in the non-deterministic evaluator. I left it without interleaving. Probably, there can be other better solution without keeping track which I have not thought.

• Implementing not turned out to be more involved. We need a way to know that if a query results in a failure. It sorts of look like using if-fail(ex-4.52) can do the job as follows:

But it did not work! Why? Because when qeval failed, we correctly get 'failed which causes the evaluation of (amb). And evaluating (amb) caused to look for alternate path. This alternate path takes us to if-fail again which returns 'failed as alternate path(failed path). And thus if returned the frame even when qeval failed!

This made me realise that we don’t need a construct like if-fail but something like (amb) but that accepts an argument and fails if that argument succeeds. This lead to the implementation of ensure-fail. The code (ensure-fail <exp1>) <exp2> will evaluate <exp2> only if <exp1> failed. Here goes it’s implementation:

• Now, there is still one thing remaining lisp-value, which requires this procedure to be evaluated in the non-deterministic evaluator.

This can be solved simply providing eval and appply of our non-deterministic evaluator as primitive procedures. And user-initial-environment can be set similar to the way we set true and false in the setup-environment:

• Driver Loop: Since the non-deterministic evaluator will run in driver loop, I implemented a procedure lp. It can be called as (lp '(supervisor ?x (Bitdiddle Ben))) for executing a query. Or for assertion use:

Well thats it!

So, as already mentioned the main point that differ with the streams, is interleaving. This gets worse with multiple infinite frames/results as it may keep answering only from one path and never evaluates the other paths! Thus the order of answers won’t be same as in the streams version.

### Execution and some examples:

• Clear the environment. In scheme, I use this:
• Now start the non-deterministic evaluator.

• Evaluate the modified logic evaluator in non-deterministic evaluator. In emacs this can be done by a simple command to send the contents of a buffer to repl(where our driver loop is running).

• If initilization for database is not inside the evaluator, then do it now by invoking (initialize-data-base microshaft-data-base).

• That’s it. Few examples of it working:

### Complete code of non-deterministic evaluator

In the above evaluator, file “ch4-mceval.scm” is used which can be downloaded from mit. Note that, there is one change to be done in this file in setup-environment mentioned in the above details.