Interpreter: Small Languages and Resource Bounds

What this concept is

Interpreter represents a small language's grammar and evaluates its sentences. Separate concrete syntax, parsing into an abstract syntax tree, and semantics. An object per grammar rule is one representation. A tagged tree and evaluator can be simpler. Visitor can add operations such as formatting to that same tree.

Why it matters here

A settings field that grows from one flag into arbitrary Boolean rules has become a language. Without a grammar, precedence, unknown-name behavior and limits become accidental. Host-language eval grants semantics and capabilities far beyond a small rule language and is not an appropriate implementation here.

Concrete example

Use this unambiguous grammar, with parentheses required around binary forms:

expr := true | false | name | (expr AND expr) | (expr OR expr) | (NOT expr)
name := an identifier from a supplied finite environment

Define Boolean-only bindings, left-to-right short-circuit evaluation, unknown names as errors only when evaluated, and rejection of malformed syntax before execution. In (false AND missing), missing is not evaluated. In (true AND missing), evaluation fails. Parsing both branches is still necessary: short-circuit semantics do not excuse malformed syntax in the untaken branch.

A tuple AST such as ('and', ('lit', False), ('name', 'missing')) makes the trace explicit. Evaluate the left child first; only then decide whether the right child is required. Count visited nodes and limit input tokens and tree depth separately.

Common confusion / misconception

Interpreter does not mean writing a general compiler. A small table can replace a language when users only select fixed presets. Rejecting unknown names during static validation rather than evaluation is also a valid policy, but it changes the example above and must be specified separately.

How to use it

Start with a grammar and examples/nonexamples. Define types, evaluation order, scope, failure and resource budgets. Keep the environment data-only; prohibit arbitrary function calls or attribute access unless deliberately designed. Prefer an established parser for a growing grammar and retain semantic tests.

Check yourself

Why does eager evaluation break the missing-name example? What is the difference between parsing and evaluation failure? Why does an O(n) node count not bound the cost of arbitrary host-language functions placed in the environment?

Mini drill or application

P20: implement the tuple evaluator without textual parsing or eval. Enumerate AND/OR/NOT truth tables and test missing names on taken/untaken paths. Then write a parser design with explicit token/depth limits as an optional extension. L07 supplies a different arithmetic AST for comparing interpreter and visitor roles.

Read this only if stuck

GoF book index, 068-interpreter-sample-code-part-1.md for grammar and tree construction. Do not copy OCR-corrupted code as a runnable implementation.