Tagged Unions Are Overrated (buttondown.email)

> "can't pattern match if something-something pointers"

The main confusion I see is that in many languages it is unclear whether sum types are a runtime or compile time thing, which decides whether pattern matching is semantic or syntactic. Of course nobody wonders whether "if then else" is semantic, but for pattern matching I admit I am myself confused:

- in C all types are compile time (and loosely enforced) so if you want sum types, do them yourself. Implementing the matching is quite straightforward but unsafe and pedantic.

- in Java all type information is available at runtime: sum types can be implemented easily (casting to Object), matching is safe and can be compact if done with e.g. arrays.

- in C++ thinks start getting trickier: you can certainly do a lot mixing static and dynamic casts, but will this remain readable?

- in ML languages: AFAIK this is completely implementation defined. The compiler may choose to box some or all variables. Obviously in such a language you much less care about what is going on under the hood. In return you get a true pattern-matching construct.

- in Rust and others: frankly I don't know where they stand in regard of compile time vs runtime :)

It's against HN's written Guidelines to moan about the format of articles

> now everything has to be boxed [...] every access has an indirection, etc.

The article makes clear that it is speaking of compiler intermediate representations. Those are pretty much by definition boxed, linked data structures that live on the heap.

> Migrating some C++ code from OOP inheritance to variant-like stack-allocated value types has always resulted in n-fold improvements to runtime performance in my case.

Was this in the context of processing some form of programming language IR?

Yes, C++ is not an "object-oriented language" and never was.

The OO features were added because at the time it was the raging fad and people thought that every language simply must have "OOP".

But "OOP" was never a foundational principle for C++, more like a tacked-on sidecar.

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.

> 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.)

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

    ;; 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) ...))

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

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

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

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.

Yes. Or to generalize, language features are overrated. Ergonomics and support are underrated.

Sadly, this reinforces the moat of legacy language. Why move to a new language with marginally better language features, when you can stick to languages that already have good JetBrains support?

Or "Tagged unions are great, but not as good as they could be (depending on whether your language has good pattern matching) and maybe you could roll something worse yourself".

There's a hack!

You can do

    data Value a =
      I32 Int32 a
      B Bool

and then

    type Value1 = Value ()
    type Value2 = Value Void

as a hack

Scala and TypeScript have (partial) answers to this.

In your example, Scala 2 would let Int32 and Int64 inherit a trait that Str doesn't. TypeScript would let you write a union type Int32 | Int64 that doesn't include Str (or add ExtraValue), and I think Scala 3 will have something very similar.

I used to think that this was only ever going to be possible with some sort of incomprehensible type trickery that I would never be able to understand. Then TypeScript came along and showed me that no, actually, in a structural type system, it's just about as simple as you could imagine:

    type Foo = { kind: 'A', aItem: number } | { kind: 'B', bItem: string } | { kind: 'C' };
    
    type SubsetFoo = Foo & { kind: 'B' | 'C' }
    type SupersetFoo = Foo | { kind: 'D', dItem: boolean };

I'm sure there are imperfections here. For a start, SubsetFoo's normalized form looks rather ugly when you mouse over it in VSCode. But it does get you the niceties of exhaustiveness checking and type-aware suggestions with control flow awareness, etc..

    type SubsetFoo = Extract<Foo, { kind: 'B' | 'C' }>;

OCaml has this for unions, see Polymorphic Variant Types here: https://www.ocaml.org/releases/4.11/htmlman/types.html