Support for `Either` type in tact

[0kenx]

Tact should add support for Either TL-B type.

I propose we use the ? operator: TL-B Either X Y -> Tact X ? Y. If it's too confusing we could also use a more explicit syntax Either<X, Y>.

[anton-trunov]

Yes, this is needed to implement #322. I'd propose to use the pipe symbol | instead of ? because it's essentially a type analogue of logical disjunction and there won't be grammar conflicts with the optional type operator: https://github.com/tact-lang/tact/blob/da6a7f6e3eb56a20f5daafa84e50d095f923f3ba/src/grammar/grammar.ohm#L24.

We should also outline the concrete syntax for the constructors and destructors for the Either type.

To construct an expression of an Either type, we need two constructors, we can reuse the Left and Right names that TL-B borrows from Haskell, because it's more general than what, for instance, Rust does with Ok and Error.

To destruct an expression of an Either type, we need pattern-matching:

let foo: X | Y = ...;
match foo {
  Left(l) => {
    return 42;
  }
  Right(r) => {
    return 24;
  }
}

or, in Ohm.js-like notation:

StatementMatch ::= "match" Expression "{" ListOf<MatchClause, ","> ","? "}"

MatchClause ::= Pattern "=>" "{" Statement* "}"

// patterns can be nested
Pattern ::= Constructor ("(" NonemptyListOf<Pattern,","> ","? ")")?
        | TactIdentifier
        | "_"

...

This could be good enough for an initial implementation, later we could support things like | for grouping patterns, etc. The initial implementation does not have to support the general algebraic data types, just the Either type.

[0kenx]

The only problem I have with using | is that, in many languages with sum types, | is either straight away commutative, or implementation details are hidden well enough so developers can treat it as commutative.

TL-B on the other hand, makes a clear distinction with the selector bit. And because we want Tact code to interoperate with TL-B definitions, there's no way to abstract that implementation detail away.

[anton-trunov]

Well, because it is commutative. In the sense that you can always build an isomorphism between Either X Y and Either Y X.

[0kenx]

Yup, but serializing type X in Either X Y would result in 0b0xxxxxxxx, and serializing X in Either Y X would result in 0b1xxxxxxxx. If people take the type from FunC and change the order without realizing what is under the hood it would lead to errors.

[anton-trunov]

Yeah, that's a good point, but still more verbose syntax won't prevent this. I'm happy to change my opinion if you have a convincing concrete example, though

[novusnota]

We may come up with an or keyword (as in Either ... or ...). It won't describe the layout, but it also won't be confused with general ADTs (not nearly as much as | would).

let foo: X or Y = ...;

As a bonus it pairs nicely with as serialization modifier, introducing a stronger visual bond between left and right parts as opposed to | or comma in Either<..., ...>

More examples:

// Maybe of Eithers'
let foo: (X or Y)? = ...;

// Alternative Maybe of Eithers'
let foo2: X or? Y = ...;

// Either of Maybes'
let bar: X? or Y? = ...;

// Throwing as into the mix
let baz: (X as uint64 or Y as coins)? = ...;
let baz2: X as uint64 or? Y as coins = ...; // alternative maybe of eithers'

[Gusarich]

// Alternative Maybe of Eithers' let foo2: X or? Y = ...;

@novusnota what’s that in TL-B notation?

[novusnota]

@Gusarich Something like this, I guess:

// TL-B: Either X Y
let ex1: X or Y = ...; // just the Either

// TL-B: Maybe (Either X Y))
let ex2: X or? Y = ...; // Maybe of Either's, like here:
                        // https://github.com/ton-blockchain/ton/blob/140320b0dbe0bdd9fd954b6633a3677acc75a8e6/crypto/block/block.tlb#L155-L157

// TL-B: Either (Maybe X) (Maybe Y)
let ex3: X? or Y? = ...; // Either of Maybe's

// TL-B: Maybe (Either (Maybe X) (Maybe Y))
let ex4: X? or? Y? = ...; // Maybe of Either of Maybe's (inception!)

[anton-trunov]

@novusnota We should just allow ? to be used for any type, not only type idents, hence X or? Y becomes (X or Y)?

[Gusarich]

I tried to implement this, but I came across the fact that in the type ABITypeRef from @ton/core there is no way to define either type.

[novusnota]

Just remembered that Kotlin (the language we name in the first commandment of Tact) uses as for type casts. See "unsafe" cast operator and "safe" nullable cast operator in their docs.

I'm not saying that we should have type casts (we probably don't, except for our !! operator), but the general idea of as? looks reminiscent of my ideas of or? syntax prior.

But this is also fine:

We should just allow ? to be used for any type, not only type idents, hence X or? Y becomes (X or Y)?

[verytactical]

Yes, obviously unsafe type casts have no place in security/finance applications.

Maybe and Either types are boolean-blind and exist in functional programming languages mostly for implementation of generic libraries that do not care about semantics of stored values. Contracts are not generic, do care about semantics, and shouldn't use either Either or Maybe.

I understand how adding Either might sound simpler than full-fledged algebraic data types, but winging it here will degrade code quality of the whole Tact ecosystem in the long run, and in my opinion just isn't worth it.

[Gusarich]

@verytactical but the thing is that token standards have Either in their message schemas so we have to give a good way to define such structs.

Maybe we should add some flag for that, so that it's possible to strictly check which of the Either options was used during parsing?