Documentation

Determinize.Proof.Traces.CompactFiberSoundness

Fiber soundness of the compact replay #

The symbolic lockstep argument for Proof.Traces.outputGivenTraceAt: along the symbolic action of a well-typed source, the compact replay of its realizations, pulled back along retain to detailed traces, is a sound fiber of the detailed joint laws, and the compact replay of the target reproduces the target output on almost every trace.

The compact replay of a symbolic source #

The compact replay of the realized source, averaged over the history of E draws.

Equations
  • One or more equations did not get rendered due to their size.
Instances For
    theorem Determinize.Proof.StepTraces.compactHistoryReplay_next {n : ℕ} {ty : Spec.Paper.Ty} (depth : ℕ) (history : Paper.Symbolic.SampleEnv Paper.primitiveLaws n) (safe : Paper.Symbolic.SampleEnv.DomainSafe Paper.primitiveLaws history) (expression next : Paper.Symbolic.AffineExpr n) (typed : Paper.Symbolic.AffineExpr.WellTyped [] expression ty) (notValue : expression.isValue ≠ true) (actionEq : expression.symbolicReduce = Paper.Symbolic.AffineExpr.SymbolicAction.next next) (tape : DrawTrace) :
    (compactHistoryReplay (depth + 1) history safe expression).kernel tape = (compactHistoryReplay depth history safe next).kernel tape
    theorem Determinize.Proof.StepTraces.compactHistoryReplay_mean {n : ℕ} {ty : Spec.Paper.Ty} {op : Spec.Paper.Op} {affine : List (Paper.Symbolic.Affine n)} {general : List ℝ} {continuation : Paper.Symbolic.Affine n → Paper.Symbolic.AffineExpr n} (depth : ℕ) (history : Paper.Symbolic.SampleEnv Paper.primitiveLaws n) (safe : Paper.Symbolic.SampleEnv.DomainSafe Paper.primitiveLaws history) (expression : Paper.Symbolic.AffineExpr n) (typed : Paper.Symbolic.AffineExpr.WellTyped [] expression ty) (actionEq : expression.symbolicReduce = Paper.Symbolic.AffineExpr.SymbolicAction.mean op affine general continuation) (valid : ∀ᵐ (env : Paper.Env n) ∂Paper.Symbolic.SampleEnv.actualMeasure Paper.primitiveLaws history, Spec.Paper.InDomain op (Paper.Symbolic.AffineExpr.meanParams op affine general env)) (tape : DrawTrace) :
    (compactHistoryReplay (depth + 1) history safe expression).kernel tape = (compactHistoryReplay depth history safe (continuation (Paper.Symbolic.AffineExpr.meanAffine op affine general))).kernel tape
    theorem Determinize.Proof.StepTraces.compactHistoryReplay_sampleE {n : ℕ} {ty : Spec.Paper.Ty} (depth : ℕ) (history : Paper.Symbolic.SampleEnv Paper.primitiveLaws n) (safe : Paper.Symbolic.SampleEnv.DomainSafe Paper.primitiveLaws history) (expression : Paper.Symbolic.AffineExpr n) (typed : Paper.Symbolic.AffineExpr.WellTyped [] expression ty) (notValue : expression.isValue ≠ true) (op : Spec.Paper.Op) (affine : List (Paper.Symbolic.Affine n)) (general : List ℝ) (continuation : Paper.Symbolic.AffineExpr (n + 1)) (actionEq : expression.symbolicReduce = Paper.Symbolic.AffineExpr.SymbolicAction.sampleE op affine general continuation) (extendedSafe : Paper.Symbolic.SampleEnv.DomainSafe Paper.primitiveLaws (history.snoc op (fun (i : Fin (Spec.Paper.affineArity op)) => affine.getD ↑i (0, fun (x : Fin n) => 0)) fun (i : Fin (Spec.Paper.generalArity op)) => general.getD (↑i) 0)) (tape : DrawTrace) :
    (compactHistoryReplay (depth + 1) history safe expression).kernel tape = (compactHistoryReplay depth (history.snoc op (fun (i : Fin (Spec.Paper.affineArity op)) => affine.getD ↑i (0, fun (x : Fin n) => 0)) fun (i : Fin (Spec.Paper.generalArity op)) => general.getD (↑i) 0) extendedSafe continuation).kernel tape
    theorem Determinize.Proof.StepTraces.compactHistoryReplay_sampleG {n : ℕ} {ty : Spec.Paper.Ty} {site : Spec.Paper.DistributionAction × Spec.Paper.Op} (depth : ℕ) (history : Paper.Symbolic.SampleEnv Paper.primitiveLaws n) (safe : Paper.Symbolic.SampleEnv.DomainSafe Paper.primitiveLaws history) (expression : Paper.Symbolic.AffineExpr n) (typed : Paper.Symbolic.AffineExpr.WellTyped [] expression ty) (notValue : expression.isValue ≠ true) (fiber : MeasureTheory.Measure ℝ) (continuation : ℝ → Paper.Symbolic.AffineExpr n) (actionEq : expression.symbolicReduce = Paper.Symbolic.AffineExpr.SymbolicAction.sampleG site fiber continuation) (op : Spec.Paper.Op) (opEq : generationOp expression.skeleton = some op) (value : ℝ) (tape : DrawTrace) :
    (compactHistoryReplay (depth + 1) history safe expression).kernel ((op, value) :: tape) = (compactHistoryReplay depth history safe (continuation value)).kernel tape

    The compact replay read through the retained draws of a detailed trace.

    Equations
    • One or more equations did not get rendered due to their size.
    Instances For
      theorem Determinize.Proof.StepTraces.compactFiber_apply {n : ℕ} (depth : ℕ) (history : Paper.Symbolic.SampleEnv Paper.primitiveLaws n) (safe : Paper.Symbolic.SampleEnv.DomainSafe Paper.primitiveLaws history) (expression : Paper.Symbolic.AffineExpr n) (trace : Trace) :
      (compactFiber depth history safe expression).kernel trace = (compactHistoryReplay depth history safe expression).kernel (retain trace)

      Fiber soundness along the symbolic action #

      theorem Determinize.Proof.StepTraces.compact_exactDepth_fiberSound {n : ℕ} (depth : ℕ) (history : Paper.Symbolic.SampleEnv Paper.primitiveLaws n) (expression : Paper.Symbolic.AffineExpr n) (safe : Paper.SymbolicSoundness.TargetSafety.SafeConfigAt Paper.primitiveLaws depth history expression) :
      FiberSound (compactFiber depth history ⋯ expression) (actualTraceLaw depth history expression) (targetTraceLaw depth history expression)

      The target replays itself #

      Replaying the determinized program along its own compact trace returns its output.

      Specialization to a concrete source #