Sum types, 2025 variant

[Araq]

Sum types, 2025 variant

We tweak case inside objects to offer:

• Type safety: field accesses are checked entirely at compile time.
• Conciseness: The duplication of enum field declarations and their usage in case objects is removed.
• Conciseness: Constructing an instance of a sum type is shorter: BinaryOpr(a: a, b: b) instead of Node(kind: BinaryOpr, a: a, b: b).
• Pattern matching.

This year's proposal accomplishes all of the above with a simple syntactic tweak of the existing case objects.
The "discriminator" can now be left out. If it is left out, the entire object is a so called "new style case object".

type
  Node = ref object
    case
    of AddOpr, SubOpr, MulOpr, DivOpr:
      a, b: Node
    of UnaryOpr:
      a: Node
    of Variable:
      name: string
    of Value:
      val: int
    # "shared" fields are directly supported:
    info: LineInfo

The "branch names" (e.g. AddOpr, UnaryOpr, etc.) are used
for construction and pattern matching.

Construction

Construction is done with the syntax Branch(fieldNameA: valueA, fieldNameB: valueB, ...). (A shortcut
for this should be added later, in a separate proposal that affects all object types!)

To access the attached values, pattern matching must be used. This enforces correct access at compile-time.

Pattern matching

The syntax of BranchName(fields...) is used for pattern matching:

proc traverse(n: Node) =
  case n
  of {AddOpr, SubOpr, MulOpr, DivOpr}(a, b):
    traverse a
    traverse b
  of UnaryOpr(a):
    traverse a

  of Variable(name):
    echo name
  of Value(x):
    counter += x

Whether the local variables (a, b, name, x in the above example) are mutable or not depends on the
mutability of expression that is being matched:

  var x = Some(90)
  case x
  of Some(y):
    y = 180 # writes to `x`
  of None:
    echo "no value"

Serialization

As before, traverse the type's AST in a macro to generate the store and load procedures. No special
additions are included in this proposal.

Future directions

• Allow object construction to leave out the field names: MyObject(1, 2) instead of MyObject(a: 1, b: 2).
• Allow for a case type to be written outside of an object and allow field names to be left out:

type
  Option[T] =
    case
    of Some: T
    of None: discard
  Either[A, B] =
    case
    of Left: A
    of Right: B

Would be short for:

type
  Option[T] = object
    case
    of Some:
      _: T
    of None:
      _: discard
  Either[A, B] = object
    case
    of Left:
      _: A
    of Right:
      _: B

[walkr]

Can't the case keyword for new style objects be dropped entirely from the type definition and only be used on matching?

type
  Option[T] = object
    of Some: T
    of None: discard

  Either[A, B] = object
    of Left: A
    of Right: B

[Araq]

Yes. But does it help?

[arnetheduck]

For completeness:

  if n.{AddOpr, SubOpr, MulOpr, DivOpr}(a, b):
    traverse a
    traverse b
  elif n.UnaryOpr(a) and a != nil:
    traverse a
  else:
    echo "bingo!"

This is useful in lots of cases, ie early returns etc:

   if myOpt.Some(a):
     return a
   ...

Implementation-wise, for ref object each branch should hopefully be similar to a subtype such that the branches don't take up too much space, ie:

 type
  Node = ref object
    case
    of BigArray:
      a: array[1024, int]
    of Int:
      a: int

An Int node should see a 16-byte allocation above (8 for the int and 8 for the vtable) - this will solve lots of pointless inefficiency in types like JsonNode for example.

[walkr]

Yes. But does it help?

@Araq Yes, I believe it helps keep the type definition simpler & symmetric, which in turn reduces the mental effort for polyglot developers switching between multiple languages.

Plus, why not prefer a simpler, more elegant solution when it introduces no ambiguity?

• Rust

enum Option<T> {
    Some(T),
    None,
}

• F#

type Option<'T> =
    | Some of 'T
    | None

• Swift

enum Option<T> {
    case some(T)
    case none
}

• Nim

type
  Option[T] = object
    of Some: T
    of None: discard

[Araq]

Shrug. These "polyglot developers" are never happy anyway.

[khaledh]

This looks promising. I've been waiting for sum types for a while :) I have a few questions though.

1. For the proposed sum types, will it be possible to pattern match nested objects? e.g.

proc traverse(n: Node) =
  case n
  of UnaryOpr(Variable(name)):
    echo "unary op against variable"
  ...

2. Will it be possible to pattern match against constant expressions (e.g. literals, enum values, etc)?

case node:
of Variable("x"):  # <-- only matches if the variable name is x
  ...

3. Will it be possible to ignore some elements of the match pattern? e.g.

case node:
of BinaryOp(_, b):  # <-- mainly to avoid introducing unused variables
  ...

4. One feature I miss from Elixir is partial destructuring with assignment. Not sure how feasible it would be though. Consider this example:

type
  Node = ref object
    case
    of BinaryOpr:
      opr: string
      a, b: Node
    of UnaryOpr:
      opr: string
      a: Node
    of Variable:
      name: string

proc traverse(n: Node) =
  case n
  of BinaryOpr(opr) = binopr:  # <-- capture only the opr field, and also assign the whole thing to binopr
    checkBinaryOpr(opr)
    traverseBinaryOpr(binopr)
  ...

Also on the related topic of pattern matching, is there a plan to provide built-in structural pattern matching? e.g.

let t = (1, "a")

case t:
of (x, "a"):
  echo "Match a with x = ", x  # this match wins since it comes first
of (1, y):
  echo "Match 1 with y = ", y
else:
  echo "No match"

Thanks!

[Araq]

@khaledh Yeah most of your examples will work and there will be "guards" for more comparisons etc. But that's all boring stuff that we figured out long ago. The sum type design itself was the hard one.

Also on the related topic of pattern matching, is there a plan to provide built-in structural pattern matching? e.g.

You can do this in today's language, read https://nim-lang.org/docs/manual.html#macros-case-statement-macros

[xigoi]

I definitely prefer case of over object of, it feels more consistent. Most languages that have both product and sum types use different keywords for them.

[bpr]

This proposal is really growing on me. On the syntax, I favor fewer keywords. It's not that it helps, but here it doesn't hurt, so all things being equal (are they?) shorter is better. I also like case of instead of object of. What I think I would like more is using enum instead of either and dropping the of, like Rust

type
  Option[T] = enum
    Some: T
    None: discard

[mrgaturus]

i think we need make the type syntax it's own thing because the usage through pattern matching and the construct using some of the branches make it very different of a regular object.

something like case object could do the trick

type
  Option[T] = case object
    of None: discard
    of Some: 
      value: T

type
  Node = ref case object
    of AddOpr, SubOpr, MulOpr, DivOpr:
      a, b: Node
    of UnaryOpr:
      a: Node
    of Variable:
      name: string
    of Value:
      val: int
    # "shared" fields are directly supported:
    info: LineInfo

[Araq]

Implementation-wise, for ref object each branch should hopefully be similar to a subtype such that the branches don't take up too much space, ie ...

Hard to implement but I see the value and never considered it. When we keep this in mind for the first impl this should be doable. Thanks!

[planetis-m]

It is not clear to me how binary serialization is supposed to work now that the kind field is hidden.

[Araq]

You generate code like:

proc store(s: Stream; x: Sum) =
  case x
  of BinaryOpr(a, b):
    s.writeByte 1u8
    store s, a
    store s, b
  of UnaryOpr(a):
     s.writeByte 2u8
  ...

[McChuck05]

I know it's asking a lot, but do you think we could eventually get two separate use cases?

• dispatch on enum value (current plan)
• dispatch on (sub)type

# generic example
type
  EnumEither1[A, B] = object 
  # Current plan, slightly modified
  # Named fields required
    case enum
    of Left:  lVal: A
    of Right:  rVal: B
  # let a: EnumEither1[int, string] = Left(lval: 2)

  EnumEither2[A, B] = object
  # Planned expansion, slightly modified
  # Named fields allowed but not required
    case enum
    of Left: A
    of Right: B
  # let b: EnumEither2[int, string] = Right("hello")

  TypedEither[A, B] = object
  # My request
  # Named fields forbidden
    case type
    of A
    of B
  # let c: TypedEither[int, string] = "Hello!"

# practical example

type
  EnumIndex = object
    case enum  
    of Forwards:  fVal: int
    of Backwards:  bVal: BackwardsIndex
    # common fields supported outside the case

  TypedIndex = object
    case type  
    of int
    of BackwardsIndex
    # common fields supported outside the case

proc `[]`[T](target: openArray[T], idx: EnumIndex): T = 
  var where: int
  case idx
  of Forwards: 
    where = idx.fval
  of Backwards:
    where = len(target) - int(idx.bval)
  if where < 0 or where >= len(target): 
    raise newException(IndexDefect, "Index out of bounds: [" & $idx & "]")
  else:
    return target[where]

proc `[]`[T](target: openArray[T], idx: TypedIndex): T = 
  var where: int
  case idx
  of int: 
    where = idx
  of BackwardsIndex:
    where = len(target) - int(idx)
  if where < 0 or where >= len(target): 
    raise newException(IndexDefect, "Index out of bounds: [" & $idx & "]")
  else:
    return target[where]

let thing = @[1, 2, 3, 4]

var there: EnumIndex
there = forwards(fval: 0)
assert thing[there] == 1
there = backwards(bval: ^1)
assert thing[there] == 4

var here: TypedIndex
here = 0
assert thing[here] == 1  
here = ^1
assert thing[here] == 4

[Araq]

It feels you don't actually care about "dispatch on subtype" but you want implicit conversions between A, B and Either[A, B]. You can use a converter for these but it's a bad idea.