Structure and Interpretation of Computer Program (aka SICP) - 01 Building abstractions with Procedures

1.1 The elements of programming

1.1.1 primitives expressions -> means of combination -> means of abstractions

465

(+ 1 2)
3

Expressions such as these, formed by delimiting a list of expressions within parentheses in order to denote procudure application, are called combinations. The leftmost element in the list is called the operator, and the remaining elements are called operands.

Placing the operator to the left of the operands is called prefix notation which has two advantages:

It’s flexible, because it can accommodate precedures that may take an arbitrary number of arguments.
A second advantage is that it extends in a straightforward way to allow combinations to be nested which means to have combinations whose elements are themselves combinations.

Following expressions demonstrate the second advantage of prefix notation:

(+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6))

This expression is confused for human, but it’s actually a very simple expression for lisp interpretor. There is a easy way for humen to understand the lisp expression.

(+ (* 3
        (+ (* 2 4)
        (+ 3 5)))
    (+ (- 10 7)
        6))

This is called pretty-printing.

1.1.2 Naming and the Environment

We can use define keyword to create association between a name and a value.

(define x 3)
(define pi 3.14)
(define radius 10)
(define circumference (* 2 pi radius))

The define keyword is our first means of abstraction. It allows us to refer to the results of computed operations.

1.1.3 Evaluating Combinations

To evaluating combinations, we need to do the following:

Evaluate the subexpressions of combination.
Apply the procedure that is the value of the leftmost subexpression to the arguments that are the value of the other subexpressions.

It’s a recursive process.

(* (+ 2 (* 4 6))
    (+ 3 5 7))

tree accumulation

1.1.4 Compound Procedures

Procedure definitions:

How to express one idea of “Squaring”?

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

Evaluating above expression creates a compound procedure and associates it with the name of square

The general form of a procdure definition is

(define (<name> <formal parameters>) <body>)

1.1.5 The substitution model for procedure application

But how the procedure work?

(square (square 5))

Indeedly, (square (square 5)) -> (square (* 5 5)) -> (square 25) -> (* 25 25) -> 625.

What we have simulated is called substitution model.