Sum types as sealed abstract types

[CameronBieganek]

In the various discussions about sum types in Julia, I don’t recall seeing any discussion of how sum types would interact with the existing type system. So, here’s one idea that comes to mind:

Perhaps a sum type could be represented by a sealed abstract type, similar to sealed classes in Java, Scala, and Kotlin. A sealed abstract type would be an abstract type with a fixed list of subtypes that cannot be extended. Aside from being sealed, sealed abstract types would behave exactly the same as regular abstract types.

We already have a good amount of pattern matching via dispatch and argument destructuring, so using a sealed abstract type as a sum type could look something like this:

sealed abstract type Shape begin
    struct Rectangle
        w::Float64
        h::Float64
    end

    struct Square
        w::Float64
    end

    struct Triangle
        b::Float64
        h::Float64
    end
end

area((; w, h)::Rectangle) = w * h
area((; w)::Square) = w * w
area((; b, h)::Triangle) = b * h / 2

[kapple]

This is almost identical Moshi.Data.@data types in Moshi.jl, including the pattern matching using Moshi.Match.@match. Is there something different I’m not catching?

I think the main difference is that each struct is its own standalone type, but in Moshi you implement the overarching type as a union, which solves problems of e.g. getting performant inferred supertypes for collections. EDIT: Oh, I realise that your design could help get this performance as well, if Julia treats sealed abstract types appropriately.

using Moshi.Data: @data
using Moshi.Match: @match

@data Shape begin
    struct Rectangle
        w::Float64
        h::Float64
    end

    struct Square
        w::Float64
    end

    struct Triangle
        b::Float64
        h::Float64
    end
end

area(shape::Shape.Type) = @match shape begin
    Shape.Rectangle(; w, h) => w * h
    Shape.Square(; w) => w * w
    Shape.Triangle(; b, h) => b * h / 2
end

[Benny]

This concept surprises me. I didn’t expect the variants to be their own concrete subtypes (hence the ability to be unqualified annotations) of the sum type, I expected the sum type itself to be a concrete type for all its instances. The distinction between introducing a sealed abstract type or variants of a concrete sum type might not matter for type inference, I’m not sure.

The bigger issue to address is multiple sum type arguments. Just 2 Shapes needs 9 methods to be exhaustive, and mandatory multimethods is not fun to maintain unless it’s all written in the same place, in which case there’s no advantage over kapple’s 1 method with a @match block that can even enforce exhaustiveness while it’s evaluated at once. That’s not hypothetical, the original example actually mistakenly overwrote Rectangle and doesn’t specify anything specific or a fallback if we throw in a Triangle.

@kapple

I think the main difference is that each struct is its own standalone type, but in Moshi you implement the overarching type as a union

The @data Shape is actually a module, and there’s a lot of indirection e.g. Shape and Shape.Square are not the types of any instances, Shape.Type and another internal type for Square is. Presumably a sum type and perhaps its variants would be promoted to true Julia types as a builtin feature.

[Tortar]

I think WrappedUnions.jl and the more experimental package GitHub - matthijscox/UnionSplit.jl: Yet another union splitting macro package · GitHub provide some ideas to make a good builtin feature in my opinion. In practice having a wrapper of a union seems the simplest and more julian way to implement a sum type efficiently to me. Maybe if implemented at the language level there could be interesting improvements, not sure though, maybe it will just give more popularity to the technique

[CameronBieganek]

@kapple

This is almost identical Moshi.Data.@data types in Moshi.jl, including the pattern matching using Moshi.Match.@match. Is there something different I’m not catching?

The main idea is that a sealed abstract type (and its subtypes) fits more naturally into the existing type and dispatch system in Julia. Moshi is great, but as @Benny mentioned, a @data Shape is actually a module, and the variants do not have a useful public type (as far as I understand). Of course, that’s partly just a result of Moshi being a package rather than a core language feature.

@Benny

The bigger issue to address is multiple sum type arguments. Just 2 Shapes needs 9 methods to be exhaustive, and mandatory multimethods is not fun to maintain unless it’s all written in the same place, in which case there’s no advantage over kapple’s 1 method with a @match block that can even enforce exhaustiveness while it’s evaluated at once.

I’m not sure how important exhaustiveness is. All errors happen at runtime since Julia is a dynamic language. I’m not sure if the difference between ExhaustivenessError and MethodError is very important. (Ok, the story is more nuanced now with juliac.)

At any rate, having an additional match statement that could be used inside a single function, like in this PR, might be a useful alternative to writing method definitions. It would be similar to Haskell, where you can pattern match via multiple function definitions or via a single function with a case expression, like this:

-- Pattern matching via function definitions.
greetUser :: Maybe String -> String
greetUser Nothing         = "Welcome, Guest!"
greetUser (Just username) = "Welcome back, " ++ username ++ "!"

-- Pattern matching via a `case` expression.
greetUser :: Maybe String -> String
greetUser maybeName = case maybeName of
    Nothing       -> "Welcome, Guest!"
    Just username -> "Welcome back, " ++ username ++ "!"

@Tortar

I think WrappedUnions.jl and the more experimental package GitHub - matthijscox/UnionSplit.jl: Yet another union splitting macro package · GitHub provide some ideas to make a good builtin feature in my opinion.

One of these days I need to study WrappedUnions.jl more closely. From a very quick skim of the README, I don’t really understand how it works.

[Benny]

@CameronBieganek

I’m not sure how important exhaustiveness is. All errors happen at runtime since Julia is a dynamic language.

Julia doesn’t have an AOT compiler that nitpicks everything, but there are still errors that occur before a function is called. Parse errors, obviously, but macro expansions in the function definition as well. If anything, there’s a demand for detecting more obvious errors in static analysis and enforcing it for more “static” Julia, and the growing interest in sum types is coming from the same place. Typical dynamic Julia hasn’t needed sum types at all, runtime dispatch has been fairly manageable. It’s also worth pointing out that runtime MethodErrors aren’t usually desirable even then; nobody wants a handful of concrete type permutations out of thousands to halt the program, let alone that handful changing unpredictably across versions as scattered methods multiply.

To correct myself on something, exhaustiveness doesn’t need 9 methods, it just needs to address all 9 cases. A fallback ::Shape method could do that job. However, that would conflict with a method that takes all Shapes and holds something like kapple’s @match statement, so maybe there needs to be distinguishing syntax.

[penelopeysm]

There’s a difference between matching on a pattern (which is what Haskell does, and what the sum type packages try to copy), vs matching on a type (which is what Julia’s dispatch does). In the former

f <pattern1> = <expr1>
f <pattern2> = <expr2>
-- ...

each pattern is tried in turn, and the first one that matches wins. Indeed, the patterns need not be mutually exclusive. For example, the call f [1] [2] here fits all three patterns:

f :: [a] -> [b] -> Int
f (x:xs) ys     = 1
f xs     (y:ys) = 2
f xs     ys     = 3

main :: IO ()
main = do
    print $ f [1] [2] -- '1'

(you can run this online)

Conversely, with Julia methods, the most specific one wins, regardless of order of definition. And if you have method definitions like the above, that’s a method ambiguity.

IMHO, I think it’s important to not conflate the two. If we want something that behaves like the former, we shouldn’t use syntax that is meant for the latter.

[cshen]

I’ve had a lot of success using WrappedUnions.jl in OptParse.jl using the pattern of defining a generic

@wrapped struct Wrapped{U}
    union::U
end

Which you can then basically use as a dynamic “sealed” type that the compiler will exhaustively explore. I use it to allow for extensible error return types where I thread a union and expand it as it bubbles up and at the top level “make it sealed” by wrapping it up in a Wrapped. The compiler is able to infer the output of the type parameter and create an ad hoc “sealed” type.

[CameronBieganek]

@Benny

nobody wants a handful of concrete type permutations out of thousands to halt the program

I think this is overstated. Nobody would write out thousands of method definitions, just like nobody writes match statements with thousands of branches. Various combinations are combined simultaneously using wildcards, fallbacks, etc.

@Benny

let alone that handful changing unpredictably across versions as scattered methods multiply.

The methods would not be scattered, they would all be next to each other in the code (just like a match statement), because we are talking about sealed abstract types that behave like sum types, not open, extensible abstract types. So, the owner of the area function would implement all the applicable area methods for Shapes.

@penelopeysm

There’s a difference between matching on a pattern (which is what Haskell does, and what the sum type packages try to copy), vs matching on a type (which is what Julia’s dispatch does).

Yeah, that’s a good point, though I didn’t mean to imply that “pattern matching” via dispatch and argument destructuring is exactly equivalent to traditional pattern matching. I should have said a flavor of pattern matching. This flavor of pattern matching has the advantage that it already exists in the language right now. And I think it covers around 80% of typical pattern matching usage. But that might not be enough in Julia, because we’re greedy.

@penelopeysm

Conversely, with Julia methods, the most specific one wins, regardless of order of definition.

I think the fact that dispatch uses method specificity doesn’t matter too much for the “pattern matching” usage with sealed abstract types that I described, since as far as I can tell we would almost always be dispatching on the concrete variants, so specificity doesn’t come into play, like in the area example:

area((; w, h)::Rectangle) = w * h
area((; w)::Square) = w * w
area((; b, h)::Triangle) = b * h / 2

@penelopeysm

And if you have method definitions like the above, that’s a method ambiguity.

I agree that Haskell example wouldn’t work with Julia method definitions, though, as a nitpick, you wouldn’t get method ambiguities. What would happen is that each new method would overwrite the previous method. Here’s an approximately analogous example with Shapes:

julia> foo((; w)::Rectangle, s::Square) = 1
foo (generic function with 1 method)

julia> foo(r::Rectangle, (; w)::Square) = 2
foo (generic function with 1 method)

julia> foo(r::Rectangle, s::Square) = 3
foo (generic function with 1 method)

julia> methods(foo)
# 1 method for generic function "foo" from Main:
 [1] foo(r::Rectangle, s::Square)

If you want to have multiple “patterns” for a single variant, then you would just use a standard conditional inside the relevant ::Rectangle method, like this:

bar(r::Rectangle) = r.w > 10 ? "a" : "b"

Of course, if you combine dispatch and argument destructuring with if-else blocks inside methods, you get 100% of what you get from pattern matching. It’s just a question of whether it’s ergonomic enough.

[Mason]

@penelopeysm

Conversely, with Julia methods, the most specific one wins, regardless of order of definition. And if you have method definitions like the above, that’s a method ambiguity.

This is a bit of a sidenote, but I did actually write a little package long(!!) time ago exploring the idea of combining pattern matching with dispatch: GitHub - MasonProtter/PatternDispatch.jl: Extensible multiple-dispatch style pattern matching in julia · GitHub

Basically the idea is just that I had to decide on what sort of patterns are more specific than other sorts of patterns, and then I was able to write dispatch-like methods for pattern matching code.

This was mostly inspired by Mathematica’s approach to defining functions in terms of pattern matching.