SICP Section 2.2

Jun 14, 2017 15:43 · 543 words · 3 minutes read sicp scheme

This part of the book deals with data and operations you can perform on it. At first, the authors talk about the closure property of lists. The closure property in this regard is different from how the term ‘closure’ is used in general programmer talk. If you are from a different programming paradigm outside SICP, closures can be thought of as functions that can be stored as a variable, and which have the special ability to access other variables local to the scope it was created in. You can read more here. However, in the context of SICP, an operation for combining data objects satisfies the closure property if the results of combining things with that operation can themselves be combined using the same operation. Such an operation is the cons primitive procedure. The results of cons can be themselves combined using cons. Here’s a quick example:

(define x (cons (cons 1 2) (cons 3 4)))

The closure property is quite useful because it enables us to create hierarchical data structures(data structures made up of parts, which are themselves made up of parts). Alot of the exercises in this book was focused on lists and pairs. I found these operations quite interesting. An example would be the map function, which operates on each element of the list using a given function. Other useful functions were the accumulate and reduce functions.

Another really cool design principle discussed was conventional interfaces. This involves expressing programs as sequence operations. For example, if we wanted to generate a list of even fibonacci numbers, we would:

;; 1. Enumerate the integers from 0 to n
;; 2. Generate the Fib number for each of these integers
;; 3. Filter the resulting sequence to keep only the even elements
;; 4. Accumulate the results into a list

(define (even-fibs n)
    (filter even?
        (map fib
            (enumerate-interval 0 n)))))
;; Example
(even-fibs 8)
;; Result
(0 2 8)

In the above program, the sequence methods are: accumulate, filter, map and enumerate-interval. Designing programs as sequence operations makes the program more modular. Making modular programs makes it easier when working with complex systems because each module is independent of other modules. This section has implemented sequences as lists which have served as conventional interfaces that permit combination of processing modules.

The hugest take away(at least for me) is the concept of stratified design- the notion that a complex system should be structured as a sequence of levels that are described using a sequence of languages. The base level consists of primitives(at that level). Each level is constructed by combining parts that are considered primitive at that level, and the parts constructed at each level are used as primitives at the next level.

This approach to stratified design can best be demonstrated by the Nand2Tetris project, a project where a fully working computer is built from first principles i.e. Nand gates. At the basic level, we have nand gates which are combined to form and, or and other basic gates. This gates are in turn combined to form more complex gates like the multiplexor and demultiplexor. Eventually, the whole computer is constructed. You can read more about it here.

You can find all my source code(of this section) here :)