SICP

These are my solutions to the CS classic Structure and Interpretation of Computer Programs. I have looked up the answer for some exercises on the Scheme Community Wiki. I have marked such exercises in their respective script.

You can use the Scheme implementation by the MIT to run these scripts. In Arch, execute pacman -S mit-scheme to install it. Then run the scripts via mit-scheme --quiet < script.scm. You can also use the shell script ./run script.scm.

I haven't completely solved the following exercises.

• Exercise 1.13. I wasn't able to do the proof.
• Exercise 4.78. I managed to use the amb-evaluator for the query system, but it does not work for joined queries.
• Exercise 4.79. I did not attempt to solve this exercise because of not finishing the previous one, and it is the last one in the chapter.
• Exercise 5.52. I have implemented the Scheme to C interpreter and it works for simple programs like computing factorials or Fibonacci numbers.

I had a great time working through this book. I feel like my mental capabilities improved throughout the process, and finishing all the exercises gives me an incredible feeling of accomplishment. I have written short summaries for each of the chapters below.

Chapter 1

The first chapter of SICP starts by explaining the Scheme syntax. The first couple of exercises are simple enough. However, already at 1.5, the book foreshadows some of the difficulty that is about to come.

(define (p) (p))
(define (test x y)
  (if (= x 0) 0 y))

The goal is to decide whether Scheme uses applicative-order-evaluation or normal-order-evaluation based on the above code. I have initially found the exercise confusing, but the code triggering an infinite loop is a clear indication of Scheme (or at least my version of Scheme, MIT Scheme) using applicative-order-evaluation.

After this exercise, things get more comfortable again. The book proceeds to introduce if-else clauses, conditionals, as well as recursion. The book uses these primitives to compare iterative and recursive procedures based on a couple of typical CS example functions such as computing Fibonacci numbers, greatest common divisor, and fast exponentiation.

Two new insights I had how using modulo instead of subtracting the divisor speeds up the GCD algorithm I learned in middle school and how exponentiation can run in O(log n) by halving even exponents.

I wasn't able to prove the Golden Ration exercise at the time of working through this chapter. My knowledge of induction and proofs was too limited. I found that depressing at the time, and I wish they hadn't included that exercise.

Nevertheless, the book moves on to further essential CS concepts such as Prime numbers and the Fermat primality test. Funnily enough, I used that probabilistic Prime test for a Project Euler exercise, wondering why I wasn't able to get the correct results. It turns out that this test detects probable primes (the book mentions that a little later and introduces the Miller-Rabin test that pseudoprimes cannot fool). On the one hand, it was cool to use an algorithm from a book directly. On the other hand, I was undoubtedly a bit annoyed by that story.

The book moves on to discuss the runtime of some of the algorithms discussed to this point. It introduces some other mathematical concepts, such as calculating roots via the fixed-point method, Euler expansions, and the Newton method for finding minima/maxima. It was cool to see how the fixed-point method can be used to implement the Newton method if you plug the derivate of a function into it. I did my project presentation for math in high school about the Newton method. So this brought up cool memories. I wish I still had that presentation.

Finally, SICP introduces the evaluation model for stateless functions and concludes with some exercises that require second-order procedures: procedures that take other procedures as arguments.

Chapter 2

Chapter 2 starts by introducing compound data structures to represent pairs and rational numbers. Abstraction barriers allow implementing procedures on data types independent of the underlying representation. For example, we could reduce a rational-number to its lowest denominator at creation or display time. The book introduces interval arithmetic to deepen the understanding of data abstractions.

Next, the book shows how to create more complex data structures such as lists and trees from cons. Higher-order procedures such as map and fold operate on these structures, for example, to update each element or to aggregate data.

The book then expands on the idea of higher-order procedures by introducing a picture language as shown in the following image. We can manipulate a painter with different transformations to create more complex images. The book does not present a way to paint to the screen, so I have implemented the painter to create a Python script that can then draw the images via the PIL library.

The next section introduces symbolic data that we utilize to implement a system for symbolic differentiation. One of my favorite things about the book is that it references concepts from other disciplines, such as calculus. I am happy that my high school knowledge of these topics is still present enough for me to work through the exercises.

Next, we explore sets and different ways to present them. The section finishes with the implementation of Huffman Encoding trees.

The rest of this chapter shows how to implement an algebra system utilizing a data-directed programming style. We create packages for different types of numbers, such as rational, complex, and imaginary numbers. We install methods for all basic algebraic operations, and the functions dispatch the correct procedure depending on the data type.

Over the next sections and many exercises, we expand the system to automatically simplify the numbers by creating a hierarchy of data types. Eventually, we extend the system to support polynomials and even rational polynomials by extending our previous rational numbers implementation.

I found these exercises challenging but incredibly rewarding. The algebra system was the point where I gave up when I worked through the book initially, so I felt a sense of accomplishment when I finished it on my second attempt.

Chapter 3

Chapter 3 introduces statefulness into the computation model. I want to point out how far we have come without explaining variables. It is one of the reasons why I enjoyed the book so much. Even though I was already familiar with functional programming, the book taught me how to think purely, leading to more solid code.

The initial section shows how we can use message dispatching to maintain the balance of a bank account. The general idea is to define variables within the scope of a procedure. Any procedure defined in the same context has access to these variables. By returning a procedure, we can thus manage the variables, such as the bank account balances, after leaving the original context.

For this approach, the interpreter needs to know how to resolve variables in a specific context. The book introduces the environment model of computation to handle variables within different contexts. As we would expect from an imperative programming language, there are nested frames, and the interpreter looks up variables starting from the current frame going outwards.

Based on our new understanding of statefulness, we learn about mutable data structures such as queues and tables. By implementing some of these data structures in Scheme, I understood and appreciated them more deeply.

The chapter about mutable data structures finishes with a simulator for digital circuits and a constraint solver. That is probably the only part in the book where I had wished that there were more exercises. There are some exercises for both tools, but they don't go too deep.

Of course, once we have introduced statefulness, that opens the possibility for race conditions when multiple parts of the program access variables concurrently. The book explains nicely how transfers from different bank accounts yield different results depending on the execution order. We can use resources to manage concurrent accesses, but that can lead to additional problems like deadlocks. The book explains all of that beautifully within a single section.

Lastly, we learn about the stream model for computation. Streams are delayed lists which means that the interpreter computes the cdr-arguments on demand. This paradigm allows us to reimplement a couple of procedures arguably more elegantly. Just take a look at the beautiful implementation of the Fibonacci sequence.

(define fibs
  (cons-stream 0
    (cons-stream 1
      (add-streams (stream-cdr fibs)
                   fibs))))

The chapter ends by explaining how the stream paradigm can resolve the concurrency problem, at least partially. We can use streams to represent events that happen over time. Nevertheless, if we get streams from multiple sources, it's still unclear how to merge them deterministically. The final sentiment has changed much in the last thirty years. Concurrency is still a challenge, for example, in embedded development.

Chapter 4

Chapter 4 introduces the concept of a metacircular evaluator. That is a Scheme program that interprets Scheme programs. This approach enables us to use the native interpreter while gradually replacing procedures with our implementations.

In particular, we can read the Scheme code with the read procedure without worrying about lexing or parsing. Calling read on a Scheme program returns a data representation of the program. In other words, we can think of a program as an abstraction for a machine.

Throughout the first section, we finish a first version of the metacircular evaluator, including implementing the environment model via frames. We then optimize the evaluator by adding an analyzer layer that optimizes a program for faster interpretation by avoiding repetitive interpretation of static data.

In the next section, we change the metacircular evaluator to lazy evaluation. In one of the book's first exercises, we learned that Scheme is an applicative-order language, meaning that Scheme evaluates all arguments before a procedure call. In contrast, lazy evaluation delays the evaluation until a primitive procedure requires the actual value. By making this change, we turn Scheme into a normal-order language.

Moving forward, we learn about even more exciting models for computation. In the next section, we implement a non-deterministic version of Scheme via the amb operator. This operator allows us to assign multiple values to a variable. The amb evaluator then determines valid values based on constraints given in the program. In the most straightforward implementation, the amb evaluator searches over all possible ways. That means the programmer must add conditions to optimize the program.

Here is a simple example that shows how the amb evaluator works:

]=> (list (amb 1 2 3) (amb 'a 'b))
(1 a) (1 b) (2 a) (2 b) (3 a) (3 b)

In the following section, we implement an interpreter for logic-based programs. The book introduces a database of employees in a company, and we can then query that database based on specific constraints. For example, to see who Ben Bitdiddle supervises, we could use the following query.

(eval-query '(supervisor ?x (bitdiddle ben)))

I have found it fascinating to learn about these alternative models for computation. The chapter has helped me better understand database query languages like SQL and the Prolog programming language that I dabbled with a couple of years ago. It's fascinating to see how we can add entirely different programming concepts to Scheme.

Chapter 5

Chapter 5 combines the previous chapter's concepts, ultimately implementing a Scheme interpreter running on physical hardware.

The first section introduces the concept of register machines. Register machines are an abstraction of physical machines that control the flow of data and can execute computations. For example, the following diagram shows a machine that computes factorials.

Based on the diagrams, we learn about an assembly-like language that can represent register-machines. For example, the following listing shows the same machine as on the previous graph in assembly form.

'(controller
   (assign product (const 1))
   (assign counter (const 1))
   test-counter
     (test (op >) (reg counter) (reg n))
     (branch (label factorial-done))
     (assign product (op *) (reg product) (reg counter))
     (assign counter (op +) (reg counter) (const 1))
     (goto (label test-counter))

In the following sections, we implement a simulator that can execute register-machine programs and use it to run a Scheme interpreter written in the register-machine language. We call this the Explicit-Control-Evaluator.

Finally, we implement a Scheme compiler that compiles into the register-machine assembly language. Ultimately, we use the compiler to translate the metacircular evaluator from chapter 4. We then use the register machine simulator to run the evaluator. Making that work was indeed a fantastic moment. I cannot explain it well, but seeing how everything comes together gave me a great sense of accomplishment.

The last two exercises in the books are programming projects in their own right. First, I implement a crude Scheme interpreter in Rust, and then I modified the compiler to generate C code. I have implemented the required runtime support, and it works, at least for simple programs like computing factorials.

Resources

• SICP book
• SICP solutions
• SICP code from book
• Scheme specification
• Scheme parser spec