cc @clattner as author
Before I start bike-shedding, I want to say thank you for getting this out. This is something Mojo sorely needs (not the least of which because I don’t like writing compilers without sum types), and I’m a fan of the implementation.
Horizontal space usage
The first thing that jumps out at me is that, while the “constructor” syntax for enums is both concise and nice for small enums, it will quickly grow out of hand.
Here’s the struct which represents a function declaration in TypeScript’s AST (since ASTs are a well known use-case for sum types):
// TypeScript Internal Structure (Interface-based AST)
interface FunctionDeclaration {
name?: Identifier;
typeParameters?: NodeArray<TypeParameterDeclaration>;
parameters: NodeArray<ParameterDeclaration>;
type?: TypeNode;
body?: Block;
modifiers?: NodeArray<Modifier>;
pos: number;
end: number;
flags: NodeFlags;
transformFlags: TransformFlags;
flowNode?: FlowNode;
}
Translated loosely to this proposed syntax:
enum TypeScriptASTNode:
case ...
case function_declaration(
name: Optiona[Identifier],
type_params: List[TypeParameterDeclaration],
params: List[ParameterDeclaration],
return_type: Optional[TypeNode],
body: Optional[Block],
modifiers: BitFlags[Modifier],
pos: Int,
end: Int,
flags: BitFlags[NodeFlags],
flow_node: Optional[FlowNode],
)
case ...
Although a typescript AST may be a bit of an extreme example, it illustrates the point I want to make, which is that I think that we may want some kind of “proper inline struct” syntax for this. This allows more complex cases to be declared using a more verbose but more expressive struct syntax, allowing familar syntactic re-use of things like member annotations. However, this leads me into my next point, which is also partially motivated by ASTs but additionally from message passing.
Enum Variants should be structs
In Rust, in order to neatly express the ability to take a reference to an enum variant, I need to do something like this:
struct GetOp {
key: String
}
struct PutOp {
key: String,
value: String,
}
struct DeleteOp {
key: String,
value: String,
}
enum KVOp {
Get(GetOp),
Put(PutOp),
Delete(DeleteOp)
}
This is annoying for a 3-message-type key/value store, but imagine an actually complex message passing system with a few dozen message variants. Given that, by my reading of the proposals, enums will desugar into unsafe unions of generated structs with an associated tag, I’d like to expose those structs. This means that the following would be valid:
def convert_to_hsl(rgb: Color.rgb) -> Color.hsl:
...
This might also enable attaching methods/traits to individual variants, which can be useful in some cases. For example for use with automatically synthesizing a top-level Writable from each member being Writable, with one of the implementations being a wrapper struct.
Destructuring/Pattern Matching Implementations
For the implementations of destructuring, has multiple out arguments been considered? That’s my preferred option because it has additional utility in other places. Even if that’s not an option, I’d like to see a little more clarity on the how the desugared enum spells destructuring and pattern matching, because how that works seems fairly important here and I don’t think that’s clear from the proposal. My main concern is that the expressiveness of that may shape what kinds of exhaustiveness we can reasonably explore.
HI Owen,
Thank you for starting this thread. I’ll focus this discussion on enums, we can create another thread for pattern matching.
On the typescript AST node - what are you trying to convey? It isn’t clear to me that that is a good idea for an enum. While enums are often used for AST’s, not all ASTs are the same. Why do you think an “inline struct” is a good thing to have? Why not make it out of line? Even if “inline structs” are a useful feature for mojo, it isn’t clear why it is related to the proposal - it seems like it should be an orthogonal consideration that would compose into this.
You then move on to point out that Rust forces out of line structs. Why also is that a good thing? Just because Rust does it, doesn’t make it better. It would help if you provided some motivation. The advantage of the proposal allowing a list of named inline fields is that it makes pattern matching much less verbose (removing the extranous struct in the middle when your case has two values). I don’t see a downside to the proposal.
Thanks for raising these topics!
-Chris
Generally love the enum proposal, specifically the beauty of enum being just syntactic sugar for the SumType trait. Three things came up while reading it: one question and two bits of food for thought.
1. Recursive enums
Is there a story for defining recursive enums? Swift handles this with the indirect keyword, which quietly inserts a box. Will Mojo have similar sugar, or go with a more explicit approach where we wrap the self-referencing value in a pointer type ourselves? I’d be happy with either, but it would be good to know which direction the proposal is leaning.
2. Opting into a guaranteed niche representation
The discriminator is a semantic case index, not necessarily a promise about the physical representation or ABI of the type. An implementation may use an explicit tag, a niche representation, or some other encoding while presenting the same
SumTypeinterface.
This is great for ergonomics, but it means layout is invisible at the source level, and a source-compatible change can silently regress it. Concretely (pseudo-syntax, please correct it to match the proposal):
enum Handle:
case Null
case Open(UnsafePointer[File])
Here Null can live in the null-pointer niche, so Handle is 8 bytes and List[Handle] is densely packed. Now someone adds a case:
enum Handle:
case Null
case Open(UnsafePointer[File])
case Closed
Nothing at the call site changes, everything still compiles, but the layout may fall back to an explicit tag: 8 bytes of payload plus a tag byte plus padding, so 16 bytes per element. An array of a million handles just doubled in size, and every traversal of it now touches twice as much memory.
Worth separating two costs here, because they have different causes and different magnitudes:
- Losing the niche. An extra tag byte and the padding that follows it. Usually triggered by adding a case. Cheap in isolation but expensive across a large array, mostly through cache pressure.
- Falling back to boxing. A heap allocation and a pointer chase on every access. Triggered by recursion or by one oversized case dominating the layout, and much more severe.
Adding a case typically causes the first, not the second. I conflated them in my head at first, and I suspect I won’t be the only one.
So it might make sense to let a declaration opt into a stricter guarantee, whether as a decorator, a trait, or a compile-time parameter, signalling to the compiler that this one has to stay niche-representable and that it should error out if it can’t. The payoff is exactly the case above, where someone extends an existing hot enum and gets a diagnostic instead of a silent 2x memory regression. Maybe my mental model is off here, in which case I’d like to know where it goes wrong.
3. Packed layouts for arrays of enums
Does it make sense for an array of enums to get a bit-packed internal representation based on the number of cases? I do this in Dagr: an array of payload-free enums is bit-packed by the enum’s capacity, and even when cases carry an associated Int/String, I store only the case index and synthesize the value on access. For genuine sum types I store the array as SoA, discriminators in one array and associated values in another, which keeps discriminator scans cache-friendly and lets the payload array stay properly aligned.
It does come with real complexity, and I can’t confidently estimate the cost/benefit ratio, so I mostly offer it as a data point rather than a request.
Lovely!
Question: Why doesn’t match/case follow significant whitespace semantics?
match some_var: defines a code block; one would expect the case statements to be within that block, but in the examples it does so sometimes and not other times, and it wasn’t explained why it behaves that way. The inconsistency - both at the match/case feature level, and in the language block/scoping semantics as a whole - is confusing.
Nice! I’m excited to see enums popping up in the Mojo design work.
The proposal here reminds me a lot of Rust-style enums, which I tend to think of as enumerated types. These are great for implementing things like Result and Optional and such, like your examples show.
To give a concrete example, your color enum works well. Three of the cases define a specific color (red, green, and blue), and the fourth case defines a kind of generic color called rgb. It’s easy to see the rgb case is a different type from the first three since it has arguments/payload and others do not.
Other languages like Java/Kotlin have enums too, but they’re quite a bit different. They don’t allow enumerating types. I tend to think of those as enumerating values instead. In those languages, each case of the enum has the same type, but different values, which can be compile-time checked/optimized/etc. To me, these enumerated values are useful too and solve different kinds of problems than enumerated types.
To get concrete here, with the colors example again, an enumerated value kind of approach would define one enum whose single type has the three r,g,b values. And each case of the enum would be a specific color. eg, red(1,0,0). There would be no way to represent the generic rgb color case with this type of enum. And rather, that’s the point. The list of possible values for this enum are defined only at compile time.
I’d love to be able to use both kinds of enums in Mojo. Your proposal handles the enumerated types case very well I think. But how would one approach enumerated values?
The comptime system seems like a good place for something like this, since enumerated values are essentially constant values. But the key addition with an enumerated value enum over just a list of constants is those enumerated constants are grouped into a list and checked at compile time at use sites.
Again, concretely, with the color enumerated values, the compiler can check if each color function argument is indeed specifically red, green, or blue at the call site. No other color values would pass compilation.
Hopefully that makes sense. I’d be curious to hear what others think about it.
I’ll focus this discussion on enums, we can create another thread for pattern matching.
ack. I had made them one thread since it was one commit for both closely connected proposals.
On the typescript AST node - what are you trying to convey?
What I’m attempting to convey here is that, for longer enums, there things start to get messy as you add more members. The typescript AST node is used here as a real-world example of something that, if it were expessed in the common “sum types as AST” form, creates a variant with many values. For instance, where do I add member annotations and member doc comments to this “constructor style” declaration?
Why do you think an “inline struct” is a good thing to have?
I suppose it’s my mistake for not illustrating the syntax more precisely. I effectively want this syntax for use with more complex variants, although it should be able to desugar to the same internal construct. Here’s what I imagine the AST node would look like written this way (with a few extra bits to illustrate things I think would be difficult to express with the other syntax).
enum TypeScriptASTNode(Movable, Copyable):
case ...
case struct FunctionDeclaration(Movable, Copyable, AstNode):
comptime AstNodeName = "Function Declaration"
var name: Optiona[Identifier]
var type_params: List[TypeParameterDeclaration]
var params: List[ParameterDeclaration]
var return_type: Optional[TypeNode]
var body: Optional[Block]
var modifiers: BitFlags[Modifier]
"""I am a doc comment describing something important about this member."""
@serialize_as(Leb128) # hypothetical member annotation
var pos: Int
@serialize_as(Leb128) # hypothetical member annotation
var end: Int
var flags: BitFlags[NodeFlags]
var flow_node: Optional[FlowNode]
case ...
In this case, we get to re-use user’s existing familiarity with the struct syntax so that they don’t need to learn a new syntax to do things they currently (doc comments) or will in the future (struct member annotations) expect to be able to do. This lets Mojo keep the shorthand rgb(r: Int, b: Int, g: Int) syntax lean and easy to use, delegating more complex cases such as “I need per-variant docs” to the more verbose case struct syntax.
You then move on to point out that Rust forces out of line structs. Why also is that a good thing?
Rust doesn’t force out of line structs, you can have them, but you can’t create a reference to inline structs. There is no way to spell “give me a reference to the value of the third variant” in Rust, it simply doesn’t exist. This is especially bad given that, as you point out in the proposal, most enum types are syntactic sugar for an integer tag stuck in front of an unsafe C-style union, so the compiler must already synthesize structs for each variant. What I’m requesting here is:
- The ability to make a reference to the value of a variant
- The ability to name a variant as a unique type
- The ability to “take” a variant from an enum for use elsewhere.
It would help if you provided some motivation.
Message passing systems, such as actor systems, can take advantage of sum types to help describe the allowed set of messages to an actor. Once an actor knows what message type it is, I expect most to dispatch inside of a match statement to a set of handlers. The ability to get a reference to the inner value saves the need to have a pile of out of line struct and a pile of variants with a single member variable, since you can just pass around a ref TypeScriptASTNode.FunctionDeclaration. This is orthogonal to case struct syntax, since I’d like this ability even for something simple like Color.rgb.
This ability to separately name structs also composes very nicely with anonymous enums to let users create “sub-enums”. For instance, fsync could raise Errno.EBADF | Errno.EINTR | Errno.EIO | ... instead of just raising errno or needing a separate “parts of errno that fsync can raise” enum.
The advantage of the proposal allowing a list of named inline fields is that it makes pattern matching much less verbose
I think you could still make pattern matching to look the same with the case struct syntax, since I don’t expect an immediate desire to pattern match on comptime information in the case struct instances (although I can think of a few places where that would be very neat).
Proposal makes pattern matching less verbose, but it also moves verbosity into enum.
What if I want to use some struct both as an enum variant and as a type, whose memory layout is independent of the enum that contains it? Without inline structs I have to do something like this:
struct Rgb:
var r: Int
var g: Int
var b: Int
enum Color:
case red
case green
case blue
case rgb(rgb: Rgb)
which is verbose for rgb variant. Another option is to copy and paste contents of the Rgb struct into the enum and keep them in sync, which is also not the best option.
With inline structs something like this can be made:
enum Color:
case red
case green
case blue
case extension Rgb
where extension keyword means that already existing struct is used, which can also be imported from an external library. In this case, the struct is extended by including it in the enum as the Color.Rgb variant.
I don’t understand, where is the verbosity in your example exactly?
In my opinion
enum Color:
case rgb(rgb: Rgb)
is not a concise syntax for variant with one struct. In Rust, it will look like this:
enum Color {
Rgb(Rgb)
}
I don’t understand why you would have to or want to do this. Why wouldn’t you just use:
enum Color:
case red
case green
case blue
case rgb(r: Int, g: Int, b: Int)
You can of course use a dedicated “struct Rgb”, but the point of doing so is if you wanted to put methods on it or re-use it somewhere else. If that’s the case, then yes you want an explicitly declared struct.
There is no proposed mechanic here - until the origin story bakes a bit more, I would like to avoid adding first class indirection. That said, I would hope that this would just be a “heap box” sort of thing, rather than a feature of enums. “Simple things that compose” are preferred over dedicated features IMO.
Sure, I can see a use-case for “explicit layout control”. If/when structs get that, it would be natural for enums to have it as well (since enums would be sugar for structs). I don’t see a reason to do enums first.
While appealing, I’m not aware of how to make this general purpose. The problem is that you want an instance of an enum to have a reliable in place memory representation - this is required to get references to it.
I’m not sure what you mean here? If you want C-style enums:
enum {
Value1 = 42,
Value2 = 17,
Value3 = 42
};
Then you can just use the existing comptime feature. As you point out, these are quite different than Rust/Swift/ML style enums, which are algebraic datatypes.
It’s also possible you’re asking for a hybrid where you define different cases but can specify the tag # and do a conversion cast between them. Such a thing is definitely possible, it would be a logical extension to this that we can explore over time. I’ll add these to the proposal as future directions and additional context. Thx!
## Future consideration: Control over layout and discriminators
The initial proposal provides a pure algebraic data type. Languages like C and C++ use a very different model, which is nonetheless very useful - enums can have specified distriminator values, and supports efficient casts to integer values, and support a specifier for layout information. For example:
enum MyColors : int32_t {
red = 0xFF0000,
green = 0x00FF00,
blue = 0x0000FF
}
The base proposal doesn’t include such affordances, but they can be layered on top when and if demand appears and the complexity is justified. Mojo doesn’t currently provide fine-grain control of struct layout, which is something that should be tackled exposing layout control for enums.
Note that C also supports “enums as random collections of values”, such as:
enum {
Value1 = 42,
Value2 = 17,
Value3 = 42
};
This is a fundamentally different construct than an algebraic data type. Mojo supports such concepts with existing `comptime` values, enums do not need to provide support for this use-case.
Future consideration: Recursive/indirect enum cases
The initial proposal doesn’t provide support for [Swift-style indirect enum cases]( What are indirect enums? - free Swift example code and tips ).
We can evaluate adding such a thing in the future, but it would be preferred to express this with existing language features if possible, e.g.:
enum LinkedListItem[T: Copyable] {
case endPoint(value: T)
case linkNode(value: T, next: HeapBox[LinkedListItem])
}
A more complex struct from an external library could be used instead of Rgb. Copying its contents into an enum would be inconvenient. In my opinion, using it as case rgb(rgb: Rgb) is too verbose
I didn’t want to go down the path of proposing new syntax for Mojo, so I didn’t write any code to explain. But maybe that’s something the discussion needs now. I still don’t want to propose any new Mojo syntax, so I’ll use Kotlin code as a reference.
In Kotlin, our color enum might look something like this:
enum class Color(val r: Int, val g: Int, val b: Int) {
Red(1, 0, 0),
Green(0, 1, 0),
Blue(0, 0, 1);
override fun toString(): String =
"Color($r, $g, $b)"
}
This enum declaration guarantees that an instance of Color is always either Red, Green, or Blue. And it has associated functions that can do things with the values. In this case, I added a string printer function.
Kotlin’s enums have a lot of useful built-in utilities too:
println(Color.Red.name) // prints "Red"
println(Color.Blue.ordinal) // prints "2", essentially the discriminator
for (color in Color.values()) {
// iterates Red, then Green, then Blue into the color variable
}
Color.Red == Color.Red // resolves to True
Color.Red == Color.Blue // resolves to False
You don’t have to write any extra code for this, the language provides these implementations automatically.
The real killer feature is this one though: The Kotlin compiler knows if you’ve handled all the values in a switch or not:
when (color) {
is Red -> // do something
is Green -> // do something else
}
This code fails to compile because the Blue case is missing! Super useful feature for code quality and reliability.
I’d love to be able to have this kind of power in Mojo too, with similar levels of ease.
I’m not sure that these kinds of language features are really appropriate for the algebraic data type vision of enums though. Kotlin-style enums are really more of “enums as random collections of values” as you say, but they’re much more expressive than a single integer.
I think I agree that kind of language feature belongs in the comptime system, but I’m having trouble seeing how it could be done with the current Mojo. Sure, you can define a Color struct with r, g, b members, and associated functions. Maybe something like this:
@fieldwise_init
struct Color:
var r: Int
var g: Int
var b: Int
comptime Red = Color(1, 0, 0)
comptime Green = Color(0, 1, 0)
comptime Blue = Color(0, 1, 0)
I didn’t add a string writer in this example, but that’s pretty straightforward I think.
What I don’t see yet, is how you can bind the three different comptime instances of the Color struct into a closed set (or list). How, for example, would you get the compiler to enforce that only these three instances of Color are possible?
So when you have a function that uses Color, say:
def use_color(color: Color):
pass
you can implement the function knowing that the only valid choices for color are Red, Green, or Blue. And anyone that tries anything else won’t be able to compile their code.
I’m not even sure how to call use_color actually… Do we need to explicitly materialize the color instance at the call site?
use_color(materialize[Color.Red]())
I wonder if that’s an efficient way to do it. I think ideally, Mojo would treat Color values as just discriminator values at runtime, until some associated function was needed. Then the appropriate part of the associated data could be materialized at the use-site to satisfy the needs of the associated function. For example, consider a magical future version of Mojo:
var color = Color.Red # internally, just a discriminator value, like 0?
print(color.r) # materialize 1 at the call site
EDIT: actually, if color is a runtime value, then color.r can’t be materialized at compile-time. Some other lookup mechanism will have to happen then.
Maybe doing these things is possible with current Mojo and I just don’t know how to do it yet. Or maybe it needs new language features? This kind of enum seems to have the discriminator part in common with your current proposal. And the flow-control analysis and match behavior might be in common too? But I don’t know much about how matching will work in Mojo yet.
But the algebraic data type part would be an anti-feature for this use-case. So maybe that means this is a different kind of enum than the proposed one? Or maybe there’s a way to do both things with a kind of hybrid? I’m not really sure either. But my main goal here is to make the case for “enums as random collections of values” as something that has good representation in Mojo that’s powerful and ergonomic.
My understanding from the proposal is that you can do
@fieldwise_init
struct Rgb
var r: Int
var g: Int
var b: Int
enum Color:
case Red(Rgb(1, 0, 0))
case Green(Rgb(0, 1, 0))
...
This is more verbose, but keeps the Enum simple.
Klotin uses the old Java Enum pattern, wheras Mojo enums are different. Those different Mojo enum cases are potentially different types and therefore can store different shapes of data.
I think there might be some confusion here, which is my fault. I wrote the proposal like this:
enum Token:
case eof
case identifier(value: String)
case integer(value: Int)
case source_range(start: Int, end: Int)
But as I think you’re pointing out, tuples don’t have names on them. Tuple cases should have a single, unlabeled type for the payload. As a convenience, we make it easy to write a tuple inline:
enum Token:
case eof
case identifier(String)
case integer(Int)
case source_range(Int, Int) # This is a single payload value of Tuple[Int, Int]
As such, pattern matching can directly work on these, and tuple patterns work as you’d expect, but you can’t use names (e.g. start/end) on the payload without defining an explicit Struct and using struct pattern matching:
match someToken:
case .eof: ... # ok
case .identifier(value): # ok
case .integer(value): # ok
case .source_range(start, end): # ok
case .source_range(start=x, end=y): # not allowed
Does this make more sense to people, I’ll update the proposal when I get a chance to align with this.
-Chris
ps. as an aside, it doesn’t make sense for a source_range to be in a Token, but you get the idea.
I’m afraid for this to work we would need to introduce a PackedSpan, or if a type has a NarrowType trait, then it can be handled differently when wrapped in a regular Span. Similar mechanism could work for SOA. For SOA there are precedents in Odin, Zig, Julia, and some library solutions in Rust and C++. Bit packing is a bit more exotic, although Ada and Pascal supposedly had them. AFAIK modern languages do not go beyond bitset, but as we already have quantized numeric types in Mojo, there might be some synergies there.
IMHO SOA, has even broader application as with SOA we could load field values directly into SIMD or hand it of to GPU.
For reference, there is this video by Jonathan Blow where he discusses the SOA concept for his programming language, as far as I know Odin was heavily influenced by this presentation:
The link jumps to a time stamp 47:43, the topics before are also quite interesting in regards to structure layout and API ergonomics, but they are quite exotic.
There is also an EoA, but it likely does not require special compiler support Enum of Arrays
Oh, thanks. I was not aware of this pattern.