Notes
2026/01/16
Continuing my note on structural types, I've been wondering how record types (and thus record subtyping) fit into the picture of a simple type system for a language with a dynamic feel. Such a type system needs to be both simple to implement and flexible enough that pattern matching can be built as a library out of simpler conditionals and destructuring, instead of being included as a core construct in the language (and the type system).
This last requirement makes ML-style algebraic data types with nominal typing a bad fit: Data type definitions bundle together the variants of a type and the fields of a type. In other words, enums + structs. Sum types + product types. This is simple (and makes recursive types a lot easier, because iso-recursive folds/unfolds can be inserted when such a data type is constructed or pattern matched).
But if variants are bundled together under a name (in the form of nominal types), the (structural) notion of subtypes of these variants is lost. In ML, you must match on the entire variant at once: You can't incrementally refine Option T to Some T in one branch and then further refine based on other conditions. The pattern matching happens in a single step, making it impossible to build up pattern matching from smaller, composable pieces.
An alternative is to use flow-sensitive typing, where a type is refined to a subtype as part of conditionals and other control flow. While TypeScript with its union types might be the most well-known example, simpler approaches have been explored in Typed Racket and various papers.
So variants should be structural and flow-sensitive typing should handle the refinement. But what about the fields themselves? If variants are structurally typed using union types, how are the fields of a struct specified and typed? One possibility, which fits the style of dynamic languages that use objects, is to use record types with named fields. This is the option chosen by TypeScript (which obviously needs to be able to type JavaScript's objects to be useful).
The big drawback is that records with named fields usually come with the expectation of supporting width and depth subtyping, so that a record such as {foo: X, bar: Y} can be used wherever a record of type {foo: X} is expected. This adds quite a bit of complexity to the type system: Record subtyping requires tracking field sets, recursive depth checking, and dealing with field permutations.
But maybe it's enough for a language to support only tuples with positional fields and without subtyping, so that (X, Y, Z) is not a subtype of (X, Y). Subtyping would still be necessary in such a system, but only for flow-sensitive typing and union types, not for the fields of a data structure. This dramatically simplifies the implementation: Tuple subtyping just checks arity and element types, while union subtyping is simple set inclusion.
If we think of algebraic data type definitions as combining unions/enums/sums and tuples/structs/products, the structural subtyping would be restricted to the former.
Has such a combination been explored in depth? It sits somewhere in the middle between nominal type systems without subtyping and fully structural type systems with sophisticated subtyping. The practical win is implementation simplicity: you get flow-sensitive pattern matching without the complexity of record subtyping. Whether this feels like a sweet spot or an awkward middle ground is something I'll need to discover by building it.