SICP - Pattern matching and rule based substitution

I'll have to admit this lecture was harder to follow, though I think I did a better job following along than the mustache guy who spent five minutes beating the same question to death.



Notes I took on this lecture:

pattern matching and rule-based substitution

Questioning why we would translate the calculus rules into the language of the computer.
Is there a way to write the DERIV program that is more clear?

All the calculus rules have a left hand and right hand side.
Given a Pattern, we use a rule to produce a skeleton
Pattern is matched against an expression, application of rule produces a new expression that is an 
instantiation of a skeleton.

Build a language that will allow the computer to understand these rules. 

Deriv-rules is a page long lisp program, I'm not going to copy it verbatim.
Uses a ? to represent a pattern variable, which we use for matching
Uses a : to represent substitution objects.

Pattern matching
foo --- matches exactly foo
(f a b) --- match 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 a constant, call it x
(?v x) --- matches a variable, call it x

Skeletons for instantiation
foo  --- instantiates to itself
(f a b) --- instantiates to a 3.list which are the result of instantiating
       each of f, a , and b.
(: x) --- instantiate to the value of x as in the matched pattern

(DEFINE DSIMP
(SIMPLIFIER DERIV-RULES))

Given a set of rules, it will produce a procedure that will simplify expressions containing the things that are referred to by these rules.

]=> (DESIMP '(dd (+ x y) x))
;VALUE (+ 0 1)

We have a whole stack of rules, and each rule has a pattern and a skeleton.
We have a matcher and an instantiator.  Patterns are fed into matcher and 
skeletons are passed into instantiator.  Expressions produced by instantiator
are passed back into matcher. This process is repeated until the expression doesn't change.

Mentions the danger of infinite loops if the rules are not well designed.  

Matcher is a box that takes as input an expression and a pattern, and it turns out a dictionary, which is a mapping of pattern variables to the values that were found by matching, and it turns out another dictionary which is the result of augmenting the dictionary as a result of matching the expression against the pattern.

Matching program is a page full of LISP...

Comparing the tree of the expression to the tree of the pattern.
Pattern (+ (* (?x) (?y)) (?y))
Expression (+ (* 3 x) x)
Dictionary -- ?x = 3, ?y = x
? x - arbitrary expression
?c x - arbitrary constant
?v x - arbitrary variable

Purpose of the instantiator is to make expressions when given a dictionary and a skeleton.
(DEFINE (INSTANTIATE SKELETON DICT)
(DEFINE (LOOP S)
(COND ((ATOM? S) S)
((SKELETON-EVALUATION? S)
(EVALUATE (EVAL-EXP S) DICT))
(ELSE (CONS (LOOP (CAR S))
(LOOP (CDR S ))))))
(LOOP SKELETON))

What happens inside EVALUATE is important.
(DEFINE (EVALUATE FORM DICT)
(IF (ATOM? FORM)
(LOOKUP FORM DICT)
(APPLY
(EVAL (LOOKUP (CAR FORM) DICT)
USER-INITIAL-ENVIRONMENT)
(MAPCAR (LAMBDA (V)
(LOOKUP V DICT))
(CDR FORM)))))
Apparently there is some magic going on here that he is going to share with us another day.

Garbage-in, Garbage-out simplifier.Building up a more complicated expression from a succession of simple parts

(DEFINE (SIMPLIFIER THE-RULES)
(DEFINE (SIMPLIFY-EXP EXP)
***)
(DEFINE (SIMPLIFY-PARTS EXP)
***)
(DEFINE (TRY-RULES EXP)
***)
SIMPLIFY-EXP)

This simplifier produces a procedure for simplifying the expression based on the context of THE-RULES.

(DEFINE (SIMPLIFY-EXP EXP)
(TRY-RULES (IF (COMPOUND? EXP)
(SIMPLIFY-PARTS EXP)
EXP)))

(DEFINE (SIMPLIFY-PARTS EXP)
(IF (NULL? EXP)
'()
(CONS (SIMPLIFY-EXP (CAR EXP))
(SIMPLIFY-PARTS (CDR EXP)))))

Alternative way to write program, that doesn't require the helper procedure:

(DEFINE (SIMPLIFY-EXP EXP)
(TRY-RULES
(IF (COMPOUND? EXP)
(MAP SIMPLIFY-EXP EXP)
EXP)))

Program to try all the rules:
(DEFINE (TRY-RULES EXP)
(DEFINE (SCAN RULES)
***)
(SCAN THE-RULES))

Now we look at SCAN
(DEFINE (SCAN RULES)
(IF (NULL? RULES)
EXP
(LET ((DICT
(MATCH (PATTERN (CAR RULES))
EXP
EMPTY-DICTIONARY))))
(IF   (EQ? DICT 'FAILED)
(SCAN (CDR RULES))
(SIMPLIFY-EXP
(INSTATNTIATE
(SKELETON (CAR RULES))
DICT)))))

The key to good programming and design is knowing what not to think about. We don't need to think about the chain of recursion going on between SCAN and SIMPLIFY-EXP

This is how the dictionary is defined:
(DEFINE (EMPTY-DICTIONARY) '())

(DEFINE (EXTEND-DICTIONARY PAT DAT DICT)
(LET ((NAME (VARIABLE-NAME PAT)))
(LET ((V (ASSQ NAME DICT)))
(COND ((NULL? V)
(CONS (LIST NAME DAT) DICT))
 ((EQ? (CADR V) DAT) DICT)
 (ELSE 'FAILED)))))

(DEFINE (LOOKUP VAR DICT)
(LET ((V (ASSQ VAR DICT)))
(IF (NULL? V) VAR (CADR V))))