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 #
noncomputable def
Determinize.Proof.StepTraces.compactHistoryReplay
{n : ℕ}
(depth : ℕ)
(history : Paper.Symbolic.SampleEnv Paper.primitiveLaws n)
(safe : Paper.Symbolic.SampleEnv.DomainSafe Paper.primitiveLaws history)
(expression : Paper.Symbolic.AffineExpr n)
:
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_apply
{n : ℕ}
(depth : ℕ)
(history : Paper.Symbolic.SampleEnv Paper.primitiveLaws n)
(safe : Paper.Symbolic.SampleEnv.DomainSafe Paper.primitiveLaws history)
(expression : Paper.Symbolic.AffineExpr n)
(tape : DrawTrace)
:
(compactHistoryReplay depth history safe expression).kernel tape = (Paper.Symbolic.SampleEnv.actualMeasure Paper.primitiveLaws history).bind fun (env : Paper.Env n) =>
Traces.outputGivenTraceAt depth (Paper.Symbolic.AffineExpr.realize env expression) tape
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
noncomputable def
Determinize.Proof.StepTraces.compactFiber
{n : ℕ}
(depth : ℕ)
(history : Paper.Symbolic.SampleEnv Paper.primitiveLaws n)
(safe : Paper.Symbolic.SampleEnv.DomainSafe Paper.primitiveLaws history)
(expression : Paper.Symbolic.AffineExpr n)
:
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_exactZero_fiberSound
{n : ℕ}
(history : Paper.Symbolic.SampleEnv Paper.primitiveLaws n)
(expression : Paper.Symbolic.AffineExpr n)
(safe : Paper.SymbolicSoundness.TargetSafety.SafeConfigAt Paper.primitiveLaws 0 history expression)
:
FiberSound (compactFiber 0 history ⋯ expression) (actualTraceLaw 0 history expression)
(targetTraceLaw 0 history expression)
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 #
theorem
Determinize.Proof.StepTraces.measurableSet_selfReplay
(depth : ℕ)
(target : Spec.Paper.Expr)
:
MeasurableSet {p : Output | Traces.outputGivenTraceAt depth target (retain p.1) = MeasureTheory.Measure.dirac p.2}
theorem
Determinize.Proof.StepTraces.target_selfReplay
{n : ℕ}
(depth : ℕ)
(history : Paper.Symbolic.SampleEnv Paper.primitiveLaws n)
(expression : Paper.Symbolic.AffineExpr n)
(safe : Paper.SymbolicSoundness.TargetSafety.SafeConfigAt Paper.primitiveLaws depth history expression)
:
∀ᵐ (p : Output) ∂targetTraceLaw depth history expression, Traces.outputGivenTraceAt depth
(Paper.Symbolic.AffineExpr.realize (Paper.Symbolic.SampleEnv.meanEnvironment Paper.primitiveLaws history)
expression).determinize
(retain p.1) = MeasureTheory.Measure.dirac p.2
Replaying the determinized program along its own compact trace returns its output.
Specialization to a concrete source #
theorem
Determinize.Proof.StepTraces.compactHistoryReplay_nil
(depth : ℕ)
(source : Spec.Paper.Expr)
(tape : DrawTrace)
:
(compactHistoryReplay depth Paper.Symbolic.SampleEnv.nil domainSafe_nil
(Paper.Symbolic.AffineExpr.ofExpr source)).kernel
tape = Traces.outputGivenTraceAt depth source tape
theorem
Determinize.Proof.StepTraces.safeConfig_of_source
(source : Spec.Paper.Expr)
(typed : Spec.Paper.Typed [] source (Spec.Paper.Ty.float Spec.Paper.Affinity.E))
(sourceSafe : Spec.Paper.DomainSafe source)
(depth : ℕ)
:
theorem
Determinize.Proof.StepTraces.compact_exactDepth_source_fiberSound
(source : Spec.Paper.Expr)
(typed : Spec.Paper.Typed [] source (Spec.Paper.Ty.float Spec.Paper.Affinity.E))
(sourceSafe : Spec.Paper.DomainSafe source)
(depth : ℕ)
:
FiberSound (compactFiber depth Paper.Symbolic.SampleEnv.nil domainSafe_nil (Paper.Symbolic.AffineExpr.ofExpr source))
(exactMeasure depth source) (exactMeasure depth source.determinize)
theorem
Determinize.Proof.StepTraces.target_selfReplay_source
(source : Spec.Paper.Expr)
(typed : Spec.Paper.Typed [] source (Spec.Paper.Ty.float Spec.Paper.Affinity.E))
(sourceSafe : Spec.Paper.DomainSafe source)
(depth : ℕ)
:
∀ᵐ (p : Output) ∂exactMeasure depth source.determinize, Traces.outputGivenTraceAt depth source.determinize (retain p.1) = MeasureTheory.Measure.dirac p.2