# SICP Solutions

### Chapter 5, Computing with Register Machines

#### Exercise 5.50

Interesting!

The whole exercise is more about integration than coding. Setting up apply took most of the time.

Here’s how i setup the code:

#### Changes in chapter-4 evaluator

File names ch4-mceval.scm contained code for chapet-4 evaluator. I took this file from mit website thus it contains no changes/customisations done as part of exercises of ch-4.

I put the whole code in an expression like this:

Before going to other parts, let me first point out few changes i made in the above code:

• intitialize the global environment.
• added few primitive procedures like -, * so that i can test factorial program :).

Here are those changes:

#### Changes in ch5-eceval-support.scm

Here, we just added few more primitive procedures:

Note: procedures installed here in the compiler are primitive procedures for evaluator. Thus we can install any procedure even which is not available in scheme and then later use it in our evaluator and even install there as a primitve procedure like we installed here scheme’s procedure as primitive procedures such that it can be used by the code written on top of evaluator!

#### setting up apply and map procedures

This is where the it took me time figuring out.

Let’s first talk about map. In the chapter-4 mceval evaluator we use map. Since this evaluator compiles on our own compiler, we need to provide map from implicitly as part of the language or just build a map in the evaluator code itself.

How to give map as part of the language?

Can we give underlying scheme map as primitive procedure like we did above for +, cons etc?

No. Because map accepts lambda and in this context this lambda is not the underlying scheme lambda but our own compiled version of lambda! The underlying scheme is not aware of our compiled represention of lambda.

The solution is we simply write map as part of a libs and while compiling evaluator, we first compile all the library these procedures like map we want to give.

Similarly we need to do with apply. But there are few more nuances for apply. Let’s first see the code how to setup this:

Note, that mceval-expression contains the code of our evaluator.

Thus, now libs-and-mceval contains all the code that needs to be compiled.

Okay, Before we put everything together, let’s first understand apply:

Recall that we need to give apply from the compiler to the evaluator.

Note that evaluator uses apply only for primtive procedures thus we can get away by writing apply which internally calls schemes underlying apply.

But, it won’t be a complete implementation of apply because it won’t work for compiled procedures!

Another approach is we give a special form apply which can understand compiled procedures!

But the special form apply won’t be a procedure like map. See how the evaluator use apply:

The first line won’t work if apply is a special form!

So, we build a special form specialform-apply and also build a procedure apply and our procedure apply internally uses specialform-apply. As show in the above code of libs.

Here’s the code of specialform-apply in the compiler(file ch5-compiler.scm):

Ofcourse, there are few procedures for this new syntax added(i added them in file ch5-syntax.scm):

Let’s put this all together:

#### Putting it all together

Now, the main part how to put all components together and compile and execute.

I used the code built in previous exercise, ch5-compiler-machine.scm and added few changes in the compiler machine so that on start it will first parse the evaluator.

Here is the updated code, after changes in the solution of previous exercise:

Note that the except for register simulator, file ch5-regsim.scm and chapter 4 evaluator ch4-mceval.scm(except the changes mentioned above) are the original files from the mit website without any changes.

The file ch5-compiler, ch5-syntax.scm and ch5-eceval-support contains changes as were done in earlier exercises including the changes mentioned in this exercise.

(i shall put the complete code of these files at the bottom of this page)

This file contains everything we need!

#### Testing/Examples

Note the call to (driver-loop) to start the evaluator inside the compiler’s read-compile-execute-print loop.

That’s it!

#### Complete code

Code in for compiler, file: ch5-compiler

Code in file ch5-eceval-support:

Complete code of syntax file, ch5-syntax.scm:

Yo!

That completes most of the exercises of sicp. As of now, i am skipping last two exercises :)