💾 Archived View for gemini.lostleonardo.xyz › sicp › lecture-1A.gmi captured on 2021-12-17 at 13:26:06. Gemini links have been rewritten to link to archived content

View Raw

More Information

⬅️ Previous capture (2021-11-30)

-=-=-=-=-=-=-

Lecture 1A - Introduction to Lisp

Computer science is a terrible name for this business. First of all, it is not a science. It might be engineering, it might be art; it actually has a lot in common with magic.

It is also not very much about computers, in the same sense that physics is not really about particle accelerators, and biology is not really about microscopes, and geometry is not really about surveying instruments.

When a field is just getting started, it is very easy to confuse the essense of what you are doing with the tools that you use.

The important idea at the centre of computer science is the notion of formalising knowledge and intuitions about process - how to do things.

Declarative knowledge: "what is true".

Imperative knowledge: "how to".

What is a process in general?

You can think of a process as like a magical spirit that lives inside the computer and does something.

The thing that directs a process is a pattern of rules called a procedure. Procedures are the spells that control the magical spirits called processes.

"Every sorcerer needs a magical language... We are going to conjour our spirits in a magical language called Lisp. Lisp is a language designed for casting the spells that are procedures that direct the processes".

Techniques for controlling complexity

The real problems arise when we try to build very large systems. To that end, computer science is really about techniques for controlling the complexity of large systems.

A physical system is made out of real parts which have to address the constraints of physics, noise and approximation. Computer science deals with idealised components; we can know as much as we want to know about the program and data pieces we have to fit together.

The constraints imposed on building large software systems are the limitations of our own minds. In that sense, computer science is like an abstract form of engineering; a kind of engineering where you ignore the constraints imposed by reality.

Techniques for controlling complexity

Black-box abstraction

A general strategy that supresses knowledge about internal implementation details.

"Procedures are going to be our way of talking about imperative knowledge".

Primitive objects

Means of combination

Means of abstraction

Capturing common patterns

Conventional interfaces

For example, linear combination, expressed as a general idea.

Generic operations such as plus (+) work with lots of different kinds of data.

Conventional interfaces

Making new languages (metalinguistic abstraction)

Supressing some kinds of detail and emphasising other kinds of detail.

Metalinguistic abstraction

A general framework for thinking about languages

Primitive data and primitive procedures in Lisp

Primitive data

Primitive procedures

Means of combination

A combination consists of applying an operator to some operands.

Lisp uses prefix notation, which means that the operator is written to the left of the operands, and parentheses denote the start point and the end point of a combination.

Combinations are trees, and parentheses are the means of writing a two-dimensional structure as a linear character string.

Means of abstraction

This is the notation for defining a procedure. Procedures are Lisp's means of abstraction; a means of naming a general idea.

(DEFINE (square x) (* x x)) is syntactic sugar for (DEFINE square (lambda (x) (* x x))), naming a procedure.

The key thing is that having defined square, you can then use it as if it were primitive; there is no need to make arbitrary distinctions between procedures that are built-in (primitive) and procedures that are user defined.

Things that are compound have an abstraction wrapper wrapped around them.

Applying a procedure to an argument

You can also introspect on the procedure

Special forms

Case analysis (conditionals)

(DEFINE (abs x)
        (COND ((< x 0) (- x))
                ((= x 0) 0)
                ((> x 0) x)))
(DEFINE (abs x)
        (IF (< x 0)
                (- x)
                x))

A conditional clause is comprised of a predicate and an option (the thing to do in the case that the predicate evaluates to true).

Recursive definitions

A recursive definition is what allows you to perform infinite computations that continue until something is true, without the need for any constructs other than the ability to call a procedure.

Block structure

A means of packaging internal procedure definitions inside other procedure definitions.

Summary

Computer programs express imperative ('how to') knowledge.

Lisp

|                      | Procedures   | Data    |
|----------------------+--------------+---------|
| Primitive elements   | +, -, /, *   | 10, 5.5 |
| Means of combination | (), cond, if |         |
| Means of abstraction | define       |         |

Next

..