SICP - Notes from Lecture 1A

Structure and Interpretation of Computer Programs
Lecture 1 - Overview and Introduction to Lisp
Covers Text Section 1.1

You can download the video lecture or stream it on MIT's OpenCourseWare site. It's also available on YouTube.

This first lecture is presented by MIT's Professor Hal Abelson.

Part 1

Prof. Abelson opens the lecture with the following “definition”

Computer Science – It's not really a science, and not about computers.

He supports the first half of this definition with the idea that computer science might be engineering or art, but that it is more akin to magic than science. A process can be thought of as like a magical spirit that lives in the computer. A pattern of rules called a procedure is like a magical spell, and the language that these spells are written in is Lisp.

These are the only references in this lecture to “computer science as magic.” Since a wizard graces the cover of the course text and the introductory slides, I hope the idea will be fleshed out as some point.

The second half of the definition, that computer science isn't about computers is supported with the following observations:

• Physics is not really about particle accelerators.
• Biology is not about microscopes and petri dishes.
• Geometry (originally from the Egyptian words for “Earth” and “measure”) is not about surveying instruments.

These are all observations that the different fields of science we study should not be confused with the tools that we use to study them. I think Edsger W. Dijkstra said it best when he said.

Computer Science is no more about computers than astronomy is about telescopes.

Prof. Abelson gives the following examples to illustrate the distinction between declarative knowledge and imperative knowledge (what he terms “how-to” knowledge).

Declarative – The square root of x is the y such that

y² = x and y ≥ 0

Imperative – In order to find the square root of x (using Heron of Alexandria's method of successive averaging):

• Make a guess, G.
• Improve the guess by averaging G and x/G.
• Keep improving the guess until the it is good enough.

Declarative knowledge is about stating and cataloguing facts. Imperative knowledge is about the methods and processes for finding knowledge (both declarative and imperative). Imperative knowledge is the meta-language for producing new knowledge of both types.

Techniques for controlling the complexity of large systems is what computer science is really about.

The three main techniques for controlling complexity in computer science, and the three main topics for discussion in the course are going to be

• Black Box Abstraction
• Conventional Interfaces
• Meta-Linguistic Abstraction (making new languages)

Black Box Abstraction – From an outside observer's point of view, the internals of how a procedure works should not be important. The example given in the lecture is the square root procedure from earlier. If we write a square root procedure, it should be modular in the sense that someone else can take it and use it as one step in their own procedures, and not need to worry about how it works.

Another reason to use Black Box Abstraction is that your imperative knowledge might be expressed in terms of a more general form of some other piece of imperative knowledge. The example given is a strategy for finding fixed points. Given a general procedure for finding fixed points, you can use it to find square roots by passing it a function as its data.

Black Box Abstraction

• Primitive Objects
• Primitive Procedures
• Primitive Data

Means of Combination

• Procedure composition
• Construction of compound data

Means of Abstraction

• Procedure Definition
• Simple data abstraction

Capturing Common Patterns

• Higher-order procedures
• Data as procedures

A programming language has primitive data and procedures as its basic building blocks. A language needs a means for combining these data and procedures to form more complex data and procedures. A language needs a means for abstracting data and procedures so they can be used as components in more complex procedures. Lisp has a means for defining common patterns in terms of procedures and data. Higher-order procedures are those whose inputs and outputs are themselves procedures.

Conventional Interfaces – agreed-upon ways of plugging things together.

• Generic Operations
• Large-scale structure and modularity
• Object-oriented programming
• Operations on aggregates

Meta-linguistic Abstraction

• Talks about how you construct new languages.
• Looks at the process of interpretation and evaluation of code.

Part 2

In the first part of the lecture, Prof. Abelson revealed that, like chess, the rules of Lisp can be learned in a few minutes, but take years to master. The second part of the lecture talks about Lisp specifically, but more generally about the three main aspects of any programming language.

Primitive Elements – What does the language include in terms of data and procedures?
Means of Combination – How do you put the primitive elements together to build bigger things out of them?
Means of Abstraction – How do you use the combinations of primitive elements that you create as though they were primitive elements themselves?

Primitive Elements of Lisp: Numbers and mathematical operators make up the primitive elements in Lisp. Some examples are

3, 17.4, 5, +, -, *, and /

No real surprises here.

Means of Combination in Lisp:
A combination consists of applying an operator to some operands. Lisp uses prefix notation. The operator is written to the left of the operands. The parentheses make combinations unambiguous. A simple combination adding three numbers would be:

(+ 3 17.4 5)

The operands themselves can also be combinations instead of primitive data values.

(+ 3 (* 2 4) 7)

In the MIT Scheme interpreter environment, you hit C-x C-e (hold down the Control key while hitting x, then e) in order to evaluate an expression you've typed in. Evaluating the expression above gives a result of 18. This is the sum of 3, plus the product of 2 and 4, plus 7.

Prefix notation also makes it easy to show the structure of a program using a tree diagram. The following combination

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

is represented by the following tree diagram (from section 1.1.3 of the course text, Evaluating Combinations)


Note that the nodes of the tree (including the non-leaf nodes) are represented by the value that the expression for that node evaluates to. If you start at the leaf nodes, the evaluation for the entire tree "percolates up" to the root node. This form of evaluation is a process known as tree accumulation.

Means of Abstraction in Lisp: Lisp uses the define keyword to define both variables (abstract data) and to apply names to procedures.

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

You can then use the new square procedure just like any other operator in Lisp.

(square 10)

An alternative syntax for the definition of square above is:

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

Technically, the first syntax we looked at is the alternative, and this syntax is the more "correct" one. In Lisp, the lambda keyword is used to define a function. If you're giving a function a name, the alternative syntax we looked at first is a shorter way to do the same thing. Later on in the course we'll be looking at situations where we might want to create a function without explicitly giving it a name. We'll come back to the lambda operator then. For now, we'll use the short syntax for defining procedures.

The following function computes the average of x and y.

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

The average of x and y is computed by dividing the sum of x and y by 2.

Now that the procedures for square and average are defined, you can use them just as you would any primitive procedure in Lisp. This is because Lisp does not make arbitrary distinctions between primitives of the language and procedures defined by the user.

The last section of the second part of the lecture explains how to do Case Analysis (Conditionals) in Lisp.

Consider the following definition of the absolute value function:

|x| = -x for x < 0
0 for x = 0
x for x > 0

The absolute value function could be implemented in Lisp using a conditional expression as follows:

(define (abs x)
   (cond ((< x 0) -x))
         ((= x 0) 0)
         ((> x 0) x)))

Refer to section 1.1.6 of the text, Conditional Expressions and Predicates for a more complete discussion of conditionals, including the most common logical composition operators (and, or , and not) which are not covered in the lecture.


Part 3

We now know enough Lisp to implement any numerical procedure.

The main lecture concludes with an implementation of Heron of Alexandria's square root procedure seen earlier in the lecture.

To find an approximation to sqrt(x)

• make a guess G
• average G and x/G
• keep improving the guess until it's good enough
• use 1 as an initial guess
  

Each of these steps can be defined as a separate procedure, some of them in terms of other procedures we've seen already.

(define (try guess x)
   (if (good-enough? guess x)
       guess
       (try (improve guess x) x)))

(define (sqrt x) (try 1 x))

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

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

Notice that the try procedure is defined partially in terms of itself. The try procedure defined above checks an initial guess, then calls itself with a refined guess if the initial guess is not good enough. This new guess is then checked to see if it is good enough, and the guess is defined again, and try will be called again with the new refined guess. This will go on until the guess is refined to the point where it is close enough. This is called a recursive definition. The ability to make recursive definitions allows you to do infinite computations that go on until a condition is reached (or just go on forever, if you make a mistake).


Summary

The following table shows what we've learned so far, and what we have yet to learn.

	Procedures	Data
Primitive Elements	+ - * / =	23 1.738
Means of Combination	( ) cond if
Means of Abstraction	define

We've learned the primitive elements for both data and procedures. We've learned how to combine functions by composing expressions. We've also learned how to abstract procedures by defining our own. We have yet to learn methods for combining and abstracting data. The next couple of lectures will be talking about making a link between the procedures that we write and the processes that happen in the machine, and how to use Lisp to not only make small computations (like we've done so far) but also about “general conventional methods of doing things.”