MEP 13. Algebraic Data Types and Match

Field	Value
MEP	13
Title	Algebraic Data Types and Match
Author	Mochi core
Status	Draft
Type	Standards Track
Created	2026-05-08

Abstract

Mochi has product types (structs) and sum types (tagged unions). The grammar accepts both. Pattern matching is checked for exhaustiveness on a union scrutinee (T050) and for irredundancy on any scrutinee (T054). This MEP documents the typing rules and lists the fixtures that pin each obligation.

Motivation

A union with an unchecked match was the single largest class of type error that Mochi used to catch at runtime instead of at compile time. MEP-10 A4 closed the exhaustiveness half. MEP-13 closes the irredundancy half (an arm that cannot fire because an earlier arm subsumes it) and pins every shape of the struct- and union-typing surface with a dedicated fixture.

Status at a glance

Item	Status
Struct decl, literal, field access typing	closed
Struct literal with missing field (T053)	closed
Struct literal with unknown field (T026)	closed
Union decl, variant constructor typing	closed
Variant constructor arity / field type mismatch	closed
Match result-type unification (MEP-5 [T-Match])	closed
Match exhaustiveness on union scrutinees (T050)	closed (MEP-10 A4)
Wildcard _ covers remaining variants	closed
Match irredundancy (duplicate / unreachable arms)	closed (T054)
Recursive variants (type List = Cons(... List) | Nil)	closed
Generic ADTs (type List<T> = ...)	deferred (depends on MEP-12)

Specification

Surface

Mochi has two ADT shapes.

Product types: structs.

type Point {
  x: int
  y: int
}

Sum types: tagged unions.

type Shape =
  Circle(r: float)
| Square(side: float)
| Rect(w: float, h: float)

Aliases:

type Id = int
type Name = string

The surface is documented in MEP 2 (grammar) and MEP 3 (AST). This MEP focuses on typing and pattern matching obligations.

Struct typing (closed)

Status. Closed. A struct declaration introduces:

• A StructType in the type environment under the declared name (types/check.go around the case s.Type != nil walk, lines around 859-925).
• A constructor of type fun(field1: T1, ...): Name accessed as the type name in expression position.
• A struct literal form Name{field1: e1, field2: e2}. Order is flexible; the literal matches by field name.

Rules:

• All fields must be present in a literal. Omitted fields raise T053 (struct literal missing required field). There are no field defaults.
• An unknown field name in a literal raises T026. A field value whose type does not unify with the declared field type raises T008.
• Field access s.f requires s : StructType{...} containing f. Otherwise T026 (unknown field) or T027 (not a struct).

Methods (type T { fun foo(...) }) attach to the struct via the Methods map and become callable as t.foo(...). The receiver is implicit; the second-pass method walk in the same code path inserts the field names and sibling methods into the method env.

Pinning fixtures. tests/types/valid/struct_field_access.mochi (literal + access flow), tests/types/valid/user_types_basic.mochi, tests/types/valid/user_type_selector.mochi, tests/types/valid/nested_type_decl.mochi; tests/types/errors/struct_unknown_field_access.mochi, tests/types/errors/user_type_field_mismatch.mochi, tests/types/errors/not_struct_selector.mochi, tests/types/errors/struct_literal_missing_field.mochi, tests/types/errors/struct_literal_missing_fields_two.mochi, tests/types/errors/struct_literal_unknown_field.mochi.

Union typing (closed)

Status. Closed. A union declaration introduces:

• A UnionType{Name, Variants, Order} in the env (definition at types/kinds.go:169).
• One constructor function per variant. Circle(r: float) : Shape.
• Each variant is also a StructType under its name with the variant's fields, so let c: Circle = Circle(1.0) parses but the canonical type is Shape.

The variants map is shared during the type decl walk so a variant can reference the union it belongs to. type List = Cons(head: int, tail: List) | Nil resolves cleanly.

Rules:

• A variant constructor must be called with the declared arity. Mismatch is T008 (the constructor signature does not unify with the call).
• A variant constructor must be called with matching field types. Same error path.
• A bare variant name (no parens) in expression position is rejected at the type checker because the constructor has function type.

Pinning fixtures. tests/types/valid/match_union_variant.mochi, tests/types/valid/union_alias.mochi, tests/types/errors/match_variant_arity.mochi, tests/types/errors/union_constructor_field_type.mochi (wrong field type, T008), tests/types/errors/union_constructor_too_many_args.mochi (over-arity, T006).

Follow-up. A recursive_list_length fixture would pin the shared-variants resolution path.

Match typing

match e { p1 => r1, ..., pn => rn }.

Pattern shapes accepted today:

• Literal: 1, "x", true, false. Matches by equality. Binds nothing.
• Identifier: matches anything, binds the name in the arm body.
• Underscore: matches anything, binds nothing.
• Variant call: Circle(r), Rect(w, h). Matches a value of the named variant and binds field positions to the listed identifiers. The number of bindings must match the variant arity.

Result type (closed). MEP-5 [T-Match] requires every arm's result type to unify with the principal type. checkMatchExpr in types/check_expr.go (around lines 1138-1226) enforces this and emits T008 on heterogeneous arms. Pinning fixtures: tests/types/valid/match_expr.mochi, tests/types/valid/match_literal_pattern.mochi, tests/types/errors/match_result_mismatch.mochi, tests/types/errors/match_pattern_mismatch.mochi.

Exhaustiveness (closed, T050)

Status. Closed. checkMatchExpr walks the arms, marks each named variant as covered (call form V(args) via matchedVariants[call.Func] = true, bare-ident form via the lookup at the same site), and notes any wildcard _ arm with hasCatchAll. After the arms loop, the missing-variant set is computed against UnionType.Order. If any variant remains uncovered and there is no catch-all, the match is rejected with T050.

error[T050]: non-exhaustive match on union `Shape`: missing variant(s) `Triangle`

The diagnostic helper is errMatchNonExhaustive at types/errors.go:290, which renders the missing names as a comma-separated list with and before the last item.

Pinning fixtures. tests/types/valid/match_union_exhaustive_wildcard.mochi, tests/types/errors/match_missing_variant.mochi (single missing), tests/types/errors/match_missing_variants_two.mochi (two missing, X and Y format), tests/types/errors/match_missing_variants_three.mochi (three missing, Oxford-comma format).

Irredundancy (closed, T054)

Status. Closed. checkMatchExpr rejects three shapes of redundant arm with T054:

• A variant pattern that names a variant already covered by an earlier arm. Detected at the same site that sets matchedVariants[v] = true; the second visit fires the error.
• A literal pattern that repeats one already seen in an earlier arm. The literalPatternKey helper canonicalises the literal to a string key (int:N, str:"...", bool:true, etc.) so the duplicate check is a map lookup.
• An arm that follows a catch-all (wildcard _ or bare-identifier catch-all). The check runs at the top of every arm walk: if hasCatchAll is already true, the arm is unreachable.

Mochi does not have pattern guards, so a duplicate pattern can never fire on a different predicate; there is no case x => x > 0 form that would let two arms with the same head pattern both be live.

Pinning fixtures. tests/types/errors/match_redundant_variant.mochi, tests/types/errors/match_redundant_literal.mochi, tests/types/errors/match_arm_after_wildcard.mochi.

Recursive ADTs (closed)

Status. Closed. The shared variants map in the union decl walk (types/check.go around lines 926-960) means a variant body can resolve a type reference to the union it belongs to. The same path is used for both type Tree = Leaf | Node(...) and type List = Cons(head: int, tail: List) | Nil. A recursive function over the list type-checks; an exhaustiveness gap on the recursive type is caught by T050 the same way as on a flat union.

Pinning fixtures. tests/types/valid/recursive_list_length.mochi (valid, defines length recursively over Cons | Nil); tests/types/errors/recursive_list_missing_nil.mochi (error, T050 catches the missing terminator arm).

Generic ADTs (deferred)

The grammar does not support type List<T> = Cons(head: T, tail: List<T>) | Nil today. The required pieces:

• Generic type declaration syntax (parser change).
• Generic constructor types parameterised by the type parameters (FuncType already supports this through the polymorphism work).
• Generic match patterns that accept a type argument list at the variant call (or infer it from the scrutinee).

We mark this as deferred. The parser change is non-trivial and MEP 12 (polymorphism) needs to land first.

Rationale

Match exhaustiveness is the textbook benefit of sum types. It landed under MEP-10 A4. Irredundancy is the remaining textbook half: redundant arms hide bugs, since the redundancy means the author thought a different value would arrive than the type can actually carry.

Recursive types are necessary for any non-trivial use of unions. The shared-variants resolution path already supports them; the only missing piece is the fixtures that pin the support.

We defer generic ADTs because they require both grammar and inference work. MEP-12 needs to land first.

Backwards Compatibility

Exhaustiveness already shipped. Irredundancy rejection is a breaking change, but a small one: the redundant arms it now rejects could never have fired in the first place.

Reference Implementation

• types/kinds.go:169, UnionType{Name, Variants, Order}.
• types/check.go case s.Type != nil walk (around lines 859-960), struct and union construction. Union decls use a shared variants map so recursive references resolve correctly during the walk.
• types/check_expr.go around line 615, struct literal walk, completeness check (T053).
• types/check_expr.go around lines 1138-1240, checkMatchExpr: arm walk, matchedVariants map, hasCatchAll flag, seenLiterals map, irredundancy emits (T054), and the post-loop T050 emit against UnionType.Order.
• types/check_expr.go literalPatternKey, canonical string key for literal pattern equality.
• types/errors.go, errMatchNonExhaustive (T050), errStructMissingField (T053), errMatchArmRedundant (T054) formatters.

Open Questions

• Pattern guards. case x => x > 0. Out of scope; revisit if the test surface demands it.
• Or-patterns. Circle(_) | Square(_) => .... Useful for catch-some-but-not-all cases. Defer.
• Nested patterns. Cons(1, _) over recursive types. Already partially supported; needs fixtures alongside the recursive-ADT pinning.

References

• Benjamin C. Pierce, Types and Programming Languages, chapters 11 and 20.
• Luc Maranget, "Compiling pattern matching to good decision trees", 2008.

Copyright

This document is placed in the public domain.