Scapegoat TIL

DEV - Building a Pattern Matcher in Go: Lessons from PAIP

I used o1-preview and claude to build a pattern matcher in Go, inspired by Peter Norvig's PAIP (Paradigms of Artificial Intelligence Programming). The goal was to create a flexible system for matching structured patterns against data while capturing variable bindings.

Add pat-match experiment

Core Concepts

The matcher supports several pattern types:

type Pattern interface {
    Match(input interface{}, bindings Bindings) (Bindings, error)
}

// Variables like ?x match and bind any value
type VariablePattern struct {
    Name string
}

// Constants match exact values
type ConstantPattern struct {
    Value interface{}
}

// Sequences match ordered lists of patterns
type ListPattern struct {
    Patterns []Pattern
}

Pattern DSL

To make patterns readable, I created a small DSL:

// Match: (a ?x c) against (a b c)
pattern := Seq(
    Const("a"),
    Var("?x"),
    Const("c"),
)

The real power comes from segment patterns that match variable-length sequences:

// Match: (a ?*x d) against (a b c d)
// Binds ?x to (b c)
pattern := Seq(
    Const("a"),
    Seg("?x", Seq(Const("d")), 0),
)

Key Challenges

1. Type Handling

Go's type system required careful handling of slices and interface{}. The solution was to normalize inputs:

func (p *ListPattern) Match(input interface{}, bindings Bindings) (Bindings, error) {
    var inputList []interface{}
    switch v := input.(type) {
    case []interface{}:
        inputList = v
    case []string:
        inputList = make([]interface{}, len(v))
        for i, s := range v {
            inputList[i] = s
        }
    default:
        // Handle other slice types via reflection
    }
    return matchList(p.Patterns, inputList, bindings)
}

2. Segment Pattern Backtracking

Segment patterns like ?* required trying different splits of the input. The key was maintaining state through bindings:

func (p *SegmentPattern) Match(input []interface{}, bindings Bindings) (Bindings, error) {
    for i := p.Min; i <= len(input); i++ {
        segment := input[:i]
        rest := input[i:]
        
        newBindings := copyBindings(bindings)
        newBindings[p.VarName] = segment
        
        if b, err := p.Rest.Match(rest, newBindings); err == nil {
            return b, nil
        }
    }
    return nil, fmt.Errorf("no valid split found")
}

3. Predicate Integration

Adding predicates allowed for powerful runtime checks:

// Match: (?x > ?y (?if (> ?x ?y)))
pattern := Seq(
    Var("?x"),
    Const(">"),
    Var("?y"),
    SingleWithPredicate("?if", func(input interface{}, bindings Bindings) bool {
        x := bindings["?x"].(int)
        y := bindings["?y"].(int)
        return x > y
    }),
)

Testing Approach

Testing focused on composing patterns of increasing complexity:

func TestPatMatch(t *testing.T) {
    tests := []struct {
        name        string
        pattern     Pattern
        input       interface{}
        wantMatch   bool
        wantBinding Bindings
    }{
        {
            name:        "Simple variable",
            pattern:     Var("?x"),
            input:      "hello",
            wantMatch:   true,
            wantBinding: Bindings{"?x": "hello"},
        },
        // More complex cases...
    }
    // ...
}

Lessons Learned

  1. Start Simple: Building from basic patterns to complex ones helped manage complexity.
  2. Type System Matters: Go's type system required more explicit handling than Lisp's.
  3. State Management: Copying bindings prevented subtle bugs in backtracking.
  4. Testing Edge Cases: Pattern matching needs comprehensive testing of edge cases.

The complete implementation is available at go-go-labs/cmd/experiments/pat-match.

Next steps include adding pattern compilation for better performance and supporting more complex matching strategies.