•

Structure and Interpretation of Computer Programs - Harold Abelson, Gerald Sussman, Julie Sussman

Table of Contents

Not much in a Zettelkasten is meant for publishing. I publish a small subset of my atomic notes, and none of my reference notes which are taken directly from a specific source. I wanted to make an exception for this note as I am starting with the intent to make it professional and well structured. Here are some of my goals:

Building Abstractions with Procedures

Processes are an abstraction provided by the operating system. They act on data, and are directed by a pattern of rules called a program.

Programs are required to be expressed in some form of language. In this book the language used is a dialect of Lisp known as Scheme. Lisp is a functional programming language developed at MIT.

The Elements of Programming

Every powerful language has three mechanisms for organizing ideas about processes:

Expressions

Expressions are the smallest chunk of a program that can be evaluated. In Lisp expressions can be as simple as 5 or 21.

Combinations are an application of a procedure over a list of expressions. The would look something like this:

(+ 137 349)

Lisp follows prefix notation, instead of infix notation that would typically be used with an operator like +.

Naming and the Environment

In Scheme, we name things with define. This is the most basic means of abstraction, allowing the use of simple names to refer to more complex combinations. The environment is what keeps track of these names and their values.

Evaluating Combinations

Evaluation of combinations is recursive in nature because in order to evaluate a top level expression, all nested expressions must be evaluated first. Combinations can easily be represented as a treelike structure, where values percolate upwards in a process known as “tree accumulation”.

Compound Procedures

Procedure definition are a much more powerful abstraction, where a compound operation can be given a name. This is the equivalent of creating a function.

(define (square x) (* x x))

(define (sum-of-squares x y )
  (+ (square x) (square y)))

The Substitution Model for Procedure Application

The substitution model is similar to solving expressions in lambda calculus where you must first apply to bound variables. In both the substitution model and lambda calculus, we evaluate expressions by replacing formal parameters (bound variables) with their corresponding argument values.

The substitution model provides an initial mental framework for understanding procedure application, though it will later be refined into the environment model which more accurately reflects how interpreters manage variable bindings. If the substitution model were to actually be used, interpreters would be more like the preprocessor from C and C++ where pure textual substitution is taking place.

Conditional Expressions and Predicates

Conditional expressions allow procedures to perform different computations based on testing conditions. The primary construct is cond (conditional), which evaluates predicates in sequence until one is true. Basic syntax:

(cond (<p1> <e1>)
      (<p2> <e2>)
      ...
      (else <en>))

Each clause consists of a predicate (a test expression) followed by a consequent expression. The interpreter evaluates predicates in order; when it finds the first true predicate, it evaluates and returns the corresponding consequent expression. The else clause is optional and acts as a catch-all. For simple two-way conditionals, use if:

(if <predicate> <consequent> <alternative>)

Predicates are expressions that evaluate to true or false. Common predicates include:

Comparison operators: <, >, = Logical operators: and, or, not

Example:

(define (abs x)
  (cond ((> x 0) x)
        ((= x 0) 0)
        ((< x 0) (- x))))
;; Equivalent using if:
(define (abs x)
  (if (< x 0) (- x) x))

Exercise 1.3 Define a procedure that takes three numbers as arguments and returns the sum of squares of the two larger numbers

(define (sum-of-two-larger x y z)
  (sum-of-squares (max x y) (max y z)))

Example: Square Roots by Newton’s Method

Mathematics typically deals with the declarative side of things, the description, while computer science is more concerned with the imperative, or “how to”.

(define (average x y)
  (/ (+ x y) 2))

(define (improve guess x)
  (average guess (/ x guess)))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

(define (sqrt x)
  (sqrt-iter 1.0 x))

Building Abstractions with Data

Modularity, Objects, and State

Metalinguistic Abstraction

Computing with Register Machines