Avoiding Accidents in Structural Types

This short survey arose from a Stack Exchange question Language constructs to reduce inadvertent interface implementation in purely structural type systems?, about ways to step out of structural type-compatibility when program logic required it. I've done some work in that area myself, but there are several other versions that make different trade-offs, so this post surveys all those. There are also some "loopholes" to construct pseudo-nominal types, which were part of what we considered as alternatives in my prior work. We argued that adding a nominal recovery on top of a structural base was preferable to adding structural types within an existing nominal type system, and that it's better to have the discretion to expose or not the abilities to create and detect these objects.

The general solution to this problem is known as "brands", also "trademarks" or "tags", and does essentially amount to adding a nominal system on top, but in various different ways that may be more (or less) palatable. This goes back at least as far as Modula-3's branded record types in practical languages. A few examples of this to refer to:

• Modula-3 branded records simply attach a single label string to a structural type.

  Brands distinguish types that would otherwise be the same; they have no other semantic effect.

  These have no subtyping, and could either have a name specified or just get a generated unique one.
• The original version of Strongtalk had brands (but dropped them).
• Glew's "tagging language" used tags as nominal labels for type-based dispatch.
• Malayeri and Aldrich's Unity integrated structural and nominal typing with brands that were quite close to nominal classes.
• There was a "trademarks" proposal for JavaScript (ECMAScript), but it didn't go anywhere.
• Lee et al.'s theory of tagged objects for Wyvern encoded nominal tags on top of a structural basis.
• And I worked with Jones et al. on brand objects for Grace, where a "brand" can annotate an object at creation and its "pattern" can detect objects with that brand's annotation, with a nominal static checker consistent with that. This is discussed in more depth in Chapter 6 of Timothy Jones's thesis.

All of these make some different tradeoffs and are more or less invasive to the rest of the language, and would be useful to look at when considering adding this functionality. I can speak more to the last one than the others; the goal there was to make use of existing language features (pattern matching and annotations), with the static checking layered on top, so the language semantics itself doesn't change, and to separate the ability to brand a value from the ability to discuss a brand type. Others introduce what amount to Java-style nominal classes that can also match structural types, type system extensions that allow more behavioural integration, and other changes that may be interesting to examine.

One of the common example use cases given for this sort of feature, and one that separates things from the "encoding business logic" part that some people have disputed, is encoding abstract syntax tree nodes. It's not uncommon to have multiple syntax elements that are structurally equivalent — variable and constant declarations, for example — but have distinct meanings and can't be interchanged. It is useful to be able to distinguish those types even within a generally structural system. Another common example is things like exception hierarchies: IOError and MemoryError are intended to be distinct, but may have the same shape. These go beyond business logic, but even making business-logic illegal states unrepresentable through the type system is a desirable property to allow in many cases.

"Make invalid states unrepresentable" isn't always the right thing to do, and sometimes that just makes the whole program more complicated, but being able to do that validation where it matters, and have the system enforce that it's consistent, is very useful. There are a wealth of other reasons to want some sort of brand on a subset of your object types, while leaving the rest extensible, and the systems above make different tradeoffs in how they use that.

There are some other techniques that don't involve nominal types and were considered in the Grace design, although they do mostly look like workarounds for the lack of a branding system.

• "Funny-named members": in a purely structural system, with no extension, adding additional slots with unique names can distinguish types. The presence of _isVarDecl distinguishes one type from another with _isConstDecl, even if these members are never accessed (or cannot be accessed). This can be done already at the level of user code, but the language can provide mechanisms for creating them automatically.

  These phantom members raise encapsulation questions as a language feature: if the names are given manually, any code can forge affiliation with the brand, which may or may not be desirable. On the other hand, if they are inutterable names produced mechanically then either the mechanism is global (unencapsulated again) or indexed by something else, preventing claims by other parts of the system — also potentially undesirable when a structural system is setting the baseline expectation.

• Singleton types: these are neither structural nor nominal, but represent a single object's identity as a type. A structural type with a member whose signature involves that singleton type is distinct from any other, and a specific field or method name returning or accepting a singleton type may be reserved for branding purposes. Accepting may be better, as that doesn't leak out the singleton object to clients.

  Singleton types have (limited) other uses, so they could be desirable anyway. Exactly how they work can vary, and whether the singleton type is distinct from the singleton object is quite important. If you have a reason to have these non-structural types anyway, this is at least a somewhat elegant use of existing language features to meet this goal.

• Separating from the static type system entirely: a user-space pattern-matching system can allow the sort of logic in your example without doing anything with types. If every VarDecl or LivestockBird is registered in a (weak) set, can be distinguished by the results of some property accesses, or can be detected at run time in any way at all, that can be encapsulated into a pattern to produce at least run-time errors if the constraint is violated. This broadly amounts to the kind of logic that could be implemented manually, but pattern-matching makes it declarative at point of use in a similar way that type annotations are.

  Dispatch models like Raku's could even allow these to produce real type errors for calling a non-existent method, albeit at run time: subset LivestockBird of Bird where * ∈ $livestockBirds allows you to declare Load(LivestockBird $b), and then passing in a value that isn't a bird or that doesn't belong to the set $livestockBirds will tell you a suitable method doesn't exist.

I think both the brand model and pattern matching offer reasonable language ergonomics, depending on what you're trying to do elsewhere in the language. The singletons & phantom method approaches feel like a hack you use when the language hasn't given you what you need for the task, but they are quite cheap inclusions to the language.