Computer science, like geometry (geo- earth, -metron measurement), has an inaccurate name. Computer science is neither a science, nor particularly about computers. Geometry is the formalisation of notions of space and time. Computer science is the formalisation of intuitions about process.

Declarative knowledge: what is a square root?
Imperative knowledge: how do we find a square root?

We will use LISP to write procedures. Procedures invoke processes. Processes are the building blocks of imperative knowledge.

Computer science is really about techniques for controlling complexity, moreso than any other discipline. In computer science we deal with idealised components. Little difference exists between what we can build and what we can imagine. We are limited by our own minds; engineers are not.

The programmer, like the poet, works only slightly removed from pure thought-stuff. He builds his castles in the air, from air, creating by exertion of the imagination.

We will learn three techniques for controlling complexity: black-box abstraction, conventional interfaces, meta-linguistic abstraction.

For any new language, first determine the primitive elements, means of combination, and means of abstraction.

LISP uses prefix notation. The following

(+ 3 17.4 5)

is a combination of an operator +, with operands 3, 17.4 and 5.

To define:

(define A (* 5 5))
(define (square x) (* x x))
(define square (labmda (x) (* x x)))

To use conditionals:

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

The following square root procedure contains other procedures (this is called block structure). try has a recursive definition.

(define (square x) (* x x))
(define (average x y) (/ (+ x y) 2))
(define (sqrt x)
  (define (improve guess)
    (average guess (/ x guess)))
  (define (good-enough? guess)
    (< (abs (- (square guess) x))
       .001))
  (define (try guess)
    (if (good-enough? guess)
        guess
        (try (improve guess))))
  (try 1))

So far we have covered:

Now go make yourself a sandwich.