What's the point of algebraic data types (Moshi.jl)

Type piracy is when you define a method for a function you do not own with a signature where none of types are owned by you. E.g. Base.show(::IO, ::Int). It’s a matter of discussion whether a parameter owned by you counts, e.g. is Base.show(::IO, ::Vector{MyType}) type piracy?

Although in your example your MyType only occurs as a parameter, it’s in the very special type Type, so few people would claim that’s type piracy.

I’m almost certain owning T doesn’t mean you own OtherModule.NotMyType{T}. Even the Julia docs discourage the practice: Style Guide · The Julia Language. Type is typically only an exception when implementing interface methods that require adding Type methods, such as eltype or IndexStyle.

Base specifically implements Base.show(::IO, @nospecialize(::Type)). Even if we consider implementing show(::IO, ::Type{MyType}) to not be type piracy, I believe it is inadvisable since it would invalidate anything that attempts to print a type.

It probably should have a different word from “piracy”, but the devs have been quite clear over the years that they do not want you to claim ownership of a dispatch signature just because you own one of the parameters, especially in the case of Type.

The only exception is functions that basically tell you that you should be overloading them based on a parameter because it’s a part of their interface (e.g. convert).

@jakobnissen That was a really good summary. Mechanically, I knew all of that, but I didn’t appreciate the implications. Thank you.

I assumed that Moshi.jl relied on union splitting in my original post, but it actually doesn’t. It explicitly introduces if branches, so it should work regardless of compiler heuristic:

julia> @macroexpand1(@match x begin
            x::Int=> 4
       end)|> MacroTools.striplines
quote
    var"##value#285" = x
    begin
        if var"##value#285" isa Int && begin
                    var"####TypeAnnotate#288#x#1" = var"##value#285"
                    true
                end
            var"##return#287" = let x = var"####TypeAnnotate#288#x#1"
                    4
                end
            @goto var"##final#286"
        end
    end
    (Base).error("matching non-exhaustive")
    (Base).@label var"##final#286"
    var"##return#287"
end

Answering my own question: Moshi.jl’s @match is unrelated to the ADT part, and could be turned into a separate package.

This leads me to wonder what is the difference between Moshi’s @match and MLStyle’s…

Author of Moshi.jl here, I came back 2 years later and I’m surprised how users of Moshi become a lot more than 2 years ago :grinning_face:

I think @ChrisRackauckas and @Mason already cover a wide range of answers, just to clarify a few things

When I wrote Moshi, I was trying to re-architect how MLStyle generates pattern-matching code into a more streamlined, proper compiler instead of ad hoc macros. This naturally leads to many fixes in the edge cases that I have already forgotten. There were some cases that we occasionally hit in MLStyle when we were trying to generate certain patterns or extend the pattern matching system. I don’t really remember the details anymore two years later, but overall, this is just trying to clean up the codebase that MLStyle was written on, which was making it hard to fix.

We kind of explored many different options in Julia, and union splitting seems to be the most reliable and performant solution to this. There were other packages back in the day, like LightSumtypes, Sumtypes, etc., that tried to tackle this problem from different angles. Looking back, I think we kind of have both.

The reason why Moshi’s ADT is in the same package with pattern matching is that our pattern matcher has first-class support for Moshi’s algebraic data type, which is why we don’t always rely on the compiler. That gives us the flexibility to fix certain performance issues across Julia versions when the compiler does not work as expected, or when you just want some more guarantee of how it works.

What I originally was planning for Moshi is something more ambitious.

Because in a static language like Rust, you can only pattern match in a very well-defined pattern; you cannot extend the pattern. But in Julia, it’s possible to extend the pattern dynamically in other packages.

So Moshi can just serve as a framework of pattern matching, instead of a single pattern matching package.


But TLDR: union is the only stable way to get the desired memory layout in Julia. This is why we generate the data type in a union, but we don’t always have to rely on union splitting if you’re using Moshi’s pattern matcher (just to clarify that).