sicpsgjd/2/4/jord/lecture.org

• Lecture 4A: Pattern Matching and Rule-Based Substitution

Lecture 4A: Pattern Matching and Rule-Based Substitution

https://youtu.be/_fXQ1SwKjDg

last week we wrote a stylized language for elementary calculus rules

it was very stylized; it followed a dispatch structure

the calculus rules are like this:

            rule
 pattern ----------> skeleton
    |                   |
    | match             | instantiation
    |                   |
    v                   v
expression |----->  expression
 source              target

pattern

something that matches

skeleton

something you substitute into to get a new expression

the pattern is matched against the expression (source) and it produces a new expression (target) by instantiation of a skeleton

instead of stooping to the computers way of understanding these rules, we are going to bring the computer to us

we will separate the structure from the rules themselves

here are some rules:

  (define deriv-rules
    '(
      ( (dd (?c c) (? v))		0 )
      ( (dd (?v v) (? v))		1 )
      ( (dd (?v u) (? v))		0 )

      ( (dd (+ (? x1) (? x2)) (? v))
	(+ (dd (: x1) (: v))
	   (dd (: x2) (: v)))	  )

      ;; ...
      ))

we are making up a language here

'?' we are calling pattern variables in the language we are inventing ':' we are calling skeleton evaluation (substitution objects)

heres some syntax:

  ;; Pattern Match

  ;; foo -- matches exactly foo
  ;; (f a b) -- matches a list whose first element is f,
  ;;					 second is a,
  ;;					 third 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,
  ;;		results of instantiating each of f, a, b
  ;; (: x) -- instantiates to the value of x as in the pattern matched

gjs: "it's so much fun to make up a language"

what would we do with such a thing?

we are going to write a program called Simplifier

  (define dsimp
    (simplifier deriv-rules))

  ;; (dsimp '(dd (+ x y) x))
  ;; -> (+ 1 0)

we have a "deck" of rules

        +----------+
      +----------+ |
    +----------+ | |
  +----------+ | |-+
  |   RULE   | |-+
  |  p -- s  |-+
  +----------+

        "dictionary"
 +-------+       +--------------+
 | match | ----> | instantiator | ---+
 +-------+       +--------------+    |
    🡑                                |
    |      *expressions*             |
    |                                |
    +--------------------------------+

–> break

THE MATCHER

                +--- PATTERN
                |
                v
               +---------+
expression --> | matcher | --> dict
               +---------+
                        |
                        v
                      dict

the matcher is complicated. i dont think ill reproduce it here

there is a string of case analyses. it ends with the general case, an important pattern:

  (define (match pat exp dict)
    (cond ((eq? dict 'failed) 'failed)
	  ((atom? pat)
	   ;;...atom patterns
	   )
	  ;; ...
	  ((atom? exp) 'failed)
	  (else
	   (match (cdr pat)
		  (cdr exp)
		  (match (car pat)
			 (car exp)
			 dict)))))

gjs sez: "go do a startup, make a couple mega bucks"

we see our first eval/apply! we wont learn about it today tho

–> break

"gigo" –> garbage in garbage out

the simplifier is a recursive traversal of an expression, in parts and in whole.

another idiom:

  (define (simplify-exp exp)
    (try-rules
     (if (compound? exp)
	 (map simplify-exp exp)
	 exp)))

the recursion here is hard we dont have to think about it if we did, we'd get confused

gjs: "learn how to program with abandon