Tagged Unions

[emil14]

Related to #747 #726 #725 and #749

Problem

Current way of dealing with unions is by checking their actual structure at runtime. TypeScript does the same thing (a pattern of adding kind/tag field manually for exactly that is somewhat common), but TS compiler has rather powerful type-inference (see e.g. type-guard feature), which isn't the case in Nevalang (original goal was to make it closer to Go in terms of simplicity). At the end of the day we 1) cannot follow Rust/Haskell like approach with pattern matching on unions because they are untagged (we don't know at runtime what union member it is) and 2) it's not clear if TS-way of doing things will work out for us.

Proposal

Proposal is to add some more type information to runtime. Specifically make unions tagged, so it's possible to use match/switch to do branching on union messages.

[emil14]

Tagged Unions + (As Is) Enums

After some thinking I've decided that

1. Unions should be tagged (Rust/Haskell-like)
2. We're not going to replace existing enums with unions that have just tags, because it feels unusual (I don't know language other than Rust that does this)

The last point is questionable depending on how this will affect match/switch functionality. If having only unions with their "tags-only" will allow to dramatically simplify their implementation or end-user API, then maybe we will go full Rust approach.

Anyway, here are some examples. Suppose you have Cat and Dog type.

type Cat struct {
    name string
    lives int
}

type Dog struct {
    name string
    barks bool
}

And you wanna have type Animal that is either Cat or Dog. Existing syntax looks like this

type Animal Cat | Dog

It's not perfect due to lack of = but let's keep that aside. The thing is - we need do add tags and existing syntax doesn't scale well (Haskell: data Result a = Ok a | Error String). Here are some variants based on Rust (but less noisy):

type Animal union {
    Cat(Cat)
    Dog(Dog)
}

type Animal union {
    Cat: Cat
    Dog: Dog
}

type Animal union {
    Cat Cat
    Dog Dog
}

Props and Cons:

1. First one resembles Rust
2. Second looks like struct/dict instance
3. Third looks like a struct definition and reflects existing syntax's clarity

Implementation Tips

1. Change syntax, keep everything as is (ignore tags)
2. Extend typesystem.UnionExpr with tags and fill them in parser
3. In analyzer/typechecker (validator?) check that tags are unique
4. Make changes to type-compatibility algorithm - check how this works in other languages with tagged unions. My guess is that order doesn't matter any longer and what matters is tags of union members.
5. Update all *.neva files and parser tests to use new syntax
6. Create new runtime.Msg type Union of shape struct { tag uint8, data Msg }

---

Last step will allow to implement pattern matching on tagged unions (not sure what's the API and implementation for that though)

[emil14]

Just an example of perfectly designed pattern matching on tagged union via switch

type Entity union {
    Type TypeEntity
    Const ConstEntity
    Component ComponentEntity
    Interface InterfaceEntity
}

def ValidateEntity(entity Entity) (err error) {
    handle_type HandleType?
    handle_const HandleConst?
    handle_component HandleComponent?
    handle_interface HandleInterface?
    ---
    :entity -> switch {
        Type -> handle_type
        Const -> handle_const
        Component -> handle_component
        Interface -> handle_interface
    }
}

Match looks similarly

def GetEntityCode(entity Entity) (code int) {
    :entity -> match {
        Type: 1
        Const: 2
        Component: 3
        Interface: 4
    } -> :code
}