Operational Grammars

7.1 The object

Part I described structures one at a time. Each had a set of operations (“moves”), a meaning for each move, a notion of which sequences of moves are allowed, and a representation with costs. The following definition collects these components.

Three remarks fix the reading.

1. Admissibility is a projection. The language constrains only the moves it mentions; observer moves such as here or read are free unless named. This is a definitional choice (CGT-D-015); without it, every constraint would have to enumerate every observer.
2. Admissibility and definedness are different. pop on an empty stack is admissible under the universal language and undefined; (a b)* a may reject a b although $\sem{ab}(x)$ is non-empty. Syntax is decided by $\Lang$ without looking at the state; semantics depends on the state.
3. The finite description of $\Lang$ is a conventional formal grammar $(\Sigma, N, P, S)$ or an automaton. What the definition adds is the structure-dependent semantics $\sem{\cdot}$ and, in Definition 7.4, a cost model.

7.2 Adequate representations

A representation implements the moves on concrete memory. It is correct when it computes what the semantics says.

Adequacy is the standard notion of a correct implementation of an abstract data type (an abstraction function relating concrete and abstract states). The SDK makes it executable: every structure has a pure reference semantics denote on its abstract value and an instrumented apply on its representation, and execute compares them call by call. The test suite checks adequacy for every structure on thousands of random expressions, including undefined ones (CGT-D-014).

Here is the whole interface, used to define a new structure from scratch: a counter that can be incremented and decremented within bounds, with an admissibility language forbidding two decrements in a row.

from cgtsdk import Cost, Inadmissible, Move, Structure

class BoundedCounter(Structure):
    """A counter in [0, K]. Abstract value: the integer."""
    name = "counter"
    SIGNATURE = (Move("inc", (), "add one"), Move("dec", (), "subtract one"), Move("value", (), "read"))

    def __init__(self, K, start=0):
        self.K, self.v = K, start

    def abstract(self):
        return (self.K, self.v)

    @classmethod
    def denote(cls, state, call):
        K, v = state
        if call.name == "inc":
            if v == K: raise Inadmissible("counter at its maximum")
            return (K, v + 1), None
        if call.name == "dec":
            if v == 0: raise Inadmissible("counter at zero")
            return (K, v - 1), None
        return state, v

    def apply(self, call, cost):
        cost.add("compare", 1)
        if call.name == "value":
            cost.add("read", 1); return self.v
        step = 1 if call.name == "inc" else -1
        if not 0 <= self.v + step <= self.K:
            raise Inadmissible("counter at its maximum" if step > 0 else "counter at zero")
        cost.add("write", 1); self.v += step

for expr in ["inc inc dec value", "inc dec dec", "dec", "inc inc inc inc", "inc value inc dec value"]:
    g = BoundedCounter(K=3).grammar(admissible="(inc | dec inc)* (dec | ε)")   # fresh state each time
    r = g.execute(expr)
    status = (f"syntax: {r.syntax.error}" if not r.syntax.ok else
              f"undefined at call {r.undefined_at}: {r.reason}" if not r.defined else f"values {r.values}")
    print(f"{expr:24s} -> {status}  [adequate={r.adequate}]")

inc inc dec value        -> values [None, None, None, 1]  [adequate=True]
inc dec dec              -> syntax: move word inc dec dec is not in the admissibility language  [adequate=None]
dec                      -> undefined at call 0: counter at zero  [adequate=True]
inc inc inc inc          -> undefined at call 3: counter at its maximum  [adequate=True]
inc value inc dec value  -> values [None, 1, None, None, 1]  [adequate=True]

Execution mutates the representation, so each expression starts from a fresh counter at zero. The second expression is rejected before execution because dec dec is not admissible; the third is admissible and undefined (the counter starts at zero); the fourth runs off the top. The last shows projection at work: value is not mentioned by the language, so it does not interfere with it.

7.3 The grammar of each structure

With the definition in hand, the structures of Part I can be written in one format. The table is a summary of Chapters 2–6; the SDK implements each row.

The table makes visible what is common — every structure is a set of states with partial moves — and what is not: the admissibility class (universal, regular, context-free), the dependence of definedness on state, and above all the cost column.

7.4 Structural grammars

An operational grammar generates operations over a structure. A second kind of grammar generates the structure itself.

The two kinds combine: navigating a grammar-compressed tree is an operational grammar whose states are given by a structural grammar (Chapter 5, CGT-THM-005). Grammar-based compression is an established field [Charikar et al. 2005; Lohrey 2015; Bille et al. 2011]; random access into a grammar-compressed string of length $N$ takes $\Oh(\log N)$ time [Bille et al. 2011], and lower bounds show that for polynomial-space structures this cannot in general be improved to constant time [Verbin & Yu 2013]. This book uses these objects and does not claim new compression results.

7.5 Cost profiles

The notation $T(n, g, q, u, o)$ is a reporting discipline, not yet a theory: whether grammar parameters yield distinctions not already captured by parameterized complexity or by preprocessing–query trade-offs is an open problem (CGT-OPEN-005).

7.6 Five mechanisms

Every advantage observed so far in this research — in the chapters of Part I and in the ten experiments of the ledger — traces to one of five mechanisms.

The thesis is not yet a mathematical statement: “conventional scheme” and “attributable” are undefined, and making them precise is an open problem (CGT-OPEN-001). It is nevertheless falsifiable in practice — by a grammar-based scheme with an advantage none of the five explains — and it organizes the rest of the book. Chapters 8–14 examine each mechanism with its cost profile and its failure cases.

7.7 Relationship to established theory

The components of an operational grammar are not new, and it is important to say which existing theories each comes from.

• Labelled transition systems and relational semantics. $(\Sigma, \Str, \sem{\cdot})$ is a labelled transition system; the extension to words is the relational model of Kleene algebra. \emph{Kleene algebra with tests} [Kozen 1997] adds Boolean guards and is a natural home for admissibility conditions that depend on state.
• Formal-language-constrained paths. With regular or context-free $\Lang$ over a labelled graph, the grammar is exactly the setting of regular path queries and CFL-reachability [Mendelzon & Wood 1995; Barrett et al. 2000; Yannakakis 1990; Reps 1998].
• Attribute grammars. Knuth’s attribute grammars [Knuth 1968] attach semantic functions to the productions of a context-free grammar and evaluate them over derivation trees. They are the classical way of making a grammar compute. CGT differs in where the grammar lives: attribute grammars describe strings and their parse trees; operational grammars describe operations over an arbitrary structure. A systematic comparison is a literature debt of this program (CGT-OPEN-010).
• Automatic structures and groups. Structures whose elements are words of a regular language and whose relations are recognized by synchronous automata [Blumensath & Grädel 2000; Khoussainov & Nerode 1995], and groups whose multiplication by generators is so recognized [Epstein et al. 1992], are the closest existing theory to the address-as-sentence idea. Chapter 13’s compiled words are a cost-oriented special case.
• Abstract data types. Adequacy is the standard notion of a correct implementation of an abstract type.

What the program adds is not a new object but a discipline: every claim filed under one layer, every cost stated as a profile in an explicit model, every advantage attributed to a mechanism and paired with the inputs that defeat it.

Report an erratum or an unclear passage in this chapter