From January to March 2021, I studied SICP, famous in the computer science field, through a group study. We studied together up to Chapter 1, and afterwards I personally studied by solving exercises in Chapters 2 and 3.

Before starting my study, I indirectly learned about SICP through the following introductions and videos:

After studying the book up to Chapter 3, I found that the content up to Chapters 1-2 covers topics worth contemplating while developing programs, dealing with abstraction, reuse, and other software engineering concepts.

When I first opened the book, I felt very burdened by its hefty thickness. I thought it was a difficult book for 4th-year undergraduate level that involves building a language interpreter directly. However, as I read it myself, I felt that even without interest in programming language theory, the philosophy about software engineering contained in the book is so practical that I could recommend it to 1st and 2nd-year undergraduates who have developed programs.

For that reason, I decided to share on my blog by examining some topics from the content up to Chapter 2.

Bottom-Up Pedagogy

I think it was an opportunity to learn more about simple mathematical concepts and how math and programming are integrated. This book explains what functions are, what procedures are, and how to define data structures through mathematical content. Also, because mathematics was incorporated into programming, there were several benefits. (omitted) Programming functionally from the start allowed me to feel that I was doing clearer programming. — Reading Books — SICP by Las | Medium

According to Las’s book review, they mentioned learning in detail how mathematical concepts and programming are integrated at the foundational stage. I was also impressed by how the book discusses mathematical fundamentals related to programming early on.

While most basic programming curricula disappointingly skip mathematical concepts used in programming and practice with procedural flow, SICP had the characteristic of mathematically and clearly introducing basic programming concepts such as arithmetic operations, procedures, and recursion through functional programming.

Finding Square Roots by Approximation aka. Newton’s Method

Do you know how to find the actual value of a square root? When I first saw this question in the book, I mistakenly thought it was an operation that could be calculated immediately like arithmetic operations. But it turned out to be a value that isn’t obtained so easily.

The book explains that you can find an approximate value close to the square root by arbitrarily determining a value y close to the square root of x, and repeatedly finding the average of y and x/y. For example, the square root of 2 is found as follows:

Guess y   Quotient      Average

1         (2/1)  = 2    ((2 + 1)/2)  = 1.5

1.5       (2/1.5)       ((1.3333 + 1.5)/2)
            = 1.3333      = 1.4167

1.4167    (2/1.4167)    ((1.4167 + 1.4118)/2)
            = 1.4118      = 1.4142

1.4142    ...           ...

Source: 1.1.7 Example: Square Roots by Newton’s Method

I wanted to include the code, but since it’s Lisp code that few people know, I only included the concept.

Finding Square Roots Through Tangent Slope

This is a method that utilizes the slope of a tangent (aka. instantaneous rate of change) learned in high school calculus.

For details, please refer to Approximating Square Roots w/ Newton’s Method.

You can obtain a value close to the actual square root by finding an arbitrary approximate value x and then finding another approximate value through its tangent, narrowing the range.

Abstraction

Programmers should always look at the programs they write to find what to abstract from them, and strive to create higher-level means of expression from this.

The habit of striving to abstract several problem-solving methods to create general means of expression that can be reused for other problem-solving is truly important. This is why higher-order procedures, that is, procedures that use procedures as valuesdata, are important.

If you don’t design to limit what is affected by data representation to only a few program parts, you will have to spend a lot of time and pay a price when writing large programs.

“Abstraction” in the book is an important concept in software development. High-level abstraction is a practical concept because code with low dependency has less impact elsewhere.1 In SICP, it’s a concept emphasized importantly throughout Chapters 1 and 2.

When writing a program to find square roots, I quoted some guidelines on abstraction that impressed me.

First-Class Functions and Functional Programming

SICP introduces the functional programming language concept of “first-class functions” in the last sub-chapter of the first chapter and introduces four characteristics. The preface to the first chapter was also full of praise for functional programming, so I felt the book’s authors are serious about functional programming.

  • Functions can be named as variables
  • Functions can be passed as parameters
  • Functions can be returned as return values
  • Functions can be put into data structures. 🤔…?

Creating Tuples Using Closures

In the definition of first-class functions, it says you “can put them into data structures,” and I was initially curious about how you can put functions into data structures. One exercise in Chapter 2 introduces how this is possible.

To accommodate those who can’t read Lisp code, I prepared the exercise in JavaScript using closures.

function cons(x, y) {
  return function (m) {
    return m(x, y);
  };
}

The cons function is a higher-order function for expressing a pair of tuples as a function. The goal is to return a function called m that makes that function return either x or y. First, the given code is as follows:

const pair = cons(2, 1);

const car = (x, y) => {}; // How should we fill the function body...?
const cdr = (x, y) => {}; // How should we fill the function body...?

console.assert(car(pair) === 2);
console.assert(cdr(pair) === 1);

The answer is to return only one of the two parameters x and y. It’s said that data structures can be expressed with functions alone in this way.

const car = (x, y) => x;
const cdr = (x, y) => y;

Source: What Is Meant by Data? (Exercise 2.4)

Closing

While reading SICP, I was able to learn about basic guidelines for software development as I read about abstraction and structural improvement until they became familiar. ⬇️ I felt it was fine to recommend it at the level of 1st and 2nd-year undergraduates who have developed programs, but… it seemed difficult for college freshmen who are not MIT students to read immediately.

There’s a new book written by the SICP authors called “Software Design for Flexibility”, and I’m waiting to read it once a Korean translation comes out. 😋

References

  1. I think such abstraction is related to Dependency Inversion, and further to Dependency Injection. This is because it depends on abstract interfaces rather than directly depending on concrete implementations. This is an opinion I came up with by referring to Taehee Kim’s article “Dependency Inversion and Dependency Injection - How to Control Dependencies in Frontend (Korean)”. ↩︎