Tagged Unions and Algebraic Data Types

Session 145 brought a concept from the academic world of programming language theory into FLIN, a language designed for pragmatic application development: algebraic data types.

The name sounds intimidating. The concept is simple. An algebraic data type is a type that can be one of several variants, where each variant can carry different data. A network request result is either a success with a response body, or a failure with an error message. A list element is either a value followed by more list, or the end of the list. A JSON value is either a string, a number, a boolean, null, an array, or an object.

In FLIN, these are called tagged unions, and they are declared with the enum keyword.

From Simple Enums to Tagged Unions

FLIN already had simple enums before Session 145:

enum Status {
    Pending,
    Active,
    Completed
}

A simple enum is a type with named variants and no associated data. Status.Pending is a value. Status.Active is a different value. You can match on them, compare them, store them. But they are just labels.

Tagged unions extend enums with associated data:

enum Message {
    Quit,
    Move(int),
    Write(text)
}

Now Quit carries no data, Move carries an int (a distance, perhaps), and Write carries a text (a message body). Each variant is a different shape. The tag -- Quit, Move, Write -- tells you which shape you have, and pattern matching lets you access the data inside.

Generic Tagged Unions

The real power comes from combining tagged unions with generics:

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

enum Result { Ok(T), Err(E) } ```

Option is a type that is either Some(42) or None. Result is a type that is either Ok(42) or Err("something went wrong"). These two types alone handle the vast majority of nullable values and error handling in any application.

The generic parameter T in Option is not a concrete type -- it is a placeholder. When you write Option, the compiler substitutes T = int throughout the enum definition. Some(T) becomes Some(int). When you write Option, Some(T) becomes Some(text).

Constrained Generic Enums

Session 145 also added support for trait-constrained type parameters on enums:

enum Container<T: Comparable> {
    Empty,
    Single(T),
    Multiple([T])
}

The constraint T: Comparable means that Container can only be instantiated with types that implement the Comparable trait. Container is valid (int is comparable). Container is valid only if there is an impl Comparable for User.

The AST Implementation

Session 145 modified the AST in three key places.

First, Stmt::EnumDecl gained a type_params field:

Stmt::EnumDecl {
    name: String,
    type_params: Vec<TypeParam>,  // NEW: <T, E>, <T: Comparable>
    variants: Vec<EnumVariant>,
    visibility: Visibility,
    span: Span,
}

The TypeParam struct carries both the parameter name and optional constraints:

pub struct TypeParam {
    pub name: String,
    pub constraints: Vec<String>,  // trait names
}

Second, EnumVariant already had an Option for associated data, but Session 145 made that field interact correctly with type parameters:

pub struct EnumVariant {
    pub name: String,
    pub data_type: Option<Type>,  // None for Quit, Some(Type::Int) for Move(int)
}

When parsing a variant like Ok(T), the parser recognizes T as a type parameter (not a concrete type) because it is in the type_params scope.

Third, a new pattern variant was added for matching enum variants:

Pattern::EnumVariant {
    enum_name: String,
    variant: String,
    inner: Option<Box<Pattern>>,
    span: Span,
}

Parser Changes

The parser needed two modifications. First, parse_enum_decl was extended to parse type parameters after the enum name:

fn parse_enum_decl(&mut self) -> Result<Stmt, ParseError> {
    self.expect_keyword("enum")?;
    let name = self.expect_identifier()?;
    let type_params = self.parse_type_params()?; // NEW

self.expect(&Token::LeftBrace)?; let mut variants = vec![]; while !self.check(&Token::RightBrace) { variants.push(self.parse_enum_variant_with_params(&type_params)?); self.optional_comma(); } self.expect(&Token::RightBrace)?;

Ok(Stmt::EnumDecl { name, type_params, variants, visibility, span }) } ```

Second, a new function parse_enum_variant_with_params was added to handle variant data types that reference type parameters:

fn parse_enum_variant_with_params(
    &mut self,
    type_params: &[TypeParam],
) -> Result<EnumVariant, ParseError> {
    let name = self.expect_identifier()?;
    let data_type = if self.match_token(&Token::LeftParen) {
        let param_names: Vec<&str> = type_params.iter().map(|p| p.name.as_str()).collect();
        let data = self.parse_type_with_params(&param_names)?;
        self.expect(&Token::RightParen)?;
        Some(data)
    } else {
        None
    };
    Ok(EnumVariant { name, data_type })
}

The parse_type_with_params function knows which identifiers are type parameters, so T in Ok(T) is parsed as Type::TypeParam("T") rather than Type::Named("T").

Type System Extension

The FlinType::Enum variant was extended to carry type parameters and typed variant data:

FlinType::Enum {
    name: String,
    type_params: Vec<String>,
    variants: Vec<(String, Option<Box<FlinType>>)>,
}

Before Session 145, variants were just Vec -- names without data types. After Session 145, each variant carries an optional FlinType for its associated data.

When the type checker registers an enum declaration, it converts the AST representation to FlinType:

fn register_enum(&mut self, decl: &Stmt) {
    let Stmt::EnumDecl { name, type_params, variants, .. } = decl else { return };

let flin_variants: Vec<(String, Option>)> = variants .iter() .map(|v| { let data = v.data_type.as_ref().map(|t| { Box::new(FlinType::from(t)) }); (v.name.clone(), data) }) .collect();

let param_names: Vec = type_params.iter().map(|p| p.name.clone()).collect();

self.type_env.insert( name.clone(), FlinType::Enum { name: name.clone(), type_params: param_names, variants: flin_variants, }, ); } ```

Variant Construction

Creating a variant value uses function-call-like syntax:

result = Ok(42)
option = Some("hello")
message = Move(10)
status = Completed

Variants with data look like function calls. Variants without data are bare identifiers. The parser distinguishes them by checking whether parentheses follow the variant name.

In the type checker, variant construction is validated against the enum definition:

fn check_variant_construction(
    &mut self,
    enum_name: &str,
    variant_name: &str,
    args: &[Expr],
) -> FlinType {
    let enum_def = self.resolve_enum(enum_name);

let variant = enum_def.variants.iter() .find(|(name, _)| name == variant_name);

match variant { Some((_, Some(expected_data))) => { if args.len() != 1 { self.report_error("variant expects exactly one argument"); } else { let arg_type = self.infer_type(&args[0]); if !self.types_compatible(expected_data, &arg_type) { self.report_error("variant data type mismatch"); } } } Some((_, None)) => { if !args.is_empty() { self.report_error("variant takes no arguments"); } } None => { self.report_error(&format!("unknown variant: {}", variant_name)); } }

FlinType::Enum { name: enum_name.to_string(), / ... / } } ```

Pattern Matching on Tagged Unions

The primary way to work with tagged unions is pattern matching:

fn handle_result(result: Result<int, text>) -> text {
    match result {
        Ok(value) -> "Success: " + text(value)
        Err(msg) -> "Error: " + msg
    }
}

The pattern Ok(value) does three things:

1. Tag check: Verifies the runtime tag is Ok 2. Data extraction: Extracts the associated data 3. Binding: Binds the data to the name value

Inside the arm body, value has the type int -- derived from Result's Ok(T) where T = int.

The type checker handles enum variant patterns:

fn check_enum_variant_pattern(
    &mut self,
    pattern: &Pattern,
    enum_type: &FlinType,
) {
    let Pattern::EnumVariant { variant, inner, .. } = pattern else { return };
    let FlinType::Enum { variants, type_params, .. } = enum_type else { return };

let variant_def = variants.iter().find(|(name, _)| name == variant);

match (variant_def, inner) { (Some((_, Some(data_type))), Some(inner_pattern)) => { // Bind inner pattern with the data type self.check_pattern(inner_pattern, data_type); } (Some((_, None)), None) => { // No data variant, no inner pattern -- OK } (Some((_, Some(_))), None) => { self.report_error("variant has data but pattern does not destructure it"); } (Some((_, None)), Some(_)) => { self.report_error("variant has no data but pattern tries to destructure"); } (None, _) => { self.report_error(&format!("unknown variant: {}", variant)); } } } ```

Real-World Usage Patterns

Tagged unions are not an academic curiosity. They model real application patterns.

Error Handling

enum ApiResult<T> {
    Success(T),
    NotFound,
    Unauthorized,
    ServerError(text)
}

fn fetch_user(id: int) -> ApiResult { // ... API call ... }

match fetch_user(42) { Success(user) -> render_profile(user) NotFound -> show_404() Unauthorized -> redirect_to_login() ServerError(msg) -> show_error(msg) } ```

Every possible outcome is a variant. The compiler ensures every call site handles every outcome.

State Machines

enum ConnectionState {
    Disconnected,
    Connecting(text),
    Connected(Socket),
    Error(text)
}

fn render_status(state: ConnectionState) -> text { match state { Disconnected -> "Not connected" Connecting(host) -> "Connecting to " + host + "..." Connected(socket) -> "Connected to " + socket.host Error(msg) -> "Error: " + msg } } ```

The state machine is the type. Transitions between states are assignments of different variants. The compiler ensures you handle every state.

Recursive Data Structures

enum JsonValue {
    Null,
    Bool(bool),
    Number(number),
    Text(text),
    Array([JsonValue]),
    Object([text: JsonValue])
}

A JSON value is either null, a boolean, a number, a string, an array of JSON values, or an object mapping strings to JSON values. This recursive definition captures the entire JSON specification in six lines.

Test Results

Session 145 added six new integration tests:

1. test_e2e_tagged_union_simple_enum -- basic enum without data 2. test_e2e_tagged_union_with_data -- Message with variant data 3. test_e2e_tagged_union_generic_enum -- Option with generic parameter 4. test_e2e_tagged_union_generic_result -- Result with two parameters 5. test_e2e_tagged_union_constrained_generic -- Container 6. test_e2e_tagged_union_pub_enum -- public visibility enum

Total test count went from 1,782 to 1,788. All existing tests continued to pass.

Files Modified

Session 145 touched seven files:

The changes were surgical. Most files needed only a few lines added or modified. This is because the infrastructure -- generic type parameters, pattern matching, the type checker framework -- already existed. Tagged unions were the feature that connected those pieces.

Design Decisions

Parentheses for variant data, not braces. We chose Ok(42) over Ok { value: 42 }. Parentheses are shorter and more familiar (Rust uses the same syntax). Braces suggest a struct, which is a different concept. Parentheses suggest a constructor, which is closer to what variant creation actually is.

Single data value per variant. Each variant carries at most one value. For multiple values, use a tuple or an entity. This keeps the syntax simple: Move(int) rather than Move(int, int). If you need two values, use Move((int, int)) with a tuple.

Type parameters on the enum, not on variants. The type parameters belong to the enum declaration: enum Result, not enum Result { Ok(T), Err(E) }. This follows Rust's convention and keeps the variant syntax clean.

Exhaustiveness is mandatory. Every match on a tagged union must cover every variant. There is no default escape hatch for enums. If you add a variant, every match must be updated. This is a deliberate choice for safety over convenience.

The Algebraic Type Theory

The name "algebraic data type" comes from a mathematical analogy. A tagged union is a sum type -- the total number of possible values is the sum of the possible values of each variant. Option has three values: Some(true), Some(false), and None. That is 2 + 1 = 3.

An entity (or struct) is a product type -- the total number of possible values is the product. An entity with a bool field and an int field has 2 * 2^64 possible values.

Together, sum types and product types give you the "algebra" of algebraic data types. You can compose them to describe any data shape: sums of products, products of sums, recursive types, generic types.

FLIN does not require developers to know this theory. But the theory explains why tagged unions are so powerful -- they are the missing half of the type algebra. Without them, you can describe records (products) but not alternatives (sums). With them, you can describe everything.

Session 145 gave FLIN the full algebra. The language's type system was now complete in the theoretical sense: it could describe any data shape that a developer might need. The remaining sessions -- destructuring, pipeline operators, while-let loops -- were ergonomic features built on top of this complete foundation.

---

This is Part 36 of the "How We Built FLIN" series, documenting how a CEO in Abidjan and an AI CTO designed and implemented a programming language from scratch.

Series Navigation: - [34] Traits and Interfaces - [35] Pattern Matching: From Switch to Match - [36] Tagged Unions and Algebraic Data Types (you are here) - [37] Destructuring Everywhere - [38] The Pipeline Operator: Functional Composition in FLIN