import Determinize.Finite.Statisticsimport Determinize.Checking.Statisticsimport Determinize.Frontend.Prettyimport Determinize.Finite.Sharednamespace Determinize.Finiteopen Spec.Paper Spec.FiniteModelprivate def rational (q : Rat) : String := if q.den == 1 then toString q.num else s!"{q.num}/{q.den}"private def leanRat (q : Rat) : String := s!"(({q.num} : Rat) / {q.den})"def proofTable (stem claim sizeName allName : String) (size : Nat) : String := let proofs := String.join ((List.range size).map fun i ↦ s!"\ntheorem {stem}_{i} : {claim} (⟨{i}, by decide +kernel⟩ : Fin {sizeName}) := by\n" ++ " decide +kernel\n") let entries := String.intercalate ", " ((List.range size).map fun i ↦ s!"⟨⟨{i}, by decide +kernel⟩, {stem}_{i}⟩") proofs ++ s!"\ndef {stem}Evidence : Vector (Subtype (fun i : Fin {sizeName} => {claim} i)) {sizeName} := \ ⟨#[{entries}], by rfl⟩\n" ++ s!"theorem {stem}Indices : ∀ i : Fin {sizeName}, ({stem}Evidence[i]).val = i := \ by decide +kernel\n" ++ s!"theorem {allName} (i : Fin {sizeName}) : {claim} i := ({stem}Indices i) ▸ \ ({stem}Evidence[i]).property\n"private def listText {α : Type} (render : α → String) (values : List α) : String := "[" ++ String.intercalate ", " (values.map render) ++ "]"private def opText : Op → String | .discrete n => s!"(.discrete {n})" | op => reprStr opprivate def siteText (site : DistributionAction × Op) : String := s!"({reprStr site.1}, {opText site.2})"private partial def valueText : Value → String | .unit => ".unit" | .nil => ".nil" | .bool b => s!"(.bool {b})" | .number q => s!"(.number {leanRat q})" | .pair a b => s!"(.pair {valueText a} {valueText b})" | .cons a b => s!"(.cons {valueText a} {valueText b})" | .inl a => s!"(.inl {valueText a})" | .inr a => s!"(.inr {valueText a})" | .closure body environment => s!"(.closure {Frontend.leanExpression body} {listText valueText environment})" | .recursive body environment => s!"(.recursive {Frontend.leanExpression body} {listText valueText environment})"private def frameText : Frame → String | .unary op => s!"(.unary {reprStr op})" | .left op right environment => s!"(.left {reprStr op} {Frontend.leanExpression right} {listText valueText environment})" | .right op left => s!"(.right {reprStr op} {valueText left})" | .choose yes no environment => s!"(.choose {Frontend.leanExpression yes} {Frontend.leanExpression no} \ {listText valueText environment})" | .letBody body environment => s!"(.letBody {Frontend.leanExpression body} {listText valueText environment})" | .matchSum left right environment => s!"(.matchSum {Frontend.leanExpression left} {Frontend.leanExpression right} \ {listText valueText environment})" | .matchList nilCase consCase environment => s!"(.matchList {Frontend.leanExpression nilCase} {Frontend.leanExpression consCase} \ {listText valueText environment})" | .discrete action => s!"(.discrete ({reprStr action}))" | .draw site pending environment arguments => s!"(.draw {siteText site} {listText Frontend.leanExpression pending} \ {listText valueText environment} {listText leanRat arguments})"def stateText : State → String | .rejected => ".rejected" | .eval expression environment stack => s!"(.eval {Frontend.leanExpression expression} {listText valueText environment} \ {listText frameText stack})" | .deliver value stack => s!"(.deliver {valueText value} {listText frameText stack})"def kindText : StateKind → String | .transient => ".transient" | .rejected => ".rejected" | .returned reward => s!"(.returned {leanRat reward})"def candidateText (candidate : Candidate) : String := let (data, shared) := (Shared.candidate candidate).run {} "import Determinize.Finite.Graph\n\n" ++ "open Determinize.Finite Determinize.Spec.Paper Determinize.Spec.FiniteModel\n\n" ++ "set_option maxRecDepth 100000\nset_option maxHeartbeats 0\nset_option Elab.async false\n\n" ++ shared.text data/-- Export kernel-checkable replay and paper-semantics correspondence. -/def replayCertificateText (source : Spec.Paper.Core) (subject : Subject) (candidate : Candidate) : String := let indices := candidate.states.toList.map fun state ↦ let destinations : List Nat := match step state with | .ok (.next _ outcomes) => outcomes.map fun (outcome : Rat × State) ↦ (candidate.states.toList.findIdx? fun s ↦ decide (s = outcome.2)).getD 0 | _ => [] "#[" ++ String.intercalate ", " (destinations.map toString) ++ "]" let indices := "#[" ++ String.intercalate ", " indices ++ "]" let rowProofs := proofTable "row" "rowClaim" "candidate.states.size" "allRows" candidate.states.size (candidateText candidate).replace "import Determinize.Finite.Graph" "import Determinize.Checking.FiniteModel" ++ s!"\ndef checkedSource : Expr Rat := {Frontend.leanExpression source}\n" ++ s!"def checkedSubject : Subject := {reprStr subject}\n" ++ s!"def successorIndices : Vector (Array Nat) candidate.states.size := ⟨{indices}, by rfl⟩\n" ++ "\nabbrev rowClaim (i : Fin candidate.states.size) : Prop := candidate.IndexedStateValid\n" ++ " (fun i k => successorIndices[i][k]!) i\n" ++ rowProofs ++ "\ntheorem indexedReplay : candidate.IndexedReplayValid checkedSource checkedSubject\n" ++ " (fun i k => successorIndices[i][k]!) :=\n" ++ " indexedStates_valid candidate checkedSource checkedSubject _ (by decide +kernel) allRows\n" ++ "\ntheorem graphValid : candidate.GraphValid :=\n" ++ " indexedReplay_valid candidate checkedSource checkedSubject _ indexedReplay\n\nabbrev model : \ Model := candidate.graphModel graphValid\n" ++ "\ntheorem modelMatches : model.Matches (checkedSubject.program checkedSource) :=\n" ++ " Determinize.Proof.FiniteModel.indexedReplay_matches candidate _ indexedReplay\n" ++ "\n#print axioms graphValid\n#print axioms modelMatches\n"structure Files where candidate : String transitions : String labels : String positiveRewards : String negativeRewards : String/-- Structural validation only; this does not check machine transition correctness. -/def render (candidate : Candidate) (includeCandidate : Bool := true) : Except String Files := do let size := candidate.states.size if size == 0 || candidate.initial ≥ size || candidate.rows.size != size then throw "invalid candidate dimensions" let mut transitions := "dtmc\n" let mut labels := "#DECLARATION\ninit returned rejected done\n#END\n" let mut positiveRewards := "" let mut negativeRewards := "" for i in [:size] do let row := candidate.rows[i]?.getD ⟨.rejected, #[]⟩ let mut mass := (0 : Rat) let mut targets : List Nat := [] for edge in row.edges do if edge.target ≥ size || edge.probability ≤ 0 || targets.contains edge.target then throw "invalid or duplicate candidate edge" targets := edge.target :: targets mass := mass + edge.probability if mass != 1 then throw "candidate row is not normalized" let mut names := if i == candidate.initial then ["init"] else [] match row.kind with | .transient => for edge in row.edges do transitions := transitions ++ s!"{i} {edge.target} {rational edge.probability}\n" | terminal => unless row.edges == #[⟨i, 1⟩] do throw "candidate terminal state is not absorbing" transitions := transitions ++ s!"{i} {size} 1\n" match terminal with | .returned reward => names := names ++ ["returned"] if reward > 0 then positiveRewards := positiveRewards ++ s!"{i} {rational reward}\n" if reward < 0 then negativeRewards := negativeRewards ++ s!"{i} {rational (-reward)}\n" | _ => names := names ++ ["rejected"] if !names.isEmpty then labels := labels ++ s!"{i} {String.intercalate " " names}\n" transitions := transitions ++ s!"{size} {size} 1\n" labels := labels ++ s!"{size} done\n" return ⟨if includeCandidate then candidateText candidate else "", transitions, labels, positiveRewards, negativeRewards⟩/-- Call only with complete exploration data. No files are written if rendering fails. -/def write (outputPath : System.FilePath) (source : Spec.Paper.Core) (subject : Subject) (candidate : Candidate) (_valid : candidate.ReplayValid source subject) (certificates : Bool := true) : IO Unit := do let files ← IO.ofExcept (render candidate false) if let some parent := outputPath.parent then IO.FS.createDirAll parent for (suffix, content) in [(".tra", files.transitions), (".lab", files.labels), (".positive.state.rew", files.positiveRewards), (".negative.state.rew", files.negativeRewards)] do IO.FS.writeFile (outputPath.toString ++ suffix) content if certificates then IO.FS.writeFile (outputPath.toString ++ ".candidate.lean") (candidateText candidate) IO.FS.writeFile (outputPath.toString ++ ".replay.lean") (replayCertificateText source subject candidate)/-- The closing theorems of a result certificate, whose statements use only `Spec` definitions,`checkedSource`, `checkedSubject` and rational literals. `printedStatistics` gives the return massand the first and second moments of the selected program's output law; its proof decides thatthe certificate's `statistics` equal the literals. When the return mass is positive,`printedConditionalMoments` follows from it and gives the conditional mean and variance. -/def printedText (statistics : OutputStatistics) : String := let literal := s!"⟨{rational statistics.returnMass}, {rational statistics.firstMoment}, \ {rational statistics.secondMoment}⟩" let program := "(checkedSubject.program checkedSource)" let conditional := match statistics.conditionalMean, statistics.conditionalVariance with | some mean, some variance => "\ntheorem printedConditionalMoments :\n" ++ s!" Determinize.Spec.returnedExpectation {program} = (({rational mean} : Rat) : ℝ) ∧\n" ++ s!" Determinize.Spec.returnedVariance {program} = \ (({rational variance} : Rat) : ℝ) :=\n" ++ " Determinize.Proof.FiniteModel.statistics_returned_moments _ _ printedStatistics\n" ++ " (by decide +kernel) (by decide +kernel)\n" ++ "\n#print axioms printedConditionalMoments\n" | _, _ => "" "\ntheorem printedStatistics :\n" ++ s!" ({literal} : Determinize.Spec.FiniteModel.OutputStatistics).Matches\n" ++ s!" (Determinize.Spec.Paper.bigStepMeasure {program}) :=\n" ++ s!" (by decide +kernel : statistics = {literal}) ▸ outputStatistics\n" ++ "\n#print axioms printedStatistics\n" ++ conditional/-- A standalone certificate for the selected program's output moments and the model'stermination probabilities, ending with `printedText`. -/def resultCertificateText (source : Spec.Paper.Core) (subject : Subject) (candidate : Candidate) (model : Model) (termination : Proof.FiniteModel.TerminationCertificate model) : String := let certificate := termination.output let stateProofs := proofTable "result" "resultClaim" "model.size" "allResults" model.size let rejection := "#[" ++ String.intercalate ", " ((List.ofFn termination.rejection).map leanRat) ++ "]" let vector := fun moment ↦ "#[" ++ String.intercalate ", " ((List.ofFn (certificate.values moment)).map leanRat) ++ "]" let ranks := "#[" ++ String.intercalate ", " ((List.ofFn certificate.rank).map toString) ++ "]" let nextEntries := (List.ofFn certificate.next).map fun j ↦ s!"⟨{j.val}, by decide +kernel⟩" let next := "#[" ++ String.intercalate ", " nextEntries ++ "]" let dead := "#[" ++ String.intercalate ", " ((List.ofFn certificate.dead).map toString) ++ "]" (replayCertificateText source subject candidate).replace "import Determinize.Checking.FiniteModel" "import Determinize.Checking.Statistics" ++ "\nopen Determinize.Proof.FiniteModel\n" ++ s!"\ndef nextStates : Vector (Fin model.size) model.size := ⟨{next}, by rfl⟩\n" ++ "\ndef result : MomentCertificate model where\n" ++ s!" dead := fun i => {dead}[i.val]!\n" ++ s!" rank := fun i => {ranks}[i.val]!\n" ++ " next := fun i => nextStates[i]\n" ++ " values := fun moment i => (match moment with\n" ++ s!" | .mass => {vector .mass}\n | .first => {vector .first}\n" ++ s!" | .second => {vector .second})[i.val]!\n" ++ "\ndef termination : TerminationCertificate model := ⟨result, fun i => " ++ rejection ++ "[i.val]!⟩\n" ++ "\nabbrev resultClaim (i : Fin model.size) : Prop := candidate.QueryStateValid graphValid \ termination i\n" ++ stateProofs ++ "\ntheorem terminationAccepted : \ Determinize.Checking.checkTermination model termination = true :=\n" ++ " (Determinize.Checking.checkTermination_valid model termination).mpr\n" ++ " (sparseResults_valid candidate graphValid termination allResults)\n" ++ "\ntheorem resultAccepted : Determinize.Checking.checkStatistics model result = true := by\n" ++ " exact (Determinize.Checking.checkStatistics_valid model result).mpr\n" ++ " ((Determinize.Checking.checkTermination_valid model termination).mp \ terminationAccepted).1\n" ++ "\ndef statistics := result.statistics model\n" ++ "\ntheorem outputStatistics : statistics.Matches (bigStepMeasure (checkedSubject.program \ checkedSource)) :=\n" ++ " Determinize.Checking.checked_statistics ⟨model, modelMatches⟩ result resultAccepted\n" ++ "\ntheorem expectedReward :\n" ++ " MeasureTheory.Integrable id (bigStepMeasure (checkedSubject.program checkedSource)) ∧\n" ++ " (∫ value : ℝ, value ∂bigStepMeasure (checkedSubject.program checkedSource)) =\n" ++ " (statistics.firstMoment : ℝ) := by\n" ++ " exact ⟨modelMatches.2 ▸ Determinize.Proof.FiniteModel.integrable_outputMeasure model, \ outputStatistics.first⟩\n" ++ "\ntheorem conditionalVariance (positive : 0 < statistics.returnMass) :\n" ++ " ProbabilityTheory.variance id ((bigStepMeasure (checkedSubject.program checkedSource) \ Set.univ)⁻¹ •\n" ++ " bigStepMeasure (checkedSubject.program checkedSource)) =\n" ++ " ((statistics.secondMoment / statistics.returnMass - (statistics.firstMoment / \ statistics.returnMass)^2 : Rat) : ℝ) :=\n" ++ " Determinize.Checking.checked_conditionalVariance ⟨model, modelMatches⟩ result resultAccepted \ positive\n" ++ "\ntheorem terminationProbabilities : (termination.statistics model).Matches model :=\n" ++ " Determinize.Checking.checked_termination model termination terminationAccepted\n" ++ "\n#print axioms terminationProbabilities\n" ++ "\n#print axioms resultAccepted\n#print axioms expectedReward\n" ++ "#print axioms outputStatistics\n#print axioms conditionalVariance\n" ++ printedText (certificate.statistics model)def writeResult (outputPath : System.FilePath) (source : Spec.Paper.Core) (subject : Subject) (candidate : Candidate) (valid : candidate.ReplayValid source subject) (limits : SolveLimits := {}) : IO Rat := do let model := candidate.toModel valid let certified ← IO.ofExcept (solveStatistics model limits) let termination ← IO.ofExcept (solveTermination model certified limits) let outcomes := termination.val.statistics model let certificate := certified.val let statistics := certificate.statistics model let rankBound := (List.ofFn certificate.rank).foldl max 0 let optional := fun value : Option Rat ↦ match value with | none => Lean.Json.null | some q => Lean.toJson (rational q) let metadata := Lean.Json.mkObj [ ("answer", Lean.toJson (rational statistics.firstMoment)), ("return_mass", Lean.toJson (rational statistics.returnMass)), ("kernel_checked", Lean.toJson false), ("certificate_status", Lean.toJson "generated"), ("termination_statistics_scope", Lean.toJson "graph"), ("rejection_probability", Lean.toJson (rational outcomes.rejectionProbability)), ("divergence_probability", Lean.toJson (rational outcomes.divergenceProbability)), ("second_moment", Lean.toJson (rational statistics.secondMoment)), ("conditional_mean", optional statistics.conditionalMean), ("conditional_variance", optional statistics.conditionalVariance), ("subject", Lean.toJson (if subject == .source then "source" else "determinized")), ("states", Lean.toJson model.size), ("rank_bound", Lean.toJson rankBound)] write outputPath source subject candidate valid IO.FS.writeFile (outputPath.toString ++ ".result.lean") (resultCertificateText source subject candidate model termination.val) IO.FS.writeFile (outputPath.toString ++ ".result.json") (metadata.pretty ++ "\n") return statistics.firstMomentend Determinize.Finite