LCL Introduction Categorical Semantics Compilation

Compilation Process

How equations are translated to computational circuits.

Overview

Translating a system of equations to a computational network happens in four stages:

  1. Resolution: Binding a unique variable identifier to each equation
  2. Isolation: Rewriting to isolate each bound variable on the left side
  3. Translation: Converting isolated equations to circuits using rewrite rules
  4. Unification: Connecting matching inputs and outputs using trace

Stage 1: Resolution

Each equation must have a bounded variable - the variable being solved for.

For equation i, the set of possible bounded variables BV(i) is determined by analyzing which variables appear in differential or integral operators.

The system of boundedness constraints is solved to assign a unique bounded variable to each equation.

Stage 2: Isolation

For each equation with a bounded variable, we isolate that variable on the left side.

Before Isolation

diff(y, t) = scalar(-0.1, y)

After Isolation

y = composition(scalar(-0.1, y), register(t))

The isolation process applies algebraic rewrites to move the bounded variable to the LHS.

Stage 3: Translation

Each isolated equation is translated to a circuit using rewrite rules.

Equation Translation

<1> = <2>  →  composition(<2>, <1>)

The RHS becomes the input, and we compose with the LHS operation.

Term Translation

(<1>)  →  <1>

Parentheses are removed during translation.

Identifier Translation

<1>  →  var(<1>)

Identifiers become variable lookups.

Number Translation

<1>  →  const(<1>)

Numbers become constant generators.

Arithmetic Operator Translation

Addition:

<1> + <2>  →  composition(monoidal(<1>, <2>), add)

Subtraction:

<1> - <2>  →  composition(monoidal(<1>, composition(scalar(-1.0), <2>)), add)

Multiplication:

<1> * <2>  →  composition(monoidal(<1>, <2>), multiplication)

Integral Translation

∫ <1> d<2>  →  composition(<1>, register(<2>))

Integration becomes composition with register (shift right).

Derivative Translation

d/d<2> <1>  →  composition(<1>, deregister(<2>))

Differentiation becomes composition with deregister (shift left).

Application and Abstraction Translation

λ<1>.<2> @ (<3>)  →  composition(monoidal(<2>, <3>), convolution(<1>))

Function application becomes convolution.

Stage 4: Unification

After translating each equation to a circuit, we must connect them:

  1. Monoidal combination: Place circuits in parallel using monoidal
  2. Wire matching: Connect outputs to matching inputs
  3. Trace application: Apply trace for feedback (self-referential systems)

Example: Coupled System

Given:

diff(x, t) = y
diff(y, t) = scalar(-1.0, x)

After translation:

circuit_x = composition(var(y), register(t))
circuit_y = composition(composition(var(x), scalar(-1.0)), register(t))

Unified:

unified = trace(trace(
  monoidal(circuit_x, circuit_y)
))

The traces connect:

Complete Example

Input: Exponential Decay

eq = Equation.from_string("diff(y, t) = scalar(-0.1, y)")

Step 1: Resolution

Bounded variable: y (appears in diff on LHS)

Step 2: Isolation

Rewrite to:

y = int(scalar(-0.1, y), t)

Step 3: Translation

Apply rewrite rules:

y = int(scalar(-0.1, y), t)
→ composition(scalar(-0.1, y), register(t))
→ composition(composition(var(y), scalar(-0.1)), register(t))

Step 4: Unification

Since y appears on both sides, apply trace:

trace(composition(composition(var(y), scalar(-0.1)), register(t)))

Final Circuit

circuit = Circuit.from_string(
    "trace(composition(composition(id, scalar(-0.1)), register(t)))"
)

This circuit computes y(t) = y₀ * exp(-0.1 * t).

Translation Rules Summary

Source Target
<1> = <2> composition(<2>, <1>)
<1> + <2> composition(monoidal(<1>, <2>), add)
<1> - <2> composition(monoidal(<1>, scalar(-1.0, <2>)), add)
<1> * <2> composition(monoidal(<1>, <2>), multiplication)
int(<1>, <2>) composition(<1>, register(<2>))
diff(<1>, <2>) composition(<1>, deregister(<2>))
identifier var(identifier)
number const(number)

Normalization

After translation, circuits are normalized using categorical axioms:

  1. Identity elimination: Remove composition(f, id) → f
  2. Constant folding: Combine composition(scalar(a), scalar(b)) → scalar(a*b)
  3. Associativity: Flatten nested compositions
  4. Interchange: Apply interchange law for optimization

Limitations

Current limitations of the compilation process:

  1. Division: <1> / <2> not fully supported
  2. Exponentiation: <1> ^ <2> not fully supported
  3. Complex systems: May require manual intervention
  4. Non-linear terms: Limited support for products of dependent variables

Next Steps