Composition as Graph Wiring: Random Variables as Nodes¶
Core Principle¶
In DDSL, random variables are the nodes; stages are the edges. Composition is graph adjacency. Definition: A stage \(S\) is a directed edge in a graph where: - Nodes are random variables (measurable functions on an underlying probability space \((\Omega, \mathcal{F}, P)\)) - Edges are operators that transform value functions defined on those random variables
We write \(a \xrightarrow{S} b\) to mean: stage \(S\) takes as input a value function \(V_b : \text{range}(b) \to \mathbb{R}\) and produces a value function \(V_a : \text{range}(a) \to \mathbb{R}\).
Random Variables as Interface¶
The Key Insight¶
Variable names like a, x, w are not lambda-bound placeholders—they are random variables in the measure-theoretic sense:
where \(\Omega\) is the underlying sample space carrying all uncertainty.
A stage \(S: a \to b\) is an operator:
where \(\mathcal{V}(X)\) denotes value functions on state space \(X\).
Composition via Shared Random Variables¶
Two stages compose iff they share a random variable at their interface:
The random variable \(b\) is the connection point. This is not name-matching—it's the same mathematical object appearing as: - The continuation r.v. of \(S_1\) - The arrival r.v. of \(S_2\)
Why This Differs from FFP Positional Composition¶
In pure FFP, composition is positional: outputs flow to inputs by slot number. In DDSL: - Composition is graph adjacency: stages connect through shared random variables - The r.v. \(b\) has identity across stages—it's not just "output slot 1" - This enables non-linear wiring: stage \(S_3\) can also connect to \(b\) if needed
Graph-Theoretic View¶
Stages as Edges in a Directed Graph¶
A DDSL model is a directed graph \(G = (V, E)\) where: - \(V\) = set of random variables (the "perches") - \(E\) = set of stages (operators between value function spaces)
| Graph Element | DDSL Meaning |
|---|---|
| Node \(v \in V\) | Random variable \(v : \Omega \to X_v\) |
| Edge \((a, b) \in E\) | Stage \(S: \mathcal{V}(X_b) \to \mathcal{V}(X_a)\) |
| Path \(a \to b \to c\) | Composed operator \(S_1 \circ S_2\) |
| Connected component | A well-formed sub-model |
Forward vs Backward Direction¶
The graph has two natural orientations:
| Direction | Nodes represent | Edges represent |
|---|---|---|
| Forward (simulation) | States realized | State transitions |
| Backward (valuation) | Value function domains | Bellman operators |
Edges point the same way in both views—but information flows opposite to edge direction in the backward pass.
Periods as Subgraphs¶
A period is a connected subgraph with designated entry and exit nodes:
where: - \(a_{\text{entry}}\) is the arrival r.v. (where the period begins) - \(b_{\text{exit}}\) is the continuation r.v. (where the period ends) - All internal nodes are reachable from \(a_{\text{entry}}\) and reach \(b_{\text{exit}}\)
Period Composition¶
Periods compose by identifying exit with entry:
This is the same random variable appearing in both periods.
Twisters as Isomorphisms¶
When two periods have isomorphic but not identical interface r.v.s, a twister provides the identification:
The twister is a measurable bijection between the ranges of the two random variables.
| Situation | Connector |
|---|---|
| Same r.v. at interface | Identity (implicit) |
| Isomorphic r.v.s | Twister \(\tau\) (explicit bijection) |
| Incompatible r.v.s | No composition possible |
Example: Rename Twister¶
If \(P_1\) exits with r.v. \(a\) taking values in \(\mathbb{R}^+\) and \(P_2\) enters with r.v. \(k\) also in \(\mathbb{R}^+\):
This is a graph edge connecting the two period subgraphs.
The MDP Guarantee (Graph-Theoretic Form)¶
Theorem: If the composition graph \(G\) is: 1. Directed acyclic (for finite horizon) or has a single cycle (for infinite horizon) 2. Connected (all nodes reachable) 3. Well-typed (each edge is a valid Bellman operator)
Then \(G\) defines a valid MDP, and backward induction on \(G\) computes the value function.
Contrapositive: A set of stages that forms a valid composition graph necessarily defines an MDP. The graph structure is the MDP structure.
Comparison: Three Views of Composition¶
| Aspect | FFP (Backus) | Name-Matching | Graph/R.V. (DDSL) |
|---|---|---|---|
| Interface | Positional slots | Variable names | Random variables |
| Composition | \(\text{cod}(f) = \text{dom}(g)\) | Names match | Same r.v. at boundary |
| Identity | None (slots are anonymous) | Syntactic (string equality) | Mathematical (same function on \(\Omega\)) |
| Wiring | Linear pipeline | Linear with renaming | Arbitrary DAG |
DDSL adopts the graph/r.v. view because: 1. Economic meaning: Random variables have economic interpretation (wealth, income, etc.) 2. Non-linear models: Branching and merging require graph structure 3. Measure-theoretic foundation: Connects to probability theory naturally
Notation Summary¶
| Syntax | Meaning |
|---|---|
| \(a \xrightarrow{S} b\) | Stage \(S\) with arrival r.v. \(a\), continuation r.v. \(b\) |
| \(S_1 \circ S_2\) | Composition (requires shared r.v. at interface) |
| \(\langle P_1, \tau, P_2 \rangle\) | Period composition with explicit twister |
| \(G = (V, E)\) | Model as directed graph of r.v.s and stages |
References¶
- Backus, J. (1978). "Can Programming Be Liberated from the von Neumann Style?" CACM 21(8). — For the FFP algebra of programs
- Bertsekas, D. (2012). Dynamic Programming and Optimal Control. — For MDP structure
- Stokey, Lucas, Prescott (1989). Recursive Methods in Economic Dynamics. — For measure-theoretic DP foundations