6
$\begingroup$

Many languages support algebraic data types which are essentially tagged unions of tuples or structs. For example, suppose we have a type for an expression node in an AST:

type Expr =
    | Literal of int                 // 23
    | Var of str                     // x
    | Add of (Expr, Expr)            // a + b
    | IndexAccess of (Expr, Expr)    // a[b]
    | FieldAccess of (Expr, str)     // a.x
    // ...

For some purposes we may need a subtype, e.g. the lvalue of an assignment statement might be a Var, IndexAccess or FieldAccess but not any other kind of expression.

In many languages (e.g. Rust) it would be necessary to declare a separate type for just these cases, and there would be no subtype relation between the two types; LValue would not be assignable to Expr via upcasting, nor vice versa by downcasting. In these languages it would be necessary to write a (trivial) type conversion function to transform values from one type to the other.

On the other hand, in some languages there can be subtype relations between tagged union types, e.g. in Typescript the above example might be written like this:

type Expr =
    | {kind: 'Literal', value: number}
    | {kind: 'Var', name: string}
    | {kind: 'Add', left: Expr, right: Expr}
    | {kind: 'IndexAccess', subject: Expr, index: Expr}
    | {kind: 'FieldAccess', subject: Expr, field: string}
    // ...

type LValue = Extract<Expr, {kind: 'Var' | 'IndexAccess' | 'FieldAccess'}>

This can be more convenient since it allows the subtype to be directly used where the supertype is expected, without needing trivial type conversion functions. It also opens the door to other features such as control-flow type narrowing, which requires that the narrower types be expressible within the type system. Given these advantages, what are the reasons against having this feature for algebraic data types?

$\endgroup$
5
  • $\begingroup$ The disadvantages for subtyping in general apply too: handling variance gets confusing, and often leads to either bugs or lack of expressiveness in the type system. $\endgroup$
    – pxeger
    May 23, 2023 at 15:09
  • $\begingroup$ Also, this question is really only about sum types, not algebraic data types in general (which also includes product types and maybe more) $\endgroup$
    – pxeger
    May 23, 2023 at 15:19
  • $\begingroup$ @pxeger I use the term the way it is used on the linked Wikipedia page ─ programming languages like Haskell, OCaml and F# have this concept where a type is declared as a sum of products. The products could be factored out to give type Expr = | Add Add | IndexAccess IndexAccess | FieldAccess FieldAccess | ... but I think this is much less clear, and it would be confusing to write the question that way because Add wouldn't be a subtype of Expr, due to lacking the tag for the Add constructor from the sum type. $\endgroup$
    – kaya3
    May 23, 2023 at 16:15
  • $\begingroup$ That's true, but OOP classes are really just products, so subtyping products is a pretty well studied idea, which is why I think the main point of your question is about subtyping with sum types. But if it's really about both then I'd say it's two questions in one, and should be narrowed in scope. $\endgroup$
    – pxeger
    May 23, 2023 at 18:13
  • 1
    $\begingroup$ @pxeger Yes, the question is about subtyping of sum types, it's just additional context that the sum types I'm interested in are sums of products. Many languages make "sum of products" a language construct without necessarily having sum types as a separate concept; and that language construct is usually called an algebraic data type, perhaps this usage is not exactly consistent with academic usage of that term $\endgroup$
    – kaya3
    May 23, 2023 at 19:30

1 Answer 1

4
$\begingroup$

Memory Layout

In some languages, such as Swift or Rust, the “associated values” are stored inline, and so the size of a sum type is a function of the size of the largest case. If subsets were required to be compatible with the whole, they could be much larger than necessary.

Consider this slightly impractical example:

enum Whole {
  case nothing
  case integer(Int32)
  case floatingPoint(Float)
  case gigantic(fee: String, fi: String, fo: String, fum: String)
}

enum Part {
  case integer(Int32)
  case floatingPoint(Float)
}

print(MemoryLayout<Whole>.size) // 65
print(MemoryLayout<Part>.size) // 5

Note that this isn’t the case in TypeScript, where these types are just a single reference either way.

$\endgroup$
4
  • 1
    $\begingroup$ This proves a casting step is necessary, but it could be implicit $\endgroup$
    – mousetail
    May 23, 2023 at 14:39
  • $\begingroup$ Languages affected by this tend not to do conversions like this implicitly; however, you could write a macro for these casts. $\endgroup$
    – Bbrk24
    May 23, 2023 at 14:41
  • $\begingroup$ @mousetail Implicit casts get more complicated once you start dealing with first-class functions ─ if foo is a function of type () => LValue and somewhere expects a callback of type () => Expr, for example, then you have to pass a version of foo that is composed with the cast operation. $\endgroup$
    – kaya3
    May 23, 2023 at 15:14
  • $\begingroup$ Supporting implicit casts for the specific case of enums does not mean you need to always support them in every case. You could not allow implicit casting of functions for the reasons stated $\endgroup$
    – mousetail
    May 23, 2023 at 15:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .