Hacker News Reader

Comment by yoneda | Hacker News Reader

The primary advantage of proper pattern matching compared to ad hoc "instanceof" checks is exhaustiveness checking. I love the comfort in knowing the compiler will tell me all the places in the code that need to be updated when I add a new case to an algebraic data type. I know the article touches on this, but IMHO the author under-appreciates this important feature.

View on HN

> The primary advantage of proper pattern matching compared to ad hoc "instanceof" checks is exhaustiveness checking.

In programming language intermediate representations (the context of the article) exhaustiveness checking might not be as useful as in other contexts. You will have many variants, but for every concrete operation you want to do on the IR you will only consider a few of them, with a default catch-all case for all others.

For example, imagine you're writing a tool to represent and process source code for a Python-like language. Here are the statement types:

    type Statement =
        | Assign var value
        | ExprStatement value
        | If cond true_branch false_branch
        | While cond body
        | Return value
        | Break
        | Continue
        | With context body

(I'm sure I forgot some interesting ones.) You want to do some analysis related to branching control flow statements. These are If and While, so you write:

    let analyze_control_flow stmt =
        match stmt with
        | If _ true_branch false_branch ->
            do_something_with true_branch;
            do_something_with false_branch
        | While _ body ->
            do_something_with body
        | _ ->  // not a branching control flow statement
            ()

This works nicely. Except that Python recently got pattern matching itself, so you add a new variant to your Statement type:

        ...
        | Match pattern cases
        ...

and then you recompile and fix a few exhaustiveness errors and feel happy that you have handled everything, except that you haven't. You would also need to update your definition of analyze_control_flow, but due to the catch-all clause your compiler didn't alert you to this.

(On the other hand, such fundamental language/IR changes are relatively rare.)

I haven't done compiler work, but your note makes sense.

However I've been writing a fair amount of ReScript (OCaml but in JavaScript: The Good Parts) for UI work, and we never use catch-all in pattern matching.

It is an all-or-nothing proposition: you want to have complete certainty all the time that the compiler will catch all possible cases when the type is modified.

Without that certainty, discriminated unions are simply a lot of work for nothing in return.

This can lead to verbose code, but sometimes it is solved by generic handlers.

    let onControlFlow = (stmt, cb) => {
      switch (stmt) {
       | If(body)
       | While(body) => cb(body)
       | Module(_)
       | Let(_)
       | Statement(_) => ()
      }
    }

This is an unrealistic contortion of your example, but in user interfaces there are often cases where there is some sort of grouping within an ADT, and thus we can apply the same function to the tagged data common to it.

The normal OCaml compilers have an optional warning (-w +E) for "Fragile pattern matching", the upshot being that you can make use of catch-alls, while still remaining aware of their presence.

I think the best solution to this is when the language's syntax supports ORing cases together like this:

    let analyze_control_flow stmt =
        match stmt with
        | If _ true_branch false_branch -> ...
        | While _ body -> ..
        | Assign _ _ | ExprStatement _ | Return ->  ...

So you still get to avoid repeating code, but all the variants are included visibly and the compiler can verify it.

Would sub-categorizing these help? Like statement contains a control flow statement or whatever other categories. A control flow statement can be a branching control flow statement or a non-branching one, etc. Or are these categories like “tags” where you might have multiple axes of analysis?

The former is available in Rust, just with a bit more boilerplate. The latter is probably achievable in some way if the language were to change and, even if not necessarily relevant to this problem, I could see being useful in some places...

The categorization would need to fit nicely into a tree of types, which seems unlikely, so a tag-based approach would be better. With a bit of custom DSL you can enforce exhaustiveness.

    ;; can store at compile time the tags for an op
    (define-op (if a b c) 
     (:tags my-tags:control my-tags:special)
      ...)

Elsewhere:

    ;; can check at compile-time if all ops 
    ;; for that category are tried
    (ematch-op (e :tags my-tags:control)
      ((if test then else) ...)
      ((while test body) ...))

Maybe this can be done with Rust macros too

Another approach in OO land is abstract classes with methods for each tag, forcing inheriting classes to implement the new tag.

The author specifically discusses that topic, toward the end of the article. You don't need to guess about the author's experience there. Just read the rest of the article.

Seems like you didn't read my comment in its entirety. I acknowledged that the article discusses exhaustiveness checking, so you don't need to point that out to me. I didn't make any guesses about the author's experience; I stated my opinion of their opinion.

I'm not sure if exhaustiveness is that useful. Rather than forcing the people who use the data-type to keep track of any changes you instead force anyone who changes the data-type to keep track of any place where it is used. If you automatically enforce exhaustiveness then you either need to freeze all your public data-types or turn every update into a breaking change.

> . If you automatically enforce exhaustiveness then you either need to freeze all your public data-types

I think that's good practice!

Reply on news.ycombinator.com