💾 Archived View for gemini.lostleonardo.xyz › sicp › lecture-1A.gmi captured on 2022-04-29 at 11:24:26. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2021-11-30)
-=-=-=-=-=-=-
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".
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".
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
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
For example, linear combination, expressed as a general idea.
Generic operations such as plus (+) work with lots of different kinds of data.
Conventional interfaces
Supressing some kinds of detail and emphasising other kinds of detail.
Metalinguistic abstraction
Primitive data
Primitive procedures
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.
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.
(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).
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.
A means of packaging internal procedure definitions inside other procedure definitions.
Computer programs express imperative ('how to') knowledge.
| | Procedures | Data | |----------------------+--------------+---------| | Primitive elements | +, -, /, * | 10, 5.5 | | Means of combination | (), cond, if | | | Means of abstraction | define | |