Interpreter Pattern #

A monitoring system needs to accept filter queries from users like status == "active" AND age > 25 AND city IN ["Jakarta", "Bandung"]. This query is not a static string — it can change at any time, can be stored in a database, and can be composed dynamically. You cannot hardcode every possible combination. The Interpreter Pattern provides the solution: define a grammar for the filter language, build a parser that turns the string into a tree of expression objects, and evaluate that tree against the data at hand. Each operator (==, >, AND, IN) becomes a class that knows how to evaluate itself. Adding a new operator means adding one new class — without changing the existing operator classes.

What Is the Interpreter Pattern? #

The Interpreter Pattern is a behavioral design pattern that defines a grammar representation for a language, and provides an interpreter to interpret sentences in that language. Each grammar rule is represented as a class, and sentences in the language are represented as an Abstract Syntax Tree (AST) of those objects.

Three core components of the Interpreter Pattern:

Abstract Expression — the interface defining the Interpret operation
Terminal Expression — a leaf expression representing a value or variable; contains no other expressions
Non-terminal Expression — an expression containing one or more other expressions; represents a recursive grammar rule

The Interpreter Pattern is the foundation of: query languages, template engines, rule engines, expression calculators, DSL-based configuration, and many other parsing systems.

flowchart TD
    subgraph "Input: Query String"
        Q["&quot;status == active AND age > 25&quot;"]
    end

    subgraph "Parse → AST"
        AND[AndExpression]
        EQ[EqualsExpression\\nstatus = active]
        GT[GreaterThanExpression\\nage > 25]
        AND --> EQ
        AND --> GT
    end

    subgraph "Evaluate with Context"
        CTX["Context: {status: active, age: 30}"]
        RES["Result: true"]
    end

    Q -->|parse| AND
    AND -->|interpret ctx| RES
    CTX --> RES

Grammar and Expression Tree #

Before writing code, it is important to understand the grammar to be implemented. The grammar formally defines the rules of the language.

Grammar for a simple filter query:

expression     = or_expression
or_expression  = and_expression ("OR" and_expression)*
and_expression = comparison ("AND" comparison)*
comparison     = identifier operator value
               | "NOT" comparison
               | "(" expression ")"
operator       = "==" | "!=" | ">" | ">=" | "<" | "<=" | "IN" | "CONTAINS"
value          = string | number | boolean | array
identifier     = [a-zA-Z_][a-zA-Z0-9_.]*

Each grammar line becomes one or several Expression classes:

Grammar Rule	Expression Class
`or_expression`	`OrExpression`
`and_expression`	`AndExpression`
`NOT comparison`	`NotExpression`
`identifier == value`	`EqualsExpression`
`identifier > value`	`GreaterThanExpression`
`identifier IN array`	`InExpression`
`identifier`	`FieldExpression`
`value` (literal)	`LiteralExpression`

Full Implementation: Filter Query Engine #

Context and Abstract Expression #

package filter

import (
    "fmt"
    "strings"
)

// Context stores the data to be evaluated against expressions.
// This is the "environment" during interpretation.
type Context map[string]interface{}

// Get retrieves a field value from the context, supporting dot notation (user.age).
func (c Context) Get(field string) (interface{}, bool) {
    parts := strings.SplitN(field, ".", 2)
    val, ok := c[parts[0]]
    if !ok || len(parts) == 1 {
        return val, ok
    }
    // Navigate nested fields
    if nested, ok := val.(map[string]interface{}); ok {
        return Context(nested).Get(parts[1])
    }
    return nil, false
}

// Expression is the Abstract Expression — the interface for all expressions.
type Expression interface {
    // Interpret evaluates the expression in the given context.
    Interpret(ctx Context) (bool, error)

    // String returns a string representation of the expression for debugging.
    String() string
}

Terminal Expressions #

package filter

import (
    "fmt"
    "reflect"
    "strconv"
    "strings"
)

// LiteralExpression represents a constant value (string, number, bool).
type LiteralExpression struct {
    Value interface{}
}

func (e *LiteralExpression) Interpret(ctx Context) (bool, error) {
    // A literal cannot be interpreted as bool directly
    // It is used as an operand in comparison expressions
    return false, fmt.Errorf("literal expression cannot be interpreted directly")
}

func (e *LiteralExpression) String() string {
    return fmt.Sprintf("%v", e.Value)
}

// getValue returns the literal value for use by the parent expression.
func (e *LiteralExpression) getValue() interface{} { return e.Value }


// FieldExpression accesses a field value from the context.
type FieldExpression struct {
    FieldName string
}

func (e *FieldExpression) Interpret(ctx Context) (bool, error) {
    val, ok := ctx.Get(e.FieldName)
    if !ok {
        return false, nil
    }
    if b, ok := val.(bool); ok {
        return b, nil
    }
    return false, fmt.Errorf("field %s is not boolean", e.FieldName)
}

func (e *FieldExpression) String() string { return e.FieldName }

func (e *FieldExpression) getValue(ctx Context) interface{} {
    val, _ := ctx.Get(e.FieldName)
    return val
}


// EqualsExpression evaluates field == value.
type EqualsExpression struct {
    Field string
    Value interface{}
}

func NewEqualsExpression(field string, value interface{}) Expression {
    return &EqualsExpression{Field: field, Value: value}
}

func (e *EqualsExpression) Interpret(ctx Context) (bool, error) {
    fieldVal, ok := ctx.Get(e.Field)
    if !ok {
        return e.Value == nil, nil
    }
    return reflect.DeepEqual(fieldVal, e.Value), nil
}

func (e *EqualsExpression) String() string {
    return fmt.Sprintf("%s == %v", e.Field, e.Value)
}


// NotEqualsExpression evaluates field != value.
type NotEqualsExpression struct {
    Field string
    Value interface{}
}

func NewNotEqualsExpression(field string, value interface{}) Expression {
    return &NotEqualsExpression{Field: field, Value: value}
}

func (e *NotEqualsExpression) Interpret(ctx Context) (bool, error) {
    eq := &EqualsExpression{Field: e.Field, Value: e.Value}
    result, err := eq.Interpret(ctx)
    return !result, err
}

func (e *NotEqualsExpression) String() string {
    return fmt.Sprintf("%s != %v", e.Field, e.Value)
}


// GreaterThanExpression evaluates field > value.
type GreaterThanExpression struct {
    Field string
    Value float64
}

func NewGreaterThanExpression(field string, value float64) Expression {
    return &GreaterThanExpression{Field: field, Value: value}
}

func (e *GreaterThanExpression) Interpret(ctx Context) (bool, error) {
    fieldVal, ok := ctx.Get(e.Field)
    if !ok {
        return false, nil
    }
    num, err := toNumber(fieldVal)
    if err != nil {
        return false, fmt.Errorf("field %s: %w", e.Field, err)
    }
    return num > e.Value, nil
}

func (e *GreaterThanExpression) String() string {
    return fmt.Sprintf("%s > %v", e.Field, e.Value)
}


// LessThanExpression evaluates field < value.
type LessThanExpression struct {
    Field string
    Value float64
}

func NewLessThanExpression(field string, value float64) Expression {
    return &LessThanExpression{Field: field, Value: value}
}

func (e *LessThanExpression) Interpret(ctx Context) (bool, error) {
    fieldVal, ok := ctx.Get(e.Field)
    if !ok {
        return false, nil
    }
    num, err := toNumber(fieldVal)
    if err != nil {
        return false, fmt.Errorf("field %s: %w", e.Field, err)
    }
    return num < e.Value, nil
}

func (e *LessThanExpression) String() string {
    return fmt.Sprintf("%s < %v", e.Field, e.Value)
}


// InExpression evaluates field IN [value1, value2, ...].
type InExpression struct {
    Field  string
    Values []interface{}
}

func NewInExpression(field string, values []interface{}) Expression {
    return &InExpression{Field: field, Values: values}
}

func (e *InExpression) Interpret(ctx Context) (bool, error) {
    fieldVal, ok := ctx.Get(e.Field)
    if !ok {
        return false, nil
    }
    for _, v := range e.Values {
        if reflect.DeepEqual(fieldVal, v) {
            return true, nil
        }
    }
    return false, nil
}

func (e *InExpression) String() string {
    vals := make([]string, len(e.Values))
    for i, v := range e.Values {
        vals[i] = fmt.Sprintf("%v", v)
    }
    return fmt.Sprintf("%s IN [%s]", e.Field, strings.Join(vals, ", "))
}


// ContainsExpression evaluates whether a string field contains a substring.
type ContainsExpression struct {
    Field     string
    Substring string
}

func NewContainsExpression(field, substring string) Expression {
    return &ContainsExpression{Field: field, Substring: substring}
}

func (e *ContainsExpression) Interpret(ctx Context) (bool, error) {
    fieldVal, ok := ctx.Get(e.Field)
    if !ok {
        return false, nil
    }
    str, ok := fieldVal.(string)
    if !ok {
        return false, fmt.Errorf("field %s is not a string", e.Field)
    }
    return strings.Contains(str, e.Substring), nil
}

func (e *ContainsExpression) String() string {
    return fmt.Sprintf("%s CONTAINS %q", e.Field, e.Substring)
}

func toNumber(v interface{}) (float64, error) {
    switch val := v.(type) {
    case float64:
        return val, nil
    case float32:
        return float64(val), nil
    case int:
        return float64(val), nil
    case int64:
        return float64(val), nil
    case string:
        n, err := strconv.ParseFloat(val, 64)
        if err != nil {
            return 0, fmt.Errorf("cannot convert %q to number", val)
        }
        return n, nil
    }
    return 0, fmt.Errorf("cannot convert %T to number", v)
}

Non-terminal Expressions #

package filter

import "fmt"

// AndExpression evaluates left AND right.
// Non-terminal: contains two other expressions.
type AndExpression struct {
    Left  Expression
    Right Expression
}

func NewAndExpression(left, right Expression) Expression {
    return &AndExpression{Left: left, Right: right}
}

func (e *AndExpression) Interpret(ctx Context) (bool, error) {
    // Short-circuit evaluation: if the left is false, no need to evaluate the right
    left, err := e.Left.Interpret(ctx)
    if err != nil {
        return false, fmt.Errorf("AND left: %w", err)
    }
    if !left {
        return false, nil // short-circuit
    }

    right, err := e.Right.Interpret(ctx)
    if err != nil {
        return false, fmt.Errorf("AND right: %w", err)
    }
    return right, nil
}

func (e *AndExpression) String() string {
    return fmt.Sprintf("(%s AND %s)", e.Left.String(), e.Right.String())
}


// OrExpression evaluates left OR right.
type OrExpression struct {
    Left  Expression
    Right Expression
}

func NewOrExpression(left, right Expression) Expression {
    return &OrExpression{Left: left, Right: right}
}

func (e *OrExpression) Interpret(ctx Context) (bool, error) {
    // Short-circuit: if the left is true, no need to evaluate the right
    left, err := e.Left.Interpret(ctx)
    if err != nil {
        return false, fmt.Errorf("OR left: %w", err)
    }
    if left {
        return true, nil // short-circuit
    }

    right, err := e.Right.Interpret(ctx)
    if err != nil {
        return false, fmt.Errorf("OR right: %w", err)
    }
    return right, nil
}

func (e *OrExpression) String() string {
    return fmt.Sprintf("(%s OR %s)", e.Left.String(), e.Right.String())
}


// NotExpression evaluates NOT expression.
type NotExpression struct {
    Expr Expression
}

func NewNotExpression(expr Expression) Expression {
    return &NotExpression{Expr: expr}
}

func (e *NotExpression) Interpret(ctx Context) (bool, error) {
    result, err := e.Expr.Interpret(ctx)
    if err != nil {
        return false, fmt.Errorf("NOT: %w", err)
    }
    return !result, nil
}

func (e *NotExpression) String() string {
    return fmt.Sprintf("(NOT %s)", e.Expr.String())
}

Parser: Turning a String into an Expression Tree #

package filter

import (
    "fmt"
    "strconv"
    "strings"
    "unicode"
)

// Token represents one lexical unit in the query string.
type Token struct {
    Type  TokenType
    Value string
}

type TokenType int

const (
    TOKEN_IDENTIFIER TokenType = iota
    TOKEN_STRING
    TOKEN_NUMBER
    TOKEN_BOOL
    TOKEN_AND
    TOKEN_OR
    TOKEN_NOT
    TOKEN_IN
    TOKEN_CONTAINS
    TOKEN_EQ
    TOKEN_NEQ
    TOKEN_GT
    TOKEN_GTE
    TOKEN_LT
    TOKEN_LTE
    TOKEN_LPAREN
    TOKEN_RPAREN
    TOKEN_LBRACKET
    TOKEN_RBRACKET
    TOKEN_COMMA
    TOKEN_EOF
)

// Lexer breaks a query string into tokens.
type Lexer struct {
    input []rune
    pos   int
}

func NewLexer(input string) *Lexer {
    return &Lexer{input: []rune(input)}
}

func (l *Lexer) skipWhitespace() {
    for l.pos < len(l.input) && unicode.IsSpace(l.input[l.pos]) {
        l.pos++
    }
}

func (l *Lexer) NextToken() Token {
    l.skipWhitespace()
    if l.pos >= len(l.input) {
        return Token{Type: TOKEN_EOF}
    }

    ch := l.input[l.pos]

    // String literal
    if ch == '"' || ch == '\'' {
        return l.readString(ch)
    }

    // Number
    if unicode.IsDigit(ch) || (ch == '-' && l.pos+1 < len(l.input) && unicode.IsDigit(l.input[l.pos+1])) {
        return l.readNumber()
    }

    // Operators
    switch ch {
    case '(':
        l.pos++
        return Token{Type: TOKEN_LPAREN, Value: "("}
    case ')':
        l.pos++
        return Token{Type: TOKEN_RPAREN, Value: ")"}
    case '[':
        l.pos++
        return Token{Type: TOKEN_LBRACKET, Value: "["}
    case ']':
        l.pos++
        return Token{Type: TOKEN_RBRACKET, Value: "]"}
    case ',':
        l.pos++
        return Token{Type: TOKEN_COMMA, Value: ","}
    case '=':
        if l.pos+1 < len(l.input) && l.input[l.pos+1] == '=' {
            l.pos += 2
            return Token{Type: TOKEN_EQ, Value: "=="}
        }
    case '!':
        if l.pos+1 < len(l.input) && l.input[l.pos+1] == '=' {
            l.pos += 2
            return Token{Type: TOKEN_NEQ, Value: "!="}
        }
    case '>':
        if l.pos+1 < len(l.input) && l.input[l.pos+1] == '=' {
            l.pos += 2
            return Token{Type: TOKEN_GTE, Value: ">="}
        }
        l.pos++
        return Token{Type: TOKEN_GT, Value: ">"}
    case '<':
        if l.pos+1 < len(l.input) && l.input[l.pos+1] == '=' {
            l.pos += 2
            return Token{Type: TOKEN_LTE, Value: "<="}
        }
        l.pos++
        return Token{Type: TOKEN_LT, Value: "<"}
    }

    // Identifier or keyword
    if unicode.IsLetter(ch) || ch == '_' {
        return l.readIdentifierOrKeyword()
    }

    l.pos++
    return Token{Type: TOKEN_EOF}
}

func (l *Lexer) readString(quote rune) Token {
    l.pos++ // skip opening quote
    start := l.pos
    for l.pos < len(l.input) && l.input[l.pos] != quote {
        l.pos++
    }
    value := string(l.input[start:l.pos])
    if l.pos < len(l.input) {
        l.pos++ // skip closing quote
    }
    return Token{Type: TOKEN_STRING, Value: value}
}

func (l *Lexer) readNumber() Token {
    start := l.pos
    if l.input[l.pos] == '-' {
        l.pos++
    }
    for l.pos < len(l.input) && (unicode.IsDigit(l.input[l.pos]) || l.input[l.pos] == '.') {
        l.pos++
    }
    return Token{Type: TOKEN_NUMBER, Value: string(l.input[start:l.pos])}
}

func (l *Lexer) readIdentifierOrKeyword() Token {
    start := l.pos
    for l.pos < len(l.input) && (unicode.IsLetter(l.input[l.pos]) || unicode.IsDigit(l.input[l.pos]) || l.input[l.pos] == '_' || l.input[l.pos] == '.') {
        l.pos++
    }
    value := string(l.input[start:l.pos])
    upper := strings.ToUpper(value)

    switch upper {
    case "AND":
        return Token{Type: TOKEN_AND, Value: "AND"}
    case "OR":
        return Token{Type: TOKEN_OR, Value: "OR"}
    case "NOT":
        return Token{Type: TOKEN_NOT, Value: "NOT"}
    case "IN":
        return Token{Type: TOKEN_IN, Value: "IN"}
    case "CONTAINS":
        return Token{Type: TOKEN_CONTAINS, Value: "CONTAINS"}
    case "TRUE":
        return Token{Type: TOKEN_BOOL, Value: "true"}
    case "FALSE":
        return Token{Type: TOKEN_BOOL, Value: "false"}
    default:
        return Token{Type: TOKEN_IDENTIFIER, Value: value}
    }
}

// Parser turns a token stream into an Expression tree using recursive descent.
type Parser struct {
    lexer   *Lexer
    current Token
}

func NewParser(query string) *Parser {
    p := &Parser{lexer: NewLexer(query)}
    p.current = p.lexer.NextToken() // load the first token
    return p
}

func (p *Parser) consume() Token {
    tok := p.current
    p.current = p.lexer.NextToken()
    return tok
}

// Parse produces an Expression tree from the query.
func (p *Parser) Parse() (Expression, error) {
    return p.parseOr()
}

func (p *Parser) parseOr() (Expression, error) {
    left, err := p.parseAnd()
    if err != nil {
        return nil, err
    }

    for p.current.Type == TOKEN_OR {
        p.consume()
        right, err := p.parseAnd()
        if err != nil {
            return nil, err
        }
        left = NewOrExpression(left, right)
    }
    return left, nil
}

func (p *Parser) parseAnd() (Expression, error) {
    left, err := p.parseComparison()
    if err != nil {
        return nil, err
    }

    for p.current.Type == TOKEN_AND {
        p.consume()
        right, err := p.parseComparison()
        if err != nil {
            return nil, err
        }
        left = NewAndExpression(left, right)
    }
    return left, nil
}

func (p *Parser) parseComparison() (Expression, error) {
    // NOT expression
    if p.current.Type == TOKEN_NOT {
        p.consume()
        expr, err := p.parseComparison()
        if err != nil {
            return nil, err
        }
        return NewNotExpression(expr), nil
    }

    // Parenthesized expression
    if p.current.Type == TOKEN_LPAREN {
        p.consume()
        expr, err := p.parseOr()
        if err != nil {
            return nil, err
        }
        if p.current.Type != TOKEN_RPAREN {
            return nil, fmt.Errorf("expected ), got %q", p.current.Value)
        }
        p.consume()
        return expr, nil
    }

    // identifier operator value
    if p.current.Type != TOKEN_IDENTIFIER {
        return nil, fmt.Errorf("expected identifier, got %q", p.current.Value)
    }
    field := p.consume().Value

    switch p.current.Type {
    case TOKEN_EQ:
        p.consume()
        value, err := p.parseValue()
        if err != nil {
            return nil, err
        }
        return NewEqualsExpression(field, value), nil

    case TOKEN_NEQ:
        p.consume()
        value, err := p.parseValue()
        if err != nil {
            return nil, err
        }
        return NewNotEqualsExpression(field, value), nil

    case TOKEN_GT:
        p.consume()
        num, err := p.parseNumber()
        if err != nil {
            return nil, err
        }
        return NewGreaterThanExpression(field, num), nil

    case TOKEN_LT:
        p.consume()
        num, err := p.parseNumber()
        if err != nil {
            return nil, err
        }
        return NewLessThanExpression(field, num), nil

    case TOKEN_IN:
        p.consume()
        values, err := p.parseArray()
        if err != nil {
            return nil, err
        }
        return NewInExpression(field, values), nil

    case TOKEN_CONTAINS:
        p.consume()
        if p.current.Type != TOKEN_STRING {
            return nil, fmt.Errorf("CONTAINS requires string value")
        }
        substring := p.consume().Value
        return NewContainsExpression(field, substring), nil
    }

    return nil, fmt.Errorf("unexpected token %q after identifier %q", p.current.Value, field)
}

func (p *Parser) parseValue() (interface{}, error) {
    switch p.current.Type {
    case TOKEN_STRING:
        return p.consume().Value, nil
    case TOKEN_NUMBER:
        num, err := strconv.ParseFloat(p.consume().Value, 64)
        if err != nil {
            return nil, fmt.Errorf("invalid number: %w", err)
        }
        return num, nil
    case TOKEN_BOOL:
        val := p.consume().Value == "true"
        return val, nil
    }
    return nil, fmt.Errorf("expected value, got %q", p.current.Value)
}

func (p *Parser) parseNumber() (float64, error) {
    if p.current.Type != TOKEN_NUMBER {
        return 0, fmt.Errorf("expected number, got %q", p.current.Value)
    }
    return strconv.ParseFloat(p.consume().Value, 64)
}

func (p *Parser) parseArray() ([]interface{}, error) {
    if p.current.Type != TOKEN_LBRACKET {
        return nil, fmt.Errorf("expected [, got %q", p.current.Value)
    }
    p.consume()

    var values []interface{}
    for p.current.Type != TOKEN_RBRACKET && p.current.Type != TOKEN_EOF {
        val, err := p.parseValue()
        if err != nil {
            return nil, err
        }
        values = append(values, val)

        if p.current.Type == TOKEN_COMMA {
            p.consume()
        }
    }

    if p.current.Type != TOKEN_RBRACKET {
        return nil, fmt.Errorf("expected ], got EOF")
    }
    p.consume()
    return values, nil
}

// ParseQuery is a helper function to parse and return an Expression.
func ParseQuery(query string) (Expression, error) {
    parser := NewParser(query)
    return parser.Parse()
}

Query Engine: Putting It All Together #

package filter

// QueryEngine evaluates queries against a collection of data.
type QueryEngine struct {
    cache map[string]Expression // cache of parsed expressions
}

func NewQueryEngine() *QueryEngine {
    return &QueryEngine{cache: make(map[string]Expression)}
}

// Filter evaluates a query against every item in the slice.
func (e *QueryEngine) Filter(items []Context, query string) ([]Context, error) {
    // Parse the query (with caching)
    expr, ok := e.cache[query]
    if !ok {
        var err error
        expr, err = ParseQuery(query)
        if err != nil {
            return nil, fmt.Errorf("invalid query: %w", err)
        }
        e.cache[query] = expr
    }

    var results []Context
    for _, item := range items {
        match, err := expr.Interpret(item)
        if err != nil {
            return nil, fmt.Errorf("evaluation error: %w", err)
        }
        if match {
            results = append(results, item)
        }
    }
    return results, nil
}

// Demonstration
func main() {
    engine := NewQueryEngine()

    users := []Context{
        {"name": "Alice", "age": float64(28), "city": "Jakarta", "status": "active"},
        {"name": "Bob",   "age": float64(35), "city": "Surabaya", "status": "inactive"},
        {"name": "Citra", "age": float64(22), "city": "Bandung",  "status": "active"},
        {"name": "Dani",  "age": float64(45), "city": "Jakarta",  "status": "active"},
        {"name": "Eka",   "age": float64(17), "city": "Medan",    "status": "active"},
    }

    queries := []string{
        `status == "active" AND age > 25`,
        `city IN ["Jakarta", "Bandung"]`,
        `status == "active" AND age > 20 AND NOT city == "Medan"`,
        `name CONTAINS "a"`,
    }

    for _, q := range queries {
        results, err := engine.Filter(users, q)
        if err != nil {
            fmt.Printf("Error: %v\n", err)
            continue
        }
        names := make([]string, len(results))
        for i, r := range results {
            names[i] = r["name"].(string)
        }
        fmt.Printf("Query: %s\nResult: %v\n\n", q, names)
    }
}

Output:

Query: status == "active" AND age > 25
Result: [Alice Dani]

Query: city IN ["Jakarta", "Bandung"]
Result: [Alice Citra Dani]

Query: status == "active" AND age > 20 AND NOT city == "Medan"
Result: [Alice Citra Dani]

Query: name CONTAINS "a"
Result: [Alice Citra Dani Eka]

Testing the Interpreter Pattern #

func TestEqualsExpression(t *testing.T) {
    expr := NewEqualsExpression("status", "active")
    ctx := Context{"status": "active"}
    result, err := expr.Interpret(ctx)
    if err != nil || !result {
        t.Errorf("expected true, got %v (err: %v)", result, err)
    }

    ctx2 := Context{"status": "inactive"}
    result2, _ := expr.Interpret(ctx2)
    if result2 {
        t.Error("expected false for non-matching value")
    }
}

func TestAndExpression_ShortCircuit(t *testing.T) {
    called := false
    // Expression that records whether it was called
    rightExpr := &EqualsExpression{Field: "trigger", Value: "yes"}
    andExpr := NewAndExpression(
        NewEqualsExpression("status", "inactive"), // false — short circuit
        rightExpr,
    )

    ctx := Context{"status": "active", "trigger": "yes"}
    result, _ := andExpr.Interpret(ctx)
    if result {
        t.Error("AND with false left should be false")
    }
    _ = called // in a real implementation, verify rightExpr is not evaluated
}

func TestInExpression(t *testing.T) {
    expr := NewInExpression("city", []interface{}{"Jakarta", "Bandung"})

    tests := []struct {
        city     string
        expected bool
    }{
        {"Jakarta", true},
        {"Bandung", true},
        {"Surabaya", false},
    }

    for _, tt := range tests {
        ctx := Context{"city": tt.city}
        result, err := expr.Interpret(ctx)
        if err != nil {
            t.Fatalf("unexpected error: %v", err)
        }
        if result != tt.expected {
            t.Errorf("city=%s: expected %v, got %v", tt.city, tt.expected, result)
        }
    }
}

func TestParser_ComplexQuery(t *testing.T) {
    query := `status == "active" AND age > 25`
    expr, err := ParseQuery(query)
    if err != nil {
        t.Fatalf("parse failed: %v", err)
    }

    activeOld := Context{"status": "active", "age": float64(30)}
    result, _ := expr.Interpret(activeOld)
    if !result {
        t.Error("expected true for active user age 30")
    }

    activeYoung := Context{"status": "active", "age": float64(20)}
    result, _ = expr.Interpret(activeYoung)
    if result {
        t.Error("expected false for active user age 20")
    }

    inactiveOld := Context{"status": "inactive", "age": float64(30)}
    result, _ = expr.Interpret(inactiveOld)
    if result {
        t.Error("expected false for inactive user")
    }
}

func TestParser_NotExpression(t *testing.T) {
    expr, err := ParseQuery(`NOT status == "inactive"`)
    if err != nil {
        t.Fatalf("parse failed: %v", err)
    }

    ctx := Context{"status": "active"}
    result, _ := expr.Interpret(ctx)
    if !result {
        t.Error("NOT inactive should be true for active status")
    }
}

func TestParser_OrExpression(t *testing.T) {
    expr, err := ParseQuery(`city == "Jakarta" OR city == "Bandung"`)
    if err != nil {
        t.Fatalf("parse failed: %v", err)
    }

    tests := []struct {
        city     string
        expected bool
    }{
        {"Jakarta", true},
        {"Bandung", true},
        {"Surabaya", false},
    }

    for _, tt := range tests {
        result, _ := expr.Interpret(Context{"city": tt.city})
        if result != tt.expected {
            t.Errorf("city=%s: expected %v, got %v", tt.city, tt.expected, result)
        }
    }
}

func TestQueryEngine_CachesExpression(t *testing.T) {
    engine := NewQueryEngine()
    query := `status == "active"`
    items := []Context{
        {"status": "active"},
        {"status": "inactive"},
    }

    results1, _ := engine.Filter(items, query)
    results2, _ := engine.Filter(items, query) // should use the cache

    if len(results1) != 1 || len(results2) != 1 {
        t.Errorf("expected 1 result, got %d and %d", len(results1), len(results2))
    }
}

Combining Interpreter with Composite and Visitor #

The Interpreter Pattern naturally collaborates with two other patterns:

flowchart TD
    subgraph "Composite — Tree Structure"
        AND2[AndExpression\\nComposite]
        EQ2[EqualsExpression\\nLeaf]
        GT2[GreaterThanExpression\\nLeaf]
        AND2 --> EQ2
        AND2 --> GT2
    end

    subgraph "Interpreter — Evaluation"
        I["Interpret(ctx)\\ncalled recursively\\nlike Composite.GetSize()"]
    end

    subgraph "Visitor — Analysis"
        OPT[OptimizeVisitor\\n'constant folding']
        STR[StringifyVisitor\\n'debug print']
    end

    AND2 -->|recursive| I
    AND2 -->|Accept| OPT & STR

The Composite Pattern explains the structure of the expression tree — non-terminal expressions are Composites, terminal expressions are Leaves
The Interpreter Pattern explains evaluation — the Interpret() method running recursively like a Composite operation
The Visitor Pattern can be added for other operations on the same tree — optimization, pretty-printing, serialization — without changing the Expression classes

When to Use and When Not to #

USE Interpreter if:
  ✓ You need to interpret a simple language or DSL (Domain Specific Language)
  ✓ The grammar is relatively simple and its rules are stable
  ✓ You need to define queries or expressions dynamically at runtime
  ✓ You are building a rule engine, filter system, or expression evaluator
  ✓ Expressions need to be stored in a database and evaluated later

AVOID Interpreter if:
  ✗ The grammar is very complex — use a parser generator (ANTLR, PEG)
  ✗ Performance is a priority — tree traversal is slower than a compiled approach
  ✗ A library already exists for the interpreted language (SQL: sqlx, math: expr)
  ✗ The grammar changes often — every grammar change can break many classes

When to Use a Library vs Implement It Yourself
The Interpreter Pattern fits simple DSLs you fully control. For more complex needs, consider: github.com/expr-lang/expr for expression evaluation, github.com/antlr4-go/antlr/v4 for complex grammars, or a template library. The Interpreter Pattern is still useful for understanding how these libraries work behind the scenes.

Interpreter Review Checklist #

GRAMMAR:
  □ The grammar is defined explicitly (BNF or EBNF)
  □ Every grammar rule is represented as an Expression class
  □ Terminal expressions are leaves — they contain no other Expression
  □ Non-terminal expressions delegate to child expressions recursively

PARSER:
  □ The Lexer breaks the input into tokens correctly
  □ The Parser implements recursive descent according to the grammar
  □ Error reporting is clear — the position and token causing the error
  □ The Parser handles edge cases (empty string, single expression)

EVALUATION:
  □ Short-circuit evaluation is implemented for AND and OR
  □ Errors from child expressions are propagated with clear context
  □ The Context supports nested field access (dot notation)
  □ Type mismatches produce errors, not panics

TESTING:
  □ Every terminal expression is tested in isolation
  □ Every non-terminal expression is tested with mock children
  □ The Parser is tested for complex queries with various operators
  □ Edge cases: missing fields, type mismatches, empty expressions

Summary #

Interpreter turns a language into an evaluable object tree — every grammar rule becomes an Expression class; sentences in the language become Expression trees.
Two kinds of expressions: terminal (leaf — a value or field with no children) and non-terminal (composite — containing child expressions evaluated recursively).
Two components: the Lexer breaks a string into tokens; the Parser turns the tokens into an Expression tree using recursive descent.
Short-circuit evaluation matters for AND and OR — if the left operand already determines the result, the right operand need not be evaluated.
A filter query engine is the most common use case — queries like status == "active" AND age > 25 are parsed into an AndExpression containing an EqualsExpression and a GreaterThanExpression.
Cache parsed expressions — parsing is an expensive operation; if the same query is used repeatedly, store the result in a cache.
Natural combinations: Interpreter uses Composite for the tree structure; Visitor can be added for other operations (optimization, serialization) without changing the Expression classes.
For complex grammars, use a parser generator — the Interpreter Pattern fits simple, controlled DSLs, not full programming languages.

← Previous: Visitor Next: Thread Pool →