Interpreteraka Expression tree, Little language

Công thức trong Excel như =IF(A1>100, B1*0.9, B1) là một 'ngôn ngữ nhỏ'. Excel tách nó thành cây: IF ở gốc, phép so sánh và phép nhân ở các nhánh, ô và số ở lá. Muốn tính, Excel đi từ lá lên gốc. Mỗi loại nút chỉ cần biết tự tính phần của mình.An Excel formula like =IF(A1>100, B1*0.9, B1) is a 'little language'. Excel turns it into a tree: IF at the root, comparison and multiplication as branches, cells and numbers as leaves. To compute, it evaluates from leaves up to the root. Each node type only knows how to compute its own part.

Thành phần tham giaParticipants

AbstractExpression

Interface chung, khai báo interpret(context).Common interface declaring interpret(context).

TerminalExpression

Lá của cây: phép so sánh, hằng số, tên biến.Tree leaves: comparisons, literals, variables.

NonterminalExpression

Nút ghép (And, Or, Not) chứa expression con và kết hợp kết quả.Combinators (And, Or, Not) holding child expressions and combining results.

Context

Dữ liệu để thông dịch (facts: total, category, tier...).The data to interpret against (facts: total, category, tier...).

Client / Parser

Dựng cây từ chuỗi và gọi interpret.Builds the tree from text and calls interpret.

Dùng Tự chạy hoặc phím mũi tên để đi qua từng bước gọi giữa các object. Console hiển thị output tương ứng của chương trình.Use Autoplay or the arrow keys to step through each call between objects. The console shows the matching program output.

Cùng một bài toán, hai ngôn ngữ. Rê chuột hoặc focus vào chú thích (số màu cam) để làm nổi bật dòng code tương ứng.Same problem, two languages. Hover or focus an annotation (orange number) to highlight its line.

package com.shop.promo;

import java.util.Map;

// Grammar: rule := rule OR rule | rule AND rule | NOT rule | (rule) | field >= number | field == word1
public sealed interface Rule {
    boolean interpret(Map<String, Object> facts);2
}

// Terminal expressions: the leaves of the tree
record AtLeast(String field, long min) implements Rule {
    public boolean interpret(Map<String, Object> facts) {
        return facts.get(field) instanceof Number n && n.longValue() >= min;3
    }
}

record Equals(String field, String value) implements Rule {
    public boolean interpret(Map<String, Object> facts) {
        return value.equals(facts.get(field));
    }
}

// Non-terminal expressions: combine child rules recursively
record And(Rule left, Rule right) implements Rule {
    public boolean interpret(Map<String, Object> facts) {
        return left.interpret(facts) && right.interpret(facts);4
    }
}

record Or(Rule left, Rule right) implements Rule {
    public boolean interpret(Map<String, Object> facts) {
        return left.interpret(facts) || right.interpret(facts);
    }
}

record Not(Rule inner) implements Rule {
    public boolean interpret(Map<String, Object> facts) {
        return !inner.interpret(facts);
    }
}

package promo

// Facts are the context the rules are interpreted against.
type Facts map[string]any1

// Rule is one node of the expression tree.
type Rule interface {
	Eval(f Facts) bool
}

// Terminal expressions
type AtLeast struct {
	Field string
	Min   int64
}

func (r AtLeast) Eval(f Facts) bool {
	n, ok := f[r.Field].(int64)2
	return ok && n >= r.Min
}

type Equals struct{ Field, Value string }

func (r Equals) Eval(f Facts) bool { return f[r.Field] == r.Value }3

// Non-terminal expressions
type And struct{ Left, Right Rule }
type Or struct{ Left, Right Rule }
type Not struct{ Inner Rule }

func (r And) Eval(f Facts) bool { return r.Left.Eval(f) && r.Right.Eval(f) }4
func (r Or) Eval(f Facts) bool  { return r.Left.Eval(f) || r.Right.Eval(f) }
func (r Not) Eval(f Facts) bool { return !r.Inner.Eval(f) }

• Spring Expression Language (SpEL)Spring Expression Language (SpEL)

  @PreAuthorize("hasRole('ADMIN') or #id == principal.id"), @Cacheable(condition = "#amount > 1000"), @Value("#{...}") — SpEL parse chuỗi thành AST rồi thông dịch.@PreAuthorize("hasRole('ADMIN') or #id == principal.id"), @Cacheable(condition = "#amount > 1000"), @Value("#{...}") — SpEL parses text into an AST and interprets it.

• Regex, SQL, templateRegex, SQL, templates

  java.util.regex.Pattern, Go regexp, text/template đều biên dịch chuỗi thành cấu trúc nội bộ rồi thực thi trên input — Interpreter ở quy mô lớn.java.util.regex.Pattern, Go's regexp and text/template all compile text into an internal structure and run it on input — Interpreter at scale.

• Rule engine & policyRule engines & policies

  Drools, Easy Rules, CEL của Google (Kubernetes ValidatingAdmissionPolicy), OPA/Rego — điều kiện được viết dạng chữ và thông dịch lúc chạy.Drools, Easy Rules, Google's CEL (Kubernetes ValidatingAdmissionPolicy), OPA/Rego — conditions written as text and interpreted at runtime.

• Điều kiện khuyến mãi, phân quyềnPromotion and permission rules

  Voucher, flash sale, phân khúc khách hàng do team vận hành tự cấu hình mà không cần deploy lại.Vouchers, flash sales, customer segments configured by ops teams without redeploying.