SICP Solutions

Chapter 4, Metalinguistic Abstraction

Exercise 4.34

Note: I built it on top of the exercise where we implemeted parameter type based evaluation, lazy, memo-lazy(ex-4.31)

This simple looking requirement took my entire day! I hope it works and have not missed any cases :)

Added the output/test after the code below.

There are many nuances, it will take some time to write all the detail. The main pointers/ideas which I think can help in understanding the code:

• As mentioned in exercise, We need to do some tagging to differentiate between the compound procedure and these cons procedures.
• Note that, it may occur that we can avoid tagging by comparing the text of expression with lambda we used to implement cons, but this is wrong because it is certainly possible to have another lambda whose text/body matches the cons lambda but they are two different procedures.
• Other possible way of avoiding tagging it to associate atleast one name with the procedure. So that we can get a procedure name like procedure-name similar to procedure-body. But this means we are changing a fundamental part of our language. So, tagging seems to be a better approach.
• We can do tagging by creating a pair of pair and our customised(or lazy we implemented) cons.
• But, ofcourse, we can not use our own cons for creating this pair. Why? :)
• The other way we can do tagging is to use, underlying cons.
• Mixing underlying cons and our cons comes with interesting results. For example, try calling display on this mixed structure :)
• How to display? Two possible ways:
• To implement display function in the implemented language like we have implemented ‘cons’.
• To implement display function in the evaluator, thus we can use our host langauge.
• Both approaches have their own pros and cons, in first approach we do not have any host language constructs available! So, we need to provide them as primitive procedures. In the second approach, we don’t have the lazy implementations of cons available to us.
• I tried the first approach, but it required availability of so many constructs like eq?, pair? and combined with the fact that the arguments our cons are lazy evaluated, it caused too many troubles.
• Second appraoch, turned out quite easier. Since I have all the evaluator code available, it turned out not a big deal to call implemented(lazy) language cons, car or cdr. We just call actual-value and pass it the syntax we want to evaluate.
• There’s only one hurdle now, Suppose the result of our evaluator(the lazy cons list) is object. Then, this call (actual-value (list 'car object)) won’t work because our evaluator will try to evaluate object which we do not want. Because object is already the result of evaluation. So, a simple solution is to put this object under a variable say 'object in the implemented langauge environment and then call (actual-value (list 'car 'object)). (Notice the quote before object).

Oh, now the main part of the exercise:

• Initially, I thought to first convert the language cons into host cons but.. since it requires traversing the list twice, I directly display it.
• I created a counter, that gets incremented every time a non-cons is printed.
• Well, ideally i guess it would be better to print in BFS order, but that would have required queue, So, I just traversed the lazy-lists with DFS traversal.
• I used the dreaded assignment for maintaining count as there seems to be no other quicker way.

I hope, I covered the main points. Since this required many changes, I am putting up the complete code:

Test Examples

First these are the outputs from my implementation as part of this exercise. Next, I also presented the output when same input is passed to the mit-scheme.

Output from MIT scheme:

Realising again that working with with lists in scheme is not very comfortable. I think most of these issue perhaps are because of my first in-depth experience with a non-typed langauge.

I generally found that there are fewer mistakes in the logical part of my approach compared to the implementation where most of the mistakes happen because I mixed wrong types.

Apart from this, this exercise is quite educational. It made me realise the nuances when we have to decide where to implement a feature? In the evaluator or on top of the implemented language.

I think, the main trouble here was because we want our evaluator to know the lazy cons. So, that it can print them. If this was not the requirement, we could have implemented it completely as procedures and it is the user concern how to print the customized cons.

But since we want that our evluator must know about the ‘cons’ because of this exercise, I think it would have been better if we implemented cons as special form instead of procedures. This would have made things easier as there was no mixing of the things from implemented language and the host language.

I am not sure if this is always possible to avoid this mixing. But, when this is the case, I think things can go quite complex and probably much more complex than this exercise.