💾 Archived View for gemini.lostleonardo.xyz › sicp › lecture-4A.gmi captured on 2021-12-04 at 18:04:22. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2021-11-30)
-=-=-=-=-=-=-
"Yesterday we learned a bit about symbolic manipulation".
"What we did is translate these rules into the language of the computer"
"... a dispatch on a type..."
A pattern is something that matches and a skeleton is something that you substitute into in order to produce a new expression. A pattern is an expression source and a skeleton is an expression target.
This emphasises the idea that we had last time that we are trying to make a solution to a class of problems rather than a particular one.
To encapsulate the control structures separate from the rules themselves.
Pattern match
- foo -> matches exactly foo
- (f a b) -> matches any list whose first element is f, whose second element is a, whose third element is b
- (? x) -> matches anything, call it x
- (?c x) -> matches a constant, call it x
- (?v x) -> matches a variable, call it x
Skeletons
- foo -> instantiates to itself
- (f a b) -> instantiates to a 3 list which are the results of instantiating each of f, a, and b
- (: x) -> instantiate to the value of x in the pattern matched
"It's so much fun to make up a language, and one of the most powerful design things you ever do is making up a language to solve problems like this"
Each rule has a pattern and a skeleton - that's the data.
The programs itself is comprised of a matcher and an instantiator. The matcher passes a dictionary (of meanings) to the instantiator which itself outputs expressions. Expressions are then passed into the matcher while the rules are passed into the instantiator until it no longer changes.
"In any programming language you invent, if it is significantly powerful to do anything, you run the risk of writing programs that go into infinite loops".
Q: "Some language designers believe that this feature should become a part of the basis language - what are your thoughts on that?"
A: "My feeling about that is that I would like to teach you how to do it so that you don't depend on some language designer. You make it yourself, you can roll your own".
The matcher matchers expressions against patterns.
The matcher takes as its input a pattern, an expression and a dictionary and executes a case analysis which bottoms out in a general case (which is the piece that recurs). The sub-expressions of the expressions are matched against the sub-expressions of the pattern.
Pattern
(+ (* (?x) (?y)) (?y))
Expression
(+ (* 3 x)) x)
Then you walk both those trees and output a dictionary.
What comes out of match is either some mapping - between pattern variables and values - or the symbol 'failed. That is constructed by extend-dict. What we're doing there is making up the dictionary for later use.
Every rule is going to look at every node and the rule either will or won't match.
The simplifier is a program that takes a set of rules and produces a program that will simplify expressions based on those rules.
"Although that was a complicated program, every complicated program is made out of a lot of simple pieces. Now, the pattern of recursions here is very complicated, and one of the most important things is not to think about them. If you try to think about the actual pattern by which this does something, you're going to get very confused. I would. This is not a matter of you can do this with practice. These patterns are hard. But you don't have to think about it."
"The key to very good programming and very good design is to know what not to think about".
"The fact is I don't have to think about it because I have specifications in my mind for what 'simplfy-exp' does, I don't have to know how it does it".
"... if simply-exp is assumed, by wishful thinking, to produce a simplified result, then I don't have to think about it anymore. I've used it, I've used it in a reasonable way, I will get a reasonable answer, and you have to learn to program that way - with abandon!"