import Determinize.Spec.Expectationimport Determinize.Spec.Traces.Semanticsimport Determinize.Spec.Inferenceimport Determinize.Spec.FiniteModel.Terminationimport Determinize.Spec.RewardModel.Resultsimport Determinize.Frontend.Inferimport Determinize.Proof.Frontend.Inferenceimport Determinize.Proof.Semantics.Terminationimport Determinize.Proof.Traces.ConditionalLawimport Determinize.Proof.Normalizationimport Determinize.Proof.FiniteModel.Terminationimport Determinize.Proof.RewardModel.FiniteIntegrabilityimport Mathlib.Analysis.Convex.Functionimport Mathlib.Probability.Kernel.Disintegration.StandardBorelimport Mathlib.Probability.Moments.Variance/-!# The theoremsEvery theorem of the development is stated here in full, over the definitions in `Spec/`, andproved by one term from `Proof/`. A reviewer reads the statements and the definitions they use,not the proofs: the command at the end of this file fails the build unless every theorem dependsonly on the standard axioms and its statement uses nothing from `Proof` except proofs.The first four sections state the paper's theorems, under the paper's names. There `e` is`program`, `Determinize(e)` is `program.determinize`, the output law `μ_e` is`bigStepMeasure program`, the joint law `J_e` is `traceAndOutputLaw program` with trace marginal`traceLaw program`, the conditional law `μ_e(· | τ)` is`(traceAndOutputLaw program).condKernel τ`, and `q_e`, `𝔼_ret[e]` and `Var_ret[e]` are`returnProbability`, `returnedExpectation` and `returnedVariance`. The remaining sections stateresults the paper does not.-/namespace Determinize.Theoremsopen MeasureTheory ProbabilityTheory Spec Spec.Paper Spec.Tracesopen scoped ENNReal/-! ## Affinity inference (paper, Section 3) -//-- Inference correctness. Inference fails only when the input has no completion. Otherwise itreturns a completion, typed at the returned type, and every completion lies below it. -/theorem inference_correctness (input : Input) : match Frontend.infer input with | .error _ => ¬ ∃ program : Annotated, Completion input program | .ok (program, ty) => input.Matches program ∧ Typed [] (interpret program) ty ∧ ∀ completion : Annotated, Completion input completion → AffinityLE completion program := Proof.Frontend.infer_correct input/-! ## Determinization (paper, appendix) -//-- Determinization preserves typing. -/theorem determinization_preserves_typing (context : List Ty) (program : Expr) (ty : Ty) (typed : Typed context program ty) : Typed context program.determinize ty := Proof.Paper.typed_determinize typed/-! ## Tracewise soundness (paper, Section 4.2) -//-- The output marginal of the joint law: erasing terminating traces recovers the ordinaryoutput semantics. -/theorem trace_erasure (program : Expr) : (traceAndOutputLaw program).map Prod.snd = bigStepMeasure program := Proof.Traces.correspondence program/-- Equality of total masses. The trace marginal, the joint law and the output law have the sametotal mass: the probability that the program returns. -/theorem equality_of_total_masses (program : Expr) : traceLaw program Set.univ = traceAndOutputLaw program Set.univ ∧ traceAndOutputLaw program Set.univ = returnProbability program := Proof.Traces.total_masses program/-- Trace preservation. Determinization preserves domain safety and the law of terminatingG traces. -/theorem trace_preservation (program : Expr) (typed : Typed [] program (.float .E)) (safe : DomainSafe program) : DomainSafe program.determinize ∧ traceLaw program.determinize = traceLaw program := Proof.Traces.trace_preservation program typed safe/-- Tracewise soundness. For almost every terminating G trace, the source's conditional outputlaw has a finite mean and the target's conditional output law is the Dirac mass at that mean.These are Mathlib's regular conditional distributions of the joint laws over their tracemarginals, unique up to null sets. No global integrability assumption is required. -/theorem tracewise_soundness (program : Expr) (typed : Typed [] program (.float .E)) (safe : DomainSafe program) : ∀ᵐ trace ∂traceLaw program, Integrable id ((traceAndOutputLaw program).condKernel trace) ∧ (traceAndOutputLaw program.determinize).condKernel trace = Measure.dirac (∫ value : ℝ, value ∂(traceAndOutputLaw program).condKernel trace) := Proof.Traces.tracewise_soundness program typed safe/-- Expectation along traces. The expectation conditioned on returning is the integral over thetrace law of the conditional expectation of the output's positive part given the trace, minusthat of its negative part, divided by the return probability. It is meaningful when the returnprobability is positive and the expectation conditioned on returning is well-defined. -/theorem returned_expectation_along_traces (program : Expr) : returnedExpectation program = ((returnProbability program).toReal⁻¹ : EReal) * (((∫⁻ trace, posPartIntegral ((traceAndOutputLaw program).condKernel trace) ∂traceLaw program : ℝ≥0∞) : EReal) - ((∫⁻ trace, negPartIntegral ((traceAndOutputLaw program).condKernel trace) ∂traceLaw program : ℝ≥0∞) : EReal)) := Proof.Traces.returned_expectation_along_traces program/-! ## Global soundness (paper, Section 4.1 and the appendix) -//-- Output-mass preservation. The source and the target return with the same probability. -/theorem output_mass_preservation (program : Expr) (typed : Typed [] program (.float .E)) (safe : DomainSafe program) : returnProbability program.determinize = returnProbability program := Proof.Paper.output_mass_soundness program typed safe/-- Expectation preservation. If the source returns with positive probability and itsexpectation conditioned on returning is well-defined in the extended reals, then the same holdsfor the target, and the two expectations agree. They may be infinite. -/theorem expectation_preservation (program : Expr) (typed : Typed [] program (.float .E)) (safe : DomainSafe program) (positive : 0 < returnProbability program) (defined : HasExpectation (bigStepMeasure program)) : 0 < returnProbability program.determinize ∧ HasExpectation (bigStepMeasure program.determinize) ∧ returnedExpectation program.determinize = returnedExpectation program := Proof.Paper.conditional_extended_expectation_soundness program typed safe positive defined/-- Variance non-increase. If the source returns with positive probability and its output lawhas a finite second moment, then the same holds for the target, and the target's varianceconditioned on returning is at most the source's. -/theorem variance_non_increase (program : Expr) (typed : Typed [] program (.float .E)) (safe : DomainSafe program) (positive : 0 < returnProbability program) (moment : MemLp id 2 (bigStepMeasure program)) : 0 < returnProbability program.determinize ∧ MemLp id 2 (bigStepMeasure program.determinize) ∧ returnedVariance program.determinize ≤ returnedVariance program := Proof.Paper.conditional_variance_soundness program typed safe positive moment/-- Convex function inequality. Every nonnegative convex function integrates to at most as muchunder the target's output law as under the source's. Both sides may be `+∞`. -/theorem convex_function_inequality (program : Expr) (typed : Typed [] program (.float .E)) (safe : DomainSafe program) (φ : ℝ → ℝ) (convex : ConvexOn ℝ Set.univ φ) (nonneg : ∀ value, 0 ≤ φ value) : ∫⁻ value, ENNReal.ofReal (φ value) ∂bigStepMeasure program.determinize ≤ ∫⁻ value, ENNReal.ofReal (φ value) ∂bigStepMeasure program := Proof.Paper.jensen_soundness program typed safe φ convex nonneg/-- Probabilistic type safety. The target is domain-safe, the source either returns or diverges(rejection counts as divergence), and the target returns, and diverges, with the sameprobabilities as the source. -/theorem probabilistic_type_safety (program : Expr) (typed : Typed [] program (.float .E)) (safe : DomainSafe program) : DomainSafe program.determinize ∧ returnProbability program + divergenceProbability program = 1 ∧ returnProbability program.determinize = returnProbability program ∧ divergenceProbability program.determinize = divergenceProbability program := Proof.Paper.probability_preservation program typed safe/-- Trace variance decomposition. If the source returns with positive probability and itsoutput law has a finite second moment, then its variance conditioned on returning is thetarget's plus the average, over the trace law normalized by the return probability, of thevariance of the source's output given the trace. That average is finite. -/theorem trace_variance_decomposition (program : Expr) (typed : Typed [] program (.float .E)) (safe : DomainSafe program) (positive : 0 < returnProbability program) (moment : MemLp id 2 (bigStepMeasure program)) : Integrable (fun trace ↦ variance id ((traceAndOutputLaw program).condKernel trace)) ((returnProbability program)⁻¹ • traceLaw program) ∧ returnedVariance program = returnedVariance program.determinize + ∫ trace, variance id ((traceAndOutputLaw program).condKernel trace) ∂((returnProbability program)⁻¹ • traceLaw program) := Proof.Traces.conditional_variance_soundness program typed safe positive moment/-! ## Further results on returned values (not stated in the paper) -//-- The first equation of `probabilistic_type_safety` at either affinity: a domain-safe,real-typed program either returns or continues forever. Rejection counts as divergence. -/theorem return_or_diverge (affinity : Affinity) (program : Expr) (typed : Typed [] program (.float affinity)) (safe : DomainSafe program) : returnProbability program + divergenceProbability program = 1 := Proof.Paper.return_or_diverge affinity program typed safe/-- `expectation_preservation` for finite expectations. If the source returns with positiveprobability and its output law is integrable, then the returned laws of source and target areprobability laws with finite, equal means. -/theorem finite_expectation_preservation (program : Expr) (typed : Typed [] program (.float .E)) (safe : DomainSafe program) (positive : 0 < returnProbability program) (integrable : Integrable id (bigStepMeasure program)) : 0 < returnProbability program.determinize ∧ IsProbabilityMeasure (returnedLaw program) ∧ IsProbabilityMeasure (returnedLaw program.determinize) ∧ Integrable id (returnedLaw program) ∧ Integrable id (returnedLaw program.determinize) ∧ (∫ x, x ∂returnedLaw program.determinize) = ∫ x, x ∂returnedLaw program := Proof.Paper.returned_expectation_soundness program typed safe positive integrable/-- Determinization preserves the expectation conditioned on acceptance, which is what makes`observe` meaningful: rejection sampling on the determinized program preserves the conditionalexpectation. An observation that fails contributes no output mass, so the return probabilityis the probability of terminating with a real value and every observation on the waysucceeding. Because every Boolean is G information, the same traces are rejected in the sourceand in the target, and both the unnormalized mean and the return probability(`output_mass_preservation`) are preserved; hence so is their quotient(`0` for a program that is always rejected, as `0 / 0 = 0`). -/theorem conditional_expectation_preservation (program : Expr) (typed : Typed [] program (.float .E)) (safe : DomainSafe program) (integrable : Integrable id (bigStepMeasure program)) : (∫ value : ℝ, value ∂bigStepMeasure program.determinize) / (returnProbability program.determinize).toReal = (∫ value : ℝ, value ∂bigStepMeasure program) / (returnProbability program).toReal := Proof.Paper.conditional_expectation_soundness program typed safe integrable/-- The target's output law is the law of the source's conditional mean given the terminatingG trace. Only typing and domain safety are assumed: the target's expectation, when defined, isthe source's conditional mean averaged over the trace law, whether or not the source has anexpectation. -/theorem determinized_output_law (program : Expr) (typed : Typed [] program (.float .E)) (safe : DomainSafe program) : bigStepMeasure program.determinize = (traceLaw program).map fun trace ↦ ∫ value : ℝ, value ∂(traceAndOutputLaw program).condKernel trace := Proof.Traces.determinized_output_law program typed safe/-! ## Finite models (not stated in the paper) -//-- Return, rejection and divergence probabilities of a finite model sum to one. -/theorem finite_mass_balance (model : Spec.FiniteModel.Model) : model.outputMeasure Set.univ + model.rejectionProbability + model.divergenceProbability = 1 := Proof.FiniteModel.mass_balance model/-- Every finite reward model has finite output moments, without extra premises. -/theorem finite_reward_integrability (model : Spec.RewardModel.Model) : model.IntegrableMoments := Proof.RewardModel.integrableMoments modelend Determinize.Theorems/-! The theorems above may depend only on the standard axioms, and their statements may rely on`Proof` only for proofs, which cannot change what they mean: Lean treats any two proofs of aproposition as equal. Following the statements through the declarations they use, stopping atproofs, must reach nothing declared in a `Proof` module. Otherwise the build fails. Theconstructors of an inductive are followed through their types even when they are proofs: theconstructors of a predicate such as `Typed` define it. -/open Lean Elab Command inrun_cmd do let env ← getEnv let theorems := (env.constants.fold (init := #[]) fun found name info ↦ if (`Determinize.Theorems).isPrefixOf name && info.isTheorem then found.push (name, info.type) else found).qsort (Name.lt ·.1 ·.1) let standard := [``propext, ``Classical.choice, ``Quot.sound] let mut sound := true for (name, _) in theorems do let extra := (← collectAxioms name).filter (!standard.contains ·) unless extra.isEmpty do sound := false logError m!"{name} depends on non-standard axioms {extra}" let moduleOf name := (env.getModuleIdxFor? name).bind (env.header.moduleNames[·]?) let mut reached : NameSet := {} let mut pending := theorems.flatMap (·.2.getUsedConstants) while !pending.isEmpty do let name := pending.back! pending := pending.pop -- Declarations outside `Determinize` cannot use ours; those in this file have no module index. if reached.contains name || !(moduleOf name).all (`Determinize).isPrefixOf then continue let some info := env.find? name | continue if ← liftTermElabM (Meta.isProp info.type) then continue reached := reached.insert name if (moduleOf name).any (`Determinize.Proof).isPrefixOf then sound := false logError m!"{name} is declared in a Proof module and is not a proof, but a theorem's \ statement relies on it" let constructors := match info with | .inductInfo type => type.ctors.toArray | _ => #[] let constructorTypes := constructors.flatMap fun constructor ↦ ((env.find? constructor).map (·.type.getUsedConstants)).getD #[] pending := pending ++ constructors ++ constructorTypes ++ info.type.getUsedConstants ++ ((info.value? (allowOpaque := true)).map (·.getUsedConstants)).getD #[] if sound then logInfo m!"{theorems.size} theorems proved, using only {standard}" logInfo m!"Their statements rely on {reached.size} declarations other than proofs, none from Proof"