Chapter 36
Decoration: One Map, Many Semirings
An earlier presentation of this material carried two separate pieces of data — a weight map valued in \(\CC\) and a cost map valued in an ordered monoid — and called the first a Lagrangian and the second a Hamiltonian. That presentation was doing more work than it needed to and claiming more than it had earned. The two maps have the same domain, the same indexing, and the same shape; they differ only in where they take their values. This chapter replaces them with a single construction, parametric in a semiring, and is careful about which classical structures the construction actually delivers.
The construction itself was built in Part Part I: a decoration is the weight map of Definition 14.4, its domain is the admissible key set of Definition 14.3, and equipping a theory with one is the endofunctor \(\Wgt_{\Semi}\) of Construction 14.1. By Theorem 14.4 that is the linear fragment of the graded where-clause — a clause that is a sum of scalars times indicators over a partition — and this chapter stays in the linear fragment on purpose. Its question is what the choice of semiring delivers, and the linear fragment is where the semiring is the only thing left to choose: the clause’s shape is fixed, and everything that varies is \(\oplus\) and \(\otimes\). What is new here is therefore the parameter. Chapter 14 developed two instances because those are the two an implementation runs; the answer below is that a surprising amount of the classical vocabulary of dynamics is a choice of \(\oplus\) and \(\otimes\).
36.1 Decorations
A semiring \(\Semi = (R, \oplus, \otimes, 0_R, 1_R)\) is a set with two monoid structures, \(\otimes\) distributing over a commutative \(\oplus\), with \(0_R\) absorbing for \(\otimes\). We do not require additive inverses; that omission is the point of the generality.
A decoration of a GSLT \(\GSLT\) in a semiring \(\Semi\) is a family \[\dec_r : \HML(\ctx) \rightharpoonup R, \qquad r \in \rules,\] whose domain consists of formulae that refine the left-hand side of \(r\): formulae \(\phi\) such that \(u \sat \phi\) implies \(u\) matches the pattern \(l_r\). A decorated GSLT is a pair \((\GSLT, \dec)\).
The refinement relation orders the domain of \(\dec_r\): write \(\phi \leq \psi\) when \(\psi\) entails \(\phi\). To evaluate a decoration at a step one must select a formula, and the selection has to be well defined. The condition under which it is, is the partition discipline of Definition 14.2: the keys of a rule are pairwise exclusive and jointly exhaustive over the rule’s left-hand side, so that by Proposition 14.1 each redex is classified by exactly one of them. We write \(\phi_r(u)\) for that unique witness and \(\dec_r(u)\) for \(\dec_r(\phi_r(u))\), and everything below assumes it. Corollary 14.2 says the discipline is unnecessary for a graded clause in general; it is retained here because the three things this chapter wants from a decoration — incremental reclassification, summable propensities, orthogonal projectors in the complex instance — are exactly what the linear fragment buys, and assuming the partition is the same decision as staying linear.
An earlier presentation of this chapter imposed a different and weaker condition, which is worth naming because it is the obvious one and because it will occur independently to any reader who tries to build the construction. Call a decoration refinement-complete when, for every rule \(r\) and every term \(u\) matching \(l_r\), the set of satisfied formulae in \(\mathrm{dom}(\dec_r)\) has a greatest element — a most refined witness — and evaluate the decoration there. This also makes the selection single-valued, and it is strictly weaker: a partition is refinement-complete, since the unique satisfied key is trivially the greatest, and the converse fails.
The reason to prefer the partition is not that most-specific-match is ill-defined but that it is differently defined, and that three things downstream need the disjointness rather than the selection. The locality of reclassification which licenses an incremental simulator needs it; the propensity of a class being summable over its redexes needs it; and in the complex instance the classes being orthogonal projectors needs it. Refinement-completeness delivers a well-defined rate and none of the three. Where a modeler genuinely wants overlapping keys — and it is a natural thing to want — what is being specified is a nonlinear graded clause, and Theorem 14.4 says which semantics that is: on a candidate satisfying two keys the clause returns the sum of their values, not the most specific one. Most-specific-match is a different semantics again, and one the clause language does not supply; a modeler who wants it must write the keys so that they do not overlap.
Let \(\gamma = r_1 \cdot r_2 \cdots r_n\) be a rewrite path from \(P\) to \(Q\), with \(u_i\) the redex at step \(i\). The path weight is the ordered product \[W(\gamma) \;=\; \dec_{r_1}(u_1) \otimes \cdots \otimes \dec_{r_n}(u_n) \;\in\; R,\] and the transition weight from \(P\) to \(Q\) is the sum over paths \[\langle Q \mid P \rangle \;=\; \bigoplus_{\gamma : P \to Q} W(\gamma),\] whenever that sum exists.
The product is ordered because \(\otimes\) need not be commutative, and is not in the cases of interest: the order of the factors is the order of the steps. This is the temporal monoid of [62, §4] reappearing inside the decoration — reduction is sequential even when interaction is parallel.
36.2 Four instances
The content of the parametrization is that familiar dynamical structures are recovered by a choice of semiring. What follows is the reading of [62, §13], transposed to the present setting.
{1.35}
| Semiring \(\Semi\) | What \((\GSLT,\dec)\) becomes |
|---|---|
| Boolean \((\{0,1\},\vee,\wedge)\) | the bare nondeterministic transition system; \(\langle Q\mid P\rangle\) is reachability |
| Tropical \((\Real\cup\{\infty\},\min,+)\) | cost; \(W(\gamma)\) is the total charge of a path and \(\langle Q\mid P\rangle\) is the cheapest way to get there |
| Non-negative reals \((\Real_{\geq 0},+,\times)\) | stochastic dynamics; \(W\) is a path weight, and the Gillespie algorithm samples it — which by Theorem 39.1 is a theorem about degeneration and not an analogy |
| Complex numbers \((\CC,+,\times)\) | amplitudes, and with them interference — see Chapter 39, for the fragment on which the reading is credible and the obstruction the linear fragment meets |
The weight map was the complex instance; the cost map was the tropical instance. They were never two kinds of structure. Nothing is lost by the merge, and something is gained: the Boolean and stochastic instances, for which the two-map presentation had no room, are now the same construction specialized twice more.
36.3 Where the Lagrangian actually is
The earlier text set \(S[\gamma] = \sum_i \log \dec_{r_i}(u_i)\), observed that \(W(\gamma) = e^{S[\gamma]}\), and called \(S\) an action. That is a change of variable, not a variational principle: it converts a product into a sum and asserts nothing further. A Lagrangian earns its name by making the realized trajectory the stationary point of an action over a space of competing trajectories, and no such principle was stated, let alone proved.
There is nevertheless a genuine least-action statement available, and it is the tropical instance.
In the tropical semiring, Definition 36.3 reads \[W(\gamma) = \sum_{i=1}^{n} \dec_{r_i}(u_i), \qquad \langle Q \mid P \rangle = \min_{\gamma : P \to Q} W(\gamma).\] The path weight is an additive action functional, and the transition weight is its minimization over all paths. The principle of least action is therefore not an approximation to the sum over paths in this setting; it is the sum over paths, computed in the semiring whose addition is \(\min\).
Immediate from \(\oplus = \min\) and \(\otimes = +\).
The relation between Proposition 36.1 and the complex instance is the relation between tropicalization and the \(\hbar \to 0\) limit: the saddle-point approximation of a complex sum over paths is a tropical minimization, which is why the classical limit of a path integral is a least-action principle. Here the two are not limits of each other but instances of one construction at different semirings, so the passage between them is a question about semiring homomorphisms rather than about asymptotics. We do not claim to have answered it. We claim only that this is where the question lives.
The honest summary is this. The decoration supplies a charge per step. The tropical instance supplies a least-action principle. The word “Lagrangian” is warranted for the tropical case and premature for the others.
36.4 Decorations move
A decoration as defined above is static: \(\dec_r\) is fixed once and for all. That is too weak for what the later parts of this book require, where the rate at which a rule fires depends on what has already happened.
A dynamic decoration equips each state with a table \(T : \mathrm{dom}(\dec) \to R\) keyed by the formulae refining the left-hand sides of the rules, and equips each rewrite with an update \(T \mapsto T'\) on the table carried by its successor. A static decoration is the special case in which every update is the identity.
Because the successor state carries a table of the same kind, the updates compose, and the weights are genuinely dynamical rather than parameters.
It is worth being explicit about what that costs and what it buys, since the chapter as previously written recorded the construction and not its consequence. A table traveling with the state means the state is not the term. The object being decorated is the configuration \((P, T)\) of Definition 14.5, and the process is Markov on configurations and in general not on terms — two runs can reach the same term carrying different tables, and then no rate function of the term alone reproduces both (Theorem 14.1, Example 14.1). This is the price of dynamism and it is paid in the size of the state space. It is also, read the other way, the reason a physics whose constants respond to what has happened is still a physics: one has not left the Markovian world, one has moved up a level inside it.
The graded clause pays the same price differently, and the difference is worth having on the page here because the physics chapters quote both forms. By Proposition 14.3, a dynamic decoration whose updates depend only on features of the current term is a static clause: the clause is re-evaluated against the term it finds, and the table it would have carried is already written in the term. The configuration \((P,T)\) then collapses to \(P\) and the chain is on terms. What survives as a configuration-level statement is the case Example 14.1 exhibits — an update that depends on history the term does not record — and Remark 14.10 says what rho does about that: it writes the history down. So “the constants respond to what has happened” has two readings. In the linear fragment the constants live in a table beside the term and the table is part of the state. In the clause language the constants are read off the term, and whatever they respond to is in the term. The second reading is the one the rest of this part should be heard in, and the first is kept because the semiring table above is stated in it.
One further consequence is worth recording early: the adequacy of a logic generated over such a structure is a function of the rewrites. Interleaving rewrites yield a logic that sees only interleaving; true-concurrency rewrites yield a logic that sees true concurrency. The decoration does not fix this; the rewrites do.
The propensity of Definition 14.7 carries a second factor this chapter has so far ignored: the geometric factor \(\gfac(k)\) accumulated along the context rules addressing a redex. It is worth naming here because the split it induces is a physical one and the book has no other statement of it. \(\dec_r(u)\) prices a step by what is transferred; \(\gfac(k)\) prices it by where in the term the interaction surfaces are. The first depends on the matter of the interaction and the second on nothing but its position. A weighting of the reduction graph therefore splits, canonically, into a geometric part and a matter part.
We take the default \(\gfac \equiv 1\) throughout — addressing is free — and record the split as an opportunity rather than a result. What would make it more than a suggestive coincidence is an action forcing the two parts to agree, in the way that a field equation forces geometry and matter to determine one another. Chapter 42 lists this among the things not attempted.
36.5 The cost instance, and affordability
The tropical instance deserves separate treatment, because it alone supports a notion of sufficiency: a step can fail for want of funds, which is not something a probability or an amplitude can do.
A resource algebra is a commutative ordered monoid \((A, +, \mathbf{0}, \leq)\). A vectorial account over resource types \(\mathbf{I} = \{1,\ldots,k\}\) is an element \(\vect{A} = (A_1,\ldots,A_k)\) of \(A^k\), each \(A_i\) tracking the available amount of one type.
For the rho calculus the natural types include a budget for fresh names (the \(@\) constructor), a budget for synchronisations, and a budget for persistent-receive firings. Heterogeneous resources are tracked separately because they are not interconvertible for free; what it costs to convert one into another is the subject of the next chapter.
A step is affordable if the account covers the charge: \(\langle P, \vect{A}\rangle \rewrite_r \langle P', \vect{A}'\rangle\) provided that \(P \rewrite_r P'\) via \(r\) with witness \(\phi_r(u)\), that \(\dec_r(u) \leq \vect{A}\) componentwise, and that \(\vect{A}' = \vect{A} - \dec_r(u)\).
Definition 36.6 is stated here in the form the earlier presentation used, and in that form it harbors a defect: it says nothing about who may draw on \(\vect{A}\). A single account adjacent to an associative–commutative soup of processes is adjacent to every process in it, and adjacency taken as the right to spend is ambient authority [64]. The next chapter states the defect precisely and repairs it, and the repair turns out to carry the most interesting physics in this part of the book.