pattern-matching

name	pattern-matching
description	Expert skill for implementing pattern matching including exhaustiveness checking, decision tree compilation, and efficient match dispatch code generation.
allowed-tools	Read, Write, Edit, Bash, Glob, Grep
graph	{"domains":["domain:software-engineering"],"specializations":["specialization:programming-languages"],"skillAreas":["skill-area:compiler-implementation","skill-area:language-design"],"roles":["role:backend-engineer"]}

Pattern Matching Skill

Implement pattern matching for programming languages including exhaustiveness checking, usefulness analysis, and efficient compilation to decision trees.

Capabilities

• Parse pattern syntax (constructor, wildcard, binding, literals)
• Implement exhaustiveness and usefulness checking
• Compile patterns to decision trees
• Implement guard clause handling
• Design or-patterns and as-patterns
• Implement nested pattern matching
• Optimize pattern match coverage
• Generate efficient match dispatch code

Usage

Invoke this skill when you need to:

• Add pattern matching to a language
• Implement exhaustiveness checking
• Compile patterns efficiently
• Handle complex pattern features

Inputs

Parameter	Type	Required	Description
patternTypes	array	Yes	Types of patterns to support
targetLanguage	string	Yes	Language for implementation
compilationStrategy	string	No	Strategy (decision-tree, backtracking)
features	array	No	Advanced features to implement

Pattern Types

{
  "patternTypes": [
    "wildcard",
    "variable",
    "literal",
    "constructor",
    "tuple",
    "record",
    "list",
    "or-pattern",
    "as-pattern",
    "guard"
  ]
}

Feature Options

{
  "features": [
    "exhaustiveness-checking",
    "usefulness-checking",
    "decision-tree-compilation",
    "guard-clauses",
    "nested-patterns",
    "view-patterns",
    "active-patterns"
  ]
}

Output Structure

pattern-matching/
├── syntax/
│   ├── pattern.grammar            # Pattern syntax
│   └── match-expr.grammar         # Match expression syntax
├── analysis/
│   ├── exhaustiveness.ts          # Exhaustiveness checker
│   ├── usefulness.ts              # Usefulness/redundancy checker
│   └── pattern-types.ts           # Pattern type inference
├── compilation/
│   ├── decision-tree.ts           # Decision tree builder
│   ├── code-generator.ts          # Code generation
│   └── optimizer.ts               # Pattern optimization
├── runtime/
│   ├── matcher.ts                 # Runtime matching (interpreter)
│   └── guards.ts                  # Guard evaluation
└── tests/
    ├── exhaustiveness.test.ts
    ├── compilation.test.ts
    └── runtime.test.ts

Pattern Syntax

// Pattern ADT
type Pattern =
  | { type: 'wildcard' }                              // _
  | { type: 'variable'; name: string }                // x
  | { type: 'literal'; value: Literal }               // 42, "hello", true
  | { type: 'constructor'; name: string; args: Pattern[] }  // Some(x), Cons(h, t)
  | { type: 'tuple'; elements: Pattern[] }            // (x, y, z)
  | { type: 'record'; fields: Map<string, Pattern> }  // { name: n, age: a }
  | { type: 'list'; elements: Pattern[]; rest?: Pattern }  // [x, y, ...rest]
  | { type: 'or'; patterns: Pattern[] }               // p1 | p2
  | { type: 'as'; pattern: Pattern; name: string }    
  | { : ; : ; :  }; 


  {
  : ;
  : [];
}

  {
  : ;
  ?: ;
  : ;
}

Exhaustiveness Checking

// Based on "Warnings for Pattern Matching" (Maranget)

type PatternMatrix = Pattern[][];  // rows = arms, columns = scrutinees

// Check if pattern matrix is exhaustive
function isExhaustive(matrix: PatternMatrix, types: Type[]): boolean {
  if (matrix.length === 0) return false;
  if (types.length === 0) return true;

  const firstCol = matrix.map(row => row[0]);
  const sigma = getConstructorSignature(types[0]);

  if (sigma.isComplete(firstCol)) {
    // All constructors present - check specializations
    return sigma.constructors.every(ctor =>
      isExhaustive(specialize(matrix, ctor), specializationTypes(types, ctor))
    );
  } else {
    // Some constructors missing - check default matrix
    return isExhaustive(defaultMatrix(matrix), types.slice());
  }
}


 (): [] |  {
   (matrix. === ) {
    
     types.(generateWildcard);
  }
   (types. === )  ;  

   sigma = (types[]);
   firstCol = matrix.( row[]);

   (sigma.(firstCol)) {
     ( ctor  sigma.) {
       witness = (
        (matrix, ctor),
        (types, ctor)
      );
       (witness) {
         [(ctor, witness.(, ctor.)), ...witness.(ctor.)];
      }
    }
     ;
  }  {
    
     missing = sigma..( !firstCol.( (p, c)));
     (missing) {
       [(missing), ...types.().(generateWildcard)];
    }
     ((matrix), types.());
  }
}

Decision Tree Compilation

// Decision tree for efficient matching
type DecisionTree =
  | { type: 'fail' }
  | { type: 'leaf'; bindings: Map<string, Access>; body: Expr }
  | { type: 'switch'; access: Access; cases: SwitchCase[]; default?: DecisionTree };

interface SwitchCase {
  constructor: Constructor;
  tree: DecisionTree;
}

interface Access {
  root: string;
  path: AccessStep[];
}

type AccessStep =
  | { type: 'field'; index: number }
  | { type: 'deref' };

// Compile patterns to decision tree
function compilePatterns(arms: MatchArm[], scrutinee: Access): DecisionTree {
  if (arms.length === 0)  { :  };

  
   column = (arms);

  
   groups = (arms, column);

   (groups. === ) {
    
     bindings = (arms[]., scrutinee);
     { : , bindings, : arms[]. };
  }

  
   : [] = [];
   ( [ctor, ctorArms]  groups) {
     specializedAccess = (scrutinee, ctor);
    cases.({
      : ctor,
      : ((ctorArms, ctor), specializedAccess)
    });
  }

   defaultArms = arms.( (arm., column));
   defaultTree = defaultArms. > 
    ? (defaultArms, scrutinee)
    : ;

   { : , : scrutinee, cases, : defaultTree };
}

Guard Clause Handling

// Guards complicate exhaustiveness - we must be conservative
interface GuardedArm {
  pattern: Pattern;
  guard: Expr | null;
  body: Expr;
}

// For exhaustiveness: treat guarded patterns as potentially failing
function exhaustivenessWithGuards(arms: GuardedArm[], types: Type[]): Warning[] {
  const warnings: Warning[] = [];

  // Remove guards for exhaustiveness check (conservative)
  const unguardedMatrix = arms.map(arm => [arm.pattern]);
  if (!isExhaustive(unguardedMatrix, types)) {
    // May still be exhaustive if guards cover all cases
    // But we can't know statically - warn
    warnings.push({
      type: 'possibly-non-exhaustive',
      message: 'Match may not be exhaustive (guards present)',
      suggestion: 'Consider adding a catch-all pattern'
    });
  }

  return warnings;
}

// Decision tree with guards
type GuardedTree =
  | { type: 'fail' }
  | { type: 'guard'; : ; : ; :  }
  | { : ; : <, >; :  }
  | { : ; : ; : []; ?:  };

Code Generation

// Generate code from decision tree
function generateCode(tree: DecisionTree, target: CodeTarget): Code {
  switch (tree.type) {
    case 'fail':
      return target.emitMatchFailure();

    case 'leaf':
      const setup = Array.from(tree.bindings.entries())
        .map(([name, access]) => target.emitBinding(name, access));
      return target.emitBlock([...setup, target.emitExpr(tree.body)]);

    case 'switch':
      return target.emitSwitch(
        target.emitAccess(tree.access),
        tree.cases.map(c => ({
          test: target.emitConstructorTest(c.constructor),
          body: generateCode(c.tree, target)
        })),
        tree.default ? generateCode(tree.default, target) : target.()
      );
  }
}


 ():  {
  
  
  
  
  
  
  
  
  
}

Or-Patterns and As-Patterns

// Or-pattern: matches if any sub-pattern matches
// (Red | Green | Blue) => "color"

function expandOrPattern(pattern: Pattern): Pattern[] {
  if (pattern.type === 'or') {
    return pattern.patterns.flatMap(expandOrPattern);
  }
  // Recursively expand in sub-patterns
  // ...
  return [pattern];
}

// As-pattern: binds entire match to name
// (x :: xs) as list => (list, x)

function handleAsPattern(
  pattern: AsPattern,
  access: Access,
  bindings: Map<string, Access>
): void {
  // Bind the name to current access
  bindings.set(pattern.name, access);
  // Continue with inner pattern
  extractBindings(pattern.pattern, access, bindings);
}

Workflow

1. Define pattern syntax - Grammar for patterns
2. Implement pattern parser - Parse patterns to AST
3. Build exhaustiveness checker - Matrix-based analysis
4. Add usefulness checker - Detect redundant patterns
5. Implement decision tree compilation - Efficient matching
6. Generate target code - From decision trees
7. Handle guards - Conservative guard analysis
8. Write tests - Exhaustiveness, compilation, runtime

Best Practices Applied

• Conservative exhaustiveness with guards
• Informative non-exhaustiveness witnesses
• Efficient decision tree compilation
• Proper binding extraction order
• Support for nested patterns
• Clear redundancy warnings

References

• Warnings for Pattern Matching (Maranget): https://moscova.inria.fr/~maranget/papers/warn/
• Compiling Pattern Matching: https://www.cs.tufts.edu/~nr/cs257/archive/luc-maranget/jun08.pdf
• Rust Pattern Matching: https://doc.rust-lang.org/reference/patterns.html
• OCaml Pattern Matching: https://ocaml.org/docs/pattern-matching

Target Processes

• pattern-matching-implementation.js
• parser-development.js
• code-generation-llvm.js
• interpreter-implementation.js