Skip to main content

Lisp: Pattern Matching

As I mentioned earlier, I'm making my way through the SICP lectures.

Today, I'm excited about pattern matching. For instance, consider this:
(define deriv-rules
'(
...
( (dd (+ (? x1) (? x2)) (? v))
(+ (dd (: x1) (: v))
(dd (: x2) (: v))) )
...))
It says that the derivative of x1 + x2 with respect to v is the derivative of x1 with respect to v + the derivative of x2 with respect to v. Notice, it's all data. "No 'if' statements were harmed in the making of this film" ;)

I've played around with Haskell, Ocaml, and Erlang, so I'm familiar with match
statements. They make sense. However, I had never seen someone implement such a system, especially in such an elegant manner.

I'm so used to coding like "if this, then do this". Pattern recognition is all about "if the data matches this pattern, fill in this skeleton and then start over." I feel like I've just been "meta'd".

I've been thinking about how I might apply these things to C. A closure is a struct with a function pointer and a void * to hold some data. A continuation is a stack (perhaps an array) of closures. I would have never thought to code that way in C. However, now that I've seen it in Lisp, it just makes sense.

Of course, major props go to the graph database team at Metaweb. They actually *do* code that way in C, and the coder who started that code base is a woman ;)

The last thing I'd like to say is that it's funny watching the professors teach. They're so confident. They say things like "it's very simple" all the time. That's because they have the material mastered. They know where they're going. Researching is quite the opposite. You don't know where you're going. You don't know if there even is an answer. You're often wrong. It's a lot of fumbling around hoping something's going to work. Since MIT professors spend so much time both teaching and researching, it would seem they must have a bit of a split personality.

As a last statement, I don't know how those students survive without pause and rewind! Seriously, it takes me at least two hours to watch a one hour lecture! Watch, pause, think. Rinse and repeat.

Comments

binary boi said…
Is pattern matching the same as macros?
No, but macros can use pattern matching.