I detect a pattern

Is someone teaching programming language theory in terms of type theory, and leaving their students with the impression that all good things are derived from static type? Or are people just dazzled by ML, and confuse its various aspects? For whatever reason, a lot of strange claims are made on behalf of static typing. It's not just people confusing it with "functional". On LtU recently, someone claimed dynamically typed languages can't have formal semantics, and no one corrected them. And then there are occasional claims that pattern matching depends on static types...

The obvious counterexample is Erlang, which uses pattern matching heavily. But other than that, there aren't many dynamically typed languages with pattern matching. Surprisingly, even in Lisps, which can add it easily, it's rarely used. I know there are Scheme pattern matchers, but I don't think I've ever seen code that uses one. There is a full-featured bind for Common Lisp, which can even match regular expressions, but it's not widely used. (CL also has destructuring-bind, but that only works on lists, and therefore isn't used for much besides macros.) Why is such a convenient feature not adopted?

This is not about static type, of course; rather, I think it's about syntax. I've tried writing simple functions with a pattern-matching defun, and been disappointed with their readability. Simple numeric ones are okay:

(defun-pat fib ((0) 1)
               ((1) 1)
               ((n) (+ (fib (- n 1)) (fib (- n 2)))))

But more complex patterns have far too many parentheses:

(defun-pat cat "Simple APPEND"
  ((nil rs) rs)
  (((cons l ls) rs) (cons l (append ls rs))))

The problem isn't specific to defun-pat; bind has the same number of parentheses. This is the same parentheses problem as let, only worse. The three left-parentheses in a row are hard to read, even if you're used to sexprs. You have to count them, which is much harder than merely recognizing them.

You can make it a little easier by the same tricks used for let. You can lose one layer of parentheses by writing alternating patterns and bodies, instead of enclosing the pairs in lists. You can use a different kind of parentheses for one of the layers, like Clojure and some Schemes. (I don't like this because it requires matching right-parens.) If you're willing to forgo matching patterns in multiargument parameter lists, you can get rid of another layer. And you can replace the parentheses with something else by adding syntax.

As with let, pattern-matching has a slightly complicated structure, and syntax can flatten it. This appears to be necessary to make it useful. Pattern-matching is valuable, but not when it's hard for humans to read.

It's also not really convenient unless it's integrated into other binding constructs. It's easier to use accessors than to write an extra bind form to split an object. Pattern matching only comes into its own when it's built into lambda and define and the other common constructs, so you can pattern-match without additional work. Theoretically this can all be done with macros, but in practice too many places have to change. Pattern matching needs to be built into the language to be useful.


  1. Chicken Scheme has a family of pattern matching macros built-in to the base language. I use them all the time, usually in complex macros. I agree that the syntax isn't very nice but it usually beats manually car, cdr and pair?

  2. Oh, it's like destructuring-bind with multiple branches. I'd probably use it, if I used Chicken (and didn't care about portability).


It's OK to comment on old posts.