Sum types covering Swift enum use-cases.

[dabrahams]

Sum types have the following properties: Sum<A, B> == Sum<B, A>, Sum<A, A> == Sum<A>, Sum<A> == A.

The question is how to generalize them to cover the use-cases handled by Swift enums. There are two issues: named cases and raw values.

Named cases can be expressed as labeled tuple types, e.g.:

// Swift
enum X {
  case a(Int), b(c: Bool, Bool), d
}

// Val
newtype X = Sum<{a: Int}, {b_c: Bool, b: Bool), {d: {}}>

The RawValue type can be expressed as an optional leading named generic argument, defaulted to Int:

// Swift
enum Y: String {
  case a = "one", b = "two"
}

// Val
newtype Y = Sum<Discriminator: String, {a:{}} = "one", {b:{}} = "two">

Which makes the idea generalizable to cases with payloads.

Lastly, various sugars can be explored to make typical enum use-cases more palatable to work with, eg. making (z:) a way to write (z:())

[kyouko-taiga]

One thing occurred to me.

If I'm not mistaken, Swift's enum cannot have raw values if they also have associated values. Nonetheless, there must be an implicit discriminator used by the language implement to tag the different cases. It is probably some sort of integer, possibly hidden in the bits of the enum's storage. I think it isn't unreasonable to imagine a world where we could access it at the user level.

Obviously we also need a discriminator in Val for the general case (e.g., Sum<Int, Bool>), which I think should be the metatype of the stored value. So one could imagine that the default discriminator be any Metatype, at least notionally. In practice, it can still be a small integer, as it happens in Swift when the raw value is set to String.

[kyouko-taiga]

Another thing: I'm not completely convinced that hiding the bits of the discriminator is worth in the general case. A metatype is one machine word, which isn't the end of the world.

One advantage of storing the metatype inline is that we can convert a Sum<A, B, C> to S<A, X, Y> without any change of representation, which might come handy in the no-std mode.

[dabrahams]

IMO it would be a terrible mistake to multiply the stride of Sum<Bool, Void> by 2x the machine word size simply for a capability we're not even sure anybody needs… to say nothing of what happens to Sum<Bool, Sum<Bool, Void>>…

What does no-std have to do with whether the representation changes anyway? IMO if you want to do that kind of thing, you should manage the bits of the storage yourself.

[kyouko-taiga]

IMO it would be a terrible mistake to multiply the stride of Sum<Bool, Void>

That's why I said "in the general case".

My position is that we can probably start with the naive approach and get an understanding of the use cases we want to address with bit hiding before we develop something very sophisticated. I'm saying that because I suspect coming up with a discriminator is slightly more complex in Val than it is in Swift.

I was mistaken about the no-std thing. Forget about it.

[dabrahams]

If I'm not mistaken, Swift's enum cannot have raw values if they also have associated values.

Yes. But, as I mentioned in slack, there's no good reason for that restriction… except possibly avoiding confusion.

Nonetheless, there must be an implicit discriminator used by the language implement to tag the different cases. It is probably some sort of integer, possibly hidden in the bits of the enum's storage.

Hidden in the bits yes, but not necessarily stored, which means it may only be a notional value. After going through your post, I believe you understand the following, but I think it may be useful for other readers:

The size of enum Q { case a(UnsafePointer<Int32>), b(Bool) } could have been 4 if the Swift compiler was smarter. Since Int32 is 4-byte aligned, there are at most 2^(32 - 2) inhabitants for case a (In fact pointers have spare high bits too, so it's less than that). Regardless, all the other 2^32 - 2^30 bit patterns in can be used for other value representations. That's how MemoryLayout<Optional<UnsafePointer<Bool>>>.size is the same as MemoryLayout<UnsafePointer<Bool>>.size.

However, there are limits to how smart we can expect to be about taking advantage of that.

I think it isn't unreasonable to imagine a world where we could access it at the user level.

Yes, “what is the ordinal of the subtype stored in this Sum type?” is a reasonable question to ask. But also note that the rawValue in Swift is not necessarily this ordinal either; in general there's a mapping between them, known to the compiler.

Obviously we also need a discriminator in Val for the general case (e.g., Sum<Int, Bool>), which I think should be the metatype of the stored value.
So one could imagine that the default discriminator be any Metatype, at least notionally. In practice, it can still be a small integer, as it happens in Swift when the raw value is set to String.

That's cute. But even if the discriminator is exposed to users as a metatype, I think it's probably also useful to be able to get an ordinal value and I'm not sure that should ever be completely hidden.

[DmT021]

If I may, I have an idea about type generalization in general and a suggestion for enums in particular.
Swift has several different ways to express what is actually all more or less the same.

struct Foo { 
  var foo: Int
  var bar: String
}

typealias Foo = (foo: Int, bar: String)

enum Foos {
  case foo(foo: Int, bar: String)
}

All these definitions are slightly different. Tuples are non-nominal, structs are (may be) ABI compatible for future changes, enum cases are sealed. But their prime purpose is to carry data, and they do it equally good.
What's interesting in enums is that they blur the line between types and values.

enum Foo {
  case buz(Int) // a type
  case bar // a value, but also kinda a type
}

And the coresponding switch statement is almost like dynamic type casting, but has the property of completeness.

switch foo {
case let .buz(value): ... // it's like (foo as? Foo.buz)?.0
case .bar: // (foo is Foo.bar)

So maybe the type system should support bar-like value/types as first class types? Let's call them unit types.

unit type Bar {}
type Buz {
  var value: Int
}
Foo = Bar | Buz

A unit type always represent one value.
Examples of unit types are: Void, Nil<T> (every specialization is unique value), true, false.
Bool can be defined as a union of true and false.

---

Another thing I find useful is tagged types. First of all they prevent mistakes when there are several business type of the same real type, like

typealias Password = String
typealias OAuthToken = String

With tagged types one can't pass a password string to a function accepting OAuthToken.
Another cool thing is that they combine nicely with implicit parameters.

The differentiation between nominal structs and non-nominal tuples in Swift seems to be inconvenient.
But basically tagged type + anonymous type = nominal type.

tagged Password = String
tagged OAuthToken = String

tagged Credential = Password | OAuthToken

[DmT021]

Sorry, my bad. In Swift we often workaround the difference between a enum's case and a type by writing a nested type with the same name as the case, but capitalized:

enum E1 {
  struct A { // or a tagged type based on Int
    var value: Int
  }
  struct B {
    var value: Int
  }
  
  case a(A)
  case b(B)
}

(In reality the structs' content are much reacher, ofc)
This allows us to use types E1.A and E1.B in code that works directly with them.
Ideally we'd like to write it more like:

enum E1 {
  case struct A {
    var value: Int
  }
  case struct B {
    var value: Int
  }
}

But anyway, the main properties are:

• the types are nested.
• the types are named.

From your example I thought there is no way to define a nested named type in a union, am I wrong?

[kyouko-taiga]

You can define the alias in the extension of E1. That will "pollute" the namespace of any other union that happens to be structurally equivalent, but I think in practice it isn't so likely to happen. That is one of the areas where newtype might come handy, because it will create an actual new nominal type, with its own unique namespace.

Another way you could approach the problem is to not make the union the namespace, but a member of a namespace shared with its elements:

namespace Color {
  typealias Any = Union<RGB, CMYK>
  type RGB { ... }
  type CMYK { ... }
}

fun foo(_ c: Color.Any) { ... }
public fun main() {
  foo(Color.RGB(...))
}

[DmT021]

That is one of the areas where newtype might come handy, because it will create an actual new nominal type, with its own unique namespace.

Yes! But will the name resolution work properly in this case? Seems challenging as the union definition is actually in the outer namespace and the nested types are in the, hm..., nested namespace.

newtype Color = Union<RGB, CMYK>
extension Color {
  type RGB { ... }
  type CMYK { ... }
}

[kyouko-taiga]

It will work with a new type, it won't with an alias. That's because name resolution has to resolve the aliased type to find its extensions, but it doesn't have to resolve the definition of a new type to start looking for extensions of the newly defined name. That's the same as with a good old struct. This is fine:

type A { let x: B }
extension A {
  type B {}
}

[DmT021]

Also it seems newtype A = {a: Int} will be equivalent to type A { var a: Int }. It would be nice to find the best common ground for them, to minimize a zoo of types of types.

[waydan]

Sum types have the following properties: Sum<A, B> == Sum<B, A>, Sum<A, A> == Sum<A>, Sum<A> == A.

Is there another property that Sum<A, Sum<A, B>> == Sum<A, B>? I think this is aluded to earlier in the thread, but I want to make sure.

[dabrahams]

Is there another property that Sum<A, Sum<A, B>> == Sum<A, B>?

Yes