* 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:
#+BEGIN_SRC scheme
  (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)))	  )

      ;; ...
      ))
#+END_SRC

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:
#+BEGIN_SRC scheme
  ;; 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
#+END_SRC

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
#+BEGIN_SRC scheme
  (define dsimp
    (simplifier deriv-rules))

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

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:
#+BEGIN_SRC scheme
  (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)))))
#+END_SRC

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:
#+BEGIN_SRC scheme
  (define (simplify-exp exp)
    (try-rules
     (if (compound? exp)
	 (map simplify-exp exp)
	 exp)))
#+END_SRC

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