Tagged Unions Are Overrated | Hacker News Reader

Tagged Unions Are Overrated

buttondown.email

44 pointsmpweiher48 comments

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.

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.

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

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

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.

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.

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

I think that's good practice!

> In object-oriented languages like Java or C++, you can implement your AST as an abstract base class and a set of subclasses, and do matching using straightforward type tests — instanceof in Java, or dynamic_cast in C++.

but at a pretty large cost : now everything has to be boxed, will be dynamically allocated by default (yes, object pools and small-size optimization, but that does not produce very readable code and needs constant care), you risk slicing, every access has an indirection, etc.

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.

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

You're arguing that a language that arose specifically to add classes to C was not meant to be object-oriented? I'd be interested in seeing that argument fleshed out in more detail.

It is true that subsequent c++ evolution de-emphasised OOP, but you are completely right that the original selling point of C++ over C definitely was (Simula style) OOP.

Three points:

a) 'Simula style' isn't at all like the Smalltalk-derived programming patterns we call 'OOP'. (Simula was about actor-oriented programming anyways, hence the name.)

b) The unique differentiator for C++ was the STL, and not the OOP features that were done better and cleaner in other languages.

c) The killer feature for early C++ adoption was operator overloading, not inheritance. (Pretty much nobody liked using inheritance in C++ even back in the day.)

> Simula was about actor-oriented programming anyways, hence the name.

Nothing about the name "Simula" suggests actors.

> The unique differentiator for C++ was the STL

https://en.wikipedia.org/wiki/C%2B%2B#History isn't very clear, but it seems to suggest that templates weren't added to C++ until 1990 or later. The STL came around 1993, eleven years after the development of C++ started, not even counting its previous life as C with Classes. Surely in those eleven years people found other differentiators that kept up interest?

> The unique differentiator for C++ was the STL

This involves such a level of ignorance of the history of C++ that you should consider deleting your comment. The STL didn't exist in C++ for the first decade of its existence.

> Pretty much nobody liked using inheritance in C++ even back in the day.

What is your basis for this claim? Don't bother responding, the answer is that it's nothing more than your fantasizing.

Simula and Smalltalk were the two original OO languages. C++ firmly takes its OO capabilities from Simula (the virtual keyword literally comes from there with the same semantics), and is quite distinct from the OO flavour of Smalltalk. Objective-C, with its selector based late binding for example, is clearly Smalltalk inspired.

Its original name was actually "C with Classes".

I can try:

> add classes to C

C is the foundation. Classes is the sidecar.

Every statement in your comment is factually incorrect.

See: http://www.cplusplus.com/info/history/

> In Rust, pattern matching breaks down as soon as your IR contains pointers to its children

> Another way this manifests is that it’s often frustrating that patterns aren’t first-class; I can’t pass around a pattern, or build up a pattern on the fly.

To me this seems like limitations of pattern matching in Rust that perhaps is addressed by Haskell's ViewPatterns language extension. The idea is that the usual ML-style pattern matching exposes too much implementation detail of the ADT, for instance, consider instead the use of a "view function" viewer to convert the structure into a initial segment xs and a last element x.

  pattern (:|>) :: Seq a -> a -> Seq a
  pattern xs :|> x <- (viewr -> xs :> x)
    where
      xs :|> x = xs |> x
  
  lastElem :: Seq a -> a
  lastElem (_ :|> e) = e

:|> would let one treat the sequence data type as abstract (it could be a finger tree[0] underneath, for instance). In the author's use case of representing IRs, one could move the unboxing work into the view.

[0] https://en.wikipedia.org/wiki/Finger_tree

I know that's not part of the article title, but could someone add "...for implementing language ASTs and IRs" to the end of this submission title? That's what the article is about and changes quite a lot the context of the discussion. The context is "tagged unions when programming languages", not just "tagged unions".

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

> the limits of pattern-matching in languages that do support it

And then goes to discuss Rust only. Nope. In many languages pattern matching is crippled because it is only allowed to be used in some contexts, but not in others. Or are crippled by things like "can't pattern match if something-something pointers".

For example, in Erlang you can use pattern matching and guards in function definitions, creating overloaded functions based on pattern-match alone. And you can match arbitrarily complex structures (because it doesn't have pointers etc.). This makes working with ASTs in such a language a breathe.

> "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 :)

I am reading this as tagged unions are overrated in rust because many use cases are not properly supported in rust, or at least not yet

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?

I would agree on most features, but I absolutely love properly implemented, exhaustive pattern matching in strongly typed languages.

Why move to garbage collection when C already has good valgrind support?

The problem with unions/enums is that is hard to pick a subset or superset of them, despite it will be not hard to add to any language. Is similar to projection on the relational model (aka:select), sometimes I need:

    enum Value {
        Int32(i32),
        Int64(i32),
        Str(String),    
    }
    fn only_int(of:Value[Int32, Int64]) -> Value.Str

And other times:

    enum ExtraValue:Value {
        Bool(bool), 
    }

This is analog to structs, where eventually is "discovered" that is nice to:

    let user2 = User {
        email: String::from("another@example.com"),
        username: String::from("anotherusername567"),
        active: user1.active,
        sign_in_count: user1.sign_in_count,
    };


    let user2 = User {
        email: String::from("another@example.com"),
        username: String::from("anotherusername567"),
        ..user1
    };

But somehow enums are still considered second-class in the algebraic type space.

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

I believe you can get a better normalized form of SubsetFoo by instead doing:

    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

Went in with righteous anger at the title came out agreeing with the article. The main advantage of any pattern being a part of the language is the ergonomics of it. If you want to use the pattern in another language for whatever reason that's just as valid but obviously less straightforward.

Aside: what the fuck is going on with this webpage? The only scripts I have blocked are from stripe.com (why are there stripe.com scripts on an newsletter?) and the webpage totally breaks rendering in Chrome. Instead there's a horizontal scroll bar that, when scrolled, renders a different part of the article but ruins the older parts. Is this some method of tracking users reading through the entire article?

Also the entire newsletter content is in a variable in a script tag? If javascript is disabled, you see the entire article. What is the point of all this javascript?

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

But it would be interesting to those of us that build web pages why this one works this way.

This is not just bad formatting, it’s a deeper mystery.

The caricature of HN is indeed a café of webdevs talking shop the whole time

And yet people still do it, always accompanied by a reference to the guidelines.

This isn't HackerParliament, I don't mind people venting about bad web design.

Moaning about clickbait, however, I immediately downvote because it actually does contribute nothing.

> HackerParliament

The right honourable website is rather slapdash with its scripts, without which it cannot render well upon Her Majesty the Chrome.

Hear hear!

> However, the crux of my argument is that it’s easy enough to emulate this construction in other languages.

It's also easy enough to emulate all control flow statements with goto. Tagged unions are valuable because they help communicate restraints. Not only to other developers, but also to the compiler.

I've got to disagree. If anything they are underrated.

Not having them in your language in 2021 should be considered the same as not having if/then/else in your language in 1980.

Reply on news.ycombinator.com