SICP Lecture 4a

Stopped at 16:20

Important part @ 19:10

From a pattern, produce a skeleton using a rule.

> A pattern is something that matches, and a skeleton is something you substitute into in order to get a new expression (03:03)

> A pattern is matched against the expression and the result of the application of the rule is to produce a new expression (target) by instantiation of the skeleton

> Build a language and the means of interpreting that language. A means of executing that language. That language allows us to directly express these rules.

> Bring the computer to the level of us by writing a way for the computer to understand rules of this sort

> We are trying to make a solution to a class of problems rather than to a particular one

> These things that begin with question marks are pattern variables (for matching)

> Colons stand for substitution objects 

#### Pattern Match
 
* 'foo' matches 'foo'
* (f a b) matches any list whose first element is f, whose second element is a, and whose third element is b
* (? x) matches anything, call it x
* (?c x) matches only constants, call it x
* (?v x) match variables, call it x

#### Skeletons

* foo instantiates to itself
* (f a b) instantiates to a 3-list; results of instantiating each of the elements
* (: x) instantiates to the value of x in the pattern matched

#### Equals for equals

> all sub-expressions of the expression has to be looked at

> all of the rules must be tried

> if any rule matches, the instantiation occurs

* re-check until you can no longer simplify further (until the thing no longer changes)

#### An organic process

 * enzymes attach to your expression, change it, and then they go away
 * key-and-lock phenomenon
 * keep changing until no longer possible

Matcher and instantiator are separate pieces (21:54)

> In any programming language you build may produce an infinite loop

matching and instantiation

the control structure in which the rules are applied

you have to examine every sub-expression (some sort of tree-walk)

for every node that I get to, I want to apply all of the rules...every rule is going to look at every node (rotating the rules around)

either a rule will or will not match...if the rule does match, then I'm going to replace that node in the expression by an alternate expression (create a new expression as a result of substituting)

instantiate relative to the dictionary (58:19)