💾 Archived View for gemini.lostleonardo.xyz › sicp › lecture-2B.gmi captured on 2021-12-17 at 13:26:06. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2021-11-30)
-=-=-=-=-=-=-
Using higher-order procedures allows you to define general methods for doing things. Combining these abstractions yields a lot of expressive power.
The crucial idea is that when we are building things we divorce the task of building things from the task of implementing the parts. In large systems, there are abstraction barriers at lots of levels.
Means of combination for data - glue that allows you to put primitive data together to make more complicated compound data
Methodology for abstraction - useful for building up data in terms of simpler data
The key idea is that you are going to build up a system in layers and set up abstraction barriers that isolate the details at the lower layers from the things that are going on at the upper layers.
The system gives us individual numbers so we can have 5 and 3 but we need a way of saying that there is a thing that has both a 2 and 3 in it. Almost as if there are these clouds that have both a numerator and denominator in it. The strategy we are going to use to solve that problem is very powerful design strategy that we have used several times already, the strategy of wishful thinking. First, let's imagine that we have these clouds.
More specifically, let's imagine we have three procedures.
(make-rat n d) -> clouds (numer cloud) -> n (denom cloud) -> d
Assume that we have these things... and then work from there.
(DEFINE (+rat x y)
(make-rat
(+ (* numer x) (denom y)
(* numer y) (denom x)
(* (denom x) (denom y)))))
That is the analogue of doing rational number addition, and it is no problem at all, assuming that we have these clouds.
(DEFINE (*rat x y)
(make-rat
(* (number x) (number y)
(* (denom x) (denom y)))))
Apart that we haven't defined what these clouds are, that is all there is to it.
Constructor: A procedure for making a data object
Selector: A procedure for extracting data from a data object
In short, it is becuase it allows you to express more complex ideas.
Say you would like to express the idea of taking two rational numbers and multiplying that by the sum of two other rational numbers... in other words, you can easily create much more complicated expressions.
The whole name of this game is that we would like the programming language to express the ideas that we have in our head.
Data abstraction is a lot like procedure abstraction. If I have the instructions, why do I want to package them together and refer to them as a procedure? If I have the parts of the data, why do I want to package them together and refer to them as a sinlge object? The answer is the same in both cases: it magnifies or amplifies your expressive power.
In order to think about this problem more clearly, we broke them problem into two pieces, with a contract between them.
Now let's look at George's problem.
How can we package together a numerator and a denominator and actually make one of these clouds?
What we need is a kind of glue for data objects that allows us to put primitive elements together. Lisp provides such a glue in the form of list structure.
List structure is a way of gluing things together, and more precisely Lisp provides a way of constructing things called pairs. A pair is a thing that has a first part and a second part.
(CONS x y) -> returns a pair (constructor)
constructs a pair wholes first part is x and whose second part is y
(CAR p) -> returns a part (selector)
selects the first part of the pair p
(CDR p) -> returns a part (selector)
selects the second part of the pair p1
Box and pointer notation allows us to depict list structure
(CONS 1 2) -> returns a pair -> | 1 | 2 |
(DEFINE (make-rat n d) (CONS n d)) (DEFINE (numer x) (CAR x)) (DEFINE (denom x) (CDR x))
This system is built in terms of pairs (CONS, CAR and CDR) that are built into Lisp
The constructor and the selectors form a layer of abstraction between the program and the lower-level implementation details, seperating the use of data objects from the representation of data objects.
Data abstraction is the programming methodology of setting up data objects by postulating constructors and selectors to isolate use from representation. The constructor and selectors are the boundary.
What is the purpose of separating use from representation?
One of the most important principles is programming is the same as one of the most important principles in sorcery, that is, if you have the name of a spirit, you get control over it.
Isolating the idea of rational number as a conceptual entity and naming it with make-rat, numer and denom allows you to have alternative representations.
As system designers you are forced to make decisions about how to do things, and in general the best way to retain flexibility to not make up your mind about anything until you are forced to do it. You want to make progress but without being bound by the consequence of your decision. Data abstraction is the means by which this is achieved. This is a very powerful technique for deferring decison-making.
LET is a way of setting up a context in which you can bind variables.
Data abstraction is a way of controlling complexity in large systems.
The power of these techniques stems from how they can be used as building blocks for making more complicated things.
Building a layered system.
The means of combination in your system is such that we you put things together, you can then put those together using the same means of combination. So, you can make a pair of numbers, and then you can make a pair of pairs.
One of the tests of quality for a means of combination is: are the things that you make closed under that means of combination.
The way to manage complexity is by naming that spirit.
"We are explicit about them so that we have control over them".
"What this really depends on is that fact that I can make pairs of pairs. If I could only make pairs of numbers I would be stuck".
Any implementation of make-rat, numer and denom could form the basis of our rational number representation.
What we built was a rational number system that could sit on top of any representation. We have seperated representation from use.
However, there has to be some way of saying what is suitable as the basis for a rational number representation.
IF x = (make-rat n d)
THEN
(numer x) n
--------- = -
(denom x) d
This is George's contract. The three procedures have to fulfil this contract, but other than that it does not matter how George does it because it is below the layer of abstraction.
In the context of our system, a rational number is really three procedures that satisfy this axiom. Abstractly, that is what a rational number is really.
Axioms for pairs
"Let me do something that I think is really going to terrify you, and is really going to bring you face to face with the existential reality of this abstraction that we are talking about, and what I am going to talk about is what are pairs - really".
"To drive that home, let me really scare you, and show you what we might build pairs in terms of. And what you are going to see is that pairs can be built out of nothing at all; pure abstraction".
(DEFINE (CONS a b)
(LAMBDA (pick)
(COND ((= pick 1) a)
((= pick 2) b))))
(DEFINE (CAR x) (x 1))
(DEFINE (CDR x) (x 2))
"I claim that this is a representation of cons, car and cdr and notice that there is no data in it. It is built out of air, it is just procedure. There are no data objects at all in that representation".
"What I have demonstrated is that particularly weird implementation of cons, car and cdr satisfies the axioms so is a perfectly valid way of building all of the data objects we are going to see in Lisp. So they all, if you like, can be built on existential nothing... it really could work this way and it wouldn't make any difference to the system at all. In some sense, we don't need data at all to build these data abstractions because we can build everything out of procedures".
"Procedures are not just the act of doing something; procedures are conceptual entities - objects - and if I build CONS of 37 and 49 that is a particular procedure that sits there, . They are objects, and that is really where we are going. It is the difference between saying that a procedure is a real object that has existence".