Chapter 17: Pattern Matching Theory (Pattern Matching Theory)

소개

Phase 6이 시작된다. Phase 5에서 커스텀 MLIR dialect를 구축했다. funlang.closure와 funlang.apply로 클로저를 추상화했고, lowering pass로 LLVM dialect로 변환했다. 이제 함수형 언어의 핵심 기능을 추가할 시간이다: **패턴 매칭(pattern matching)**과 데이터 구조(data structures).

Phase 6 로드맵

Phase 6: Pattern Matching & Data Structures

이번 phase에서 구현할 내용:

1. Chapter 17 (현재): Pattern matching 이론 - Decision tree 알고리즘
2. Chapter 18: List operations - funlang.nil, funlang.cons 구현
3. Chapter 19: Match compilation - funlang.match operation과 lowering
4. Chapter 20: Functional programs - 실전 예제 (map, filter, fold)

왜 이 순서인가?

• 이론 먼저: Decision tree 알고리즘을 이해해야 MLIR 구현이 명확해진다
• 데이터 구조 다음: List operations가 있어야 패턴 매칭할 대상이 생긴다
• 매칭 구현: funlang.match operation으로 decision tree를 MLIR로 표현한다
• 실전 활용: 지금까지 배운 모든 기능을 종합해서 함수형 프로그램을 작성한다

Phase 5 복습: 왜 패턴 매칭이 필요한가?

Phase 5까지 우리는 이런 코드를 작성할 수 있게 되었다:

// F# compiler input
let make_adder n =
    fun x -> x + n

let add_5 = make_adder 5
let result = add_5 10  // 15

// Phase 5 MLIR output (FunLang dialect)
%closure = funlang.closure @lambda_adder, %n : !funlang.closure
%result = funlang.apply %closure(%x) : (i32) -> i32

하지만 함수형 언어의 진짜 힘은 데이터 구조와 패턴 매칭의 조합이다:

// F#에서 list 패턴 매칭
let rec sum_list lst =
    match lst with
    | [] -> 0
    | head :: tail -> head + sum_list tail

sum_list [1; 2; 3]  // 6

(* OCaml에서 패턴 매칭 *)
let rec length = function
  | [] -> 0
  | _ :: tail -> 1 + length tail

패턴 매칭이 제공하는 것:

1. 구조적 분해(structural decomposition): 데이터를 한 번에 분해하고 변수에 바인딩
2. Exhaustiveness checking: 컴파일러가 모든 경우를 다뤘는지 검증
3. 효율적인 분기: 각 subterm을 최대 한 번만 테스트하는 코드 생성
4. 가독성: if-else 체인보다 선언적이고 명확한 코드

Pattern Matching Compilation의 도전

Naive한 접근:

// 잘못된 방법: if-else 체인으로 번역
%is_nil = // list가 nil인지 테스트
scf.if %is_nil {
    %zero = arith.constant 0 : i32
    scf.yield %zero : i32
} else {
    %is_cons = // list가 cons인지 테스트 (중복!)
    scf.if %is_cons {
        %head = // head 추출
        %tail = // tail 추출
        %sum_tail = func.call @sum_list(%tail) : (!funlang.list<i32>) -> i32
        %result = arith.addi %head, %sum_tail : i32
        scf.yield %result : i32
    }
}

문제점:

1. 중복 테스트: Nil 테스트 실패 후 Cons 테스트는 중복이다 (list는 Nil 아니면 Cons)
2. 비효율적 코드: Nested patterns에서 exponential blowup 발생
3. Exhaustiveness 검증 어려움: 모든 case를 다뤘는지 확인이 복잡하다

올바른 접근: Decision Tree Compilation

Luc Maranget의 decision tree 알고리즘 (2008)을 사용하면:

• 각 subterm을 최대 한 번만 테스트
• Pattern matrix representation으로 체계적 변환
• Exhaustiveness checking이 자연스럽게 통합됨
• 최적화된 분기 코드 생성

Chapter 17 목표

이 장을 마치면:

• Pattern matrix 표현법을 이해한다
• Decision tree 알고리즘의 동작 원리를 안다
• Specialization과 defaulting 연산을 설명할 수 있다
• Exhaustiveness checking이 어떻게 동작하는지 안다
• Chapter 18-19에서 MLIR 구현을 시작할 준비가 된다

이론 중심 장(theory-focused chapter):

이 장은 구현 코드가 없다. 알고리즘 설명과 예제에 집중한다. 왜냐하면:

1. Decision tree 알고리즘은 MLIR과 독립적이다 (OCaml, Haskell, Rust 등 모든 함수형 언어에서 사용)
2. 알고리즘을 먼저 이해하면 MLIR lowering 구현이 명확해진다
3. Pattern matrix 표기법은 Chapter 19의 funlang.match operation 설계 기반이 된다

성공 기준

이 장을 이해했다면:

1. Pattern matrix에서 rows/columns가 무엇을 의미하는지 설명할 수 있다
2. Specialization 연산이 pattern을 어떻게 분해하는지 예시를 들 수 있다
3. Default 연산이 wildcard rows를 어떻게 처리하는지 설명할 수 있다
4. Empty pattern matrix가 왜 non-exhaustive match를 의미하는지 안다
5. Decision tree가 if-else chain보다 효율적인 이유를 설명할 수 있다

Let’s begin.

Pattern Matching 문제 정의

패턴 매칭 컴파일의 핵심 문제를 정의하자.

ML 계열 언어의 패턴 매칭

OCaml/F# syntax:

(* OCaml *)
match expr with
| pattern1 -> action1
| pattern2 -> action2
| pattern3 -> action3

// F#
match expr with
| pattern1 -> action1
| pattern2 -> action2
| pattern3 -> action3

Example: List length function

let rec length lst =
  match lst with
  | [] -> 0
  | _ :: tail -> 1 + length tail

구성 요소:

1. Scrutinee (lst): 매칭 대상 expression
2. Patterns ([], _ :: tail): 구조 템플릿
3. Actions (0, 1 + length tail): 패턴이 매칭되면 실행할 코드
4. Pattern variables (tail): 패턴 내부에서 값을 바인딩

FunLang 패턴 매칭 구문

FunLang의 제안 syntax (Phase 6 구현 목표):

// match expression
match list with
| Nil -> 0
| Cons(head, tail) -> head + sum tail

Pattern types:

1. Wildcard pattern (_): 모든 값과 매칭, 변수 바인딩 없음
2. Variable pattern (x, tail): 모든 값과 매칭, 변수에 바인딩
3. Constructor pattern (Nil, Cons(x, xs)): 특정 constructor와 매칭
4. Literal pattern (0, true): 특정 상수 값과 매칭

Constructor patterns의 subpatterns:

// Nested constructor patterns
match list with
| Nil -> "empty"
| Cons(x, Nil) -> "singleton"  // tail is Nil
| Cons(x, Cons(y, rest)) -> "at least two elements"

Cons(x, Nil)에서:

• Cons는 constructor
• x는 head subpattern (variable)
• Nil은 tail subpattern (constructor)

컴파일 문제: Patterns → Efficient Branching Code

Input: Pattern clauses (scrutinee, patterns, actions)

match list with
| Nil -> 0
| Cons(head, tail) -> head + sum tail

Output: Efficient branching code (MLIR IR)

%tag = llvm.extractvalue %list[0] : !llvm.struct<(i32, ptr)>
%is_nil = arith.cmpi eq, %tag, %c0 : i32

%result = scf.if %is_nil -> (i32) {
    %zero = arith.constant 0 : i32
    scf.yield %zero : i32
} else {
    // Cons case: extract head and tail
    %data = llvm.extractvalue %list[1] : !llvm.struct<(i32, ptr)>
    %head = llvm.load %data[0] : !llvm.ptr -> i32
    %tail = llvm.load %data[1] : !llvm.ptr -> !llvm.struct<(i32, ptr)>

    %sum_tail = func.call @sum(%tail) : (!funlang.list<i32>) -> i32
    %result_val = arith.addi %head, %sum_tail : i32
    scf.yield %result_val : i32
}

핵심 요구사항:

1. Correctness: 패턴 순서를 존중 (첫 번째 매칭 패턴이 선택됨)
2. Efficiency: 각 subterm을 최대 한 번만 테스트
3. Exhaustiveness: 모든 가능한 값이 처리되는지 검증
4. Optimization: 불필요한 테스트 제거 (Nil 아니면 자동으로 Cons)

Naive 컴파일의 문제점

If-else chain으로 직접 번역하면?

// Pattern 1: Nil
%is_nil = // test if tag == 0
scf.if %is_nil {
    scf.yield %zero : i32
} else {
    // Pattern 2: Cons(head, tail)
    %is_cons = // test if tag == 1 (redundant!)
    scf.if %is_cons {
        // extract head, tail, compute result
    } else {
        // No more patterns -> error!
    }
}

문제 1: 중복 테스트

Nil 테스트가 false면 자동으로 Cons다 (list는 Nil 또는 Cons만 존재). 하지만 naive 번역은 다시 Cons를 테스트한다.

문제 2: Nested patterns의 exponential blowup

match (list1, list2) with
| (Nil, Nil) -> 0
| (Nil, Cons(_, _)) -> 1
| (Cons(_, _), Nil) -> 2
| (Cons(x, _), Cons(y, _)) -> x + y

두 개의 scrutinee를 독립적으로 테스트하면:

list1 test -> list2 test (중복!)
            -> list2 test (중복!)
-> list1 test (중복!)
            -> list2 test (중복!)
            -> list2 test (중복!)

4개의 패턴이 8번의 테스트를 발생시킨다. Patterns이 늘어나면 2^n 테스트가 필요하다.

문제 3: Exhaustiveness 검증 복잡도

If-else tree를 분석해서 모든 경로가 종료되는지 확인해야 한다. 복잡한 중첩 패턴에서는 거의 불가능하다.

해결책: Decision Tree Compilation

Key insight (Maranget 2008):

“패턴 매칭은 search problem이다. Pattern clauses를 structured representation (pattern matrix)로 변환하면, systematic하게 optimal decision tree를 구성할 수 있다.”

Decision tree 특징:

1. 각 internal node는 하나의 test (constructor tag, literal value)
2. 각 edge는 test outcome (Nil vs Cons, 0 vs 1 vs 2)
3. 각 leaf는 action (실행할 코드)
4. Root에서 leaf까지 경로는 unique test sequence

장점:

• 각 subterm을 최대 한 번만 테스트 (no redundancy)
• Test 순서를 최적화 가능 (heuristic으로 선택)
• Exhaustiveness checking이 자연스러움 (leaf가 없는 경로 = missing pattern)

다음 섹션에서: Pattern matrix 표기법과 decision tree 구성 알고리즘을 자세히 살펴본다.

Pattern Matrix 표현법

Decision tree 알고리즘의 핵심은 pattern matrix라는 structured representation이다.

Pattern Matrix 정의

Pattern matrix는 2차원 테이블이다:

• Rows: Pattern clauses (각 row는 하나의 pattern -> action)
• Columns: Scrutinees (매칭 대상 values)
• Cells: Patterns (wildcard, constructor, literal)

Notation:

P = | p11  p12  ...  p1m  →  a1
    | p21  p22  ...  p2m  →  a2
    | ...
    | pn1  pn2  ...  pnm  →  an

• P: Pattern matrix (n rows × m columns)
• pij: Row i, column j의 pattern
• ai: Row i의 action
• m: Scrutinee 개수
• n: Pattern clause 개수

Example 1: 단일 Scrutinee (List Length)

FunLang code:

match list with
| Nil -> 0
| Cons(head, tail) -> 1 + length tail

Pattern matrix:

Scrutinee: [list]

Matrix:
| Nil             →  0
| Cons(head, tail) →  1 + length tail

설명:

• 1개의 scrutinee column: list
• 2개의 pattern rows:
  • Row 1: Nil pattern → action은 0
  • Row 2: Cons(head, tail) pattern → action은 1 + length tail

Constructor patterns의 subpatterns:

Cons(head, tail)은 2개의 subpatterns를 가진다:

• head: variable pattern (head 값에 바인딩)
• tail: variable pattern (tail 값에 바인딩)

나중에 이 subpatterns가 새로운 columns로 확장된다 (specialization).

Example 2: 다중 Scrutinee (Pair Matching)

FunLang code:

match (list1, list2) with
| (Nil, Nil) -> 0
| (Nil, Cons(x, _)) -> 1
| (Cons(_, _), Nil) -> 2
| (Cons(x, _), Cons(y, _)) -> x + y

Pattern matrix:

Scrutinee: [list1, list2]

Matrix:
| Nil         Nil          →  0
| Nil         Cons(x, _)   →  1
| Cons(_, _)  Nil          →  2
| Cons(x, _)  Cons(y, _)   →  x + y

설명:

• 2개의 scrutinee columns: list1, list2
• 4개의 pattern rows
• 각 cell은 해당 scrutinee의 pattern

Wildcard pattern _:

값을 바인딩하지 않는 pattern. 모든 값과 매칭된다.

Variable pattern x, y:

값을 변수에 바인딩하는 pattern. 모든 값과 매칭되지만 이름을 부여한다.

Wildcard vs Variable: Semantically 둘 다 모든 값과 매칭된다. Variable은 추가로 바인딩을 생성한다. Pattern matrix 관점에서는 동일하게 취급된다 (irrefutable pattern).

Example 3: Nested Pattern (List Prefix)

FunLang code:

match list with
| Nil -> "empty"
| Cons(x, Nil) -> "singleton"
| Cons(x, Cons(y, rest)) -> "at least two"

Initial pattern matrix:

Scrutinee: [list]

Matrix:
| Nil                   →  "empty"
| Cons(x, Nil)          →  "singleton"
| Cons(x, Cons(y, rest)) →  "at least two"

Nested constructor Cons(y, rest):

Row 3의 tail subpattern Cons(y, rest)는 또 다른 constructor pattern이다. 이게 nested pattern이다.

Compilation strategy:

1. 먼저 list의 constructor (Nil vs Cons) 테스트
2. Cons인 경우, head와 tail 추출
3. 이제 tail에 대해 다시 pattern matching (Nil vs Cons)

Specialization 후 matrix는 확장된다 (나중에 자세히 설명).

Occurrence Vectors

Pattern matrix와 함께 occurrence vectors를 유지한다.

Occurrence vector (π):

Scrutinee values에 어떻게 접근하는지 나타내는 경로(path) 목록.

Initial occurrences:

π = [o1, o2, ..., om]

• o1: First scrutinee (예: list)
• o2: Second scrutinee (예: list2)

Example: Single scrutinee

π = [list]

Example: Pair of scrutinees

π = [list1, list2]

Specialization 시 occurrences 확장:

Constructor pattern Cons(x, xs)를 specialize하면:

π = [list]
  → [list.head, list.tail]

list.head와 list.tail은 subterm access path를 의미한다 (MLIR에서는 llvm.extractvalue operations).

왜 occurrence vectors가 필요한가?

Decision tree를 생성할 때, 각 test가 어느 값을 검사하는지 알아야 한다.

• Initial: list 자체를 테스트
• After specialization: list.head, list.tail을 테스트

Occurrence vectors는 code generation의 기반이다.

Pattern Matrix Properties

Irrefutable row:

Row의 모든 patterns가 wildcard 또는 variable이면 irrefutable이다 (항상 매칭).

| _  _  _  →  action  // Irrefutable

Exhaustive matrix:

Matrix가 exhaustive하면 모든 가능한 input values가 어떤 row와 매칭된다.

Non-exhaustive matrix:

어떤 input value도 매칭되지 않는 경우가 있으면 non-exhaustive.

Empty matrix (P = ∅):

Row가 하나도 없는 matrix. 항상 non-exhaustive다.

Example: Non-exhaustive pattern

match list with
| Nil -> 0
// Missing: Cons case!

Matrix:

| Nil  →  0

Input Cons(1, Nil)은 어떤 row와도 매칭 안 됨 → non-exhaustive.

Pattern Matrix Compilation Goal

Compilation algorithm의 목표:

Pattern matrix P와 occurrence vector π를 입력받아서:

1. Decision tree를 생성한다 (efficient branching code)
2. Exhaustiveness를 검증한다 (empty matrix 체크)
3. Optimal test sequence를 선택한다 (heuristic)

Next section: Decision tree의 구조와 pattern matrix의 관계를 살펴본다.

Decision Tree 개념

Pattern matrix를 compile하면 decision tree가 생성된다. 이 섹션에서 decision tree의 구조와 특징을 이해한다.

Decision Tree 구조

Decision tree는 다음 요소로 구성된다:

1. Internal nodes (decision nodes): Test operations
   • Constructor test: “Is this value Nil or Cons?”
   • Literal test: “Is this value 0 or 1 or 2?”
2. Edges: Test outcomes (branches)
   • Constructor edges: Nil branch, Cons branch
   • Literal edges: 0 branch, 1 branch, default branch
3. Leaf nodes: Actions
   • Success leaf: Execute action (return value)
   • Failure leaf: Match failure (non-exhaustive error)

Tree traversal:

• Root에서 시작
• 각 internal node에서 test 실행
• Test outcome에 따라 edge 선택
• Leaf에 도달하면 종료 (action 실행 또는 failure)

Example: List Length Decision Tree

Pattern matrix:

| Nil             →  a1 (return 0)
| Cons(head, tail) →  a2 (return 1 + length tail)

Decision tree:

       [list]
         |
    Test: constructor
       /   \
     Nil   Cons
     /       \
   Leaf     [head, tail]
   a1          |
             Leaf
              a2

Tree 설명:

1. Root node: list의 constructor 테스트
2. Nil edge: Nil constructor → Leaf (action a1)
3. Cons edge: Cons constructor → Intermediate node (head, tail 추출)
4. Cons leaf: Action a2 실행

왜 [head, tail] node가 필요한가?

Cons pattern Cons(head, tail)은 subpatterns를 가진다. Cons case에서:

• head 값을 추출해서 변수 head에 바인딩
• tail 값을 추출해서 변수 tail에 바인딩

이 바인딩들이 action a2에서 사용된다.

Simplified view (bindings 생략):

       [list]
         |
    Test: constructor
       /   \
     Nil   Cons
     /       \
   a1        a2

구현에서는 Cons branch에서 head/tail 추출 코드를 삽입한다.

Example: Nested Pattern Decision Tree

Pattern matrix:

| Nil                   →  a1 ("empty")
| Cons(x, Nil)          →  a2 ("singleton")
| Cons(x, Cons(y, rest)) →  a3 ("at least two")

Decision tree:

          [list]
            |
       Test: constructor
         /   \
       Nil   Cons
       /       \
     a1      [head, tail]
                |
          Test: tail constructor
              /   \
            Nil   Cons
            /       \
          a2      [y, rest]
                     |
                    a3

Tree traversal example:

Input: Cons(1, Cons(2, Nil))

1. Root: Test list constructor → Cons
2. Extract head = 1, tail = Cons(2, Nil)
3. Test tail constructor → Cons
4. Extract y = 2, rest = Nil
5. Leaf a3 (“at least two”)

Key property: 각 subterm을 한 번만 테스트

• list constructor: 1번 테스트
• tail constructor: 1번 테스트

Naive if-else chain은 list constructor를 여러 번 테스트할 수 있다.

Comparison: Decision Tree vs If-Else Chain

If-Else chain (naive compilation):

// Pattern 1: Nil
%is_nil = arith.cmpi eq, %tag, %c0 : i32
scf.if %is_nil {
    scf.yield %a1 : i32
} else {
    // Pattern 2: Cons(x, Nil)
    %is_cons = arith.cmpi eq, %tag, %c1 : i32  // Redundant test!
    scf.if %is_cons {
        %tail = // extract tail
        %tail_tag = llvm.extractvalue %tail[0] : !llvm.struct<(i32, ptr)>
        %tail_is_nil = arith.cmpi eq, %tail_tag, %c0 : i32
        scf.if %tail_is_nil {
            scf.yield %a2 : i32
        } else {
            // Pattern 3: Cons(x, Cons(y, rest))
            // ... (more tests)
        }
    }
}

문제:

1. %is_cons test는 중복 (Nil이 아니면 자동으로 Cons)
2. Nested if-else는 depth가 깊어진다
3. 각 level에서 동일한 값을 반복 테스트

Decision tree (optimal compilation):

// Test list constructor once
%tag = llvm.extractvalue %list[0] : !llvm.struct<(i32, ptr)>
%result = scf.index_switch %tag : i32 -> i32
case 0 {  // Nil
    scf.yield %a1 : i32
}
case 1 {  // Cons
    %data = llvm.extractvalue %list[1] : !llvm.struct<(i32, ptr)>
    %head = llvm.load %data[0] : !llvm.ptr -> i32
    %tail_ptr = llvm.getelementptr %data[1] : (!llvm.ptr) -> !llvm.ptr
    %tail = llvm.load %tail_ptr : !llvm.ptr -> !llvm.struct<(i32, ptr)>

    // Test tail constructor once
    %tail_tag = llvm.extractvalue %tail[0] : !llvm.struct<(i32, ptr)>
    %tail_result = scf.index_switch %tail_tag : i32 -> i32
    case 0 {  // Nil
        scf.yield %a2 : i32
    }
    case 1 {  // Cons
        %tail_data = llvm.extractvalue %tail[1] : !llvm.struct<(i32, ptr)>
        %y = llvm.load %tail_data[0] : !llvm.ptr -> i32
        %rest_ptr = llvm.getelementptr %tail_data[1] : (!llvm.ptr) -> !llvm.ptr
        %rest = llvm.load %rest_ptr : !llvm.ptr -> !llvm.struct<(i32, ptr)>
        scf.yield %a3 : i32
    }
    scf.yield %tail_result : i32
}

장점:

1. 각 constructor tag를 정확히 한 번만 테스트 (scf.index_switch)
2. 불필요한 비교 연산 제거
3. Structured control flow (SCF dialect)로 최적화 기회 제공

Decision Tree Benefits

1. Efficiency: O(d) tests (d = pattern depth)

Nested pattern의 depth가 d면, 최대 d번의 test만 필요하다.

• Flat pattern (Nil, Cons(_, _)): 1번 test
• Nested pattern (Cons(_, Cons(_, _))): 2번 test (outer, inner)

If-else chain은 worst case O(n × d) tests (n = pattern 개수).

2. Exhaustiveness checking: Leaf coverage

모든 가능한 input이 어떤 leaf에 도달하면 exhaustive.

Leaf에 도달하지 않는 경로가 있으면 non-exhaustive.

Example: Non-exhaustive detection

Pattern matrix:
| Nil  →  a1
// Missing Cons case

Decision tree:

    [list]
      |
  Test: constructor
    /   \
  Nil   Cons
  /       \
a1      FAILURE  // No action for Cons

Cons branch가 Failure leaf로 이어진다 → Compile error: “non-exhaustive match”

3. Optimization opportunities

Decision tree는 structured representation이라서:

• Common subexpression elimination (같은 test를 여러 번 안 함)
• Dead code elimination (도달 불가능한 patterns 제거)
• Branch prediction hints (frequent cases 먼저 테스트)

Relationship: Pattern Matrix → Decision Tree

Compilation function:

compile : PatternMatrix × OccurrenceVector → DecisionTree

Input:

• Pattern matrix P (n rows × m columns)
• Occurrence vector π (m elements)

Output:

• Decision tree T

Recursive algorithm:

function compile(P, π):
    if P is empty:
        return Failure  // Non-exhaustive

    if first row is irrefutable:
        return Success(action)  // Found match

    column = select_column(P)
    constructors = get_constructors(P, column)

    branches = {}
    for each constructor c:
        P_c = specialize(P, column, c)
        π_c = specialize_occurrences(π, column, c)
        branches[c] = compile(P_c, π_c)

    P_default = default(P, column)
    π_default = default_occurrences(π, column)
    default_branch = compile(P_default, π_default)

    return Switch(π[column], branches, default_branch)

핵심 operations:

1. select_column: 어느 column을 먼저 테스트할지 선택 (heuristic)
2. specialize: Constructor와 매칭되는 rows만 남기고, subpatterns 확장
3. default: Wildcard rows만 남기고, 테스트한 column 제거

Next sections: Specialization과 defaulting을 자세히 설명한다.

Specialization 연산

Specialization은 decision tree 알고리즘의 핵심 operation이다. Constructor test가 성공했을 때 pattern matrix를 어떻게 변환하는지 정의한다.

Specialization 정의

Specialization (S):

S(c, i, P) = Specialized pattern matrix

Parameters:

• c: Constructor (예: Cons, Nil)
• i: Column index (어느 scrutinee를 테스트하는가)
• P: Original pattern matrix

Operation:

1. Column i의 pattern이 constructor c와 호환되는 rows만 유지
2. 호환되는 patterns를 subpatterns로 확장 (constructor decomposition)
3. Column i를 제거하고 subpattern columns를 삽입

Example 1: Simple List Specialization (Cons)

Original pattern matrix:

Column: [list]

| Nil             →  a1
| Cons(head, tail) →  a2
| _               →  a3

Specialize on column 0, constructor Cons:

S(Cons, 0, P):

Step 1: Filter compatible rows

• Row 1 (Nil): Incompatible with Cons → 제거
• Row 2 (Cons(head, tail)): Compatible → 유지
• Row 3 (_): Wildcard, compatible → 유지

Step 2: Decompose patterns

• Row 2: Cons(head, tail) → expand to [head, tail]
• Row 3: _ → expand to [_, _] (wildcard for each subpattern)

Step 3: Replace column 0 with subpattern columns

Columns: [head, tail]

| head  tail  →  a2
| _     _     →  a3

Occurrence vector update:

Before: π = [list]
After:  π = [list.head, list.tail]

Example 2: Specialization on Nil

Original pattern matrix:

Column: [list]

| Nil             →  a1
| Cons(head, tail) →  a2
| _               →  a3

Specialize on column 0, constructor Nil:

S(Nil, 0, P):

Step 1: Filter compatible rows

• Row 1 (Nil): Compatible → 유지
• Row 2 (Cons(head, tail)): Incompatible with Nil → 제거
• Row 3 (_): Wildcard, compatible → 유지

Step 2: Decompose patterns

Nil constructor는 subpatterns가 없다 (nullary constructor).

• Row 1: Nil → no subpatterns
• Row 3: _ → no subpatterns

Step 3: Remove column 0 (no subpatterns to add)

Columns: [] (empty)

| →  a1
| →  a3

Occurrence vector update:

Before: π = [list]
After:  π = [] (empty)

Empty occurrence vector는 모든 tests가 완료되었음을 의미. 이제 첫 번째 row의 action을 선택한다.

Example 3: Nested Pattern Specialization

Original pattern matrix:

Column: [list]

| Cons(x, Nil)          →  a1
| Cons(x, Cons(y, rest)) →  a2

Specialize on column 0, constructor Cons:

S(Cons, 0, P):

Step 1: Filter compatible rows

Both rows have Cons → 둘 다 유지

Step 2: Decompose patterns

• Row 1: Cons(x, Nil) → subpatterns [x, Nil]
• Row 2: Cons(x, Cons(y, rest)) → subpatterns [x, Cons(y, rest)]

Step 3: Replace column 0 with subpattern columns

Columns: [head, tail]

| x  Nil              →  a1
| x  Cons(y, rest)    →  a2

Occurrence vector update:

Before: π = [list]
After:  π = [list.head, list.tail]

이제 column 1 (tail)에 대해 다시 specialization:

Matrix after first specialization:

| x  Nil              →  a1
| x  Cons(y, rest)    →  a2

Specialize on column 1, constructor Nil:

Columns: [head]

| x  →  a1

Specialize on column 1, constructor Cons:

Columns: [head, y, rest]

| x  y  rest  →  a2

Nested patterns는 여러 번의 specialization으로 처리된다.

Wildcard Expansion Rule

Wildcard pattern _의 specialization:

Constructor c가 arity n (subpatterns 개수)를 가지면:

_ → [_, _, ..., _]  (n개의 wildcards)

Example: Cons constructor (arity 2)

_ → [_, _]  // head wildcard, tail wildcard

Example: Nil constructor (arity 0)

_ → []  // No subpatterns

왜 wildcard를 확장하는가?

Wildcard는 “모든 값과 매칭“을 의미한다. Constructor c와 매칭되면, c의 모든 subpatterns도 wildcard로 매칭된다.

// Original pattern
| _ -> action

// After specialization on Cons
// Equivalent to:
| Cons(_, _) -> action

Variable Pattern Specialization

Variable pattern x의 specialization:

Variable은 wildcard와 동일하게 확장되지만, binding name을 유지한다.

x → [_, _, ..., _]  // Subpatterns, 하지만 x는 여전히 전체 값에 바인딩됨

Example:

match list with
| xs -> length xs  // xs는 전체 list에 바인딩

Specialize on Cons:

Columns: [head, tail]

| _  _  →  length (Cons head tail)

xs 바인딩은 original occurrence에 남는다. Specialization 후에도 xs는 사용 가능하다.

Implementation note: Variable bindings는 pattern matrix에 직접 저장되지 않고, occurrence vector와 함께 관리된다. Action에서 variable을 사용할 때 occurrence path로 접근한다.

Specialization Pseudocode

Algorithm: specialize(P, column, constructor)

def specialize(P, column, constructor):
    """
    P: Pattern matrix (n rows × m columns)
    column: Column index to specialize
    constructor: Constructor to match (e.g., Cons, Nil)

    Returns: Specialized matrix
    """
    result_rows = []
    arity = get_arity(constructor)  // Subpattern 개수

    for row in P:
        pattern = row[column]

        if matches_constructor(pattern, constructor):
            # Compatible pattern
            if pattern.is_constructor and pattern.name == constructor:
                # Extract subpatterns
                subpatterns = pattern.subpatterns  // e.g., [head, tail]
            elif pattern.is_wildcard or pattern.is_variable:
                # Expand to wildcard subpatterns
                subpatterns = [Wildcard] * arity  // e.g., [_, _]
            else:
                # Incompatible (different constructor)
                continue  # Skip this row

            # Build new row: columns before + subpatterns + columns after
            new_row = (
                row[:column] +
                subpatterns +
                row[column+1:]
            )
            result_rows.append((new_row, row.action))

    return PatternMatrix(result_rows)

def matches_constructor(pattern, constructor):
    """Check if pattern is compatible with constructor"""
    if pattern.is_wildcard or pattern.is_variable:
        return True  # Wildcard matches everything
    if pattern.is_constructor and pattern.name == constructor:
        return True  # Same constructor
    return False  # Different constructor

Visual Example: Specialization Flow

Original:

   [list]
     |
| Nil        →  a1
| Cons(x, y) →  a2
| _          →  a3

After S(Cons, 0, P):

   [x, y]  (head, tail)
     |
| x  y  →  a2  (from Cons(x, y))
| _  _  →  a3  (from _)

Row 1 (Nil) 제거됨 (incompatible).

After S(Nil, 0, P) on original:

   []  (no occurrences)
    |
| →  a1  (from Nil)
| →  a3  (from _)

Rows 2 (Cons) 제거됨 (incompatible).

Key Insight: Specialization = Assumption + Decomposition

Specialization의 의미:

“Column i의 constructor가 c라고 가정하면, pattern matrix는 어떻게 변하는가?”

Assumption:

• Constructor test가 성공했다 (e.g., list가 Cons)
• 이제 c의 subpatterns에 접근 가능 (e.g., head, tail)

Decomposition:

• 호환되지 않는 rows 제거 (Nil patterns)
• 호환되는 rows의 patterns를 subpatterns로 확장

Next: Defaulting 연산은 반대 상황을 다룬다 (constructor test 실패).

Defaulting 연산

Defaulting은 specialization의 complement다. Constructor test가 실패했을 때 (또는 테스트하지 않고 default case로 가려 할 때) pattern matrix를 어떻게 변환하는지 정의한다.

Defaulting 정의

Defaulting (D):

D(i, P) = Default pattern matrix

Parameters:

• i: Column index
• P: Original pattern matrix

Operation:

1. Column i의 pattern이 wildcard 또는 variable인 rows만 유지
2. Column i를 제거 (더 이상 테스트 안 함)
3. 나머지 columns는 유지

의미:

“Column i에 대한 모든 constructor tests가 실패했다. Wildcard rows만 남는다.”

Example 1: Simple List Defaulting

Original pattern matrix:

Column: [list]

| Nil             →  a1
| Cons(head, tail) →  a2
| _               →  a3

Default on column 0:

D(0, P):

Step 1: Filter wildcard rows

• Row 1 (Nil): Constructor pattern → 제거
• Row 2 (Cons(head, tail)): Constructor pattern → 제거
• Row 3 (_): Wildcard → 유지

Step 2: Remove column 0

Columns: [] (empty)

| →  a3

Occurrence vector update:

Before: π = [list]
After:  π = [] (empty)

Empty matrix with one row → Irrefutable → Select action a3.

Example 2: Empty Default Matrix

Original pattern matrix:

Column: [list]

| Nil             →  a1
| Cons(head, tail) →  a2

Default on column 0:

D(0, P):

Step 1: Filter wildcard rows

• Row 1 (Nil): Constructor pattern → 제거
• Row 2 (Cons(head, tail)): Constructor pattern → 제거

Result: Empty matrix

Columns: []

(no rows)

의미: Non-exhaustive match!

모든 rows가 constructor patterns이면, defaulting은 empty matrix를 생성한다. 즉, wildcard case가 없다 → Non-exhaustive.

Compiler action:

Empty default matrix는 compile error를 발생시킨다:

Error: Non-exhaustive pattern match
Missing case: (other constructors or wildcard)

Example 3: Multiple Columns Defaulting

Original pattern matrix:

Columns: [list1, list2]

| Nil         Nil          →  a1
| Nil         Cons(x, _)   →  a2
| Cons(_, _)  Nil          →  a3
| Cons(x, _)  Cons(y, _)   →  a4
| _           _            →  a5

Default on column 0:

D(0, P):

Step 1: Filter wildcard rows on column 0

• Row 1 (Nil): Constructor → 제거
• Row 2 (Nil): Constructor → 제거
• Row 3 (Cons(_, _)): Constructor → 제거
• Row 4 (Cons(x, _)): Constructor → 제거
• Row 5 (_): Wildcard → 유지

Step 2: Remove column 0

Columns: [list2]

| _  →  a5

Occurrence vector update:

Before: π = [list1, list2]
After:  π = [list2]

이제 column 0 (이전 list2)에 대해 specialization 또는 defaulting을 계속할 수 있다.

Defaulting vs Specialization: When to Use

Specialization:

Constructor test가 성공했을 때.

if (tag == CONS) {
    // Specialize on Cons
    S(Cons, 0, P)
}

Defaulting:

모든 constructor tests가 실패했을 때.

if (tag == NIL) {
    S(Nil, 0, P)
} else if (tag == CONS) {
    S(Cons, 0, P)
} else {
    // Default case
    D(0, P)
}

하지만 list는 Nil 또는 Cons만 존재한다!

완전한 constructor set (Nil, Cons)을 모두 테스트하면 default case는 unreachable이다.

Defaulting이 필요한 경우:

1. Extensible constructors: Open constructor sets (예: integers)
2. Incomplete specialization: 일부 constructors만 테스트
3. Wildcard-only rows: 모든 constructors 후 남은 wildcard 처리

List의 경우 (closed constructor set):

if (tag == NIL) {
    S(Nil, 0, P)
} else {
    // Must be CONS (only two constructors)
    S(Cons, 0, P)
}

Default branch는 필요 없다. 하지만 algorithm에서는 여전히 defaulting을 계산해서 exhaustiveness를 체크한다.

Defaulting Empty Matrix Detection

Defaulting의 중요한 역할: Exhaustiveness checking

Case 1: Non-empty default matrix

Pattern matrix:
| Cons(x, xs)  →  a1
| _            →  a2  // Wildcard exists

Default on column 0:

| →  a2  // Non-empty

Result: Exhaustive (wildcard catches everything)

Case 2: Empty default matrix

Pattern matrix:
| Cons(x, xs)  →  a1
// No wildcard

Default on column 0:

(empty matrix)

Result: Non-exhaustive (missing Nil case and wildcard)

Compiler error:

Error: Non-exhaustive pattern match
Missing case: Nil

Defaulting Pseudocode

Algorithm: default(P, column)

def default(P, column):
    """
    P: Pattern matrix (n rows × m columns)
    column: Column index to default

    Returns: Default matrix (wildcard rows only, column removed)
    """
    result_rows = []

    for row in P:
        pattern = row[column]

        if pattern.is_wildcard or pattern.is_variable:
            # Wildcard row: keep it, remove column
            new_row = row[:column] + row[column+1:]
            result_rows.append((new_row, row.action))
        else:
            # Constructor pattern: remove this row
            continue

    return PatternMatrix(result_rows)

Simplicity:

Defaulting은 specialization보다 간단하다:

• No subpattern expansion
• Just filter wildcard rows and remove column

Visual Example: Defaulting Flow

Original:

   [list]
     |
| Nil        →  a1
| Cons(x, y) →  a2
| _          →  a3

After D(0, P):

   []  (no occurrences)
    |
| →  a3  (from _)

Rows 1 (Nil) and 2 (Cons) 제거됨 (constructor patterns).

Empty default example:

   [list]
     |
| Nil        →  a1
| Cons(x, y) →  a2

After D(0, P):

   []
    |
(empty - no wildcard rows)

Compiler: “Error: Non-exhaustive match”

Key Insight: Defaulting = Catch-All Case

Defaulting의 의미:

“모든 명시적 constructor tests가 실패했다. 남은 rows는 wildcard만 있다. Wildcard는 catch-all이다.”

Properties:

1. Default matrix는 항상 wildcards만 포함 (constructors 제거됨)
2. Empty default matrix = non-exhaustive (catch-all 없음)
3. Default 후 irrefutable row가 남으면 항상 매칭 (first wildcard row 선택)

Next: Specialization과 defaulting을 결합해서 complete compilation algorithm을 만든다.

Complete Compilation Algorithm

이제 specialization과 defaulting을 결합해서 complete decision tree compilation algorithm을 구성한다.

Algorithm Overview

Recursive function:

compile : PatternMatrix × OccurrenceVector → DecisionTree

Input:

• Pattern matrix P (n rows × m columns)
• Occurrence vector π (m elements, scrutinee access paths)

Output:

• Decision tree T

Strategy:

1. Base cases: Empty matrix, irrefutable first row
2. Recursive case: Select column, specialize on constructors, recurse
3. Default case: Default on column, recurse

Base Case 1: Empty Matrix

Condition:

if P.is_empty():

Meaning:

No pattern rows remain. 어떤 pattern도 매칭되지 않는다.

Action:

return FailureLeaf()

MLIR equivalent:

// Non-exhaustive match error
llvm.call @match_failure() : () -> ()
llvm.unreachable

Example:

Pattern matrix:
(empty)

Input: Cons(1, Nil)

No patterns → match failure

Base Case 2: Irrefutable First Row

Condition:

if all(p.is_wildcard or p.is_variable for p in P[0]):

Meaning:

첫 번째 row의 모든 patterns가 wildcard 또는 variable이다. 이 row는 항상 매칭된다.

Action:

return SuccessLeaf(P[0].action)

Example:

Pattern matrix:
| _  _  →  a1
| ... (more rows, but unreachable)

Any input → select action a1

Unreachable rows:

첫 번째 irrefutable row 이후의 rows는 절대 실행 안 됨.

match list with
| _ -> 0
| Nil -> 1  // Warning: Unreachable pattern

Compiler warning: “Unreachable pattern (row 2)”

Recursive Case: Constructor Test

Condition:

if P is not empty and first row has constructors:

Steps:

1. Select column: 어느 occurrence를 테스트할지 선택
2. Get constructors: 그 column에 등장하는 constructors 수집
3. Specialize: 각 constructor에 대해 specialized matrix 생성, recurse
4. Default: Wildcard rows로 default matrix 생성, recurse

Pseudocode:

def compile(P, π):
    # Base case 1: Empty matrix
    if not P:
        return Failure()

    # Base case 2: Irrefutable first row
    if is_irrefutable(P[0]):
        return Success(P[0].action)

    # Recursive case: Constructor test
    column = select_column(P, π)
    constructors = get_constructors(P, column)

    # Build switch node
    branches = {}
    for c in constructors:
        # Specialize on constructor c
        P_c = specialize(P, column, c)
        π_c = specialize_occurrences(π, column, c)
        branches[c] = compile(P_c, π_c)

    # Default branch (wildcard rows)
    P_default = default(P, column)
    π_default = default_occurrences(π, column)
    default_branch = compile(P_default, π_default)

    return Switch(π[column], branches, default_branch)

Column Selection Heuristic

문제: 여러 columns가 있을 때, 어느 column을 먼저 테스트하는가?

Heuristic 1: Left-to-right (simple)

def select_column(P, π):
    return 0  # Always test first column

장점: 간단, 예측 가능 단점: 비효율적일 수 있음 (redundant tests)

Heuristic 2: Needed by most rows (Maranget)

def select_column(P, π):
    """Select column needed by most rows (first constructor pattern)"""
    for col in range(len(π)):
        needed_count = sum(1 for row in P if not row[col].is_wildcard)
        if needed_count > 0:
            return col
    return 0  # All wildcards, any column works

의미:

• Constructor pattern이 가장 많은 column 선택
• Wildcards는 어떤 constructor도 요구 안 함 (skip 가능)

Example:

Columns: [c1, c2]

| _     Cons(x, _)  →  a1  // c1 not needed, c2 needed
| Nil   _           →  a2  // c1 needed, c2 not needed
| _     _           →  a3  // neither needed

• c1 needed by: 1 row
• c2 needed by: 1 row
• Tie → select c1 (left-to-right tie-breaker)

Heuristic 3: Minimize combined row count (optimal)

def select_column(P, π):
    """Select column that minimizes total specialized matrix sizes"""
    best_column = 0
    min_cost = float('inf')

    for col in range(len(π)):
        constructors = get_constructors(P, col)
        cost = sum(len(specialize(P, col, c)) for c in constructors)
        if cost < min_cost:
            min_cost = cost
            best_column = col

    return best_column

의미: Specialized matrices의 크기 합이 최소인 column 선택

Tradeoff: 계산 비용이 높음 (모든 columns에 대해 specialize 시뮬레이션)

FunLang Phase 6 choice: Heuristic 1 (left-to-right)

간단하고 예측 가능. 대부분의 FunLang patterns는 단순해서 heuristic 차이가 크지 않다.

Occurrence Specialization

Specialization 후 occurrence vector 업데이트:

Example: Cons specialization

Before: π = [list]
Constructor: Cons (arity 2)

After: π = [list.head, list.tail]

Pseudocode:

def specialize_occurrences(π, column, constructor):
    """Expand occurrence at column into suboccurrences"""
    arity = get_arity(constructor)
    suboccurrences = [
        Occurrence(π[column].path + f".{i}")
        for i in range(arity)
    ]

    # Replace column with suboccurrences
    return π[:column] + suboccurrences + π[column+1:]

Occurrence paths:

• list → list.0 (head), list.1 (tail)
• list.tail → list.1.0 (tail’s head), list.1.1 (tail’s tail)

MLIR code generation:

// π = [list]
%list = ...

// π = [list.0, list.1]
%head = llvm.extractvalue %list[0] : !llvm.struct<(i32, ptr)>
%tail_ptr = llvm.getelementptr %list[1] : (!llvm.ptr) -> !llvm.ptr
%tail = llvm.load %tail_ptr : !llvm.ptr -> !llvm.struct<(i32, ptr)>

Occurrence paths는 extraction code를 생성하는 template이다.

Occurrence Defaulting

Defaulting 후 occurrence vector 업데이트:

Example:

Before: π = [list, other]
Default on column 0:

After: π = [other]

Pseudocode:

def default_occurrences(π, column):
    """Remove occurrence at column"""
    return π[:column] + π[column+1:]

Defaulting은 column을 제거한다 (더 이상 테스트 안 함).

Complete Example: List Length Compilation

Pattern matrix:

π = [list]

| Nil             →  0
| Cons(head, tail) →  1 + length tail

Step 1: compile(P, [list])

• Not empty
• First row not irrefutable (Nil is constructor)
• Select column 0

Step 2: Get constructors

constructors = [Nil, Cons]

Step 3: Specialize on Nil

P_nil = specialize(P, 0, Nil)
π_nil = [list] → []

Result:

π = []

| →  0

Irrefutable → Success(0)

Step 4: Specialize on Cons

P_cons = specialize(P, 0, Cons)
π_cons = [list] → [list.head, list.tail]

Result:

π = [list.head, list.tail]

| head  tail  →  1 + length tail

Irrefutable → Success(1 + length tail)

Step 5: Default

P_default = default(P, 0)

Result: Empty (no wildcard rows)

compile(P_default, []) = Failure()

하지만 Nil + Cons가 complete constructor set이므로 default branch는 unreachable.

Generated decision tree:

Switch(list, {
    Nil: Success(0),
    Cons: Success(1 + length tail)
}, Failure())

MLIR output:

%tag = llvm.extractvalue %list[0] : !llvm.struct<(i32, ptr)>
%result = scf.index_switch %tag : i32 -> i32
case 0 {  // Nil
    %zero = arith.constant 0 : i32
    scf.yield %zero : i32
}
case 1 {  // Cons
    %data = llvm.extractvalue %list[1] : !llvm.struct<(i32, ptr)>
    %head = llvm.load %data[0] : !llvm.ptr -> i32
    %tail_ptr = llvm.getelementptr %data[1] : (!llvm.ptr) -> !llvm.ptr
    %tail = llvm.load %tail_ptr : !llvm.ptr -> !llvm.struct<(i32, ptr)>

    %one = arith.constant 1 : i32
    %len_tail = func.call @length(%tail) : (!funlang.list<i32>) -> i32
    %result_val = arith.addi %one, %len_tail : i32
    scf.yield %result_val : i32
}
default {
    llvm.unreachable  // Should never reach (exhaustive)
}

Example 2: Nested Pattern Compilation

Pattern matrix:

π = [list]

| Cons(x, Nil)          →  "singleton"
| Cons(x, Cons(y, rest)) →  "at least two"
| _                     →  "other"

Step 1: compile(P, [list])

Select column 0, constructors = [Cons]

Step 2: Specialize on Cons

P_cons = specialize(P, 0, Cons)
π_cons = [list.head, list.tail]

Result:

π = [list.head, list.tail]

| x  Nil              →  "singleton"
| x  Cons(y, rest)    →  "at least two"
| _  _                →  "other"

Step 3: compile(P_cons, [list.head, list.tail])

First row not irrefutable (column 1 has Nil constructor).

Select column 1 (tail), constructors = [Nil, Cons]

Step 4: Specialize on Nil (column 1)

P_cons_nil = specialize(P_cons, 1, Nil)
π_cons_nil = [list.head]

Result:

π = [list.head]

| x  →  "singleton"
| _  →  "other"

First row irrefutable → Success("singleton")

Step 5: Specialize on Cons (column 1)

P_cons_cons = specialize(P_cons, 1, Cons)
π_cons_cons = [list.head, list.tail.head, list.tail.tail]

Result:

π = [list.head, list.tail.head, list.tail.tail]

| x  y  rest  →  "at least two"
| _  _  _     →  "other"

First row irrefutable → Success("at least two")

Step 6: Default (column 1)

P_cons_default = default(P_cons, 1)
π_cons_default = [list.head]

Result:

π = [list.head]

| _  →  "other"

Irrefutable → Success("other")

Step 7: Default on column 0 (original)

P_default = default(P, 0)
π_default = []

Result:

π = []

| →  "other"

Irrefutable → Success("other")

Generated decision tree:

Switch(list, {
    Cons: Switch(list.tail, {
        Nil: Success("singleton"),
        Cons: Success("at least two")
    }, Success("other"))
}, Success("other"))

Nested structure: Cons branch 안에 또 다른 switch (tail test).

Exhaustiveness Checking

Exhaustiveness checking은 decision tree 알고리즘에 자연스럽게 통합된다.

Exhaustiveness 정의

Exhaustive pattern match:

모든 가능한 input values가 어떤 pattern과 매칭된다.

Non-exhaustive pattern match:

어떤 input value는 어떤 pattern과도 매칭되지 않는다.

Example: Exhaustive

match list with
| Nil -> 0
| Cons(_, _) -> 1

모든 list는 Nil 또는 Cons다 → Exhaustive.

Example: Non-exhaustive

match list with
| Nil -> 0
// Missing: Cons case

Input Cons(1, Nil)은 매칭 안 됨 → Non-exhaustive.

Empty Matrix = Non-Exhaustive

Key insight:

Empty pattern matrix는 어떤 input도 매칭 안 됨을 의미한다.

Compilation algorithm:

def compile(P, π):
    if not P:
        return Failure()  # Non-exhaustive!

Detection points:

1. Initial matrix empty: 아예 patterns가 없음
2. Specialization 후 empty: 특정 constructor case가 없음
3. Default 후 empty: Wildcard case가 없음

Example 1: Missing Constructor Case

Pattern matrix:

π = [list]

| Nil  →  0

Compile:

• Specialize on Nil: Success(0)
• Specialize on Cons: specialize(P, 0, Cons) → empty matrix
  • No Cons patterns in original matrix
  • Result: Failure()

Decision tree:

Switch(list, {
    Nil: Success(0),
    Cons: Failure()  // Non-exhaustive!
}, Failure())

Compiler error:

Error: Non-exhaustive pattern match
Location: match list with ...
Missing case: Cons(_, _)

Example 2: Missing Wildcard

Pattern matrix:

π = [list]

| Nil         →  0
| Cons(x, xs) →  1

Compile:

• Specialize on Nil: Success(0)
• Specialize on Cons: Success(1)
• Default: default(P, 0) → empty matrix
  • No wildcard rows
  • Result: Failure()

하지만 이 경우는 실제로 exhaustive다!

Nil + Cons가 complete constructor set이므로 default branch는 unreachable.

Optimization:

Complete constructor set일 때 default branch를 생략할 수 있다.

def compile(P, π):
    # ...
    constructors = get_constructors(P, column)
    if is_complete_set(constructors):
        # No default branch needed
        return Switch(π[column], branches, None)
    else:
        # Default branch for incomplete sets
        default_branch = compile(default(P, column), ...)
        return Switch(π[column], branches, default_branch)

Complete constructor sets:

• List: {Nil, Cons}
• Bool: {True, False}
• Option: {None, Some}

Example 3: Nested Non-Exhaustiveness

Pattern matrix:

π = [list]

| Cons(x, Nil)  →  "singleton"
// Missing: Cons(x, Cons(y, rest))
// Missing: Nil

Compile:

1. Specialize on Cons:

   π = [list.head, list.tail]
   
   | x  Nil  →  "singleton"
   

2. Specialize on Nil (column 1):

   π = [list.head]
   
   | x  →  "singleton"
   

   Result: Success("singleton")

3. Specialize on Cons (column 1):

   (empty matrix)  // No Cons(x, Cons(...)) pattern
   

   Result: Failure() → Non-exhaustive

4. Default on column 0:

   (empty matrix)  // No wildcard or Nil pattern
   

   Result: Failure() → Non-exhaustive

Decision tree:

Switch(list, {
    Cons: Switch(list.tail, {
        Nil: Success("singleton"),
        Cons: Failure()  // Missing!
    }, Failure()),
}, Failure())  // Missing Nil!

Compiler error:

Error: Non-exhaustive pattern match
Missing cases:
  - Nil
  - Cons(_, Cons(_, _))

Exhaustiveness Error Reporting

Basic approach: Failure leaf

Compile 중 empty matrix 발견 시 error 발생:

def compile(P, π):
    if not P:
        raise CompileError("Non-exhaustive pattern match")

Advanced approach: Missing pattern reconstruction

Empty matrix가 발생한 경로를 추적해서 missing pattern 생성:

def compile(P, π, path=[]):
    if not P:
        missing = reconstruct_pattern(path)
        raise CompileError(f"Missing case: {missing}")

    # ...
    for c in constructors:
        P_c = specialize(P, column, c)
        compile(P_c, π_c, path + [(column, c)])

Example path:

path = [(0, Cons), (1, Cons)]
→ Missing pattern: Cons(_, Cons(_, _))

FunLang Phase 6 approach:

간단한 error message만 제공:

Error: Non-exhaustive pattern match at line X
Consider adding a wildcard pattern: | _ -> ...

자세한 missing case 분석은 나중 phase 또는 bonus 섹션에서 다룬다.

Exhaustiveness Check가 자연스러운 이유

Decision tree 알고리즘의 장점:

“Exhaustiveness checking은 별도의 분석 pass가 아니다. Compilation 과정에서 자동으로 발견된다.”

왜 자연스러운가?

1. Empty matrix는 명확한 신호: No patterns left = no matches possible
2. Recursive structure: 각 specialization/default 단계에서 independently 체크
3. Complete constructor sets: 간단한 rule로 false positives 제거 가능

Contrast with if-else chain analysis:

If-else tree를 분석하려면:

• 모든 경로를 traverse
• 각 경로가 종료되는지 확인
• Missing 경로를 역으로 추론

Decision tree는 construction 과정에서 바로 확인된다.

리터럴 패턴과 와일드카드 최적화

지금까지 constructor patterns (Nil, Cons)를 중심으로 설명했다. 하지만 실제 프로그래밍에서는 리터럴 패턴과 와일드카드 패턴도 매우 중요하다.

리터럴 패턴 컴파일 (Literal Pattern Compilation)

리터럴 패턴이란?

리터럴 패턴은 특정 상수 값과 매칭되는 패턴이다:

// 정수 리터럴 패턴
match x with
| 0 -> "zero"
| 1 -> "one"
| 2 -> "two"
| _ -> "other"

// 문자열 리터럴 패턴 (문자열 타입이 있다면)
match color with
| "red" -> 0xFF0000
| "green" -> 0x00FF00
| "blue" -> 0x0000FF
| _ -> 0x000000

Constructor patterns와의 차이:

리터럴 패턴의 특징:

1. 분해되지 않음: Cons(x, xs)는 x와 xs로 분해되지만, 42는 그 자체로 atomic하다
2. 무한 가능성: 정수는 무한히 많으므로 모든 case를 나열할 수 없다
3. 등호 테스트: Constructor tag가 아니라 값 자체를 비교해야 한다

리터럴 패턴의 Pattern Matrix

Example: Modulo 3 classification

let classify_mod3 n =
    match n % 3 with
    | 0 -> "divisible by 3"
    | 1 -> "remainder 1"
    | 2 -> "remainder 2"
    | _ -> "unexpected"  // 논리적으로 unreachable

Pattern matrix:

Scrutinee: [x]  (where x = n % 3)

Matrix:
| 0   →  "divisible by 3"
| 1   →  "remainder 1"
| 2   →  "remainder 2"
| _   →  "unexpected"

리터럴 패턴의 specialization:

리터럴 lit에 대한 specialization S(lit, 0, P):

S(0, 0, P):
| →  "divisible by 3"   (from 0 pattern)
| →  "unexpected"       (from _ pattern)

리터럴 0과 호환되는 rows만 남는다:

• Row 1 (0): 리터럴 0과 일치 → 유지
• Row 2 (1): 리터럴 1 ≠ 0 → 제거
• Row 3 (2): 리터럴 2 ≠ 0 → 제거
• Row 4 (_): Wildcard는 모든 값과 호환 → 유지

리터럴 specialization 후에는 column이 사라진다 (리터럴은 subpatterns가 없음).

리터럴 패턴 vs Constructor 패턴 컴파일

Constructor patterns (유한 set):

// List patterns: {Nil, Cons} = complete set
%tag = llvm.extractvalue %list[0] : !llvm.struct<(i32, ptr)>
%result = scf.index_switch %tag : i32 -> i32
case 0 { /* Nil */ }
case 1 { /* Cons */ }
default { /* unreachable */ }

O(1) dispatch: Tag 값으로 바로 jump.

Literal patterns (무한 set):

// Integer patterns: 0, 1, 2, ... = infinite set
%is_zero = arith.cmpi eq, %x, %c0 : i32
%result = scf.if %is_zero -> i32 {
    scf.yield %zero_result : i32
} else {
    %is_one = arith.cmpi eq, %x, %c1 : i32
    %result1 = scf.if %is_one -> i32 {
        scf.yield %one_result : i32
    } else {
        %is_two = arith.cmpi eq, %x, %c2 : i32
        %result2 = scf.if %is_two -> i32 {
            scf.yield %two_result : i32
        } else {
            scf.yield %default_result : i32
        }
        scf.yield %result2 : i32
    }
    scf.yield %result1 : i32
}

O(n) sequential tests: 각 리터럴을 순서대로 비교.

Decision Tree for Literal Patterns

Example: FizzBuzz remainder check

match (n % 3, n % 5) with
| (0, 0) -> "FizzBuzz"
| (0, _) -> "Fizz"
| (_, 0) -> "Buzz"
| (_, _) -> string_of_int n

Decision tree:

       [n % 3]
          |
    Test: == 0?
      /      \
   Yes        No
   /            \
 [n % 5]      [n % 5]
   |            |
 == 0?        == 0?
  / \          / \
Yes  No      Yes  No
 |    |       |    |
FB   Fizz   Buzz  n

생성된 코드:

%mod3 = arith.remsi %n, %c3 : i32
%mod5 = arith.remsi %n, %c5 : i32

%is_div3 = arith.cmpi eq, %mod3, %c0 : i32
%result = scf.if %is_div3 -> !llvm.ptr<i8> {
    // First column is 0
    %is_div5 = arith.cmpi eq, %mod5, %c0 : i32
    %inner = scf.if %is_div5 -> !llvm.ptr<i8> {
        scf.yield %fizzbuzz : !llvm.ptr<i8>
    } else {
        scf.yield %fizz : !llvm.ptr<i8>
    }
    scf.yield %inner : !llvm.ptr<i8>
} else {
    // First column is not 0
    %is_div5_2 = arith.cmpi eq, %mod5, %c0 : i32
    %inner2 = scf.if %is_div5_2 -> !llvm.ptr<i8> {
        scf.yield %buzz : !llvm.ptr<i8>
    } else {
        %str = func.call @int_to_string(%n) : (i32) -> !llvm.ptr<i8>
        scf.yield %str : !llvm.ptr<i8>
    }
    scf.yield %inner2 : !llvm.ptr<i8>
}

와일드카드 최적화 (Wildcard Optimization)

와일드카드 패턴 _의 핵심 특성:

Wildcard는 어떤 런타임 테스트도 생성하지 않는다.

Example 1: Wildcard in constructor pattern

match list with
| Cons(_, tail) -> length tail + 1
| Nil -> 0

_ vs named variable:

// Case A: Wildcard (no extraction)
| Cons(_, tail) -> ...

// Case B: Named variable (extraction needed)
| Cons(head, tail) -> ...

생성된 코드 비교:

// Case A: Wildcard - head 추출 안 함
case 1 {  // Cons
    // %head = 추출 안 함! (unused)
    %tail_ptr = llvm.getelementptr %data[1] : (!llvm.ptr) -> !llvm.ptr
    %tail = llvm.load %tail_ptr : !llvm.ptr -> !llvm.struct<(i32, ptr)>
    // ...
}

// Case B: Named variable - head 추출 필요
case 1 {  // Cons
    %head = llvm.load %data : !llvm.ptr -> i32  // 추출함
    %tail_ptr = llvm.getelementptr %data[1] : (!llvm.ptr) -> !llvm.ptr
    %tail = llvm.load %tail_ptr : !llvm.ptr -> !llvm.struct<(i32, ptr)>
    // ...
}

Wildcard 최적화 효과:

• 메모리 접근 감소: 불필요한 load 제거
• 레지스터 절약: 사용하지 않는 값을 저장 안 함
• Dead code elimination 촉진: 컴파일러가 더 쉽게 최적화

Example 2: Wildcard as default case

match color_code with
| 0 -> "black"
| 1 -> "white"
| _ -> "unknown"

Wildcard default는 테스트를 생성하지 않는다:

%is_black = arith.cmpi eq, %color, %c0 : i32
%result = scf.if %is_black -> !llvm.ptr<i8> {
    scf.yield %black_str : !llvm.ptr<i8>
} else {
    %is_white = arith.cmpi eq, %color, %c1 : i32
    %result1 = scf.if %is_white -> !llvm.ptr<i8> {
        scf.yield %white_str : !llvm.ptr<i8>
    } else {
        // _ case: NO TEST, just yield
        scf.yield %unknown_str : !llvm.ptr<i8>
    }
    scf.yield %result1 : !llvm.ptr<i8>
}

Default branch에서는 equality test가 없다!

이전 tests가 모두 실패했으면 자동으로 default case가 실행된다.

생성 코드 비교 (Generated Code Comparison)

패턴 종류별 MLIR operation mapping:

Complete example: Mixed patterns

match (list, n) with
| (Nil, _) -> 0
| (Cons(x, _), 0) -> x
| (Cons(x, xs), n) -> x + process xs (n - 1)

Decision tree structure:

        [list]
           |
      Constructor test
        /        \
      Nil       Cons
       |          |
    yield 0    [n]
              Literal test
                /    \
            n==0    n!=0
              |        |
          yield x  yield x + ...

생성된 MLIR (simplified):

// Step 1: Constructor test on list
%list_tag = llvm.extractvalue %list[0] : !llvm.struct<(i32, ptr)>
%tag_index = arith.index_cast %list_tag : i32 to index

%result = scf.index_switch %tag_index : index -> i32
case 0 {  // Nil
    // Wildcard _ on n: NO TEST
    %zero = arith.constant 0 : i32
    scf.yield %zero : i32
}
case 1 {  // Cons
    %data = llvm.extractvalue %list[1] : !llvm.struct<(i32, ptr)>
    %x = llvm.load %data : !llvm.ptr -> i32

    // Step 2: Literal test on n
    %is_zero = arith.cmpi eq, %n, %c0 : i32
    %inner = scf.if %is_zero -> i32 {
        // Literal 0 matched, wildcard _ on tail: NO extraction
        scf.yield %x : i32
    } else {
        // Default case, extract tail for recursion
        %tail_ptr = llvm.getelementptr %data[1] : (!llvm.ptr) -> !llvm.ptr
        %xs = llvm.load %tail_ptr : !llvm.ptr -> !llvm.struct<(i32, ptr)>
        %n_minus_1 = arith.subi %n, %c1 : i32
        %rest = func.call @process(%xs, %n_minus_1) : (...) -> i32
        %sum = arith.addi %x, %rest : i32
        scf.yield %sum : i32
    }
    scf.yield %inner : i32
}

리터럴 패턴 최적화 기회

1. Jump table for dense ranges

리터럴이 0, 1, 2, …와 같이 연속적일 때:

// Before: Sequential tests
%is_0 = arith.cmpi eq, %x, %c0
scf.if %is_0 { ... } else {
    %is_1 = arith.cmpi eq, %x, %c1
    scf.if %is_1 { ... } else { ... }
}

// After: Range check + index_switch
%in_range = arith.cmpi ult, %x, %c3 : i32
scf.if %in_range {
    %idx = arith.index_cast %x : i32 to index
    scf.index_switch %idx {
        case 0 { ... }
        case 1 { ... }
        case 2 { ... }
    }
} else {
    // default
}

2. LLVM switch optimization

LLVM backend는 sequential comparisons를 자동으로 switch instruction으로 변환할 수 있다:

; Input: sequential icmp + br
%cmp0 = icmp eq i32 %x, 0
br i1 %cmp0, label %case0, label %check1
check1:
%cmp1 = icmp eq i32 %x, 1
br i1 %cmp1, label %case1, label %default

; Optimized: switch instruction
switch i32 %x, label %default [
    i32 0, label %case0
    i32 1, label %case1
]

3. Guard patterns (future)

리터럴 테스트와 predicate guard를 결합:

match x with
| n when n > 0 && n < 100 -> "small positive"
| n when n >= 100 -> "large positive"
| _ -> "non-positive"

이런 guard patterns는 Phase 7 이후에 다룰 수 있다.

Wildcard Specialization 규칙 상세

Wildcard expansion for different constructor arities:

Example: Option type

type 'a option = None | Some of 'a

match opt with
| Some x -> x + 1
| _ -> 0

Specialization of _ on Some:

Original:
| Some x  →  x + 1
| _       →  0

S(Some, 0, P):
| x  →  x + 1    (from Some x)
| _  →  0        (from _, expanded to Some _)

Wildcard는 어떤 constructor와도 호환된다!

Key Takeaways

1. 리터럴 패턴은 equality tests를 생성한다 (arith.cmpi eq)
2. Constructor 패턴은 tag switch를 생성한다 (scf.index_switch)
3. Wildcard는 테스트를 생성하지 않는다 (fallthrough/binding only)
4. 리터럴 set이 연속적이면 switch 최적화 가능
5. Wildcard default는 마지막 else branch로 컴파일
6. Named variables와 wildcards는 semantics만 다름 (binding vs no binding)

Summary and Next Steps

Chapter 17 핵심 개념 정리

1. Pattern Matrix Representation

• Rows = pattern clauses
• Columns = scrutinees
• Cells = patterns (wildcard, constructor, literal)
• Occurrence vectors = access paths to values

2. Decision Tree Structure

• Internal nodes = tests (constructor, literal)
• Edges = outcomes (Nil, Cons, default)
• Leaves = actions (success, failure)
• Property: Each subterm tested at most once

3. Specialization Operation

• Filters rows compatible with constructor
• Expands constructor patterns to subpatterns
• Updates occurrence vector with subpaths
• Formula: S(c, i, P) = specialized matrix

4. Defaulting Operation

• Keeps only wildcard rows
• Removes tested column
• Detects non-exhaustiveness (empty result)
• Formula: D(i, P) = default matrix

5. Compilation Algorithm

• Recursive function: compile(P, π) = DecisionTree
• Base cases: empty (failure), irrefutable (success)
• Recursive case: select column, specialize, default
• Heuristics: column selection strategy

6. Exhaustiveness Checking

• Empty matrix = non-exhaustive match
• Complete constructor sets = no default needed
• Natural integration with compilation
• Error reporting from failure leaves

Decision Tree Algorithm의 장점 요약

Efficiency:

• O(d) tests (d = pattern depth), not O(n × d)
• Each subterm tested exactly once
• No redundant comparisons

Correctness:

• Respects pattern order (first-match semantics)
• Handles nested patterns systematically
• Works with any constructor arity

Verification:

• Exhaustiveness checking built-in
• Detects missing cases at compile time
• Identifies unreachable patterns

Optimization:

• Structured representation enables optimizations
• Column selection heuristics improve code quality
• Complete constructor sets eliminate default branches

Pattern Matrix Workflow

전체 과정 요약:

1. FunLang match expression
   ↓
2. Pattern matrix + occurrence vector
   ↓
3. Recursive compilation algorithm
   ├─ Specialization (constructor tests)
   ├─ Defaulting (wildcard cases)
   └─ Column selection (heuristic)
   ↓
4. Decision tree
   ↓
5. MLIR IR (scf.index_switch, scf.if)
   ↓
6. LLVM IR (switch, br)

Connection to MLIR Lowering

Chapter 17 (theory) → Chapter 19 (implementation):

Pattern matrix → funlang.match operation:

%result = funlang.match %list : !funlang.list<i32> -> i32 {
^nil:
    %zero = arith.constant 0 : i32
    funlang.yield %zero : i32
^cons(%head: i32, %tail: !funlang.list<i32>):
    %one = arith.constant 1 : i32
    %len_tail = func.call @length(%tail) : (!funlang.list<i32>) -> i32
    %result = arith.addi %one, %len_tail : i32
    funlang.yield %result : i32
}

Decision tree → SCF dialect:

%tag = llvm.extractvalue %list[0] : !llvm.struct<(i32, ptr)>
%result = scf.index_switch %tag : i32 -> i32
case 0 { ... }  // Nil branch
case 1 { ... }  // Cons branch

Specialization → Region block arguments:

^cons(%head: i32, %tail: !funlang.list<i32>):
// Block arguments = pattern variables from specialization

Exhaustiveness → Verification:

LogicalResult FunLang::MatchOp::verify() {
    // Check all constructor cases are present or wildcard exists
    if (!isExhaustive()) {
        return emitOpError("non-exhaustive pattern match");
    }
    return success();
}

Chapter 18-20 Preview

Chapter 18: List Operations

• funlang.nil operation: Create empty list
• funlang.cons operation: Prepend element to list
• !funlang.list<T> type: Parameterized list type
• LLVM representation: !llvm.struct<(i32, ptr)> with tag
• Heap allocation with GC_malloc

Chapter 19: Match Compilation

• funlang.match operation: Region-based pattern matching
• Region block arguments for pattern variables
• Lowering to SCF dialect (scf.index_switch)
• OpConversionPattern with region handling
• Type conversion for !funlang.list<T>

Chapter 20: Functional Programs

• Complete examples: map, filter, fold
• List manipulation functions
• Recursive list traversal
• Higher-order functions on lists
• Performance analysis

Practice Questions

이 장을 이해했는지 확인하는 질문들:

Q1: Pattern matrix의 각 요소는 무엇을 의미하는가?

Q2: Specialization이 Cons(x, Nil) pattern을 어떻게 변환하는가?

Q3: Defaulting 후 empty matrix는 무엇을 의미하는가?

Q4: Decision tree가 if-else chain보다 효율적인 이유는?

Q5: Column selection heuristic이 왜 필요한가?

성공 기준 달성 확인

이 장의 목표를 모두 달성했는가?

• Pattern matrix 표현법을 이해한다

  • Rows, columns, occurrences 개념 설명
  • Example matrices with nested patterns

• Decision tree 알고리즘의 동작 원리를 안다

  • Recursive compilation function
  • Base cases (empty, irrefutable)
  • Recursive case (specialize, default)

• Specialization과 defaulting 연산을 설명할 수 있다

  • Specialization: constructor assumption + decomposition
  • Defaulting: wildcard filtering + column removal
  • Occurrence vector updates

• Exhaustiveness checking이 어떻게 동작하는지 안다

  • Empty matrix detection
  • Complete constructor sets
  • Error reporting strategies

• Chapter 18-19에서 MLIR 구현을 시작할 준비가 된다

  • Pattern matrix → funlang.match operation mapping
  • Decision tree → SCF dialect lowering
  • Specialization → Region block arguments

Next chapter: Let’s build the foundation for pattern matching—list data structures!