SICP series - Introduction

14 November 2019
Tags: fundamentals SICP

With this post I am going to start a series of posts concerning what I believe (and not only me) to be one of the most valuable resources on programming and more in general computer science: the mythical Structure and Interpretation of Computer Programs. The full content of the book is available online at the link [1]; I also warmly advise to have a look at the MIT courseware which offers valuable resources which aid the understanding of the book; I recommend in particular the videos (which can be found here [2]) as both Sussman and Abelson, the authors of the book, are phenomenal teachers. The lecture notes are also useful and can be found here [3].

My purpose with this series of posts is to illustrate the major topics of the book, but I will not cover all of them though; in particular, I will leave out the whole Chapter 5 which dives deeply low-level.

Small preamble before starting: I have to clarify that I did not read the book fully nor did I complete the exercises (I know the hacker community will hate me for this and I will be branded as poser). To actually get the most out of the book, one should complete the notoriously challenging exercises, which will your understanding to the next level. It is however particularly time consuming and requires a hell of a determination, so be prepared.

What is it about

So, the reason why this book is considered an essential reading is because it does the amazing job of compacting an astonishing number of fundamental topics related to programming, software development and language design. Historically, this book used to be taught to freshmen of MIT, so to people with likely no prior experience in programming and computer science. I can imagine that a student successfully completing the exam would be well equipped for any further topic (I would personally hire him on the spot already as he knows way more than many practicioners in the industry). I believe nonetheless that if someone is experienced this book is equally valuable, as it allows the reader to go through the concepts he may have been exposed to by presenting them in a logical and coherent framework. This book may shed a new light on concepts which the reader may have not been reasoning about so much and overall will bring his understanding to the next level. Besides, the reader will finally have the opportunity to get acquainted if not even becoming well-versed with the very cool Scheme, one dialect of the revered and feared Lisp language. I affirm that fundamental concepts should be very well founded not only for the academic, but in particular for the practicioner, as he will build software which will have a reach and impact to the world and its people.

Contents

in this paragraph I will list the main concepts which the book covers to provide an overview of the breadth of topics it touches:

  • Abstraction through procedures

  • Imperative vs declarative

  • Functional programming (lambda function, pure functions, higher-order functions, …​)

  • Iterative vs recursive algorithms

  • Algorithm complexity

  • Abstraction on data focusing on the pair and list as fundamental building blocks of Lisp programs

  • Types

  • Abstract data type

  • Mutation of state

  • The Environment Model as a framework for evaluation

  • Fundamental data structures: tables, stack, queue, tree, graph

  • Object-oriented programming

  • Concurrency

  • Interpretation for building a language using Scheme

  • Interpretation for building Scheme using Scheme (metacircular evaluator)

  • Lazy evaluation and streams

  • Register machines and compilation (how the evaluation model is actually implemented in the hardware)

Key takeaways

The book is a gold mine of valuable teachings, but there are a few which I think stand out and should be remembered the most.

The fundamental building blocks constituting a language are the following: primitive elements, means of combination (syntax) and means of abstraction (semantics). Further than this, meta-linguistic abstractions provide the tools to create languages suited to any problem domain.

Procedural abstraction allows to capture patterns of computation which result in a modular system.

Data abstraction allows to decouple the implementation from the usage of the data structures suited to the problem. This also results in added modularity to the system.

In Lisp, it turns out that there is not a real boundary between procedure abstraction and data abstraction, as programs are but lists of expressions. One can view a program as a tree composed of expressions expressed in the form of lists. Anything can then be defined both in terms of the procedures which implement its behavior and the data structures which implement it. I will make an article to further flesh out on this.

Lisp is a language powerful enough that it allows the programmer to define a language using the language itself. Furthermore, it allows to define the Lisp language by using the language itself (this is referred as metacirular evaluator in the book and is perhaps the most crucial point). The concept is mind-bending as well as illuminating, and I will dedicate another post to elaborate more on this.