Derivation Model

The derivation model is the central data structure that Mate produces when generating or parsing an object graph. It records how an object graph was constructed (or decomposed) according to the grammar, preserving the full derivation trace from root type to leaf values.

Derivation Tree

Every time Mate generates or parses an object, it produces a derivation tree — a tree of MateOGDerivationNode objects. Each node represents one step in the derivation: the grammar declaration that was applied, the resulting object instance, and the context in which the derivation occurred.

                      Player
                   /   |    \      \
              name  charClass level  missingExp
               |       |       |        |
          "xyz123"   Warrior   47       12

Node Structure

Each MateOGDerivationNode holds:

• declaration — The MateDecl that produced this node (e.g., MateInstDecl for a Player, MateInstVarDecl for a field)
• edges — A dictionary mapping edge keys to child derivation nodes. For instance nodes, keys are field names ('name', 'level'). For array nodes, keys are indices (1, 2, 3).
• instance — The actual Pharo object at this position (e.g., a Player instance, the integer 47)
• context — The MateContext that was active during derivation, tracking the path of declarations and the derivation depth

Context

The MateContext tracks the derivation state as the tree is being built:

• path — An ordered collection of declarations visited so far (the derivation's call stack)
• level — The current depth in the derivation tree (incremented on each copy)
• parentNode — A reference to the parent derivation node

The context serves two purposes:

1. Depth control — The generator checks context level >= maxDerivationHeight to prevent infinite recursion in recursive grammars (e.g., BlElement containing BlChildrenArray containing BlElement...)
2. Reward tracking — Declarations use context key (a combination of path and level) to store per-context visit counts and rewards for the UCT selection strategy

Reward Back-Propagation

The derivation tree supports reward feedback to guide future generations toward higher-quality object graphs. This implements a Monte Carlo Tree Search (MCTS)-inspired approach:

The Feedback Loop

1. Generate object graph → derivation tree
2. Evaluate the generated object (application-specific metric)
3. Back-propagate the reward through the derivation tree
4. Future generations use accumulated rewards to make better choices

How Back-Propagation Works

grammar backpropagate: derivationTree improvement: 42.

This calls recursiveBackPropagate:seen: on the root node, which:

1. Updates the current node's declaration reward via declaration updateReward: improvement context: context
2. Recursively propagates the same improvement to all child edges
3. Uses a seen set to prevent infinite loops in cyclic derivations (from self-references)

Each declaration maintains per-context visit counts and rewards. These are used by union types (MateOptionalType) and oneOf declarations (MateInstOneOfVarDecl) to select options using the UCT (Upper Confidence Bound for Trees) formula:

UCT = (reward / visits) + C × √(ln(total_visits) / visits)

Where C is the exploration constant (default: 2). This balances exploitation (choosing options that performed well) with exploration (trying under-explored options).

Reward Flow in Union Types

When a grammar has a union type like Warrior | Rogue | Mage, each option tracks its own visit counts and rewards per context. During generation:

1. If a context has never been seen → pick randomly
2. If some options haven't been tried yet → pick an unexplored one
3. If all options have been tried → use UCT to select the best-rewarded option

After back-propagation, the option that was actually chosen in the derivation receives the reward, influencing future selections.

Visualization

Mate provides built-in rendering of derivation trees using Roassal:

grammar := MateBlocGrammar new.
derivation := grammar generator gen: BlElement from: MateContext new.
derivation render.

Each node is rendered as a colored box with its declaration name. The layout automatically switches between RSHorizontalDominanceTreeLayout (for small trees) and RSRadialTreeLayout (for trees with 100+ nodes) for readability. Nodes support hover tooltips showing type, value, and depth information.