💾 Archived View for gemini.lostleonardo.xyz › sicp › lecture-3A.gmi captured on 2022-04-29 at 11:24:34. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2021-11-30)
-=-=-=-=-=-=-
Methodology of data abstraction: Separating use from representation.
Lisp's method of data abstraction: Pairs, which fulfil the contract of cons, car and cdr.
Procedures can be objects and you can name them.
You can use cons to glue together arbitrary data to form pairs.
Closures allow us to start building up complexity, which does not trap us in pairs.
The things that we make can themselves be combined (using cons) to make more complicated things. This is what allows us to build complexity.
"When you look at means of combination, you should be asking whether things are closed under that means of combination".
When you are using pairs to glue things together, it helps to have conventions so that you are not constantly making an ad-hoc choice.
Lisp has a particular convention for representing a sequence of things as a chain of pairs - and that is called a list.
A list is a convention for representing a sequence.
[1|-] -> [2|-] -> [3|-] -> [4|/]
Shorthand notation for nested CONS operations (syntactic sugar)
(LIST 1 2 3 4)
(DEFINE 1-TO-4 (LIST 1 2 3 4))
One very common operation in Lisp is to write a procedure that applies an transformation to every element in a list.
A general pattern for recursively applying a procedure to a list - applying your procedure to the first element in the list then apply the same procedure to the rest of the list.
Map - apply a procedure to every item in a list and return a new list. Map builds that recursion into a general strategy.
(DEFINE (map p l)
(if (null? l)
nil
(cons (p (car l))
(map p (cdr l)))))
"The really important idea in APL is that you stop thinking about control structures and you start thinking about operations on aggregates".
ForEach - apply a procedure to every item in a list (transform the values of an existing list).
(DEFINE (for-each proc list)
(COND ((null? list) "done")
(else (proc (car list))
(for-each proc
(cdr list)))))
An example that summarises everything we have done up until now - list structure, issues of abstraction, and representation, and capturing commonality with higher-order procedures... and will introduce metalinguistic abstraction.
Language
Peter Henderson's language was for describing images that look like that and drawing them on a display screen.
"I hope by the end of this morning, if you are not already, you would be completely confused about what the difference between procedures and data are".
Primitives: There is only one primitive, called a picture. A picture is something that draws a figure scaled to fit a rectangle that you specify.
Means of combination and the operations: rotate, flip, beside, above
"How are we able to build up complexity so fast. The answer is the closure property... the world of pictures is closed under that means of combination, so whenever I have something I can turn right around and use that as an element in something else"
That's George's problem, that's a data representation problem... strong implication is the more interesting part is figuring out the behaviours.
"Once you have implemented the primitives in this way, the means of combination just fall out by implementing procedures".
"The real punchline comes when you look at the means of abstraction in this language. We have implemented the means of combination as procedures, so when we go to abstract in this language, everything Lisp provides us is automatically available to do things in this picture language. The technical term... not only is this language implemented in Lisp, the language is nicely embedded in Lisp".
"Lisp is a lousy language for doing any particular problem. What it is good for is figuring out the right language that you want and embedding that in Lisp. That is the real power of this type of design".
"What in the system is procedure and what is data? And the answer is, there really isn't any difference".
"At each level, the objects that are being talked about are the things that were erected at the previous level".
"Levels of language rather than a strict hierarchy".
"The design process is not so much implementing programs as implenting languages, and that is really the power of Lisp".