RFC: native algebra data type/tagged union/sum type/enum support

[Roger-luo]

I tried to find an issue that contains a discussion for native support of this but didn't find any.

I think this is a very well-explored feature in the community already and people seem to have been using it for many different cases through packages, I collect some implementations by searching JuliaHub (that might not be complete, so please feel free to add yours):

• Expronicon.ADT (my own): discourse post
• Unityper used by Symbolics.jl: https://github.com/YingboMa/Unityper.jl
• SumTypes (by @MasonProtter ): https://github.com/MasonProtter/SumTypes.jl
• MLStyle (by @thautwarm ): https://thautwarm.github.io/MLStyle.jl/latest/preview.html#generalized-algebraic-data-types
• a few packages trying to improve the current enum should also fall in this category

The reason why I'm requesting opinions on having this supported natively is that I find there are some limitations as a package implementation, mostly because of type-instability created by package implementation and not being able to actually manage the behaviour of allocation, I will refer to this feature as ADT in the following context:

I'm not if this is the only solution, but to make it static, the ADT requires a special fixed memory layout, similar to a C union, that is in principle the maximum size of the variant it contains. Currently Expronicon and Unityper implements this as a special structure, which has a size larger than theoretical because there is no access to control the memory layout from Julia (and we probably shouldn't do it...)

On the other hand, supporting generic ADT can be problematic without support from Julia's type inference, taking the Option<T> type (similar cases like Result etc. are similar) from rust as an example,

using Expronicon.ADT: @adt

@adt Option{T} begin
    None
    Some(T)
end

currently, if we try to make None and Some share the same Julia struct (which also means the same size), the None from Option{Float64} will be different from Option{Int}, so it seems an unintuitive, I don't have a good solution to this if we allow something like this it will create type instability, but perhaps if this is a native type, then type inference can at least warn people.

Better support of the ADT requires also pattern matching, but I think we can do that separately as long as reflections are implemented for the built-in ADT.

There probably gonna be more design details that the community wants to work on since I'm not the first one proposing this. But I want to open this post so people could push it forward.

[StefanKarpinski]

but perhaps if this is a native type, then type inference can at least warn people.

Type inference in Julia doesn't emit warnings, it's purely for optimization, not type checking.

[vtjnash]

Also reserved names include a, b, var, and body. Though the list changes quite regularly, and you can mess up performance for other people quite badly by doing this, so it is very highly discouraged.

[Roger-luo]

Also reserved names include a, b, var, and body. Though the list changes quite regularly,

I could also just forward non-variant names to getfield it would result in a less informative error message but probably not that bad.

you can mess up performance for other people quite badly by doing this, so it is very highly discouraged.

could you elaborate why overloading getproperty(::Type{MyType}, name::Symbol) will mess up performance? I thought this will only affect MyType, not other types? Or this creates a problem for the optimization?

[vtjnash]

It creates an optimization barrier, which can end up hurting anyone else's performance.

[Roger-luo]

Ok, thanks for notifying this, I didn't know overloading this signature would affect other people's code even if it's not defined for other types since it seems to me getproperty is just a normal function that forwards to getfield.

I probably still don't get what optimization barrier means, but this seems now giving us another reason that we should have a native ADT rather than package-level support.

[chriselrod]

This getproperty overload breaks my code doing a linsolve!, a fairly small example is here: Roger-luo/Expronicon.jl#77

[RigobertoPalinskiHJS]

It's great to see that there are already several package implementations of Algebraic Data Types (ADT) in Julia, and that they are being used for different use cases. However, you raise an interesting point about the limitations of package implementations of ADT, specifically with regards to type instability and memory layout.

Having ADT supported natively in Julia would certainly be beneficial in terms of performance and memory management. However, it is important to carefully consider the design and implementation details of such a feature to ensure that it is consistent with Julia's type system and type inference.

In addition to pattern matching, which is a common feature of ADT in other programming languages, it would also be useful to have some reflection capabilities for built-in ADT. This would allow users to introspect on the structure of the ADT and its fields, which could be useful in certain use cases.

Overall, I think it's a great idea to explore the possibility of adding native support for ADT in Julia, and it's encouraging to see that there are already several package implementations that can serve as a starting point for such a feature. It will be interesting to see how the Julia community approaches this topic and how a native implementation of ADT could be integrated into the language.

[Tokazama]

I'm not sure we really need a new TaggedType<:Type to accomplish this. As I mentioned in elsewhere, we mostly just need ways to optimized direct user intervention in inferring unions. We already have union tags but we have no way of directly interacting with them and have to completely load data before we know the type at the user level.

This LLVM guide is a good read if you want to think about how this is done. Again, we already kind of do this, but haven't settled on a single way of making this happen internally and efficiently.

[Roger-luo]

We already have union tags but we have no way of directly interacting with them and have to completely load data before we know the type at the user level.

Do you mean we are already doing this for Union? Could you elaborate on what a potential example would be if what you described in implemented?

This LLVM guide is a good read if you want to think about how this is done.

Yeah, I think that looks similar to how I supported ADT in Expronicon, with some limitations due to new, getproperty etc. as mentioned above.

[Roger-luo]

We already have union tags but we have no way of directly interacting with them and have to completely load data before we know the type at the user level.

I'm not sure I get what you mean here, but do you mean this is just a syntax issue but the compiler actually supports it?

[Tokazama]

Do you mean we are already doing this for Union? Could you elaborate on what a potential example would be if what you described in implemented?

Yes. Rust's Enum type is just a named union instance that uses tag bits, almost exactly how that LLVM guide does it just under the hood.

Now our unions aren't exactly that because as soon as it's not a bits type within a certain size, then we just do a pointer to a boxed value. It may be worth exploring if it's worth having a specific type that adjusts this storage model a bit, taking advantage of quick runtime inference on the bits type.

With the exception of generating optimized methods to access those bit tags, I don't think it's a compiler issue as much at this point. You can jerry rig this with mutable types but immutable types you really need to do this in C first with how stuff is designed right now.

So if someone is really interested in making this happen I'd start with making an ergonomic named and tagged Union type work first. We can do compiler optimizations in places like the "compiler/tfuncs.jl" once we know what works and won't take too long in JIT compilation.

[Tokazama]

That seems to be the existing implementation of typeof you copied, so I'd recommend to just use typeof.

I'm not sure what you mean by this since it's not at all like the implementation of jl_typeof. It takes jl_get_nth_field and returns the type tag known at run time.

[vtjnash]

returns the type tag known at run time

What do you think typeof is?

[Tokazama]

I mean the union type tag byte that is UInt8, not the jl_taggedvalue or any of its union components. In the pattern matching example this can be lowered to code that just tests if two UInt8 are equal because the field, union type, and expected union member type are compile time known and the result of find_union_component can be resolved at compile time.

[vtjnash]

Have you looked at the lowered code for typeof when used on a value from a field?

[Tokazama]

I'm assuming you're talking about getfield(obj, field) isa expected_type && return getfield(obj, field) lowering to what I described above and a bit cast. My point has been that we already have the basic components in place to do ADTs and some pattern matching is close to what we do (when fully optimized), we just need to expose some of the internals so that something like Expronicon can build on it to create more sophisticated patterns/methods.

[MasonProtter]

Thanks for bringing this up @Roger-luo. After thinking about this conversation, I've made some updates to SumTypes.jl that I think makes some steps towards the concerns raised here.

supporting generic ADT can be problematic without support from Julia's type inference, taking the Option type (similar cases like Result etc. are similar) from rust as an example

SumTypes.jl is able to handle this pretty well now, fully generically and without type instability.

I'm not if this is the only solution, but to make it static, the ADT requires a special fixed memory layout, similar to a C union, that is in principle the maximum size of the variant it contains. Currently Expronicon and Unityper implements this as a special structure, which has a size larger than theoretical because there is no access to control the memory layout from Julia (and we probably shouldn't do it...)

My structs are a bit bigger than Expronicon's / Unityper's structs because I can't compactify at macroexpansion time, but IMO they're still quite small. It'd be great to go smaller though. I think the answer to this would be @generated structs.

The problem is when you want to support the namespace. I meant generating getproperty(::Type{MyADT}, name::Symbol) to support the namespace, which means you are overloading getproperty on DataType, and Julia Core and Base are not expecting that, e.g in Expronicon you can have

julia> using Expronicon.ADT: @adt

julia> @adt D begin
           D1
           D2(::Int)
       end

julia> D1
ERROR: UndefVarError: D1 not defined

julia> D.D1
D.D1

and

Also reserved names include a, b, var, and body. Though the list changes quite regularly, and you can mess up performance for other people quite badly by doing this, so it is very highly discouraged.

I've sidestepped this by overloading Base.adjoint on sum types:

julia> @sum_type Foo{T} :hidden begin
           A
           B{T}(::T)
       end

julia> A
ERROR: UndefVarError: A not defined

julia> B
ERROR: UndefVarError: B not defined

julia> Foo{Int}'.A
A::Foo{Int64}

julia> Foo'.B(1)
B(1)::Foo{Int64}

julia> let (; B) = Foo'
           B(1)
       end
B(1)::Foo{Int64}

[MasonProtter]

I'm actually still confused tbh why getproperty is so special? If you can overload adjoint, why we cannot overload getproperty?

So far as I understand

1. Methods for getproperty(::Type{T}, ::Symbol) already exist, unlike adjoint.
2. The compiler itself relies on specific behaviour and implementation of those methods, unlike adjoint.

I'll take a look at your solution to see how it supports this, thanks for sharing! We are thinking about a rewrite a MLStyle and hopefully we can have something first-class in MLStyle with all these mentioned above.

Yes, I would love to see a rewrite of MLStyle! Hopefully something that's more maintainable, I could never figure out what was going on inside it. If you have questions about how SumTypes works, let me know, I can try and write up the flow of stuff.

[MasonProtter]

I think it's a pretty clever solution but as I've been thinking about this issue more it seems like a good example of how the current tooling is falling short of clean and intuitive usage. We might need a new type but I'm not quite sure what it would look like.

Yes, I think there's a few reasons we should still want something like this natively supported in Base. Though, that said, I think if we got #49187 then I think almost everything we want could be done in a package.

[Tokazama]

I don't have a fully hashed out proposal but I'd like to see this approached piecewise, instead of just a raw implementation of an algebraic data type. Just off the top of my head, I thing we'd need something like ClosedUnion (where it's basically a union that lays everything out linearly and always includes a byte tag to avoid loading boxed pointers), NamedUnion to appropriately support dot operator access, and then you can easily create a algebraic data types that outside of Base that function the way described here.

[MasonProtter]

If we had NamedUnion what would be left to do in a package? That is a sum type (i.e. a disjoint union)

[Tokazama]

If people wanted to use the syntax where the declaration of the ADT/sum type also declares new types. I guess you could implement that in a separate package too, but I just assumed that since we have NamedTuple it would be natural to include it here.