Interpreter in Go — Go Patterns

The Problem

Some rules change faster than code ships. A promotions team wants to express “orders over $100 with 3+ items get the bulk discount” today and tweak the threshold tomorrow — without a deploy. Hardcoding each rule as a Go function means every change goes through the full release cycle, and the people who own the rules can’t read or edit them.

The Solution

The Interpreter pattern defines a tiny language for the rules and represents each rule as an expression tree. Terminal expressions (a comparison like total >= 100) evaluate directly against an environment of variables; non-terminal expressions (AND, OR, NOT) combine the results of their children. A small recursive-descent parser turns rule strings into trees once, at load time, and malformed rules are rejected before anything runs.

Structure

Interpreter Pattern

Step 1 of 5

Parse Once

Parse() tokenizes the rule string and builds an expression tree with a small recursive-descent parser. Syntax errors surface here, at load time, not during evaluation.

flowchart TD
Rule["Rule string
'total >= 100 AND items >= 3'"]
Parser["Parse()"]
And["And (non-terminal)"]
CompA["Comparison
total >= 100"]
CompB["Comparison
items >= 3"]
Env["Env
order facts"]
Result["bool result"]

Rule --> Parser
Parser --> And
And --> CompA
And --> CompB
Env -->|"Evaluate(env)"| And
And --> Result

Abstract expression: Expression declares Evaluate(env) for every node in the tree.
Terminal expression: Comparison resolves one variable against a literal.
Non-terminal expressions: And, Or, and Not compose child expressions.
Context: Env supplies the variable values for one evaluation.
Parser: Parse() turns rule text into a validated tree before first use.

Implementation

This example interprets discount-eligibility rules for an order. Rules are plain strings a product team could own, parsed once into expression trees and evaluated against each order’s facts.

gofmt ✓

package main

import "fmt"

// Env supplies variable values (order facts) to the expression tree.
type Env map[string]float64

// Expression is the interpreter contract: every AST node — terminal or
// composite — evaluates itself against the environment.
type Expression interface {
	Evaluate(env Env) (bool, error)
	String() string
}

// Comparison is a terminal expression: <variable> <op> <number>.
type Comparison struct {
	Variable string
	Operator string
	Value    float64
}

func (c *Comparison) Evaluate(env Env) (bool, error) {
	actual, ok := env[c.Variable]
	if !ok {
		return false, fmt.Errorf("unknown variable %q", c.Variable)
	}

	switch c.Operator {
	case ">":
		return actual > c.Value, nil
	case ">=":
		return actual >= c.Value, nil
	case "<":
		return actual < c.Value, nil
	case "<=":
		return actual <= c.Value, nil
	case "==":
		return actual == c.Value, nil
	default:
		return false, fmt.Errorf("unknown operator %q", c.Operator)
	}
}

func (c *Comparison) String() string {
	return fmt.Sprintf("%s %s %g", c.Variable, c.Operator, c.Value)
}

// And is a non-terminal expression that is true when both operands are true.
type And struct {
	Left, Right Expression
}

func (a *And) Evaluate(env Env) (bool, error) {
	left, err := a.Left.Evaluate(env)
	if err != nil {
		return false, err
	}
	if !left {
		return false, nil
	}
	return a.Right.Evaluate(env)
}

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

// Or is a non-terminal expression that is true when either operand is true.
type Or struct {
	Left, Right Expression
}

func (o *Or) Evaluate(env Env) (bool, error) {
	left, err := o.Left.Evaluate(env)
	if err != nil {
		return false, err
	}
	if left {
		return true, nil
	}
	return o.Right.Evaluate(env)
}

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

// Not is a non-terminal expression that inverts its operand.
type Not struct {
	Operand Expression
}

func (n *Not) Evaluate(env Env) (bool, error) {
	value, err := n.Operand.Evaluate(env)
	if err != nil {
		return false, err
	}
	return !value, nil
}

func (n *Not) String() string {
	return fmt.Sprintf("NOT %s", n.Operand)
}

package main

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

// Parse builds an Expression tree from a rule string using this grammar:
//
//	expr       := term { "OR" term }
//	term       := factor { "AND" factor }
//	factor     := "NOT" factor | "(" expr ")" | comparison
//	comparison := IDENT (">" | ">=" | "<" | "<=" | "==") NUMBER
func Parse(rule string) (Expression, error) {
	p := &parser{tokens: tokenize(rule)}
	expr, err := p.parseExpr()
	if err != nil {
		return nil, fmt.Errorf("parse %q: %w", rule, err)
	}
	if tok := p.peek(); tok != "" {
		return nil, fmt.Errorf("parse %q: unexpected token %q", rule, tok)
	}
	return expr, nil
}

func tokenize(rule string) []string {
	for _, symbol := range []string{"(", ")"} {
		rule = strings.ReplaceAll(rule, symbol, " "+symbol+" ")
	}
	return strings.Fields(rule)
}

type parser struct {
	tokens []string
	pos    int
}

func (p *parser) peek() string {
	if p.pos >= len(p.tokens) {
		return ""
	}
	return p.tokens[p.pos]
}

func (p *parser) next() string {
	tok := p.peek()
	p.pos++
	return tok
}

func (p *parser) parseExpr() (Expression, error) {
	left, err := p.parseTerm()
	if err != nil {
		return nil, err
	}
	for strings.EqualFold(p.peek(), "OR") {
		p.next()
		right, err := p.parseTerm()
		if err != nil {
			return nil, err
		}
		left = &Or{Left: left, Right: right}
	}
	return left, nil
}

func (p *parser) parseTerm() (Expression, error) {
	left, err := p.parseFactor()
	if err != nil {
		return nil, err
	}
	for strings.EqualFold(p.peek(), "AND") {
		p.next()
		right, err := p.parseFactor()
		if err != nil {
			return nil, err
		}
		left = &And{Left: left, Right: right}
	}
	return left, nil
}

func (p *parser) parseFactor() (Expression, error) {
	switch tok := p.peek(); {
	case strings.EqualFold(tok, "NOT"):
		p.next()
		operand, err := p.parseFactor()
		if err != nil {
			return nil, err
		}
		return &Not{Operand: operand}, nil

	case tok == "(":
		p.next()
		expr, err := p.parseExpr()
		if err != nil {
			return nil, err
		}
		if closing := p.next(); closing != ")" {
			return nil, fmt.Errorf("expected %q, got %q", ")", closing)
		}
		return expr, nil

	default:
		return p.parseComparison()
	}
}

func (p *parser) parseComparison() (Expression, error) {
	variable := p.next()
	if variable == "" {
		return nil, fmt.Errorf("expected variable, got end of input")
	}

	operator := p.next()
	switch operator {
	case ">", ">=", "<", "<=", "==":
	default:
		return nil, fmt.Errorf("expected comparison operator after %q, got %q", variable, operator)
	}

	literal := p.next()
	value, err := strconv.ParseFloat(literal, 64)
	if err != nil {
		return nil, fmt.Errorf("expected number after %q, got %q", operator, literal)
	}

	return &Comparison{Variable: variable, Operator: operator, Value: value}, nil
}

package main

import "fmt"

func main() {
	fmt.Println("=== Interpreter in Go ===")

	// Facts about the current order, supplied to every rule evaluation.
	order := Env{
		"total":         142.50,
		"items":         3,
		"loyalty_years": 2,
	}

	// Business rules written by non-programmers, stored as plain strings —
	// in a real system these would live in a database or config file.
	rules := []struct {
		name string
		text string
	}{
		{"bulk-discount", "total >= 100 AND items >= 3"},
		{"vip-shipping", "loyalty_years >= 5 OR total > 500"},
		{"first-order-promo", "NOT ( loyalty_years >= 1 )"},
	}

	for _, rule := range rules {
		expr, err := Parse(rule.text)
		if err != nil {
			fmt.Printf("%-18s invalid: %v\n", rule.name, err)
			continue
		}

		eligible, err := expr.Evaluate(order)
		if err != nil {
			fmt.Printf("%-18s failed: %v\n", rule.name, err)
			continue
		}

		fmt.Printf("%-18s %-40s => %t\n", rule.name, expr, eligible)
	}

	// Malformed rules are rejected at parse time, before any evaluation.
	if _, err := Parse("total >>> 100"); err != nil {
		fmt.Printf("\nrejected rule: %v\n", err)
	}
}

Real-World Analogy

Think of a spreadsheet formula. The person typing =IF(AND(A1>100, B1>=3), ...) isn’t a programmer, and the spreadsheet doesn’t ship a new binary for each formula. It parses the formula into a tree once and re-evaluates it whenever the cells change.

Pros and Cons

| Pros | Cons | | --- | --- | | Rules become data: stored, versioned, and edited without redeploying. | A grammar, parser, and AST are heavy machinery for a handful of static rules. | | Each grammar rule maps to one small type that is easy to test in isolation. | Complex grammars make the class-per-rule approach sprawl quickly. | | Malformed rules fail at parse time, before they can affect an order. | Tree-walking interpreters are slower than compiled code on hot paths. | | New operators are added by writing one new expression type. | Error messages need deliberate care to be useful to rule authors. |

Best Practices

Parse once, evaluate many times. Cache the tree per rule; never re-parse inside a request loop.
Keep the grammar as small as the domain allows. Every operator you add is grammar you must parse, document, and support forever.
Return errors, don’t panic. Rule text is user input; a typo in a rule must never take down the process.
Short-circuit AND/OR the way rule authors expect from every other language.
Reach for an existing engine (text/template, CEL, expr) before writing your own once the grammar grows past simple boolean logic.

When to Use

Business rules change often, are owned by non-engineers, and must not require a deploy.
The language is genuinely small: boolean logic, comparisons, a fixed set of variables.
You need rules to be validated up front and stored as data.

When NOT to Use

The rules are stable — plain Go functions are simpler, faster, and type-checked.
The grammar is growing toward a real language — use an existing expression engine or embed a scripting runtime instead.
Evaluation sits on a hot path where tree-walking overhead matters.

Interpreter