Source lean/Determinize/Finite/Export.lean
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